PintOS Project 1.2(3) - Priority Inversion (정글사관학교 59일차 TIL)

1. 과제 개요: Priority Inversion Problem 해결

이번 과제에서는 Priority Inversion Problem을 해결하는 것이 목표이며, 이를 위해 3가지 도네이션 기능을 구현해야 한다. 이를 위해 먼저 priority inversion problem이 무엇인지부터 이해하고 넘어가보자.

 

 

Priority Inversion Problem: 우선순위가 높은 스레드가 우선순위가 낮은 스레드를 기다리는 현상

 

아래 이미지만 보면 뭔 소린가 싶을 거다. 차근차근 설명에 들어간다. 아래 이미지에서 priority가 높은 순은 주황(High, H) > 파랑(Medium, M) > 연두(Low, L)이다. 여기서 연두와 주황은 Lock A를, 파랑은 Lock B에 접근하려고 한다고 하자. 즉, 여기서 셋 다 모두 똑같은 공유자원에 접근하는 게 아니라 연두와 주황이 동일한 자원 A에, 파랑은 다른 자원 B에 접근한다는 말이다.

 

(여기서 꼭 파랑이 다른 자원 B에 접근하는 케이스만 있는 건 아니다. 이해를 돕기 위해 파랑이 다른 lock B에 접근한다고 했으나 파랑이가 Lock A에 접근하지만 않으면 모든 상황이 아래와 같이 진행된다. ex) 파랑이가 아무런 공유 자원에도 접근하지 않는 스레드인 경우에도 아래 케이스가 성립)

 

Prioirity: 주황(High) > 파랑(Medium) > 연두(Low)

Lock A: 연두 & 주황

Lock B: 파랑

 

이 상황에서 다시 이미지를 보자. 맨 처음에 연두색 스레드만 들어오는 상황부터 시작한다. (설명이 길 수 있으니 Priority Inversion Problem을 이해하고 있다면 바로 2로 넘어가자!)

 

1) Lock A에 접근한 연두색 스레드(Low)는 자기가 맨 처음 도착했으니 Lock A를 열고 공유 데이터 A에 접근한다.

2) Lock B에 접근한 주황색 스레드(High)가 ready list에서 줄을 선다.

우리는 이미 앞 과제에서 priority 기반으로 CPU를 선점하는 기능을 추가했기에 주황색이 CPU 우선순위가 높아 CPU를 연두색으로부터 빼앗아 오고 연두색 스레드는 ready list로 밀려난다. 하지만 CPU 점유와 별개로 공유 자원에 대한 접근 권한은 연두색 스레드가 갖고 있다. 따라서 주황색 스레드는 자원을 기다리기 위해 waiters 리스트로 들어간다.

 

 

여기서 중간 정도의 우선순위를 갖는 파란색 스레드가 들어온다. 파란색 스레드는 연두색 스레드보다 우선순위가 높으니 CPU를 잡는다.

 

여기서부터 주황색의 비극이 시작된다. 주황색은 자기도 연두가 공유 데이터 점하고 있어서 밀려났지만 가장 첫번째로 줄 섰으니 M이 자기 뒤에 와야 할 것이라고 생각하고 맘을 놓는다. 하지만 파랑은 공유 데이터 A에 접근할 생각 자체가 없었다.

파랑이는 공유데이터 B를 잡기 위해 lock B를 열고 공유 데이터 안에 들어가서 작업을 시도한다. 작업을 시도하는데 아무런 문제가 없으니 파랑 스레드는 작업을 수행한다. 주황이는 이때부터 당황하기 시작한다. 자신(High)이 파랑(Medium)보다 우선순위가 더 높은데 작업은 파랑이가 먼저 하는 상황이 벌어진다. 이런 상황을 Priority Inversion이라고 한다.

더 큰 비극은 아래와 같은 상황이 닥쳤을 때다. 공유 데이터 B를 잡기 위해 파랑이의 친구들이 차례대로 ready list에 줄서기 시작했다.

 

