💡 우선순위가 높은 스레드가 먼저 CPU를 점유할 수 있도록 Priority Scheduling을 구현한다.
스레드들은 각 우선순위에 따라 ready list에 추가된다.
현재 실행 중인 스레드의 우선순위보다 높은 우선순위의 스레드가 ready list에 추가되면, 현재 실행 중인 스레드는 바로 CPU를 양도한다.
스레드는 언제든지 자신의 우선순위를 변경할 수 있다.
lock, semaphore, condition variable을 사용하여 대기하고 있는 스레드가 여러 개인 경우, 우선순위가 가장 높은 스레드가 먼저 깨어나야 한다.
thread_yield
, thread_unblock
/* thread.c */
void thread_yield(void)
{
struct thread *curr = thread_current();
enum intr_level old_level;
ASSERT(!intr_context());
old_level = intr_disable();
if (curr != idle_thread)
list_insert_ordered(&ready_list, &curr->elem, cmp_thread_priority, NULL);
do_schedule(THREAD_READY);
intr_set_level(old_level);
}
/* thread.c */
void thread_unblock(struct thread *t)
{
enum intr_level old_level;
ASSERT(is_thread(t));
old_level = intr_disable();
ASSERT(t->status == THREAD_BLOCKED);
list_insert_ordered(&ready_list, &t->elem, cmp_thread_priority, NULL);
t->status = THREAD_READY;
intr_set_level(old_level);
}
cmp_thread_priority
/* thread.h */
bool cmp_thread_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED);
/* thread.c */
bool cmp_thread_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
struct thread *st_a = list_entry(a, struct thread, elem);
struct thread *st_b = list_entry(b, struct thread, elem);
return st_a->priority > st_b->priority;
}
thread_create
, thread_wakeup
preempt_priority()
호출 )/* thread.c */
tid_t thread_create(const char *name, int priority,
thread_func *function, void *aux)
{
...
/* Add to run queue. */
thread_unblock(t);
preempt_priority();
return tid;
}
/* thread.c */
void thread_wakeup(int64_t current_ticks)
{
enum intr_level old_level;
old_level = intr_disable(); // 인터럽트 비활성
struct list_elem *curr_elem = list_begin(&sleep_list);
while (curr_elem != list_end(&sleep_list))
{
struct thread *curr_thread = list_entry(curr_elem, struct thread, elem); // 현재 검사중인 elem의 스레드
if (current_ticks >= curr_thread->wakeup_ticks) // 깰 시간이 됐으면
{
curr_elem = list_remove(curr_elem); // sleep_list에서 제거, curr_elem에는 다음 elem이 담김
thread_unblock(curr_thread); // ready_list로 이동
preempt_priority();
}
else
break;
}
intr_set_level(old_level); // 인터럽트 상태를 원래 상태로 변경
}
thread_set_priority
preempt_priority()
호출 )/* thread.c */
void thread_set_priority(int new_priority)
{
thread_current()->init_priority = new_priority;
preempt_priority();
}
preempt_priority
/* thread.h */
void preempt_priority(void);
/* thread.c */
void preempt_priority(void)
{
if (thread_current() == idle_thread)
return;
if (list_empty(&ready_list))
return;
struct thread *curr = thread_current();
struct thread *ready = list_entry(list_front(&ready_list), struct thread, elem);
if (curr->priority < ready->priority) // ready_list에 현재 실행중인 스레드보다 우선순위가 높은 스레드가 있으면
thread_yield();
}
/* Test: /threads에서 입력 */
make check
👇🏻 구현 전
👇🏻 구현 후
priority 관련 테스트 4개를 더 통과했다!
sema_down
, cond_wait
/* 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) // 세마포어 값이 0인 경우, 세마포어 값이 양수가 될 때까지 대기
{
list_insert_ordered(&sema->waiters, &thread_current()->elem, cmp_thread_priority, NULL);
thread_block(); // 스레드는 대기 상태에 들어감
}
sema->value--; // 세마포어 값이 양수가 되면, 세마포어 값을 1 감소
intr_set_level(old_level);
}
/* 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_insert_ordered(&cond->waiters, &waiter.elem, cmp_sema_priority, NULL);
lock_release(lock);
sema_down(&waiter.semaphore);
lock_acquire(lock);
}
cmp_sema_priority
/* thread.h */
bool cmp_sema_priority(const struct list_elem *a, const struct list_elem *b, void *aux);
/* synch.c */
bool cmp_sema_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
struct semaphore_elem *sema_a = list_entry(a, struct semaphore_elem, elem);
struct semaphore_elem *sema_b = list_entry(b, struct semaphore_elem, elem);
struct list *waiters_a = &(sema_a->semaphore.waiters);
struct list *waiters_b = &(sema_b->semaphore.waiters);
struct thread *root_a = list_entry(list_begin(waiters_a), struct thread, elem);
struct thread *root_b = list_entry(list_begin(waiters_b), struct thread, elem);
return root_a->priority > root_b->priority;
}
sema_up
, cond_signal
preempt_priority()
호출 )/* synch.c */
void sema_up(struct semaphore *sema)
{
enum intr_level old_level;
ASSERT(sema != NULL);
old_level = intr_disable();
if (!list_empty(&sema->waiters)) // 대기 중인 스레드를 깨움
{
// waiters에 들어있는 스레드가 donate를 받아 우선순위가 달라졌을 수 있기 때문에 재정렬
list_sort(&sema->waiters, cmp_thread_priority, NULL);
thread_unblock(list_entry(list_pop_front(&sema->waiters), struct thread, elem));
}
sema->value++;
preempt_priority(); // unblock이 호출되며 ready_list가 수정되었으므로 선점 여부 확인
intr_set_level(old_level);
}
/* synch.c */
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, cmp_sema_priority, NULL);
sema_up(&list_entry(list_pop_front(&cond->waiters),
struct semaphore_elem, elem)
->semaphore);
}
}
/* Test: /threads에서 입력 */
make check
👇🏻 구현 전
👇🏻 구현 후
priority - sema, condvar 테스트 2개를 더 통과했다!