지금까지의 개념 정리_Alram Clock & Priority Scheduling

목요일(사실상 금요일)부터 지금까지 급격히 확확 많은 내용을 습득하다보니 정리가 잘 안되어서 뇌정지가 오더라구요

지금 잡지 않으면 그 다음 시간들이 뻘로 지나갈걸 알기에 다시 한 번 저에게 물음표를 던지며 되돌아보려 합니다

---

Alram Clock

 

EX) timer_sleep(100) 이 호출됐을 때 내부적으로 어떤 함수들이 호출되고, 어떤 흐름으로 흘러가는지

(1) 사용자 스레드가 timer_sleep(100)을 호출한다
    ↓
(2) 현재 tick + 100 을 계산해 thread_sleep(wakeup_tick) 호출
    ↓
(3) thread_sleep():
    - 현재 스레드를 sleep_list에 삽입 (wake_up_tick 기준 정렬)
    - thread_block()으로 상태를 BLOCKED로 전환
    ↓
(4) 이후 인터럽트 발생마다 timer_interrupt() 호출
    - 그 안에서 thread_awake(now_tick) 호출됨
    ↓
(5) thread_awake():
    - sleep_list에서 깨어날 시간이 된 thread를 READY로 만들고
    - thread_unblock()으로 ready_list에 삽입

Q: thread_sleep()은 어떤 상태의 스레드에게 호출되어야 하고, 그 이유는?

 

thread_sleep()은 현재 CPU를 점유하고 있는 실행 중인 스레드가

“앞으로 X tick 동안은 쓸 일이 없으니 스스로 BLOCKED 상태로 들어가겠다”

라고 선언하는 것

 

즉, 자발적으로 BLOCKED 상태로 들어가는 케이스

(이게 핵심 차이, 세마포어나 락을 기다리는 BLOCK과는 다름)

• ✔️ thread_sleep()은 RUNNING 상태에서 호출된다.
• ✔️ 내부에서 thread_block()을 통해 상태를 BLOCKED로 바꾸고,
• ✔️ schedule()을 호출해서 다른 스레드에게 CPU를 넘긴다.
• ✔️ 그러면서 sleep_list에 본인을 wake_up_tick 기준으로 정렬해서 넣는다.

 

Q: thread_sleep()에서 왜 intr_disable()을 사용해서 인터럽트를 꺼야할까?

 

thread_sleep()은 sleep_list를 조작하고 스레드 상태를 변경하는 함수

그런데 이 시점에 타이머 인터럽트(timer_interrupt)가 들어오면 경쟁상태 발생

1. 지금 스레드 A가 thread_sleep()을 실행 중이라 sleep_list에 자신을 넣으려 함
2. 근데 그 순간 timer_interrupt()가 들어와서 thread_awake()를 실행해버림
3. 아직 A가 sleep_list에 제대로 들어가기도 전에 thread_awake()는 그 리스트를 순회하면서 “깰 스레드가 없네~” 하고 넘어감
4. A는 결국 BLOCKED 됐지만, 누구도 깨워줄 수 없는 상태가 되어버림 = 영영 못 깨는 좀비 스레드

(1) A 스레드가 thread_sleep() 호출 중 → 아직 list에 삽입 안 했는데
(2) 인터럽트 발생 → timer_interrupt() → thread_awake() → sleep_list 스캔
(3) A는 아직 리스트에 안 들어가 있어서 무시됨
(4) A는 이후에 리스트에 들어가고 block됨 → 영영 깨어나지 않음

 

---

Priority Scheduling

 

흐름 요약

스레드 생성 → unblock → ready_list에 정렬 삽입
                          ↓
     thread_current보다 priority 높으면 thread_yield()
                          ↓
         yield 되면 schedule() → next_thread_to_run() 호출
                          ↓
     ready_list에서 가장 높은 priority 스레드 실행

 

 

 

Q: thread_block()은 언제 호출되어야 하냐?

스레드가 스스로 CPU를 포기하고 잠들어야 할 때

예시:

• sema_down()에서 세마포어 값이 0이라 자원이 없을 때
• timer_sleep()에서 정해진 tick이 되기 전까지 기다려야 할 때
• lock_acquire()에서 lock을 이미 누가 들고 있으면 기다려야 할 때
• cond_wait()에서 조건이 만족될 때까지 대기해야 할 때

