IT 성장기 (교육이수)/크래프톤정글 (2025.03-07)

[PintOS] Project 1 : Priority Donation 구현

eezy 2025. 5. 30. 14:58

PintOS Project 1 : Priority Donate

과제 설명

Priority Donation

Priority Donation은 우선순위 역전 (Priority Inversion) 문제를 해결하기 위한 기법이다. 우선순위 역전은 낮은 우선순위의 스레드가 자원을 점유하고 있을 때, 높은 우선선위의 스레드가 해당 자원을 기다리면서 실행되지 못하고, 그 사이 중간 우선순위의 스레드가 실행되는 상황을 말한다.

Gitbook 에서 말한 예시를 자세히 살펴보자. 아래는 단일 기부 방식 형태이다.

H (priority 50) : 락 A를 기다리는중
L (priority 10) : 락 A를 가지고 있음
M (priority 30) : 아무 락도 안 기다리고 CPU를 계속 쓴다. 락이 필요 없는 함수.
이 경우, L이 우선순위가 낮으니까 CPU를 못받아서 락 A를 놓을 수 없고 → 따라서 H가 절대 실행될 수 없다. → 우선순위 역전 발생
해결 : H가 기다리는 락 A의 소유자인 L에게 자신의 우선순위를 기부한다 (우선순위 : H = 50, L = 50) → CPU가 L을 먼저 실행하여 H가 락을 획득. → 우선순위 : L = 10 으로 강등

Nested Donation

스레드(H)가 락(A)을 기다리는데, 그 락의 소유자(M)가 또 다른 락(B)을 기다리고 있고, 그 락의 소유자가 또 다른 스레드(L)인 경우이다. 우선순위 기부가 연쇄적으로 전파되는 구조이다.

Multiple Donation

하나의 락을 여러 높은 우선순위의 스레드가 기다리는 경우. 하나의 대상에게 여러 스레드가 동시에 우선순위를 기부하고, 락의 소유자는 가장 높은 우선순위를 기부 받으며, 나머지는 무시함.

구현 목표

priority-donate-* 은 다양한 우선순위 기부 상황에서 구현이 올바르게 작동하는지 검증합니다.
스레드가 기다리는 락을 추적하고 기부받은 우선순위 리스트를 관리한다.
락을 해제할 때 우선순위를 정확히 복원해야 한다.
priority-sema 는 semaphore를 이용한 스레드 우선순위에 따라 ready_list를 정렬한다.
priority-condvar는 조건변수와 waiters 리스트를 우선순위 기준으로 관리해 가장 높은 우선순위의 스레드가 깨어나도록 구현한다.

구현 : Priority Donations

구조체 추가

경로 : include/threads/thread.h

struct thread

struct thread {    
    int original_priority;
    struct lock *wait_lock;
    struct list donations;
    struct list_elem donation_elem;
}

/* Project 1 : 함수 선언 */
bool cmp_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED);
void donate_priority (void);
void remove_with_lock (struct lock *lock);
void refresh_priority(void);
void test_max_priority(void);

수정 함수 구현

경로 : threads/synch.c

lock_acquire

락을 기다리는 donation 리스트에 접근하기 전에 인터럽트를 비활성화한다
curr→wait_lock = lock; : lock holder가 존재하면, 현재 스레드는 해당 락을 기다린다고 표시한다
락의 소유자의 donation 리스트에 현재 스레드를 우선순위 기준으로 삽입한다
donate_priority()를 호출하여 우선순위를 전파한다 → 함수 내부에서 재귀적으로 donation chain이 수행될 수 있다
락을 대기할 때 세마포어를 다운시킨다. 세마포어 값이 0이면 대기하고, 1 이상이면 감소시키면서 락을 획득한다
락을 획득하면 wait_lock 상태를 NULL로 초기화하고, 락의 소유자를 현재 스레드로 갱신한다.

void
lock_acquire (struct lock *lock) {
    ASSERT (lock != NULL);
    ASSERT (!intr_context ());
    ASSERT (!lock_held_by_current_thread (lock));

    enum intr_level old_level = intr_disable();
    struct thread *curr = thread_current();

    /* Project 1 - priority donate */
    if(lock->holder != NULL){
        curr->wait_lock = lock;
        list_insert_ordered(&lock->holder->donations, &curr->donation_elem, cmp_donation_priority, NULL);
        donate_priority();
    }

    sema_down (&lock->semaphore);        // 락 요청
    curr->wait_lock = NULL;                // 락 대기자 리스트에서 제거
    lock->holder = curr;                // 락 부여 후 holder 설정
    intr_set_level(old_level);
}

lock_release

donations list에서 스레드를 제거하고 우선순위를 원복한다
sema_down()에서 대기 중이던 스레드 중 하나에게 락을 넘겨줄 수 있도록 wake-up
락을 놓은 직후 현재 스레드보다 더 높은 우선순위를 가진 ready 스레드가 있다면 즉시 CPU를 양보한다

