PintOS 프로젝트 1주차 [Threads / Priority Scheduling]

Priority Scheduling은 우선순위 스케줄링을 의미한다. Alarm Clock에서는 ready_list에 우선순위를 생각하지 않고 스레드를 삽입했고, 모든 스레드가 공평하게 CPU를 사용했기에 더 자주 CPU를 사용해야 할 스레드가 자주 CPU를 사용하지 못해서 비교적 비효율적 이었다.(FIFO방식)

 

이번엔 스레드마다 우선순위(Priority)를 부여해서 ready_list에 우선순위 순으로 정렬하여 삽입하고, 우선순위가 높은 스레드부터 CPU를 점유하도록 개선할 것이다.

 

또한, 이미 특정 스레드가 CPU를 사용하고 있더라도 더 높은 우선순위의 스레드가 ready_list에 들어오면 CPU를 빼앗는 선점(Preemption)도 구현할 것이다.

 

단 timer_interrupt마다 thread_awake()가 실행되고 ready_list에 스레드가 들어가는데, 이 때마다 Preemption을 하도록 하면 안 된다. 너무 자주 선점되어 오히려 오버헤드가 증가하여 비효율적일 수 있다는 이유 때문이다. 따라서 thread_create, , thread_set_priority 함수에만 선점을 추가해주면 된다.

 

thread_create()에 추가해 주는 이유는 thread가 생성되면 우선적으로 ready_list에 추가되기 때문이고,

thread_set_priority()에 추가해 주는 이유는, 해당 함수는 현재 실행중인 스레드의 priority를 바꾸는 것이기 때문에 running thread가 변경될 수 있기 때문이다.

 

스레드 우선순위를 관리하기 위해서는 3가지 메커니즘이 추가로 사용된다. Lock, Semaphore, Condition Variable이다.

 

Condition Variable

struct condition {

    struct list waiters;        /* List of waiting threads. */

};

 

condition 구조체는 list 형태의 waiters 라는 필드를 가지고 있다. 이 필드엔 semaphore_elem 형태로 대기자 세마포어들이 들어갈 것이다.

 

cond_wait 함수를 통해서 Lock을 가진 채로 running되던 스레드는 lock을 해제하고 blocked 상태로 들어가게 되며, 그 동안 condition의 waiters 리스트에서 대기한다. 이후 cond_signal을 받으면 waiters 리스트에서 제거된 후 작업을 위해 lock을 요청하게 된다.

 

여기서 만약 해당 lock의 semaphore value가 0이었다면, 해당 lock 의 semaphore의 waiters 리스트에 스레드가 추가되어 다시 blocked 상태로 기다린다.

 

즉, condition의 waiters 는 어떠한 이유로 스레드를 잠재울 때 lock을 release 하고 잠재우는 것이고

semaphore의 waiters 는 어떤 공유 자원을 기다리기 위한 대기로써 잠재우는 것이다.

 

condition의 waiters는 cond_signal을 받았을 때 깨어나고 lock을 요청하며,

semaphore의 waiters는 어떤 공유자원의 자리가 났을 때(lock을 해제했을 때 sema_up이 되는 경우) 깨어나서 lock을 점유하게 된다.

 

 

Semaphore_elem

struct semaphore_elem {

    struct list_elem elem;              /* List element. */

    struct semaphore semaphore;         /* This semaphore. */

};

 

Semaphore_elem은 대단한 건 아니고, 그저 각 semaphore를 list로써 관리하기 쉽게 하기 위해 elem을 추가하여 semaphore와 묶어둔 구조체이다.

 

 

Lock

struct lock {

    struct thread *holder;      /* Thread holding lock (for debugging). */

    struct semaphore semaphore; /* Binary semaphore controlling access. */

};

 

Lock은 자물쇠, 또는 열쇠라고 생각하면 된다.

Lock의 semaphore는 binary semaphore로써 0 또는 1 값만을 가진다. 

즉 Lock의 소유자(holder)가 존재할 때 semaphore value는 0이고, holder가 없을 때 semaphore value는 1이다.

