PintOS_Priority_Scheduling_part_1

자 저번에는 Alram Clock을 구현했었죠

그럼 이제 우선순위 스케줄링을 구현할 차레입니다

우선순위 스케줄링을 저는 크게 이렇게 나눠서 구현할 예정입니다

 

기본 틀 잡기: Priority Scheduling

• ready_list를 우선순위 기준으로 정렬하고, 높은 우선순위 스레드가 CPU를 빨리 차지하도록
• ready_list를 priority 순으로 정렬 (list_insert_ordered)
• 새로 들어온 스레드가 현재 스레드보다 우선순위가 높으면 선점 (thread_create 후 thread_test_preemption)
• timer_interrupt()에서 예약 양보(intr_yield_on_return) 수행
• thread_set_priority() 시에도 ready_list와 비교해서 선점 조건 확인

 

우선순위 기반 동기화: Semaphore & Condition Variable

• semaphore의 waiters 리스트도 우선순위 기준으로 정렬
• 세마포어 unblock 시 높은 우선순위의 스레드를 먼저 깨움 (sema_up에서 정렬 + thread_unblock)
• condition variable은 cond->waiters에 semaphore_elem이 저장됨 → 각 semaphore의 waiters 내부를 비교해서 정렬 (sema_compare_priority)
• signaling 시 우선순위가 가장 높은 waiter부터 처리됨 (cond_signal 내부 정렬 + sema_up)

 

Priority Donation

• 락을 잡고 있는 낮은 우선순위 스레드에게 우선순위를 ‘기부’해서 priority inversion을 막는다
• 세마포어나 락을 사용하는 상황에서 priority inversion 발생 가능
• 대기 중인 높은 priority 스레드가 락을 쥔 낮은 priority 스레드에게 우선순위를 기부함
• nested donation도 처리해야 함 (chain donation)
• 락을 풀면 기부받은 우선순위를 초기화하고, hold_list를 기반으로 다시 우선순위를 갱신 (refresh_priority)

그래서 일단 기본틀을 잡았고 그 내용을 다뤄보겠습니다

---

 

목표

1. ready_list는 항상 priority 내림차순으로 정렬되어 있어야 한다.
2. 현재 실행 중인 스레드보다 높은 priority의 스레드가 ready_list에 들어오면 즉시 양보(preemption) 되어야 한다.

스케줄링 방식 바꾸기 전 확인 사항

 

PintOS 기본 스케줄러는 Round-Robin 방식입니다

즉, `ready_list`에 들어온 순서대로 CPU를 할당하며, 

각 스레드에게 동일한 시간 조각(time slice)을 분배하는 방식이죠

 

그래서 기본 코드에서는 `list_push_back()`으로 스레드를 넣고,

스케줄링 순서를 "삽입 순서"로 결정했습니다

 

이제부터는 아래 조건을 만족하도록 스케줄링을 변경할 것이에요

 

• ready_list는 항상 높은 priority 순서로 정렬되어야 한다
• 현재 실행 중인 thread보다 높은 priority를 가진 thread가 ready_list에 들어오면 선점(preempt) 되어야 한다

일단 ready_list를 우선순위 정렬로 유지하기 위해서 기존 함수 대신 list_insert_ordered로 넣어줍니다

list_push_back(&ready_list, &t->elem);

이게 기존 코드인데요

• 그냥 큐의 맨 뒤에 삽입 → Round-Robin 방식 유지
• 우선순위 고려 XX
• Priority Scheduling에서는 ready_list가 항상 우선순위 내림차순이어야 함
• 높은 우선순위 스레드는 먼저 실행되어야 하므로, 큐가 아닌 “정렬된 리스트”로 유지해야 함

이 때문에 수정해줘야 합니다

list_insert_ordered(&ready_list, &t->elem, thread_cmp_priority, NULL);

 

→ thread_cmp_priority()는 우선순위 높은 스레드가 앞에 오도록 비교

→ ready_list가 항상 정렬된 상태로 유지됨

 

이 함수를 위한 정렬함수도 만들어 주고요

bool thread_cmp_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
  const struct thread *t_a = list_entry(a, struct thread, elem);
  const struct thread *t_b = list_entry(b, struct thread, elem);
  return t_a->priority > t_b->priority;
}

그럼 이렇게 unblock함수 수정이 됩니다

 

thread_unblock

/* 
 * Transitions a blocked thread T to the ready-to-run state.
 * 
 * 이 함수는 BLOCKED 상태의 스레드를 READY 상태로 전환시킴
 * 단, 호출 당시 인터럽트는 비활성화해야 하고, 현재 스레드가 BLOCKED 상태여야 함
 */
void thread_unblock(struct thread *t) {
  enum intr_level old_level;

  ASSERT(is_thread(t));  // t가 유효한 thread인지 확인

  // 인터럽트 비활성화 (ready_list 조작은 atomic해야 하므로)
  old_level = intr_disable();
  ASSERT(t->status == THREAD_BLOCKED);  // unblock할 대상이 BLOCKED 상태인지 확인

  // 우선순위 정렬된 상태로 ready_list에 삽입
  // (priority scheduling을 위한 포인트)
  list_insert_ordered(&ready_list, &t->elem, thread_cmp_priority, NULL);

  t->status = THREAD_READY;  // 스레드 상태를 READY로 갱신

  intr_set_level(old_level);  // 인터럽트 상태 복원
}
  // 주의: 이 함수 안에서는 yield()를 호출하면 안 됨.
  // why?: timer interrupt 안에서 이 함수가 호출될 수 있고,
  //       그 안에서 yield()를 직접 부르면 nested schedule() 발생 → 커널 패닉 발생 가능