void
lock_release (struct lock *lock) {
    ASSERT (lock != NULL);
    ASSERT (lock_held_by_current_thread (lock));

    enum intr_level old_level = intr_disable();

    remove_with_lock(lock);
    refresh_priority();

    lock->holder = NULL;

    sema_up (&lock->semaphore);
    thread_yield();
    intr_set_level(old_level);
}

경로 : threads/thread.c

thread_set_priority

priority: 현재 우선순위 (donation 결과까지 반영됨)
original_priority: 원래 우선순위 (기부받기 전 기준)
refresh_priority 함수를 사용하여 우선순위 변경으로 인한 donation 정보를 갱신한다
test_max_priority 함수를 사용하여 priority donation을 수행하고 스케줄링한다

void
thread_set_priority (int new_priority) {
    /* Project 1 : Priority */
    struct thread *curr = thread_current();
    enum intr_level old_level = intr_disable();

    thread_current()->priority = new_priority;
    thread_current()->original_priority = new_priority;
    refresh_priority();
    test_max_priority();

    intr_set_level(old_level);
}

추가 함수 구현

void donate_priority(void)

락을 대기하고 있는 인자가 있는 경우, 락을 가지고 있는 스레드에게 우선순위를 기부한다
이 때 nested donation의 경우 재귀 호출의 깊이를 제한하여 무한 루프를 방지한다.
현재 스레드보다 기다리는 락의 소유자(holder)의 우선순위가 낮다면 → holder에게 우선순위를 기부한다
그 다음 holder를 curr로 바꾸어 우선순위 기부를 전파한다

void
donate_priority (void){
    int depth;
    struct thread *curr = thread_current();
    int priority = curr->priority;

    for(depth = 0; depth < 8; depth++){
        if(!curr->wait_lock)
            break;
        struct thread *holder = curr->wait_lock->holder;
        if(holder->priority < priority){
            holder->priority = priority;
        }
        curr = holder;
    }
}

void remove_with_lock(struct lock *lock)

락을 해지한 후 waiters 리스트에서 스레드를 삭제한다
리스트를 확인하여 해지할 lock을 보유하고 있는 스레드를 찾아 삭제한다

void
remove_with_lock (struct lock *lock){
    struct thread *curr = thread_current();
    struct list_elem *e;

    for(e = list_begin(&curr->donations); e != list_end(&curr->donations); e = list_next(e)){
        struct thread *t = list_entry(e, struct thread, donation_elem);
        if(t->wait_lock == lock)
            list_remove(&t->donation_elem);
    }
}

void refresh_priority(void)

우선순위를 원래대로 복구하거나
아직 기부자 리스트가 남아있다면, 그 중 가장 높은 우선순위로 재설정한다

void
refresh_priority(void){
    struct thread *t = thread_current();
    t->priority = t->original_priority;

    if(list_empty(&t->donations))
        return;
    list_sort(&t->donations, cmp_priority, 0);

    struct list_elem *max_elem = list_front(&t->donations);
    struct thread *max_thread = list_entry(max_elem, struct thread, donation_elem);

    if(t->priority < max_thread->priority){
        t->priority = max_thread->priority;
    }
}

bool cmp_donation_priority

기부받은 우선순위 스레드들을 정렬된 리스트에 넣기 위한 비교 함수

bool
cmp_donation_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED){
    struct thread *t_a = list_entry(a, struct thread, donation_elem);
    struct thread *t_b = list_entry(b, struct thread, donation_elem);

    if(t_a->priority == t_b->priority){
        return t_a->tid < t_b->tid;
    }else{
        return t_a->priority > t_b->priority;
    }
}

구현 : Semaphore

수정 함수 구현

경로 : threads/synch.c

sema_down

세마포어 값이 0이면 현재 스레드를 대기(waiters 리스트에 삽입)시키고 thread_block 한다
세마포어 값이 1 이상이면 -1을 감소하고 즉시 반환한다
waiters 리스트에 접근하기 전에 인터럽트를 비활성화한다
PRI_DEFAULT 로 예외 처리를 한 이유는 thread_current 가 대기 리스트에 삽입되기 전에 sema→value == 0 이지만 자원이 할당되지 않음에도 루프를 탈출하는 경우가 있었다.
이때 priority가 정상적으로 전달되지 않아 cmp_priority 함수로 제대로 정렬을 하지 않는 문제가 있었다.
그래서 기본 우선순위로 donation 전이라면 맨 뒤로 보내고, 그 다음 루프에서 정렬을 시도했다.

