CPU 스케줄링 (OSTEP 7장 기반)
1) 스케줄링을 배우는 이유
- 성능: 같은 하드웨어로 더 짧은 대기 시간/완료 시간을 얻는다.
- 상호작용성: 사용자 체감 응답을 개선한다(터미널·GUI 반응성).
- 공정성: 특정 작업만 독식하는 상황(Convoy)을 완화한다.
트레이드오프 경고: 응답성과 회전 시간은 종종 충돌합니다. 공정성까지 고려하면 “모두를 완벽히 만족”시키기 어렵습니다.
2) 문제 단순화를 위한 Workload 가정
- 모든 작업(Job)이 같은 실행 시간을 가진다.
- 모든 작업이 동시에 도착한다.
- 시작하면 선점 없이 완료될 때까지 돈다.
- I/O 없음(CPU만 사용).
- 각 작업의 실행 시간(길이)을 안다(전지전능한 스케줄러!).
학습용으로는 유용하지만 현실적이진 않음. 이후 하나씩 완화하면서 현실에 근접합니다.
3) 핵심 지표(Metrics)
3.1 회전 시간(Turnaround Time)
작업 완료 시각 − 도착 시각
동시 도착이면 “완료 시각” 평균을 최소화하는 것이 목표.
3.2 응답 시간(Response Time)
첫 실행 시각 − 도착 시각
상호작용(타이핑 → 반응) 체감과 직결. “얼마나 빨리 첫 슬라이스를 받냐”가 중요합니다.
4) 기본 알고리즘과 직관
4.1 FIFO(FCFS)
Queue: [A, B, C] (각 10초)
타임라인: AAAAAAAAAA BBBBBBBBBB CCCCCCCCCC
완료시각: A=10, B=20, C=30 → 평균 회전=20문제: 긴 작업이 맨 앞이면 뒤의 짧은 작업이 줄줄이 지연(Convoy Effect).
길이: A=100, B=10, C=10
A가 먼저면: A........(100) B(110) C(120) → 평균 회전=110 (끔)4.2 SJF(Shortest Job First, 비선점)
“짧은 것부터 먼저 돌리면 평균 회전 시간 최적(동시 도착 가정).”
길이: A=100, B=10, C=10
SJF: BBBBBBBBBB CCCCCCCCCC A...(100)
완료: B=10, C=20, A=120 → 평균 회전=50 (대폭 개선)현실 비유: 마트의 “상품 10개 이하” 계산대 = SJF의 고객 만족 전략.
4.3 STCF / PSJF(Shortest Time-to-Completion First, 선점형 SJF)
도중에 더 짧은 남은 작업이 들어오면 선점하여 교체.
t=0: A(100) 시작
t=10: B(10), C(10) 도착 → 남은 시간 가장 짧은 B부터, 그다음 C, 이후 A
→ 평균 회전이 SJF 대비 더 좋아짐(동시 도착 아님에도 대응)SJF는 “처음 고른 순서”를 끝까지 유지(비선점), STCF는 “언제나 현재 남은 시간 최단”을 유지(선점).
4.4 RR(Round Robin, 시분할)
모두에게 공평하게 짧은 Time Slice를 번갈아 준다.
Jobs: A,B,C (각 5초), Quantum=1초
타임라인: A B C A B C A B C A B C A B C
응답시간 평균: (A=0, B=1, C=2) → 1 (SJF=5보다 훨씬 좋음!)대가: 회전 시간 악화. 작업별 완료가 길게 “늘어짐”(공정성의 비용).
Quantum 선택: 너무 짧으면 컨텍스트 스위치 오버헤드↑, 캐시/분기예측/TLB 세트 손실↑. 너무 길면 응답성↓. HW 타이머 주기의 배수로 설정.
5) 공정성 vs 성능: 핵심 트레이드오프
| 알고리즘 | 응답 시간 | 회전 시간 | 공정성 | 특징 |
|---|---|---|---|---|
| FIFO | 보통 | △/긴 잡 선두 시 악화 | 낮음 | 간단, Convoy 위험 |
| SJF | 나쁠 수 있음 | 최적(동시 도착) | 불공정 | 짧은 작업 우대 |
| STCF | 보통 | 매우 좋음 | 불공정 | 선점으로 동적 최단 유지 |
| RR | 좋음 | 나쁨 | 높음 | 시분할, 상호작용 우수 |
6) I/O를 포함한 현실적 시나리오
아이디어: CPU 버스트와 I/O 대기를 교차시켜 겹침(Overlap)으로 자원 활용을 극대화.
나쁜 경우(겹침 없음)
CPU: A(10) A(10) ... B(50)
DISK: I/O(10) I/O(10) ...
→ CPU·DISK가 동시에 놀거나 한쪽만 바쁨좋은 경우(겹침 활용)
CPU: A(10) B(10) A(10) B(10) ...
DISK: I/O(10) I/O(10)
→ A가 I/O 중일 때 B가 CPU 사용 → 전체 처리율↑실무에서는 인터랙티브(자주 I/O 발생) 잡에 자주 CPU를 쥐여주고, 그 사이에 CPU 집약 잡을 끼워 넣어 둘 다 살립니다.
7) “잡 길이를 모른다” 문제와 직관
- SJF/STCF는 이상적이지만 잡 길이를 모르면 구현 불가.
- 현대 OS는 과거의 CPU 버스트로 미래를 추정(지수평활 등)해 가짜 SJF에 근접합니다.
- 동시에 RR의 응답성 철학을 섞어 MLFQ(다단계 피드백 큐)로 진화(다음 장 주제).
8) 손으로 해보는 미니 계산
8.1 평균 회전 시간(동시 도착 가정)
예) [5, 1, 3] (초)
FIFO (순서 그대로): 완료시각 [5, 6, 9] → 평균= (5+6+9)/3 = 6.67
SJF (정렬 [1,3,5]): 완료시각 [1, 4, 9] → 평균= (1+4+9)/3 = 4.678.2 RR의 응답 시간
동시 도착 N개, Quantum=Q (같은 길이 가정)
첫 실행까지 최대 대기 ≈ (N-1)*Q → 최악 응답 시간 상한9) 그림으로 보는 타임라인(Gantt)
9.1 SJF vs RR (A,B,C 각 5초)
SJF(비선점)
[0] AAAAA [5] BBBBB [10] CCCCC [15]
응답: A=0, B=5, C=10 (평균=5)
회전: A=5, B=10, C=15 (평균=10)RR(Q=1)
[0] A B C A B C A B C A B C A B C [15]
응답: A=0, B=1, C=2 (평균=1)
회전: A=13, B=14, C=15 (평균=14)10) 실무 체크리스트
- 목표 명확화: 배치 처리면 회전 시간, 사용자 인터랙션이면 응답 시간을 우선.
- Quantum 튜닝: 타이머 주기의 배수로, 컨텍스트 스위치/캐시 오버헤드와 응답성 사이 균형.
- I/O 겹침: I/O 대기 중 다른 잡을 돌려 총 처리율↑.
- 추정 기반 우선순위: 최근 CPU 버스트로 짧을 듯한 잡을 가볍게 우대.
- Starvation 방지: 에이징/피드백 큐로 장기 대기 작업도 언젠가 위로.
11) 요약 한 장
- FIFO: 간단하지만 Convoy에 취약.
- SJF: 회전 시간 최적(동시 도착); 응답성·공정성은 희생.
- STCF: 선점으로 “남은 시간 최단” 유지 → 도착 시각이 달라도 강력.
- RR: 응답성·공정성 우수, 회전 시간 나쁨. Quantum이 성능을 좌우.
- I/O 고려: CPU/I/O 겹침으로 활용도 극대화.
- 현실: 잡 길이 미지 → 과거를 바탕으로 미래 추정, MLFQ로 절충.
12) 연습 문제(자기점검)
- 동시 도착 길이 [200,200,200]일 때 FIFO와 SJF의 평균 회전 시간을 구하라.
- 길이 [100,200,300]일 때 FIFO/SJF 평균 회전 시간을 비교하라.
- 위 2번 케이스에 RR(Q=1)을 적용해 응답/회전을 추정하라.
- 어떤 워크로드에서 SJF와 FIFO의 회전 시간이 같아지는가?
- RR에서 N개의 잡이 있을 때 최악 응답 시간을 N, Q로 표현하라.