OSTEP: 7. Scheduling: Introduction

이 글은 OSTEP(Operating Systems: Three Easy Pieces)의 ‘Scheduling: Introduction’ 문서를 직접 읽고 정리한 내용이다.
이론적 가정과 실제 운영체제의 현실을 비교해 이해하는 데 초점을 맞췄다.

---

1. Turnaround Time vs Response Time

Turnaround Time (완료 지연 시간)

• 정의: 작업이 도착(arrival)한 시점부터 완료(completion)될 때까지의 시간.
• 사용처: 배치(batch) 시스템. 전체 처리량(throughput) 극대화.
• 특징: 평균 실행시간 단축에 초점.

Response Time (응답 시간)

• 정의: 작업이 도착한 후 처음으로 CPU를 할당받아 실행되기까지 걸린 시간.
• 사용처: 대화형(interactive) 환경. 사용자 경험(UX)에 직결.
• 특징: 빠른 반응 제공.

비교

• Turnaround 최적화 → 전체 완료 시간 단축, 하지만 사용자 체감 응답은 느려질 수 있음.
• Response 최적화 → 사용자 응답은 빠르지만, 전체 완료 시간은 늘어날 수 있음.
• 따라서 시스템 목표에 따라 지표 선택이 달라진다.

---

2. SJF, STCF vs RR

SJF (Shortest Job First)

• Non-preemptive: 가장 짧은 작업부터 실행.
• 장점: 평균 turnaround time 최소화.
• 단점: 긴 작업은 계속 밀려 응답성 악화.

STCF (Shortest Time To Completion First, Preemptive SJF)

• Preemptive: 새 작업이 현재 남은 시간보다 짧으면 중단 후 실행.
• 장점: 평균 turnaround time 최적화.
• 단점: 긴 작업 희생, fairness 문제.

RR (Round Robin)

• Time slice(quantum) 단위로 작업을 순환하며 실행.
• 장점: 응답성이 매우 좋고 공정함. 대화형 환경에 적합.
• 단점: turnaround 시간은 길어질 수 있음. quantum이 너무 짧으면 context switching 오버헤드 증가.

비교 표

항목	SJF / STCF	RR
평균 Turnaround Time	매우 우수	상대적으로 나쁨
Response Time	종종 느림	매우 좋음
Fairness	낮음	높음
구현 난이도	실행시간 예측 필요	단순

---

3. CPU Scheduling의 5 Assumptions (및 현실성 고려)

Assumption 1: All jobs run for the same amount of time

• 설명: 모든 작업 실행시간 동일.
• 현실성: 실제로는 작업마다 실행 길이 천차만별.
• 의미: 짧은/긴 작업 혼재 고려 필수.

---

Assumption 2: All jobs arrive at the same time

• 설명: 모든 작업이 동시에 도착.
• 현실성: 실제로는 작업이 랜덤하게 들어옴.
• 의미: 동적 도착을 반영하는 스케줄러 필요.

---

Assumption 3: Once started, a job runs to completion

• 설명: 시작하면 끝까지 실행 (no preemption).
• 현실성: 현실 OS는 반드시 preemption 사용.
• 의미: 긴 작업 독점을 막기 위해 선점 기반 필요.

---

Assumption 4: All jobs only use the CPU (no I/O)

• 설명: CPU-bound만 존재.
• 현실성: 실제는 I/O와 CPU 혼합.
• 의미: I/O-bound vs CPU-bound 균형 필요.

---

Assumption 5: The run-time of each job is known

• 설명: 실행시간이 미리 알려져 있음.
• 현실성: 현실에서는 불가능, 과거 기록 기반 추정만 가능.
• 의미: SJF/STCF는 이론적 최적이지만, 현실에서는 예측 오차 존재.

---

4. 요약 및 맺음말

• Turnaround vs Response: 어떤 지표를 우선할지는 시스템 목표에 달려 있음.
• SJF/STCF vs RR: 배치 처리 → SJF/STCF, 대화형 환경 → RR.
• 5 Assumptions: 분석 단순화를 위한 모델일 뿐, 현실 OS는 변동성과 불확실성을 전제로 동작.

따라서 실제 스케줄러는 공평성, 응답성, 추정 기법, I/O 고려, 선점을 종합적으로 반영해야 한다.
현대 시스템에서 사용하는 다단계 피드백 큐(MLFQ)는 바로 이러한 현실성을 해결하려는 접근이다.