PintOS | Project1. Threads | Advanced Scheduling (4.4 BSD)

핀토스 프로젝트에서는 4.4 BSD 스케줄러를 채택하고 있다. BSD는 Berkeley Software Distribution의 약자이고, UNIX의 한 버전인 4.4 BSD에서 사용되는 프로세스 스케줄러라고 한다. 앞서 공부했던 MLFQ 기반에서 변형된 버전이다. 

 

이번 기록에서는 4.4 BSD를 구현하면서 이해한 바와 고민했던 내용들을 적어보는 시간을 가져보고자 한다.

---

BSD의 스케줄링 철학

BSD 스케줄러의 핵심 철학은 다음과 같다. 

1. If the thread is nicer, lower the priority.
2. If the thread have been using lots of CPU recently, lower the priority.
3. For all threads, priority is recalculated once in every fourth clock tick.
4. The result is truncated to its nearest integer.

BSD도 우선순위 스케줄링의 일종인 MLFQS에 기반을 두고 있으므로 Priority가 더 높은 작업이 먼저 수행되며, Priority가 같다면 라운드로빈 방식을 통해 순차적으로 작업을 수행한다.

 

결과적으로 작업별로 이 Priority 값을 어떻게 구하는지, 왜 그렇게 하는지를 이해하는 것이 a to z라고 볼 수 있을 것이다. 

4번을 제외한 1, 2, 3번 규칙을 하나씩 살펴보면서 how와 why를 고민해보자. 

 

[철학 3] For all threads, priority is recalculated once in every fourth clock tick 

3번부터 보자. BSD 스케줄러는 기존 MLFQ와 달리 Boost(모든 쓰레드의 Priority를 max값으로 올려주는 조치)를 해주는 과정이 없다.

대신 4 ticks마다 한번씩 모든 쓰레드의 Priority를 업데이트 해준다. 

 

그 말은 무슨 뜻일까? Priority 도출 공식을 살펴보면, PRI_MAX(= 최대 우선순위값 = 63)는 상수이므로 recent_cpu와 nice라는 값 말고는 Priority에 영향을 줄 요인이 없다.

 

즉, recent_cpu와 nice 라는 변수가 4 ticks 이내에 바뀔 수 있음을 의미한다. recent_cpu와 nice 변수를 적절히 조정해줌으로써 응답시간과 반환시간 측면에서 효율적인 스케줄링을 자동으로 실현한다는 게 해당 철학의 핵심이다. 

 

 

[철학 1] If the thread is nicer, lower the priority.

nicer하다는 게 무슨 말일까? BSD 스케줄러의 쓰레드는 MLFQ에서 필수적인 recent_cpu 외에도, nice라는 특수한 필드를 갖는다. 

 

 

nicer 하다는 것은 CPU 양보를 잘해주는 작업이라는 의미이다. 말 그대로 나이스한 정도라는 뜻에서 이런 네이밍이 붙었다. nice 변수값이 클 수록 nicer하며, 그럴수록 우선순위가 빠르게 하락하는 경향이 있음을 위 Priority 수식을 통해 유추 가능하다.

 

nice 변수값은 [-20, 20] 의 범위를 갖는다. 만일 nice 값이 20이라면, 즉 해당 작업이 매우 nice하다면 priority는 철학 3번에 의해 4 tick 마다 40씩 떨어지게 될 것이다. 

 

운영체제 작업관리자에서 특정 작업의 우선순위를 [높음, 중간, 낮음] 으로 설정할 수 있다고 하는데, 아마 그게 이 nice 값을 조정하는 것일거라는 추측을 하고있다. 

 

 

[철학 2] If the thread have been using lots of CPU recently, lower the priority.

 

nice는 시스템이나 유저가 임의로 변경하는 값이므로 nice == 0으로 가정하고 이어서 살펴보자.

 

그렇다면 recent_cpu가 바뀌는 경우는 오직 두 가지이다. 

1. 1 tick에 한 번씩, 해당 쓰레드가 CPU를 점유하고 있는 경우 +1 카운트된다.
2. 1초에 한 번씩, 위 공식에 따라 recent_cpu를 재계산한다. 이때, decay라는 특수한 감쇠율에 의해 감쇠된다. 

