📀 KAIST:PINTOS | Implementation | Priority Scheduling | Step 1 / 6

오늘은 첫 번째 단계로, 스레드 우선순위 기반 스케줄링의 정렬 구조를 구현하고
priority-fifo, priority-preempt, priority-change 테스트를 성공시킨 기록을 정리했다.

---

🎯 최종 목표 테스트 목록 (총 12개)

카테고리	테스트 이름
우선순위 조작	priority-change
기본 도네이션	priority-donate-one, priority-donate-multiple, priority-donate-multiple2
도네이션 체인	priority-donate-nest, priority-donate-chain
락/세마포어 기반 도네이션	priority-donate-sema, priority-donate-lower
우선순위 기반 스케줄링	priority-fifo, priority-preempt
동기화 기반 우선순위	priority-sema, priority-condvar

✅ 현재 통과한 테스트:
priority-fifo, priority-preempt, priority-change
→ Step 1 / 6 완료

---

🧩 왜 Step 1을 먼저 구현해야 할까?

priority-fifo와 priority-preempt는
ready_list가 priority 기준으로 정렬되어 있는가?
그리고 더 높은 priority의 스레드가 등장했을 때 선점되는가?를 확인하는 테스트이다.

즉, 이 테스트들이 통과하지 않으면 이후 도네이션을 구현해도 의미가 없음.
왜냐하면 기부받은 priority가 제대로 반영되지 않고, 여전히 낮은 우선순위가 먼저 실행되기 때문.

---

🛠 Step 1에서 구현한 것들

✅ 1. priority_cmp() 함수 구현

ready_list의 정렬을 우선순위 기준으로 정렬하기 위해 priority_cmp() 함수를 구현했다.
이 함수는 list_insert_ordered()와 함께 사용되어 ready_list가 항상 우선순위가 높은 스레드가 먼저 실행되도록 유지하게 함.

📄 threads/thread.c:

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

📄 threads/thread.h:

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

이 함수는 ready_list를 priority 기준으로 오름차순 정렬하는 데 사용된다.

---

✅ 2. thread_unblock()에서 priority_cmp() 사용하여 ready_list에 삽입

기존에 list_push_back()을 사용하던 부분을 list_insert_ordered()로 바꾸어,
ready_list가 FIFO가 아닌 priority 순으로 유지되게 했다.
이제 priority_cmp() 함수에 의해 우선순위가 높은 스레드가 먼저 실행되도록 보장할 수 있따.

📄 threads/thread.c:

기존 코드:

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

수정 후:

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

---

✅ 3. thread_yield()에서 ready_list 우선순위 정렬 삽입

스레드가 양보할 때에도 우선순위가 높은 스레드가 먼저 실행되도록 하기 위해,
thread_yield()에서 ready_list에 정렬된 순서로 삽입할 수 있도록 했고

📄 threads/thread.c:

void thread_yield(void) {
  struct thread *curr = thread_current();
  enum intr_level old_level;

  ASSERT (!intr_context ());

  old_level = intr_disable();
  if (curr != idle_thread)
    list_insert_ordered(&ready_list, &curr->elem, priority_cmp, NULL);  // ✅ 정렬 기반 삽입
  do_schedule(THREAD_READY);
  intr_set_level(old_level);
}

이 코드로 우선순위가 높은 스레드가 먼저 실행되도록 할 수 있다.

---

✅ 4. thread_set_priority()와 priority 관리

thread_set_priority() 함수를 구현하여 스레드의 우선순위를 변경하고,
이때 기존 priority가 복원되거나 기부받은 우선순위로 변경되도록 하였다.

void thread_set_priority(int new_priority) {
  struct thread *cur = thread_current();
  cur->original_priority = new_priority;
  refresh_priority();   // 기부 고려해서 priority 반영
  thread_yield();       // 양보 필요 시 처리
}

---

✅ 5. 테스트 실행 (make 방식)

위의 구현이 잘 되었는지 확인하기 위해, priority-fifo와 priority-preempt 테스트를 실행해보면

make clean && make check

또는 개별 테스트만 실행할 땐:

cd build
make tests/threads/priority-fifo.result
make tests/threads/priority-preempt.result

또는 pintos 수동 실행:

pintos -v -k -T 60 -m 20 -- -q run priority-fifo
pintos -v -k -T 60 -m 20 -- -q run priority-preempt

---

✅ 통과한 테스트 확인

📄 콘솔 출력 예시

(priority-fifo) 16 threads will iterate 16 times in the same order each time.
(priority-fifo) end
(priority-preempt) The high-priority thread should have already completed.

→ 둘 다 정상 종료되면 PASS

---

🧱 다음 단계 (Step 2 / 6)

우선순위 직접 변경 + 도네이션 구현

다음 단계에서는 다음 테스트들을 통과시키기 위한 기능들을 구현할 예정이다:

목표 테스트	필요한 구현
priority-change	thread_set_priority()
priority-donate-one	donate_priority()
priority-donate-multiple	도네이션 리스트 관리
priority-donate-nest, -chain	도네이션 체인 구현
priority-donate-lower, -multiple2	donation rollback (remove_with_lock, refresh_priority)

---

✨ 마무리

• Step 1: ready_list 우선순위 정렬 구현 완료
• priority-fifo, priority-preempt, priority-change 테스트 통과 확인