Lock은 1명만 소유할 수 있기 때문에 binary semaphore로 동작한다.

또한, Lock의 소유자(holder)만이 lock을 해제할 수 있다.

 

Lock->semaphore->waiters 리스트에 해당 Lock을 기다리는 스레드들이 모여있다.

 

 

Semaphore

struct semaphore {

    unsigned value;             // 현재 값 /* Current value. */

    struct list waiters;        // 대기중인 스레드 목록 /* List of waiting threads. */

};

 

semaphore 구조체는 value와 waiters 필드로 이루어져 있다. 

value는 공유자원 (CPU 등)에 접근할 수 있는 스레드의 수를 의미한다. 만약 value가 0이라면 접근할 수 없는 상태인 것이다.

waiter는 해당 공유자원을 차지하기 위해 기다리는 스레드들이 담겨있다.

 

 

 

Priority

스레드 우선순위를 의미하며, 0 ~ 63 값을 가지고 기본값은 31이다. 숫자가 높을 수록 우선순위가 높다.

기본적으로 우선순위는 스레드가 create 될 때 정해진다.

 

 

Priority Inversion(우선순위 역전)

Priority Inversion

 

Priority Inversion은 우선순위가 낮은 스레드가 우선순위가 높은 스레드보다 먼저 CPU(또는 공유자원)를 점유하는 현상이다. 

 

아래와 같은 상황이라고 가정해보자.

H > M > L 순서의 우선순위를 가진다. H가 가장 높은 우선순위를 가진다.

H, L은 Lock에 영향을 받는 상태이고, M은 그렇지 않다(또는 다른 Lock에 영향을 받는다거나).

-> M이 H,L의 공유 자원에 접근하지 않는 경우, 또는 다른 공유 자원에 접근하려 할 때

-> 또는 아무런 공유 자원에 접근하지 않는 경우도 성립

 

L은 Lock을 가지고 있는 상태이다.

이 때 H가 L에게 CPU 요청을 하면 넘겨줄 수 없다. Lock 되어 있으니까.

 

하지만 H보다 우선순위가 낮은 M이 CPU를 요청하면 그냥 넘겨주게 된다. M은 H,L의 Lock에 영향을 받지 않는 상태니까. 게다가 L의 작업이 끝나지도 않았는데 Lock을 넘겨주게 되므로, M의 작업이 끝난 후 다시 L의 작업이 끝난 후 가장 마지막에 H가 Lock을 받고 CPU을 사용하게 된다.

 

이런 식으로 우선 순위에 맞지 않게 CPU가 점유되는 현상을 Priority Inversion(우선순위 역전) 이라고 한다.

이것을 해결할 수 있는 방법이 Priority Donation(우선순위 기부)이다.

 

 

Priority Donation(우선순위 기부)

Priority Donation

 

 

L이 Lock을 가지고 있는 상황에서 우선순위가 더 높은 H가 CPU를 요청할 경우, H의 우선순위를 잠시 빌려온다. L은 Lock을 H에게 넘겨줄 때 까지 H의 우선순위를 갖게 된다. 그리하여 Lock에 영향을 받지 않는 M이 CPU를 요청하더라도 L이 잠시동안 우선순위가 더 높기 때문에 CPU를 넘겨주지 않게 된다.

 

만약 L보다 우선순위가 높고 CPU를 요청한 스레드가 H 뿐만 아니라 여러 개라고 가정해보자. 이럴 땐 현재 Lock을 가진 holder 스레드의 Donation List에, Lock을 요청한 스레드들을 저장하게 된다. (Donation List는 각 스레드마다 가지고 있다) 그리고 L은 Donation List에서 가장 높은 우선순위를, 해당 스레드에게 CPU를 넘겨줄 때 까지 갖게 된다. CPU를 넘겨주고 나면 해당 lock을 기다리던 스레드들은 모두 기존 holder의 Donation List에서 지워진다.

 

이렇게 Priority Donation을 사용하면 우선순위에 따라서 정상적인 스케줄링이 가능하게 된다.

 

 