예 밑에 주석 보이시죠

이 함수에서는 절대 thread_yield 함수를 호출해선 안돼.........저도 알고싶지 않았어요

스케줄러가 중복 호출어쩌구 하는데 사실 크게 이해는 가지 않습니다 좀 더 알아보고 트러블 모음집을 따로 올릴 예정입니다

암튼 여러분은 조심하십쇼 심지어 강의나 공유슬라이드에서도 create함수에 넣으라했더라구요 하핫

 

그리고 thread_create에 우선순위 비교하는 코드를 넣어줍니다

원래는

• thread_unblock(t)만 하고 바로 return
• 선점 여부는 고려하지 않음

이런 방식이었어요

그치만 우선순위 스케줄링은 새로 만든 스레드가 현재 스레드보다 우선순위가 높으면, 바로 CPU를 넘겨줘야해요

안그러면 높은 우선순위 스레드가 불필요하게 대기하게 됩니다 

tid_t thread_create(...) {
    ...
    thread_unblock(t);

    // 새로 생성된 스레드가 더 높은 priority라면 양보
    thread_test_preemption();
    return tid;
}

이렇게요 

자연스레 선점하게 되겠조?

thread_test_preemption()이 뭐냐

그냥 비교해서 양보해주는 겁니다

void thread_test_preemption(void) {
    if (!list_empty(&ready_list) &&
        thread_current()->priority < list_entry(list_front(&ready_list), struct thread, elem)->priority)
        thread_yield();
}

 

그리고 우선순위를 낮출 시에 즉시 yield하기 위해 thread_set_priority도 수정해줍니다

기존엔 그냥 priority 필드만 바꾸고 이후 행동은 없었어요

그치만 우선순위 스케줄링을 구현하기 위해선

• 현재 스레드의 우선순위가 낮아졌다면,
• ready_list에 더 높은 우선순위가 있을 수 있음
• 그럴 땐 CPU를 양보해야 함

이걸 지켜야합니다

void thread_set_priority(int new_priority)
{
    thread_current()->priority = new_priority;
    // project1 : priority schedule
    thread_test_preemption(); // priority가 변경되었으니까 우선순위 변경 확인
}

 

맞다 그리고 우선순위 따라 다시 삽입되도록하게 thread_yield함수도 수정해줘야 합니다

/* 
 * Yields the CPU. 현재 실행 중인 스레드를 READY 상태로 바꾸고 CPU를 양보한다
 * 이 스레드는 다시 ready_list에 들어가 우선순위에 따라 나중에 다시 실행될 수 있다
 */
void thread_yield(void) {
	struct thread *curr = thread_current();
	enum intr_level old_level;

	ASSERT(!intr_context());

	old_level = intr_disable();

	// idle_thread는 ready_list에 넣으면 안 됨
	if (curr != idle_thread)
		list_insert_ordered(&ready_list, &curr->elem, thread_cmp_priority, NULL);  // 우선순위 삽입

	do_schedule(THREAD_READY);  // 현재 스레드를 ready 상태로 바꾸고 다음 스레드 스케줄링
	intr_set_level(old_level);
}

이랗게요

---

자 지금까지 했던 수정을 거치면 

priority-change

priority-fifo

priority-preempt

 

이 세가지 테스트는 통과하는 걸 볼 수 있습니다

 

✅ 1. priority-fifo 통과 흐름

테스트 목적:

• 동일한 우선순위(priority)를 가진 스레드들이 FIFO 순서로 실행되는지 확인

 통과 조건:

• ready_list 삽입 시 우선순위가 같다면, 먼저 들어온 스레드가 먼저 실행되어야 함

실패 원인 (수정 전):

• list_push_back()이나 list_push_front()을 쓰면 순서 꼬일 수 있음
• Round-Robin이 아니라 우선순위 기반으로만 정렬하니 FIFO 보장 안 됨

포인트:

• thread_cmp_priority() 함수는 priority가 같을 때 기존 순서를 유지함
• 즉 Stable Sort가 된다 → FIFO 유지됨

 

✅ 2. priority-change 통과 흐름

테스트 목적:

• 실행 중인 스레드가 자신의 우선순위를 낮췄을 때,
• 더 높은 우선순위 스레드가 ready_list에 있다면 즉시 양보하는지 확인

실패 원인 (수정 전):

• thread_set_priority() 함수가 그냥 값을 바꾸기만 하고 스케줄링을 고려하지 않음

포인트:

• thread_set_priority() 내부에서 즉시 선점 여부 판단
• 양보할 타이밍을 놓치지 않음

 

✅ 3. priority-preempt 통과 흐름

테스트 목적:

• 새로운 스레드가 생성되었을 때, 현재 스레드보다 우선순위가 높다면
• 즉시 스케줄링하여 CPU를 선점하는지 확인

실패 원인 (수정 전):

• thread_create() 이후 thread_unblock()만 호출하고 현재 스레드가 계속 실행됨

포인트:

• 새로 생성된 스레드가 더 중요하다면 즉시 선점
• create → unblock → yield 흐름이 필수

 

 

이제 다음은 donation이네요

해봅시다