CPU 스케줄링은 어떻게 동작하며, 흔한 알고리즘에는 무엇이 있는가?

Question

IT Interview Practice · Accepted Answer

**CPU 스케줄링(CPU scheduling)**은 준비된 thread 중 *어느* 것에게 CPU를 *다음에*, 그리고 *얼마나 오래* 줄지에 대한 kernel의 결정이다. 보통 실행 가능한 thread가 core보다 많으므로, **scheduler**는 이들을 다중화(multiplex)하며 서로 충돌하는 목표 — **throughput**, **낮은 latency / 응답 시간**, **공정성** — 의 균형을 맞추는 동시에 **starvation**(굶주림)을 피하려 한다.

## 흔한 알고리즘

```text
FCFS (first-come, first-served) → simple, but one long job blocks everyone (convoy effect)
SJF  (shortest job first)       → optimal avg wait, but needs to know job length; can starve long jobs
Round-robin (RR)                → each job a fixed TIME SLICE (quantum), cycle through → fair, good latency
Priority                        → highest priority first → can STARVE low priority (fix: aging)
MLFQ (multi-level feedback)     → several priority queues; jobs that use a full quantum sink,
                                  interactive jobs that yield stay high → approximates SJF without knowing lengths
```

**Round-robin**은 핵심 조절 손잡이인 **quantum**을 잘 보여 준다:

```text
quantum too SMALL → fair & responsive, but lots of context-switch overhead
quantum too LARGE → less overhead, but degrades toward FCFS (poor responsiveness)
```

## 실제 scheduler

Linux의 오랜 기본값은 **CFS(Completely Fair Scheduler)**였다: 고정된 슬라이스 대신, 각 task의 **virtual runtime(vruntime)**을 추적하고 지금까지 CPU를 가장 적게 받은 thread를 항상 실행하되, 그 task의 **nice** 값으로 가중치를 준다 — "모두가 공정한 몫을 받는다"에 근사하는 것이다. vruntime을 키로 하는 red-black tree를 쓰므로 다음 task를 고르는 데 O(log n)이 든다. (더 새로운 kernel은 같은 공정성 목표에 더 촘촘한 latency 한계를 더한 개선판 EEVDF를 쓴다.)

**Preemptive vs cooperative:** 현대 OS는 **preemptive**하다 — timer interrupt로 scheduler가 강제로 CPU를 되찾을 수 있으므로 한 thread가 core를 독점할 수 없다.

## 왜 중요한가

스케줄링은 사용자가 체감하는 latency와 throughput을 직접 좌우한다. 면접관은 당신이 트레이드오프를 이해하는지 보려고 이 주제를 파고든다 — 왜 인터랙티브 워크로드는 짧은 quantum이나 priority boost를 원하는지, 왜 priority scheduling에는 starvation을 막기 위한 **aging**이 필요한지, 그리고 MLFQ/CFS가 job 길이를 미리 알지 못한 채 어떻게 좋은 인터랙티브 동작을 얻는지. 이는 `nice`, real-time priority를 조율하고, 굶주리거나 버벅이는 서비스를 진단하는 데 쓰는 사고 모델이기도 하다.

흔한 알고리즘

실제 scheduler

왜 중요한가

관련 질문