(2021.10.17) 고오급 스케줄러 (Mlfqs) 가이드라인

이건 내가 처음 해보는 과제이다. 이전 것들까지는 지난 핀토스 때도 구현했던 것들이어서 어느 정도 간단하게 끝났지만 이번 것은 정말 미지의 영역이다. 때문에 디버깅에 시달릴 것으로 보인다. 또, 지금까지 테스팅을 여러 번 돌려본 결과 시간이 정~말 길게 걸린다. 다른 것들은 5초 내로 끝나는 데에 비해 한 1분? 정도의 소요 시간에 테스트 케이스 하나가 끝난다. 그 결과도 어떻게 판단하는지 모호하다. 다른 케이스는. ck 파일의 내용대로 나오면 정답이라는 명확한 기준이 있는데 이건 뭔가 자체적으로 시뮬레이션을 돌리는것인지 .ck 파일이 실행 프로그램처럼 되어있다. 때문에 디버깅을 어떻게 할지도 감이 잘 안 잡힌다. 뭐, 언제나 그랬듯이, 맨 땅에 헤딩 말고는 답이 없다. 일단 부딪혀 보자.

 

매뉴얼을 읽어보면 고오급 스케줄러를 구현해야 한단다. 지금까지의 테스트 케이스를 살펴보면 모두 mlfqs 환경이 아닌 경우에서 돌아가는 것, 즉 기본적인 priority 스케줄링을 기반으로 돌아가는 것을 상정했으나, mlfqs 테스트 케이스는 옵션으로 mlfqs를 주어 환경을 다르게 한다. 코드를 읽어보면, thread_mlfqs 변수가 true로 설정되어 조건에 따라 다르게 동작할 수 있을 것으로 보인다. 일단 기억을 해 두자.

 

구현을 해야 하는 스케줄러는 4.4BSD 스케줄러이다. 우선 다음의 안내 사항에서

The advanced scheduler is not used in any later project.

 

차후 프로젝트에서는 사용되지 않는다고 하니 해당 테스트 케이스만 잘 돌아가도록 해 놓으면 나머지 프로젝트에서는 봉인시켜 놓으면 된다는 것이다. 또한 우리가 지난 포스팅까지 골머리를 썩게 한 priority donation 또한

The 4.4BSD scheduler does not include priority donation.

 

사용되지 않도록 할 필요가 있다. thread_mlfqs 변수에 따라 실행되는 것을 조정하도록 해야 할 것이다.

동작 방식

일반적으로 각 Thread의 I/O와 CPU 필요양은 시간에 따라 변하기 마련이다. 이러한 Thread의 변화에 적응하여 어떤 Thread가 실행되어야 하는지를 계속 계산해야 하는 것이 옳게 설계된 스케줄링 기법이라고 한다. 우리가 구현해야 하는 4.4BSD 스케줄러는 이러한 요구 사항을 맞추기 위해 Multilevel feedback queue schedule 방식을 채택한다고 한다. 그래서 이를 줄인 것이 MLFQS인 것이다. 뜻을 그대로 풀어쓰면 여러 단계의 피드백 큐가 존재하는 스케줄링 방식이다. 

 

해당 "단계"를 나누는 것은 직관적으로 priority, 즉 우선도가 되어야 할 것 같고 매뉴얼에도 그렇게 나와있다. 각 큐마다 지정된 우선도가 있어 해당 우선도를 가진 Thread를 큐에 넣고 관리하는 것이다. 그리고 스케줄러가 다음 실행되어야 할 Thread를 선택할 때, 가장 높은 우선도의 큐에서 Round-Robin 형태로 가져오는 것이다. 여기까지는 일반적인 priority 스케줄링이랑 큰 차이가 없어 보이지만 중요한 점이 있다. 바로 Thread에서 자체적으로 우선도를 설정할 수 없다는 점이다. 매뉴얼에도 나와 있듯 :

When the 4.4BSD scheduler is enabled, threads no longer directly control their own priorities. The priority argument to thread_create() should be ignored, as well as any calls to thread_set_priority(), and thread_get_priority() should return the thread's current priority as set by the scheduler.

 

