[Project_1_THREADS]_Priority Scheduling_2

Priority Inversion

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

카이스트 핀토스 가이드 설명에서 Priority inversion은 어떠한 것이며 우리가 무슨 상황을 해결해야 할지 설명해 주고있다.

간략하게 말하자면 H, M, L의 우선순위가 있고 딱 한명만 사용가능한 자원 LOCK 이 있다고 했을때 

처음에 L이 LOCK을 가지고 작업을 하는도중 H가 들어오면 L은 작업대는 H에게 넘겨주지만 자신의 LOCK은 들고가버린다. 그럼 H도 LOCK이 필요하다 했을때 L때문에 작업을 못하고 작업대를 양보한다. 대기리스트에 있던 M이 빈 작업대를 들어오고 M은 LOCK이 필요없기 떄문에 자신의 작업을 끝마치고 나간다. 그후 작업을 못하고 밀려난 L이 돌아와 작업을 마무리하고 LOCK을 반납하면 그제서야 H가 LOCK을 받아 작업을 마친다.

이렇게 되면 작업의 종료시기가 M->L->H가 된다. 낮은우선순위의 스레드가 먼저 작업을 마치게 되는 Priority Inversion이 발생한 것이다.

 

우리는 우선순위 스케쥴링을 통해 이러한 문제점을 해결해 주어야 한다. 

 

우선순위 반전 상황은 우선순위 donation으로 해결이 가능하며  이 donaiton 상황은 Mulltiple donation, Nested donation이 일어날수있다.

 

 Mulltiple donation

여러번의 donation이 일어난 상황을 Multipel donation이라고 한다. 

위의 예시를 보면 priority가 31인 L이 LockA와 LockB를 들고있다. 그러던중 LockA를 M이 요청하고 이것을 빨리 반납해 주기 위해 L은 M의 우선순위를 기부받아 잠시 32가 된다.

그런데 H가 또 들어와 LockB를 요구하고있다 M보다 우선순위가 높기때문에 또 L은 잠시 H에게 우선순위를 기부받아 33이 된다.  이런식으로 여러번의 donation을 받는 상황을 Multipel donation 이라고 한다.

 

Nested donation

네스티드 도네이션은 여러번의 단계적 기부가 일어나는 것을 말한다.

L이 처음 lockA에 대한 소유권을 가지고 있다고 할때  M도 lockA을가지고 싶어 wait_on_lock

락을 하고 기다린다. M이 기다리는 LockA의 소유권자는 A이고 우선순위를 L에게 양도한다. 이때  H가들어와 lockB를 요구하지만 lockB는 M이 소유하고 있다 그러면 B를 받기위해서는 M의 우선순위를 높여주어야 한다. M이 끝나려면 L이 끝나야 하므로 M은 다시L의 우선순위를 높인다. 그렇게 L이 A를 먼저 다 쓰고 반환하면 M이 작업을 시작한다. 전체적인 흐름을 보면 아래 그림과 같다. 

구현

 

앞선 Priority Scheduling 1 에서는 먼저들어간 스레드가 우선적으로 먼저 나오는 간단한 우선순위 스케줄링을 하였다.

하지만 우선순위가 달라 먼저 들어온애가 나중에 들어온 애보다 우선순위가 밀려 나중에 실행이 되도록 스케줄링을 해주어야한다.

 

이러한 Priority Scheduling을 하기위 해 우선  스레드들 간에 누가 먼저 할것인지, 누군가 일을하고 있다면? 방해하지 않도록 서로 약속을 하는 동기화 과정이 필요하다.

핀토스 동기화 도구 

pintos의  thread/synch.h, synch.c 안에 들어가 어떤식으로 이러한 약속을 하는지 봐본다.

/* thread/synch.h */
struct semaphore 
  {
    unsigned value;             /* Current value. */
    struct list waiters;        /* List of waiting threads. */
  };
  
struct lock 
  {
    struct thread *holder;      /* Thread holding lock (for debugging). */
    struct semaphore semaphore; /* Binary semaphore controlling access. */
  };
  
struct condition 
  {
    struct list waiters;        /* List of waiting threads. */
  };

1. 세마포어

핀토스에서 세마포어는 공유되는 자원의 개수를 포함하는 value와 현재 자원을 기다리는 스레드들의 리스트 wairtes정보를 담은 구조체

2. lock

lock을 할당받은 스레드의 정보 holder 와 value가 1인 세마포어 로 이루어진 구조체

3. conditton

condition variables 가 만족하기를 기다리는 waiters 의 리스트

 

 

세마포어가 뭔지 궁금하신분들을 위한 링크

6.Process Synchronization & Mutual Exclusion

세마포어는 상호배제를 위한 해결책으로 다익스트라님이 고안하신 아이디어이다. 즉 내가어떠한 자원을 점유하였을때 다른사람이 못건드리게 하기위한 변수이다. 

 

하나의 자원을 두고 여러 스레드가 sema_down(P연산)으로 자신도 그 자원을 소유하고 싶다 외치는경우 우선순위 스케줄링을 위해서

