Project_1 : Threads - Priority Scheduling(4)
Priority Scheduling의 마지막 문제는 우선순위 반전(Priority Inversion)이다.
이는 우선순위가 낮은 스레드가 우선순위가 높은 스레드보다 우선하여 실행되는 문제이다. 아래의 그림을 살펴보자.
Thread H, Thread M, Thread L 세 개의 스레드가 있고, 우선순위는 Thread H > Thread M > Thread L 순이다.
즉, 우선순위 기준으로 스레드가 실행되어야 한다면 H -> M -> L 순이어야 한다.
하지만 현재 Lock을 점유하고 있는 스레드는 Thread L이다.
실행을 위해 Lock이 필요한 Thread H는 CPU 점유를 반환하고 Thread L이 Lock을 반환할 때까지 대기 상태에 들어간다.
문제는 Thread H가 CPU 점유를 반환할 경우, 우선순위에 기반하여 Thread M이 CPU를 점유한다는 것이다.
따라서 Thread M이 먼저 실행되고, 이후 Thread L이 실행되어 Lock을 반환한 이후에야 Thread H가 실행된다.
정리하자면 앞서 기대한 것과 달리 M -> L -> H 순으로 스레드가 실행되는 것이다.
이를 해결하기 위해서는 Priority Donation이 이루어져야 한다.
Priority Donation이란 높은 우선순위의 스레드가 낮은 우선순위의 스레드에게 자신의 우선순위를 양도하는 것을 의미한다.
위의 예시에서 Thread H가 자신의 우선순위를 Thread L에게 양도하여, Thread L이 Thread H와 동일한 우선순위를 갖게 되는 것이다.
이제 우선순위 기준으로 스레드 실행 순서는 H -> L -> M 또는 L -> H -> M 순이 된다.
그런데 Thread L이 Lock을 갖고 있기에 Thread H보다 Thread L이 먼저 실행되어 최종 스레드 실행 순서는 L -> H -> M 순이 된다.
Priority Donation을 완벽하게 구현하기 위해서는 아래의 Multiple Donation, Nested Donation과 같은 특별한 상황 역시 고려해야 한다.
Multiple Donation
특정 스레드가 두 개 이상의 Lock을 갖고 있을 경우, 각각의 Lock에 의해 Priority Donation이 발생할 수 있다.
이를 Multiple Donation이라 한다.
Nested Donation
Nested Donation은 아래와 같이 Thread H가 Lock B를 얻기 위해 Thread M에게 Priority Donation을 진행하고,
Thread M은 Lock A를 얻기 위해 Priority Donation을 단계적으로 발생하는 상황을 의미한다.
이제 본격적인 구현을 해보고자 한다.
우선, 개별 스레드에서 Priority Donation 관련 정보들을 관리할 수 있도록 thread 구조체를 변경해야 한다.
/* include/threads/thread.h */
struct thread {
/* Owned by thread.c. */
tid_t tid; /* Thread identifier. */
enum thread_status status; /* Thread state. */
char name[16]; /* Name (for debugging purposes). */
int priority; /* Priority. */
/* PROJECT1: THREADS */
int64_t wakeup; /* time to wake up */
/* Shared between thread.c and synch.c. */
struct list_elem elem; /* List element. */
#ifdef USERPROG
/* Owned by userprog/process.c. */
uint64_t *pml4; /* Page map level 4 */
#endif
#ifdef VM
/* Table for whole virtual memory owned by thread. */
struct supplemental_page_table spt;
#endif
/* Owned by thread.c. */
struct intr_frame tf; /* Information for switching */
unsigned magic; /* Detects stack overflow. */
/* PROJECT1: Priority Scheduling */
int init_priority;
struct lock *wait_on_lock;
struct list donations;
struct list_elem donation_elem;
};4개의 변수를 추가하였다(init_priority, wait_on_lock, donations, donation_elem).
init_priority는 스레드의 고유 우선순위를 저장하기 위한 변수이다. wait_on_lock은 스레드가 기다리고 있는 Lock을 가리키는 변수이다.
donations는 자신에게 우선순위를 나누어준 스레드들의 리스트이며, donation_elem는 해당 리스트를 관리하기 위한 element 이다.
thread 구조체를 변경하였으므로, thread를 초기화 하는 함수 init_thread( ) 역시 수정해주어야 한다.
/* thread/thread.c */
static void init_thread (struct thread *t, const char *name, int priority) {
ASSERT (t != NULL);
ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
ASSERT (name != NULL);
memset (t, 0, sizeof *t);
t->status = THREAD_BLOCKED;
strlcpy (t->name, name, sizeof t->name);
t->tf.rsp = (uint64_t) t + PGSIZE - sizeof (void *);
t->priority = priority;
t->magic = THREAD_MAGIC;
/* PROJECT1: Priority Scheduling */
t -> init_priority = priority;
t -> wait_on_lock = NULL;
list_init (&t -> donations);
}스레드가 Lock을 요청하기 위해 실행하는 함수 lock_acquire( ) 수정해야 한다. Lock을 현재 점유하고 있는 스레드가 없으면 상관 없지만,
특정 스레드가 점유하고 있다면 자신의 우선순위를 양도하여 Lock을 점유하고 있는 스레드가 우선적으로 Lock을 반환하도록 해야 한다.
아래 lock_acquire( ) 함수의 구현 코드를 살펴보자. if 절 내의 lock->holder는 현재 Lock을 점유하고 있는 스레드를 가리킨다.
해당 스레드가 있다면 lock_acquire( ) 함수를 호출한 스레드의 wait_on_lock에 lock을 저장한다.
그리고 Lock을 점유하고 있는 스레드의 donations 리스트에는 lock_acquire( ) 함수를 호출한 스레드를 추가한다.
이때, list_insert_ordred( ) 함수를 이용하는데, 삽입의 기준이 되는 함수는 thread_compare_donate_priority( )이다.
thread_compare_donate_priority( )는 이전의 삽입 기준 함수들과 크게 다르지 않다.
이후, 우선순위 양도를 위하여 dontae_priority( ) 함수를 호출한다.
특정 스레드의 Lock을 점유 여부와 상관없이 sema_down( ) 함수 호출 이후에는
lock_acquire( ) 함수 호출 스레드의 wait_on_lock은 NULL로 변경하고, Lock의 holder를 lock_acquire( ) 함수 호출 스레드로 변경한다.
/* thread/synch.c */
/* PROJECT1: THREADS - Priority Scheduling */
void lock_acquire (struct lock *lock) {
ASSERT (lock != NULL);
ASSERT (!intr_context ());
ASSERT (!lock_held_by_current_thread (lock));
struct thread *cur = thread_current();
if (lock->holder){
cur->wait_on_lock = lock;
list_insert_ordered(&lock->holder->donations, &cur->donation_elem, thread_compare_donate_priority, 0);
donate_priority();
}
sema_down(&lock->semaphore);
cur->wait_on_lock = NULL;
lock->holder = cur;
}
/* include/thread/thread.h */
bool thread_compare_donate_priority (const struct list_elem *l, const struct list_elem *s, void *aux UNUSED)
/* thread/thread.c */
bool thread_compare_donate_priority (const struct list_elem *l, const struct list_elem *s, void *aux UNUSED){
return list_entry (l, struct thread, donation_elem)->priority > list_entry (s, struct thread, donation_elem)->priority;
}우선순위 양도를 위한 함수 donate_priority( )는 아래와 같이 Nested Donation 상황을 고려하여 구현되어야 한다.
여기서는 Nested의 최대 깊이를 8로 지정하였다.
현재 스레드의 wait_on_lock이 NULL이 아니라면 스레드가 기다리는 Lock이 있다는 의미이다.
따라서 해당 Lock의 holder를 찾아 우선순위를 양도해주어야 하며, 양도 과정을 Nested의 최대 깊이 까지 진행한다.
/* thread/thread.c */
/* PROJECT1: THREADS - Priority Scheduling */
void donate_priority (void){
int depth;
struct thread *cur = thread_current ();
for (depth = 0; depth < 8; depth++){
if (!cur->wait_on_lock) break;
struct thread *holder = cur->wait_on_lock->holder;
holder->priority = cur->priority;
cur = holder;
}
}
/* inclue/thread/thread.h */
void donate_priority (void);다음으로 우선순위를 양도받은 스레드가 Lock을 반환할 때의 경우를 구현해야 한다.
이를 위해 lock_release( ) 함수를 수정해보자. 이때 고려해야하는 것이 Multiple Donation이다.
아래 그림에서 lock_release( )를 하기 전 Thread L의donations 리스트에는 Thread H와 Thread M이 존재한다.
그런데 만약 Thread L이 lock_release(lock_B)를 호출한다면,
donations 리스트에서 Thread H은 삭제되어야 하며, 우선순위는 33에서 32로 변경되어야 한다.
이후, lock_release(lock_A)를 추가로 호출한다면,
Thread M 역시 삭제되어야하고, 우선순위는 Thread L의 초기 우선순위인 31로 변경되어야 한다.
상기 과정을 함수로 구현하면 된다.
우선, 아래와 같이 donations 리스트에서 스레드를 삭제하는 함수 remove_with_lock( )을 만들어보자.
현재 스레드의 donations 리스트를 처음부터 끝까지 돌면서 특정 스레드의 wait_on_lock이 lock인 경우를 찾고,
해당 스레드를 donations에서 삭제해주는 방식으로 구현하면 된다.
/* thread/thread.c */
/* PROJECT 1 : Threads - Priority Scheduling */
void remove_with_lock (struct lock *lock) {
struct list_elem *e;
struct thread *cur = thread_current ();
for (e = list_begin (&cur->donations); e != list_end (&cur->donations); e = list_next (e)){
struct thread *t = list_entry (e, struct thread, donation_elem);
if (t->wait_on_lock == lock)
list_remove (&t->donation_elem);
}
}
/* include/thread/thread.c */
void remove_with_lock (struct lock *lock);다음으로 우선순위를 재설정하는 함수 refresh_priority( )를 구현해보자.
가장 먼저 현재 스레드의 우선순위를 현재 스레드의 init_priority로 변경한다.
현재 스레드의 donations 리스트가 비어있지 않다면,
해당 리스트를 list_sort( ) 함수를 이용하여 우선순위 기준으로 내림차순 정렬한다.
이후, 정렬된 리스트의 맨 앞 스레드의 우선순위와 init_priority를 비교하여 더 큰 우선순위로 현재 스레드의 우선순위를 변경한다.
/* thread/thread.c */
/* PROJECT 1 : Threads - Priority Scheduling */
void refresh_priority (void){
struct thread *cur = thread_current ();
cur->priority = cur->init_priority;
if (!list_empty (&cur->donations)) {
list_sort (&cur->donations, thread_compare_donate_priority, 0);
struct thread *front = list_entry (list_front (&cur->donations), struct thread, donation_elem);
if (front->priority > cur->priority)
cur->priority = front->priority;
}
}
/* include/thread/thread.h */
void refresh_priority (void);lock_release( ) 함수에는 단순히 두 함수를 추가하면된다.
/* thread/synch.c */
/* PROJECT1: THREADS - Priority Scheduling */
void lock_release (struct lock *lock) {
ASSERT (lock != NULL);
ASSERT (lock_held_by_current_thread (lock));
remove_with_lock(lock);
refresh_priority();
lock->holder = NULL;
sema_up (&lock->semaphore);
}마지막으로, 현재 CPU를 점유 중인 스레드의 우선순위가 변경되었을 때,
donations 리스트에 있는 스레드들의 우선순위보다 높아지는 경우가 발생할 수 있다.
이 경우 우선순위는 현재 CPU를 점유 중인 스레드의 새로 바뀐 우선순위로 유지되어야 한다.
이는 thread_set_priority( ) 함수 내에 refresh_priority( ) 함수를 추가해주면 간단히 해결된다.
/* thread/thread.c */
/* PROJECT1: THREADS - Priority Scheduling */
void thread_set_priority (int new_priority) {
thread_current ()->init_priority = new_priority;
refresh_priority ();
thread_test_preemption ();
}