→ 즉, 의도적으로 block 상태로 보내야 할 때 thread_block()을 호출

 

Q: 그럼 sema_up()에서 thread_unblock()으로 깨운 다음, 바로 thread_test_preemption()을 호출해야 하는 이유는?

 

sema_up()은 다음과 같은 흐름:

1. waiters 리스트에서 가장 priority 높은 스레드를 깨움
2. thread_unblock()으로 READY 상태로 전환됨
3. 하지만 현재 실행 중인 스레드는 계속 실행 중

 

그래서 반드시 방금 깬 애가 나보다 우선순위 높나?를 확인해야 함

 

→ 맞다면  thread_test_preemption()으로 양보해야 함

→ 그렇지 않으면 계속 낮은 우선순위 스레드가 CPU 점유

 

 

Q: cond->waiters에서 쓰는 정렬 함수랑 sema->waiters에서 쓰는 정렬 함수가 왜 다르냐? 

정렬 대상의 구조 차이

 

sema->waiters는 struct thread 리스트

• sema_down()할 때: &curr->elem을 넣고
• sema_up()할 때: 그냥 list_entry(..., struct thread, elem)
• 그래서 정렬 함수는 thread 구조체 기준으로 정렬:

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;
}

 

 

cond->waiters는 struct semaphore_elem 리스트

• cond_wait() 할 때는 semaphore_elem을 만들어서 넣고
• 그 안에 또 struct semaphore가 있고
• 그 안에 또 waiters라는 thread 리스트가 있음
• 그래서 정렬하려면 세마포어 안의 waiters 리스트를 들여다봐야 함:

bool sema_compare_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
  struct semaphore_elem *s_a = list_entry(a, struct semaphore_elem, elem);
  struct semaphore_elem *s_b = list_entry(b, struct semaphore_elem, elem);

  struct thread *t_a = list_entry(list_front(&s_a->semaphore.waiters), struct thread, elem);
  struct thread *t_b = list_entry(list_front(&s_b->semaphore.waiters), struct thread, elem);
  return t_a->priority > t_b->priority;
}

 

---

 

1. Alarm Clock (Sleep 기능 구현)

문제 정의

• timer_sleep(ticks) 호출 시 해당 스레드를 주어진 tick 수만큼 BLOCKED 상태로 만든다.
• 이후 시간이 되면 자동으로 깨워야 한다.

핵심 개념

• sleep 중인 thread를 sleep_list에 저장
• 매 tick마다 깨어날 시간이 된 thread를 READY 상태로 전환

구현 함수 정리

• thread_sleep(int64_t wake_tick)
• → 현재 스레드를 BLOCKED 상태로 만들고 sleep_list에 정렬 삽입
• thread_awake(int64_t now)
• → 깨어날 시간이 된 thread를 thread_unblock()으로 깨움
• compare_wake_up_tick()
• → sleep_list를 정렬하기 위한 함수

 

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

 문제 정의

• READY 상태의 thread 중 priority가 가장 높은 것을 먼저 실행해야 한다.

핵심 개념

• ready_list를 priority 기준으로 정렬
• 새로운 스레드가 만들어지거나, 우선순위가 바뀌었을 때 양보 여부 판단 필요

구현 함수 정리

• thread_cmp_priority()
• → ready_list 정렬용
• thread_unblock()
• → ready_list에 넣을 때 priority 기준 정렬 삽입
• thread_yield()
• → 현재 스레드를 READY로 돌리고 다음 스레드에게 양보
• thread_test_preemption()
• → 우선순위 비교 후 필요한 경우 thread_yield() 실행
• thread_create()
• → 새 스레드 생성 후 현재보다 priority 높으면 양보

 

3. Priority-aware Synchronization (동기화 기초)

문제 정의

• sema_down()으로 BLOCK된 thread 중에서 priority가 가장 높은 것부터 깨워야 함
• cond_signal() 호출 시에도 마찬가지로 priority가 가장 높은 waiters를 깨워야 함

핵심 개념

• sema->waiters, cond->waiters에 들어가는 리스트를 정렬해서 priority 순서대로 관리
• 리스트의 자료형이 다르기 때문에 별도 비교 함수 필요

구현 함수 정리

