CPU 스케줄링(CPU Scheduling)
1. 개요
가. 정의
CPU 스케줄링은 준비 상태(ready)의 여러 프로세스·스레드 중 다음에 CPU를 점유할 하나를 선택하고, 디스패처가 실제로 문맥을 전환해 실행 흐름을 넘기는 운영체제의 핵심 자원 관리 기법이다.
현대 운영체제가 CPU 스케줄링을 두는 근본 이유는 다중 프로그래밍(multiprogramming) 때문이다. 단일 CPU는 한 순간에 하나의 명령만 실행할 수 있는데, 프로세스는 실행 도중 I/O를 요청하며 수시로 멈춘다. 만약 한 프로세스가 디스크 응답을 기다리는 동안 CPU가 함께 놀아버리면 값비싼 연산 자원이 낭비된다. 스케줄러는 이 대기 구간을 포착해 다른 준비된 프로세스에 CPU를 넘김으로써, 사용자에게는 여러 작업이 동시에 돌아가는 것처럼 보이게 하고 전체 처리량을 끌어올린다.
나. 등장 배경과 필요성
초기 일괄처리(batch) 시대에는 작업을 제출 순서대로 하나씩 끝까지 돌렸기 때문에 스케줄링이라 부를 것이 사실상 없었다. 그러나 시분할(time-sharing) 시스템이 등장하면서 여러 사용자가 하나의 CPU를 공유하게 되었고, "짧은 작업이 긴 작업 뒤에 갇혀 하염없이 기다리는" 문제, "대화형 작업이 즉각 반응하지 않는" 문제가 전면에 드러났다. CPU 스케줄링은 이처럼 한정된 처리 자원을 다수의 경쟁 작업에 어떻게 공정하고 효율적으로 분배할 것인가라는 질문에 대한 해답으로 발전해 왔다. 오늘날 스마트폰부터 대규모 서버·실시간 제어기까지, 응답성·공정성·전력효율을 동시에 요구하는 환경에서 스케줄러의 품질은 시스템 체감 성능을 좌우하는 결정적 요소다.
CPU 스케줄링이 효과를 내는 전제는 CPU 버스트와 I/O 버스트의 교대다. 프로그램 실행은 "CPU를 쓰는 구간(계산)"과 "I/O를 기다리는 구간"이 번갈아 나타나는데, 계산 중심(CPU-bound) 작업과 입출력 중심(I/O-bound) 작업이 섞여 있을 때 스케줄러가 이들을 잘 엮으면 CPU와 I/O 장치가 동시에 바쁘게 돌아 자원 활용이 극대화된다. 따라서 좋은 스케줄링은 단순히 "누굴 먼저"가 아니라 작업의 성격을 읽어 장치 간 병렬성을 최대화하는 일이기도 하다.
다. CPU 스케줄링의 특징
CPU 스케줄링은 몇 가지 본질적 특징을 지닌다. 첫째, 빈번성이다. 단기 스케줄러는 수 밀리초마다 호출되므로 선택 알고리즘 자체가 가벼워야 하며, 선택 비용이 크면 그 자체가 오버헤드가 된다(그래서 리눅스 CFS도 O(log n) 자료구조를 쓴다). 둘째, 무관용의 자원 분배로, CPU는 한 순간에 하나만 점유할 수 있어 선택은 곧 나머지의 대기를 의미한다. 셋째, 예측 불확실성이다. 다음 CPU 버스트 길이나 I/O 시점을 정확히 알 수 없으므로 과거 행동에 기반한 추정·적응이 불가피하다. 넷째, 정책과 메커니즘의 분리로, "누구를 고를지(정책)"와 "어떻게 문맥을 바꿀지(디스패처 메커니즘)"를 분리 설계해 다양한 정책을 같은 하부 구조 위에서 교체할 수 있게 한다.
2. 프로세스 상태 전이와 스케줄링 계층
프로세스는 생성에서 종료까지 여러 상태를 오가며, 스케줄링은 바로 이 상태 전이의 특정 길목에서 개입한다. 아래는 전형적인 5-상태 모델이다.
stateDiagram-v2
[*] --> New
New --> Ready: "승인(admit)"
Ready --> Running: "디스패치(scheduler)"
Running --> Ready: "선점(time-out/preempt)"
Running --> Waiting: "I/O·이벤트 대기"
Waiting --> Ready: "I/O 완료"
Running --> Terminated: "종료(exit)"
Terminated --> [*]
여기서 Running→Ready(선점) 전이가 가능한지가 스케줄링 정책의 성격을 가른다. 선점이 허용되면 실행 중인 프로세스라도 더 급한 작업이나 타임 슬라이스 만료에 의해 CPU를 빼앗길 수 있고, 허용되지 않으면 스스로 I/O를 요청하거나 종료할 때까지 CPU를 쥔다. 또한 Waiting→Ready 전이 직후가 I/O 중심 작업에 다시 기회를 주는 중요한 결정 지점이 된다.
스케줄링은 시간 척도에 따라 세 계층으로 나뉜다. 아래 구조도는 각 스케줄러의 역할과 위치를 보여준다.
flowchart LR
J["작업 큐(new)"] -->|"장기 스케줄러<br/>다중프로그래밍 정도 결정"| R["준비 큐(ready)"]
R -->|"단기 스케줄러<br/>밀리초 단위 선택"| D["디스패처"]
D --> C["CPU 실행(running)"]
C -->|"I/O 요청"| W["대기 큐(waiting)"]
W -->|"완료"| R
C -.->|"스왑 아웃"| M["중기 스케줄러<br/>메모리 과부하 조절"]
M -.->|"스왑 인"| R
디스패처는 선택 직후 다음 일들을 순차 수행하며, 이 전 과정에 걸리는 시간이 디스패치 지연이다.
- 문맥 저장·복원: 떠나는 프로세스의 레지스터·PC를 PCB에 저장하고, 들어오는 프로세스의 상태를 적재한다.
- 모드 전환: 커널 모드에서 사용자 모드로 전환한다.
- 주소공간 전환: 페이지 테이블·TLB를 새 프로세스 기준으로 교체한다(가상주소 보호).
- 점프: 복원한 프로그램 카운터 위치로 분기해 사용자 코드를 재개한다.
장기 스케줄러(long-term)는 어떤 작업을 메모리에 올려 활성화할지를 결정해 다중 프로그래밍의 정도를 조절하고, 중기 스케줄러(medium-term)는 메모리 압박 시 일부 프로세스를 디스크로 스왑 아웃했다가 되돌리며 부하를 평탄화한다. 우리가 보통 "CPU 스케줄링"이라 부르는 것은 밀리초 단위로 가장 빈번히 동작하는 단기 스케줄러(short-term)이며, 선택된 프로세스로 문맥을 실제 전환하는 역할은 디스패처(dispatcher)가 맡는다. 디스패처가 소모하는 시간을 디스패치 지연(dispatch latency)이라 하며, 이 오버헤드가 크면 스케줄링을 자주 할수록 손해이므로 타임 슬라이스 설계와 직결된다.
3. 스케줄링 성능 기준과 선점 여부
스케줄러를 평가하는 척도는 서로 상충(trade-off)한다는 점이 핵심이다. 대표 지표는 다음과 같다.
- CPU 이용률(utilization): CPU가 쉬지 않고 일하는 비율. 높을수록 좋다.
- 처리량(throughput): 단위 시간당 완료 작업 수. 일괄처리 서버가 중시한다.
- 반환시간(turnaround time): 작업 제출부터 완료까지의 총 시간.
- 대기시간(waiting time): 준비 큐에서 기다린 시간의 합. 스케줄러가 직접 줄일 수 있는 양이다.
- 응답시간(response time): 요청 후 첫 반응이 나올 때까지의 시간. 대화형·실시간 시스템의 핵심이다.
처리량을 높이려 긴 타임 슬라이스를 쓰면 문맥 전환 오버헤드는 줄지만 응답성은 나빠지고, 반대로 짧게 쪼개면 대화형 반응은 빨라지지만 전환 비용이 늘어 이용률이 떨어진다. 따라서 어떤 지표를 최우선으로 삼느냐가 곧 정책 선택이며, 범용 OS는 여러 지표의 균형을, 실시간 시스템은 마감시간 준수를 절대 우선한다. 지표별 우선순위를 시스템 유형과 매핑하면 다음과 같다.
| 시스템 유형 | 최우선 지표 | 대표 정책 |
|---|---|---|
| 일괄처리 서버 | 처리량·이용률 | SJF 근사 |
| 시분할·대화형 | 응답시간 | RR·MLFQ |
| 실시간 제어 | 마감시간 준수 | EDF·RMS |
| 모바일 단말 | 응답성·전력효율 | EAS 결합 스케줄러 |
| 구분 | 비선점(Non-preemptive) | 선점(Preemptive) |
|---|---|---|
| CPU 반납 | 자발적(I/O·종료 시) | 강제 회수 가능 |
| 응답성 | 낮음(긴 작업이 독점) | 높음 |
| 문맥전환 오버헤드 | 적음 | 많음 |
| 공유자원 일관성 | 단순 | 경쟁상태·동기화 필요 |
| 적용 | 단순 일괄처리 | 시분할·실시간 |
선점형은 응답성을 얻는 대신 공유 데이터의 일관성이라는 대가를 치른다. 커널 자료구조를 갱신하던 중 선점되면 다른 프로세스가 반쪽 상태를 읽을 수 있으므로, 임계구역 보호(세마포어·스핀락)와 커널 선점 지점 설계가 함께 요구된다.
한편 모든 선점·전환에는 문맥 전환(context switch) 비용이 숨어 있다. 전환 시 OS는 떠나는 프로세스의 레지스터·프로그램 카운터·메모리 맵 정보를 PCB(Process Control Block)에 저장하고 들어올 프로세스의 상태를 복원하는데, 이 작업 동안 CPU는 유용한 일을 전혀 하지 못한다. 더 큰 숨은 비용은 캐시·TLB 오염으로, 새 프로세스는 데워진 캐시를 쓸 수 없어 초기에 캐시 미스가 폭증한다. 따라서 스케줄링 빈도를 높여 공정성을 얻는 설계는 이 간접 비용과의 균형 위에서만 정당화되며, 이것이 타임 퀀텀을 "문맥 전환 시간의 수십 배 이상"으로 잡는 실무적 근거다.
4. 주요 스케줄링 알고리즘
가. FCFS(First-Come, First-Served)
가장 단순한 비선점 정책으로, 도착 순서대로 큐에서 꺼내 끝까지 실행한다. 구현이 쉽고 기아(starvation)가 없다는 장점이 있으나, 긴 작업 하나가 앞을 막으면 뒤의 짧은 작업들이 모두 밀리는 호위 효과(convoy effect)가 치명적이다. 예컨대 버스트가 24·3·3ms인 P1·P2·P3가 이 순서로 도착하면 평균 대기시간은 (0+24+27)/3 = 17ms지만, P2·P3·P1 순이면 (0+3+6)/3 = 3ms로 급감한다. 동일 작업 집합인데도 순서만으로 성능이 5배 이상 벌어지는 셈이며, 이 사례는 "먼저 온 순서"가 효율과 무관함을 극적으로 보여준다.
나. SJF / SRTF(Shortest Job First / Shortest Remaining Time First)
남은 CPU 버스트가 가장 짧은 작업을 먼저 처리하는 정책으로, 평균 대기시간을 최소화한다는 것이 수학적으로 증명된 최적 알고리즘이다. 비선점 버전이 SJF, 선점 버전이 SRTF다. 그러나 실제로는 다음 버스트 길이를 미리 알 수 없다는 근본 한계가 있어, 과거 버스트의 지수 평활(exponential averaging, τ(n+1)=α·t(n)+(1-α)·τ(n))로 예측해 근사한다. 또 다른 약점은 기아로, 짧은 작업이 끊임없이 들어오면 긴 작업은 영원히 선택되지 못할 수 있다. 이를 완화하는 장치가 뒤에서 다룰 에이징(aging)이다. 실무에서는 빌드 큐·배치 잡 스케줄러가 예상 수행시간 기반 우선순위로 SJF 사상을 차용한다.
다. 우선순위 스케줄링(Priority Scheduling)
각 작업에 우선순위를 부여하고 높은 쪽을 먼저 실행한다(SJF도 "버스트가 짧을수록 높은 우선순위"인 특수 사례다). 선점·비선점 모두 가능하며, 시스템 데몬·사용자 작업·백그라운드 작업을 차등 대우할 수 있어 유연하다. 핵심 함정은 역시 무기한 봉쇄(기아)이며, 이를 막기 위해 오래 기다린 작업의 우선순위를 서서히 올리는 에이징을 결합한다. 또한 낮은 우선순위 작업이 공유 자원을 쥔 채 높은 우선순위 작업을 막는 우선순위 역전(priority inversion)이 발생할 수 있어, 우선순위 상속(priority inheritance) 프로토콜로 대응한다(화성 탐사선 Mars Pathfinder의 리셋 사고가 대표 사례다).
라. 라운드 로빈(Round Robin, RR)과 MLFQ
RR은 시분할의 표준으로, 각 작업에 동일한 타임 퀀텀(time quantum)을 주고 소진하면 큐의 맨 뒤로 보내는 선점형 FCFS다. 공정하고 응답시간이 예측 가능하다는 장점 덕에 대화형 시스템에 적합하다. 성능은 퀀텀 크기에 민감한데, 너무 크면 FCFS로 퇴화하고 너무 작으면 문맥 전환 오버헤드가 폭증한다. 통상 전환 비용의 수십 배(수 ms~수십 ms)로 잡아 "버스트의 80%가 퀀텀 안에 끝나도록" 조정한다. 예를 들어 버스트 24·3·3ms, 퀀텀 4ms면 P1이 4ms 후 선점되어 P2·P3가 빠르게 끼어들므로 평균 응답시간이 FCFS보다 크게 개선된다.
타임 퀀텀 설정의 실무 원칙은 다음과 같이 요약된다.
- 전환 비용 대비 충분히 크게: 문맥 전환 시간의 수십 배 이상으로 두어 오버헤드 비율을 1% 수준 이하로 억제한다.
- 버스트 분포에 맞추기: 대다수(약 80%) CPU 버스트가 한 퀀텀 안에 끝나도록 잡아 불필요한 선점을 줄인다.
- 워크로드별 차등: 대화형은 작게(빠른 반응), 계산 중심은 크게(전환 절감) — MLFQ가 이를 자동화한다.
다단계 피드백 큐(MLFQ, Multi-Level Feedback Queue)는 여러 RR 큐를 우선순위별로 쌓고, 작업의 행동을 관찰해 큐를 이동시키는 적응형 정책이다. 퀀텀을 다 쓴 CPU-bound 작업은 아래 큐(긴 퀀텀)로 내리고, 일찍 CPU를 반납하는 I/O-bound·대화형 작업은 위 큐(짧은 퀀텀, 높은 우선순위)에 머물게 해 응답성과 처리량을 동시에 노린다. 미리 작업 성격을 몰라도 스스로 학습하듯 분류한다는 점이 강력하며, 주기적 우선순위 재조정(부스팅)으로 기아를 방지한다.
| 알고리즘 | 선점 | 평균대기 | 기아 | 특징 |
|---|---|---|---|---|
| FCFS | X | 나쁨 | 없음 | 단순, 호위 효과 |
| SJF/SRTF | 선택 | 최적 | 있음 | 예측 필요 |
| Priority | 선택 | 가변 | 있음 | 에이징 필요 |
| RR | O | 보통 | 없음 | 퀀텀 민감, 공정 |
| MLFQ | O | 우수 | 없음(부스팅) | 적응형, 범용 OS 표준 |
마. 종합 비교 예제 — 같은 작업, 다른 결과
정책 간 차이를 수치로 체감하기 위해, 동시(시각 0)에 도착한 세 프로세스 P1(24ms)·P2(3ms)·P3(3ms)를 FCFS·SJF·RR(퀀텀 4ms)로 각각 돌린 결과를 비교한다. 아래 표는 각 정책의 완료시각과 대기시간(= 완료시각 − 버스트)을 정리한 것이다. 같은 입력인데도 평균 대기시간이 정책에 따라 3배 이상 벌어진다는 점에 주목해야 한다.
| 정책 | P1 완료/대기 | P2 완료/대기 | P3 완료/대기 | 평균 대기시간 |
|---|---|---|---|---|
| FCFS(P1→P2→P3) | 24 / 0 | 27 / 24 | 30 / 27 | 17ms |
| SJF(P2→P3→P1) | 30 / 6 | 3 / 0 | 6 / 3 | 3ms |
| RR(퀀텀 4) | 30 / 6 | 10 / 7 | 13 / 10 | 7.7ms |
FCFS는 긴 P1이 앞을 막아 호위 효과로 평균 대기가 가장 나쁘다. SJF는 짧은 작업을 앞세워 평균 대기를 최소화(최적)하지만, 만약 짧은 작업이 계속 유입되면 P1은 기아에 빠질 위험을 안는다. RR은 평균 대기는 SJF만 못해도 P2·P3가 최초 반응을 받기까지의 응답시간(각각 4ms, 8ms 이내)이 짧아, 대화형 환경에서 체감 성능이 가장 우수하다. 즉 "평균 대기시간이 작다"와 "반응이 빠르다"는 다른 목표이며, 이 예제는 스케줄러 선택이 곧 어떤 지표를 희생하고 무엇을 얻을지의 결정임을 분명히 보여준다.
5. 심화 — 실무 스케줄러와 멀티코어 동향
현실의 범용 OS는 위 고전 알고리즘을 그대로 쓰지 않고 공정성·확장성·전력을 결합한 정교한 스케줄러를 운용한다. 리눅스는 2007년부터 CFS(Completely Fair Scheduler)를 도입했는데, 타임 슬라이스 대신 각 작업이 받은 CPU 시간을 가상 실행시간(vruntime)으로 누적하고 레드-블랙 트리에서 vruntime이 가장 작은 작업을 O(log n)에 선택함으로써, "모든 작업에 균등한 CPU 몫"을 근사한다. 2024년 리눅스 6.6부터는 지연 민감 작업을 더 잘 다루는 EEVDF(Earliest Eligible Virtual Deadline First)로 교체되어, 가상 마감시간 개념으로 응답성과 공정성의 균형을 개선했다. 윈도우는 32단계 우선순위 기반 선점형 스케줄러에 우선순위 부스팅(포그라운드 창·I/O 완료 시 일시 상향)을 결합한다.
이 발전의 효과는 구체적 수치로 나타난다. 리눅스가 O(1) 스케줄러에서 CFS로 넘어오며 수천 개 작업이 동시에 돌아도 선택 비용이 로그 규모로 억제되어 대규모 웹 서버의 꼬리 지연(tail latency)이 개선되었고, EEVDF 도입 후 오디오·게임 같은 지연 민감 작업의 프레임 드랍이 줄었다는 보고가 이어진다. 반대로 스케줄러를 잘못 다루면 성능이 무너진다. 대표적 실무 사례가 쿠버네티스의 CFS 대역폭 스로틀링(CPU throttling) 문제로, 컨테이너에 CPU limit을 낮게 설정하면 CFS가 100ms 주기마다 쿼터 소진 시 해당 컨테이너를 강제로 멈춰, CPU 여유가 있는데도 응답시간 p99가 수백 ms 치솟는다. 많은 조직이 이 현상 때문에 지연 민감 서비스에서 CPU limit을 제거하거나 상향 조정하는 운영 지침을 두는데, 이는 OS 스케줄링 원리를 모르면 클라우드 성능 튜닝도 불가능함을 보여주는 실례다.
모바일·서버의 이기종 멀티코어는 새로운 차원을 더한다. ARM big.LITTLE / DynamIQ는 고성능 코어와 저전력 코어를 섞어 두고, 스케줄러가 작업 부하와 전력 예산에 따라 코어를 선택(EAS, Energy-Aware Scheduling)해 배터리 수명을 늘린다. 또 코어마다 준비 큐를 두는 멀티코어 환경에서는 부하 불균형이 생기므로, 주기적 로드 밸런싱과, 캐시가 데워진 코어에 작업을 묶어두는 캐시 친화성(processor affinity) 사이의 트레이드오프를 관리해야 한다. 가상화·클라우드에서는 하이퍼바이저가 vCPU를 물리 CPU에 다시 스케줄링하므로 이중 스케줄링(double scheduling)과 락 홀더 선점(lock-holder preemption) 문제까지 고려 대상이 된다. 실시간 영역에서는 주기적 작업의 마감 보장을 위해 RMS(Rate Monotonic)·EDF(Earliest Deadline First) 같은 마감 기반 정책이 별도로 쓰인다.
6. 고려사항 및 시사점(기술사 관점)
- 적용 전략 — 목적에 맞는 정책 선택: 대화형 단말은 응답시간(RR·MLFQ), 배치 서버는 처리량(SJF 근사), 실시간 제어기는 마감 준수(EDF·RMS)를 최우선으로 삼아야 한다. 단일 "최고의 스케줄러"는 없으며, 워크로드 특성 분석이 선행되어야 한다.
- 트레이드오프 관리: 타임 퀀텀은 응답성(짧게)과 문맥전환 오버헤드(길게)의 균형점이며, 선점은 응답성을 주는 대신 동기화 비용과 캐시 오염을 유발한다. 지표 간 상충을 정량적으로 측정(utilization·p99 지연)하고 튜닝하는 역량이 요구된다.
- 기아·역전 방지의 제도화: 우선순위 기반 정책에는 반드시 에이징과 우선순위 상속을 함께 설계해 무기한 봉쇄와 우선순위 역전을 구조적으로 차단해야 한다(임무 수행 시스템에서는 안전사고로 직결된다).
- 전력·지속가능성 연계: 이기종 코어·DVFS와 결합한 에너지 인지 스케줄링은 모바일 배터리와 데이터센터 전력비(그린 IT)에 직접 영향을 미친다. 향후 스케줄러는 성능뿐 아니라 와트당 성능과 탄소효율을 함께 최적화하는 방향으로 진화할 것이다.
- 연계 기술로의 확장: 컨테이너(cgroups CPU 쿼터·CFS 대역폭 제어)·쿠버네티스 요청/제한, 가상화의 vCPU 스케줄링, 그리고 GPU·NPU 작업 스케줄링까지 동일한 원리가 확장 적용되므로, OS 스케줄링 이해는 클라우드 자원 관리의 토대가 된다.
- 관측·검증 체계의 필요성: 스케줄링 품질은 평균값이 아니라 꼬리 지연(p99·p99.9)과 스케줄 지연(scheduling latency)으로 드러나므로,
perf sched·eBPF 기반 추적 등으로 실제 지연 분포를 계측하고 SLO에 연동해 관리하는 관측 체계가 함께 갖춰져야 정책 튜닝이 근거를 갖는다.
참고자료
- Operating System Concepts (Silberschatz et al.), CPU Scheduling 장
- Linux Kernel Documentation, "CFS Scheduler" / "Scheduler" — https://docs.kernel.org/scheduler/
- Arpaci-Dusseau, "Operating Systems: Three Easy Pieces" — Scheduling(MLFQ) — https://pages.cs.wisc.edu/~remzi/OSTEP/
한 줄 요약: CPU 스케줄링은 준비 큐의 작업 중 다음 실행 대상을 선택해 다중 프로그래밍의 효율을 끌어내는 기법으로, FCFS·SJF·우선순위·RR·MLFQ가 응답성·처리량·공정성을 저마다 다르게 저울질하며, 실무에서는 리눅스 CFS/EEVDF와 에너지 인지·멀티코어 스케줄링으로 발전하고 있다.