PintOS_Priority_Scheduling_part_2

기존 문제: 세마포어의 waiters 리스트가 FIFO 정렬

 

• PintOS 기본 세마포어(semaphore) 구현에서는 waiters 리스트가 삽입 순서(FIFO) 기준으로 관리됨
• Lock 요청이 먼저 들어온 스레드가 priority가 낮더라도 먼저 lock을 획득함
• 결과적으로 우선순위 높은 스레드가 낮은 스레드보다 늦게 실행되는 역전 현상 발생

 

해결 방법: waiters 리스트를 우선순위 기준 정렬

 

• 스레드가 sema_down() 혹은 cond_wait()로 대기열에 들어갈 때, 우선순위(priority) 기준으로 정렬되도록 수정
• 즉, waiters 리스트를 FIFO → priority-based 구조로 변경

 

---

우선 가장 먼저 했던건 sema_down에서 정렬이 되도록 바꿔주었습니다

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

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

	// 임계구역 진입: 인터럽트를 비활성화하여 동시성 문제 방지
	old_level = intr_disable ();

	// 세마포어 값이 0이면 사용할 수 없으므로 대기해야 함
	while (sema->value == 0) {
    	// 현재 스레드를 세마포어의 waiters 리스트에 우선순위 순으로 삽입
    	// 즉, priority 높은 순서로 정렬되어 삽입됨
    	list_insert_ordered(&sema->waiters, &thread_current()->elem, thread_cmp_priority, 0);

    	// 현재 스레드를 BLOCKED 상태로 전환하고 스케줄러에게 CPU 양보
		thread_block ();
	}

	// 세마포어를 사용할 수 있으므로 값을 감소시켜 잠금 상태로 전환
	sema->value--;

	// 임계구역 종료: 인터럽트 상태 복원
	intr_set_level (old_level);
}

• list_push_back() → list_insert_ordered()로 변경
• 정렬 함수: thread_cmp_priority()
• → 높은 priority가 앞에 오도록 정렬

그리고 깨어날 스레드를 우선순위가 가장 높은 스레드로 선택하도록 sema_up을 수정합니다

void sema_up(struct semaphore *sema) {
    // 동시 접근 방지: 세마포어 waiters 리스트 보호를 위해 인터럽트 비활성화
    enum intr_level old_level = intr_disable();

    ASSERT(sema != NULL);

    // 대기 중인 스레드가 있다면
    if (!list_empty(&sema->waiters)) {
        // 우선순위 기준으로 waiters 리스트 정렬
        list_sort(&sema->waiters, thread_cmp_priority, NULL);

        // 가장 우선순위 높은 스레드를 꺼내서 unblock
        struct thread *t = list_entry(list_pop_front(&sema->waiters), struct thread, elem);
        thread_unblock(t);
    }

    // 세마포어 값 증가 (리소스 사용 가능 상태로 변경)
    sema->value++;

    // 인터럽트 다시 활성화 (임계구역 벗어남)
    intr_set_level(old_level);  

    // 현재 실행 중인 스레드보다 우선순위가 높은 스레드가 ready_list에 있다면
    // CPU를 양보하여 우선순위 높은 스레드가 실행되도록 함
    if (!list_empty(get_ready_list()) &&
        thread_current()->priority < list_entry(list_front(get_ready_list()), struct thread, elem)->priority) {
        thread_yield();  
    }
}

 

그리고 중요한게 조건변수의 waiters는 struct semaphore_elem을 가집니다

각각의 semaphore_elem은 내부적으로 또 다른 semaphore.waiters 리스트를 가지구요

예를 들어:

cond->waiters
    ↓
┌────────────────────┐
│ semaphore_elem A   │────┐
│  └─ semaphore      │    │
│      └─ waiters:   │    ▼
│         [ T3, T7 ] ├→ T3 (priority 30)
└────────────────────┘

┌────────────────────┐
│ semaphore_elem B   │────┐
│  └─ semaphore      │    ▼
│      └─ waiters:   │    ▼
│         [ T6, T9 ] ├→ T6 (priority 25)
└────────────────────┘

┌────────────────────┐
│ semaphore_elem C   │────┐
│  └─ semaphore      │    ▼
│      └─ waiters:   │    ▼
│         [ T5 ]     ├→ T5 (priority 35)
└────────────────────┘

이런 형식인거에요

그래서 비교를 위해서 정렬함수를 따로 구현해주어야합니다

정리하자면

• 조건변수는 내부에 semaphore_elem을 갖는 구조로 되어 있음
• 각 semaphore_elem 안에 있는 semaphore.waiters에서 우선순위를 비교해야 함
• 그래서 cond_signal() 호출 전에는 cond->waiters를 정렬해야 함
• 이를 위해 별도 정렬 함수 sema_compare_priority() 정의

// 조건 변수의 waiters 리스트를 우선순위 기준으로 정렬하기 위한 비교 함수
// 각 리스트 요소는 struct semaphore_elem 이며, 그 안에 세마포어가 있음
// 세마포어의 waiters 리스트의 가장 앞에 있는 thread의 priority를 기준으로 비교

bool 
sema_compare_priority (const struct list_elem *l, const struct list_elem *s, void *aux UNUSED)
{
    // 각 list_elem을 semaphore_elem 구조체로 변환
    struct semaphore_elem *l_sema = list_entry (l, struct semaphore_elem, elem);
    struct semaphore_elem *s_sema = list_entry (s, struct semaphore_elem, elem);

    // 각 세마포어의 내부 waiters 리스트 가져오기
    struct list *waiter_l_sema = &(l_sema->semaphore.waiters);
    struct list *waiter_s_sema = &(s_sema->semaphore.waiters);

    // 각 waiters 리스트에서 가장 앞에 있는 thread를 꺼내서 priority 비교
    // → priority가 더 높은 thread가 앞에 오도록 정렬
    return list_entry (list_begin (waiter_l_sema), struct thread, elem)->priority
         > list_entry (list_begin (waiter_s_sema), struct thread, elem)->priority;
}

 

이를 cond_signal(Condition Variable에서 대기 중인 스레드 하나를 깨워주는 함수)에 적용해줍니다

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)); // 현재 스레드가 lock을 가지고 있어야 signal 가능

	if (!list_empty (&cond->waiters)) {
		// condition 변수의 대기 리스트를 우선순위 기준으로 정렬
		// waiters 리스트에는 semaphore_elem들이 들어있고, 각 세마포어의 waiters 리스트의 우선순위를 기준으로 정렬
		list_sort (&cond->waiters, sema_compare_priority, 0);

		// 정렬된 리스트에서 가장 우선순위 높은 세마포어의 스레드를 꺼내고
		// 해당 세마포어를 up시켜 대기 중인 스레드 하나를 깨움
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
	}
}

• cond->waiters에는 semaphore_elem이 저장됨
• 각 semaphore_elem은 내부에 semaphore 하나를 가지고 있고, 그 안에 실제 대기 중인 스레드들이 들어 있음
• sema_compare_priority()를 통해 이 중에서 가장 우선순위가 높은 스레드를 가진 semaphore_elem을 골라서 sema_up()을 통해 그 스레드 하나를 깨워줌