목표

• Priority inversion 상황을 막기 위해 Priority donation 역시 구현해야 한다.
• Prioirity donation 시 발생할 수 있는 multiple donation이나 nested donation 상황도 같이 고려하도록 한다. 특히 nested donation의 경우 그 depth limit을 정해주어야 한다(예를 들면 8 정도).
• 모든 핀토스의 synchronization contructs들에 대해 priority scheduling을 구현한다. 하지만 priority donation은 Lock에 대해서만 구현하면 된다.

현재 상황

Priority Scheduling을 구현한 상태이다. 다시 말해, CPU를 점유하기 위해 대기(READY) 중인 스레드들을 우선순위 내림차순으로 정렬된다. Synchronization constructs들도 마찬가지다. 각 Primitive들은 해당 임계구역을 이용하기 위해 기다리는 waiting list가 있는데, 이 list에 스레드(conditional variable의 경우에는 세마포어)들도 우선순위 내림차순으로 정렬된다.

이런 우선순위 스케줄링에서 발생할 수 있는 문제 중 하나는 바로 Priority Inversion 문제이다. 이는 새로 들어온 스레드 A의 우선 순위가 현재 CPU를 점유하고 있는 스레드 B보다 높고, A가 실행되기 위해서 B가 소유하고 있는 공유 자원이 필요할 때 발생한다. 우선 순위 스케줄링에 따라 B는 block되고 A가 실행되는데, A가 실행되기 위해서는 B가 해당 공유 자원을 반환해야 하기 때문이다.

따라서 이를 해결하기 위해 Priority Donation 방식을 사용하기로 한다. 이 때, semaphore의 경우와는 달리 lock은 현재 lock을 소유하고 있는 스레드를 명시하여 주므로, lock에 대해서만 Donation을 구현하기로 한다.

Priority Donation(Inversion)에서 두 가지 경우를 생각해 주어야 한다. Multiple donation과 Nested donation.

해결 방안

struct thread 수정

struct thread가 우선순위를 donation 받을 수 있도록 수정해준다.

include/threads/thread.h/struct thread

struct thread {
...
/* priority donation */
	int init_priority;

	struct lock *wait_on_lock;

	struct list donations; 	// multiple donation을 위함
	struct list_elem donation_elem;  // multiple donation을 위함
...
}

• init_priority : 우선순위를 donate 받을 때, 자신의 원래 우선순위를 저장할 수 있는 변수
• wait_on_lock : 해당 스레드가 우선순위 inversion 때문에 사용하지 못하고 기다리고 있는 lock 자료구조의 주소.
• multiple donation을 고려하기 위한 리스트
  • donations : 자신에게 priority를 donate한 스레드의 리스트
  • donation_elem : priority를 donate한 스레드들의 리스트를 관리하기 위한 element. 이 element를 통해 자신이 우선 순위를 donate한 스레드의 donations 리스트에 연결된다.

init_thread() 수정 ← struct thread 수정하였으므로.

thread.c/init_thread()