[정글] PintOS Project1 #3 Priority Scheduling 2/2

[정글] PintOS Project1 #2 Priority Scheduling 1/2 은 여기에 정리

 

Priority Inversion 

Priority Inversion 은 H (High), M (Middle), L (Low) 라는 세 개의 쓰레드가 있고, 각각의 우선순위는 H > M > L 일 때 
H 가 L 을 기다리고 있는 상황 (L이 Lock을 점유하고 있는 상황에서 H가 Lock을 요청한 상황) 에서 
H 가 L 에게 CPU 점유권을 넘겨주면, M 이 L 보다 우선순위가 높으므로 점유권을 선점하여 실행되기 때문에 
Thread 가 마무리되는 순서가 M -> L -> H 가 되어 M 이 H 보다 우선하여 실행되는 현상이다 

이런 문제를 해결하기 위해 Priority Donation 을 구현해야 한다, 아까와 같은 상황에서 H 가 자신이 가진 Priority 를
L 에게 일시적으로 양도해서 (H 자신의 실행을 위해) L 이 우선적으로 실행될 수 있도록 만드는 방법이다 

우리는 Multiple Donation 과 Nested Donation 을 구현할 예정이다

Multiple Donation

아까와 같은 상황에서 L 가 Lock A 와 Lock B 두 가지 Lock 을 점유하고 있다고 가정했을 때
M 이 Lock A 를, H 가 Lock B 를 각각 요청한다면 L 은 (자신이 가지고 있는) Lock 을 요청한 모든 Thread 들에게 Priority 를 양도 받고, 이 중 가장 높은 Priority 를, 일시적으로 자신의 Priority 를 가진다 
M 과 H 중에 더 높은 H 의 Priority 를 가질 수 있다 
Multiple Donation 은 아래와 같은 Data Structure 를 가진다 

Nested Donation 

Donation 은 재귀적으로 이어진다
T1 이 점유한 Lock A 를 T2 가 요청했을 떄, T2 Piority > T1 Priority 라면 T1 이 T2 Priority 로 갱신한다 
아래 그림처럼 Chained Lock Holding Relationship 인 경우 제일 높은 Prioirty 가 재귀적으로 Donate 된다 

Nested Donation 의 Data Structure 는 아래와 같다 

Multiple Donation 구현하기 

 Thread 들이 양도 받은 내역을 관리할 수 있도록 Donation 구조체들을 Thread Struct 에 추가해줬다 

/* Path - threads/thread.h */ 
struct thread {
	...
	int init_priority;  /* 원래의 Prioirty 를 저장하는 변수 */

	struct lock *wait_on_lock; /* Thread 가 현재 얻기 위해 기다리고 있는 Lock */
	struct list donations; /* 자신에게 Priority 를 나누어준 Threads List */
	struct list_elem donation_elem; /* Donation List 관리하는 Element*/
	...
}

init_priority - Priority 를 양도 받았다가 다시 반납할 때 원래의 Priority 를 복원할 수 있도록 원래의 Priority 를 저장하는 변수 
wait_on_lock - Thread 가 현재 얻기 위해 기다리고 있는 Lock 
donations - 자신에게 Priority 를 나누어준 Thread 들의 List 
donation_elem - donations 를 관리하기 위한 element 

/* Path - threads/thread.c */
static void
init_thread (struct thread *t, const char *name, int priority) {
	...
	t->init_priority = priority; /* priority Init */
	t->wait_on_lock = NULL; /* Wait on lock Init */
	list_init(&t->donations); /* Donation Init */
    ...
}

struct thread() 에서 넣어줬던 요소들을 init_thread() 에서 초기화시켜준다 

lock_acquire (stuct lock *lock) 기존 방식 

Thread 가 Lock 을 요청하면 lock_acquire() 함수가 실행된다, 누군가 Lock 을 점유하고 있는 상테라면 Priority 를 양도하여 Lock 을 점유 중인 Thread 가 우선적으로 Lock 을 반환하도록 해야한다 

/* Path - threads/synch.c */
/* lock_acquire 는 sema_down 에 의해 Lock 을 기다리는 동안 Blocking 된다 */
void
lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL); /* Lock 이 NULL 이 아닌지 확인 */
	ASSERT (!intr_context ()); /* 인터럽트 컨텍스트가 아닌지 확인 */
	/* 현재 Thread 가 이미 이 Lock 을 가지고 있지 않은지 확인 */
	ASSERT (!lock_held_by_current_thread (lock));

	/* Semaphore 를 감소시키며 Lock 을 획득하려 시도 */
	sema_down (&lock->semaphore);
	/* Lock 획득한 후 현재 Thread 를 Lock 소유자로 설정 */
	lock->holder = thread_current ();
}

