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

드디어 Priority Scheduling 의 마지막 파트인 Priority Inversion 까지 왔다. 이전에 다루었던 문제들보다 꽤 많이 복잡해서 생각보다 시간이 오래 걸렸다ㅜㅜ 시작해보자!

 

Priority Inversion

핀토스 Documents 에 나와있는 설명을 해석해보자. 우선 priority inversion 이란 다음과 같은 상황에서 발생한다. H (high), M (medium), L (low) 라는 세 개의 스레드가 있고 각각의 우선순위는 H > M > L 일 때, H 가 L 을 기다려야 하는 상황(예를 들어, H 가 lock 을 요청했는데 이 lock 을 L 이 점유하고 있는 경우)이 생긴다면 H 가 L 에게 CPU 점유를 넘겨주면 M 이 L 보다 우선순위가 높으므로 점유권을 선점하여 실행되어서 스레드가 마무리 되는 순서가 M->L->H 가 되어서 M 이 더 높은 우선순위를 가진 H 보다 우선하여 실행되는 문제가 발생한다. 이를 잘 나타낸 그림이 있어서 가져와 보았다.

출처 : https://oslab.kaist.ac.kr

이러한 문제를 해결하기 위한 방법으로 priority donation 을 구현하여야 한다. priority donation 이란 위의 상황에서 H 가 자신이 가진 priority 를 L 에게 일시적으로 양도하여서 H 자신의 실행을 위해 L 이 자신과 동일한 우선순위를 가져서 우선적으로 실행될 수 있도록 만드는 방법이다. priority donation 이 작동하면 실행 순서는 아래와 같이 바뀐다.

 

핀토스 documents 에서는 priority donation 이 일어난 수 있는 모든 상황을 고려해야 한다고 하면서 Multiple donation, Nested donation 두 가지를 언급한다.

 

Multiple donation

단어에서 알 수 있듯이 여러번의 donation 이 일어난 상황이라고 볼 수 있다. 위의 예시에서 L 가 lock A, lock B 라는 두 가지 lock 을 점유하고 있다고 해보자. H 가 lock A 를, M 이 lock B 를 각각 요청하였을 때, L 은 자신이 가지고 있는 lock 을 요청한 모든 스레드에게 priority 를 양도받고, 이 중 가장 높은 priority 를 일시적으로 자신의 priority 로 갖는다. 그림으로 보면 아래와 같다.

이 경우에 L 이 lock B 를 release 해도 아직 M 에게 양도받은 priority 가 있기 때문에 31 이 아닌 32의 priority 를 가지게 된다.

반응형

​

Nested donation

그림에서 볼 수 있듯이 H 가 lock B 를 얻기 위해 M 에게 priority donation 을 행하고 M 은 lock A 를 얻기 위해 L 에게 priority donation 을 행하는 것 처럼, 여러번의 단계적 donation 이 일어나는 상황이다.

시간에 따라 스레드의 진행 순서는 위와 같다.

 

그럼 이제 구현을 시작해보자.

 

struct thread

우선 각 스레드가 양도받은 내역을 관리할 수 있게 thread 의 구조체를 변경해줄 필요가 있다.

struct thread
  {
    ...
    int init_priority;
    
    struct lock *wait_on_lock;
    struct list donations;
    struct list_elem donation_elem;
	...
  };

4개 정도의 항목을 추가해주었다. init_priority 는 스레드가 priority 를 양도받았다가 다시 반납할 때 원래의 priority 를 복원할 수 있도록 고유의 priority 값을 저장하는 변수이다. wait_on_lock 은 스레드가 현재 얻기 위해 기다리고 있는 lock 으로 스레드는 이 lock 이 release 되기를 기다린다. donations 는 자신에게 priority 를 나누어준 스레드들의 리스트이고 donation_elem 은 이 리스트를 관리하기 위한 element 로 thread 구조체의 그냥 elem 과 구분하여 사용하도록 한다.

multiple donation 에서 사용했던 그림으로 예시를 들면, L->donations = [M, H],   M->wait_on_lock = A,   H->wait_on_lock = B 이고, L->init_priority = 31 이다.

