[DevLog][PintOS] PRJ1 Threads/Priority Scheduling

우선순위 스케줄링

Assignment Overview

우선순위를 고려해 스레드를 스케줄링해라. 크게 두 가지 step이 있다. 첫 번째는 단순히 준비 큐를 정렬하고, 즉시 CPU를 양도하면 해결된다. 두 번째는 동기화 (synchronization)와 관련된 문제로, 여러 가지 동기화 메커니즘에서도 우선순위대로 스레드가 실행될 수 있게 처리해주면 된다. 이를 위한 방법이 우선순위 기증 (priority donation)이다.

• 문제 1: 주어진 우선순위대로 스레드가 실행되도록 만들어라
  • 스레드는 준비 큐에서 우선순위 순서대로 나와야 한다.
  • 현재 스레드보다 우선순위가 높은 스레드가 준비 큐에 들어오면, 즉시 CPU를 양보해야 한다.
  • 현재 스레드의 우선순위가 변경되면, 준비 큐의 스레드와 우선순위를 비교해서 적절히 실행해야 한다.
• 문제 2: 우선순위 역전 (Priority Inversion)을 해결해라.
  • 현재 스레드가 자신보다 우선순위가 낮은 스레드에 의해 막혀 실행이 되지 못하고 있는 문제를 해결해라
  • 여기서 '막혀 실행이 되지 못하고 있는' 상태란 구체적으로 lock, semaphore, conditional variable 등의 동기화 메커니즘에 의해 blocked 된 상태를 말한다.
  • 이러한 경우, 현재 스레드가 자신을 막고 있는 스레드에게 자신의 우선순위를 기증(donation)해서 lock을 빨리 해제하도록 해야 한다.
  • 스레드가 lock을 풀고 나올 때, 만약 기증받은 우선순위가 있으면 모두 반환하여, 실제 더 높은 우선순위를 가지고 있는 스레드에게 즉시 CPU를 양도하여야 한다.
  • 하나의 스레드는 여러 개의 lock을 가지고 있을 수 있고(multiple), 접근하려고 하는 lock을 가진 스레드가 다른 lock에 접근하기 위해 대기하고 있을 수 도 있다. (nested)

Implementation

01) 문제 1

1) 준비 큐를 우선순위순으로 정렬해야 한다.

이는 준비 큐에 스레드를 넣을 때 삽입 정렬을 하거나, 뺄 때 리스트를 검색하여 최대 우선순위부터 스케줄링하는 것으로 해결할 수 있다. 우리 팀은 삽입 정렬 방식으로 진행했다.

void thread_unblock(struct thread* t) {
    ...
    list_insert_ordered(&ready_list, &t->elem, high_priority, NULL);
    ...
}

/* compare function */
bool high_priority(struct list_elem* _a, struct list_elem* _b, void* aux) {
    struct thread* a = list_entry(_a, struct thread, elem);
    struct thread* b = list_entry(_b, struct thread, elem);
    return a->priority > b->priority; 
}

2) 현재 스레드보다 우선순위가 높은 스레드가 오면 CPU를 즉시 양보해야 한다.

우선순위가 변경되면 이에 맞게 처리해야 한다. (내가 낮아졌으면 양보해야 할 상황이 생길 수 있음)

void thread_create(...) {
    ...

    thread_unblock(t);  /* ready_list에 삽입 정렬 */

    thread_yield();     /* 한 번 yield를 실행합니다. */
    intr_enable();      /* yield로 CPU를 점유하게 된 스레드가 인터럽트를 허용 */
}

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

    thread_yield();     /* 한 번 yield를 실행합니다. */
}

이 두 가지 조건은 스레드가 생성될 때, 그리고 우선순위가 변경될 때 thread_yield()를 한 번씩 실행해 줌으로서 해결할 수 있다. 준비 큐가 늘 우선순위 높은순으로 유지되기 때문이다. thread_yield()를 실행하면, 현재 실행중이던 스레드를 준비 큐에 (삽입정렬으로) 넣고 schedule()을 호출하여 다음에 실행될 스레드를 큐에서 뽑는다. 이 때 현재 스레드와 다음 스레드가 다르면 thread_launch()를 호출해 (현재 레지스터 상태를 저장하고, 다음 스레드의 context를 올리는) 실질적인 context switching이 일어나게 된다. 이 조건문 (if(curr != next))이 이미 걸려 있으므로, thread_create()나 thread_set_priority()에서 따로 우선순위를 비교하는 조건문을 걸지 않고, thread_yield를 바로 호출해도 된다.

