[pintos] Week1: Priority Scheduling - Part.3

이전 포스팅에서는 세마포어와 조건 변수에 대한 수정을 진행했다. 이번 포스팅에서는 우선순위 기부기능을 구현하는 것을 목표로 한다.

2025.05.12 - [분류 전체보기] - [pintos] Week1: Priority Scheduling - Part.2

[pintos] Week1: Priority Scheduling - Part.2

---

구현 요구사항 설명

의존관계 역전

우선순위가 높은 스레드가 우선순위가 낮은 스레드를 기다리는 상황이다.

2025.05.10 - [크래프톤 정글] - [pintos] 우선순위 역전과 우선순위 기부

[pintos] 우선순위 역전과 우선순위 기부

우리는 이런 의존관계 역전 현상을 방지 혹은 해결하기 위해 우선순위 기부라는 기법을 이용할 것이다.

---

구현 목표

• 잠금 보유자에게 우선 순위를 상속한다.

pintos에서는 Nested Donation과 Multiple Donation 현상을 모두 고려해야 한다.

1. Nested Dondation

• Donation은 재귀적으로 이어진다.
  • T1이 점유한 lockA를 T2가 요청하면 (T2가 더 높을 경우) T2의 priority로 갱신한다.
  • 위 상황에서, T2가 점유한 lockB를 T3이 요청하면 (T3이 더 높을 경우) T1과 T2를 T3의 priority로 갱신한다.

2. Multiple Donation

• lock을 여러 개 점유한 스레드는 lock을 요청한 스레드의 priority 중 가장 높은 priority로 갱신한다.
• lock을 반환할 경우에는, 반환한 lock을 획득한 스레드를 제외한 lock을 요청한 스레드들의 priority 중에서 가장 높은 priority로 갱신한다.

---

구현

1. thread 구조체에 priority donation 관련 항목 추가

• include/threads/thread.h

.
.
.
/* Priority Donation Field */
int init_priority; /* 원래 우선순위 */
struct list donations; /* 이 스레드에게 우선순위를 기부한 스레드의 목록 */
struct list_elem donations_elem; /* 다른 스레드의 donations 리스트에 포함되기 위한 요소 */
struct lock *wait_on_lock; /* 이 스레드가 기다리고 있는 락 */
.
.
.

---

2. init_thread() 함수 수정

• threads/thread.c

static void
init_thread (struct thread *t, const char *name, int priority) {
	ASSERT (t != NULL);
	ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
	ASSERT (name != NULL);

	memset (t, 0, sizeof *t);
	t->status = THREAD_BLOCKED;
	strlcpy (t->name, name, sizeof t->name);
	t->tf.rsp = (uint64_t) t + PGSIZE - sizeof (void *);
	t->priority = t->init_priority = priority;
	t->magic = THREAD_MAGIC;

	list_init(&t->donations);
	t->wait_on_lock = NULL;
}

• priority donation 관련 초기화 코드 적용

---

3. lock_acuire() 함수 수정

• threads/synch.c

• 잠금을 사용할 수 없는 경우 잠금 주소를 저장한다.
• 현재 우선순위를 저장하고 기부된 스레드를 목록에 유지한다(다중 기부).
• Donate priority

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

	struct thread *t = thread_current();
	if (lock->holder != NULL){ // 이미 락이 점유된 경우
		t->wait_on_lock = lock;
		// 우선순위 순으로 정렬하여 삽입
		list_push_back(&lock->holder->donations, &t->donations_elem);
		donation_priority();
	}

	sema_down(&lock->semaphore);
    lock->holder = t;
    t->wait_on_lock = NULL;
}

• 현재 스레드(t)가 이 락을 기다리고 있음을 기록한다. t->wait_on_lock = lock;
• 락을 소유한 스레드의 donations 리스트에 현재 스레드를 추가한다.
• donation_priority() 함수를 호출하여, 현재 스레드의 우선순위가 락을 소유한 스레드보다 높으면 우선순위 기부가 일어나도록 한다.
• 락의 소유자를 현재 스레드로 설정한다: lock->holder = t;
• 현재 스레드가 더 이상 락을 기다리지 않음을 표시한다: t->wait_on_lock = NULL;

---

4. lock_release() 함수 수정

• threads/synch.c

void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock));

	lock->holder = NULL;

	// 우선순위 기부 반환: donations 리스트에서 해당 락을 기다리던 스레드 제거
	remove_with_lock(lock);
	refresh_priority();

	sema_up (&lock->semaphore);
}

• lock을 해제한 후, 현재 쓰레드의 대기 리스트 갱신 (remove_with_lock() 사용)
• priority를 donation 받았을 수 있으므로 원래의 priorit로 초기화 (refresh_priority() 사용)

---

5. thread_set_priority() 함수 수정

• threads/thread.c

// 우선 순위 변경 -> 우선순위에 따라 선점 
void thread_set_priority (int new_priority) {
    thread_current ()->priority = new_priority;
	/* 현재 스레드의 원래 우선순위를 설정한다. */
	thread_current()->init_priority = new_priority;

	/* 우선순위를 재 계산한다.  */
	refresh_priority();

	/* 우선순위에 따른 스케줄링 진행 */
	cmp_nowNfirst();
}

• refresh_priority() 함수를 사용하여 우선순위의 변경으로 인한 donation 관련 정보를 갱신
• donation_priority(), test_max_priority() 함수를 적절히 사용하여 priority donation을 수행하고 스케줄링

---

6. 추가 함수 구현

thread.h에 구현할 함수 선언

