CPU Scheduling

CPU Scheduling은 한정된 CPU를 여러 프로세스에게 어떤 기준으로 배분할지 결정하는 정책이다. 메모리의 page replacement 정책은 OS Page Replacement Policies에서 별도로 다룬다.

핵심 메트릭

메트릭	정의	최적화
Turnaround time	완료 시각 − 도착 시각	짧은 잡 먼저 처리
Response time	첫 번째 실행 시각 − 도착 시각	빠른 CPU 배분
Fairness	각 프로세스의 CPU 점유 비율 균형	공평한 time slice

Turnaround time과 Response time은 서로 상충한다. Turnaround를 최적화하면 Response가 나빠지고, Response를 최적화하면 Turnaround가 나빠진다.^[1]

기본 스케줄링 알고리즘

FIFO (First In, First Out) / FCFS

먼저 도착한 잡을 먼저 실행한다. 긴 잡이 앞에 있으면 짧은 잡들이 오래 대기하는 Convoy Effect가 문제다.^[1:1] 예를 들어 A(100s) → B(10s) → C(10s) 순서면 평균 turnaround는 110s가 된다.

SJF (Shortest Job First)

잡 길이가 짧은 것을 먼저 실행한다. 모든 잡이 동시에 도착하면 turnaround time이 최적이지만, 잡이 다른 시점에 도착하면 convoy effect가 여전히 발생한다.^[1:2] 예를 들어 A(100s, t=0 도착)가 실행 중일 때 B, C(10s, t=10 도착)가 와도 A가 끝날 때까지 대기해야 한다. 잡 실행 시간을 미리 알아야 한다는 가정이 현실에서는 성립하지 않는다.

STCF (Shortest Time-to-Completion First) / PSJF

SJF에 선점(Preemption)을 더한 정책이다. 새 잡이 도착하면 남은 실행 시간이 가장 짧은 잡을 즉시 실행한다. 잡이 임의 시간에 도착해도 turnaround time이 최적이지만, Response time이 나쁠 수 있다.^[1:3]

Round Robin (RR)

모든 잡을 time slice 단위로 순환 실행한다. Response time은 최적이지만, 각 잡을 조금씩 늘려가며 처리하므로 turnaround time이 매우 나쁘다.^[1:4]

Time slice 설정에는 트레이드오프가 있다: 너무 짧으면 context switch 비용이 전체 성능을 지배하고, 너무 길면 Response time이 저하된다. Context switch 비용은 레지스터 저장/복원만이 아니라 CPU 캐시/TLB/Branch predictor flush도 포함한다.^[1:5]

I/O Overlap

I/O 요청 시 CPU를 다른 잡에게 양보해 CPU와 I/O가 겹쳐 실행되게 한다(overlap). STCF에서는 I/O 잡의 각 CPU burst를 독립 sub-job으로 취급해 I/O-intensive 잡이 높은 우선순위를 유지하게 한다.^[1:6]

MLFQ (Multi-Level Feedback Queue)

SJF/STCF는 잡 실행 시간을 미리 알아야 하고, RR은 Response time은 좋지만 turnaround가 나쁘다. MLFQ는 잡의 과거 행동으로 미래를 예측해 두 목표를 동시에 달성하려는 정책이다 — "Learn from history": 잡의 과거 행동으로 단기/장기 잡을 구분하고 우선순위를 동적으로 조정한다.^[2]

[Q_high]  ──── 최고 우선순위 (interactive / 짧은 잡)
[Q_mid]
[Q_low]   ──── 최저 우선순위 (CPU-bound / 긴 잡)

5가지 기본 규칙

규칙	내용
Rule 1	Priority(A) > Priority(B)이면 A만 실행
Rule 2	Priority(A) = Priority(B)이면 A, B를 RR로 실행
Rule 3	새 잡 진입 시 → 최고 우선순위 큐에 배치
Rule 4a	할당 시간(allotment)을 다 쓰면 → 우선순위 1단계 강등
Rule 4b	할당 시간 내에 CPU를 자발 반납(I/O 등)하면 → 같은 우선순위 유지
Rule 5	주기 S마다 → 모든 잡을 최고 우선순위 큐로 강제 이동 (Priority Boost)