문제 2) Donation

동기화가 개입되면서 문제가 복잡해진다. 내가 코드를 짜면서 어려웠던 지점이 몇 가지 있었다.

1. 함수의 실행이 하나의 스레드에서 원자적으로 일어나지 않는다. 코드의 각 라인이 어느 스레드에서 어디까지 실행되고 넘어가는지를 머릿속으로 따라가는 것이 헷갈렸다.
2. donate를 한 스레드와 donate를 받은 스레드를 구체적으로 어떻게 관리할 것인가?
3. lock이 multiple하게 걸린 경우와 nested하게 걸린 경우, lock_acquire와 lock_release에서 어떤 처리를 해 줘야 할까?

1) 스레드 상태 변화를 잘 추적하자

1번 문제와 같은 경우가 다음의 상황이다. 우선순위가 낮은 low 스레드가 lock의 holder인 상황에서 current_thread인 high가 lock_acquire를 시도한다고 하자.

void lock_acquire(struct lock* lock) {
    ... // 기타등등..

    struct thread* curr = thread_current();
    struct thread* holder = lock->holder;

    /* donation */
    if(holder && curr->priority > holder->priority) {
        holder->priority = curr->priority;
    }

    sema_down(...);
    lock->holder = thread_current();

    /* 나는 sema의 주인이 되었다! 여기서 기증했던 것을 반환받으면 안 될까? */
    /* 예를 들어 이전 holder를 저장해두고, holder->priority = old_priority */
    ...
}

코멘트에 달린 부분에 기증의 반환 로직을 짜면 안 된다. 왜냐하면, holder의 우선순위를 잔뜩 올려 놓은 상태에서 lock을 획득한 후 반환을 하고자 한들, holder의 실행에 막혀 정작 진짜 우선순위가 높았던 나(현재 실행중인 스레드)는 실행이 안 되고 holder가 끝날 때 까지 ready_list에만 남아있게 되기 때문이다. 즉, sema_down 라인의 다음 코드가 바로 실행되지 않는다.

그래서 acquire할 때는 나를 막고 있는 스레드 (lock->holder)의 우선순위를 높여주어야 하고, lock_release를 할 때는 (우선순위가 가장 낮은 입장에서) 나의 lock해제를 기다리고 있던 스레드들이 기증한 우선순위를 모두 반환해야 한다. 다른 말로 하면, acquire에서는 higer thread, release에서는 lower thread의 입장에서 로직을 짜야 한다.

동기화 문제 뿐만 아니라, 스레드를 다루면서는 코드 각 라인을 실제로 어떤 스레드가 실행하게 되는지를 잘 생각해야 한다.

2) donation 정보를 갖는 자료구조를 잘 설계하자

donation의 관계를 잘 생각해 봐야 한다. donate를 하는 스레드와, donate를 받는 스레드의 관계는 일대 다 관계이다. 어떤 스레드 t가 donate를 했다면, t는 lock에 막혀 waiters의 리스트에 blocked된 상태로 들어가 있을 것이다. 따라서, 한 스레드는 여러 개의 lock을 waiting하는 상태가 될 수 없다.

하지만 donate을 받는 입장에서는, 여러 스레드로부터 우선순위를 donate를 받을 수 있다. 따라서 이는 리스트 또는 배열로 관리해야 한다. 우리 조에서는 먼저 배열의 아이디어를 떠올렸다.

struct thread {

    ...
    int donate_list[64];     /* 내가 받은 donation */
    struct thread* holder;   /* 내가 donate한 애 */
    ...
}

/* donate을 받는 상황에서는 */
lock->holder->donate_list[curr_priority]++;

/* donate을 회수하는 상황에서는 */
curr_thread->donate_list[donator_priority]--;

이런 식으로 기증받은 우선순위를 관리한다. 우선순위가 donation으로 인해 변경될 수 있으므로, 우선순위를 반환하거나 비교하는 함수도 모두 바꾸어준다.