얘네들의 우선순위는 연두보다 높은 중간 단계이니 우선순위 기반으로 줄을 재조정해 자연스럽게 새치기를 한다.(ㄱㅅㄲ들..)그리고 얘네들은 공유 데이터 B를 점하기 위해 줄섰으니 맨 첫번째 파랑이가 작업을 끝내면 계속해서 공유 데이터 B를 기다리고 있는 중간 단계 우선순위 애들이 작업을 진행할 것이다. 따라서 주황이는 작업이 계속 밀리게 되고 어쩌면 영영 작업을 하지 못하는 상태(starvation)이 발생할 수도 있게 된다.

 

 

 

2. 과제 솔루션: Priority Donation

 

이러한 문제를 해결하기 위해서는, 주황이가 Lock을 요청할 때 연두한테 자기의 우선순위를 빌려주는 것이다. 그러면 연두는 우선순위가 높아져서 파랑이한테 우선순위를 빼앗기지 않고 작업을 완료할 수 있으며, 작업이 끝나면 자연스럽게 주황이가 뒤를 이어 CPU를 잡고 작업을 진행할 것이다. 그 작업이 끝나고서야 중간 단계의 우선순위인 파랑이가 CPU를 잡는다. 이러면 모두가 해피엔딩!

 

이 문제에 대해 조금 더 깊이 파보자. 핀토스 document에서는 priority donation이 일어날 수 있는 모든 상황을 고려해야 한다고 하며 Multiple donation, Nested donation 두 가지를 언급한다.

 

Multiple donation

단어에서 뜻하는 것과 같이 multiple donation은 도네이션이 여러 번 발생한 상황을 뜻한다. 위의 예시는 각 스레드가 필요로 하는 자원이 각각 하나(A 또는 B 중 하나)였다. 이번에는 하나의 스레드가 두 개의 공유 데이터에 접근하기 위해 Lock A, Lock B라는 두 가지 Lock을 점유해야 하는 상황을 생각해보자. 주황(H)이 lock A를, 파랑(M)이 lock B를 각각 요청할 때, 연두(L)은 자신이 갖고 있는 lock을 요청한 모든 스레드에게 priority를 기부받고 이 중 가장 높은 우선순위를 일시적으로 자신의 priority로 갖는다. 아래 예시를 보자.

 

괄호 안의 숫자는 우선순위이며, 화살표는 갖고자 하는 lock을 뜻한다. 가장 낮은 우선순위를 갖는 L 스레드(31)는 Lock A, B를 모두 필요로 하는 스레드이다. 이 친구는 가장 먼저 왔기 때문에 두 자원을 갖고서 작업을 진행 중이다.

 

이때, 더 높은 우선순위(32)를 갖는 M이 와서 Lock A를 요청한다. 중간에 CPU를 점했다가 다시 내어주고 waiters list로 가는 과정은 아래 그림에서 생략했다. waiters list로 갈텐데, 그 전에 우선순위를 기부한다.

 

이어서 아래와 같이 더 높은 우선순위 갖는 H가 도착해 Lock B를 요청한다. 여기서 또 우선순위를 기부해 L의 우선순위는 더 높아진다. 이러한 과정을 multiple donation이라 한다.

 

위 과정을 한 장으로 요약하면 아래와 같다. M(32)이 lock A, H(33)이 lock B를 요청해 L(31)의 우선순위가 순차적으로 높아진다. 여기서 만약 lock B를 release한다고 해보자. 그래도 여전히 lock A를 요청한 M의 priority를 기부받았기 때문에 L의 우선순위는 31이 아닌 32가 된다. (단, 33은 아님! 따라서 H가 준 우선순위를 제거한다.)

Nested donation

이번에는 위와 비슷하면서도 약간 다른 개념이다. 위에서는 L 스레드에게 M, L이 각각 자신의 priority를 기부했다. (M->L, H->L). 이와 달리, Nested donation은 마치 체인처럼 H, M, L이 서로 연결되어 우선순위를 기부하는 상황이다. (H-> M -> L) 

 

