(2021.10.16) Priority Scheduling - priority inversion (donation)

1. 서론 및 필요 내용 설명

priority inversion 현상에 대해서는 이전 포스팅에서 자세히 다루었으니 궁금한 사람은 참조하면 된다. 이제 해당 문제를 해결하여 priority 스케줄링을 위해 필요한 priority donation을 구현해보자. priority donation을 고려할 때는, 물론 여러 케이스가 있을 수 있겠지만, 결국 이를 어떻게 일괄적으로 구현할 수 있는가가 문제가 된다. 

 

priority donation과 연관되어 priority에 변동이 일어나는 경우는, lock을 acquire하거나, release하는 경우 뿐이다. 각 케이스에서 신경써야 할 부분을 살펴보자.

1-1. Acquire할 때

우선 Thread가 lock(후술 락)을 acquire하려면, 지금 실행되는 상태여야 한다는 것이 중요하다. 또한, 현재 acquire하는 락 외에 wait하는 락은 없어야 한다. 만약 현재 acquire하려는 락의 소유자가 없다면 문제될 것이 없다. 그냥 카운터를 하나 내리고 락을 가져가면 된다.

 

문제는 acquire하려는 락이 소유자가 있는 경우이다. 소유자가 있는 경우 현재 Thread가 Block되고, 락을 가진 Thread (Thread A라 하자)는 현재 실행되던 Thread에게 priority를 받을지를 결정해야 한다. 만약 A의 현재 priority보다 현재 실행되는 Thread의 priority가 더 높다면 A는 priority를 갱신하게 된다. 여기서 끝나지 않는다. 만약 priority가 갱신된 A가 이미 다른 락을 acquire하기 위해 Block된 상태라면, 그 락을 소유하는 Thread는 다시 A의 priority를 받아 갱신할지를 결정해야 하기 때문이다. 이런 식으로 재귀적으로 타고 들어가면서 Priority를 갱신해주어야 하며, 더 이상 갱신이 되지 않거나, Thread가 기다리는 락이 없으면 Priority Donation이 종료된다.

 

정리하면, 다음과 같다.

 

1. 락을 Acquire할 때 소유 Thread가 있을 경우 이 과정은 트리거 된다.
2. 락의 waiter가 되어 Priority를 넘기는 Thread를 Donor, 락을 소유하고 있어 Priority를 받는 Thread를 Acceptor라 하자.
3. 만약 Acceptor의 현재 priority보다 Donor의 priority가 높다면, 해당 priority로 자신의 priority를 갱신한다. 아니라면 과정을 종료한다.
4. Acceptor가 또다른 락을 기다리고 있어 Block된 상태라면, Acceptor를 다음 Donor로, 해당 락의 소유자를 다음 Acceptor로 하여 3으로 돌아간다.

어때요, 참 쉽죠?

1-2. Release할 때

우선 Release를 하는 시점에서 Thread가 실행이 되고 있었을 것이기에, 해당 Thread가 기다리고 있는 락은 없다. 따라서 만약 priority에 변동이 있다면, 락을 하나 Release하는 것으로 인해 락을 기다리는 Thread의 목록이 변동함으로 생기는 것이다. 따라서 Priority에 생기는 변화는 해당 Thread 내에서 벌어지는 것으로 끝난다.

 

문제는, 그 락을 Release함으로 생기는 부가적인 문제이다.

 

• 락을 가지고 있던 Thread에서 생기는 priority 변화로 인한 preemption
• acquire 과정 중에 생긴 donation으로 인해 락의 waiter들의 priority 순서가 뒤죽박죽이 될 수 있는 점
• Release한 이후에 priority는 어떻게 계산하는지

우선 첫 문제에 대해서는 이전 포스팅에서 sema_up에 preemption 루틴을 넣어 놨기에 만약 preemption 루틴 이전에 priority만 제대로 계산된다면 문제될 것이 없다. 두 번째에 대해서는 waiter를 priority에 따라 한 번 정렬하는 루틴을 추가하는 것으로 해결할 수 있다. 마지막 문제가 중요한 문제인데, Thread가 원래 가지고 있었던 priority와, Thread가 현재 보유하고 있는 락들의 waiter중 가장 높은 priority들을 선별한 뒤, 이들 중 가장 높은 priority를 현재의 priority로 정하면 된다. 이를 위해서는 Thread가 다음의 정보를 저장하고 있을 필요가 있다.

 