새로운 요소를 추가하였으면 언제나 초기화는 기본이다. init_thread 에서 초기화 코드를 추가해준다.

/* thread/thread.c */
static void
init_thread (struct thread *t, const char *name, int priority)
{
  ...
  t->init_priority = priority;
  t->wait_on_lock = NULL;
  list_init (&t->donations);
  ...
}

 

 

lock_acquire (struct lock *lock)

lock_acquire() 함수는 스레드가 lock 을 요청할 때 실행된다. lock 을 현재 점유하고 있는 스레드가 없으면 상관 없지만, 누군가 점유하고 있다면 자신의 priority 를 양도하여 lock 을 점유하고 있는 스레드가 우선적으로 lock 을 반환하도록 해야한다. 우선 현재 lock_acquire() 가 어떻게 구현되어 있는지 보자.

/* thread/synch.c */
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 = thread_current ();
}

lock 에대한 요청이 들어오면 sema_down 에서 멈췄다가 lock 이 사용가능하게 되면 자신이 lock 을 선점하는 것을 볼 수 있다. sema_down 을 기점으로 이전은 lock 을 얻기 전, 이후는 lock 을 얻은 후이다. sema_down 에 들어가기 전에 lock 을 가지고 있는 스레드에게 priority 를 양도하는 작업이 필요하다.

/* 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;
  lock->holder = cur;
}

lock->holder 는 현재 lock 을 소유하고 있는 스레드를 가르킨다. 현재 lock 을 소유하고 있는 스레드가 없다면 바로 해당 lock 을 차지하고 lock 을 누군가 소유하고 있다면 그 스레드에게 priority 를 넘겨주어야 한다. 여기서 한 가지 알아야 할 점은, 현재 lock_acquire() 를 요청하는 스레드가 실행되고 있다는 자체로 lock 을 가지고 있는 스레드보다 우선순위가 높다는 뜻이기 때문에 if (cur->priority > lock->holder->priority) 등의 비교 조건은 필요하지 않다.

lock 을 점유하고 있는 스레드(holder) 가 있다면 현재 스레드의 wait_on_lock 에 lock 을 추가하고 holder 의 donations 리스트에 현재 스레드를 추가하고 priority donation 을 실행한다. thread_compare_donate_priority 함수는 thread_compare_priority 의 역할을 donation_elem 에 대하여 하는 함수이다. 

/* thread/thread.c */
bool
thread_compare_donate_priority (const struct list_elem *l, 
				const struct list_elem *s, void *aux UNUSED)
{
	return list_entry (l, struct thread, donation_elem)->priority
		 > list_entry (s, struct thread, donation_elem)->priority;
}

donate_priority () 함수는 뒤에서 살펴보기로 하고, sema_down 이후에는 현재 스레드가 lock 을 차지한 상태이므로 wait_on_lock 을 NULL 로 만들어주고 lock->holder 를 현재 스레드로 만들어준다.

 

donate_priority ()

이 함수는 자신의 priority 를 필요한 lock 을 점유하고 있는 스레드에게 빌려주는 함수이다. 한 가지 주의할 점은, nested donation 에서 살펴본 것처럼 하위에 연결된 모든 스레드에 donation 이 일어난다는 것이다. 

위에서 살펴본 위와 같은 상황에서 H 는 M 에게 전달하고 M 은 이 priority 를 다시 L 에게 전달하여서 L 이 우선적으로 실행될 수 있도록 한다.

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

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

구현은 간단하게 가능하다. depth 는 nested 의 최대 깊이를 지정해주기 위해 사용했다(max_depth = 8). 스레드의 wait_on_lock 이 NULL 이 아니라면 스레드가 lock 에 걸려있다는 소리이므로 그 lock 을 점유하고 있는 holder 스레드에게 priority 를 넘겨주는 방식을 깊이 8의 스레드까지 반복한다. wait_on_lock == NULL 이라면 더 이상 donation 을 진해할 필요가 없으므로 break 해준다. 여기까지 구현이 됐다면 priority 의 양도는 성공적으로 수행된다.

 