각 Thread의 우선도는 스케줄러에서 관리하게 되는 것이 가장 큰 차이다. 그럼 스케줄러 입장에서 볼 때 각 Thread의 priority는 어떻게 계산하여 관리하는 것일까? 각 Thread의 변수를 조합해 우선도를 계산하는 다음의 공식이 매뉴얼에 나와 있다.

priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)

 

아직까지는 nice와 recent_cpu라는 변수가 뭔지 모르겠다. 다시 매뉴얼을 들여다 본다.

nice 변수

Thread가 다른 Thread들에게 얼마나 "친절"한지를 나타내는 변수라고 한다. 좀 더 풀어서 설명하면 얼마나 CPU를 양도하려고 하는지를 나타내는 척도인 것이다. 어떤 Thread가 다른 Thread에게 많이 "친절"하면, CPU를 많이 양도할 것이다. 그렇지 않다면, 더 많이 CPU를 가지고 있을 것이며, 나아가 다른 Thread로부터 CPU를 뺏어오려고 할 것이다. 위의 계산식에서도 이러한 내용이 잘 반영되어 있다. 만약 nice 값이 커질수록 priority는 줄어들기 때문에 CPU를 차지하고 있는 빈도가 줄어들 것이며, nice 값이 작아질수록 priority가 높아져서 해당 Thread에의 CPU 할당 시간이 커질 것이다. 

 

설명을 읽어보면 init_thread의 nice는 초기에 0으로 설정되고, 다른 thread는 부모 thread의 nice를 물려받는다. 이것만 있으면 nice가 존재하는 의미가 없기에 따로 nice를 설정하는 함수가 있고, 이것이 thread_set_nice() 함수이다. 해당 함수가 호출되는 것이 아니라면 nice는 변동되지 않기에 비교적 간단한 변수다. 문제는 다음에 나오는 recent_cpu 변수이다.

recent_cpu 변수

우선 전직 수학맨으로서 맨 뒤에 나오는 계산식부터 들여다봤다.

load_avg = (59/60) * load_avg + (1/60) * ready_threads
recent_cpu = (2 * load_avg) / (2 * load_avg + 1) * recent_cpu + nice

 

갑자기 load_avg라는 변수도 튀어나오고 ready_threads라는 것도 들어간다. 이것부터 일단 보고 오자.

load_avg 변수

다시 식을 보자.

load_avg = (59/60) * load_avg + (1/60) * ready_threads

 

처음봤을 때는 다소 혼란스러웠지만 결국 해당 변수의 궁극적인 의미는 주식 그래프에서의 이평선이랑 똑같다. 이평, 즉 이동평균을 계산하는 식이다. ready_threads는 설명을 읽어보면 해당 계산을 실행할 때 실행되고 있거나 ready 상태에 있는 thread의 개수를 나타내는 변수이다. (idle thread는 개수에서 제외한다.) 즉, 현재 준비 또는 실행 상태의 Threads의 개수의 이평을 계산하여 저장하고 있는 것이 load_avg이다. 60일 이평선

 

이해하기 어렵다면 평균적으로 몇 개의 Thread가 CPU를 놓고 경쟁을 하고 있는지를 나타낸 것인지라고 생각하면 된다. 다만 그 평균을 구하는 방식이 계속 변하는 환경에 따른 적응을 포함하고 있어야 하기에 moving average 방식을 채택한 것이다. 매뉴얼에 따르면 이 식은 매 초마다 계산해야 하고, 초기에는 0으로 세팅된다고 한다. 그럼 다시 recent_cpu를 보자.

다시 recent_cpu 변수

recent_cpu = (2 * load_avg)/(2 * load_avg + 1) * recent_cpu + nice

 

