Multi-Level Feedback Queue Scheduler

핀토스 1주차 Option 과제인 Advanced Scheduler를 구현해봤습니다.

 

기존의 Priority Scheduler의 경우에는 우선 순위가 낮은 스레드가 오랫동안 CPU를 점유하지 못하는 문제가 발생할 수 있습니다. 이로 인해 스레드의 평균 반응 시간이 너무 길어지는 문제가 발생합니다. 이를 해결 하기 위한 방법으로 multi-level feedback queue scheduler가 제시되었습니다.

 

MLFQS는 Priority에 따라 여러 개의 Ready Queue가 존재하고, Priority에 영향을 주는 변수가 있어서 Feedback으로 Priority를 조절할 수 있습니다. 이 때, multi level까지는 구현하기 힘들 것 같아서 Feedback만 구성을 해봤습니다. 사실 상 feedback queue scheduler가 되겠네요.

 

Advanced Scheduler에서 중요한 키워드들을 정리해 봤습니다.

 

 

PRIORITY, RECENT_CPU, LOAD_AVG를 구하는 식은 다음과 같습니다.

 

PRIORITY는 제시된 가중치로 결정되게 되고, RECENT CPU의 경우 CPU 점유시간의 값을 지수 가중 평균을 사용하여 계산하게 됩니다. LOAD AVERAGE는 1분 동안 수행 가능한 스레드의 평균 개수를 추정하는 계산식입니다.

NICENESS가 없는데 이는 Test Program에서 임의로 지정해줍니다.

이 때 주의해야 할 점이 있습니다. 바로 실수형이라는 것입니다. 그러나 핀토스에서는 실수를 지원하지 않습니다. 이를 위해 17.14 고정소수점 표현을 사용하게 됩니다.

 

 

17.14 고정소수점 표현이란 32비트짜리 정수형을 갖고 14번째 자리를 기준으로 제일 앞 1자리는 부호, 왼쪽 17자리는 정수, 오른쪽 14자리는 소수로 사용하는 기법입니다. 

 

 

그래서 F라는 2의14승짜리 숫자를 만들어 실수와 정수를 전환하게 되고 이에 따라 특수한 매크로를 만들어 연산을 수행해야 합니다. 예를 들면 덧셈을 할때는 정수에 F를 곱해 실수로 만들어 줄 수 있습니다. 실수끼리 곱셈을 할 때는 둘 다 F가 곱해진 상태이므로 중복된 F를 삭제하기 위해 F로 나누어 줍니다.

 

 

구현에 앞서 Priority 또한 새롭게 계산을 하였는데, 기존의 함수가 Priority를 조절할 수 있기 때문에 thread_mlfqs인자가 선언이 되어있으면 동작하지 않고 return하게 수정하였습니다.

 

 

또한, Priority가 Donate될 경우 mlfqs의 Priority와 충돌할 것을 염려해 Lock Acquire와 Release 시에 Priority Donation을 작동하지 않도록 수정하였습니다.

 

 

Advanced Scheduler에서 가장 중요한 Timer Interrupt 함수 입니다. 먼저, Timer가 Interrupt할 때마다, 즉 1틱마다 현재 thread의 CPU 점유시간을 1씩 증가시켜줍니다. 그리고 4틱마다 CPU 점유시간, Niceness에 의해 모든 Thread의 Priority를 재조정합니다. 그리고 100틱마다 Load Average를 측정하고 모든 Thread의 Recent CPU를 지수 가중 평균으로 재조정합니다.

 

 

이러한 재조정을 할 때 기존에 사용하던 Ready List는 대기중인 Thread만 들어있습니다. 그래서 만료되지 않은 모든 thread를 넣는 list를 새로 만들어 sleep 중인 thread까지 priority와 recent cpu를 계산할 수 있게 했습니다..
그 외에 수정해야 하는 함수가 더 있으니 이는 Github를 참고하면 좋을 것 같습니다.

 

테스트 결과