Nested Donation(중첩된 기부)

Nested Donation

 

Nested Donation은 Priority Donation이 중첩되어 일어난 현상을 말한다. 

 

아래 상황이라고 가정해보자.

L이 Lock A를 점유한 상태이다.

Lock B는 M이 점유한 상태이다.

이 때 M이 L에게 Lock A를 요청하면 L의 우선순위가 M과 동등해진다.

이후 H가 M에게 Lock B를 요청하면 어떻게 될까?

-> M은 L의 Lock A를 기다리고 있기 때문에, 결국 L이 Lock A를 반환한 후 M이 Lock A,B로 작업을 마친 후 Lock B를 H에게 넘겨줘야 끝이 난다.

-> 따라서 H의 우선순위를 기부하게 되는데, L과 H 모두가 H의 우선순위를 물려받게 된다.

-> H는 M에게 기부, M은 L에게 기부.... 

 

이렇게 각 스레드가 다른 Lock을 갖고 있고, 서로 의존관계가 맞물린 경우를 Nested Donation 이라고 한다.

 

donation list 현황

 

위 경우에서 각 스레드의 donation list는 이렇게 된다.

왜 L의 donation list가 [10, 5]가 아니냐고 물어볼 수 있는데, donation list엔 "해당 lock을 요청한 스레드"만 들어가기 때문에다.

M은 L이 가진 lock을 요청했고, H는 M이 가진 lock을 요청했기 때문에 리스트 현황이 저런 것이다. 그러나 M은 H에게 priority donation을 받은 상태이기 때문에, 해당 priority가 L에게도 영향을 주게 된다.

 

사실 일반적인 donation 상황이나, 각 스레드가 Lock을 최대 1개뿐만 가지는 nested 상황에서는 donation list가 필요가 없다.

가진 Lock이 하나뿐이고, 그 Lock을 해제하면 더이상 donation을 받지 않으니 donation list가 얼마나 컸든 전부 삭제될 뿐이다.

 

그렇다면 donation list는 언제 필요한 걸까? 바로 Multiple Donation 상황이다. 즉 하나의 스레드가 2개 이상의 Lock을 가진 상황.

 

 

Multiple Donation(다중 기부)

Multiple Donation

 

Multiple Donation 상황은 한 스레드가 여러 개의 Lock을 가지고 있을 때 일어난다.

 

스레드T1이 Lock A, B, C를 가지고 있는 상황에서 T2, T3, T4가 각각 A, B, C를 요청했다고 가정하자.

T1의 donation list는 [11, 12, 13]이 되고(priority 순 정렬) 가장 높은 13을 빌려 쓰게 된다.

 

이 때 T1이 Lock C를 해제하면, C를 기다리던 스레드인 T4(13)가 donation list에서 지워지고 T2(12), T3(11)만 남는다.

[11, 12] 이렇게.

 

T1은 아직 Lock A, B에 대한 donation을 받고 있기 때문에, 다시 이 리스트에서 가장 높은 priority를 빌려 사용한다.

이런 식으로 특정 Lock을 해제한 후, 다른 Lock을 요청한 스레드의 priority 중에서 다시 가장 높은 priority를 빌려야 하기 때문에 이것을 저장할 donation list가 필요한 것이다.

 

 

 

======================= 구현 ======================

 

thread.c

// list_insert_ordered를 위한 구현, priority 기준 정렬

bool compare_thread_priority(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);

    if (thread_a -> priority > thread_b -> priority) {

        return true;

    }

    else return false;

}

 

우리는 priority 순으로 스레드가 running 되게 만들어야 하기 때문에, ready_list로 스레드를 삽입하는 부분들을 전부 list_insert_ordered 함수로 정렬해서 넣어줄 필요가 있다.

 

compare_thread_priority 함수는 list_insert_ordered 함수의 정렬 기준을 정해주기 위한 함수이다.

이 함수를 인자로 넣으면 priority가 높은 스레드가 list의 HEAD쪽에 위치하게 된다.

 

 

thread.c

