Priority Scheduling 구현
-
삽입 방식 변경
Priority Scheduling을 구현하기 위해 Priority 가 높은 쓰레드가 ready_list의 맨 앞에 위치하게 하여 list_pop_front를 그대로 사용한다. 핀토스에는 list_insert_ordered 함수가 있어 리스트내에 원하는 위치에 원소를 삽입 할 수 있다. list_inser_ordered 함수에 원소간 비교하는 함수를 대입해야 하므로 스레드의 우선순위를 비교하는 함수를 따로 만들어 주어야 한다. 만든 함수를 이용해 list_push_back을 list_insert_ordered로 바꿔준다.
/* thread/thread.c */ bool thread_compare_priority (struct list_elem *l, struct list_elem *s, void *aux UNUSED) { return list_entry (l, struct thread, elem)->priority > list_entry (s, struct thread, elem)->priority; } void thread_unblock (struct thread *t) { ... //list_push_back (&ready_list, &t->elem); list_insert_ordered (&ready_list, &t->elem, thread_compare_priority, 0); ... } void thread_yield (void) { ... if (cur != idle_thread) //list_push_back (&ready_list, &cur->elem); list_insert_ordered (&ready_list, &cur->elem, thread_compare_priority, 0); ... } -
우선순위 변경에 따른 스케줄 진행
새로 생성된 스레드의 우선순위가 현재 진행중인 스레드의 우선순위 보다 높거나 프로세스 진행 중에 우선순위가 변경 될 수 있다. 이러한 경우 더 높은 스레드에게 cpu를 할당해야한다. 이 기능을 하는 함수를 새로 만들고 thread_create와 thread_set_priority 함수 내에서 사용한다.
/* thread/thread.c */ void thread_test_preemption (void) { if (!list_empty (&ready_list) && thread_current ()->priority < list_entry (list_front (&ready_list), struct thread, elem)->priority) thread_yield (); } tid_t thread_create (const char *name, int priority, thread_func *function, void *aux) { ... thread_unblock (t); thread_test_preemption (); return tid; } void thread_set_priority (int new_priority) { thread_current ()->priority = new_priority; thread_test_preemption (); }
세마포어, lock, condition value
핀토스에서는 세마포어, lock, condition value를 사용하여 동기화 및 상호배제를 구현한다. 우선 가장 기본인 세마포어는 우리가 알고 있는 세마포어와 동일하다. sema_down이 P, sema_up이 V라고 생각하면 편하다. 이때 세마포어가 풀리기 기다리는 스레드들은 waiters라는 리스트에서 대기한다.
lock은 세마포어를 활용하여 만든 도구이다. 세마포어는 sema_up을 임의의 스레드가 할 수 있지만 lock은 lock 을 가지고 있는 스레드(holder)만이 lock을 풀 수 있다. 그리고 lock은 세마포어의 값을 1로 초기화 하여 사용한다. 따라서 처음 lock을 획득한 스레드가 lock 홀더가 되며 세마포어 값을 down 시켜 임계영역을 보호 한다.
condition value는 세마포어 초기값을 0으로 설정한다. 이 경우는 스레드가 처음 오더라도 공유자원을 사용하지 못한다. condition value는 lock과 마찬가지로 waiter(세마포어들) 리스트에서 대기한다. lock의 경우는 holder가 lock을 풀었지만 condition value의 경우 signal 함수가 공유자원에 대한 접근을 허용한다.
-
세마포어
기존 핀토스에서 sema_down, sema_up이 어떻게 구현되어있는지 확인해보자.
/* thread/synch.c */ void sema_down (struct semaphore *sema) { enum intr_level old_level; ASSERT (sema != NULL); ASSERT (!intr_context ()); old_level = intr_disable (); while (sema->value == 0) { list_push_back (&sema->waiters, &thread_current ()->elem); thread_block (); } sema->value--; intr_set_level (old_level); } void sema_up (struct semaphore *sema) { enum intr_level old_level; ASSERT (sema != NULL); old_level = intr_disable (); if (!list_empty (&sema->waiters)) { thread_unblock (list_entry (list_pop_front (&sema->waiters), struct thread, elem)); } sema->value++; intr_set_level (old_level); }sema_down 에서 list_push_back을, semp_up에서 list_pop_front를 사용한다. 전과 마찬가지로 list_insert_ordered를 활용하면 된다. 다만 sema_up을 할 때 우선순위의 변동이 있을 수 있으니 waiter를 한번 정렬 해준다.
/* thread/synch.c */ void sema_down (struct semaphore *sema) { enum intr_level old_level; ASSERT (sema != NULL); ASSERT (!intr_context ()); old_level = intr_disable (); while (sema->value == 0) { list_insert_ordered (&sema->waiters, &thread_current ()->elem, thread_compare_priority, 0); thread_block (); } sema->value--; intr_set_level (old_level); } void sema_up (struct semaphore *sema) { enum intr_level old_level; ASSERT (sema != NULL); old_level = intr_disable (); if (!list_empty (&sema->waiters)) { list_sort (&sema->waiters, thread_compare_priority, 0); thread_unblock (list_entry (list_pop_front (&sema->waiters), struct thread, elem)); } sema->value++; thread_test_preemption (); intr_set_level (old_level); } -
lock
lock은 세마포어에 홀더만 포함된 개념이므로 세마포어를 수정하면 수정할 요소가 없다.
-
condition value
기존 condition value 관련 함수를 확인해 보면 다음과 같다.
/* thread/synch.c */ void cond_wait (struct condition *cond, struct lock *lock) { struct semaphore_elem waiter; ASSERT (cond != NULL); ASSERT (lock != NULL); ASSERT (!intr_context ()); ASSERT (lock_held_by_current_thread (lock)); sema_init (&waiter.semaphore, 0); list_push_back (&cond->waiters, &waiter.elem); lock_release (lock); sema_down (&waiter.semaphore); lock_acquire (lock); } void cond_signal (struct condition *cond, struct lock *lock UNUSED) { ASSERT (cond != NULL); ASSERT (lock != NULL); ASSERT (!intr_context ()); ASSERT (lock_held_by_current_thread (lock)); if (!list_empty (&cond->waiters)) { sema_up (&list_entry (list_pop_front (&cond->waiters), struct semaphore_elem, elem)->semaphore); } }cond_wait에서 세마포어를 모아둔 waiter를 선언한다. 그리고 list_push_back을 통해 해당 세마포어를 waiter 리스트에 넣어준다. 그리고 signal 함수에서 pop_front를 통해 세마포어를 선택하여 sema up을 하여 공유자원에 접근하게 한다. 따라서 sema_up을 할때 정렬을 한다면 우선순위가 가장 높은 세마포어를 뽑을 수 있다. list_push_back은 그대로 사용해도 결과는 같다. 그 이유는 cond_wait를 호출 할때마다 새로운 waiter가 생성되고 그 waiter에 push하기 때문에 굳이 정렬해서 삽입할 필요가 없다.(확실하진 않다.) 마지막으로 세마포어간 우선순위 비교를 위해 새로운 비교함수를 만들어 줘야한다.
/* thread/synch.c */ bool sema_compare_priority (const struct list_elem *l, const struct list_elem *s, void *aux UNUSED) { struct semaphore_elem *l_sema = list_entry (l, struct semaphore_elem, elem); struct semaphore_elem *s_sema = list_entry (s, struct semaphore_elem, elem); struct list *waiter_l_sema = &(l_sema->semaphore.waiters); struct list *waiter_s_sema = &(s_sema->semaphore.waiters); return list_entry (list_begin (waiter_l_sema), struct thread, elem)->priority > list_entry (list_begin (waiter_s_sema), struct thread, elem)->priority; } void cond_wait (struct condition *cond, struct lock *lock) { struct semaphore_elem waiter; ASSERT (cond != NULL); ASSERT (lock != NULL); ASSERT (!intr_context ()); ASSERT (lock_held_by_current_thread (lock)); sema_init (&waiter.semaphore, 0); list_push_back (&cond->waiters, &waiter.elem); lock_release (lock); sema_down (&waiter.semaphore); lock_acquire (lock); } void cond_signal (struct condition *cond, struct lock *lock UNUSED) { ASSERT (cond != NULL); ASSERT (lock != NULL); ASSERT (!intr_context ()); ASSERT (lock_held_by_current_thread (lock)); if (!list_empty (&cond->waiters)) { list_sort (&cond->waiters, sema_compare_priority, 0); sema_up (&list_entry (list_pop_front (&cond->waiters), struct semaphore_elem, elem)->semaphore); } }
donation priority
아래의 경우 우선순위가 높은 스레드(H)가 lock을 요청하지만 우선순위가 낮은 스레드(L)이 lock을 반환하지 않아 H보다 낮은 M이 cpu를 선점한다. 이런 경우 L스레드에 H의 우선순위을 기증하여 우선 lock을 반환하게 하여 H가 먼저 cpu를 선점하게 한다. 이를 donation priority라 한다.
이 경우는 매우 간단하지만 더욱 복잡한 Multiple donation과 Nested donation이 있다.
Multiple donation은 한 스레드에 기부가 여러번 일어나는 상황이다. 아래의 그림을 보면 쉽게 이해할 수 있다.
Nested donation은 다단계와 비슷하게 서로 얽혀있는 상태이다. 그래서 높은 우선순위의 요청을 해결하기 위해 여러 단계의 기부가 일어난다.
우선 우선순위 기부를 하기 위해 스레드에 우선순위 관련 인자들을 추가해준다.
struct thread
{
...
int init_priority;
struct lock *wait_on_lock;
struct list donations;
struct list_elem donation_elem;
...
};
init_priority는 스레드 생성시 부여되며 기증받은 우선순위를 반납하고 원상태로 돌아가기위해 기록해 두어야한다. wait_on_lock은 스레드가 얻고싶어 하는 lock을 기록한다. donations는 해당 스레드에 우선순위를 기부한 스레드들의 리스트이다. donation_elem은 다른 elem과 동일하게 donations를 탐색하기 위한 요소이다.
추가한 인자들을 init_thread에서 초기화 하게끔 init_thread를 수정한다.
/* thread/thread.c */
static void
init_thread (struct thread *t, const char *name, int priority)
{
...
t->init_priority = priority;
t->wait_on_lock = NULL;
list_init (&t->donations);
...
}
위 그림에서 H스레드가 Lock을 요청하면 L스레드에게 H스레드의 우선순위를 L에게 기부하게끔 lock_acquire를 수정해야한다.
/* thread/synch.c */
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;
}
홀더의 donations에 lock요청한 현재 스레드를 추가하고 donate_priority를 통해 우선순위를 기부한다. nested donation에서 보았듯이 연결된 스레드 모두에 기부가 일어나게끔 함수를 만들어준다.
/* thread/thread.c */
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;
}
}
이렇게 우선순위를 기부하게끔 함수를 수정하고 새로운 함수를 만들어 주었다. 이제 우선순위를 잘 반납하게끔 새로운 함수를 만들고 활용하면된다.
/* thread/thread.c */
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);
}
}
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;
}
}
remove_with_lock을 통해 donations를 순회하며 해당 lock을 가진 스레드를 donation에서 제거한다. 그리고 남아있는 donations에서 가장 높은 우선순위를 가진 스레드의 우선순위와 현재 스레드의 우선순위를 비교하여 만약 donations에서 가장 높은 우선순위를 가진 스레드의 우선순위가 더 높다면 현재 스레드에 해당 우선순위를 기부한다.
이 두 함수 lock_release와 thread_set_priority에 활용하면 다음과 같다.
/* thread/synch.c */
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);
}
/* thread/thread.c */
void
thread_set_priority (int new_priority)
{
thread_current ()->init_priority = new_priority;
refresh_priority ();
thread_test_preemption ();
}
thread_set_priority에 refresh_priority를 호출하는 이유는 thread_set_priority를 통해 donations내의 우선순위가 변경되거나 현재 스레드의 우선순위가 변경되어 재조정할 필요가 있는 경우가 있기 때문이다.