💿 KAIST:PINTOS | Concept | Priority

목차

1. 스레드와 우선순위란?
2. Priority Scheduling (우선순위 스케줄링)
3. Preemption (선점)
4. Priority Inversion (우선순위 역전 현상)
5. Priority Donation (우선순위 기부)
6. Donation Chain (도네이션 체인)
7. Donation 복구 (Rollback)
8. Ready List와 정렬 기준
9. 락(Lock), 세마포어(Semaphore), 조건변수(Condvar)
10. 정리: 구현 체크리스트
11. 용어 사전

---

1. 스레드와 우선순위란?

• 스레드(Thread)
  → 실행 가능한 최소 단위입니다. PintOS에서 각각의 스레드는 struct thread 구조체로 표현됩니다.

• 우선순위(Priority)
  → 숫자가 클수록 우선순위가 높습니다.
  priority 필드가 스레드의 우선순위를 나타냅니다. 이 값은 스케줄러가 누구에게 CPU를 줄지 결정할 때 사용됩니다.

---

2. Priority Scheduling (우선순위 스케줄링)

운영체제는 ready_list 안에 있는 스레드들 중 가장 높은 priority를 가진 스레드를 골라 CPU를 할당합니다.

• 이 리스트는 항상 priority 내림차순 정렬되어 있어야 합니다.
• 즉, 숫자가 클수록 먼저 실행됨!

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

이 정렬이 안 되어 있으면 낮은 priority가 먼저 실행되는 이상한 상황이 생깁니다.

---

3. Preemption (선점)

현재 실행 중인 스레드보다 더 높은 priority의 스레드가 깨거나 생성되면,
현재 스레드는 CPU를 양보해야 합니다.

if (!intr_context() && thread_current()->priority < max_priority)
  thread_yield();

• intr_context()는 인터럽트 처리 중인지 확인합니다.
• thread_yield()는 현재 스레드를 ready_list로 보내고 스케줄링을 다시 합니다.

---

4. Priority Inversion (우선순위 역전 현상)

낮은 priority의 스레드가 락을 쥐고 있고, 높은 priority의 스레드가 그 락을 기다리는 상황이 오면?

• 높은 priority 스레드는 락을 얻기 전까지 기다려야 함
• 하지만 중간 priority 스레드가 계속 실행되면 → 높은 priority 스레드가 실행되지 못하는 우선순위 역전 발생

이 문제를 해결하기 위해 Priority Donation 개념이 등장합니다.

---

5. Priority Donation (우선순위 기부)

높은 priority의 스레드가 락을 쥐고 있는 낮은 priority의 스레드를 기다릴 때,
자신의 priority를 임시로 기부합니다.

donation 발생 조건

• lock_acquire() 도중 lock이 이미 다른 스레드에 의해 사용 중일 때
• waiting_lock 필드를 따라가며 holder에게 priority를 전달

🔨 필요한 구조체 필드

int original_priority;           // 기부받기 전 우선순위 저장
struct lock *waiting_lock;       // 내가 기다리고 있는 락
struct list donations;           // 나에게 우선순위를 기부한 스레드들

---

6. ⛓️ Donation Chain (도네이션 체인)

하나의 스레드가 또 다른 락을 기다리고 있다면?

Thread C (priority 50) → 대기 중: lock2
Thread B (priority 20) → lock2 holder, 대기 중: lock1
Thread A (priority 10) → lock1 holder

이렇게 연결된 상황에서, Thread C는 B에게, B는 A에게 priority를 순차적으로 기부해야 합니다.

→ 도네이션은 재귀적으로 전달되어야 합니다.

while (lock && lock->holder && lock->holder->priority < t->priority)
{
  lock->holder->priority = t->priority;
  lock = lock->holder->waiting_lock;
}

---

7. 🧹 Donation 복구 (Rollback)

락을 해제할 때는 해당 락을 통해 받은 donation을 되돌려야 합니다.

remove_with_lock(lock);     // 해당 락 관련 donation 제거
refresh_priority();         // 가장 높은 donation으로 priority 복원

• 기부받은 donation 목록을 유지하고,
• 특정 락에 대한 donation만 제거하는 방식