// 스레드 blocked에서 ready list로 넣고 state Ready로 바꿔주기

// 인터럽트 알아서 멈춰줌

void

thread_unblock (struct thread *t) {

    enum intr_level old_level;

    ASSERT (is_thread (t));

    old_level = intr_disable ();

    ASSERT (t->status == THREAD_BLOCKED);

    // 스레드 우선순위대로 정렬하여 ready_list에 삽입한다

    list_insert_ordered(&ready_list, &t->elem, compare_thread_priority, NULL);

    t->status = THREAD_READY;

    intr_set_level (old_level);

}

 

이렇게 priority를 비교하는 compare_thread_priority 함수를 만들어서 list_insert_ordered 함수의 3번째 인자로 넣어주자.

 

 

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) {

        // 우선순위대로 정렬하여 ready_list에 넣기

        list_insert_ordered(&ready_list, &curr->elem, compare_thread_priority, NULL);

    }

    do_schedule (THREAD_READY);

    intr_set_level (old_level);

}

 

현재 스레드에 대해서 CPU를 양보하고 ready_list에 들어가게 하는 하는 yield함수에서도 마찬가지로 list_insert_ordered 함수를 사용해서 priority 순으로 정렬해서 넣는다.

 

 

thread.c

// 현재 스레드와 ready_list의 HEAD를 비교하여 필요 시 yield하는 함수

void thread_preemption(void) {

    // ready_list가 비어 있지 않은 경우 진행

    if(!list_empty(&ready_list)) {

        // ready_list의 HEAD 가지고 오기

        struct list_elem *readyHead = list_front(&ready_list);

        struct thread *readyHeadt = list_entry(readyHead, struct thread, elem);

        // 현재 스레드의 우선순위가 ready_list HEAD의 우선순위보다 작다면 yield하기

        if(thread_current()->priority < readyHeadt->priority) {

            thread_yield();

        }

    }

}

 

선점 함수이다. 현재 실행 중인 스레드와 ready_list HEAD에 존재하는 스레드의 우선순위를 비교해, 필요 시 CPU를 yield한다.

이곳저곳에서 쓰일 함수이니 미리 만들어 둔다.

 

 

thread.c

tid_t

// 스레드 이름, 우선순위, 스레드가 실행할 함수, 함수에 전달할 보조 인자

thread_create (const char *name, int priority,

        thread_func *function, void *aux) {

    struct thread *t;

    tid_t tid;

    ASSERT (function != NULL);

    /* Allocate thread. */

    // 스레드 할당 + 생성

    t = palloc_get_page (PAL_ZERO);

    // 실패했으면 에러 리턴

    if (t == NULL)

        return TID_ERROR;

    /* Initialize thread. */

    // 스레드 이름, 우선순위, tid 초기화

    init_thread (t, name, priority);

    tid = t->tid = allocate_tid ();

    /* Call the kernel_thread if it scheduled.

     * Note) rdi is 1st argument, and rsi is 2nd argument. */

    t->tf.rip = (uintptr_t) kernel_thread;

    t->tf.R.rdi = (uint64_t) function;

    t->tf.R.rsi = (uint64_t) aux;

    t->tf.ds = SEL_KDSEG;

    t->tf.es = SEL_KDSEG;

    t->tf.ss = SEL_KDSEG;

    t->tf.cs = SEL_KCSEG;

    t->tf.eflags = FLAG_IF;

    /* Add to run queue. */

    // 스레드가 생성되면, 일단 바로 ready_list에 들어가게 된다.

    thread_unblock (t);

    // ready_list에 들어갔으니 우선순위 체크하여 필요 시 선점한다

    thread_preemption();

    // 스레드 id를 반환

    return tid;

}

 

thread_create 함수이다. 스레드가 create 되면 바로 ready_list에 들어가기 때문에, 우선순위를 비교하여 필요 시 선점하는 로직이 필요하다. 따라서 방금 만들어 둔 선점 함수인 thread_preemption 함수를 로직에 추가해 주자.

 

 

thread.c

// 우선순위 변경 후 ready_list HEAD랑 비교해서 필요하다면 yield하기