sema_down 으로 Lock 을 획득하려고 시도하고, Lock 획득 후 현재 Thread 를 Lock 소유자로 결정한다 
sema_down 전에 Lock 을 가지고 있는 Thread 에게 Priority 를 양도하는 작업을 구현해야 한다 
먼저, list_inserted_ordered 를 사용하기 위해 thread_compare_donate_priority() 함수를 만들었다 
thread.h 에 함수원형을 넣어주는 것도 잊지 않아야 한다 

thread_compare_donate_priority()

/* Path - threads/thread.c
/* Thread 의 Priority 를 비교하는 함수 */
bool thread_compare_priority (struct list_elem *l, struct list_elem *s, void *aux UNUSED) {
	struct thread *t1 = list_entry(l, struct thread, elem);
	struct thread *t2 = list_entry(s, struct thread, elem);
	return t1->priority > t2->priority;
}

lock_acquire(struct lock *lock) 개선 방식 

주석에 달아놓은 것처럼, lock->holder 가 있다면 (Lock 을 점유하고 있는 Thread 가 있다면)
현재 Thread 는 대기 상태이고 그 Thread 에게 Priority 를 Donation 해주어야 한다
그렇기 위해서는 아래와 같은 단계를 밟아야 한다 
1. wait_to_lock 에 기다리고 있는 Lock 을 추가하고 
2. holder 의 donations List 에 현재 Thread 를 추가하고
3. Priority Donation 을 실행한다 

/* Path - threads/synch.c */
/* lock_acquire 는 sema_down 에 의해 Lock 을 기다리는 동안 Blocking 된다 */
void
lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL); /* Lock 이 NULL 이 아닌지 확인 */
	ASSERT (!intr_context ()); /* 인터럽트 컨텍스트가 아닌지 확인 */
	/* 현재 Thread 가 이미 이 Lock 을 가지고 있지 않은지 확인 */
	ASSERT (!lock_held_by_current_thread (lock));

	struct thread *cur = thread_current();
	/* Lock 을 점유하고 있는 Thread 가 있다면, 현재 Thread 는 대기 상태가 된다
	현재 Thread 의 wait_to_lock 에 Lock 을 설정하고
	donation_elem 기준으로 삽입하여 정렬하고, Priority 를 Donation 한다 */
	if (lock->holder) {
		cur->wait_on_lock = lock; 
		list_insert_ordered(&lock->holder->donations, &cur->donation_elem,
		thread_compare_donate_priority, 0);
		donate_priority();
	}

	/* Semaphore 를 감소시키며 Lock 을 획득하려 시도 */
	sema_down (&lock->semaphore);
	/* Lock 획득한 후 현재 Thread 를 Lock 소유자로 설정 */
	lock->holder = thread_current ();
}

donate_priority() 만들기 

현재 Thread 가 원하는 Lock 을 가진 Holder 에게 현재 Thread 의 Priority 를 Donate 하는 함수이다 
무한 루프를 방지하기 위해 Nested 의 Detph 를 8까지만 지정해줬다 
wait_on_lock == NULL 이라면 (기다리는 Thread 없음) 더 이상 Donation 을 할 필요 없으므로 break 한다 
Holder 가 있는 Lock 에게 요청을 한다는 것은, 현재 Thread 가 Holder 보다 Priority 가 높다는 것이므로 
Priority 를 비교할 필요 없이 Holder 가 존재한다면 Priority 를 바꿔주면 된다 

/* Path - threads/thread.c */
/* 현재 Thread 의 Priority 를 Nested 로 Donation 하는 함수 */
void donate_priority (void) {
	int depth; /* Priority Donation 의 Nested 깊이 설정 */
	struct thread *cur = thread_current();

	for (depth=0; depth<8; depth++){ /* Depth 8까지만 Donation 진행 */
		if(!cur->wait_on_lock) break; /* wait_on_lock 이 없으면 break */
		struct thread *holder = cur->wait_on_lock->holder;
		holder->priority = cur->priority; /* 현재 Priority Donation */
		cur = holder; /* Holder 가 다음 Donor 가 되어 Priority 전달 */
	}
}