.
.
void donation_priority(void);
void remove_with_lock(struct lock *lock);
void refresh_priority(void);
.
.

donation_priority() 함수 추가

• threads/.c

void donation_priority(void) {
    struct thread *t = thread_current();
	int priority = t->priority;
    int depth = 0;

	for (int depth = 0; depth < 8; depth++) 
	{
        if (t->wait_on_lock == NULL)
            break;
        t = t->wait_on_lock->holder;
        t->priority = priority;
    }
}

• 현재 실행 중인 스레드(t)를 가져오고, 그 스레드의 우선순위를 priority에 저장한다.
• 최대 8번 반복(중첩 기부 깊이 제한, 무한 루프 방지)
• 각 반복에서 다음을 수행한다:
  • 현재 스레드(t)가 기다리고 있는 락(wait_on_lock)이 없다면(즉, 더 이상 기부할 대상이 없으면) 반복 종료.
  • 락을 소유한 스레드(t->wait_on_lock->holder)를 가져와 t로 갱신.
  • 락 소유자의 우선순위를 현재 스레드의 우선순위로 강제로 덮어씀.
• 예시
  • A(우선순위 30)가 락을 점유, B(40)가 기다림, C(50)가 B가 점유한 다른 락을 기다림.
  • C가 락을 기다리면, C(50) → B(40) → A(30) 순으로 우선순위가 50으로 전파됨.

---

remove_with_lock() 함수 추가

• threads/thread.c

void remove_with_lock(struct lock *lock){
	struct thread *t = thread_current();
    struct list_elem *curr = list_begin(&t->donations);
    struct thread *curr_thread = NULL;

	while (curr != list_end(&t->donations)) 
	{
        curr_thread = list_entry(curr, struct thread, donations_elem);

        if (curr_thread->wait_on_lock == lock)
            list_remove(&curr_thread->donations_elem);

        curr = list_next(curr);
    }
}

remove_with_lock 함수는 우선순위 기부(priority donation) 메커니즘에서 특정 락(lock)을 기다리던 스레드에 대한 기부 정보를 제거하는 역할을 한다.

• 현재 실행 중인 스레드(t)의 donations 리스트의 첫 번째 요소(curr)부터 시작한다.
• 리스트의 끝까지 반복하며 다음을 수행한다:
  • curr_thread는 현재 donations 리스트 요소에 해당하는 스레드다.
  • 만약 curr_thread가 현재 해제하려는 락(lock)을 기다리고 있다면:
    • 해당 스레드를 donations 리스트에서 제거한다.
  • 다음 요소로 이동한다.
• 예시
  • 스레드 A가 락 L을 점유하고 있고, 스레드 B와 C가 L을 기다리며 A에게 우선순위를 기부한 상태라고 가정.
  • A가 L을 해제할 때, B와 C가 더 이상 A에게 우선순위를 기부할 필요가 없음.
  • 이 함수가 호출되어, A의 donations 리스트에서 "L을 기다리던" B와 C를 제거함.

---

refresh_priority() 함수 추가

• threads/thread.c

void refresh_priority(void){
	struct thread *t = thread_current();
    t->priority = t->init_priority;

    if (list_empty(&t->donations))
        return;

    list_sort(&t->donations, cmp_priority, NULL);

    struct list_elem *max_elem = list_front(&t->donations);
    struct thread *max_thread = list_entry(max_elem, struct thread, donations_elem);

    if (t->priority < max_thread->priority)
        t->priority = max_thread->priority;
}

• refresh_priority 함수는 우선순위 기부(priority donation) 메커니즘에서 스레드의 우선순위를 적절히 복원하는 역할을 한다.
• 이 함수는 주로 락(lock)을 해제한 후에 호출되어, 스레드의 우선순위를 다음 중 더 높은 값으로 설정한다:

1. 원래 가지고 있던 기본 우선순위(init_priority)
2. 여전히 남아있는 우선순위 기부자들 중 가장 높은 우선순위

• 현재 실행 중인 스레드(t)의 우선순위를 기본 우선순위(init_priority)로 초기화
• 만약 donations 리스트가 비어있다면(기부자가 없다면) 함수를 종료한다.
• 우선순위에 따라 donations 리스트를 정렬한다. 이는 가장 높은 우선순위의 기부자를 쉽게 찾기 위함이다.
• 정렬된 리스트의 첫 번째 요소(가장 높은 우선순위)를 가져온다.
• 만약 최고 우선순위 기부자의 우선순위가 현재 스레드의 기본 우선순위보다 높다면, 현재 스레드의 우선순위를 그 값으로 갱신한다.
• 예시
  • 스레드 A(기본 우선순위 20)가 락 L1과 L2를 점유하고 있고,
  • 스레드 B(우선순위 40)가 L1을 기다리며 A에게 우선순위를 기부,
  • 스레드 C(우선순위 30)가 L2를 기다리며 A에게 우선순위를 기부한 상태.
  • A가 L1을 해제하면, B의 기부는 제거되지만 C의 기부는 여전히 유효.
  • refresh_priority 호출 시:
    • A의 우선순위는 먼저 20(기본값)으로 복원됨
    • donations 리스트에서 C(30)가 가장 높은 우선순위
    • A의 우선순위는 30으로 설정됨

---

테스트 실행

• donate-one
• donate-multiple
• donate-multiple2
• donate-nest
• donate-chain
• donate-lower

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.
../../tests/Make.tests:28: recipe for target 'check' failed
make: *** [check] Error 1

---

참고

[Pintos-KAIST] Project 1 : Priority Donation