https://poalim.tistory.com/35?category=758538
🛑거의 대부분의 도움을 해당 링크에서 받아왔습니다.

📖Priority Inversion (donation)

---

📑Priority scheduling 에서 Inversion은 왜 발생하고 Donation 왜 필요할까?

---

https://web.eecs.umich.edu/~akamil/teaching/sp04/pri/#fig:inversion

Priority Scheduling 은 프로세스 혹은 쓰레드 중 다음에 무엇이 실행 될 지 scheduling 하기 위해 사용된다.

이를 priority를 기준으로 선정하게 되면 priority scheduling이다. Priority는 thread 구조체에 맴버로 각 쓰레드에 기록된다. thread_ready state 인 thread들이 ready_list에 priority 기준 오름 차순으로 기록되어있다.

• 다음과 같이 ready thread들 A, B, C가 각각 1, 2, 3 priority를 가지고 있다. 참고로 priority는 큰 수 일 수록 우선순위가 높다. 이 경우 schedule 이 진행되면 C thread가 실행된다.

https://web.eecs.umich.edu/~akamil/teaching/sp04/pri/#fig:inversion

📅Priority Inversion

---

priority가 낮은 thread(A or L)이 Key를 들고 있을 때, 실행 중인 thread(H, C)가 key를 요청하는 경우, key가 다른 thread에게 종속되어있기에 key가 반환 될 때까지 thread(H, C)는 Blocked state로 들어가고, 그 후 schedule에 의해 다음 priority 인 thread(B, M)이 실행되는데, 이 상황이 Priority inversion이다. Priority가 높은 thread(H, L)이 멀쩡히 있는데 priority가 상대적으로 낮은 thread(B, M)이 실행되는 Inversion 이다.

thread 들은 한 프로세스 안에서 생성되는 여러개의 실행 흐름인데 이들은 프로세스에 할당된 메모리 공간을 공유한다. 이때 서로 동시에 한 자원을 건드릴 경우 문제가 생긴다. 이를 제어하기 위해 semaphore/lock/conditional variable등을 이용한다.

https://renelemon.tistory.com/99?category=950734

📅Priority Donation

위와 같은 Inversion case를 해결하기 위해 priority donation 기능을 만들자.

Priority Donation은 key holder thread에게 lock을 요청하고 있는 thread의 priority를 donate해주어 donate 받은 thread가 실행되어 lock을 release 해줄 때까지 실행 될 수 있게 해준다.

발생할 수 있는 특수 상황

🚸Multiple Donation

---

스레드, 락 구조체를 도식화해보면 아래 그림과 같다.

단어에서 알 수 있듯이 여러번의 donation 이 일어난 상황이라고 볼 수 있다. 위의 예시에서 L 가 lock A, lock B 라는 두 가지 lock 을 점유하고 있다고 해보자. H 가 lock A 를, M 이 lock B 를 각각 요청하였을 때, L 은 자신이 가지고 있는 lock 을 요청한 모든 스레드에게 priority 를 양도받고, 이 중 가장 높은 priority 를 일시적으로 자신의 priority 로 갖는다. 그림으로 보면 아래와 같다.

🚸Nested Donation

---

이 상황에서 스레드, 락 구조체를 도식화해보면 아래 그림과 같다.

그림에서 볼 수 있듯이 H 가 lock B 를 얻기 위해 M 에게 priority donation 을 행하고 M 은 lock A 를 얻기 위해 L 에게 priority donation 을 행하는 것 처럼, 여러번의 단계적 donation 이 일어나는 상황이다.

이때 donation은 H부터 발생해서 M, L 모두 H의 priority를 donate 받아 순차적으로 lock을 해소해 thread H가 정상적으로 lock을 accquire 할 수 있게 해준다.

✅구현

---

💻thread.h, .c

---

struct thread

Priority donation을 위해 thread.h의 thread 구조체에 추가적인 맴버를 선언해준다.

	...
		/* priority donation */
	/* priority를 양도 받고 반환하고나서 원래 priority를 복원하기 위해 기록*/
	int init_priority; 
	/* thread가 현재 얻기 위해 기다리고 있는 lock의 주소로 스레드는 이 lock 이 release 되기를 기다린다. */
	struct lock *wait_on_lock; 
	/* 자신에게 priority 를 나누어준 thread들의 리스트이고 */
	struct list donations; 
	 /*  donations 리스트를 관리하기 위한 element 로 thread 구조체의 그냥 elem 과 구분하여 사용하도록 한다. */
	struct list_elem donation_elem;
	...

새롭게 추가된 맴버들인 만큼 초기화 시켜줘야한다. init_thread() 에서.

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

🔰donate_priority()

---

이 함수는 자신의 priority 를 필요한 lock 을 점유하고 있는 스레드에게 빌려주는 함수이다. 한 가지 주의할 점은, nested donation 에서 살펴본 것처럼 하위에 연결된 모든 스레드에 donation 이 일어난다는 것이다.

void
donate_priority (void) {
    int depth;
    struct thread *cur = thread_current ();

	/* Nested donation 상황을 대비해 for문을 돌린다 */
    for (depth = 0; depth < 8; depth++){
		/* lock을 얻기 기다리는 thread가 아닐 경우 break한다. */
		if (!cur->wait_on_lock) break;
		/* 일 경우 최상위 priority를 donate 해준다. */
		struct thread *holder = cur->wait_on_lock->holder;
		holder->priority = cur->priority;
		cur = holder;
    }
}

🔰remove_with_lock()