lock_release (struct lock *lock) 기존 방식 

Thread 가 Priority 를 양도 받아서 Critical Section 을 마치고 Lock 을 반환할 때의 경우를 만들어주어야 한다 
기존 방식은 lock->holder 를 NULL 로 만들어 주고 sema_up 을 해준다 
sema_up 으로 Lock 을 반환하기 전에 Lock Donor 들을 List 에서 제거하고 Priority 를 재설정해주어야 한다 

/* Path - threads/synch.c */
void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL); /* Lock 이 NULL 이 아닌지 확인 */
	/* 현재 Thread 가 이미 이 Lock 을 가지고 있는지 확인 */
	/* 다른 함수들과 달리 ! 가 없음, Lock 을 가지고 있어야 Release 할 수 있다 */
	ASSERT (lock_held_by_current_thread (lock));

	remove_with_lock (lock);
	refresh_priority ();

	lock->holder = NULL; /* Lock 이 가지고 있는 Thread 해제 */
	sema_up (&lock->semaphore);
}

 

remove_with_lock (struct lock *lock) 만들기 

우선, donations List 에서 Thread 를 지우는 함수를 만든다
cur->donations List 를 돌면서 wait_on_lock 이 현재 Release 하려는 Lock 이라면 해당 Thread 를 List 에서 제거한다 

/* Path - threads/thread.c */
/* Lock 을 삭제하면서 Lock 의 Donor 를 지우는 함수 */
void remove_with_lock (struct lock *lock) {
	struct list_elem *e;
	struct thread *cur = thread_current();

	/* cur->donations List 를 돌면서 wait_on_lock 이  
	이번에 Release 하는 Lock 이라면 해당 Thread 를 List 에서 제거한다 */
	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);		
	}
}

refresh_priority (void) 만들기 

Priority 를 재설정할 때 donations List 가 비어 있다면 init_priority 로 설정하고 
List 가 비어 있지 않다면 list_sort 를 이용하여 남아 있는 Thread 중에서 가장 높은 Priority 를 찾는다 
그렇게 찾은 Priority 와 init 을 비교하여 큰 Priority 를 적용한다 
아래에서부터 여기 참고해서 다시 수정하기 

/* Path - threads/thread.c */
/* Lock 을 삭제하면서 priority Refresh 하는 함수 */
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_release() 개선 구현

Lock 이 가지고 있는 Thread 를 해제하기 전에 Priority Donor 을 제거하고 Priority 를 Refresh 해주는 함수를 추가한다 

/* Path - threads/synch.c */
void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL); /* Lock 이 NULL 이 아닌지 확인 */
	/* 현재 Thread 가 이미 이 Lock 을 가지고 있는지 확인 */
	/* 다른 함수들과 달리 ! 가 없음, Lock 을 가지고 있어야 Release 할 수 있다 */
	ASSERT (lock_held_by_current_thread (lock));

	remove_with_lock (lock);
	refresh_priority ();

	lock->holder = NULL; /* Lock 이 가지고 있는 Thread 해제 */
	sema_up (&lock->semaphore);
}

그리고 마지막으로, Running Thread 의 Priority 가 변경되는 상황이 종종 발생하기 때문에 
Donations List 의 Priority 를 재설정하는 함수를 thread_set_priority() 함수에 추가해 준다 

thread_set_priority() 개선

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

	refresh_priority (); /* Priority 재설정 */
	preempt_priority(); /* CPU 양보 함수 추가 */
}

결과는,

앞에 PASS 였던 항목들 중에서 몇 개는 FAIL 이 났다
최적화는 담에 시간 나면 진행하려고 하는데 정글에 있는 동안은 못 하겠지?

그래도 make check 하면서 오탈자도 많이 수정했는데 그건 다시 업데이트 해야겠다
어찌저찌 Donation 까지 구현(?)은 했다,....!

멘붕 온 나를 도와주고 위로해준 ㅇㅈ ㄷㅇ ㅎㅇ 고맙습니다 🫡🫡
Advanced Scheduler 못 한 건 아쉽지만 Priority Scheduling 은 어찌됐건 끝내서 조금은 위안이 된다

점점 칭구들의 표정이 어두워지고 건강이 안 좋아진다
다들 힘냅시다~~~~!