1번은 그렇다 치고, 2번은 왜 필요한걸까? 

 

우선, decay(감쇠율)를 구하는 공식은 다음과 같다. 

decay는 load_average라는 인자 크기에 따라 [0, 1) 의 범위를 갖는다는 점을 알 수 있다. 

 

그럼 load_average를 구해야한다는 말이다. load_average는 다음과 같은 공식으로 구해진다. 

new_load_average = (1 - α) * old_load_average + α * ready_threads

/* 
ready_threads = ready list에 존재하는 쓰레드의 수 + 현재 실행중인 쓰레드 수 (idle은 제외)
*/

 

(핀토스 과제에서는 가중치 α를 1/60 로 지정하고 있다.)

 

load_avg는 recent_cpu를 갱신해주는 1초마다 재계산이 필요하며, 계산을 거듭할수록 ready_threads에 매우 천천히 가까워진다. 

 

 

여기서부터 역으로 올라가보자. load_average 는 부하 평균, 즉 현재 시스템에 작업 부하가 얼마나 큰지를 나타낸다.

(처음에는 0으로 세팅되어 있고, 작업이 하나 추가될 때마다 ready_threads가 하나씩 올라갈 것이다.) 

 

만일 시스템에 부하가 크다면 load_average 도 커질 것이고, 그럴수록 decay 값은 1에 가까워지게 된다. 

(반대로 load_average가 0인 초기상태에서 decay 값은 0이다.)

 

decay(감쇠율) 값이 1에 가까워질 수록, recent_cpu는 '덜' 감쇠된다. 즉, decay가 낮을 때보다 recent_cpu는 더 큰 상태이다. 

그 결과 Priority는 더 빠르게 하락한다. (Priority = PRI_MAX - (recent_cpu/4) - (2*nice) 이므로)

 

중간 다리를 제하고 원인과 결과만 보자면 '시스템 부하가 클수록, CPU 점유중인 작업의 우선순위를 더 빠르게 내린다' 라는 결론이 나온다. 

 

이는 작업량이 너무 많을 때, 우선순위상 뒤에 있는 작업이 starvation에 빠지는 것을 방지하고 최대한 공정하게 cpu를 분배하기 위한 조치이다. MLFQ 이론에서 이러한 역할은 Boost를 통해서 수행하는데, 모든 작업의 우선순위를 최대값으로 올린다는 것은 비교적 오버헤드가 크기 때문에, 이렇게 동적으로 조정해주는 것으로 판단된다. 

 

카이스트 과제에서는 decay를 통한 recent cpu 조정을 Running 쓰레드 외에도 ready list와 sleep list에 있는 쓰레드에도 적용해줘야 한다. 처음에는 이 부분이 CPU를 빠르게 양보하게 만든다는 decay의 원래 취지에 어긋나는거 아닌가? 라는 생각을 했다. 

 

그러나 CPU 점유중인 쓰레드는 매 tick마다 +1되고 있으며, 그렇다면 똑같은 감쇠율이 적용되더라도 CPU 점유중인 쓰레드가 비교적 높은 recent_cpu를 유지할 수밖에 없으므로 취지에 크게 어긋나지 않는다. 오히려, Blocked 되었다가 돌아온 작업이 시스템 부하량과 관계없이 엉뚱한 Priority 자리에 배정받는 것이 더 큰 문제로 이어질 수도 있기 때문에, 시스템에 존재하는 모든 작업에 decay를 적용해주는 것이 합리적이라는 결론을 내리게 되었다. 

 

 

구현 방법

1. thread 구조체에 recent_cpu와 nice 필드를 추가한다. (따라서 자연스럽게 init과 thread 생성 함수에도 이를 반영해준다.)
2. 다른 스케줄링 기법(ex. donation을 활용한 priority 스케줄링)과의 혼동을 막기 위해, 적절한 위치에 조건문을 활용한 분기처리를 해준다. (mlfqs 모드일 때 true가 되는 변수를 활용하여, lock 함수들에 제한을 걸어놓는다던지..)
3. timer_interrupt 에 위 논리를 구현한다.
   • timer_interrupt 논리 구현을 위해 필요한 함수들을 구현한다.

