[pintos] Project1:Threads - Priority Scheduling (2)

priority preemptive scheduling에 이어서 priority inversion을 해결하기 위해 priority donation을 구현해야한다.

priority inversion

pintos manual과 교재의 설명을 참고해 정리하면 H, M, L로 priority가 낮아지는 세 프로세스가 있고 priority scheduling을 따라 프로세스가 실행되면 H, M, L, 순서로 실행이 끝나야 한다. 하지만 아닌 경우가 발생하는데 이때 priority inversion이 발생했다고 한다.
만약 H가 L에 점유되어 있는 lock을 기다려야 하는 상황이 생겼다고 가정하자. H는 L이 lock을 풀어줄 때까지 CPU를 점유하지 못하고 waiting 상태에 놓인다. L이 lock을 풀어주는 코드를 실행하려면 L이 CPU를 점유해야하는데 M에 비해 priority가 낮기 때문에 L이 CPU를 점유하지 못하고 M이 실행되게 된다. 이렇게 H가 실행되지 못하고 M이 H보다 먼저 실행이 종료될 수 있는데 이렇게 우선순위가 더 높은 H보다 M이 먼저 우선권을 가지고 실행되는 문제를 priority inversion이라고 한다.

priority donation

priority inversion을 해결하기 위해 도입된 방법이 priority donation이다. 말 그대로 자신의 priority를 일시적으로 양도하는 것인데 H가 L에 의해 점유된 lock에 들어갈 때 자신의 높은 priority를 L에 일시적으로 넘겨주어 L이 M보다 우선적으로 실행될 수 있도록 해 자신이 lock을 점유할 수 있도록 하는 것이다.
H가 자신의 priority를 L에게 넘겨주면 L은 일시적으로 H와 같은 우선순위를 가지기 때문에 M보다 우선권을 가지고 CPU를 점유하게 되고 L이 lock을 반환하게 되면 H가 lock을 점유하게 되면서 우선순위대로 실행될 수 있게 된다.

pintos manual에서는 multiple donation과 nested donation을 모두 고려해 프로그램을 설계해야한다고 언급하고 있다.

multiple donation

말 그대로 한 thread가 여러 thread에 priority donation을 받은 경우이다. L에 의해 점유된 lock이 있고 M이 lock을 얻기 위해 lock을 요청했을 때 L은 M의 priority를 양도 받아 M과 priority가 같은 상태가 된다. 이때 H 또한 L에 의해 점유된 lock을 요청하게 되면 L은 H의 priority도 양도 받게 되는데 H가 M보다 우선순위가 높기 때문에 L은 H와 같은 priority를 가진 상태로 실행된다.
L이 lock을 반환하게 되면 L은 H의 priority를 반납하게 되는데 이때 L의 priority는 원래 자신의 것으로 돌아가는 게 아니라 M의 priority를 가지고 있을 수 있도록 프로그램을 설계해야한다.

nested donation

multiple donation이 수평적인 donation 관계라면 nested donation은 수직적인 관계이다. 위와 같이 M이 L에 의해 점유된 lock을 요청해 L이 M의 priority를 양도 받은 상태에 있다고 하자. 이때 H가 M에 의해 점유된 다른 lock을 요청하게 되면 M은 H의 priority를 양도 받게 된다. 하지만 M은 L이 점유하고 있는 lock을 요청한 상태이기 때문에 당장 실행될 수 없다. 따라서 M은 H에게 양도 받은 priority를 다시 L에게 양도함으로써 L이 H의 우선순위를 가지고 실행될 수 있도록 설계해야한다. 이때 L이 lock을 반환하게 되면 L은 M에게만 priority를 양도받은 상태였기 때문에 반환 후 원래 자기 자신의 priority로 돌아가게 된다.

예시

코드 설계를 위해 좀 더 복잡한 예시를 만들어 보았다.

위처럼 2개의 서로 다른 priority를 가지는 thread와 3개의 lock A, B가 있다고 하자. 현재 lock B, C는 P1에 점유되어 있다.

이때 priority 31을 가지는 P3가 들어오게 되면 priority에 따라 P3가 실행된다. P3가 lock A를 점유하고 lock B를 요청하게 되면 P3는 B의 waiter로 들어가게 되고 이때 자신의 priority 31을 P1에게 양도한다. 따라서 P1, P2 중 P1이 다음 running thread가 된다.

