[Nachos]#5. Priority Scheduling

Nachos 학교과제에서 이번 부분이 마지막이다.

사실 Nachos 프로젝트를 하면서 OS는 내 머리의 능력 밖이다라고 뼈져리게 느꼈다.

요구사항

TASK V (35%, 125 lines) priority scheduling

priority scheduling은 real-time system에서의 핵심이다.

이 Scheduling을 사용하기 위해서 Nachos 폴더 proj1 폴더안에 있는 Nachos.conf 부분에서

ThreadedKernel.scheduler = nachos.threads.PriorityScheduler

변경해주어야한다.

- getPriority(), getEffectivePriorty(), setPriority()

이건 선택사항으로

- increasePrioirty(), decreasePriorty() 함수를 반드시 실행해야한다.

그리고 큐를 대기시킬 Thread를 선택할 때에 Scheduler는 항상 High Priority Thread를 선택해야하고, 동일한 Priority Thread가 대기중인 경우에는 대기열에서 가장 긴 대기시간을 가졌던 Thread를 선택해야한다.

하지만, Priority Scheduling은 Priority Inversion문제가 발생할 수 도 있다. 

예를 들면, Low Priority Thread가 Lock을 가진 상태로 Sleep을 하게된다면 High Priority Thread가 Critical Section에 접근하려고 할 경우 일반적으로 Busy-waiting 하거나, Sleep을 한다. 하지만 Priority Scheduling 알고리즘에 따라 Low Priority Thread는 자신의 차례를 받기 힘들고, 이로인해 High Priority Thread는 아무 작업도 못하는 Starvation 상태에 빠진다.

이 부분에 대한 부분적 해결은 대기중인 Thread가 우선순위가 낮은 Thread에게 먼저 우선순위를 제공하여 잠금을 유지하는 것으로 해결할 수 있다.

우선순위를 먼저 제공하는 Scheduler를 구현하기 위해 Scheduler.getEffectivePriority() 부분을 구현해야한다.

Class nachos.threads.Scheduler -> 수정 금지

Class nachos.threads.Lock -> 수정 금지

Class nachos.threads.ThreadQueue를 활용