-
[Pintos] Project 1 : Thread(스레드) - Priority Scheduling(2)프로젝트/Pintos 2021. 4. 30. 09:23
이번에는 동기화 도구들의 스케쥴링 방식을 살펴보자. 스케쥴링 도구들의 코드는 thread 폴더의 synch.h, synch.c 에 구현되어 있다. 우리가 다루어야 할 동기화 도구는 lock, semaphore, condition variable 3가지이다. 하나씩 살펴보자.
/* thread/synch.h */ struct semaphore { unsigned value; /* Current value. */ struct list waiters; /* List of waiting threads. */ }; struct lock { struct thread *holder; /* Thread holding lock (for debugging). */ struct semaphore semaphore; /* Binary semaphore controlling access. */ }; struct condition { struct list waiters; /* List of waiting threads. */ };semaphore 은 공유 자원의 개수를 나타내는 value 와 공유 자원을 사용하기 위해 대기하는 waiters 의 리스트를 가진다. lock 은 value = 1인 특별한 semaphore 로 구현되어 있고, 현재 lock 을 가지고 있는 thread 정보와 semaphore 를 멤버로 가진다. condition 은 condition variables 가 만족하기를 기다리는 waiters 의 리스트를 가진다.
Semaphore
semaphore 를 예로 들면, 하나의 공유자원을 사용하기 위해 여러 스레드가 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); }semaphore 를 다루는 함수는 sema_down, sema_up 두 가지이다. 공유 자원을 사용하고자 하는 스레드는 sema_down 을 실행하고, 사용 가능한 공유자원이 없다면 sema->waiters 리스트에 list_push_back 함수로 맨 뒤에 추가된다. 공유자원의 사용을 마친 스레드가 sema_up 을 하면 thread_unblock 을 하는데, list_pop_front 함수로 sema->waiters 리스트의 맨 앞에서 꺼내는 것을 볼 수 있다. 이전 포스트에서 봤던 ready_list 와 똑같이 리스트에 들어온 순서대로 차례로 실행되는 방식을 따르는 것을 알 수 있다. ready_list 에서 했던 것처럼 이번에도 priority 에 따라 자원을 할당받도록 만들어보자. 추가할 때는 priority 에 내림차순으로 리스트에 추가하고 꺼낼 때는 그대로 맨 앞에서 꺼내면 된다.
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); }while 문장 안에 있던 list_push_back 을 list_insert_ordered 을 사용하여 내림차순으로 정렬되도록 추가하였다. semaphore 에 추가되는 element 들은 스레드이므로 스레드에서 사용하였던 thread_compare_priority 함수를 그대로 사용하면 된다.
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); }sema_up 에서는 waiters 리스트에 있던 동안 우선순위에 변경이 생겼을 수도 있으므로 waiters 리스트를 내림차순으로 정렬하여 준다. <lib/kernel/list.c> 에 있는 list_sort 함수를 사용하면 간단하게 가능하다. 그 후 unblock 된 스레드가 running 스레드보다 우선순위가 높을 수 있으므로 thread_test_preemption () 함수를 실행하여 CPU 선점이 일어나게 해준다.
이렇게 하면 semaphore 에 대한 작업은 끝이났다. 다음은 lock 의 구조를 살펴보자.
/* thread/synch.c */ void lock_acquire (struct lock *lock) { ASSERT (lock != NULL); ASSERT (!intr_context ()); ASSERT (!lock_held_by_current_thread (lock)); sema_down (&lock->semaphore); lock->holder = thread_current (); } void lock_release (struct lock *lock) { ASSERT (lock != NULL); ASSERT (lock_held_by_current_thread (lock)); lock->holder = NULL; sema_up (&lock->semaphore); }lock 을 다루는 두 함수를 살펴보면 알 수 있듯이 마지막이 sema_down, sema_up 으로 끝난다. 즉 lock 은 value = 1 이고, holder 정보를 가지고 있다는 것을 제외하고는 semaphore 와 동일하게 동작하기 때문에 sema_down, sema_up 을 이미 처리해주었으므로 lock 은 따로 처리해 줄 필요가 없다는 것을 알 수 있다.
Condition variables
우선 condition variables 을 다루는 cond_wait, cond_signal 함수를 살펴보자.
/* 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); } }condition variables 도 마찬가지로 waiters 리스트를 가지고 있는데, semaphore 와 다른 점이 하나가 있다. semaphore 는 waiters 가 스레드들의 리스트였다면 condition variables 의 waiters 는 세마포들의 리스트라는 점이다. cond_wait 함수의 list_push_back 부분을 보면 알 수 있는데, cond->waiters 리스트에 waiter.elem 을 추가하는데 여기서 waiter 는 함수의 맨 위에서 선언한 세마포 element 이다. 이 점을 유의하면서 진행하여 보자. 이 condition variables 에 묶여있는 여러 세마포들의 리스트 중에서 가장 우선순위가 높은 하나의 세마포를 깨워야 하는데, 이미 각 세마포의 waiters 리스트는 위의 세마포를 다루는 함수에서 내림차순으로 정렬되게 하였으므로 각 세마포의 waiters 리스트의 맨 앞의 element 가 각 세마포에서 가장 priority 가 큰 스레드이고 이들을 비교하여 가장 큰 priority 를 가진 스레드를 가진 세마포를 깨우면 된다.
여기서도 마찬가지로 list_push_back 함수를 list_insert_ordered 로 바꾸어주는 것이 거의 전부이다. 이번에는 입력받는 파라미터가 스레드가 아니라 semaphore_elem.elem 로 들어오기 때문에 thread_compare_priority 함수는 사용하지 못하고, semaphore_elem 가 나타내는 세마포의 waiters 리스트의 맨 앞 thread 끼리 priority 를 비교하는 함수가 필요하다. (semaphore_elem 구조체는 synch.c 에 선언되어 있다.)
/* 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; }semaphore_elem.elem 을 입력받으면 list_entry 로 semaphore_elem 구조체를 구하여 저장하고 이 구조체가 가지는 semaphore 의 waiters 리스트를 받아온다. 이 waiters 리스트의 맨 앞 element 스레드의 priority 끼리 비교하여 반환하면 된다. 얼핏 복잡해 보이지만 천천히 따라가며 이해해보길 바란다.
비교함수를 만들었으니 cond_wait 를 완성할 수 있다.
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_insert_ordered (&cond->waiters, &waiter.elem, sema_compare_priority, 0); lock_release (lock); sema_down (&waiter.semaphore); lock_acquire (lock); }list_push_back 대신에 list_insert_ordered 함수에 sema_compare_priority 를 사용해서 가장 높은 priority 를 가지는 스레드가 묶어있는 세마포가 가장 앞으로 오도록 내림차순으로 cond->waiters 리스트에 push 한다.
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); } }깨울 때도 마찬가지로, wait 도중에 priority 가 바뀌었을 수 있으니 list_sort 로 내림차순으로 정렬해주고, sema_up 은 그대로 맨 앞에서 꺼내도록 둔다.
결과
2개의 테스트를 더 통과한 것을 볼 수 있다. 방금 우리가 구현한 priority-sema, priority-condvar 가 pass 가 나왔다. FAIL 의 숫자가 빠르게 줄어가는 것이 보기 좋다. 다음 시간에는 priority-donate 문제를 풀어보도록 한다.
'프로젝트 > Pintos' 카테고리의 다른 글