priority 47을 가지는 프로세스 P4가 들어오면 priority가 가장 높기 때문에 CPU를 점유해 running thread가 된다. 이때 P4가 lock A를 요청하면 A는 P3에 점유되어 있기 때문에 P4는 A의 waiter로 들어가게 되고 자신의 priority 47을 P3에게 양도한다. 이때 P3는 B에 lock이 걸려 있기 때문에 P3는 양도받은 priority 47을 다시 P1에게 양도한다.

ready list에서 P1이 priority가 가장 높아졌기 때문에 다시 P1이 running thread가 된다. 이때 priority 65를 가진 P5가 들어오게 되면 priority preemptvie scheduling에 의해 P5가 running thread가 된다.
P5가 lock C를 요청하면 C는 P1에 점유되어 있기 때문에 P5는 C의 waiter로 들어가게 되고 이때 P1이 현재 양도 받은 priority 47보다 P5의 priority가 더 크기 때문에 P1은 P5의 priority를 양도 받아 63의 priority를 갖는다.

priority에 따라 P1이 우선순위를 갖게 되고 이때 lock B를 release 하게 되면 B의 waiter P3가 B를 점유하게 되고 P1의 현재 priority는 P5에 받은 priority이기 때문에 반납하지 않고 priority 63을 유지하게 된다. P1이 계속 실행되고 lock C를 release 하게 되면 P5가 lock C를 점유하게 되고 P1은 P5에게 양도받은 priority를 반납한다. 이때 더이상 남아있는 donor thread가 없기 때문에 다시 원래의 priority로 돌아가게 된다.

이제 가장 높은 priority를 가진 thread는 P5기 때문에 P5가 실행되고 P5가 종료되면 다음으로 priority가 높은 P3가 실행되게 된다. P3가 lock A를 release하면 P4가 lock A를 점유하게 되고 P3는 priority를 반납하고 원래 자신의 priority인 31로 돌아간다.

priority 순서대로 P4, P3, P2, P1이 차례로 실행이 종료되면 priority inversion없이 thread들이 잘 실행된다.

코드 구현

위의 예시를 바탕으로 priority donation에 필요한 데이터를 생각해보면

1. 자신의 원래 priority를 알고 있어야 함
2. donation 해준 thread와 해당 thread가 waiting하고 있는 lock을 알아야 함

이렇게 두 가지 내용을 기억하고 있어야 함을 알 수 있다.

기존 코드

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

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

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

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

기존의 lock_acquire() 코드를 살펴보면 sema down이 일어나면서 lock->semaphore의 waiter에 thread가 들어가게 되고 다른 thread에 의해 lock_release()가 실행되면 sema up이 일어나면서 sema_down(&lock->semaphore) 다음 라인부터 코드가 실행되면서 thread가 해당 lock의 holder가 되는 것을 알 수 있다.

따라서 priority donation의 경우 sema_down(&lock->semaphore)이 일어나기 전에 실행되어야 하며 lock_release() 함수에서 priority 반환과 이에 따른 priority 변화를 확인하면 된다.

struct thread 수정

먼저 아래와 같이 thread 구조체에 변수를 추가한다.

struct thread
  {
    // ...

    struct list_elem elem;              /* List element. */

    /* Project1 */
    int64_t wakeup;                     /* wake up time when thread go to sleep */

    struct lock *wait_on_lock;
    struct list donor_list;             /* donor thread list */
    int origin_prior;                   /* save origin priority when priority donation occur */
    struct list_elem delem;             /* donor list element */

    // ...
  };

thread는 자신의 본래 priority와 donation을 해준 thread를 기억하고 있어야 하기 때문에 thread 구조체에 int origin_prior와 struct list donor_list를 추가해 각각을 기억할 수 있도록 했다.

또한 list donor_list가 추가되면서 이 list에 대한 list element가 따로 필요하기 때문에 struct list_elem delem을 멤버 변수로 추가하였다.

lock_release()에서 lock->holder가 인자로 넘어온 struct lock *lock에 해당하는 lock을 요청한 thread 중 가장 priority가 높은 thread를 donor_list에서 제거해야 하기 때문에 donor thread가 어떤 lock을 요청하면서 donation을 했는지 기억하고 있어야 한다. 따라서 struct lock *wait_on_lock을 추가해 thread가 lock을 요청할 때 해당 lock을 저장할 수 있도록 했다.

