Pintos Project 1 Threads. Advanced Scheduler

우선순위 스케쥴링을 하게 되면 발생하는 문제 중 하나로 우선순위가 낮은 스레드가 긴 시간동안 CPU를 점유하지 못하는 starvation 문제가 있다.

이를 해결하기 위해서 pintos document가 제시하는 방법은 BSD Scheduler이다.

기본 골자는 CPU를 많이 점유했던 애들의 우선순위는 낮추는 방향으로, CPU를 점유하지 못했던 스레드들의 우선순위는 올리는 방향으로 런타임 중에 우선순위들을 꾸준히 수정해주는 것이다.

이를 위해서 스레드별로 nice, recent_cpu라는 값을 새로 정의하고 시스템 전체에서 load_avg라는 값을 따로 관리하게 된다.

스레드의 우선순위는 $PRI\_MAX - recent\_cpu/4 - nice*2$로 결정된다.

nice란 스레드의 nice한 정도라고 설명하고 있다. nice할수록 자신의 우선순위를 낮춰서 CPU를 잘 양보해준다는 뜻이다.

recent_cpu란 스레드가 최근에 CPU를 어느정도 점유했는지를 나타내는 변수다. 실행중인 스레드는 매 tick마다 recent_cpu를 1씩 늘린다.

load_avg는 실행될 준비가 끝난 스레드의 평균 숫자를 의미한다. pintos에선 두 값 모두 moving average를 이용한 근사치로 계산한다.

여기서 중요한 것이 두 값 모두 다 실수값인데 실수 연산은 매우 비싼 연산이다. timer interrupt 시에 사용할만한 연산이 아닌 것이다.

따라서, int를 이용해서 실수 연산을 대체해야만 한다. 이 실수 연산에 대한 내용과 위 내용은 전부 pintos document의 appendix에 상세히 나와있다.

그래서 여기까지는 간단한 설명이었고 어떤 것을 구현해야 되는지를 정리하자.

1. recent_cpu와 load_avg를 계산하기 위한 실수 연산을 fixed_point.h로 구현하자.
2. Advanced Scheduler는 priority_donation과 동시에 동작하면 안된다. 이를 잘 막아두자.
3. priority를 사용자가 직접 설정하지 않고 nice만 설정 가능하다. 이것도 잘 체크하자.
4. 4 tick마다 모든 스레드의 우선순위를 다시 계산해야 한다.
5. TIMER_FREQ마다 load_avg과 모든 스레드의 recent_cpu를 새로 계산해줘야 한다.
6. 매 tick마다 실행중인 스레드의 recent_cpu를 1 증가시켜야한다.

각 업데이트의 계산 수식들 또한 document에 잘 나와 있으며, 아래와 같다.

실수 연산에 관한 내용도 잘 나와 있으며 그대로 구현하면 된다. Project 1을 이 전까지 해냈다면 사실 이 과제 자체는 단순 구현이라고 볼 수도 있다.

실제 코드 구현은 여기에서 implement mlfqs 커밋까지를 살펴보면 될 거 같다.

이걸로 Project 1의 모든 테스트를 통과할 수 있다.