[pintos] Week1: Priority Scheduling - Part.2

이 전 포스팅에서는 우선순위에 따라 선점을 하는 기능을 구현했다. 이번 포스팅에서는 세마포어, 조건 변수에 따른 Lock 기능을 구현해 보겠다.

2025.05.12 - [크래프톤 정글] - [pintos] Week1: Priority Scheduling - Part.1

[pintos] Week1: Priority Scheduling - Part.1

---

구현 요구사항 설명

• 잠금(또는 조건 변수)을 기다리는 스레드 집합에서 스레드의 우선순위에 따라 대기 중인 스레드를 깨운다.

현재 pintos는 잠금은 우선순위를 무시하고 대기자 목록에서 FIFO 순서로 획득하고 있다.

수정 전

우리가 수행해야 하는 기능은 스레드가 세마포어를 획득하려고 할 때 waiterslist를 우선순위 순으로 정렬하는 것이다.

수정 후

---

구현 목표

• sema_down() / cond_wait() 수정

1. sema_down() 함수 수정

• Semaphore를 얻고 waiters 리스트 삽입 시, 우선순위대로 삽입되도록 수정

2. sema_up() 함수 수정

• waiter list에 있는 스레드의 우선순위가 변경되었을 경우를 고려하여 waiter list를 정렬 (list_sort)
  세마포어 해제 후 priority preemption 기능 추가

---

구현

1. sema_down() 함수 수정

• 세마포어를 요청한다. 세마포어를 획득했다면 값을 1 감소시킨다.

void
sema_down (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);
	ASSERT (!intr_context ());

	old_level = intr_disable ();
	while (sema->value == 0) {
		
		// list_push_back (&sema->waiters, &thread_current ()->elem);
		list_insert_ordered(&sema->waiters, &thread_current()->elem, 
                           &cmp_priority, NULL);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

---

2. sema_up() 함수 수정

• 세마포어를 해제하고 값을 1만큼 증가시킨다.
• waiter list에 있는 쓰레드의 우선순위가 변경되었을 경우를 고려하여 waiter list를 정렬 (list_sort)
• 세마포어 해제 후 priority preemption 기능 추가

void
sema_up (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (!list_empty (&sema->waiters)){
		/* 세마포어 대기자 목록을 정렬한다. */
		list_sort(&sema->waiters, cmp_priority, NULL);
        thread_unblock(list_entry(list_pop_front(&sema->waiters), struct thread, elem));
	}
	sema->value++;
	/* 우선순위를 비교해 더 높은 우선순위를 가진 스레드에게 스레드를 넘긴다. */
	cmp_nowNfirst();
	intr_set_level (old_level);
}

---

3. cond_wait() 함수 수정

• 조건 변수에 의한 신호를 기다린다.
• condition variable의 waiters list에 우선순위 순서로 삽입되도록 수정한다.

void
cond_wait (struct condition *cond, struct lock *lock) {
	struct semaphore_elem waiter;

	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	sema_init (&waiter.semaphore, 0);
	//list_push_back (&cond->waiters, &waiter.elem);
	list_insert_ordered(&cond->waiters, &waiter.elem, cmp_sem_priority, NULL);

	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}

---

4. cond_signal() 함수 수정

• condition variable의 waiters list를 우선순위로 재 정렬
• 대기 중에 우선순위가 변경되었을 가능성이 있음

void
cond_signal (struct condition *cond, struct lock *lock UNUSED) {
	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	if (!list_empty (&cond->waiters))
		/* 세마포어의 watier list내에 스레드들의 우선순위에 따라 정렬한다. */	
	    list_sort(&cond->waiters, cmp_sem_priority, NULL);
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
}

---

5. 추가 함수 구현

• threads/thread.c

thread.c 상위에 구현할 함수 선언

bool cmp_sem_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED);

cmp_sem_priority() 함수 추가

bool cmp_sem_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
    struct semaphore_elem *sema_a = list_entry(a, struct semaphore_elem, elem);
    struct semaphore_elem *sema_b = list_entry(b, struct semaphore_elem, elem);

    if (sema_a == NULL || sema_b == NULL)
        return false;

    struct list *list_a = &(sema_a->semaphore.waiters);
    struct list *list_b = &(sema_b->semaphore.waiters);

    if (list_a == NULL || list_b == NULL)
        return false;

    struct thread *thread_a = list_entry(list_begin(list_a), struct thread, elem);
    struct thread *thread_b = list_entry(list_begin(list_b), struct thread, elem);

    if (thread_a == NULL || thread_b == NULL)
        return false;

    return thread_a->priority > thread_b->priority;
}

• cmp_sem_priority 함수는 조건 변수(condition variable)의 대기자 목록에서 세마포어 요소들을 우선순위에 따라 비교하는 함수다.

---

테스트 실행

• priority-sema
• priority-condvar

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
FAIL tests/threads/priority-change
FAIL tests/threads/priority-donate-one
FAIL tests/threads/priority-donate-multiple
FAIL tests/threads/priority-donate-multiple2
FAIL tests/threads/priority-donate-nest
FAIL tests/threads/priority-donate-sema
FAIL 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
FAIL 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
15 of 27 tests failed.
../../tests/Make.tests:28: recipe for target 'check' failed
make: *** [check] Error 1

---

참고

[Pintos-KAIST] Project 1 : Priority Scheduling and Synchronization