내가 donate한 스레드를 의미하는 holder의 정보는, nested donation을 위해 필요하다. 내가 lock a에 접근했는데, lock a의 holder가 lock b의 waiters에 들어가 있다면, lock->holder->holder와 같은 식으로 holder를 검색해서 lock b의 holder에게 나의 우선순위를 기증해야 한다.

/* donate을 고려하여 특정 스레드의 최고 우선순위를 반환하려면 */
int thread_max_priority(struct thread* t) {
    int i = 0;
    int max_priority = t->priority;

    for(; i < 64; i++) {
        if(t->donate_list[i] > 0 && i > max_priority) {
            max_priority = i;
        }
    }
    return max_priority;
}

/* 현재 스레드의 우선순위 구하는 함수 갱신! */
int thread_get_priority(void) {
    return thread_max_priority(thread_current());
}

/* ordered list insert의 비교함수도 갱신! */
bool high_priority(...) {
    ...
    return thread_max_priority(a) > thread_max_priority(b);
}

마지막으로, 준비 큐에 있는 스레드의 우선순위가 donation으로 인해 바뀔 수 있음을 고려해야 한다. 대부분의 test case에서 donate을 받는 스레드가 main으로 하나라서 잘 통과되었지만, 만약 준비 큐에서 대기하고 있던 여러 스레드가 donate을 받았다면, 준비 큐가 재정렬될 필요성이 생긴다. 이 때도 물론 thread_next_to_run에서 최고 우선순위를 검색하여 뽑을 수 있지만, 우리 조에서는 한번 reorder(?) 해주기로 했다.

// sync.c
void lock_acquire(struct lock* lock) {
    ...

    /* 여기서 lock->holder에게 donation을 했다면 */
    /* ready_list에서 한번 뽑았다가 다시 삽입정렬한다. */
    if(lock->holder->statuc == THREAD_READY) {
        thread_reorder(lock->holder);
    }

    sema_down(&lock->semaphore);
    ...
}

// thread.c
void thread_reorder(struct thread* t) {
    ASSERT(t->status == THREAD_READY);

    list_remove(&t->elem);
    list_insert_ordered(&ready_list, &t->elem, high_priority, NULL);
}

donate 관련 정보를 관리하는 방법에는 이외에도 여러 가지가 있을 수 있는데, 이를테면 donate을 준 스레드를 리스트로 관리할 수도 있다.

struct thread {
    ...
    struct list donate_list;

    struct list_elem d_elem; // 얘끼리 연결
}

thread 구조체 내부에 있는 struct list_elem 간 연결하는 것이기 때문에, 하나의 스레드가 여러 스레드의 donate_list에 들어가게 되는 상황을 경계해야 한다.

또 다른 방법은 lock마다 자신의 waiters에 있는 스레드 중 max 우선순위를 관리해 주는 것이다. 그리고 스레드가 자신이 소유한 lock의 리스트를 가지고 있으면, lock을 release할 때 마다 lock을 리스트에서 삭제하는 식으로 구현할 수도 있겠다. (아직 생각일 뿐 구현은 안 했다.) 이 경우, lock의 waiters의 max 우선순위를 잘 갱신해 주는 것이 관건이 될 것 같다.

구현의 방법이 매우 다양하다. 그 중에서 메모리를 덜 잡아먹고, (스레드 구조체의 크기는 약 1KB로 제한된다. 스택의 크기도 작아서 배열 많이 넣으면 stack overflow 난다.) 리스트의 검색 시간을 줄일 수 있는 방법으로.. 잘 균형을 잡아야 한다. 그리고 대부분의 경우 커널 스레드는 많이 생성되지 않는다는 것을 고려하면 좋다.

3) multiple, nested donation 상황을 고려하자

multiple donation 상황은 한 스레드가 여러 개의 lock을 들고 있는 상황이다.

thread 0 = low
thread 1 = mid
thread 2 = high

thread 0 이 lock a를 갖는다.
thread 0 이 lock b를 갖는다.

thread 1 이 생성되어 lock a에 접근한다.
thread 2 가 생성되어 lock b에 접근한다.

