운영체제 · Pintos · Project 1 Threads · 1편
Pintos alarm-priority: ready_list 우선순위 정렬로 출력 순서 맞추기
이번 글은 Pintos Project 1 전체가 아니라 Alarm 테스트 중 alarm-priority에서 드러난 우선순위 문제를 다룹니다. timer_sleep()과 busy waiting은 배경으로만 보고, 실제 코드 분석은 thread.c의 ready list 정렬 수정에 맞춥니다.
이번 글에서 다루는 것
- Alarm Clock 테스트가 thread 상태 전이를 어떻게 확인하는지
alarm-priority가 왜 ready list 정렬 문제로 이어지는지- 실제로 반영한
thread_priority_more,thread_unblock(),thread_yield()코드 - 테스트셋을 기준으로 문제를 쪼개고, 완료 후 코드를 분석하는 방법
1. Project 1 안에서 Alarm Clock의 위치
Project 1 Threads에는 Alarm Clock, Priority Scheduling, Priority Donation, MLFQS가 이어서 나옵니다. 하지만 첫 구현은 Alarm Clock부터 시작하는 편이 좋습니다. 여기서 thread를 잠들게 하고, 기다리게 하고, 다시 실행 가능한 상태로 돌리는 흐름을 처음으로 직접 만지기 때문입니다.
이 글은 첫 번째 칸인 Alarm Clock만 다룹니다. 뒤의 priority 관련 내용은 여기서 깊게 설명하지 않고, Alarm 구현 후 다음 글로 넘깁니다.
2. Alarm Clock이 요구하는 한 가지 규칙
공식 문서에서 Alarm Clock은 devices/timer.c에 있는 timer_sleep()을 다시 구현하라고 요구합니다. 이미 동작하는 구현은 있지만, 그 방식은 busy waiting입니다.
핵심 규칙: thread가 일정 tick 동안 기다려야 한다면, CPU를 계속 쓰며 기다리게 하지 말고 BLOCKED 상태로 보내야 합니다.
여기서 tick은 Pintos timer가 세는 시간 단위입니다. 기본값 기준으로 TIMER_FREQ는 100이므로, 1초에 100번 timer interrupt가 발생한다고 생각하면 됩니다.
3. busy waiting이 왜 문제인가
busy waiting은 기다려야 하는 thread가 실제로는 아무 일도 하지 않으면서 CPU를 계속 확인하는 방식입니다. Pintos의 기존 timer_sleep()은 시간이 지났는지 반복해서 확인하고, 아직 시간이 안 됐으면 thread_yield()로 CPU를 양보하는 식입니다.
| 구분 | busy waiting 방식 | Alarm Clock에서 원하는 방식 |
|---|---|---|
| 기다리는 thread 상태 | 계속 실행 후보로 남음 | BLOCKED로 이동 |
| CPU 사용 | 시간 확인을 위해 불필요하게 사용 | 다른 실행 가능한 thread에게 넘김 |
| 깨우는 주체 | 자기 자신이 계속 확인 | timer interrupt가 시간이 된 thread를 깨움 |
| 테스트 관점 | Alarm Clock 요구사항 위반 | alarm-* 테스트의 목표 동작 |
잠자는 thread가 READY 상태로 남아 있다면 제대로 잠든 것이 아닙니다. 이 파트의 핵심은 "기다리는 동안 실행 후보에서 빼는 것"입니다.
4. 상태 전이로 보면 이해가 쉬워진다
Alarm Clock을 코드로 보기 전에 thread 상태부터 봐야 합니다. timer_sleep()이 해야 할 일은 현재 thread를 잠깐 실행 대상에서 빼고, 시간이 되면 다시 실행 가능하게 만드는 것입니다.
timer_sleep 호출
sleep list에 저장
wakeup tick 도달
scheduler가 선택
여기서 중요한 점은 READY로 돌아온 thread가 반드시 바로 실행된다는 뜻은 아니라는 것입니다. READY는 실행 가능하다는 뜻이고, 실제 실행 여부는 scheduler가 결정합니다.
5. 구현에 필요한 파일 지도
Alarm Clock은 Project 1 중에서도 수정 범위가 비교적 좁습니다. 처음부터 thread.c 전체를 이해하려고 하지 말고, 아래 파일만 차례로 보면 됩니다.
| 파일 | 역할 | Alarm에서 보는 이유 |
|---|---|---|
pintos/devices/timer.c |
timer tick과 sleep 함수 | timer_sleep()과 timer_interrupt()를 수정할 가능성이 가장 큽니다. |
pintos/threads/thread.h |
struct thread 정의 |
Alarm Clock 전체 구현에서는 wakeup tick 필드가 필요할 수 있습니다. 이번 수정의 직접 대상은 아닙니다. |
pintos/threads/thread.c |
block, unblock, scheduling | thread_block(), thread_unblock()이 상태를 어떻게 바꾸는지 확인합니다. |
pintos/lib/kernel/list.h |
Pintos list API | sleep list를 정렬 삽입하거나 순회할 때 필요합니다. |
6. 개념 배경: sleep list와 wakeup tick
Alarm Clock 전체 구현의 전형적인 중심은 잠든 thread들을 따로 모아두는 sleep list와 각 thread가 언제 깨어나야 하는지 기록하는 wakeup tick입니다. 다만 이번 글에서 실제로 반영한 코드는 이 부분이 아니라, 깨어난 뒤 ready list에 들어가는 순서를 고친 코드입니다.
timer_sleep(5) 호출wakeup_tick = 105로 기록하고 sleep list에 넣음sleep list를 wakeup tick 기준으로 정렬해 두면 앞에서부터 확인하면서 시간이 된 thread만 깨울 수 있습니다. 이 방식은 구현도 단순하고, 여러 thread가 서로 다른 시간에 잠드는 테스트를 이해하기 좋습니다.
7. 개념 수도코드: Alarm Clock 전체 흐름
아래는 Alarm Clock 전체 구현을 이해하기 위한 개념 수도코드입니다. 이번 글의 실제 반영 코드는 다음 섹션의 ready list 정렬 수정이고, 이 수도코드는 alarm-priority가 어떤 흐름 뒤에 등장하는지 이해하기 위한 배경입니다.
timer_sleep(ticks):
ticks <= 0 이면:
잠들 필요가 없으므로 바로 return
인터럽트를 잠깐 끈다
현재 thread를 구한다
현재 thread의 wakeup_tick = 현재 tick + ticks 로 기록한다
현재 thread를 sleep_list에 wakeup_tick 기준으로 정렬 삽입한다
현재 thread를 BLOCKED 상태로 만든다
인터럽트 상태를 원래대로 복구한다
timer_interrupt():
ticks 값을 1 증가시킨다
sleep_list의 앞에서부터 확인한다
wakeup_tick <= 현재 tick 인 thread가 있으면:
sleep_list에서 제거한다
thread_unblock()으로 READY 상태로 만든다
아직 깨어날 시간이 아닌 thread를 만나면:
뒤쪽 thread도 아직 시간이 안 된 것이므로 순회를 멈춘다8. 실제 반영한 코드로 다시 읽기
여기서부터는 실제로 반영한 코드만 기준으로 봅니다. 이 수정은 timer_sleep() 자체를 완성한 코드가 아니라, alarm-priority에서 드러난 ready list 우선순위 정렬 문제를 해결한 코드입니다.
앞서 일반적인 Alarm Clock 구현 패턴인 wakeup_tick, sleep_list, timer_sleep() 완성 코드를 넣을 수 있다고 생각했지만, 이 글은 실제 작업한 코드 분석 글이어야 하므로 해당 코드는 제외합니다.
8-1. 비교 함수 선언 추가
먼저 ready_list에 thread를 넣을 때 priority 기준으로 비교할 함수가 필요합니다. 그래서 thread.c 상단의 static 선언부 근처에 비교 함수 선언을 추가했습니다.
static bool thread_priority_more (const struct list_elem *a,
const struct list_elem *b, void *aux);8-2. 비교 함수 정의 추가
Pintos의 list는 struct thread를 직접 들고 있는 것이 아니라, thread 안에 들어 있는 struct list_elem elem을 연결합니다. 따라서 비교 함수 안에서는 list_entry()로 원래 thread를 꺼낸 뒤 priority를 비교합니다.
static bool
thread_priority_more (const struct list_elem *a,
const struct list_elem *b,
void *aux UNUSED) {
const struct thread *ta = list_entry (a, struct thread, elem);
const struct thread *tb = list_entry (b, struct thread, elem);
return ta->priority > tb->priority;
}함수 이름의 more는 priority가 더 큰 thread를 앞에 두겠다는 의미입니다. Pintos priority는 숫자가 클수록 높은 우선순위이므로 > 비교가 맞습니다.
8-3. thread_unblock() 수정
기존 코드는 BLOCKED 상태에서 깨어난 thread를 ready list 뒤에 붙였습니다. 이렇게 하면 깨어난 순서가 실행 순서에 영향을 주고, priority 순서가 보장되지 않습니다.
/* 기존 코드 */
list_push_back (&ready_list, &t->elem);/* 수정 코드 */
list_insert_ordered (&ready_list, &t->elem,
thread_priority_more, NULL);이 한 줄 때문에 unblock된 thread는 ready list 안에서 priority가 높은 쪽으로 들어갑니다. 즉 나중에 scheduler가 ready list 앞쪽에서 thread를 꺼낼 때 높은 priority thread가 먼저 선택될 수 있습니다.
8-4. thread_yield() 수정
thread_yield()는 현재 실행 중인 thread가 CPU를 양보하면서 자신을 다시 ready list에 넣는 함수입니다. 여기서도 뒤에 그냥 붙이면 ready list 정렬이 깨집니다.
/* 기존 코드 */
if (curr != idle_thread)
list_push_back (&ready_list, &curr->elem);/* 수정 코드 */
if (curr != idle_thread) {
list_insert_ordered (&ready_list, &curr->elem,
thread_priority_more, NULL);
}이 수정은 현재 thread가 다시 READY 상태로 돌아갈 때도 priority 순서를 유지하게 만듭니다. 그래서 ready list가 한 번 정렬됐다가 yield 때문에 다시 흐트러지는 일을 막을 수 있습니다.
8-5. 완성 후 코드 흐름 분석
BLOCKED → READY → insert ordered
priority 기준 삽입 → ready_list
높은 priority가 앞 → schedule
앞쪽 thread 선택
이 수정의 핵심은 "깨우는 로직"이 아니라 깨운 뒤 ready list에 어떤 순서로 넣는가입니다. alarm-priority에서 여러 thread가 깨어난 뒤 priority 30부터 출력되려면, ready list가 priority 기준으로 유지되어야 합니다.
이 글의 실제 반영 코드는 ready list 정렬까지입니다. 더 높은 priority thread가 생겼을 때 즉시 선점하는 문제는 priority-preempt 등 다음 Priority Scheduling 글에서 별도로 다루는 편이 맞습니다.
9. 이번 수정에서 interrupt를 직접 건드리지 않은 이유
처음에는 alarm-priority라는 이름 때문에 timer interrupt 쪽을 먼저 의심할 수 있습니다. 하지만 이번에 실제로 고친 부분은 interrupt handler가 아니라 READY 상태가 된 thread를 ready list에 넣는 방식입니다.
깨어난 thread가 thread_unblock()을 통해 ready list에 들어온다면, ready list 삽입 정책을 priority 기준으로 바꾸는 것만으로도 출력 순서를 바꿀 수 있습니다.
intr_yield_on_return() 같은 선점 처리는 이번 반영 코드에 들어가지 않았습니다. 즉시 선점까지 다루는 글은 다음 Priority Scheduling 글로 분리하는 편이 더 정확합니다.
10. 테스트를 작은 문제처럼 보기
Alarm 파트도 한 번에 전체를 맞추려고 하면 복잡합니다. 테스트 이름 하나를 작은 문제 하나로 보고, 그 테스트가 요구하는 규칙만 먼저 확인합니다.
| 테스트 | 검증하는 규칙 | 먼저 의심할 곳 |
|---|---|---|
alarm-single |
thread 하나가 지정 tick 이후 깨어나는가 | timer_sleep(), wakeup tick 계산 |
alarm-multiple |
여러 thread가 각자 다른 시간에 깨어나는가 | sleep list 정렬, 여러 thread 저장 |
alarm-simultaneous |
같은 tick에 깨어나야 하는 thread를 모두 깨우는가 | 순회 중 remove 처리, 한 개만 깨우는 실수 |
alarm-zero |
0 tick sleep을 block하지 않는가 | ticks <= 0 처리 |
alarm-negative |
음수 tick sleep을 안전하게 무시하는가 | 음수 입력 early return |
alarm-priority |
깨어난 뒤 priority scheduling이 유지되는가 | Alarm만으로는 완전히 해결되지 않을 수 있음. 다음 Priority 글과 연결 |
11. alarm-priority를 테스트셋 기준으로 풀어보기
alarm-priority는 이름은 Alarm 테스트지만, 사실 Alarm과 Priority Scheduling이 만나는 지점입니다. 이 테스트는 "정해진 시간에 깨웠는가"에서 한 걸음 더 나아가, 같은 시간에 깨어난 thread들이 높은 priority 순서로 실행되는가를 봅니다.
- 테스트는 깨어날 시각을
현재 tick + 5초로 정합니다. - priority가 서로 다른 thread 10개를 만듭니다.
- 각 thread는 거의 같은 시점에
timer_sleep()을 호출해 같은 wakeup time을 기다립니다. - 깨어난 thread는 자기 이름을 출력하고 semaphore로 부모 thread에게 끝났다고 알립니다.
기대 출력은 priority 30부터 21까지 내려가는 순서입니다. thread를 만든 순서가 아니라, 깨어난 뒤 scheduler가 선택해야 하는 순서가 기준입니다.
기대 출력 흐름:
Thread priority 30 woke up.
Thread priority 29 woke up.
Thread priority 28 woke up.
...
Thread priority 21 woke up.이 테스트를 문제처럼 쪼개면
| 단계 | 질문 | 의심할 코드 |
|---|---|---|
| 1 | 10개 thread가 모두 같은 시각까지 잠드는가? | 테스트가 만든 전제. 이번 수정의 직접 대상은 아님 |
| 2 | 같은 tick에 깨어날 thread를 모두 unblock하는가? | 테스트가 통과하려면 필요한 전제. 이번 수정은 그 다음 단계에 집중 |
| 3 | unblock된 thread들이 ready list에 priority 순서로 들어가는가? | thread_unblock(), ready list 삽입 정책 |
| 4 | yield로 다시 들어오는 thread도 ready list 정렬을 유지하는가? | thread_yield(), ready list 삽입 정책 |
흐름으로 보면 이렇게 된다
같은 시각에 깨어남
10개 모두 READY
priority 높은 순서
30부터 실행
이번에 실제로 해결한 방향을 한글 수도코드로 쓰면
timer_interrupt():
시간이 된 sleeping thread를 모두 꺼낸다
각 thread를 thread_unblock()으로 READY 상태로 만든다
thread_unblock(t):
기존처럼 ready_list 뒤에 붙이지 않는다
t를 ready_list에 priority 높은 순서로 삽입한다
thread_yield():
현재 thread가 idle thread가 아니라면:
ready_list 뒤에 붙이지 않는다
현재 thread를 ready_list에 priority 높은 순서로 삽입한다
next_thread_to_run():
ready_list 앞에서 thread를 꺼낸다
ready_list가 정렬되어 있으므로 높은 priority thread가 먼저 나온다alarm-priority는 Alarm 구현만으로 끝나는 테스트가 아닙니다. 그래도 Alarm 글에서 다뤄야 하는 이유는, wakeup의 결과가 결국 ready list로 들어가기 때문입니다. 이번 수정은 "깨운 뒤 어떤 순서로 실행 후보에 세울 것인가"를 고친 것이고, 즉시 선점 같은 더 넓은 priority scheduling은 다음 글의 범위로 남깁니다.
12. 이번 코드에서 자주 나는 실수
현재 thread가 yield로 ready list에 다시 들어갈 때 list_push_back()을 쓰면 ready list 정렬이 다시 흐트러질 수 있습니다.
Pintos priority는 숫자가 클수록 높습니다. ta->priority > tb->priority가 아니라 반대로 쓰면 낮은 priority가 앞에 옵니다.
list_entry(a, struct thread, elem)에서 elem은 struct thread 안의 list_elem 필드명입니다.
ready list 정렬은 중요한 시작점이지만, 더 높은 priority thread가 생겼을 때 즉시 CPU를 넘기는 선점 문제는 별도로 확인해야 합니다.
13. 이번 수정의 완료 기준
이 글의 목표는 Alarm Clock 전체 구현 완료가 아니라, alarm-priority에서 드러난 ready list 순서 문제를 정리하는 것입니다. 따라서 완료 기준도 실제 반영 코드에 맞춰 잡습니다.
thread_priority_more()가 priority 큰 thread를 앞에 두도록 비교한다.thread_unblock()이list_push_back()대신list_insert_ordered()를 사용한다.thread_yield()도 ready list에 다시 들어갈 때 priority 순서를 유지한다.alarm-priority의 출력 순서가 priority 30부터 21까지 내려가는지 확인한다.- 즉시 선점이 필요한 테스트는 다음 Priority Scheduling 글에서 별도로 다룬다.
14. 스스로 점검
list_push_back()을 쓰면 ready list 순서가 왜 priority 기준으로 유지되지 않는가?thread_priority_more()에서>비교를 쓰는 이유는 무엇인가?thread_unblock()과thread_yield()를 둘 다 수정해야 하는 이유는 무엇인가?alarm-priority에서 priority 30 thread가 먼저 출력되려면 ready list는 어떤 상태여야 하는가?- 이번 수정으로 해결한 문제와 아직 다음 Priority Scheduling 글로 남겨둔 문제를 구분할 수 있는가?
이번 글에서 기억할 것
alarm-priority는 Alarm 테스트처럼 보이지만 ready list 우선순위 정렬 문제를 드러낸다.- 실제로 반영한 코드는
thread_priority_more(),thread_unblock(),thread_yield()수정이다. - 핵심은 READY 상태가 된 thread를 ready list 뒤에 붙이지 않고 priority 기준으로 삽입하는 것이다.
- 이 수정은 priority 출력 순서를 설명하지만, 즉시 선점까지 모두 해결했다는 뜻은 아니다.
다음 글 예고
다음 글에서는 Priority Scheduling으로 넘어가서, ready_list에서 highest priority thread를 먼저 실행하게 만드는 방법과 priority-preempt, priority-change, priority-fifo 테스트를 어떻게 읽어야 하는지 정리합니다.