• 우선순위 역전이 무엇인가?

  

  • 위 상황에서 B는 LOCK1을 잡고 A의 실행을 대기 중
  • C는 B가 가진 LOCK1이 필요해서 wait-list에 들어감
  • C는 실제로 A보다 우선순위가 높지만, 락이 필요하기 때문에 실행될수가 없음

• 우선순위 기부가 무엇인가?

  

  • C가 자신이 가진 우선순위를 B에게 기부하여 B의 우선순위를 자신과 같게 설정한다. B는 이제 A보다 우선순위가 높아졌으므로 CPU를 선점하게 되고, CPU에서 실행하며 Lock을 놓으면 C가 해당 Lock을 가지게 되어 레디 리스트에서 스케줄링이 될 수 있다.

• 연쇄 기부(chain donate)는 무엇인가?

  

  • 위 상황에서는 C가 B가 가진 Lock 2 를 기다리고 있고, B는 A가 가진 Lock 1을 기다리고 있다. 이 때 레디 리스트 K는 CPU에서 실행중인 A보다 우선순위가 크므로 선점하게 되어 우선순위 역전이 일어나게 된다

  

  • 이 상황에서 C의 우선순위를 B에 기부하게 되고, B가 대기하던 Lock 1을 가진 A에게까지 연쇄적으로 기부가 발생하게 된다

• 중첩 기부는 무엇인가?

  

  • 위 상황에서 B는 C와 D가 필요한 락 두개를 가지고 있다.
  • C와 D 둘다 우선순위 역전이 발생해서 B에게 우선순위를 기부한다

  

  • 둘 중 가장 큰 우선순위인 33을 우선순위로 사용한다.
  • 이후 락을 release할 때, 만약 D가 기다리는 Lock 1이 먼저 해제되었다면, 다음으로 큰 우선순위를 찾아 도네이션 리스트를 순회하여 우선순위로 사용하게 된다.

• 중첩 기부받은 쓰레드 B가 다른 쓰레드 M의 락을 기다리게 되어서 기부하게 될 때 B의 기부 리스트에는 무엇이 들어가야 하는가?

  • 자신의 유효 우선순위 (기부받은 우선순위)를 M에게 넘겨주고, M의 기부 리스트에는 B만 있으면 된다.

작업 코드

thread.h

struct thread

struct thread
{
	/* Owned by thread.c. */
	tid_t tid;				   /* Thread identifier. */
	enum thread_status status; /* Thread state. */
	char name[16];			   /* Name (for debugging purposes). */
	int priority;			   /* 기부받은 우선순위 */
	int original_priority;	   /* 원래의 우선순위 */

	/* Shared between thread.c and synch.c. */
	struct list_elem elem; /* List element. */
	struct list donations; /* 자신한테 기부해준 리스트 */
	struct lock *pending_lock;
}

• original_priority
  • 자신의 실제 우선순위
• donations
  • 자신에게 기부해준 리스트, donation 구조체가 들어간다
• pending_lock
  • 자신이 기다리고 있는 락

struct donation

typedef struct __donation__
{
	struct list_elem elem;
	int priority;
	struct thread *donor;
	struct lock *lock;
} donation;

• priority
  • 기부해준 우선순위
  • 나중에 락을 해제할 때 다른 기부 우선순위를 사용할때 필요
    • donor 안에도 있으므로 굳이 필요하지 않을지도..?
• donor
  • 기부해준 쓰레드
• lock
  • donor가 어떤 락 때문에 기다리기 싫어서 기부해주었는지 확인하는 용도

thread.c

thread_set_priority

void thread_set_priority(int new_priority)
{
	struct thread *cur = thread_current();
	thread_current()->original_priority = new_priority;

	if (list_empty(&cur->donations))
	{
		cur->priority = new_priority;
	}
	else
	{
		int first_priority = list_entry(list_front(&cur->donations), donation, elem)->priority;
		if (first_priority > new_priority)
			cur->priority = first_priority;
		else
			cur->priority = new_priority;
	}

	compare_cur_next_priority();
}