Priority Scheduling

struct thread { // 동일 코드... int64_t wakeup_tick; /* 깨워야 할 tick */ int base_priority; // 기존 우선순위 struct lock* waiting_lock; // 대기중인 lock struct list_elem donation_elem; // 내가 다른 스레드의 donation_list에 들어갈 때 쓰이는 원소 struct list donation_list; // 나에게 donation해준 스레드들의 리스트 // 동일 코드... };

static void init_thread (struct thread *t, const char *name, int priority) { // 동일 코드... t->base_priority = priority; t->waiting_lock = NULL; // 동일 코드... }

tid_t thread_create (const char *name, int priority, thread_func *function, void *aux) { // 동일한 코드... /* 새로 생성된 스레드가 현재 스레드보다 우선순위가 높으면 양보 */ if (t->priority > thread_current()->priority) { thread_yield(); } // 동일한 코드... }

int thread_get_priority (void) { // 인터럽트 끄기 enum intr_level old_level = intr_disable(); struct thread* current_thread = thread_current(); // 현재 스레드 // 인터럽트 다시 켜기 intr_set_level(old_level); // 이미 계산된(기부 상황이면 기부까지 반영된) 우선순위 값 반환 return current_thread->priority; }

// 우선순위 비교 함수(내림차순) static bool priority_compare(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) { struct thread *thread_a = list_entry(a, struct thread, elem); struct thread *thread_b = list_entry(b, struct thread, elem); return thread_a->priority > thread_b->priority; }

void thread_yield (void) { // 동일 코드... if (curr != idle_thread) list_insert_ordered(&ready_list, &curr->elem, priority_compare, NULL); // 동일 코드... }

void thread_set_priority (int new_priority) { // 현재 스레드 struct thread* current_thread = thread_current(); current_thread->base_priority = new_priority; // 인터럽트 끄기 enum intr_level old_level = intr_disable(); // donation이 적용된, 최종 우선순위 계산 // 나한테 기부한 스레드가 없다면, 기존 우선순위 if(list_empty(&current_thread->donation_list)) { current_thread->priority = new_priority; } // 나한테 기부한 스레드가 있다면, 기부받은 우선순위와 기존 우선순위 중 더 높은 값을 최종 우선순위 값으로 설정 else { // donation_list는 우선순위 순으로 정렬된 상태(내림차순) struct thread* highest_donated_thread = list_entry(list_front(&current_thread->donation_list), struct thread, donation_elem); if(highest_donated_thread->priority > new_priority) { current_thread->priority = highest_donated_thread->priority; } else { current_thread->priority = new_priority; } } // 현재 스레드의 우선순위가 최고가 아니라면, 즉시 CPU 양보 // ready_list는 우선순위 순으로 정렬된 상태(내림차순) bool should_yield = false; if(!list_empty(&ready_list)) { struct thread *highest_priority_thread = list_entry(list_front(&ready_list), struct thread, elem); if(current_thread->priority < highest_priority_thread->priority) { should_yield = true; } } // 인터럽트 다시 켜기 intr_set_level(old_level); // yield는 인터럽트 복원 후에 수행 if(should_yield) { thread_yield(); } }

// 현재 스레드의 우선순위가 최고가 아니라면, 즉시 CPU 양보 // ready_list는 우선순위 순으로 정렬된 상태(내림차순) bool should_yield = false; if(!list_empty(&ready_list)) { struct thread *highest_priority_thread = list_entry(list_front(&ready_list), struct thread, elem); if(current_thread->priority < highest_priority_thread->priority) { should_yield = true; } } // 인터럽트 다시 켜기 intr_set_level(old_level); // yield는 인터럽트 복원 후에 수행 if(should_yield) { thread_yield(); }

void lock_acquire (struct lock *lock) { ASSERT (lock != NULL); ASSERT (!intr_context ()); ASSERT (!lock_held_by_current_thread (lock)); // lock 소유 스레드가 있으면 우선순위 기부 struct thread* current_thread = thread_current(); if(lock->holder != NULL) { current_thread->waiting_lock = lock; donate_priority(current_thread, lock->holder); } sema_down (&lock->semaphore); // lock 획득 성공 후 정리 current_thread->waiting_lock = NULL; lock->holder = thread_current (); }

void donate_priority(struct thread* giver, struct thread* receiver){ if(receiver == NULL || giver == NULL) return; int depth = 0; // 8단계 이상 기부 방지 struct thread* current_giver = giver; struct thread* current_receiver = receiver; // 체인을 따라가면서 기부 수행 while(current_receiver != NULL && depth < 8) { // 기부할 필요가 없으면 중단 if(current_giver->priority <= current_receiver->priority) { break; } // 우선순위 기부 current_receiver->priority = current_giver->priority; // 중복 방지 : receiver의 donation_list에 이미 giver가 있으면 제거 if(!list_empty(&current_receiver->donation_list)) { struct list_elem* element = list_begin(&current_receiver->donation_list); while(element != list_end(&current_receiver->donation_list)) { struct thread* td = list_entry(element, struct thread, donation_elem); if(td == current_giver) { // 이미 기부한 기록이 있으면 제거 list_remove(element); break; } element = list_next(element); } } // receiver의 donation_list에 giver 추가 (receiver가 giver로부터 기부받았다는 기록) list_insert_ordered(&current_receiver->donation_list, &current_giver->donation_elem, donation_priority_compare, NULL); // 다음 단계로 진행 (nested donation) if(current_receiver->waiting_lock != NULL && current_receiver->waiting_lock->holder != NULL) { current_giver = current_receiver; // 현재 receiver가 다음 giver current_receiver = current_receiver->waiting_lock->holder; depth++; } else { break; // 더 이상 진행할 곳이 없음 } }}void donate_priority(struct thread* giver, struct thread* receiver) { if(receiver == NULL || giver == NULL) return; int depth = 0; // 8단계 이상 기부 방지 struct thread* current_giver = giver; struct thread* current_receiver = receiver; // 체인을 따라가면서 기부 수행 while(current_receiver != NULL && depth < 8) { // 기부할 필요가 없으면 중단 if(current_giver->priority <= current_receiver->priority) { break; } // 우선순위 기부 current_receiver->priority = current_giver->priority; // receiver의 donation_list에 giver 추가 (receiver가 giver로부터 기부받았다는 기록) list_remove(&current_receiver->donation_elem); // 중복 추가 방지 list_insert_ordered(&current_receiver->donation_list, &current_giver->donation_elem, donation_priority_compare, NULL); // 다음 단계로 진행 (nested donation) if(current_receiver->waiting_lock != NULL && current_receiver->waiting_lock->holder != NULL) { current_giver = current_receiver; // 현재 receiver가 다음 giver current_receiver = current_receiver->waiting_lock->holder; depth++; } else { break; // 더 이상 진행할 곳이 없음 } } }

void lock_release (struct lock *lock) { ASSERT (lock != NULL); ASSERT (lock_held_by_current_thread (lock)); // donation 정리 및 우선순위 업데이트 remove_donations(lock); update_priority_of_thread(thread_current()); lock->holder = NULL; sema_up (&lock->semaphore); }

void remove_donations(struct lock *lock) { struct thread* current_thread = thread_current(); struct list_elem* elem = list_begin(&current_thread->donation_list); while(elem != list_end(&current_thread->donation_list)) { struct thread* td = list_entry(elem, struct thread, donation_elem); // td가 기다리는 lock이 인자로 받은 lock과 같다면, donation_list에서 제거 if(td->waiting_lock == lock) { elem = list_remove(elem); } else { // 기다리던 lock이 아니면, 다음 원소로 이동 elem = list_next(elem); } } }

void update_priority_of_thread(struct thread* t) { // donation_list가 우선순위 순으로 정렬되어 있으므로, 첫 번째 요소가 가장 높은 우선순위를 가짐 if(!list_empty(&(t->donation_list))) { struct thread* highest_donor = list_entry(list_front(&t->donation_list), struct thread, donation_elem); t->priority = (highest_donor->priority > t->base_priority) ? highest_donor->priority : t->base_priority; } else { // donation이 없으면 기본 우선순위로 복원 t->priority = t->base_priority; } }

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->value++; if(!list_empty (&sema->waiters)) { list_sort(&sema->waiters, priority_compare, NULL); // 정렬(우선순위 기준 내림차순) struct thread* unblocked_thread = list_entry(list_pop_front (&sema->waiters), struct thread, elem); thread_unblock(unblocked_thread); // 깨운 스레드의 우선순위가 현재 스레드보다 높으면 양보(선점) if(unblocked_thread->priority > thread_current()->priority) { thread_yield(); } } intr_set_level (old_level); }