• 보유하고 있는 락의 리스트
• 원래 부여받은 priority

여기까지 꽤나 자세한 사항을 살펴봤으니 구현을 해보도록 하자. 머리가 아프다.

 

---

2. 구현해야 하는 것

• Thread와 lock 구조체의 수정
• 재귀적으로 실행될 수 있는 priority_donate() 함수
• 호출할 때마다 그 상황에서의 Thread가 보유한 락에 기반하여 priority를 계산하는 priority_calculate() 함수
• 기타 함수 수정

 

---

3. 구현 과정

priority donation을 위해서는 각 Thread에서 자신이 어떤 락들을 보유하고 있는지 알고 있어야 한다. 따라서, Thread가 소유한 락들을 관리할 리스트를 Thread 구조체에 넣는다. 또한, 락을 기다리다가 Block된 Thread에서 priority donation 재귀를 따라가기 위해서는 어떤 락을 기다리고 있는지를 알고 있어야 하기 때문에 해당 락을 가리키는 wait_on_lock 포인터도 추가해준다. 

struct thread {
	...
	int priority;                       /* Current Priority. */
	int org_priority;                   /* Original Priority */
	
	...
	
	/* For priority donation */
	struct list lock_list;
	struct lock *wait_on_lock;
	...    
};

static void
init_thread (struct thread *t, const char *name, int priority) {
	...
	t->priority = priority;
	t->org_priority = priority;

	list_init(&t->lock_list);
	t->wait_on_lock = NULL;

	t->magic = THREAD_MAGIC;
}

또, 위에 언급한대로 자신이 원래 부여받은 priority 또한 저장해두고 있어야 하기에, org_priority라는 이름으로 멤버를 추가해서 관리하도록 한다.

 

락을 리스트로 만들기 위해서는 락 구조체에 list_elem 구조체를 추가할 필요가 있다. 추가해준다.

/* Lock. */
struct lock {
	struct list_elem lock_elem; /* Used for lock list in each threads */
	struct thread *holder;      /* Thread holding lock (for debugging). */
	struct semaphore semaphore; /* Binary semaphore controlling access. */
};

추가한 변수들을 바탕으로 priority_donate() 함수를 구현하자. 위에 설명한 플로우를 그대로 구현하면 된다.

void
priority_donate(struct thread *donor, struct thread *acceptor)
{
	if (donor->priority > acceptor->priority) {
		acceptor->priority = donor->priority;

		if (acceptor->wait_on_lock != NULL)
		{
			priority_donate(acceptor, acceptor->wait_on_lock->holder);
		}
	}

	return;
}

이러면 재귀적으로 타고 들어가면서 priority를 갱신할 수 있다.

 

다음으로, priority_calculate() 함수를 구현한다. 파라미터로 priority를 계산하려는 Thread t를 주면, 우선 원래의 priority인 org_priority를 최초 priority로 두고 계산을 시작한다. t의 락 리스트를 순회하면서, 각 락의 waiters 중 가장 priority가 높은 것을 뽑아 현재까지 최고의 priority와 비교하여 더 높은 priority를 남겨둔다. 이 때, donation 과정에 의해 waiter의 정렬 상태가 깨져 있을 수 있기 때문에 list_sort를 해 주어야 한다. 최종적으로 저장된 priority를 t의 priority로 지정하면 루틴이 종료된다. 이대로 구현하면 아래와 같다.

void
priority_calculate(struct thread *t)
{
	struct list_elem *e;
	struct list_elem *t_e;
	struct lock *lock_ptr;

	int max_priority = t->org_priority;
	int max_waiter_priority = 0;

	if (!list_empty(&t->lock_list))
	{
		for (e = list_begin(&t->lock_list); e != list_end(&t->lock_list); e = list_next(e))
		{
			lock_ptr = list_entry(e, struct lock, lock_elem);

			if (!list_empty(&lock_ptr->semaphore.waiters))
			{
				list_sort(&lock_ptr->semaphore.waiters, cmp_priority, NULL);
				max_waiter_priority = list_entry(list_front(&lock_ptr->semaphore.waiters), struct thread, elem)->priority;

				if (max_waiter_priority > max_priority)
					max_priority = max_waiter_priority;
			}
		}
	}

	t->priority = max_priority;
	return;
}