타이머 프리퀀시(TIMER_FREQ)는 100이다. (핀토스에선 1초 = 100 tick)

 

 

 

구현 당시 이슈

BSD 스케줄링을 구현함에 있어서 역시나 많은 이슈가 있었다.

 

1. Recent CPU 재계산을 어느 범위까지 해주어야 하는가?

첫번째로는 위에서도 적은 바 있듯, recent_cpu 재계산을 어느 작업까지 해줘야 하는가를 결정하는게 어려웠다. 시행착오 끝에 모든 쓰레드에 recent_cpu 재계산을 해줘야 함을 알게 되었다. 

 

매우 간단하게 적었지만, 이 사실을 바로 깨닫는건 쉽지 않고, 또 어찌보면 설계자의 마음에 달린 문제이기 때문에 수많은 FAIL을 마주한 다음에야 알 수 있는 영역이었다. 테스트할 때마다 짧게는 1분 ~ 길면 20분이 걸릴 때도 있어서 마음 졸이면서 수정했던 기억이 있다 ㅎㅎ

 

 

2. int만 활용해서 fixed point 연산해주기

핀토스 OS는 float 연산을 지원하지 않는다. 가끔 임베디드 시스템이나 OS 등 매우 예민하고 정밀한 프로그램 중에, 효율성을 위해 이런 경우가 있는 것 같다. 왜냐하면 정수부와 실수부를 인식하고 처리하는 것도 또 하나의 오버헤드이기 때문.. 그래서 shift 연산(2 << 14)을 활용하여 분수 계산을 처리해주어야 했다. 

이 과정에서 정말x10 많은 실수가 나왔는데.. 사실 꼼꼼하면 아무 문제 없었겠지만, 사람인데 어떻게 실수가 없겠는가.. 아마 우리반 사람들을 가장 많이 괴롭힌 문제일 거다. 그래도 그 양이 많지 않아 다들 금방 찾기는 했다. 

 

3. 함수을 얼마나 활용해야 하는가?

2번 이슈에서 연계된 이슈이다. fixed point 연산 과정에서 실수를 줄이기 위해 모든 연산을 함수로 정의해놓고 함수만을 활용해서 사칙연산을 수행하자고 결론 내렸다.

 

그 결과 Priority = PRI_MAX - (recent_cpu/4) - (nice*2) 라는 간단한 식이 아래와 같은 괴랄한 형태로 바뀌게 되었다. 

 

코치님께서 현업에서는 실수를 줄이고 의도를 명확하게 하기 위해, 이와 같이 함수를 활용하는 경우도 꽤 있다고 하셨다.

그러나 한편으로는, 가면 갈수록 '사람이 읽기 좋은 코드'의 중요성도 점점 커지고 있다는 말씀도 주셨다. 

 

이 가치들 사이에서 균형을 잘 잡는 것이 중요한 것 같다. 

 

예를 들어, fixed point로 표현된 수와 그냥 정수 사이의 연산 중 일부는 그냥 연산자를 활용해도 되는 경우가 있다(곱셈 연산, fixed point value를 정수로 나누는 경우). 또, fixed point 끼리의 덧셈 뺄셈도 그냥 정수간의 연산처럼 취급해도 된다. 

 

이를 잘 활용하면, 

 

비교적 균형이 더 잘잡힌 코드로 바꿀 수 있다. 

 

 

4. 방어코드 세우기 (Priority가 범위를 벗어나는 경우 처리)

특정 쓰레드가 장기간 CPU를 점유하여 recent_cpu가 매우 높은 경우, 혹은 nice 값이 계속해서 반영되는 경우에 Priority가 [0, 63] 범위를 벗어나게 될 수도 있다. 이러한 경우는 테스트에서 고려하지 않지만, 실제 시스템이라면 Boost와 같은 초기화 메커니즘이 없기 때문에 특정 작업은 무한 Starvation에 빠지거나, 특정 작업만 CPU를 독점하게 되는 상황이 발생할 수 있다.

 

따라서 방어코드를 세워주는 것이 좋은 것 같다. 

 

 

이런 함수를 정의해준 다음에, Priority를 갱신해주는 함수 적절한 곳에 넣어준다. 

 

 

 

 

 

 

 

---