CPU 스케줄링 — FCFS부터 CFS까지, 면접에서 깊이 있게 답하기
Ready 큐에 프로세스가 여러 개 쌓여 있을 때, 누구한테 CPU를 줄 것인가 — 이게 CPU 스케줄링입니다.
각 알고리즘은 독립적으로 존재하는 게 아닙니다. FCFS의 문제(Convoy Effect)를 해결하려고 SJF가 나왔고, SJF의 문제(기아)를 해결하려고 Round Robin이 나왔습니다. 이 인과 흐름을 따라가봅니다.
선점형 vs 비선점형
스케줄링을 이해하려면 이 구분부터 잡아야 합니다.
| 비선점형 (Non-preemptive) | 선점형 (Preemptive) | |
|---|---|---|
| 동작 | 프로세스가 CPU를 자발적으로 놓을 때까지 기다림 | OS가 강제로 CPU를 빼앗을(선점할) 수 있음 |
| 장점 | 구현이 단순, 컨텍스트 스위칭 적음 | 응답 시간이 짧음, 대화형 시스템에 적합 |
| 단점 | 하나가 오래 잡으면 나머지 전부 대기 | 컨텍스트 스위칭 오버헤드 발생 |
교착 상태 글에서 다룬 ** 비선점(No Preemption)** 조건이 기억나시죠? 데드락 발생 조건 중 하나가 "자원을 강제로 빼앗을 수 없는 것"이었습니다. 스케줄링에서의 비선점도 같은 맥락입니다 — CPU라는 자원을 빼앗느냐 마느냐의 차이.
현대 OS는 전부 선점형입니다. 비선점형은 한 프로세스가 CPU를 10초간 잡으면 나머지가 10초간 멈추니까요.
비선점형 스케줄링
FCFS (First-Come, First-Served)
가장 단순합니다. 먼저 온 순서대로 처리. 큐에 들어온 순서 그대로.
프로세스 도착 시간 실행 시간
P1 0 24
P2 1 3
P3 2 3
실행 순서: P1(0~24) → P2(24~27) → P3(27~30)
평균 대기 시간: (0 + 23 + 25) / 3 = 16
P2와 P3는 3밀리초면 끝나는 작업인데, P1이 24밀리초 동안 CPU를 잡고 있으니까 한참 기다려야 합니다.
이게 Convoy Effect 입니다. 느린 프로세스 하나가 뒤의 빠른 프로세스들을 전부 막아버리는 현상. 마트에서 카트 가득 채운 사람 뒤에 음료수 하나 들고 줄 선 상황이랑 똑같습니다.
SJF (Shortest Job First)
실행 시간이 가장 짧은 프로세스부터 처리합니다.
프로세스 도착 시간 실행 시간
P1 0 24
P2 1 3
P3 2 3
실행 순서 (비선점): P1(0~24) → P2(24~27) → P3(27~30)
어라, P1이 먼저 도착했으니까 비선점 SJF에서는 결과가 FCFS랑 같습니다. P1이 이미 실행 중이면 못 빼앗으니까요.
그래서 선점형 버전인 SRTF (Shortest Remaining Time First) 가 나옵니다. 새 프로세스가 도착했을 때 남은 시간이 더 짧으면 현재 프로세스를 밀어냅니다.
SRTF 실행:
t=0: P1 시작 (남은 24)
t=1: P2 도착 (남은 3) → P1보다 짧으니 P2 실행
t=2: P3 도착 (남은 3) → P2(남은 2)가 더 짧으니 P2 계속
t=4: P2 완료 → P3 실행 (남은 3)
t=7: P3 완료 → P1 재개 (남은 23)
t=30: P1 완료
평균 대기 시간: ((30-24-0) + (4-3-1) + (7-3-2)) / 3 = (6+0+2) / 3 = 2.67
평균 대기 시간은 최적이지만, 치명적인 문제가 있습니다. 실행 시간을 미리 알 수 없다 는 것. 프로세스가 얼마나 걸릴지 어떻게 압니까? 과거 실행 이력으로 추정하는 방법이 있지만, 정확하지 않습니다.
그리고 또 하나 — 짧은 프로세스가 계속 들어오면 긴 프로세스는 영원히 실행을 못 합니다. 이게 기아 상태(Starvation) 입니다. 교착 상태 글에서 다뤘던 그 기아 상태. 데드락은 모든 프로세스가 멈추지만, 기아는 특정 프로세스만 계속 밀리는 겁니다.
Priority Scheduling
각 프로세스에 우선순위를 부여하고, 높은 우선순위부터 실행합니다.
프로세스 우선순위 (낮을수록 높음) 실행 시간
P1 3 10
P2 1 1
P3 4 2
P4 2 5
실행 순서: P2 → P4 → P1 → P3
SJF도 사실 우선순위 스케줄링의 특수한 형태입니다. "실행 시간이 짧을수록 우선순위가 높다"는 기준을 쓰는 거니까요.
역시 기아 문제가 발생합니다. 해결법은 에이징(Aging) — 대기 시간이 길어질수록 우선순위를 점진적으로 올려줍니다. 교착 상태 글에서 기아 상태의 해결책으로 언급했던 바로 그 기법입니다.
선점형 스케줄링
Round Robin (RR)
모든 프로세스에게 동일한 ** 타임 퀀텀(time quantum)**을 부여하고 돌아가며 실행합니다. 타임 퀀텀이 끝나면 Ready 큐 맨 뒤로 보내고 다음 프로세스를 실행.
타임 퀀텀 = 4
프로세스 실행 시간
P1 24
P2 3
P3 3
실행: P1(4) → P2(3) → P3(3) → P1(4) → P1(4) → P1(4) → P1(4) → P1(4)
타임 퀀텀의 크기가 핵심입니다.
- ** 너무 크면 **: FCFS랑 다를 바 없음
- ** 너무 작으면 **: 컨텍스트 스위칭이 너무 자주 발생
이전 글에서 컨텍스트 스위칭의 비용을 다뤘습니다 — 레지스터 저장/복원, TLB 플러시, 캐시 미스 폭증. 타임 퀀텀이 1ms인데 컨텍스트 스위칭에 0.5ms가 걸리면, CPU 시간의 33%를 스위칭에 낭비하는 셈입니다.
일반적으로 10~100ms 정도가 적절하다고 봅니다. 컨텍스트 스위칭 시간의 비중이 전체 실행 시간의 10% 이하가 되도록.
Multilevel Queue
프로세스를 ** 여러 그룹으로 나누고 **, 각 그룹마다 별도의 큐와 스케줄링 알고리즘을 적용합니다.
┌─────────────────────────┐ ← 최고 우선순위
│ 시스템 프로세스 (FCFS) │
├─────────────────────────┤
│ 대화형 프로세스 (RR) │
├─────────────────────────┤
│ 배치 프로세스 (FCFS) │
└─────────────────────────┘ ← 최저 우선순위
큐 간에도 스케줄링이 필요합니다. 보통 상위 큐가 비어야 하위 큐가 실행됩니다. 문제는 역시 기아 — 대화형 프로세스가 계속 들어오면 배치 프로세스는 영원히 대기합니다.
큐 간 CPU 시간을 비율로 나누는 방식도 있습니다. 시스템 큐 50%, 대화형 큐 40%, 배치 큐 10%처럼요.
Multilevel Feedback Queue (MLFQ)
멀티레벨 큐의 가장 큰 문제는 ** 프로세스가 큐 사이를 이동할 수 없다 **는 것이었습니다. MLFQ는 이걸 해결합니다.
Queue 0 (RR, 퀀텀=8ms) ← 새 프로세스는 여기서 시작
│ 타임 퀀텀 내에 완료 못 하면
▼
Queue 1 (RR, 퀀텀=16ms)
│ 타임 퀀텀 내에 완료 못 하면
▼
Queue 2 (FCFS) ← CPU 집중 프로세스가 여기로
동작 원리:
- 새 프로세스는 최상위 큐(짧은 퀀텀)에 진입
- 타임 퀀텀 내에 끝나면 그대로 종료 — I/O 바운드 프로세스는 대부분 여기서 끝남
- 못 끝나면 한 단계 아래 큐로 강등 — 점점 더 긴 퀀텀을 받지만 우선순위는 떨어짐
- CPU 바운드 프로세스는 결국 최하위 큐로 내려감
이 방식이 영리한 이유는 ** 프로세스의 성격을 자동으로 분류 **한다는 겁니다. 짧게 끝나는 대화형/I/O 프로세스는 높은 우선순위를 유지하고, CPU를 오래 쓰는 프로세스는 자연스럽게 낮은 우선순위로 갑니다.
기아 문제도 해결합니다. 일정 시간이 지나면 ** 모든 프로세스를 최상위 큐로 올려버리는** 방식(에이징)으로요.
대부분의 범용 OS가 MLFQ의 변형을 사용합니다.
Linux CFS (Completely Fair Scheduler)
Linux 2.6.23부터 도입된 기본 스케줄러입니다. "완전히 공정한 스케줄러"라는 이름답게, CPU 시간을 모든 프로세스에게 공평하게 나눠주는 게 목표입니다.
핵심 아이디어: vruntime
CFS는 각 프로세스의 ** 가상 실행 시간(vruntime)**을 추적합니다. 실제 실행 시간이 아니라, 가중치가 적용된 가상 시간.
vruntime = 실제 실행 시간 × (기본 가중치 / 프로세스 가중치)
- nice 값이 0(기본)이면: vruntime = 실제 실행 시간
- nice 값이 낮으면(높은 우선순위): vruntime이 천천히 증가 → 더 많이 실행됨
- nice 값이 높으면(낮은 우선순위): vruntime이 빨리 증가 → 덜 실행됨
스케줄러는 항상 vruntime이 가장 작은 프로세스 를 선택합니다. CPU를 가장 적게 쓴 프로세스한테 우선권을 주는 거죠.
Red-Black Tree
vruntime이 가장 작은 프로세스를 빠르게 찾아야 하니까, CFS는 Red-Black Tree 에 프로세스를 저장합니다. 가장 왼쪽 노드가 vruntime이 가장 작은 프로세스이고, 이걸 꺼내는 데 O(log n)입니다.
[vruntime=15]
/ \
[vruntime=10] [vruntime=20]
/ \
[vruntime=5] [vruntime=12]
← 가장 왼쪽 = 다음에 실행할 프로세스
기존의 O(1) 스케줄러가 O(1)이었는데 왜 O(log n)인 CFS로 바꿨을까? — O(1) 스케줄러는 휴리스틱 기반이라 공정성이 떨어지고 코드가 복잡했습니다. CFS는 단순한 원칙(vruntime이 작은 놈 먼저)으로 더 나은 공정성을 달성합니다.
CFS의 타임 슬라이스
CFS에는 고정된 타임 퀀텀이 없습니다. 대신 스케줄링 주기(scheduling period) 안에서 각 프로세스의 가중치 비율로 시간을 나눕니다.
실행 가능한 프로세스가 5개, 스케줄링 주기가 20ms이면:
- 가중치가 동일하면 각각 4ms씩
- 가중치가 다르면 비율에 따라 분배
프로세스가 너무 많아지면 각자의 슬라이스가 지나치게 짧아질 수 있습니다. 그래서 ** 최소 단위(min_granularity)**를 두고, 이보다 짧아지면 스케줄링 주기를 늘립니다.
컨텍스트 스위칭 비용 — 다시 한번 짚기
프로세스와 스레드 글에서 다뤘지만, 스케줄링과 직접 연결되는 내용이라 한 번 더 정리합니다.
직접 비용
- 레지스터 저장/복원
- 메모리 맵 전환 (프로세스 전환 시)
- 커널 모드 ↔ 사용자 모드 전환
간접 비용 (이게 더 큼)
- **TLB 플러시 **: 프로세스가 바뀌면 TLB(주소 변환 캐시)가 무효화됨. 전환 직후 모든 메모리 접근에서 TLB 미스 발생
- **CPU 캐시 오염 **: 이전 프로세스의 데이터가 캐시에 있고, 새 프로세스의 데이터는 메모리에서 다시 가져와야 함
- ** 파이프라인 플러시 **: CPU 명령어 파이프라인이 비워짐
스레드 간 전환이 프로세스 간 전환보다 싼 이유는, 같은 주소 공간을 쓰기 때문에 TLB를 날릴 필요가 없다 는 겁니다. 캐시 미스도 상대적으로 적고요.
"컨텍스트 스위칭 비용을 줄이는 방법은 뭔가요?" 핵심만 정리하면:
- 스레드를 쓴다 — 프로세스 전환보다 가벼움
- ** 스레드 수를 적절히 유지한다** — 코어 수보다 훨씬 많으면 스위칭만 늘어남
- ** 경량 스레드(코루틴, 가상 스레드)를 쓴다** — 커널 개입 없이 사용자 공간에서 전환
주의할 점
Convoy Effect
FCFS에서 CPU burst가 긴 프로세스 하나가 뒤의 짧은 프로세스들을 전부 지연시키는 현상입니다. I/O 바운드 프로세스들이 CPU 바운드 프로세스 뒤에서 대기하면, I/O 장치도 놀게 됩니다. CPU 이용률과 I/O 이용률이 동시에 떨어지는 거죠.
해결법: 선점형 스케줄링(Round Robin 등)을 쓰면 됩니다.
Starvation 해결법
** 에이징(Aging)**입니다. 대기 시간이 길어질수록 우선순위를 점진적으로 올려줍니다. MLFQ에서는 일정 주기로 모든 프로세스를 최상위 큐로 끌어올리는 방식을 씁니다.
CFS에서는 vruntime이 자연스럽게 에이징 역할을 합니다. 오래 기다린 프로세스는 vruntime이 작으니까 자동으로 먼저 실행됩니다.
실시간 스케줄링 vs 일반 스케줄링
일반 스케줄링은 ** 처리량(throughput)**과 ** 공정성 **이 목표지만, 실시간 스케줄링은 ** 데드라인을 지키는 것 **이 목표입니다.
| Hard Real-time | Soft Real-time | |
|---|---|---|
| 데드라인 | 절대 못 어김 (어기면 시스템 실패) | 가끔 어겨도 됨 (품질 저하) |
| 예시 | 항공기 제어, ABS 브레이크 | 영상 스트리밍, VoIP |
Linux에서 실시간 프로세스는 CFS가 아니라 별도의 실시간 스케줄링 클래스를 사용합니다.
- SCHED_FIFO: 선입선출, 같은 우선순위 내에서 선점 없음
- SCHED_RR: 같은 우선순위 내에서 Round Robin
실시간 프로세스는 일반 프로세스(SCHED_NORMAL/CFS)보다 항상 먼저 실행됩니다.
"CPU 바운드 프로세스와 I/O 바운드 프로세스를 어떻게 구분하나요?"
- **CPU 바운드 **: CPU burst가 길고, I/O 요청이 드물다. 행렬 연산, 영상 인코딩 같은 작업.
- **I/O 바운드 **: CPU burst가 짧고, I/O 요청이 잦다. 웹 서버, DB 쿼리 처리 같은 작업.
MLFQ는 이걸 자동으로 판별합니다. 타임 퀀텀을 다 쓰면 CPU 바운드로 판단하고 강등, 타임 퀀텀 내에 I/O 요청으로 자발적으로 양보하면 I/O 바운드로 판단하고 우선순위를 유지합니다.
"멀티코어 환경에서 스케줄링은 어떻게 달라지나요?"
코어가 여러 개면 고려할 게 늘어납니다.
- ** 로드 밸런싱 **: 특정 코어에 프로세스가 몰리지 않도록 분산
- ** 캐시 친화성(Cache Affinity)**: 프로세스를 이전에 실행했던 코어에 다시 배치하면, 캐시에 데이터가 남아 있어서 빠름
- **NUMA 인식 **: 메모리가 코어마다 가깝고 먼 게 있으니까, 가까운 메모리를 가진 코어에 배치
Linux CFS는 ** 스케줄링 도메인** 개념으로 이를 처리합니다. 같은 코어에서 먼저 찾고, 같은 소켓 → 같은 NUMA 노드 순서로 범위를 넓혀가며 밸런싱합니다.
파생되는 개념들
- ** 가상 메모리** — 페이징, 세그멘테이션, 페이지 폴트. TLB 플러시와 직결됨
- IPC (Inter-Process Communication) — 프로세스 간 통신. 프로세스가 독립된 메모리를 가지기 때문에 필요
- ** 동기화 도구 (뮤텍스/세마포어)** — 스레드 간 자원 공유 시 경쟁 조건 방지. 교착 상태와 직결됨
- ** 인터럽트와 시스템 콜** — 선점형 스케줄링이 타이머 인터럽트로 동작하는 원리
- ** 프로세스 동기화** — 임계 영역, 모니터, CAS 같은 동시성 제어 기법