어떻게 이런 상황이 발생할까? 아래 이미지 예시를 보자. L 스레드가 Lock A를 점유하고서 작업 중인 상황에서 M 스레드가 들어온다. M 스레드의 우선순위가 더 높고 다른 Lock을 점유하고 있으니 CPU 제어권은 M이 잡는다.

 

이어서 M이 Lock A를 요청한다. 그러면 donation이 일어나 L의 우선순위가 M과 동등해진다. 여기서 lock A는 L이 잡고 있었으니 CPU 제어권은 L에게 넘어오고 L 이 작업을 시도할 것이다.

 

그 사이에 H가 들어온다. H는 처음에 아무런 Lock도 요청하지 않았기에 바로 CPU를 잡고 작업을 한다. 그러다 중간에 Lock B를 요청하는데, Lock B는 M 스레드가 잡고 있었다. 하지만 M 스레드는 Lock A를 요청하고 기다리던 상황이었기 때문에 M 스레드가 H한테 Lock B를 넘겨주기 위해서는 가장 먼저 L 스레드가 Lock A를 반환해야 이 순환고리가 끝이 난다. 따라서 M과 L 둘다 H의 우선순위를 물려받는다. 

 

그러면 L 스레드가 작업을 끝내고 A를 반환하고, 이어서 M이 lock B를 반환한다. 마지막으로 H가 작업을 끝내며 모든 것이 종료된다.

 

 

3. 과제 구현

 

수정 및 추가 함수, 자료구조 수정

우리가 바꿔야 할 함수/자료구조들부터 살펴보자.

 

자료구조 수정: struct thread

Priority를 donation 받기 위해서는 받은 값을 관리해줄 자료구조가 필요하다. 총 4개의 항목을 추가해준다.

// @/include/threads/thread.h

struct thread {
	
	...
    
	int priority;                       /* Priority. */
	/*---Project 1.4 Priority donation ---*/
    
	int init_priority; // thread의 priority는 donation에 의해 매번 바뀔 수 있음. 그러니 맨 처음에 할당받은 priority를 기억해둬야!
	struct lock *wait_on_lock; // 해당 스레드가 대기하고 있는 lock 자료구조 주소 저장: thread가 원하는 lock을 이미 다른 thread가 점유하고 있으면 lock의 주소를 저장한다.
	struct list donations; // multiple donation 고려하기 위해 사용: A thread가 B thread에 의해 priority가 변경됐다면 A thread의 list donations에 B 스레드를 기억해놓는다.
	struct list_elem donation_elem; // multiple donation 고려하기 위해 사용: B thread는 A thread의 기부자 목록에 자신 이름 새겨놓아야! 이를 donation_elem!
 	... 
 }

1) init_priority: 위 예시에서 본 것처럼, thread의 priority는 기부받을 때마다 값이 바뀐다. 그럼 바뀐대로 두면 되는 거 아닌가? 싶은데 multiple donation 문제와 같이, 여러 자원을 들고 있다가 중간에 자원 하나를 반납하면 해당 자원을 기다리고 있던 더 우선순위 높은 스레드가 해당 작업을 가져가고 우선순위를 기부받았던 스레드는 자신이 받은 우선순위를 반납해야 한다. 만약 자신이 기부받은 우선순위를 다 반납하고 나면 어떻게 해야 될까? 당연히 자신이 원래 갖고 있던 우선순위를 기억해두고 있어야 한다. 그래서 init_priority가 필요하다.

2)wait_on_lock: 스레드가 현재 얻기 위해 기다리고 있는 lock을 뜻한다. lock이 release되면 여기에 기록해둔 lock 자료구조를 확인하고 해당 주소로 이동한다.

3) donations: 자신에게 priority를 나눠준 스레드의 리스트이다. 여기서 해당 스레드만 찾으면 위에 보는 것처럼 멤버로 int priority를 들고 있으니 우리가 알고자 하는 priority 값을 찾아낼 수 있다.

4) donation_elem: 위의 list donation에 넣어줄 리스트 성분이다.

 

이전 예시와 매칭해보면, L->init_priority = 31, L->donations = [M, H], M->wait_on_lock = A, H->wait_on_lock = B 이며,