thread 0 이 lock a를 푼다.
thread 0 이 lock b를 푼다.

이 경우, thread 0의 우선순위는 low → mid → high 로 높아진다. 그리고 lock a를 풀 때, 우선순위가 high로 유지되어야 한다. 왜? lock b의 waiters로 thread 2(high)가 있기 때문이다. 우선순위를 기증하고.. 회수하고 이 난리를 왜 치는지를 생각해 보자. 우선순위가 가장 높은 작업을 빨리 처리하기 위해서이다. 즉, thread 0의 우선순위가 high로 높아진 이유는, thread 2(high)를 waiters에서 빨리 내보내기 위함이므로, lock a를 풀었다고 해서 thread 1(mid)를 먼저 실행하는 게 아니라 lock b를 빨리 풀어줘야 하는 것이다.

따라서 thread 0는 lock a를 풀고, thread 1로부터 기증받았던 우선순위 mid를 반환한다. (donate_list에서 삭제한다.) 그리고 기증받은 우선순위 high를 유지한다. 그러면 thread 2(mid)는 ready_list로 들어가고, current thread는 여전히 thread 0이므로 다음 라인으로 가서 lock b를 푼다. 이 때 thread 2로부터 기증받았던 high를 반환하고, 우선순위가 low로 낮아져 ready_list로 들어간다. 반환이 모두 끝났으므로 thread 2(high)가 먼저 실행되고, thread 1(mid)가 실행, 마지막으로 thread 0(low)가 실행된다.

이에 따라 코드를 짜보면 다음과 같다.

/* lock acquire 할 때 기증을 한다 */
void lock_acquire(struct lock* lock) {

    struct thread* curr = thread_current();
    struct thread* holder = lock->holder;

    if(thread_max_priority(curr) > thread_max_priority(holder)) {
        holder->donate_list[curr->priority]++;
    }

    sema_down(lock->semaphore);
    lock->holder = thread_current();
}

/* sema의 waiters를 우선순위순으로 뺸다 */
void sema_up(struct semaphore *sema) {
    ...

    /* 현재 스레드 다음으로 sema를 잡을 애 */
    struct list_elem* next_elem;
    struct thread* next;

    if(!list_empty(&sema->waiters)) {
        next_elem = min(&sema->waiters, high_priority, NULL); // less func이므로 min
        next = list_entry(next_elem, struct thread, elem);

        list_remove(next);
        thread_unblock(next);
    }
    sema->value++;
    intr_enable();
}