void

thread_set_priority (int new_priority) {

    struct thread *cur = thread_current();

    // 현재 실행중인 스레드 우선순위 변경

    // cur->priority = new_priority;

    cur->originPriority = new_priority;

   

    // 필요 시 yield하기

    thread_preemption();

}

 

thread_set_priority 함수이다. 현재 running 중인 스레드의 priority를 변경하는 함수인데, priority를 변경했으니 다른 스레드의 우선순위가 더 높아졌을 수 있다. 따라서 마찬가지로 선점 로직이 필요하기 때문에, thread_preemption 함수를 추가한다.

 

 

thread.c

// donation 리스트가 비어 있으면 originPriority로 복구하고, 남아 있다면 가장 높은 Priority를 가져온다

void refresh_priority(void) {

    // release 할 현재 스레드 가져오기

    struct thread *cur = thread_current();

    cur->priority = cur->originPriority;

    if(!list_empty(&cur->donation)) {

        // donation list의 첫 번째 스레드를 가져오기

        struct thread *front = list_entry(list_front(&cur->donation), struct thread, donationElem);

        // donation list의 첫 번째 스레드 우선순위가 현재 스레드 우선순위보다 높으면 바꿔주기

        if(front->priority > cur->priority) {

            cur->priority = front->priority;

        }

    }

}

 

refresh_priority 함수이다.

현재 스레드의 donation list를 확인해서, 더 높은 priority를 가진 스레드가 있다면 priority를 빌려온다.

 

이제 Semaphore, Lock, Condition variable을 건드려 보자.

 

 

synch.c

void

sema_down (struct semaphore *sema) {

    enum intr_level old_level;

    ASSERT (sema != NULL);

    ASSERT (!intr_context ());

    old_level = intr_disable ();

    // value가 0이면, 즉 들어갈 수 없다면 waiters 에 들어가기

    // if여도 기능상 문제는 없지만 while로 하는게 race condition이나 Spurious Wakeup (가짜 깨어남) 상황에서

    // 올바르게 동작하게 해 준다

    while(sema->value == 0) {

       

        // waiters 리스트에 우선순위 정렬하여 스레드 삽입

        list_insert_ordered(&sema->waiters, &thread_current()->elem, compare_thread_priority, NULL);

        // waiters에 있는 동안 block된다

        thread_block ();

    }

    sema->value--;

    intr_set_level (old_level);

}

 

sema_down 함수이다. 특정 공유 자원(CPU등)을 기다리는 스레드들은 semaphore의 waiters 리스트에 priority 순으로 정렬되어 저장된다. 따라서 list_insert_ordered 함수를 사용해야 한다.

 

공유자원을 차지하기 위해서 sema_down을 실행했을 때 만약 sema->value가 0 이라면 현재 공유자원에 접근할 수 없다는 뜻이기 때문에 waiters 리스트로 들어가서 공유자원이 해제되고 sema_up이 되기를 기다린다.

 

그 동안 스레드는 block되어 있다가 sema_up 함수에 의해서 깨어나면 sema->value--; 부분을 실행하게 되는 것이다.

 

 

synch.c

// waiters의 스레드를 1개 unblock하고, semaphore 값을 1 올리는 함수

void

sema_up (struct semaphore *sema) {

    enum intr_level old_level;

    ASSERT (sema != NULL);

    old_level = intr_disable ();

    // waiter가 존재할 때 진행

    if (!list_empty (&sema->waiters)) {

       

        // waiters 우선순위 순으로 정렬해주기

        list_sort(&sema->waiters, compare_thread_priority, NULL);

        // unblock으로 인해 ready_list로 들어갈 때 우선순위 정렬되어 들어가게 된다.

        thread_unblock (list_entry (list_pop_front (&sema->waiters),

                    struct thread, elem));

    }

    // sema 값 올리기, 이후 unblock된 스레드가 알아서 바로 down 한다

    sema->value++;

    // waiters의 스레드가 unblock되어 ready_list에 들어갔으니, 우선순위에 따라 선점하도록 함수 실행

    thread_preemption();

    intr_set_level (old_level);

}

 