L->donations = [M, H]에 들어있는 M, H는 thread가 아닌 list_elem 구조체인 donation_elem이다.

 

스레드 초기화 함수 수정: init_thread()

위에서 스레드 구조체 멤버를 수정했으니, 초기화 함수 역시 수정해준다.

@/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;

	/* --- Project 1.4 priority donation --- */
	/* --- 자료구조 초기화 --- */
	t->init_priority = priority;
	t->wait_on_lock = NULL;
	list_init(&t->donations);

}

 

 

 

 

수정 & 추가함수

 

void lock_acquire (struct lock *lock) (수정 전)

lock_acquire() 함수는 스레드가 CPU 제어권을 잡고나서 lock을 요청할 때 실행된다.  sema_down()을 실행해 lock을 얻기 위해 세마포어를 waiters 리스트에 줄세운 다음 해당 스레드를 blocked 상태로 전환한다. 그러다 앞서 lock을 점유하던 애가 반환하면 sema_down()에서 sema->value 값을 1 빼고(여기까지 sema_down) 다시 lock_acquire()로 와서 lock을 받는다 (lock->holder).

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

여기서 donation 기능을 추가하자. lock을 현재 점유하는 스레드가 없다면 상관없으나, 앞서 다른 스레드가 lock을 점유하고 있으면 자신의 priority를 양도해 lock을 점유하는 스레드가 우선적으로 lock을 반환하도록 해야 한다. 따라서 sema_down()을 실행하기 전에 lock 가지고 있는 스레드에게 priority를 기부하는 작업을 선행해준다.

void lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (!lock_held_by_current_thread (lock));
	/* --- pjt 1.2 priority donation --- */
    if (lock->holder) {
    	struct thread *cur = thread_current (); // 현재 lock_acquire를 실행하는 스레드가 thread_current
        cur->wait_on_lock = lock; // 현재 스레드가 어떤 lock 기다리고 있는지 입력
        list_insert_ordered(&lock->holder->donations, &cur->donation_elem, 
        thread_compare_donate_priority, 0);
        donate_priority(); 	
    }
    /* --- pjt 1.2 priority donation --- */
    
    sema_down (&lock->semaphore);
    /* --- pjt 1.2 priority donation --- */
    cur->wait_on_lock = NULL;
    /* --- pjt 1.2 priority donation --- */
    lock->holder = thread_current ();
}

lock->holder는 현재 lock을 소유하고 있는 스레드를 가리킨다. 현재 lock을 소유하는 스레드가 없다면 (if(lock->holder)) if 문을 건너 뛰고 바로 sema_down()을 실행한 뒤, lock을 점유(lock->holder = thread_current())할 것이다.

 

여기서 주의! 현재 스레드가 lock_acquire()를 실행했다는 건 이미 이전에 lock을 점유하고 있는 스레드보다 우선순위가 높기 때문에 CPU 제어권을 선점한 것이다. 따라서 lock을 점유하고 있던 CPU와 우선순위 크기를 비교할 필요가 없다. 현재 스레드의 우선순위가 높기 때문에 lock_acquire를 실행할 수 있는 것이기 때문이다.

 

반면 lock을 누군가 점유하고 있다면 현재 스레드의 wait_on_lock 멤버에 기다려야 할 lock을 추가한다. 이어서 현재 lock을 들고 있는 스레드의 donations 리스트에 자신의 donation_elem을 달아준다. 이때, list_push_back이 아닌 list_insert_ordered 방식으로 달아주는데, 이는 donations 리스트에 들어있는 스레드들이 우선순위를 기부한 순서가 아니라 가장 높은 우선순위부터 lock을 들고 기부 리스트에서 빠져나가는 구조기 때문이다. 이 부분 주의할 것!(list_push_back으로 했다가 생고생했다..) thread_compare_donate_priority는 이전에 했던 우선순위 비교 함수와 유사하게 우선순위를 비교하는 함수다. 단, 비교하는 인자가 thread가 아닌 donation 리스트에 들어갈 구조체 멤버 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()