/* donate 회수 */
void lock_release(struct lock* lock) {

    struct list_elem* curr_elem;
    struct thread* curr;

    struct list* waiters = &lock->semaphore->waiters;

    if(!list_empty(waiters)) {
        for(curr_elem = list_begin(waiters);
            curr_elem != list_end(waiters);
            curr_elem = list_next(curr_elem);) {

            curr = list_entry(curr_elem, struct thread, elem);
            lock->holder->donate_list[curr->priority]--;
        }
    }

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

nested donation은 하나의 스레드가 lock a에 접근했을 때, lock a의 holder가 lock b가 풀리기를 대기하고 있는 상황이다. nested가 연속적으로 나타나면 chain으로 볼 수 있다. (꼬리물기..)

thread 0 = 3 priority
thread 1 = 6 priority
thread 2 = 9 priority // 클수록 높음

thread 0 이 lock a를 갖는다.
thread 1 이 생성되어 lock b를 갖는다.
thread 1 이 lock a에 접근한다. waiters로 들어가 대기.
thread 2 가 생성되어 lock b에 접근한다.

이 경우 thread 2는 lock b의 holder인 thread 1이 빨리 lock a를 획득하고, 실행되어 lock b를 풀어줄 수 있도록 자신의 우선순위인 9를 thread 1에게 기증한다. 그리고 thread 1이 접근하고자 하는 lock a의 holder인 thread 0에게도 9를 기증한다. 그래야 thread 0이 lock a를 빨리 release할 수 있기 때문이다.

현재 케이스에서는 thread 0만 있기 떄문에 왜 우선순위 9가 thread 0에게까지 기증되어야 하는지 필요성이 느껴지지 않을 수 있지만, 만약 thread 3이 8의 우선순위를 가지고 돌고 있다고 생각해보자. thread 2는 8보다 높은 우선순위를 가지고 있음에도 불구하고, thread 0이 lock a를 가지고 있으므로 먼저 실행되지 못한다. 따라서, thread 2는 자신의 우선순위를 nested lock을 최종적으로 갖고 있는 thread 0으로 기증하여 빠르게 lock을 해소할 수 있도록 해야 한다.

이를 구현하기 위해 thread 구조체 내의 holder (이 스레드가 우선순위를 기증한 스레드) 필드가 사용된다. 기증을 while문을 돌면서 하고, 반환 역시 이중 for문을 돌면서 한다.

void lock_acquire(struct lock *lock) {

    /* nested priority donation */
    struct thread *holder = lock->holder;
    struct thread *curr = thread_current();

    while (holder) {
      if (thread_max_priority(curr) > thread_max_priority(holder)) {
        holder->donate_list[thread_max_priority(curr)]++;        
        holder = holder->holder;
      } else
        break;
    }

    /* lock holder가 ready list에 있었다면 */
    if (lock->holder && lock->holder->status == THREAD_READY) {
        thread_reorder(lock->holder);
    }

    /* 나의 홀더를 현재 lock->holder로 설정 */
    thread_current()->holder = lock->holder;

    sema_down(&lock->semaphore);
    lock->holder = thread_current();
}

void lock_release(struct lock *lock) {
  if (!list_empty(&lock->semaphore.waiters)) {
    struct list_elem *curr;
    struct thread *donator;

    /* 다음으로 holder가 될 스레드 */
    struct list_elem *next_elem =
        list_min(&lock->semaphore.waiters, high_prio, NULL);
    struct thread *next = thread_entry(next_elem);

    for (curr = list_begin(&lock->semaphore.waiters);
         curr != list_end(&lock->semaphore.waiters); curr = list_next(curr)) {
      donator = thread_entry(curr);

      /* waiter가 기증받았던 우선순위 반환 for nested */
      for (int i = 0; i < 64; i++) {
        if (donator->donate_list[i] > 0) {
          thread_current()->donate_list[i]--;
        }
      }
      /* waiter에게서 기증받은 우선순위 반환 */
      thread_current()->donate_list[donator->priority]--;
      donator->holder = next;
    }
    /* 나의 holder는 NULL */
    thread_current()->holder = NULL;
  }

  lock->holder = NULL;
  sema_up(&lock->semaphore);
  thread_yield(); /* 위에서 unblock된 애가 우선순위가 더 높으면 스케줄 */
}

기증과 반환을 잘 수행하고, 원래 있던 thread 정보 외에 새로 생긴 donate_list, holder 정보를 잘 관리해주면 된다. 이외에도 semaphore, conditional variable에서도 우선순위대로 down, wake 할 수 있도록 thread_yield를 적절히 실행해준다.

동기화에 관한 문제는 여러 스레드의 실행 순서를 머릿속으로 따라가기 힘들다는 점에서 어렵게 느껴지는 것 같다. 각 함수마다 printf를 심어 놓고 전체 코드 흐름이 어떻게 되는지를 먼저 이해해보는 것이 도움이 되었다. 또, donation관련 정보를 어떻게 관리할지 그 자료구조를 짜는 것이 굉장히 다양할 수 있겠다는 생각이 든다. lock을 release할 때 이중 for문을 돌지 않기 위해, 하나의 lock으로 인해 기증받은 최대의 우선순위만을 저장해두어도 좋을 것 같다. donate가 이루어질때마다 최댓값을 갱신하면서. 여러 가지 방법이 있음을 알고, 각 방법의 단점과 장점을 숙고해서 균형 잡힌 구현방법을 택할 수 있도록 하고 싶다. 일단은 현재 코드가 정말로 (test case 뿐만 아니라) 모든 donation 상황에서 의도대로 동작하는 것이 맞는지 반례를 조금 더 생각해봐야겠다.

코드량은 적은데 한 라인 치는데 한시간씩 걸린듯

2023.10.03 수정: 현재 코드의 반례를 발견. test code에서 처리되지 않은 반례가 있음.