Project 1 Priority donation

핀토스는 사람을 병들게 한다.

전체적인 코드를 보고싶으면 여기 있는 레포지토리에서 확인하시면 됩니다.

https://github.com/jun9898/pintos-kaist

 

🐳 문제정의

현재상황

Pintos - thread - alarm_clock 까지 구현된 상태에서는 작업의 우선순위가 고려되지 않은 채 쓰레드 스케쥴링을 수행한다. ( thread_unblock, thread_set_priority )

여기서 만약 Priority에 따라 Ready_list를 정렬한다고 할지라도, Priority Inversion이 발생할 수 있기 때문에 공유자원에 대한 관리 또한 필요하다. (sema_up, sema_down)


Priority Inversion을 해결하기 위한 방법으로는 priority inheritance protocol에서 소개된 Priority Donation이 있습니다.

Donation을 할 때 고려해야할 3가지 케이스

1. Priority donation
2. Nested donation
3. Multiple donation

해결방안

thread_unblock, thread_yield, 그리고 set_thread_priority

1) thread_unblock()

void
thread_unblock (struct thread *t) {
	enum intr_level old_level;

	ASSERT (is_thread (t));

	old_level = intr_disable ();
	ASSERT (t->status == THREAD_BLOCKED);
	// list_push_back (&ready_list, &t->elem);
	list_insert_ordered(&ready_list, &t->elem, cmp_thread_priority,NULL);
	t->status = THREAD_READY;
	intr_set_level (old_level);
}

2) thread_unblock()

void
thread_yield (void) {
	struct thread *curr = thread_current ();
	enum intr_level old_level;

	ASSERT (!intr_context ());

	old_level = intr_disable ();
	if (curr != idle_thread) {
		// list_push_back (&ready_list, &curr->elem);
		list_insert_ordered(&ready_list, &curr->elem, cmp_thread_priority,NULL);
	}
	do_schedule (THREAD_READY);
	intr_set_level (old_level);
}

ready_list에 Thread를 삽입할 때, Priority를 기준으로 정렬된 형식을 유지하게
list_insert_orderded()를 사용합니다.

3) preempt()

void
preempt() {
	// 쓰레드를 선점할 수 있어야 합니다.
	// 현재 running 중인 thread와 ready 리스트에 있는 스레드 비교를 해야함
	struct thread *cur = thread_current();

	if (list_empty(&ready_list)) {
		return;
	}
	if (cur == idle_thread) {
		return;
	}
	// list_elem 타입의 '변수명' 이 elem 이므로.
	// list_front vs list_begin ;
	if (cur->priority < list_entry(list_front(&ready_list), struct thread, elem)->priority) { 
		thread_yield();
	}
}

void
thread_set_priority (int new_priority) {
	thread_current ()->original_priority = new_priority;
	update_donation(); // 추후 설명합니다
	preempt();
}

새로운 쓰레드가 ready_list에 추가되거나, 현재 쓰레드의 우선순위가 변경 됐을 때(thread_set_priority) 대기중인 쓰레드들과 우선순위를 비교합니다. 만약 더 높은 우선순위를 가진 쓰레드가 존재하면, thread_yield()를 실행하여 context-switching을 수행해줍니다.

4) 🐭 sema_up , sema_down

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

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	//sema->value++;
	if (!list_empty (&sema->waiters)){
		list_sort(&sema->waiters, cmp_thread_priority, NULL); // donate 받아서 순위가 변경된 상황 고려.
		thread_unblock (list_entry (list_pop_front (&sema->waiters),
					struct thread, elem));
	}
	sema->value++;
	preempt(); // 락을 모두 사용하고, sema를 올려준 다음에 선점을 해주면 다음 우선순위의 쓰레드가 선점을 할 수 있습니다!
	intr_set_level (old_level);
}

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

	ASSERT (sema != NULL);
	ASSERT (!intr_context ());
	
	struct thread *t = thread_current();

	old_level = intr_disable ();
	while (sema->value == 0) {
		// list_push_back (&sema->waiters, &thread_current ()->elem);
		list_insert_ordered(&sema->waiters, &t->elem, cmp_thread_priority, NULL);
		thread_block ();
	}
	sema->value--; // 이제 내가 lock을 차지하겠다! 
	intr_set_level (old_level);
}

