[week08] PintOS - Project 1(thread) : Priority scheduling(3) donation

Project1: priority schedule(3)

Priority Inversion Problem

문제 : priority 높은 thread가 priority가 낮은 thread를 기다리는 현상

L, M, H는 thread의 이름이라고 하자. 그리고 우선순위는 H가 가장 높고, L이 가장 낮다.

지금 M보다 H가 우선순위가 높은데, L이 lock을 가지고 있기 때문에 H는 실행되지 못하고, L보다 우선순위가 큰 M이 먼저 실행된다. H는 M이 다 끝날때까지 기다려야 한다.

해결책 : priority donation

H이 lock을 획득하려고 요청할 때, L에게 자신의 priority를 donate(기부)한다. 이렇게 되면 M보다 H가 먼저 실행되어서 문제를 해결할 수 있다.

그러나 이렇게 간단하게 priority donation을 하면 모든 문제가 해결되는 것은 아니다.

PintOS GITBOOK에서는

💡 Be sure to handle multiple donations, You must also handle nested donation

이라고 명시되어있다. 두 가지 종류의 donation 문제를 살펴보자.

Multiple Donation 상황

thread가 두 개 이상의 lock 보유시 각 lock을 획득하고자 하는 thread들에게 donation 발생가능

예시) thread L이 lock A와 lock B를 점유하고 있을 때 thread M이 lock A를 요청, thread H가 lock B를 요청하는 상황

고려해야 할 요소

이전 상태의 우선순위를 기억하도록 만듬(donation list 사용, refresh priority 사용)

Nested Donation 상황

lock B를 점유하기 위해서는 lock A도 반환되어야 하는 상황

예시) thread H가 lock B(thread M이 점유중)를 얻기 위해 대기하고 있고,

thread M은 lock A(thread L이 점유중)를 얻기 위해 대기하고 있는 상태

고려해야 할 요소

thread H의 우선순위는 thread L, M에게 모두 donation되어야 함

코드 추가 및 변경사항

struct thread

각 thread가 donation 받은 내역을 관리할 수 있게 thread의 구조체를 변경해주자.

// threads/thread.h

// priority donation
    int init_priority;  // 최초 스레드 우선순위 저장.
    struct lock *wait_on_lock;  // 현재 thread가 요청했는데 받지못한 lock. 기다리는중
    struct list donations; // 자신에게 priority 를 나누어준 thread의 list
    struct list_elem donation_elem; // 위의 thread list를 관리하기위한 element. thread 구조체의 elem과 구분.

새로운 요소를 추가했으므로 초기화도 수정해주자.

// threads/thread.c

static void
init_thread (struct thread *t, const char *name, int priority) {
    ASSERT (t != NULL);
    ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
    ASSERT (name != NULL);

    memset (t, 0, sizeof *t);
    t->status = THREAD_BLOCKED;
    strlcpy (t->name, name, sizeof t->name);
    t->tf.rsp = (uint64_t) t + PGSIZE - sizeof (void *);
    t->priority = priority;
    t->magic = THREAD_MAGIC;
    // priority donation
    t->init_priority = priority;
    t->wait_on_lock = NULL;
    list_init (&t->donations);
}

lock acquire

lock_acquire() 함수는 thread가 lock을 요청할 때 실행된다.

lock이 다른 thread에 의해 점유되고 있다면 자신의 priority가 높은경우, 내 priority를 donate하여 현재 lock을 점유하고 있는 thread가 우선적으로 실행되어 lock을 빨리 반환하도록 해야한다.

// thread/synch.c