• thread_cmp_priority()
• → sema->waiters 정렬에 사용
• sema_up()
• → 가장 priority 높은 thread를 pop하여 thread_unblock()
• cond_signal()
• → cond->waiters (semaphore_elem 리스트) 내부를 정렬 후 가장 우선순위 높은 스레드를 깨움
• sema_compare_priority()→ 내부의 semaphore.waiters를 들여다봐야 함
• → semaphore_elem을 비교하기 위한 함수

---

PintOS 스레드/동기화 핵심 함수 요약

 

1. thread_block()

• 🔒 Interrupt가 꺼진 상태에서 호출되어야 한다.
• 😴 현재 실행 중인 thread를 THREAD_BLOCKED 상태로 전환하고 스케줄러에게 양보한다.
• 💥 CPU에서 사라지며, 다시 실행되기 위해서는 누군가가 thread_unblock()을 호출해야 한다.
• ✅ 주로 sleep이나 동기화(wait) 상황에서 사용됨.

 

2. thread_unblock(struct thread *t)

• 🚪 BLOCKED 상태의 스레드를 THREAD_READY로 전환하여 ready_list에 넣는다.
• 📥 단순히 “깨우는 것”이지 실행까지 시키는 것은 아니다. (CPU를 바로 넘기지 않음)
• ⚠️ ready_list에 넣을 때 priority 정렬이 되도록 list_insert_ordered() 사용
• 💡 preemption은 하지 않음, CPU 점유 중인 애가 직접 양보해야 실행됨.

 

3. thread_yield()

• 🙋‍♂️ 현재 실행 중인 스레드를 자발적으로 양보한다.
• 🔁 상태는 THREAD_READY로 바뀌며, ready_list에 다시 삽입됨.
• 🤝 주로 자신보다 우선순위 높은 애가 들어왔거나, 타이머 쿼텀이 끝났을 때 호출
• ❗ 인터럽트를 꺼야 안전하므로 내부에서 intr_disable() 호출함.

 

4. thread_test_preemption()

• 👀 현재 스레드보다 우선순위가 높은 thread가 ready_list에 있으면 thread_yield() 호출
• 🔄 주로 thread_set_priority(), thread_create(), sema_up() 등에서 사용됨
• 🎯 목적: **우선순위 기반 선점(preemption)**을 구현하기 위해 필요한 체크 함수

 

5. thread_sleep(int64_t wakeup_tick)

• 🛏️ 현재 스레드를 BLOCKED로 만들고, sleep_list에 wakeup_tick 기준 정렬 삽입
• ⏲️ 지정된 tick이 될 때까지 깨워지지 않음
• 🚫 idle_thread는 절대 재우지 않음
• ❗ 인터럽트 비활성화 상태에서 호출해야 함

 

6. thread_awake(int64_t now_tick)

• ⏰ sleep_list를 순회하며, wakeup_tick <= now_tick인 스레드를 깨운다
• ✅ thread_unblock()으로 다시 READY 상태로 돌림
• 🧹 리스트가 정렬되어 있기 때문에 조건 만족하지 않으면 바로 break

 

7. sema_down(struct semaphore *sema)

• 🚪 세마포어 value가 0이면 현재 스레드를 BLOCKED로 만들고 waiters 리스트에 삽입
• ✅ 우선순위 정렬로 삽입됨 (list_insert_ordered)
• 🔒 인터럽트는 직접 꺼줘야 race condition 방지 가능

 

8. sema_up(struct semaphore *sema)

• 🔓 세마포어 value를 1 증가시킨다
• 🧼 waiters 중에서 priority 가장 높은 애를 pop해서 thread_unblock()으로 깨움
• 🧠 이후 thread_test_preemption() 호출하여 스케줄링 체크
• ⚠️ 단순히 깨우는 작업이라 실행 시점은 yield() 등에 달림

 

9. cond_wait(struct condition *cond, struct lock *lock)

• 🧼 condition waiters 리스트에 semaphore_elem 추가 후, lock을 release하고 wait 상태
• 💤 내부적으로 sema_down() 사용됨
• 🚨 반드시 lock을 잡은 상태에서 호출해야 함

 

10. cond_signal(struct condition *cond, struct lock *lock)

• 🎙️ condition waiters 중에서 가장 우선순위 높은 애를 깨움
• 🧠 내부적으로 sema_up() 호출됨
• ⚠️ 내부 semaphore의 waiters 리스트 기준으로 비교해야 하므로 sema_compare_priority() 필요