설명을 보면 recent_cpu가 표현하고자 하는 것은 해당 Thread가 CPU를 할당받은 양이다. 이에 대한 증거로, recent_cpu는 매 tick마다 실행되는 CPU에서는 1 증가하고, 나머지 Thread에서는 증가하지 않는다. 그러나, 이렇게 단순하게 tick을 누적하는 방식으로 따지면 비교적 최근에 CPU를 사용한 Thread와 예~전에 CPU를 사용한 Thread가 같은 취급을 받을 수 있다.

 

예를 들어, Thread A가 10 tick동안 실행되다가 새로운 Thread B가 실행되기 시작했다고 하자. A의 입장에서는 B가 무조건 10 tick 동안 실행되어야 recent_cpu가 같아져 priority가 같아질 것이기에 B의 실행을 10 tick동안 기다려야 기회가 생긴다. 이를 극단적으로 늘려보면 A가 10000 tick 동안 실행됐으면, 다시 실행 기회가 생길 때까지 B의 10000 tick을 기다려야 한다. 뭔가 잘못되었다. 

 

이를 방지하기 위해 과거의 CPU 사용 기록은 최신의 CPU 사용 기록과 비교할 때 가중치를 낮게 둘 필요가 있다. 다르게 표현하면 과거의 CPU 사용을 점차 옅어지도록 하는 계산이 필요하다. 이것을 수식으로 표현한 것이 위의 계산식이고, 이를 decay라고 한다. 이 계산을 포함한다면 위 사례에서 A는 10000 tick이 아닌 그보다 짧은 시간에 recent_cpu가 B와 비슷해지기에 보다 공평한 CPU 배분이 가능해지는 것이다. 

 

recent_cpu가 클 수록 priority는 작아지기에, CPU 할당량이 많은 Thread가 CPU를 양보해야 한다는 이치와 부합한다. nice 변수가 보정 차원에서 들어가 있으며, 해당 식은 매 초마다 계산되어야 한다. recent_cpu는 음수도 될 수 있기 때문에 음수를 0으로 보정하지 말라고 나와있다.

 

---

 

여기까지 보면, 해당 계산식에 따라 priority를 계산하면 CPU를 꽤 공정하게 배분할 것 같다. 위의 계산은 모두 매뉴얼에서 매 초, 즉 timer_ticks () % TIMER_FREQ == 0일 때 실행하도록 나와있으니 일괄적으로 매 tick마다 호출되는 timer_interrupt에서 처리하도록 하면 될 것이다. 문제는 해당 식들의 계산 순서가 어떻게 되어야 할지가 모호하다. 그래서 우선은 load_avg, recent_cpu, priority 순으로 계산하도록 두고 잘못되면 순서를 바꿔보도록 한다.

 

여기서 또 문제가 있다. 최종 결과인 priority는 정수라 하더라도, load_avg와 recent_cpu 계산에는 실수 연산이 필연적인데, 핀토스에는 실수 구현이 안되어 있다는 것이다. 따라서, 제한된 환경 내에서 실수 연산을 하도록 만들어야 한다. 그래서 매뉴얼에서는 fixed point 실수 연산을 구현할 것을 추천한다.

 

우리가 이전 수업들에서 공부했던 floating point 실수 연산과 달리, fixed point 연산은 어떠한 수 \(N\)이 있을 때, 일정한 분모 \(2^k\)를 미리 정해놓고 그 수가 실은 \( \frac {N} {2^k}\)를 나타내는 것으로 생각한다는 것이다.  그래서 분수 \( \frac {p} {q} \)를 이 fixed point 방식으로 나타내려면 \( \frac {p \times 2^k} {q} \)를 정수로 계산하면 되는 것이다. 더 자세한 내용은 어차피 구현할 때 또 다루어야 하니 다음 포스팅에서 소개하도록 하겠다.  

 

여기까지 정리하면 구현해야 할 단계는 다음과 같다.

 

• fixed point 실수 연산을 수행하는 라이브러리(?) 구현
• load_avg, recent_cpu, priority 계산 루틴 구현
• thread_mlfqs 변수에 따라 다른 루틴이 실행되도록 기존 함수 수정

하.... 이제 다음 포스팅부터 구현을 시작하자.