lock_acquire() 수정

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

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

  if(holder && holder->priority < cur->priority)
  {
    cur->wait_on_lock = lock;
    list_insert_ordered(&(holder->donor_list), &(cur->delem), thread_donate_priority_compare, NULL);
    priority_donate();
  }

  sema_down (&lock->semaphore);

  cur->wait_on_lock = NULL;
  lock->holder = cur;
}

thread가 lock을 요청할 때 해당 lock을 점유하고 있는 thread가 존재하고 donation이 필요한 상태이면 thread의 wait_on_lock에 해당 lock을 추가하고 lock->holder의 donor_list에 해당 thread를 추가하였다.

lock에서 풀려 다시 나머지 코드가 실행되면 thread의 wait_on_lock을 NULL로 초기화해주는 코드도 추가하였다.

후에 list에서 thread를 제거할 때 priority가 높은 thread가 먼저 나와야 하기 때문에 list를 thread_donate_priority_compare() 함수를 구현해 priority 순서로 정렬 삽입해주었다.

bool thread_donate_priority_compare (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
  struct thread *A = list_entry(a, struct thread, delem);
  struct thread *B = list_entry(b, struct thread, delem);

  return (A->priority > B->priority);
}

void priority_donate()
{
  struct thread *cur = thread_current();
  struct lock *lock = cur->wait_on_lock;
  int depth;

  for(depth=0; depth<8; depth++){
    if (!lock) break;
    if(lock->holder && lock->holder->priority < cur->priority){
      lock->holder->priority = cur->priority;
      lock = lock->holder->wait_on_lock;
    }
    else break;
  }
}

priority donation은 void priority_donate()함수를 선언해 구현하였다. pintos manual에서 nested donation을 depth를 제한해 depth 8까지 확인하라고 하였기에 8까지 holder의 wait_on_lock이 존재하는지 확인하고 donation이 필요한 경우 donation을 진행하였다.

lock_release() 수정

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

  priroity_donation_check(lock);

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

sema_up(&lock->semaphore)를 통해 lock을 점유하게 될 thread를 찾아 donor_list에서 제거하고 donation 받은 priority를 반납하고 priroity를 재설정하는 과정을 priority_donation_check(lock)을 통해 구현하였다.

void priroity_donation_check(const struct lock *lock)
{
  struct list_elem *delem;
  struct thread *t;

  if(!list_empty(&(lock->holder->donor_list))){
    for(delem = list_begin(&(lock->holder->donor_list)); delem != list_end(&(lock->holder->donor_list)); delem = list_next(delem)){
      t = list_entry(delem, struct thread, delem);
      if(t->wait_on_lock == lock){
        list_remove(delem);
      }
    }
  }

  lock->holder->priority = lock->holder->origin_prior;
  if(!list_empty(&(lock->holder->donor_list))){
    list_sort(&(lock->holder->donor_list), thread_donate_priority_compare, NULL);
    t = list_entry(list_begin(&(lock->holder->donor_list)), struct thread, delem);
    if(t->priority > lock->holder->origin_prior){
      lock->holder->priority = t->priority;
    }
  }

}

donor_list를 돌면서 인자로 넘어온 lock과 일치하는 wait_on_lock을 가지는 첫 번째 thread를 list에서 제거하였다. 후에 list를 다시 priority 순서로 정렬해 가장 첫 번째 thread의 priority를 확인해 holder thread의 priority를 업데이트 해주었다.

thread_set_priority() 수정

void
thread_set_priority (int new_priority) 
{
  struct thread *cur = thread_current ();
  int old_priority = cur->priority;
  cur->priority = cur->origin_prior = new_priority;
  if(!list_empty(&(cur-> donor_list))){
    if(old_priority > new_priority)
      cur->priority = old_priority;
  }
  priority_preemptive_check();
}

thread 구조체에 본래의 priority를 저장하는 변수인 origin_prior가 추가됨에 따라 해당 함수도 수정에 들어갔다. thread가 set priority를 요청하면 바뀌어야 하는건 donation 받은 priority가 아니라 본래 자신의 priority이기 때문에 origin_prior를 인자로 들어온 new_priority로 바꿔주었다.

이때 origin_prior뿐만 아니라 priority도 new_priority로 바뀌어야 하는 경우가 있다. 만약 새로 설정하고자 하는 new_priority가 donation 받은 priority보다 크다면 thread는 new_priority를 priority에 할당받아야 한다.

결과