[PintOS] project 1 : Thread - Priority Scheduler

Alarm-Clock에 이어서 이번에는 Priority Scheduler를 구현해보자 !

PintOS 부터는 팀 활동이 중요하다고 코치님들이 매번 말씀을 하셔서 부분적으로 나눠서 진행하기로 했다.

구현해야 할 로직들을 살펴보자.

구현에 들어가기 전에 Priority Scheduler가 무엇인지, 왜 필요한지 짚고 가보자
또한 다른 CPU 스케줄링 방식들에 대해 간단하게 이야기 해보겠다.

---

CPU Scheduling

CPU 스케줄링이란 어떤 작업에 CPU를 배정할지 결정하는 것이다. 컴퓨터 시스템의 효율은 어떤 프로세스 혹은 스레드에 CPU를 먼저 배정하느냐에 따라 달라지므로 CPU 스케줄링은 작업의 형평성과 효율성을 결정하는 중요한 일이다 !

간단하게 CPU 스케줄링에 어떤 방식들이 있는지 살펴보자

• FCFS(First Come First Serve) : 먼저 온 놈 먼저 처리
• RR(Round Robin) : 일정 시간만 일하고 뒤로 가라
• SJF(Shortest Job First) : 제일 금방 끝나는 놈 먼저 처리

• Priority Scheduling : 우선순위 높은 놈 먼저 처리

참고로 PintOS의 기본 스케줄링은 FCFS이다. (FIFO 방식)
우리가 지금 바꾸는 것은 바로 이 구조를 Priority 기반으로 만드는 것임

👇 아래의 표는 각 스케줄링 방식의 특징과 장단점을 요약해놓은 표이다 👇

CPU 스케줄링에는 선점형, 비선점형 스케줄링이라는 개념도 있고
CPU 알고리즘의 평가 기준 (대기 시간, 응답 시간, 실행 시간, 반환 시간) 같은 것들이 있는데 이것들을 다 이야기하면
너무 길어질 수 있으니 다른 게시글에서 따로 다뤄보도록 하자.

우리는 Priority Scheduler를 구현하면서 thread가 다음 중 어느 경우든지:

• 새로 생성되었을 때 (thread_create)
• 잠에서 깨어났을 때 (thread_wakeup)
• 우선순위가 변경되었을 때 (thread_set_priority)

→ 항상 현재 실행 중인 스레드보다 더 높은 우선순위를 가지면
즉시 CPU를 양보하게 만들어야 했다.

이를 위해 preempt_priority()라는 함수를 만들어
모든 상황에서 일관된 조건으로 preemption을 처리하도록 설계했다.

이제 위에 To-do리스트에 작성했던 함수들을 구현해보도록 하자 !

---

thread_create()

우리가 구현할 priority scheduler의 첫 시작은 thread_create() 함수에서 시작된다.

• 역할 :

  • 새 스레드를 생성하고, 초기화 한 뒤, READY 상태로 전환시킴
  • Priority Scheduler 에서는 :
    • 생성한 스레드가 현재 실행 중인 스레드보다 우선순위가 높다면,
    • 즉시 CPU를 양보해야 할 수 있다

• 주요 흐름 설명 :

1. init_thread() 호출로 priority 포함한 구조체 초기화
2. thread_unblock(t) 호출 → 스레드를 READY 상태로 만들고 ready_list에 삽입
3. 그 직후 preempt_priority() 호출
   → 생성한 스레드의 priority가 더 높다면, thread_yield() 를 호출해 자발적 선점 발생

→ 즉, 이 함수는 우리가 구현할 priority scheduler의 첫 연결고리 역할을 한다.

핵심 코드

thread_unblock(t);
preempt_priority(); // 생성된 스레드의 priority가 더 높을 수 있으므로 선점 판단

• 이 시점에서 선점 판단을 안 하면,
  priority 40짜리 thread가 생성되었는데도,
  priority 10짜리 thread가 계속 CPU를 점유할 수 있다

• 그래서 thread_create() 에서는 반드시 Preemption을 고려한 스케줄링이 필요함 !

---

thread_unblock()

• 역할 :

  • BLOCKED 상태의 스레드를 READY 상태로 전환하고,
    ready_list 에 삽입하는 유일한 통로이자, 스레드 상태 전이의 핵심 함수

• 동작 흐름 :

1. 인자로 받은 thread t 가 유효한지 확인 (is_thread(t))
2. interrupt를 disable 상태로 전환 (race condition 방지)
3. BLOCKED 상태인지 검사
4. ready_list 에 t 를 priority 기준 정렬로 삽입
5. 상태를 THREAD_READY 로 변경
6. interrupt 상태 복구

핵심 코드

list_insert_ordered(&ready_list, &t->elem, cmp_priority, NULL);
t->status = THREAD_READY;

preemption 판단이 여기 없는 이유

• thread_unblock() 함수 내에서 thread_yield() 혹은 intr_yield_on_return() 을 호출할 경우,
  문맥 전환 발생 조건이 복잡해지고, 무한 루프 가능성이 생긴다.

• 대표적 예 : thread가 자기 자신을 unblock 하는 경우
  → yield() 반복 발생 가능

• 그래서 현재 구조에서는 preemption 판단 책임을 완전히 preempt_priority()에 위임함

---

cmp_priority()

• 역할 :

  • ready_list 에 thread를 삽입할 때 사용할 비교 함수
  • list_insert_ordered() 에서 사용됨
  • 우선순위(priority)가 높은 thread가 앞에 오도록 내림차순 정렬을 보장

