CPU 스케줄링 알고리즘: FCFS·SJF·Round-Robin·MLFQ 선택 기준
FCFS, SJF/SRTF, Round-Robin, MLFQ의 선점 방식과 대기 시간, 응답성, 기아 위험, 운영 튜닝 기준을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
CPU 시간을 배분할 때 보는 지표
CPU 스케줄러는 제한된 CPU 시간을 어떤 작업에 먼저 줄지 결정한다. 이 선택은 지연 시간, 처리량, 사용자 체감 품질에 직접 영향을 준다.
판단 기준은 평균 대기 시간만이 아니다. 작업이 준비 큐에 머문 시간을 뜻하는 대기 시간, 도착부터 완료까지의 반환 시간, 처음 CPU를 할당받기까지의 응답 시간, 그리고 컨텍스트 스위치 오버헤드를 함께 봐야 한다. 목표는 대기 시간을 낮추면서 응답성과 처리량, 공정성을 확보하고 기아(starvation)를 막는 데 있다.
스케줄러는 장기·중기·단기로 나뉘며, 여기서 다루는 대상은 단기 CPU 스케줄러다. 실행 중인 작업을 중단시킬 수 있는 선점형(preemptive)과, 작업이 CPU를 반납할 때까지 기다리는 비선점형(non-preemptive)의 차이도 정책을 구분하는 핵심 기준이다.
고정 우선순위 방식은 단순하지만 낮은 우선순위 작업이 오래 밀릴 수 있다. 적응형 피드백 방식은 최근 실행 패턴을 반영해 우선순위를 바꾸며, 에이징(aging)으로 장기 대기 작업의 우선순위를 높여 기아를 완화한다.
도착 순서를 그대로 따르는 FCFS
FCFS(First-Come, First-Served)는 준비 큐에 먼저 들어온 작업부터 실행하는 비선점형 정책이다. 구현이 단순하고 컨텍스트 스위치가 적다는 점이 장점이다.
대신 긴 작업이 앞에 놓이면 뒤의 짧은 작업까지 함께 기다리는 Convoy 효과가 발생할 수 있다. 이 경우 평균 대기 시간이 늘고 응답 분산도 커진다.
짧은 작업을 우대하는 SJF와 SRTF
SJF(Shortest Job First)는 실행 시간이 가장 짧은 작업을 먼저 고르는 비선점형 방식이다. SRTF(Shortest Remaining Time First)는 남은 실행 시간이 더 짧은 작업이 들어오면 현재 작업을 선점하는 방식이다.
완전한 실행 시간 정보를 가정하면 SJF는 평균 대기 시간을 최소화하는 이론적 최적성을 갖는다. 하지만 실제 환경에서는 실행 시간을 추정해야 하며, 추정 오차가 정책의 효과를 떨어뜨릴 수 있다. 긴 작업이 계속 밀리는 기아 위험도 있으므로 에이징 같은 보완책이 필요하다.
quantum으로 순환하는 Round-Robin
Round-Robin은 각 작업에 고정 시간 할당량(quantum)을 주고 순서대로 CPU를 배분하는 선점형 정책이다. 공정성을 확보하기 쉽고 응답 시간이 짧아 대화형 워크로드에 적합하다.
quantum이 너무 크면 FCFS에 가까워진다. 반대로 너무 작으면 작업 전환이 잦아져 컨텍스트 스위치 오버헤드가 커진다. 따라서 응답성과 전환 비용 사이에서 quantum을 조정해야 한다.
CPU 사용 패턴에 반응하는 MLFQ
MLFQ(Multi-Level Feedback Queue)는 여러 우선순위 큐를 두고 최근 CPU 사용 패턴에 따라 작업을 승급하거나 강등한다. 짧게 실행되고 상호작용이 많은 태스크는 높은 우선순위를 유지하고, 배치형 작업은 점차 낮은 큐로 내려간다.
큐 수, 각 큐의 quantum, 승급·강등 규칙, 에이징 주기는 모두 정책의 일부다. 이 값이 맞지 않으면 심한 기아나 과도한 선점이 생길 수 있다.
스케줄러 이벤트에서 완료까지
새 태스크 도착, I/O 완료, 타이머 인터럽트가 스케줄러의 입력이 된다. 정책은 FCFS, SJF, RR, MLFQ 가운데 하나의 기준으로 다음 후보를 고르고, 디스패치와 실행 뒤에는 완료 또는 재큐잉을 결정한다. MLFQ라면 이 과정에서 우선순위도 조정한다.
타임 슬라이스를 0으로 설정하지 않도록 막아야 하며, 우선순위 역전이 발생하면 임시 승급(priority inheritance)을 적용한다.
워크로드가 정책을 가르는 환경
데스크톱과 모바일 OS에서는 RR 또는 CFS(가중 공정 공유) 기반 정책을 사용하고, 상호작용 프로세스에는 짧은 quantum을 적용하며 백그라운드 앱에는 낮은 가중치를 배정할 수 있다. 배터리와 발열 제약이 있는 환경에서는 컨텍스트 스위치 빈도도 관리 대상이다.
웹 서버와 애플리케이션 서버처럼 짧은 요청 비중이 높은 환경에서는 RR 또는 MLFQ가 tail latency 완화에 쓰일 수 있다. 컨테이너 런타임에서는 CPU shares/weights와 결합하고 cgroup 스케줄링과 정책 일관성을 맞춘다.
배치·HPC·큐잉 시스템에서는 FCFS와 백필(backfilling)을 조합해 장기 점유를 줄일 수 있다. 과거 실행 시간을 이용한 예측 스케줄링으로 SJF와 유사한 효과를 노리기도 한다. 소프트 실시간 요구에서는 MLFQ와 고정 우선순위를 혼합하고 상위 큐를 예약하며, 우선순위 역전 방지 메커니즘을 함께 둔다.
정책별 운영상 차이
| 알고리즘 | 성능(평균 대기/응답) | 확장성(다중 작업) | 일관성(응답 분산) | 안정성(기아/역전) | 운영 편의(튜닝) |
|---|---|---|---|---|---|
| FCFS | 낮음~보통, Convoy 영향 | 높음, 오버헤드 최소 | 낮음, 긴 꼬리 발생 | 기아 낮음, 역전 낮음 | 매우 쉬움 |
| SJF/SRTF | 높음(이론 최적), SRTF가 유리 | 보통, 추정 비용 발생 | 보통, 추정 품질 의존 | 기아 위험, 에이징 필요 | 보통(추정·에이징) |
| Round-Robin | 보통, 응답 빠름 | 높음, 단 컨텍스트 스위치 증가 | 보통, quantum 의존 | 기아 낮음 | 쉬움(quantum 튜닝) |
| MLFQ | 높음(대화형에 유리) | 높음, 정책 복잡 | 보통~높음, 정책 의존 | 기아 위험, 에이징 필수 | 어려움(파라미터 다수) |
RR 또는 MLFQ를 적용하면 I/O 빈도가 높은 대화형 워크로드에서 quantum 210ms 구간 기준 P95 응답 시간이 2050% 개선될 수 있다. SRTF는 짧은 작업 비중이 높을수록 평균 대기 시간 최적화 효과가 커진다.
FCFS와 비교하면 SJF/SRTF는 처리량 향상을 기대할 수 있지만, 실행 시간 추정이 실패하면 변동성이 늘어난다. MLFQ는 상호작용 작업과 배치 작업이 섞인 환경에서 사용자 체감 품질과 처리량의 균형을 맞추는 데 쓰인다.
운영 중에는 컨텍스트 스위치 비용(cs)과 작업 평균 CPU 버스트(b)를 비교해 cs/b ≤ 5%를 유지하도록 quantum을 조정한다. 장기 대기 태스크의 기아를 막기 위해 우선순위 상승 주기는 예를 들어 수십~수백 ms 범위에서 설정한다. 대기·응답 지표의 P50/P95/P99를 관측하면서 파라미터를 점진적으로 바꾸고, 락 경합 구간에는 priority inheritance 또는 ceiling을 적용한다.
Round-Robin 동작을 확인하는 코드
전제조건은 Python 3.10+이며, 입력은 (이름, 도착시각, CPU버스트) 형식이다. 출력은 평균 응답·대기·반환 시간이다.
# python 3.10+
from collections import deque
def rr(jobs, q=4):
# jobs: list of (name, arrival, burst)
time = 0
ready = deque()
i = 0
n = len(jobs)
rem = {name: burst for name, _, burst in jobs}
first_resp = {}
wait_time = {name: 0 for name, _, _ in jobs}
last_run_end = {name: 0 for name, _, _ in jobs}
finish = {}
jobs = sorted(jobs, key=lambda x: x[1])
def enqueue_arrivals(t):
nonlocal i
while i < n and jobs[i][1] <= t:
ready.append(jobs[i][0])
last_run_end[jobs[i][0]] = t
i += 1
enqueue_arrivals(time)
while ready or i < n:
if not ready:
time = jobs[i][1]
enqueue_arrivals(time)
name = ready.popleft()
if name not in first_resp:
first_resp[name] = time - next(a for n2, a, _ in jobs if n2 == name)
waited = time - last_run_end[name]
if waited > 0:
wait_time[name] += waited
run = min(q, rem[name])
time += run
rem[name] -= run
enqueue_arrivals(time)
if rem[name] == 0:
finish[name] = time
else:
last_run_end[name] = time
ready.append(name)
def metric(avg_of):
return sum(avg_of(name) for name, _, _ in jobs) / n
avg_resp = metric(lambda nm: first_resp[nm])
avg_wait = metric(lambda nm: wait_time[nm])
avg_turn = metric(lambda nm: finish[nm] - next(a for n2, a, _ in jobs if n2 == nm))
return avg_resp, avg_wait, avg_turn
if __name__ == "__main__":
jobs = [("A",0,5), ("B",1,2), ("C",2,1), ("D",3,3)]
print("avg_response, avg_wait, avg_turnaround =", rr(jobs, q=2))q를 줄이면 응답 시간은 감소하고 컨텍스트 스위치 오버헤드는 증가한다. q를 늘리면 동작은 FCFS에 수렴한다.
선택은 워크로드와 관측 결과에서 시작한다
대화형 서비스에는 RR 또는 MLFQ를 기본 후보로 두고 P95/P99를 기준으로 조정한다. 배치 처리나 균질한 작업에는 SJF/SRTF를 먼저 검토하되 예측 모델과 에이징을 함께 고려한다. 단순한 큐와 리소스 제약 환경은 FCFS로 시작하고, 필요하면 backfilling을 보강할 수 있다.