void
sema_down (struct semaphore *sema) {
    enum intr_level old_level;

    ASSERT (sema != NULL);
    ASSERT (!intr_context ());

    old_level = intr_disable ();
    /* Project 1 : priority-sema */
    while (sema->value == 0) {
        if(thread_current()->priority != PRI_DEFAULT){
            list_insert_ordered(&sema->waiters, &thread_current()->elem, cmp_priority, NULL);
        }else{
            list_push_back (&sema->waiters, &thread_current ()->elem);
        }
        thread_block ();
    }
    sema->value--;
    intr_set_level (old_level);
}

sema_up

세마포어 자원을 하나 반환(증가)하면서,
그 자원을 기다리던 스레드 중 가장 높은 우선순위를 가진 스레드를 깨워서 ready 상태로 전환한다

void
sema_up (struct semaphore *sema) {
    enum intr_level old_level;

    ASSERT (sema != NULL);

    old_level = intr_disable ();
    if (!list_empty (&sema->waiters)){
        /* Project 1 : priority-sema */
        list_sort(&sema->waiters, cmp_priority, NULL);
        thread_unblock (list_entry (list_pop_front (&sema->waiters),
                    struct thread, elem));
    }
    sema->value++;
    test_max_priority();
    intr_set_level (old_level);
}

추가 함수 구현

bool cmp_sema_priority

sema waiters 리스트 정렬
waiters 리스트에 우선순위를 기준으로 삽입될 수 있도록 비교하는 함수를 구현한다
만약 waiters 리스트에 아무것도 없는 경우를 위한 if 분기문을 추가하여, 커널 패닉을 방지한다

bool
cmp_sema_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED){
    struct semaphore_elem *sa = list_entry(a, struct semaphore_elem, elem);
    struct semaphore_elem *sb = list_entry(b, struct semaphore_elem, elem);

    if (list_empty(&sa->semaphore.waiters))    return false;
    if (list_empty(&sb->semaphore.waiters))    return true;

    struct thread *ta = list_entry(list_front(&sa->semaphore.waiters), struct thread, elem);
    struct thread *tb = list_entry(list_front(&sb->semaphore.waiters), struct thread, elem);

    return ta->priority > tb->priority;
}

Trouble Shooting

donations 리스트만 정렬하면 된다고 생각하여, waiters 리스트 정렬을 간과하였다

내 생각으로는 기부 우선순위만 관리하면 된다고 생각해서 donate_priority로 우선순위를 올려주고, donations 리스트를 정렬해두면 그 스레드가 높은 priority를 갖게 되고, CPU를 먼저 받을 수 있다고 생각했다.

또한 waiters 리스트는 ready_list 처럼 스케줄링에 직접 영향을 줄 것이라고 생각하지 않았다. 단순 대기열로만 생각을했지만, 사실 sema_up 함수를 보면 waiters 리스트를 기준으로 스레드의 깨어나는 순서를 결정한다.

그래서 처음에는 아래와 같이 waiters 리스트를 순회하며 가장 우선순위가 높은 max_elem을 꺼내는 방식으로 했었으나, 생각해보니 매번 스레드를 찾을때 리스트를 순회하는것이 비효율적이었고, 리스트를 정렬된 상태로 유지하는 것이 가장 안정적이라 생각하여 변경하였다.

👉 기존 코드

void
sema_up (struct semaphore *sema) {
    enum intr_level old_level;

    ASSERT (sema != NULL);

    old_level = intr_disable ();
    if (!list_empty (&sema->waiters)){
        /* Project 1 : priority-sema */
        struct list_elem *max_elem = list_max(&sema->waiters, cmp_sema_priority, NULL);
      list_remove(max_elem);
      thread_unblock(list_entry(max_elem, struct thread, elem));
    }
    sema->value++;
    test_max_priority();
    intr_set_level (old_level);
}

구현 : Condvar

수정 함수 구현

경로 : threads/synch.c

cond_wait

이 함수는 스레드가 어떤 조건이 만족될 때까지 기다린다.
조건 변수의 waiters 리스트에 semaphore_elem을 우선순위 기준으로 정렬하여 삽입한다
cmp_sema_priority()는 내부 waiter.semaphore.waiters 리스트의 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);
    /* Project 1 : priority-condvar */
    list_insert_ordered(&cond->waiters, &waiter.elem, cmp_sema_priority, NULL);
    lock_release (lock);
    sema_down (&waiter.semaphore);
    lock_acquire (lock);
}

cond_signal

조건이 충족되었음을 알릴때 호출된다
현재 락을 가진 스레드가 signal을 호출하고 조건변수에 기다리고 있는 스레드 중 가장 앞의 스레드를 깨운다
이 때, 리스트 정렬을 유지하여 우선순위가 가장 높은 스레드를 깨운다

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)){
        /* Project 1 : priority-condvar */
        list_sort(&cond->waiters, cmp_sema_priority, NULL);
        sema_up (&list_entry (list_pop_front (&cond->waiters), struct semaphore_elem, elem)->semaphore);
    }
}

테스트 결과