dl 함수는 자신의 priority를 스레드에게 빌려주는 함수다. 여기서 주의해야 할 점은, nested donation 케이스처럼 lock에 연결된 모든 스레드에 donation이 일어난다는 점이다. 따라서 wait_on_lock에서 기다리고 있는 lock을 현재 점유하고 있는 holder들을 순회하면서 모두에게 자신의 우선순위를 기부한다.

 

/* threads/thread.c */

void donate_priority(void)
{
	int depth;
    struct thread *cur = thread_current();
    
    for (depth =0, depth < 8, depth++) {
    	if (!cur->wait_on_lock) // 기다리는 lock이 없다면 종료
        	break;
        struct thread *holder = cur->wait_on_lock->holder;
        holder->priority = cur->priority;
        cur = holder;
    }
}

과제에서 nested donation의 깊이를 최대 8로 정해놨기 때문에 depth 값을 설정해준다. 맨 처음에는 현재 스레드가 기다리고 있는 lock의 holder 스레드로 가서 걔한테 우선순위를 기부한다. 그러면 cur을 그 holder 스레드로 변경하고, 다음 for문에서 그 스레드가 기다리는 또다른 lock을 현재 들고 있는 holder 스레드에도 우선순위를 기부하는 식. 그러다 더이상 연결된 wait_on_lock이 없다면 종료한다.

 

 

void lock_release (struct lock *lock)

수정 전 함수는 아래와 같다. 해당 스레드가 lock 안에서 작업을 끝마치면 현재 스레드가 갖고 있던 lock을 NULL 상태로 바꾸고 sema_up을 실행한다. 그러면 다음 차례에서 기다리고 있던 스레드가 해당 lock을 잡을 것이다.

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

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

여기서 스레드가 priority를 양도받아서 작업을 마치고 lock을 반환할 때의 경우를 만들어줘야 한다. 즉, sema_up 하여 lock 점유를 반환하기 전에 lock을 사용하기 위해 나한테 priority를 빌려준 스레드들을 donations 리스트에서 전부 제거하고 priority를 재설정해주는 작업을 추가한다. 이를 위해 두 가지 새로운 함수를 짠다. 바로 remove_with_lock(lock) (priority 빌려준 스레드를 donations 리스트에서 제거)과 refresh_priority() (priority 재설정)이다.

 

/* thread/synch.c */
void
lock_release (struct lock *lock) 
{
  ASSERT (lock != NULL);
  ASSERT (lock_held_by_current_thread (lock));
  
  /*--- priority donation ---*/
  remove_with_lock(lock);
  refresh_priority();
  /*--- priority donation ---*/
  
  
  lock->holder = NULL;
  sema_up (&lock->semaphore);
}

 

위의 lock_release()를 실행하면 해당 lock을 사용하기 위해서 자신의 우선순위를 기부하고 기다리고 있던 스레드는 이제 priority를 빌려줄 이유가 없어지니 donation 리스트로부터 자신을 지운다. 이를 위해 remove_with_lock()에서는 donations 리스트에 달려 있는 list_elem으로부터 thread를 불러온다. 현재 점유가 풀린 lock에 대해 donations 리스트에 있는 스레드가 해당 lock을 원하는 애라면 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);
  }
}

 

이어서 donations 리스트의 우선순위를 재설정한다. 만약 donations 리스트가 비었다면 init_priority로 설정하고 도네이션 리스트 중 가장 높은 priority를 가져온다. 이를 위해 list_sort()를 실행한다.

/* 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;
  }
}

 

void thread_set_priority (int new_priority)

이전에 수정한 함수. 현재 스레드의 우선순위를 인자로 받은 new_priority로 변경해준 뒤, test_max_priority()로 ready 리스트 맨 앞에서 기다리고 있던 스레드와 우선순위를 비교해 만약 ready 리스트에 기다리고 있던 스레드의 우선순위가 더 높다면 현재 작업 중인 스레드가 CPU를 기다리고 있던 애한테 양보한다. 

void thread_set_priority (int new_priority) {
	thread_current ()->priority = new_priority;
	/* --- Pjt 1.2 --- */
	test_max_priority();
}