• 동작 흐름 :

  1. list_elem 포인터 두 개를 struct thread* 로 복원 (list_entry 사용)
  2. 각 스레드의 priority 값을 비교
  3. ta->priority > tb->priority 일 경우, true 반환 → ta가 tb보다 앞에 옴

전체 코드

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

• ready_list 는 스케줄러가 다음에 실행할 thread를 고르는 큐

• 이 리스트가 priority 내림차순으로 유지되어야,
  → list_front(&ready_list) 에서 가장 높은 priority의 thread를 항상 바로 고를 수 있음

• cmp_priority() 는 그 정렬 기준을 제공함

참고사항

• 현재 구조에서는 priority tie-break (예: tid로 순서 고정)는 구현하지 않았지만, 기본 테스트에서는 문제없이 통과

• 다만, priority가 같은 스레드들 간의 실행 순서를 안정적으로 유지하고 싶다면
  tid 를 비교하는 조건을 추가해도 됨

if (ta->priority == tb->priority)
	return ta->tid < tb->tid;

---

thread_yield() – 현재 실행 중인 스레드의 자발적 양보

• 역할 :

  • 현재 실행 중인 스레드가 자발적으로 CPU를 양보하는 함수
  • 양보한 후에도 다시 READY 상태로 되기 때문에,
    → 다른 스레드가 없으면 자기 자신이 다시 선택될 수도 있음
  • priority scheduler 기준에서는 ready_list에 정렬 삽입 → 스케줄러 호출까지가 핵심 흐름

• 동작 흐름 :

1. 현재 스레드 포인터를 가져옴 (thread_current())
2. interrupt를 disable (동기화)
3. idle thread가 아니라면 → ready_list에 priority 정렬로 삽입
4. do_schedule(THREAD_READY) 호출로 상태 변경 + 스케줄러 진입
5. interrupt 복구

핵심 코드

old_level = intr_disable ();
if (curr != idle_thread)
    list_insert_ordered(&ready_list, &curr->elem, cmp_priority, NULL);
do_schedule (THREAD_READY);
intr_set_level (old_level);

• 기존에는 list_push_back() 을 사용했기 때문에.
  → 우선순위와 무관하게 무조건 뒤에 삽입
  → 낮은 priority thread가 계속 실행되는 문제 가능
• 이제는 list_insert_ordered() + cmp_priority() 로 삽입하므로
  → 현재 thread보다 높은 priority thread가 있다면 → 그 thread가 실행될 수 있게 됨

---

preempt_priority()

• 역할 :

  • 현재 실행 중인 스레드가 CPU를 계속 점유해도 되는지 판단하는 함수
  • ready_list에 더 높은 priority를 가진 스레드가 있다면 → 양보 (thread_yield())

• 동작 흐름 :

  1. idle thread면 무시 (양보 대상이 아니기 때문에)
  2. ready_list가 비어있으면 비교 대상 없음 → 무시
  3. ready_list의 list_front() 는 가장 높은 priority thread
  4. 현재 실행 중인 thread와 비교해서 priority가 낮으면 → thread_yield()

핵심 코드

void preempt_priority(void) {
	if (thread_current() == idle_thread)
    	return;
    
    if (list_empty(&ready_list))
    	return;
       
    struct thread *curr = thread_current();
    struct thread *ready = list_entry(list_front(&ready_list), struct thread, elem);
    
    if (curr->priority < ready->priority)
    	thread_yield();
 }

• 이 함수는 ready_list를 직접 수정하지 않음

• 다만, 정렬된 ready_list를 신뢰하고,
  list_front() 만으로 선점 대상 여부를 판단함

• 따라서 이 구조가 성립하려면 :

  • ready_list 는 항상 cmp_priority 로 정렬되어 있어야 한다.
    → thread_unblock(), thread_yield() 모두 정렬 삽입 유지

호출 위치

---

thread_set_priority()

• 역할 :

  • 현재 실행중인 스레드의 priority 값을 변경한다
  • 만약 priority를 낮췄고, 현재보다 높은 priority의 스레드가 ready_list에 있다면
    → 즉시 CPU를 양보해야 한다

핵심 코드

void thread_set_priority(int new_priority) {
	thread_current()->priority = new_priority;
	preempt_priority();
}

• 이 전 코드에서는 priority 만 바꿨기 때문에,
  낮은 priority로 변경해도 계속 CPU를 점유하는 문제가 있었음

• 지금 구조에서는 변경 직후 preempt_priority() 를 호출함으로써,
  스레드가 양보할지 판단을 중앙집중적으로 처리한다.

---

✅ 구조적으로 안정적인 priority scheduler란?

우리는 preemption 로직을 preempt_priority()라는 단일 함수로 통합함으로써,
스레드 생성, 깨어남, 우선순위 변경 등 모든 상황에서 일관된 방식으로 우선순위 기반 스케줄링이 작동하도록 만들었다.

이 방식은 코드 중복을 제거하고, interrupt context와 user context를 구분하여
무한 루프나 race condition을 방지하는 데에도 효과적이었다.

테스트 결과, alarm-*, priority-preempt, priority-change, priority-fifo 등 핵심 테스트를 모두 통과하며
정확한 priority scheduler 동작을 보장함을 검증했다.

이와 같이 구현한 부분의 testcase가 통과된 것을 확인할 수 있었다 !

이후에 진행하는 동기화 Primitive 과정과 Priority Donation 과정은 같은 팀원의 블로그를 첨부하도록 하겠다.

👉 동기화 Primitive 보러가기

👉 Priority Donation 보러가기

그럼 20000