lock_release (struct lock *lock)

다음은 스레드가 priority 를 양도받아 critical section 을 마치고 lock 을 반환할 때의 경우를 만들어주어야 한다. 우선 현재 lock_release() 함수가 어떻게 생겼는지 확인해보자.

/* thread/synch.c */
void
lock_release (struct lock *lock) 
{
  ASSERT (lock != NULL);
  ASSERT (lock_held_by_current_thread (lock));

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

현재는 그냥 lock 이 가진 holder 를 비워주고 sema_up 하여주는 게 전부이다. sema_up 하여 lock 의 점유를 반환하기 전에 현재 이 lock 을 사용하기 위해 나에게 priority 를 빌려준 스레드들을 donations 리스트에서 제거하고, priority 를 재설정 해주는 작업이 필요하다. 

다시 한 번 위 그림을 예로 들어보면, thread L 에서 lock_release(lock B) 를 실행하면 lock B 를 사용하기 위해서 priority 를 나누어 주었던 Thread H 는 이제 priority 를 빌려줘야 할 이유가 없으므로 donations 리스트에서 Thread H 를 지워주어야 한다. 그 후 Thread H 가 빌려주던 33 이라는 priority 를 지우고 Thread L 의 priority 를 다시 정해주어야 하는데, 이 때 남아있는 donations 리스트에서 가장 높은 priority 를 가지고 있는 스레드의 priority 를 받아서 Thread L 의 priority 로 설정해준다. 만약 더 이상 donations 리스트에 남아있는 스레드가 없다면 원래 값인 init_priority 로 priority 를 설정해주면 된다. 우선 donations 리스트에서 스레드들을 지우는 함수를 만들어보자.

/* thread/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 리스트를 처음부터 끝까지 돌면서 리스트에 있는 스레드가 priority 를 빌려준 이유, 즉 wait_on_lock 이 이번에 release 하는 lock 이라면 해당하는 스레드를 리스트에서 지워준다. 이 때 <list/kernel/list.c> 에 구현되어 있는 list_remove 함수를 사용하였다. 모든 donations 리스트와 관련된 작업에서는 elem 이 아니라 donation_elem 을 사용하여야 함을 명심하자. 다음은 priority 를 재설정하는 함수를 보자.

/* thread/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 리스트에 스레드가 남아있다면 남아있는 스레드 중에서 가장 높은 priority 를 가져와야 한다. priority 가 가장 높은 스레드를 고르기 위해 list_sort 를 사용하여 donations 리스트의 원소들을 priority 순으로 내림차순 정렬한다. 그 후 맨 앞의 스레드(priority 가 가장 큰 스레드)를 뽑아서 init_priority 와 비교하여 둘 중 더 큰 priority 를 적용한다. 이제 새로 만든 함수들로 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);
}

단순히 두 함수를 추가하기만 하면 된다.

 

한 가지 생각하여야 하는 상황이 더 있다. 만약 현재 진행중인 running thread 의 priority 변경이 일어났을 때 (이 경우 init_priority 의 변경을 의미한다.) donations 리스트들에 있는 스레드들보다 priority 가 높아지는 경우가 생길 수 있다. 이 경우 priority 는 donations 리스트 중 가장 높은 priority 가 아니라 새로 바뀐 priority 가 적용될 수 있게 해야 한다. 이는 thread_set_priority 에 refresh_priority() 함수를 추가하는 것으로 간단하게 가능하다.

/* thread/thread.c */
void
thread_set_priority (int new_priority) 
{
  thread_current ()->init_priority = new_priority;
  
  refresh_priority ();
  thread_test_preemption ();
}

 

 

 

결과

저번에 fail 을 받았던 priority 관련 테스트들을 순식간에 모두 통과하였다! 생각보다 많이 복잡하고 시간도 오래 걸렸지만 그만큼 뿌듯한 마음도 크다. 다음 시간에는 Advanced Scheduler 를 구현해본다. 나머지 7개의 테스트에 관한 내용으로 background 포스트에서 nice, load_avg 값의 계산을 보았다면 알겠지만 상당히 어려워보인다. 화이팅!