sema_up에서 list_sort()를 해주는 이유와 preempt()를 해주는 이유

sema_up이 되는 상황은, thread가 공유자원을 활용한 작업을 마치고 lock을 반납하는 상황이다. 그렇기 때문에 우선순위가 가장 높은 thread가 CPU를 선점할 수 있도록 정렬을 해준 뒤 thread_unblock을 해준다. 그 뒤 preempt 함수를 실행해주면 priority가 높은 thread가 실행 될 수 있다.

5) condvar -> condition을 활용한 lock

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_insert_ordered(&cond->waiters, &waiter.elem, cmp_priority_by_sema , NULL);
	list_push_back(&cond->waiters, &waiter.elem); // 그냥 넣어줘도 됨.
	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)) {
		list_sort(&cond->waiters,cmp_priority_by_sema,NULL); // pop 할때 정렬이 안되어 있을 수 있나?
		sema_up(&list_entry (list_pop_front (&cond->waiters), struct semaphore_elem, elem)->semaphore);
	}
}

cond_wait 및 cond_signal 테스트 코드

Test code에서 cond_wait 의 동작 과정은 아래와 같다.

1. 스레드가 lock 소유권을 획득한다.

2. 이후 cond_wait 에서 Condition 을 위한 세마포어를 따로 생성해줍니다. 해당 세마포어는 생성할 때 부터 0 으로 초기화 되어 cond_signal 을 기다립니다.

3. 그 후, lock 을 해제해주면서( cond의 lock 이 아님을 유의) 다른 스레드 가 1번의 과정을 반복한다. 이 때, lock을 release한 쓰레드는 cond_wait 함수에 진입하여 cond_signal을 기다린다.

Test code에서 cond_signal 의 동작 과정은 아래와 같다.

1. 스레드가 lock 소유권을 획득한다.

2. 이후 cond_signal 함수 에서 cond_wait에서 초기화 한 list를 호출합니다.

3. 그 후, 조건에 맞고 대기중인 thread를 sema_up 을 통해 실행해줍니다.

6) donation

Implement priority donation. You will need to account for all different situations in which priority donation is required. Be sure to handle multiple donations, in which multiple priorities are donated to a single thread. You must also handle nested donation: if H is waiting on a lock that M holds and M is waiting on a lock that L holds, then both M and L should be boosted to H's priority. If necessary, you may impose a reasonable limit on depth of nested priority donation, such as 8 levels.

깃북 가이드에서 multiple donations 와 nested donation 케이스를 고려하여 구현해야 한다고 명시되어 있다.

Nested donation

void
donate(void) {
	struct thread *cur = thread_current();
	for (int i=0; i<8; i++) {
		if (cur->wait_on_lock == NULL) return;
		if (cur->priority > cur->wait_on_lock->holder->priority) {
			cur->wait_on_lock->holder->priority = cur->priority; // priority 변경
			cur = cur->wait_on_lock->holder; // cur = next(cur); 와 비슷한 느낌.
		}else {
			return;
		}
	}
}

donate 함수는 lock_acquired 내에서 만약 얻으려는 lock의 홀더가 있을때 작동한다.

Multiple donation

void 
update_donation() {
	struct thread *cur = thread_current();
	struct list_elem *e;

	int max_priority = 0;
	cur->priority = cur->original_priority;
	if (!list_empty(&cur->donation_list)) {
		list_sort(&cur->donation_list, cmp_priority_by_donation_elem, 0);
		e = list_front(&cur->donation_list);
		struct thread *max = list_entry(e, struct thread, donation_elem);
		max_priority = max->priority;
	}
	// list가 비어있는 경우를 생각해서, 미리 cur->priority = cur->original_priority 를 수행해놔야함.
	if (max_priority > cur->priority) {
		cur->priority = max_priority;
	}
}

update_donation 함수는 lock_release 함수 내에서 donation_list를 갱신한 뒤, 새로운 donation 값을 업데이트 해줍니다.

 

 

이 글은 

김준혁 : https://github.com/JunHyeokDev

김광윤 : https://github.com/leorivk

정승호 : https://github.com/seungho-jg

황연경 : https://github.com/yunnn426

님과 함께 작성했습니다.