void
lock_acquire (struct lock *lock) {
    ASSERT (lock != NULL);
    ASSERT (!intr_context ());
    ASSERT (!lock_held_by_current_thread (lock));
    struct thread *cur = thread_current ();
    if (lock->holder) {
        cur->wait_on_lock = lock;
        list_insert_ordered (&lock->holder->donations, &cur->donation_elem, 
        thread_compare_donate_priority, 0);
        donate_priority ();
    }
    sema_down (&lock->semaphore);
    cur->wait_on_lock = NULL; // sema down 에서 lock을 얻었으므로 필요한 lock이 NULL.
    lock->holder = cur; // lock->holder를 현재 thread로 만듬
}

lock_acquire() 함수를 요청하는 thread가 실행되고 있다는 의미는 지금 lock을 가지고 있는 thread보다 우선순위가 높다는 뜻이므로 별다른 조건은 필요가 없다.

list_insert_ordered 함수 안에 thread_compare_donate_priority 함수가 있는데, 이 함수는 donation_elem에 대해 priority 비교를 해주는 함수이다.

// threads/thread.c

// priority donation 
// donation_elem에 대해 priority 비교를 해주는 함수
bool
thread_compare_donate_priority (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
    return list_entry (a, struct thread, donation_elem)-> priority
                > list_entry (b, struct thread, donation_elem) -> priority;
}

donate priority

lock을 점유하고 있는 holder thread에게 priority를 넘겨주는 함수이다.

// threads/thread.c

void 
donate_priority (void)
{
    int depth;
    struct thread *cur = thread_current ();

    for (depth = 0; depth < 8; depth++) { // 최대깊이 8(GITBOOK예시로 나와있음)
        if (!cur->wait_on_lock) break;
            struct thread *holder = cur->wait_on_lock->holder;
            holder->priority = cur->priority;
            cur = holder; // 우선순위가 낮았던 holder부터 실행을 해야하므로 cur를 holder로 바꿔서 지금 실행.
    }
}

lock release

// thread/synch.c

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

    remove_with_lock (lock);
    refresh_priority ();

    lock->holder = NULL;
    sema_up (&lock->semaphore);
}

lock이 가진 holder를 비우고 sema_up() 함수를 실행한다. sema_up() 함수를 실행하여 lock의 점유를 반환하기 전에 나에게 priority를 빌려준 thread들을 donations list에서 제거하고, priority를 재설정하는 작업이 필요하다.

// threads/thread.c
void
remove_with_lock (struct lock *lock)
{
    struct list_elem *e;
    struct thread *cur = thread_current ();

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

cur->donations 리스트를 처음부터 끝까지 돌면서 wait_on_lock이 이번에 release하는 lock이라면 해당 thread를 list에서 지운다.

위에서 priority를 재설정해야 한다고 말했는데, 그 함수인 refresh_priority 함수를 살펴보자.

// threads/thread.c

void
refresh_priority (void) 
{
    struct thread *cur = thread_current ();
    cur->priority = cur->init_priority;
    if (!list_empty (&cur->donations)) {
        list_sort (&cur->donations, thread_compare_donate_priority, 0);
        struct thread *front = list_entry (list_front (&cur->donations), 
        struct thread, donation_elem);
        if (front->priority > cur->priority)
            cur->priority = front->priority;
    }
}

donations 리스트가 비어있다면 init_priority로 초기화되고, donations 리스트에 thread가 남아있다면, 남아있는 thread 중에서 가장 높은 priority를 가져온다.

함수의 원형을 header file에 선언해주는 거 잊지말자.

// threads/thread.h

// priority donation
bool
thread_compare_donate_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);

마지막으로 thread_set_priority에서 priority의 변경이 일어난 경우, refresh_priority() 함수를 사용해서 조정을 해줘야 한다.

void
thread_set_priority (int new_priority) {
    thread_current ()->init_priority = new_priority;

    refresh_priority (); // 이거 추가
    thread_test_preemption ();
}

실행결과

priority 관련한 test들은 모두 pass 가능!

참고자료

조원 ipad 그림자료

한양대학교 핀토스 운영체제 실습(Youjip Won)

[Pintos] Project 1 : Thread(스레드) - Priority Inversion(donation)