원래 해당 자원을 소유하던 스레드가 사용을 마치고 sema_up(V연산)을통해 자원을 반납하였을때 우선순위가 높은 스레드에게 해당자원을 넘겨주어야 한다.

sema_up, sema_down 수정

핀토스에 기본적으로 구현되어있는 sema_up과 sema_down을 살펴보고 수정하자

/* thread/synch.c */
sema_up (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (!list_empty (&sema->waiters))
	{
	/*--------------- PROJECT1: THREADS - Priority Scheduling ----------------*/
		//list_sort() 를 이용 waiters 리스트를 내림차순으로 정렬하여 준다
		list_sort(&sema->waiters, thread_compare_priority, 0);
	/*------------------------------------------------------------------------*/
	thread_unblock(list_entry(list_pop_front(&sema->waiters), struct thread, elem));
	}

    	sema->value++;
    	/*--------------- PROJECT1: THREADS - Priority Scheduling ----------------*/
	//unblock된 스레드가 running 스레드 보다 우선순위가 높을 수 있기 때문에 thread_test_preemption(); 실행
    	thread_test_preemption();
	/*------------------------------------------------------------------------*/
	intr_set_level (old_level);
}

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

	ASSERT (sema != NULL);
	ASSERT (!intr_context ());

	old_level = intr_disable ();
	while (sema->value == 0) {
		
		//list_push_back (&sema->waiters, &thread_current ()->elem);
		/*--------------- PROJECT1: THREADS - Priority Scheduling ----------------*/
		list_insert_ordered(&sema->waiters, &thread_current()->elem, thread_compare_priority, 0);
		/*------------------------------------------------------------------------*/
		thread_block ();
		
	}
	sema->value--;
	intr_set_level (old_level);
}

sema_up 수정 설명

우선 기존의 세마 업은 세마포어를 얻기위해 대기하고있는 스레드 리스트(waiters)가 비어있으면 세마포어 변수를 증가시키고 unblock된 스레드가 있다면 현재 running 중인 스레드와 비교를 위해 thread_test_preemption()을 통해 우선순위를 비교한다.

waiters가 비어있지 않다면? 수정 이전에는 세마포어를 기다리던 스레드들의 리스트중 우선순위 상관없이 가장 앞의 스레드를 pop해서 unblock해주었다. 이전에 waiters 안의 스레드들에 대한 우선순위를 정리하여 우선순위가 높은 스레드를 꺠워주어야 한다. 따라서 핀토스 기본함수 list_sort함수를 통해 waiter를 우선순위를 고려하여 정렬해주도록 수정하였다.

sema_down 수정 설명

세마다운은 기존에 세마포어가 0 즉 사용가능한 공유자원이 없는경우 세마포어가 생길때까지 waiters리스트 맨뒤로 추가되었다.  이제는 우선순위를 고려해야하므로 대기상태로 들어갈때 우선순위를 고려하여 집어넣도록 한다.

그후 해당 tread는 블락 시킨다.

 

Condition_wait, Cond_signal 수정

Condition variables 가 가진 waiter리스트의 요소들 cond->waiters는 어떠한 세마포어를 기다리는지 저장하는 리스트이다.

void
cond_wait (struct condition *cond, struct lock *lock) {
	struct semaphore_elem waiter;

	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	sema_init (&waiter.semaphore, 0);
	list_push_back (&cond->waiters, &waiter.elem);
	//여기서 추가하는 waiter.elem은 세마포어elemnt이다. 
	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}

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)){
/*--------------- PROJECT1: THREADS - Priority Scheduling ----------------*/
		list_sort(&cond->waiters, sema_compare_priority, 0);
/*------------------------------------------------------------------------*/
	sema_up(&list_entry(list_pop_front(&cond->waiters),
						struct semaphore_elem, elem)->semaphore);
	}
    
 /*--------------- PROJECT1: THREADS - Priority Scheduling ----------------*/
bool sema_compare_priority(const struct list_elem *l, const struct list_elem *s, void *aux UNUSED)
{
	struct semaphore_elem *l_sema = list_entry(l, struct semaphore_elem, elem);
	struct semaphore_elem *s_sema = list_entry(s, struct semaphore_elem, elem);

	struct list *waiter_l_sema = &(l_sema->semaphore.waiters);
	struct list *waiter_s_sema = &(s_sema->semaphore.waiters);

	return list_entry(list_begin(waiter_l_sema), struct thread, elem)->priority > list_entry(list_begin(waiter_s_sema), struct thread, elem)->priority;
}
/*------------------------------------------------------------------------*/

 

그렇다면 세마포어가 반납될떄 이를 cond_signal함수를 통해 반납되는 세마포어가 대기목록에 있다면 이를 우선순위가 높은 자에게 넘겨주기 위한 정렬이 필요하다. 따라서 위와 같이 수정해 주었다. 

sema_compare_priority는 세마포어의 우선순위를 비교하기 위한 함수이다.

 

이제 동기화에 대해서는 이정도로 마무리 해주고 

