[Pintos Project] 2.2.3 Priority Scheduling requirement 번역

2.2.3 Priority Scheduling

Implement priority scheduling in Pintos. When a thread is added to the ready list that has a higher priority than the currently running thread, the current thread should immediately yield the processor to the new thread. Similarly, when threads are waiting for a lock, semaphore, or condition variable, the highest priority waiting thread should be awakened first. A thread may raise or lower its own priority at any time, but lowering its priority such that it no longer has the highest priority must cause it to immediately yield the CPU.

Pintos의 priority scheduling을 구현해라. 현재 돌고 있는 스레드보다 priority가 높은 스레드가 ready_list에 추가될 때, 현재 스레드는 즉시 새로운 스레드로 프로세서를 넘겨준다. 비슷하게, 스레드가 락, 세마포어, 조건 변수(condition variable)를 waiting할 때, 높은 priority의 waiting 중인 스레드는 가장 먼저 깨워져야 한다. 스레드는 언제든지 자신의 priority를 높이거나 낮출 수 있다. 하지만 priority를 낮춘다면 해당 스레드는 다시 가장 높은 priority를 가질 수 없다. 왜냐 하면 즉시 CPU를 넘겨 줘야 하기 때문이다.

Thread priorities range from PRI_MIN (0) to PRI_MAX (63). Lower numbers correspond to lower priorities, so that priority 0 is the lowest priority and priority 63 is the highest. The initial thread priority is passed as an argument to thread_create(). If there’s no reason to choose another priority, use PRI_DEFAULT (31). The PRI_ macros are defined in ‘threads/thread.h’, and you should not change their values.

스레드 priority의 범위는 PRI_MIN (0) 에서 PRI_MAX (63) 까지이다. 낮은 수들은 priority가 낮은 것이다. 그러므로 0은 가장 낮은 priority이고 63은 가장 높은 priority이다. initial 스레드 priority는 thread_create() 함수의 argument로 넘겨진다. 만약 다른 priority를 선택할 이유가 없다면 PRI_DEFAULT (31)을 써라. PRI_매크로들은 'threads/thread.h'에 정의되어 있고, 그 값들을 바꾸면 안 된다.

One issue with priority scheduling is “priority inversion”. Consider high, medium, and low priority threads H, M, and L, respectively. If H needs to wait for L (for instance, for a lock held by L), and M is on the ready list, then H will never get the CPU because the low priority thread will not get any CPU time. A partial fix for this problem is for H to “donate” its priority to L while L is holding the lock, then recall the donation once L releases (and thus H acquires) the lock. 

priority scheduling에 관련된 이슈 하나가 있는데,  바로 "priority inversion (우선 순위가 꼬이는 것)" 이다.

High, Medium, 그리고 low priority 스레드들인 H, M, L 제각각을 고려해야 한다. 만약 H가 L을 기다려야 하는 상황이고(예를 들어,  L이 lock을 걸었을 때), M이 ready_list에 있다면, H는 CPU를 점유할 수 없다. 왜냐 하면 낮은 priority의 스레드는 CPU를 얻을 수 없기 때문이다. 문제를 해결하기 위해 부분적으로 수정하는 방법이 있는데, L이 lock을 잡고 있을 때, H가 자신의 priority를 L로 "기부" 하는 것이다. 그리고 L이 lock을 해제할 때 다시 원래 priority로 되돌리는 것이다.

-> ready_list에서 맨 앞의 것을 pop 하는 것이 아닌 가장 높은 우선 순위를 가진 스레드를 찾아 반환해 주는 것이라 가정.

-> Thread가 ready_list에 우선 순위 상관 없이 M ? ? H ? ? 순으로 들어 있다면, 현재 Round-Robin 방식에서는 M이 가장 앞에 있고, M은 L보다는 우선 순위가 높으므로 H가 아닌 M이 CPU를 점유하게 된다. 그러므로 H는 M보다 우선 순위가 높지만 더 낮은 우선 순위인 것 처럼 동작하게 된다. 이를 해결하는 방법이 있는데, L이 lock을 잡고 있을 때 H의 우선 순위와 같게 하고, L이 lock을 해제할 때 원래 우선 순위로 되돌리는 것이다. 그러면 잠시나마 L이 H와 같은 우선 순위가 되기 때문에, H 이상의 우선순위를 ready_list에서 검색하고 M은 지나치게 되므로 정상 동작 하게 된다.

Implement priority donation. You will need to account for all different situations in which priority donation is required. Be sure to handle multiple donations, in which multiple priorities are donated to a single thread. You must also handle nested donation: if H is waiting on a lock that M holds and M is waiting on a lock that L holds, then both M and L should be boosted to H’s priority. If necessary, you may impose a reasonable limit on depth of nested priority donation, such as 8 levels. 

Priority donation (우선 순위 기부)를 구현해라. 당신은 priority donation이 요구하는 다른 모든 상황들에 대한 내용이 필요할 것이다. 반드시 multiple donation을 처리하고, multiple priority는 single thread로 donate된다. 또 해야하는 것이 있는데, 바로 "중첩된 donation (nested donation)"이다. 만약 H가 M이 락을 잡고 있는 걸 기다리고, M은 L이 락을 잡고 있는 걸 기다린다면, M과 L은 H의 priority로 증폭되야 할 것이다. 필요하다면, 8 단계의 중첩된(nested) priority donation의 깊이에 대한 합리적인 제한을 도입해야 할 수도 있다.

You must implement priority donation for locks. You need not implement priority donation for semaphores or condition variables (but you are welcome to do so). You do need to implement priority scheduling in all cases. 

lock에 대해 priority donation을 구현해야 한다. 세마포어나 조건 변수(condition variable)에 대해서는 priority donation을 구현할 필요 없다(구현할 필요는 없지만 그리 한다면 금상첨화). 모든 경우의 priority scheduling을 구현할 필요가 있다.

Finally, implement the following functions that allow a thread to examine and modify its own priority. Skeletons for these functions are provided in ‘threads/thread.c’. 

마지막으로, 다음의 함수들을 구현해라. 이 함수들은 스레드 자신의 priority를 검사하고 수정할 수 있다.

이 함수들의 뼈대는 'threads/thread.c'에서 제공된다.

void thread_set_priority (int new_priority)

Sets the current thread’s priority to new priority. If the current thread no longer has the highest priority, yields.

현재 스레드의 priority를 새로운 priority로 설정한다. 만약 현재 스레드가 더 이상 가장 높은 priority를 가지지 않는다면, yield해라.

int thread_get_priority (void) 

Returns the current thread’s priority. In the presence of priority donation, returns the higher (donated) priority.

현재 스레드의 priority를 반환한다. priority donation이 있는 곳에서는 높은(donate된) 우선순위를 반환한다.

You need not provide any interface to allow a thread to directly modify other threads’ priorities.

The priority scheduler is not used in any later project.

당신은 직접적으로 다른 스레드의 priority를 수정할 수 있는 다른 인터페이스를 제공할 필요가 없다.

Priority scheduler는 다른 프로젝트에서는 사용되지 않는다.