PintOS Project 1 : Thread (Priority)

우선순위 스케줄링

 

 

 

CPU 스케줄링 중 하나의 기법인 우선순위 스케줄링은 비선점(Non- Preemptive) 방식이다. 따라서 CPU를 점유하고 있는 스레드가 우선순위가 제일 높으면, 이 스레드의 모든 작업이 끝나야 CPU를 양보한다. 또한 현재 실행 중인 스레드의 우선순위보다 높은 우선순위를 가진 새로운 스레드가 생성되었을 때, 바로 현재 스레드는 즉시 CPU를 양보한다.

 

 

 

 

 

---

 

 

 

 

 

 

여러 스레드가 동시에 같은 데이터를 조작할 때 타이밍이나 접근 순서에 따라 결과가 달라질 수 있는 상황인 경쟁 조건을 방지하기 위해 OS는 여러 스레드를 동시에 실행해도 공유 데이터의 일관성을 유지하는 동기화(synchronization) 작업을 해야한다.

 

이 때의 공유 데이터를 임계 영역(critical section)이라고 한다. 여기서 또 필요한 개념인 LOCK이 있다. LOCK은 critical section에 접근 할 수 있는 권한이라고 생각하면 될 것 같다.

데이터의 일관성을 유지하기 위해서 critical section은 하나의 스레드만 접근 할 수 있어야 하고, 이 스레드는 LOCK을 소유한다는 것으로 표시할 수 있다.

 

 

 

 

하지만 이제 우선순위 역전(Priority inversion) 문제에 대해서 직면하게 된다.

1. 낮은 우선순위(31)를 가진 스레드가 LOCK A를 소유하고 있고, 현재 CPU를 점유하고 있다.
2. 이후, 높은 우선순위(35)를 가진 스레드가 생성되었고, LOCK A를 획득하려고 하지만 이미 현재 실행 중인 스레드가 LOCK A를 소유하고 있기 때문에 LOCK A가 해제될 때 까지 기다리고 있다.
3. 우선순위(33)를 가진 스레드 하나가 생성되어 ready_list에 있고, 이 스레드는 LOCK을 필요로 하지 않기 때문에 우선순위 스케줄링에 의해 context switching이 발생한다.
4. 우선순위 스케줄링 때문에 현재 실행 중인 스레드(priority : 33)는 작업을 완료하기 전에는 CPU를 양보하지 않는다.
5. 우선순위가 가장 높은 스레드(priority : 35)는 우선순위 스케줄링에 의해 가장 먼저 작업을 해야하는 스레드지만 LOCK을 획득하지 못하고 절대 실행 할 수 없는 스레드 , 즉 우선순위 역전 현상이 발생된다. 이때 스레드(priority : 31)는 기아상태(starvation situation) 라고 한다.

 

 

 

따라서 이러한 문제를 우선순위 기부(priority donation)를 함으로써 해결한다.

 

 

 

 

 

현재 실행 중인 스레드(priority : 31)가 LOCK을 소유하고 있고, LOCK을 기다리는 스레드(priority : 35)가 LOCK을 획득하기 위해 자신의 우선순위를 기부함으로써 기존 우선순위(31)보다 높은 우선순위를 가진 스레드가 생성되더라도 CPU점유를 뺏기지 않고 작업을 완료한 후 LOCK을 해제하여 LOCK을 기다리던 스레드(priority : 35)가 LOCK을 획득하여 작업을 진행하도록 하는 방법이다.

물론 새로 생성되는 스레드가 우선순위가 35보다 높으면 context switching은 일어나는 것이 당연하다.

 

 

 

 

 

 

 

위와 같은 우선순위 역전 현상을 방지 하기 위해 우선순위 기부가 일어난다.

우선순위 기부가 한 번 있는 경우와 차이점은 실행 중인 스레드가 LOCK을 A,B 두 개를 가지고 있고 이 LOCK들을 원하는 스레드가 차례로 우선순위를 기부한다. 이 때, 어떤 스레드가 우선순위를 기부했는지 알기 위해 donation_list 라는 변수로 스레드들을 관리할 수 있고, LOCK A를 해제하면 스레드 내의 변수 wait_lock이라는 변수로 donation_list에서 제거해줌으로써 LOCK A를 얻었다는 처리를 해줄 수 있다. 또한 동시에 LOCK A 의 semaphore waiters에서도 제거해준다.

이러한 방식으로 다중 LOCK 문제를 해결할 수 있다.

 

 

 

 

---

 

 

코드구현

/* Sets the current thread's priority to NEW_PRIORITY. */
void thread_set_priority(int new_priority)
{
	thread_current()->original_priority = new_priority;

	refresh_priority();

	if (context_switching_possible())
	{
		thread_yield();
	}
}

// 실행중인 스레드와 ready_list의 첫번째 스레드의 우선순위를 비교해서 컨텍스트 스위칭이 가능하면 true를 반환한다.
bool context_switching_possible(void)
{
	if (!list_empty(&ready_list) && thread_current() != idle_thread)
	{
		if (thread_current()->priority < list_entry(list_front(&ready_list), THREAD, elem)->priority)
		{
			return true;
		}
	}
	return false;
}

 

---

 

lock acquire

