[Pintos] Multi-Level Feedback Queue Scheduler(mlfqs)

핀토스 프로젝트 1의 extra 과제이다. multi-level feedback queue scheduler의 구현인데, 일단 저번 포스팅에서 소개했던 스케줄러들과 비교해서 어떤 점이 좋은지 살펴보자. 

 

기존 Priority Scheduler의 문제점

기존 우선순위 스케줄러는 저번 포스팅에서도 언급했다시피 우선순위가 낮은 작업이 계속해서 순서가 밀려 CPU를 얻지 못하는 Starvation 현상이 발생할 수 있다는 점이 있었다. 물론 핀토스에서 구현하는 우선순위 스케줄러에서는 priority donation도 있어 우선순위가 낮은 작업도 충분히 실행될 기회를 잡을 수 있지만, 특별히 락을 소유하지 않고 우선순위도 낮은 작업들은 이러한 조정도 받지 못할 수 있다. 이로 인해 task들의 평균 대기 시간이 길어질 수 있는 문제점이 있었다. 

 

 

Multi-Level Feedback Queue Scheduler(mlfqs)

이를 mlfqs에서는 priority aging 기법을 활용하여 해결한다. priority aging이란 ready list에서 대기를 오래 한 작업일수록 priority를 높여주고 CPU를 오래 쓴 작업일수록 priority를 낮춰주는 식으로 우선순위를 보정하는 기법을 말한다. 이를 통해 처음에 우선순위가 낮은 작업일지라도 오랫동안 순서가 밀리면 후에는 우선순위가 높게 보정되어 기존의 starvation이 발생할 수 있었던 문제를 해결할 수 있다. 또한 mlfqs에서는 스레드들이 nice value를 갖는데, 이 값이 높을수록 다른 스레드에게 순서를 양보하려는 경향이 있다. 정확히 무슨 의미인지는 아래의 식을 보면서 이해해 보자! 

 

 

 

Nice Value

nice value는 각각의 스레드별로 존재하는 값이다. 정수 값을 가지며 위에서 언급했다시피 이 값이 클수록 다른 스레드에게 CPU를 양보하려는 경향이 있다. nice value가 가질 수 있는 값의 범위는 아래와 같다.

$$ -20 \leq \text{nice value} \leq 20 $$

범위를 보면 음수 값을 가질수도 있는데, nice value가 음수의 값을 가진다는 것은 다른 스레드로부터 CPU를 뺏어오려는 경향이 강하다는 것을 의미한다. 이 값이 어떤 방식으로 반영되는지는 뒤의 다른 값들의 계산식들을 살펴보면 이해할 수 있을 것이다. 

nice value는 스레드 생성 시 설정해 주는 값이며, 직접 nice value를 바꿔주지 않는 이상 스레드가 종료될 때까지 값은 바뀌지 않는다. 

 

Load Avg

nice value나 recent cpu 값과는 달리 모든 스레드가 공유하는 공유 변수이다. 이 값은 nice value와는 달리 실수의 값을 가진다. CPU가 최근 1분 동안 수행 가능한 스레드의 평균 개수를 나타내는 값이다. recent cpu의 값을 계산할 때 감쇠 계수로 쓰인다. 계산식은 아래와 같다. 

$$ \text{load avg} = \frac{59}{60}*\text{load avg} + \frac{1}{60} * \text{ready threads} $$ 

위의 식에서 ready threads는 idle thread를 제외하고 현재 ready list에 있는 스레드와 실행중인 스레드의 개수를 합한 값이다. load avg 값은 초기에 0으로 시작하며, 매 초마다 위의 식에 따라 값을 새로 계산한다. 

 

Recent CPU

위의 load avg 값과 같이 실수의 값을 가진다. nice value와 마찬가지로 스레드마다 개별적으로 가지고 있는 값이며 스레드가 최근에 CPU를 얼마나 많이 사용했는지를 나타낸다. 식은 아래와 같다.

$$ \text{recent cpu} = \frac{2 * \text{load avg}}{2 * \text{load avg} + 1} * \text{recent cpu} + \text{nice} $$

 

 

Priority 

마지막으로 우선순위를 재조정하는 식을 살펴보자. 

$$ \text{priority} = \text{PRI_MAX} - \frac{1}{4} * \text{recent cpu} - 2 * \text{nice} $$

식을 살펴보면 다음과 같은 사실을 알 수 있다. 

• recent cpu 값이 클수록 우선순위가 많이 낮아진다.
• nice 값이 높을수록 우선순위가 많이 낮아진다. 

recent cpu의 값이 클수록 최근에 CPU를 많이 사용했다는 의미이므로 값이 크면 우선순위가 많이 낮아지는 것이다. 여기서 load avg는 recent cpu의 감쇠 계수의 역할을 한다고 했다. load avg가 클수록 recent cpu의 감쇠 계수는 1에 가까워지고, load avg가 작을수록 감쇠 계수는 0에 가까워진다. 즉, load avg가 클수록 recent cpu의 값이 천천히 감소한다는 의미이다. 이는 현재 단위 시간당 수행 가능한 스레드의 수가 많을 때는 우선순위의 조정을 조금 천천히 진행하고, 반대로 수행 가능한 스레드의 수가 적을 때는 우선순위의 조정을 빠르게 한다는 의미를 지닌다. 

 

 

 

 

Fixed-point arithmetic

위의 식에서 nice value와 priority를 제외한 값들은 모두 실수 값을 가진다는 것을 살펴보았다. 우리의 핀토스는 부동 소수점 연산을 지원하지 않기 때문에, 고정 소수점 연산(fixed-point arithmetic)을 활용해야 한다. 

고정 소수점 연산이란, 위의 그림과 같이 총 32비트의 정수형 자료형에 뒤의 14bit는 소수 부분을, 그 다음 17bit은 정수 부분을, 마지막 1bit은 값의 부호를 나타내는 방식을 말한다. 

단 이렇게 고정 소수점을 사용하는 방식에서는 연산에 주의가 필요하다. 아래의 예를 살펴보자.

위와 같이 고정 소수점으로 나타낸 5.5와 1.5를 곱하면 아래의 결과를 얻을 수 있다. 이 값을 그냥 사용하게되면 우리가 연산의 결과로 기대하는 값과 아주 다른 값이 나온다. 그리고 만약 1.5가 아닌 조금만 더 큰 수를 곱했다면 표현할 비트가 모자라 오버플로우가 발생했을 수도 있다. 따라서 고정 소수점을 사용한 두 수를 곱할 때는 먼저 앞의 수를 (int64) 자료형으로 타입 캐스팅을 진행한 뒤에, 두 수를 곱하고 $ 2^{14} $으로 나누는 연산이 필요하다. 그 결과 아래와 같은 값을 얻을 수 있다. 

이렇게 고정 소수점을 다루기 위해서는 오퍼랜드에 따라 연산 방식이 조금씩 다르다. 모든 연산을 전부 다 이렇게 다루기에는 양이 너무 많으니... 연산 테이블만 첨부한다! 참고로 핀토스 문서에 보면 자세하게 나와있으니 그걸 참고해도 좋다. 

아래의 표에서 n은 정수, x와 y는 고정 소수점 형태의 실수이다.

 

이렇게 mlfqs까지 구현을 완료하면 프로젝트 1에서는 다음과 같이 all pass를 받을 수 있다!