Priority Scheduling
Pintos에서 우선순위 스케줄링 및 우선순위 기부를 구현하세요.
현재 실행 중인 스레드보다 우선순위가 높은 새로운 스레드가 ready 목록에 추가되면 현재 스레드는 즉시 프로세서를 새로운 스레드에 양보해야 합니다. 마찬가지로, 스레드가 lock, semaphore 또는 condition variable을 기다리고 있는 경우, 대기 중인 스레드 중 가장 높은 우선순위 스레드가 먼저 깨어나야 합니다. 스레드는 언제든지 자체의 우선순위를 높이거나 낮출 수 있지만, 우선순위를 낮춰 현재 가장 높은 우선순위를 가지지 않게 되면 CPU를 즉시 양보해야 합니다.
스레드의 우선순위는 PRI_MIN(0)에서 PRI_MAX(63)까지의 범위를 가집니다. 낮은 숫자가 낮은 우선순위를 나타내므로, 우선순위 0은 가장 낮은 우선순위이고, 우선순위 63은 가장 높은 우선순위입니다. 초기 스레드 우선순위는 thread_create()에 전달되는 인자로 설정됩니다. 다른 우선순위를 선택할 이유가 없다면 PRI_DEFAULT(31)를 사용하세요. PRI_ 매크로는 threads/thread.h에 정의되어 있으며, 이 값을 변경해서는 안 됩니다.
우선순위 스케줄링의 한 가지 문제는 "우선순위 역전"입니다. 높은, 중간, 낮은 우선순위 스레드 H, M 및 L을 고려해보세요. H가 L(예를 들어, L이 보유한 락 때문)을 기다려야 하고 M이 ready 목록에 있는 경우, 낮은 우선순위 스레드는 CPU 시간을 받지 못하므로 H는 CPU를 얻지 못합니다. 이 문제를 해결하기 위한 부분적인 방법은 H가 L이 락을 보유하는 동안 우선순위를 L에 "기부"하고, L이 해제되면(따라서 H가 획득함) 기부를 되돌리는 것입니다.
우선순위 기부를 구현하세요. 기부가 필요한 모든 상황을 고려해야 합니다. 하나의 스레드에 여러 개의 기부가 이루어지는 경우를 처리해야 하며, 여러 우선순위가 하나의 스레드에 기부되는 경우도 처리해야 합니다. 또한 중첩된 기부에 대해 처리해야 합니다: H가 M이 보유한 락을 기다리고 있고 M이 L이 보유한 락을 기다리고 있다면 M과 L은 모두 H의 우선순위로 높여져야 합니다. 필요한 경우 중첩된 우선순위 기부의 깊이에 합리적인 제한을 설정할 수 있습니다(예: 8단계).
락에 대한 우선순위 기부를 구현해야 합니다. Pintos 동기화 구조물의 다른 우선순위 기부는 구현할 필요가 없습니다. 그러나 모든 경우에 우선순위 스케줄링을 구현해야 합니다.
마지막으로, 스레드가 자체 우선순위를 조사하고 수정할 수 있는 다음 함수를 구현하세요. 이러한 함수에 대한 뼈대 코드는 threads/thread.c에 제공됩니다.
void execute_max_priority(void) { // 우선순위가 가장 높은 스레드를 실행
if (!list_empty(&ready_list)) { // 대기하는 스레드가 있다면
struct thread *max_thread = list_entry(list_begin(&ready_list), struct thread, elem);
if (max_thread->priority > thread_get_priority()) {
if (!intr_context())
thread_yield(); // 우선순위가 높은 스레드에게 cpu 양보
}
}
}
void thread_set_priority (int new_priority);
현재 스레드의 우선순위를 새로운 우선순위로 설정합니다. 현재 스레드가 더 이상 가장 높은 우선순위가 아니라면, 양보합니다.
void thread_set_priority(int new_priority) {
if (list_empty(&thread_current()->donations)) {
thread_current()->priority = new_priority; // 스레드의 우선순위 설정
}
thread_current()->init_priority = new_priority;
execute_max_priority();
}
int thread_get_priority (void);
현재 스레드의 우선순위를 반환합니다. 우선순위 기부가 있는 경우 더 높은(기부된) 우선순위를 반환합니다.
다른 스레드의 우선순위를 직접 수정하는 인터페이스를 제공할 필요는 없습니다.
우선순위 스케줄러는 이후의 프로젝트에서 사용되지 않습니다.
int thread_get_priority(void) {
return thread_current()->priority; // 스레드의 우선순위 반환
}
lock, semaphore, cond_var에 대한 구현
void lock_acquire(struct lock *lock) { // 락 요청
ASSERT(lock != NULL);
ASSERT(!intr_context());
ASSERT(!lock_held_by_current_thread(lock));
if (lock->holder != NULL) { // 락 홀더가 있다면
thread_current()->wait_on_lock = lock; // 해당 락 대기
if (!thread_current()->is_user_thread)
donate_priority(); // 우선순위 기부
}
sema_down(&lock->semaphore); // 락의 세마 다운
thread_current()->wait_on_lock = NULL; // 세마 다운을 탈출하면 락을 획득했으므로 대기 삭제
lock->holder = thread_current(); // 해당 스레드가 락 홀더
}
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_push_back(&sema->waiters, &thread_current()->elem); // 세마 대기 리스트에 push
thread_block();
}
sema->value--; // 세마 업으로 while문 탈출하면 세마 획득했으므로 세마 값 -1
intr_set_level(old_level);
}
void lock_release(struct lock *lock) {
ASSERT(lock != NULL);
ASSERT(lock_held_by_current_thread(lock));
lock->holder = NULL; // 락 홀더 해제
if (!thread_current()->is_user_thread) {
remove_with_lock(lock);
refresh_priority();
sort_donation_list(); // donation_list 정렬
}
sema_up(&lock->semaphore); // 해당 락에 대한 세마 업
execute_max_priority();
}
void sema_up(struct semaphore *sema) {
enum intr_level old_level;
ASSERT(sema != NULL);
old_level = intr_disable();
list_sort(&(sema->waiters), priority_less, NULL); // 세마 대기 리스트 우선순위로 정렬
if (!list_empty(&sema->waiters))
thread_unblock(list_entry(list_pop_front(&sema->waiters), // 가장 앞에 있는 스레드 unblock
struct thread, elem));
sema->value++; // 세마 반납 후 세마 값 +1
intr_set_level(old_level);
execute_max_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));
list_sort(&cond->waiters, cd_priority_less, NULL);
if (!list_empty(&cond->waiters))
sema_up(&list_entry(list_pop_front(&cond->waiters),
struct semaphore_elem, elem)
->semaphore);
}
우선순위 기부 구현
void donate_priority(void) {
build_donations();
percolate_up();
sort_donation_list();
}
void build_donations(void) {
struct thread *receiver = thread_current()->wait_on_lock->holder; // 현재 락 홀더가 우선순위를 기부 받음
for (struct list_elem *tmp = list_begin(&(receiver->donations)); tmp != list_end(&(receiver->donations)); tmp = list_next(tmp)) {
struct thread *tmp_thread = list_entry(tmp, struct thread, donation_elem);
if (tmp_thread->wait_on_lock == thread_current()->wait_on_lock && tmp_thread->priority < thread_current()->priority) {
list_remove(tmp);
list_insert_ordered(&(receiver->donations), &(thread_current()->donation_elem), d_priority_less, NULL);
return;
}
}
list_insert_ordered(&(receiver->donations), &(thread_current()->donation_elem), d_priority_less, NULL);
} // donation list에 넣어서 관리
void percolate_up(void) {
struct thread *receiver = thread_current()->wait_on_lock->holder;
while (receiver->priority < thread_current()->priority) { // 중첩된 우선순위 기부 처리
receiver->priority = thread_current()->priority;
if (receiver->wait_on_lock == NULL) {
break;
}
receiver = receiver->wait_on_lock->holder;
}
}
void sort_donation_list(void) {
struct thread *root = thread_current();
while (root->wait_on_lock != NULL) {
root = root->wait_on_lock->holder;
}
list_sort(&(root->donations), d_priority_less, NULL); // donation_list 우선순위에 따라 정렬
}