donations 리스트를 순회하며 현재 thread에게 priority를 빌려준 thread들을
donation 리스트에서 제거해주는 함수. 다만 현재 release하고 있는 lock 때문에
donate한 thread만 해당된다.

---

/* thread/thread.c */
/* donations 리스트를 순회하며 현재 thread에게 priority를 빌려준 thread들을
	donation 리스트에서 제거해주는 함수. 다만 현재 release하고 있는 lock 때문에
	donate한 thread만 해당된다. */
void
remove_with_lock (struct lock *lock) {
    struct list_elem *e;
    struct thread *cur = thread_current ();

	/* donation 리스트를 순회하며 */
    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);
		/* 인자로 받은 lock을 원해서 donate를 한 경우라면 */
		if (t->wait_on_lock == lock)
			list_remove (&t->donation_elem);
    }
}

donation 리스트를 순회하는 경우는 nested donation이 발생한 경우 때문이다.

🔰refresh_priority()

---

현재 thread의 priority를 원래대로 복구시키거나, 아직 donations 리스트가 비어있지 않다면
(아직 나에게 priority를 빌려준 thread들이 남아잇다면) 그중 가장 높은 priority로 재설정.

/* thread/thread.c */
/* 현재 thread의 priority를 원래대로 복구시키거나, 아직 donations 리스트가 비어있지 않다면
	(아직 나에게 priority를 빌려준 thread들이 남아잇다면) 그중 가장 높은 priority로 재설정. */
void
refresh_priority (void) {
    struct thread *cur = thread_current ();

    cur->priority = cur->init_priority;

	/* donate 받은 priority가 아직 남아있다면 */
    if (!list_empty (&cur->donations)) {
		list_sort (&cur->donations, thread_compare_donate_priority, 0);

		/* 그중 가장 높은  priority를 현재 thread의 priority로 설정 */
    	struct thread *front = list_entry (list_front (&cur->donations), struct thread, donation_elem);
		if (front->priority > cur->priority)
			cur->priority = front->priority;
    }
}

💻synch.c

---

🔰lock_acquire()

---

lock을 받아오는, 요청하는 함수입니다. 다른 thread가 key를 보유중일 경우 lock을 받아올 수 있을 때까지 (key가 release 될 때까지) thread를 sleep/block 시킵니다.

donate_priority()가 사용되었습니다.

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

	/* ==================== project1 Priority Donation ==================== */
	struct thread *cur = thread_current();

	/* 위에서 lock이 현재 thread에게 있는지를 이미 assert했기에 holder가 있다면 다른 thread다.
		따라서 donation을 통해 lock holder thread가 실행될 수 있게 해준다. */
	if (lock->holder) {
		cur->wait_on_lock = lock;
		/* lock holder의 donation 리스트에 현재 thread를 기록해준다. Priority 순으로 */
		list_insert_ordered(&lock->holder->donations, &cur->donation_elem, 
						thread_compare_donate_priority, NULL);
		donate_priority();
	}
	
	sema_down (&lock->semaphore);
	cur->wait_on_lock = NULL;
	lock->holder = cur;
	/* ============

🔰lock_release()

현재 thread가 들고 있는 lock을 반환하는 함수.

remove_with_lock(), refresh_priority가 사용되었습니다.

---

/* Releases LOCK, which must be owned by the current thread.
   This is lock_release function.

   An interrupt handler cannot acquire a lock, so it does not
   make sense to try to release a lock within an interrupt
   handler. */
void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock));

	/* ==================== project1 Priority Donation ==================== */
    remove_with_lock (lock);
    refresh_priority ();	
	/* ==================== project1 Priority Donation ==================== */

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

🚸extra case / thread_set_priority()

---

현재 thread가 lock, donation과 관계없이 thread_set_priority 함수를 호출함으로 자신의 priority가 변경될 수 있다. 이 경우 필히 init_priority즉 원본 priority를 갱신해주어야한다. 또한 donations 리스트들에 있는 스레드들보다 priority 가 높아지는 경우가 생길 수 있다. 이 경우 priority 는 donations 리스트 중 가장 높은 priority 가 아니라 새로 바뀐 priority 가 적용될 수 있게 해야 한다.

/* thread/thread.c */
/* Sets the current thread's priority to NEW_PRIORITY. */
void
thread_set_priority (int new_priority) {
	/* ==================== project1 Prioirity Scheduling ==================== */
    thread_current ()->init_priority = new_priority;
    // thread_current ()->priority = new_priority;
	refresh_priority ();
	test_max_priority();
	/* ==================== project1 Prioirity Scheduling ==================== */
}

condition variable

---

https://firecatlibrary.tistory.com/58?category=875424

💯

pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
pass tests/threads/priority-donate-one
pass tests/threads/priority-donate-multiple
pass tests/threads/priority-donate-multiple2
pass tests/threads/priority-donate-nest
pass tests/threads/priority-donate-sema
pass tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
pass tests/threads/priority-donate-chain
FAIL tests/threads/mlfqs/mlfqs-load-1
FAIL tests/threads/mlfqs/mlfqs-load-60
FAIL tests/threads/mlfqs/mlfqs-load-avg
FAIL tests/threads/mlfqs/mlfqs-recent-1
pass tests/threads/mlfqs/mlfqs-fair-2
pass tests/threads/mlfqs/mlfqs-fair-20
FAIL tests/threads/mlfqs/mlfqs-nice-2
FAIL tests/threads/mlfqs/mlfqs-nice-10
FAIL tests/threads/mlfqs/mlfqs-block
7 of 27 tests failed.