---

8. 📋 Ready List와 정렬 기준

ready_list, sema->waiters, condvar->waiters 등 모든 대기 큐는 priority 순서대로 정렬되어야 합니다.

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

---

9. 🔒 락, 세마포어, 조건변수

• 락(lock): 한 번에 하나의 스레드만 자원을 사용하도록 제어
  → lock_acquire(), lock_release()에서 donation 처리 필요

• 세마포어(semaphore): 대기 큐와 signal 개념으로 자원을 제어
  → sema_down()에서 priority 순서로 대기 큐 삽입

• 조건변수(condvar): 어떤 조건이 만족될 때만 깨우기
  → cond_signal()에서 가장 높은 priority 스레드를 깨워야 함

---

10. ✅ 구현 체크리스트

구현 항목	설명	관련 테스트
ready_list 정렬	높은 priority가 앞에	priority-fifo, priority-preempt
donate_priority()	기부 로직	priority-donate-one, -multiple, -nest, -chain
remove_with_lock()	donation 제거	priority-donate-multiple2, -lower
thread_set_priority()	우선순위 수동 변경	priority-change
sema/cond 정렬	세마포어 / 조건변수 대기 순서 정렬	priority-sema, priority-condvar

---

📚 용어 사전

용어	설명
Thread (스레드)	CPU에서 실행 가능한 작업 단위
Priority (우선순위)	스레드의 실행 우선도
Preemption (선점)	더 높은 priority가 나타날 때 CPU를 양보하는 것
Priority Inversion	낮은 priority가 높은 priority를 막는 현상
Donation	높은 priority가 낮은 priority에게 우선권을 일시적으로 넘겨주는 것
Chain Donation	도네이션이 여러 스레드에 걸쳐 연쇄적으로 일어나는 것
Rollback	락 해제 시 도네이션을 회수하고 원래 priority 복원
Lock	자원에 대한 접근을 제한하는 동기화 기법
Semaphore	대기 큐를 관리하는 고전적 동기화 기법
Condvar	조건이 충족될 때까지 대기하는 구조

---

🔁 구현 순서와 의존성 – 무엇부터 만들어야 할까?

PintOS Project 1의 priority-* 관련 기능들은 서로 강하게 연결되어 있습니다.
단순히 순서대로 구현하는 게 아니라, 기능 간 의존성을 고려해서 순서를 정해야 테스트가 제대로 통과됩니다.

---

🧱 구현 단계별 의존 구조

단계	구현 항목	의존 이유
1️⃣	ready_list 정렬	모든 priority 스케줄링 로직의 기반. 스레드가 깨어날 때 올바른 순서로 정렬되어 있어야 이후 donation도 의미 있음.
2️⃣	donate_priority()	도네이션 로직 구현. 역전 현상 해결의 핵심이며, ready_list 정렬이 되어야만 donation이 효과적으로 반영됨.
3️⃣	remove_with_lock() & refresh_priority()	락 해제 시 도네이션 회수. donation이 구현된 후에야 필요하며, rollback 로직으로 반드시 이어져야 함.
4️⃣	thread_set_priority()	사용자가 수동으로 priority를 바꿀 때, donation 여부에 따라 어떤 값을 반영할지 결정해야 함. donation 로직이 선행되어야 의미 있음.
5️⃣	sema_down() / cond_signal() 정렬	세마포어/조건변수 waiters 리스트도 priority 기반 정렬이 필요. 락 기반 donation 로직이 모두 동작한 이후 구현하는 게 안전.

---

💡 왜 순서가 중요한가?

• 정렬 먼저 → donation 나중
  도네이션을 해도 ready_list가 FIFO 방식이라면 높은 priority 스레드는 실행되지 못함 → 테스트 실패

• rollback은 donation 없이는 의미 없음
  도네이션이 없는데 rollback 먼저 구현하면 코드만 복잡해지고 테스트에 영향 없음

• 세마포어 정렬은 마지막에
  기본적인 락 기반 donation이 완전히 작동한 후에, 나머지 동기화 구조에 priority-aware 동작을 확장하면 된다