구현된 함수를 이제 thread.c와 synch.c에 포함시켜 보자. priority_donate() 의 경우, 락을 acquire하는 lock_acquire() 에만 포함되면 된다. 구하려는 락의 보유자가 이미 있을 경우, 현재 실행되던 Thread는 Block될 것이므로 wait_on_lock을 설정하고 priority_donate() 를 호출한 뒤,  sema_down을 해주면 된다. sema_down() 내에서 Block 된 Thread가 언젠가 락을 얻기 위해 Unblock되면 wait_on_lock을 NULL로 초기화한 뒤, 본인의 락 리스트에 해당 락을 넣어준다.

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

	enum intr_level old_level;
	old_level = intr_disable();

	struct thread *cur = thread_current ();
	
	if (lock->holder)
	{
		cur->wait_on_lock = lock;
		priority_donate (cur, lock->holder);
	}

	sema_down (&lock->semaphore); // gets blocked when there is holder
	
	cur->wait_on_lock = NULL;
	list_push_back (&cur->lock_list, &lock->lock_elem);
	
	lock->holder = thread_current ();

	intr_set_level (old_level);
}

priority_calculate() 의 경우, 원래는 lock_release()에 추가하는 것이 맞지만, 해당 함수에 의해 현재 Thread의 priority가 낮아지고 sema_up을 하기 전 타이머 인터럽트 등 외부 인터럽트에 방해를 받을 경우, 이상한 문제가 초래될 수 있을 것이라 생각했다. 따라서 sema_up() 내에서 인터럽트가 꺼진 상태로 atomic하게 처리하는 것이 더 좋을 것이라고 판단하여 preemption 직전에만 실행되도록 구현하였다. 

void
sema_up (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (!list_empty (&sema->waiters))
		thread_unblock (list_entry (list_pop_front (&sema->waiters),
					struct thread, elem));
	sema->value++;

	priority_calculate (thread_current());
	preemption ();
	intr_set_level (old_level);
}

또 수정할 곳이 있다. 바로 thread_set_priority(). 이 때 바꿔주는 것은 지금 OS에 의해 인식되는 donation이 관여하는 priority가 아닌, 원래 부여받은 priority이기에 org_priority를 바꿔주도록 정정한다. 또한 바뀐 org_priority에 의거하여 priority_calculate()를 다시 해 줄 필요가 있기에 추가해준다.

void
thread_set_priority (int new_priority) {
	thread_current ()->org_priority = new_priority;
	priority_calculate (thread_current ());
	preemption ();
}

 

---

4. 디버깅

여기까지 코딩하고 실행하면 몇 개의 테스트가 통과하지 않는다. priority-donate-sema, priority-donate-lower, priority-sema, priority-donate-chain으로 간단한 케이스인 donate-sema부터 들여다 보았다.

 

priority-donate-sema.c의 주석 내용은 다음과 같은데,

/* Low priority thread L acquires a lock, then blocks downing a
   semaphore.  Medium priority thread M then blocks waiting on
   the same semaphore.  Next, high priority thread H attempts to
   acquire the lock, donating its priority to L.

   Next, the main thread ups the semaphore, waking up L.  L
   releases the lock, which wakes up H.  H "up"s the semaphore,
   waking up M.  H terminates, then M, then L, and finally the
   main thread.

   Written by Godmar Back <gback@cs.vt.edu>. */