이 다섯 규칙은 MLFQ 정책을 구성한다.^[2:1]

flowchart TD
    A["새 잡 도착 → Q_high 배치"] --> B{"allotment 내에\nCPU 자발 반납?"}
    B -- "Yes (I/O 등)" --> C["같은 큐 유지\n→ interactive 잡으로 간주"]
    B -- "No (allotment 소진)" --> D["한 단계 강등\n→ CPU-bound 잡으로 간주"]
    D --> E["Q_low에서 CPU-bound 실행"]
    E --> F["주기 S 도달 → Priority Boost\n모든 잡 Q_high 복귀"]
    F --> A

3가지 문제와 해결

문제	원인	해결
Starvation	interactive 잡이 너무 많으면 CPU-bound 잡이 영구 대기	Rule 5 Priority Boost — 주기 S마다 전체 큐 리셋^[2:2]
Gaming	allotment 직전에 I/O를 발행해 항상 높은 우선순위 유지	allotment를 남은 잔량 누적 방식으로 추적 (Rule 4a/4b 통합)^[2:3]
행동 변화	CPU-bound 잡이 나중에 interactive로 전환되어도 낮은 우선순위 유지	Rule 5 Priority Boost — 정기적으로 모든 잡에 새 기회 부여^[2:4]

실제 구현 파라미터

큐 수는 Solaris에서 60개 우선순위 레벨을 쓴다. 시간 할당량(allotment)은 높은 큐일수록 짧은 time slice, 낮은 큐일수록 긴 time slice를 준다. Priority Boost 주기 S는 너무 길면 장기 실행 잡이 starvation에 빠지고, 너무 짧으면 interactive 잡이 CPU를 적절히 배분받지 못한다. 그래서 S는 보통 시스템 관리자가 적절한 값을 찾도록 남겨 두며, 최근에는 머신러닝 기반 자동 방법에 맡기는 경우가 늘고 있다.^[2:5]

알고리즘 요약 비교

알고리즘	Turnaround	Response	선점	잡 길이 필요
FIFO	나쁨 (convoy)	나쁨	X	X
SJF	최적 (동시 도착)	나쁨	X	O
STCF	최적 (임의 도착)	나쁨	O	O
RR	나쁨	최적	O	X
MLFQ	좋음 (SJF 근사)	좋음 (interactive 우선)	O	X

출처

테스트 질문

FIFO 스케줄러에서 Convoy Effect가 발생하는 상황은?
SJF가 최적이지만 현실에서 쓰기 어려운 이유는?
MLFQ가 SJF를 실행 시간 정보 없이 근사하는 원리는?
Priority Boost(Rule 5)가 없으면 MLFQ에서 어떤 문제가 생기는가?
Time slice를 매우 짧게 설정할 때의 단점은?

cpu-sched.pdf — Scheduling Metrics, FIFO/SJF/STCF/RR 각 절 (Convoy Effect, Time slice trade-off, Context switch 비용 포함). PDF 렌더링 도구(poppler)가 이 환경에 설치되어 있지 않아 원문 대조는 하지 못했다.^[3] ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
cpu-sched-mlfq.pdf — MLFQ 5 Rules, Starvation/Gaming/행동 변화 대응, 실제 구현 파라미터(Solaris 60 레벨) 절. PDF 렌더링 도구(poppler)가 이 환경에 설치되어 있지 않아 원문 대조는 하지 못했다.^[3:1] 단, 주기 S 서술은 추출 텍스트(p.7)로 대조했다: "If it is set too high, long-running jobs could starve; too low, and interactive jobs may not get a proper share of the CPU. As such, it is often left to the system administrator to find the right value – or in the modern world, increasingly, to automatic methods based on machine learning [A+17]." ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
출처 매핑 미확인 — 이번 포맷 변환 작업 환경에는 PDF 페이지 렌더 도구가 없어 cpu-sched.pdf/cpu-sched-mlfq.pdf 원문을 직접 대조하지 못했다. 본문의 수치·규칙·용어는 기존 Wiki 페이지(이전 ingest)의 서술을 그대로 유지했다. 다음에 poppler 또는 대체 PDF 렌더 도구를 확보하면 원문과 대조할 것. ↩︎ ↩︎