// ~/synch.c
/* 
인자로 받은 lock을 통해 sema down을 함. 만약 lock의 홀더 스레드가 있으면 실행중인 스레드가 인자 lock을
기다린다고 해놓고, lock holder 스레드의 donation_list에 우선순위로 현재 스레드를 추가함.
그리고 우선순위 기부를 진행한다. 이후 sema down을 진행함. (세마다운은 0일때 sema waiters에 스레드를 추가하는것.)
이후 현재 스레드가 기다리는 lock을 NULL로 하고 lock을 현재 스레드가 가지도록 한다. 
*/
void lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (!lock_held_by_current_thread (lock));

   THREAD *t = thread_current();

   // lock을 가진 스레드가 존재하면 
	if(lock->holder){
		//현재 스레드가 어떤 lock을 기다리는지 추가  내가 얻길 원하는 lock 또는 풀리기를 기다리는 lock 
		t->wait_lock = lock;

		//holder의 donation 리스트에 현재 스레드를 우선순위 기준으로 내림차순 정렬하여 추가
		list_insert_ordered(&lock->holder->donation_list,&t->donation_elem,comparing_priority,NULL);
		
		//현재 스레드부터 wait_on_lock을 확인하여 priority를 donate한다(nested priority일 가능성 고려)
		donate_priority();
	}

	sema_down (&lock->semaphore);

   	////////////// lock 관련해서 수정 ///////////////
	//down을 했다면 lock을 획득했다는 것이므로 wait_on_lock(현재 스레드가 기다리는 lock)을 NULL로 바꾼다
	t->wait_lock = NULL;

	lock->holder = thread_current ();
}

 

 

 

// 우선순위를 기부하는 함수
void donate_priority(void)
{
	int depth;
	struct thread *cur = thread_current();
	int DEPTH_NESTED_PRIORITY = 8;
	for (depth = 0; depth < DEPTH_NESTED_PRIORITY; depth++)
	{
		// 현재 스레드가 lock을 기다리고 있는 상태가 아니면(lock 소유하고 있거나 영향이 없다면) 탈출
		// 보통 다중 우선순위를 계산해야되는 경우면 순서상 마지막 스레드다
		if (!cur->wait_lock)
			return;

		struct thread *lock_holder = cur->wait_lock->holder;

		lock_holder->priority = cur->priority;
		cur = lock_holder;
	}
}

 

 

/* 
sema 값이 0이면 실행중인 스레드를 sema waiters에 우선순위에따라 넣음. 그리고 BLOCK상태로 만들고 스케줄 진행  
sema 값이 0이 아니면 무한루프를 탈출해서 sema값을 줄이고 함수를 리턴함.
*/
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_insert_ordered (&sema->waiters, &thread_current()->elem, comparing_priority ,NULL);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

 

 

---

 

 

lock release

/*
해제하려는 lock을 인자로 받음. remove from donation list를 실행하면
인자의 lock를 필요로 하는 스레드가 donation list로 부터 제거된다.
*/
void lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock));

	//lock을 release할 때, 해제할 lock을 기다리는 스레드들을 donation 리스트에서 제거한다
	remove_from_donation_list(lock);
	//donation 리스트가 변동되었으니,우선순위를 재설정한다
	refresh_priority();
	lock->holder = NULL;
	sema_up (&lock->semaphore);
}

 

 

// donation_list에서 lock을 얻을 스레드를 지우는 함수
void remove_from_donation_list(struct lock *lock)
{
	struct list_elem *elem;
	struct thread *cur = thread_current();

	for (elem = list_begin(&cur->donation_list); elem != list_end(&cur->donation_list); elem = list_next(elem))
	{
		struct thread *thread = list_entry(elem, struct thread, donation_elem);

		if (thread->wait_lock == lock)
		{
			list_remove(&thread->donation_elem);
		}
	}
}

 

 

/*
sema waiters가 비어있지 않으면 sema waiters에서 앞에 것을 하나 pop하고 그 스레드로 unblock실행
이는 pop한 스레드를 우선순위에 따라 정렬함.
이후 sema +1 해주고 실행중인스레드의 우선순위가 ready_list의 첫번째스레드 우선순위보다 작으면 yield실행
*/
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,comparing_priority,NULL);
		thread_unblock (list_entry (list_pop_front (&sema->waiters),struct thread, elem));
	}
	sema->value++;	
	if(context_switching_possible()){
		thread_yield();
	}
	intr_set_level (old_level);
}

 

 

/*
 donation 리스트가 변동되었음, 따라서 현재 스레드의 우선순위를 초기우선순위로 반환하고
 현재 스레드의 donation_list를 우선순위로 정렬하여 처음의 스레드를 가지고 현재 스레드 우선순위와 
 비교하여 처음스레드가 더 크면 기부해준다.
*/
void refresh_priority(void)
{
	struct thread *cur = thread_current();

	cur->priority = cur->original_priority;

	if (!list_empty(&cur->donation_list))
	{
		// list_sort(&cur->donation_list, comparing_priority, NULL);

		struct thread *front = list_entry(list_front(&cur->donation_list), THREAD, donation_elem);

		if (front->priority > cur->priority)
			cur->priority = front->priority;
	}
}