H가 L에게 priority donate를 한 이후 main thread가 sema_up을 했을 때 L이 아닌 M이 실행된 것으로 보인다. priority donation에 문제가 있는건지 해서 priority를 printf로 찍어봤지만 정상적으로 나왔다. 코드를 다시 잘 살펴보니 참 간단한 실수를 저질렀다. 앞서 priority_calculate() 때도 donation 과정에 의해 waiter의 priority 순 정렬 상태를 보장할 수 없어 list_sort를 해 줬었는데, sema_up에서도 당연히 해 줬어야 한다. donation 이후에 정렬이 안되어 있어서 priority가 높아진 L보다 앞서 있는 M이 튀어나온 것이다. 추가하고 다시 실행해줬다.

void
sema_up (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (!list_empty (&sema->waiters))
	{
		list_sort(&sema->waiters, cmp_priority, NULL);
		thread_unblock (list_entry (list_pop_front (&sema->waiters),
					struct thread, elem));
	}
	sema->value++;

	priority_calculate (thread_current());
	preemption ();
	intr_set_level (old_level);
}

그 결과 mlfqs를 제외한 케이스들은 모두 통과하는 것을 볼 수 있다. 제발 이런 초보적인 실수는 저지르지 말자...

와 통과~

 

---

5. 후기 및 잡담

사실 포스팅의 주요한 내용이 아니라 생략한 내용이지만 그래도 추가하는 것이 맞을 것 같아 여기 기록한다. 테스트 케이스 중 condvar이 붙은 테스트 케이스는 synch.c의 또다른 함수군을 고쳐야 통과할 수 있다. condvar은 condition variable의 줄임일 것이며, condition variable은 OSTEP에 자세한 설명이 있으니 설명은 생략하겠다.

 

아무튼 이를 구현하는 방식으로는 condition은 waiters라는 리스트를 가지고 있으며, 이 리스트는 semaphore_elem이라는 구조체를 관리한다. semaphore_elem은 그냥 semaphore에 list_elem을 추가한 것이라 생각하면 된다. 각 Thread에서 cond_wait()을 호출하면 지역변수인 semaphore_elem waiter을 하나 생성해 카운트를 0으로 초기화하고 waiter를 waiters 리스트에 넣은 뒤, 해당 Thread가 waiter를 sema_down() 하게 만들어 Thread를 Block시킨다. 그리고 cond_signal에서 waiters 리스트에 있는 waiter 중 하나를 sema_up() 시켜 Block된 Thread 중 하나를 Unblock 시키는 방식이다.

 

이 때, 구현해야 하는 것은 cond_signal에서 waiter 중 하나를 sema_up 시켜 Thread 하나를 깨울 때, 기다리고 있는 Thread 중 priority가 높은 순서대로 깨워야 한다는 것이다. 이는 간단하다. sema_down()을 할 때, 카운트가 0으로 초기화되어있어 Thread는 무조건 Block 당하기 때문에 cond_wait()을 호출한 Thread는 semaphore의 waiter로서 포함될 것이다. 따라서 waiters 리스트의 각 waiter(semaphore)의 waiters의 맨 앞 원소로 cond_wait를 호출했던 Thread를 참조할 수 있다. 이름이 참 헷갈린다. Thread를 참조할 수 있으면 해당 Thread의 priority를 비교할 수 있기 때문에 다음과 같은 비교함수를 구현할 수 있다.

bool
cmp_cond_waiters (const struct list_elem *a, const struct list_elem *b, void *aux) {
	struct semaphore_elem *s_a = list_entry(a, struct semaphore_elem, elem);
	struct semaphore_elem *s_b = list_entry(b, struct semaphore_elem, elem);
	
	struct thread *t_a = list_entry(list_front(&s_a->semaphore.waiters), struct thread, elem);
	struct thread *t_b = list_entry(list_front(&s_b->semaphore.waiters), struct thread, elem);

	return t_a->priority > t_b->priority;
}

비교함수를 구현하면 리스트를 정렬할 수 있기에, cond_signal에서 뽑기 전에 정렬하는 루틴을 추가하면 끝이다.

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))
	{
		list_sort (&cond->waiters, cmp_cond_waiters, NULL);
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
	}	
}

내용 자체가 뭔가 플러스 알파 느낌이라 자세히 다루지는 않고 넘어가는 점 참조바란다.

 

어쨌든 여기까지 Priority 스케줄링이 끝났다. 이제 다음 포스팅부터는 mlfqs를 건드려보자.