진짜 목적 이 동기화 를 이용해 우선순위 스케줄링을 마무리해 보자

 

thread 구조체 수정

struct thread {
	/* Owned by thread.c. */
	tid_t tid;                          /* Thread identifier. */
	enum thread_status status;          /* Thread state. */
	char name[16];                      /* Name (for debugging purposes). */
	int priority;                       /* Priority. */

	/* Shared between thread.c and synch.c. */
	struct list_elem elem;              /* List element. */
	 
/*--------------- PROJECT1: THREADS - Alarm Clock----------------*/
	int64_t	wakeup;						/* time to wake up */

/*--------------- PROJECT1: THREADS - Priority Scheduling ----------------*/
	int init_priority;

	struct lock *wait_on_lock;
	struct list donations;
	struct list_elem donation_elem;
/*-----------------------------------------------------------------------*/
.
.
.
	/* Owned by thread.c. */
	struct intr_frame tf;               /* Information for switching */
	unsigned magic;                     /* Detects stack overflow. */
};

우선 스레드 구조체 안에 자신의 원래 우선순위를 저장할 init_priority, lock을 기다림을 선언할 wait_on_lock 기부를 해주는 스레드를 저장할 donation list,  list_elem donation_elem 구조체를 추가해준다.

 

thread_init 수정

구조체에 무언가를 추가해 주었으니 스레드 초기화시 위 사항들도 초기화 해준다.

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;
	/*--------------- PROJECT1: THREADS - Priority Scheduling ----------------*/
	t->init_priority = priority;
	t->wait_on_lock = NULL;
	list_init(&t->donations);
	/*------------------------------------------------------------------------*/
}

 

lock_acquire 수정

도네이션이 일어나는경우는 언제일까?

어떤 스레드가 lock을 요청하고 해당 lock을 다른 스레드가 들고있다면 그 스레드에게 기부를 해야하므로 lock을 요청하는 함수 Lock_acquire 함수를 보도록하자

lock_acquire (struct lock *lock) 
{
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (!lock_held_by_current_thread (lock));
	/*--------------- PROJECT1: THREADS - Priority Scheduling ----------------*/
	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 을 얻기 전,
	 이후는 lock 을 얻은 후이다.sema_down 에 들어가기 전에 lock 을 가지고 있는 스레드에게 
	 priority 를 양도하는 작업이 필요
	 */
	sema_down(&lock->semaphore);

	/*--------------- PROJECT1: THREADS - Priority Scheduling ----------------*/
	cur->wait_on_lock = NULL;
	/*------------------------------------------------------------------------*/

	lock->holder = cur;
}

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

lock 요청이 들어왔을때 해당 락에 대한 holder가 이미 존제한다면 요청한 자신의 우선순위를 기부함을 현재 소유자에게 알리고 우선권을 양보하는 과정을 넣어준다.

그후 락이 반납될때까지 기다리다가 반납이 되면 더이상 락을 기다리지 않으므로 wait_on_lock을 초기화 해주고 자신이 소유권자가 된다.

thread_compare_donate_priority함수는 donate list에 들어가기전 우선순위를 확인하여 들어가기 위해 만들어준다.

 

 

donate_priority () 생성

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

이제 우선순위 도네이션을 해주는 함수를 생성한다. 현재 내가 기다리는 lock의 소유주에게 나의 우선권을 넘기고 그 소유권자도 lock을 기다리고 있다면 그 스레드의 우선권을 갱신한다 이렇게 최대 깊이 8까지 들어가 소유권을 넘겨준다 8은 임의로 설정한 수이다.

 

lock_release 수정

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

	/*--------------- PROJECT1: THREADS - Priority Scheduling ----------------*/
	remove_with_lock(lock);
	refresh_priority();
	/*------------------------------------------------------------------------*/

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

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

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

스레드가 우선순위를 양도받아 일을하고 lock을 반환 즉 realease할때 현재 스레드에게 우선순위를 빌려준 스레드들 중에서 반환되는 락을 기다리는 스레드가 있는지 검사하고 있다면 반환이 되었으니 기부자 리스트에서 제거한다.

그후 기부를 했으니 현재 스레드는 자신의 원래 우선순위를 회복하는 refresh과정이 필요하다.

 

따라서 이 두과정을 하는 함수를 생성하여 lock_release함수에 추가해준다.

 

또한 running과정에서 우선순위 변동이 일어나는 경우가 있을 수 있으니 이런경우 init_priority 를 새 우선순위로 변경하고 현재 ready 안에 있는 스레드 들과 비교하는 과정을 거친다. 

/* Sets the current thread's priority to NEW_PRIORITY. */
void
thread_set_priority (int new_priority) {
	thread_current ()->init_priority = new_priority;
	/*--------------- PROJECT1: THREADS - Priority Scheduling ----------------*/
	refresh_priority();
	thread_test_preemption();
	/*------------------------------------------------------------------------*/
}

이렇게 마무리 되면 아래 결과와 같이 priority_scheduling이 마무리된다.

 

통과

 

도움받은 블로그 :

https://poalim.tistory.com/35?category=758538 

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