sema_up 함수이다. sema_down에서 waiters에 잠들어 있던 스레드가 이 함수에 의해 unblock되고 ready_list로 들어간다.

unblock돼서 ready_list에 있다가 running되면 sema_down에서 못 했던 코드들로 복귀해 sema 값을 down하고 작업을 실행하는 것이다.

 

그리고 ready_list에 들어갔다면 당연히 선점 조건을 확인해야 하기 때문에 thread_preemption() 함수를 추가해 준다.

 

 

synch.c

bool sema_compare_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {

    struct semaphore_elem *a_sema = list_entry(a, struct semaphore_elem, elem);

    struct semaphore_elem *b_sema = list_entry(b, struct semaphore_elem, elem);

    struct list *waiter_a_sema = &(a_sema->semaphore.waiters);

    struct list *waiter_b_sema = &(b_sema->semaphore.waiters);

    struct thread *aHead = list_entry(list_begin(waiter_a_sema), struct thread, elem);

    struct thread *bHead = list_entry(list_begin(waiter_b_sema), struct thread, elem);

    if(aHead->priority > bHead->priority) {

        return true;

    }

    else {

        return false;

    }

}

 

이 함수도 list_insert_ordered의 인자로 들어가기 위한 함수이다.

아래에서 바꿀 cond_wait 함수에서는 condition 구조체의 waiters 리스트에 대기자를 저장할 때, semaphore_elem 구조체 단위로 저장한다.

 

이 함수는 "condition -> waiters" 에 저장된 요소들을, "semaphore_elem -> semaphore -> waiters -> HEAD 스레드 -> priority" 기준으로 정렬시켜주는 함수이다. 

 

 

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));

    // 0으로 초기화 해 두면, sema_down을 실행할 때 스레드가 대기 상태가 된다(waiters list에 들어간다)

    sema_init (&waiter.semaphore, 0);

    // cond waiters의 각 세마포어의 우선순위가 가장 높은 스레드끼리만 비교하여 sema를 정렬해서 넣는다.

    list_insert_ordered(&cond->waiters, &waiter.elem, sema_compare_priority, NULL);

    // 현재 스레드의 lock 풀기

    lock_release (lock);

    // down을 실행하고 기다리기. 위에서 value 0 으로 초기화 했으므로, 외부에서 cond_signal을 줄 때까지 자게 된다.(blocked)

    sema_down (&waiter.semaphore);

    // cond_signal을 받아서 unblock 되면, 그 때 lock을 요청한다.

    lock_acquire (lock);

}

 

cond_wait는 현재 스레드를 잠들게 하는 함수이다.

 

잠든 스레드는 특정 조건이 달성되어 cond_signal 함수로 깨워지기 전까지 cond_wait의 waiters 리스트에 Block상태로 저장되어 있다. 현재 스레드가 lock을 가지고 있다면, 다른 스레드가 사용할 수 있도록 잠들기 전에 해제하고 잠든다.

 

이후 cond_signal로 깨어나면 작업 진행을 위해 lock_acquire로 lock을 요청하게 된다.

 

 

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)) {

        // cond waiters 우선순위 순으로 정렬

        list_sort(&cond->waiters, sema_compare_priority, NULL);

        // condition waiters에 있는 HEAD semaphore_elem의 semaphore를 가져와서 sema_up 해준다.

        sema_up(&list_entry (list_pop_front (&cond->waiters), struct semaphore_elem, elem)->semaphore);

    }

}

 

cond_wait 으로 인해 자고 있는 스레드를 깨우는 cond_signal 함수이다.

waiters 리스트는 애초에 정렬되어 저장되지만 wait 도중에 priority가 바뀌었을 수도 있으니 한번 더 정렬을 수행한 후 가장 priority가 높은 스레드를 깨워준다.

 

 

 

 ============================

 

이제 Priority Donation에 관한 코드들을 작성해야 하는데, 글이 너무 길어져서 다음 글로 나누겠다.