CPU 스케줄링 알고리즘의 선택 기준과 동작 방식
FCFS, SJF, Round Robin, 우선순위, MLQ, MLFQ의 CPU 스케줄링 특성과 선점 방식, 적용 환경을 비교한다.
2026-08-14 · 최초 발행 2026-01-16
CPU를 누구에게 먼저 줄 것인가
CPU 스케줄링은 다중 프로그래밍 환경에서 Ready Queue의 프로세스 중 CPU를 할당할 대상을 고르는 운영체제 기능이다. 같은 CPU 자원이라도 어떤 정책을 적용하느냐에 따라 처리량, 대기 시간, 응답 시간, 반환 시간, 공정성이 달라진다.
스케줄러가 주로 다루는 목표는 다음과 같다.
| 목표 | 의미 | 측정 지표 |
|---|---|---|
| CPU 활용률 최대화 | CPU가 계속 작업하도록 유지 | CPU Utilization |
| 처리량 최대화 | 단위 시간당 완료 작업 수 증가 | Throughput |
| 대기 시간 최소화 | Ready Queue에서 기다리는 시간 감소 | Waiting Time |
| 응답 시간 최소화 | 요청 뒤 첫 응답까지 걸리는 시간 감소 | Response Time |
| 반환 시간 최소화 | 작업 제출부터 완료까지의 시간 감소 | Turnaround Time |
| 공정성 보장 | 모든 프로세스에 적절한 CPU 시간 배분 | Fairness |
스케줄링은 CPU를 회수할 수 있는지에 따라 비선점형과 선점형으로 나뉜다.
| 유형 | 특징 | 장점 | 단점 |
|---|---|---|---|
| 비선점형 | CPU를 자발적으로 반환 | 컨텍스트 스위칭이 적음 | 응답성이 낮아질 수 있음 |
| 선점형 | 운영체제가 CPU를 회수할 수 있음 | 응답성 향상 | 오버헤드 증가 |
FCFS는 도착 순서를 그대로 따른다
FCFS(First-Come, First-Served)는 Ready Queue에 먼저 들어온 프로세스부터 실행하는 비선점형 정책이다. FIFO 큐로 구현할 수 있어 단순하지만, 도착 순서가 대기 시간에 큰 영향을 준다.
| 항목 | 내용 |
|---|---|
| 구현 방식 | FIFO 큐 |
| 선점 여부 | 비선점형 |
| 복잡도 | O(n) |
| 대기 시간 | 가변적이며 도착 순서에 크게 의존 |
FCFS는 도착 순서 기준의 공정성을 제공하고 기아 현상도 없다. 반면 긴 작업이 먼저 들어오면 짧은 작업이 그 뒤에서 오래 대기하는 Convoy Effect가 발생한다. 평균 대기 시간이 길어질 수 있는 이유도 여기에 있다.
SJF는 짧은 CPU 버스트를 앞세운다
SJF(Shortest Job First)는 CPU 버스트 시간이 가장 짧은 프로세스에 CPU를 먼저 할당한다. 평균 대기 시간을 줄이는 데 유리하지만, 실행 시간을 미리 알아야 한다는 제약이 있다.
| 유형 | 설명 | 특징 |
|---|---|---|
| 비선점형 SJF | 실행 중인 프로세스가 끝날 때까지 대기 | 단순한 구현 |
| 선점형 SJF(SRTF) | 더 짧은 프로세스가 도착하면 선점 | 최적의 평균 대기 시간 |
SRTF(Shortest Remaining Time First)는 남은 실행 시간이 더 짧은 프로세스가 들어오면 현재 작업을 선점하는 방식이다.
| 항목 | 비선점형 SJF | 선점형 SJF(SRTF) |
|---|---|---|
| 평균 대기 시간 | 비선점형 중 최소 | 이론상 최적 |
| 기아 가능성 | 있음 | 있음 |
| 구현 복잡도 | 중간 | 높음 |
| 실행 시간 예측 | 필요 | 필요 |
실제 환경에서는 과거 실행 기록을 바탕으로 지수 평균(Exponential Averaging)을 사용해 버스트 시간을 예측한다.
τ(n+1) = α × t(n) + (1-α) × τ(n)
- τ: 예측된 버스트 시간
- t: 실제 버스트 시간
- α: 가중치 (0 < α ≤ 1)
SJF는 처리량을 높이고 Convoy Effect를 완화할 수 있다. 다만 CPU 버스트 시간 예측이 어렵고, 긴 프로세스가 무한히 대기하는 기아 현상이 생길 수 있다.
Round Robin의 핵심은 Time Quantum이다
Round Robin은 각 프로세스에 같은 Time Quantum을 주고, 시간이 끝나면 다음 프로세스로 CPU를 넘기는 선점형 스케줄링이다. 대화형 시스템에서 공정한 CPU 배분과 예측 가능한 응답 시간을 제공한다.
| 프로세스 | 버스트 시간 | Time Quantum = 4ms |
|---|---|---|
| P1 | 24ms | 실행 6회 |
| P2 | 3ms | 실행 1회 (완료) |
| P3 | 3ms | 실행 1회 (완료) |
Time Quantum이 너무 크면 FCFS와 비슷해져 응답성이 떨어지고, 너무 작으면 컨텍스트 스위칭이 잦아져 오버헤드가 증가한다.
| Time Quantum | 특성 |
|---|---|
| 너무 크면 | FCFS와 동일해짐 |
| 너무 작으면 | 컨텍스트 스위칭 오버헤드 증가 |
| 적정 크기 | 일반적으로 10-100ms |
Round Robin은 기아 현상이 없고 대화형 시스템에 적합하다. 평균 대기 시간이 길어질 수 있으며 CPU 바운드 작업에는 비효율적일 수 있으므로, Time Quantum 설정이 중요하다.
우선순위가 높은 작업을 먼저 처리하는 방식
우선순위 스케줄링은 프로세스마다 우선순위를 지정하고 높은 우선순위의 프로세스부터 CPU를 배정한다. 우선순위는 시간 제한, 메모리 요구량, 열린 파일 수, CPU 버스트 대비 I/O 버스트 비율 같은 내부 요소와 사용자 지정, 프로세스 중요도, 비용/요금, 정책적 요인 같은 외부 요소를 기준으로 정할 수 있다.
| 유형 | 특징 | 사용 사례 |
|---|---|---|
| 비선점형 | 실행 중인 프로세스가 완료될 때까지 대기 | 배치 시스템 |
| 선점형 | 높은 우선순위 프로세스가 도착하면 선점 | 실시간 시스템 |
| 정적 우선순위 | 실행 중 우선순위가 변하지 않음 | 단순 시스템 |
| 동적 우선순위 | 상황에 따라 우선순위 변경 | 적응형 시스템 |
낮은 우선순위 프로세스가 높은 우선순위 작업에 밀려 무한정 기다리는 현상을 기아 현상(Starvation)이라고 한다. 에이징(Aging)은 대기 시간이 길수록 우선순위를 점진적으로 올려 이를 완화한다.
MLQ는 작업 유형별로 큐를 고정한다
MLQ(Multi-Level Queue)는 프로세스를 여러 독립 큐로 분류하고, 각 큐에 다른 스케줄링 알고리즘을 적용한다. 프로세스는 분류된 큐에 고정되며 큐 사이를 이동할 수 없다.
| 특성 | 설명 |
|---|---|
| 큐 분류 | 프로세스 유형별 고정 분류 |
| 큐 간 스케줄링 | 고정 우선순위 또는 시간 분할 |
| 큐 내 스케줄링 | 각 큐별 독립적 알고리즘 |
| 큐 이동 | 불가능 (고정 분류) |
| 방식 | 설명 | 장단점 |
|---|---|---|
| 고정 우선순위 | 상위 큐 우선 처리 | 단순하나 기아 가능 |
| 시간 분할 | 각 큐에 CPU 시간 비율 할당 | 공정하나 복잡 |
MLQ는 프로세스 유형별 최적화와 시스템 프로세스 우선 처리에 유리하며 구현도 비교적 단순하다. 반대로 큐 간 이동이 불가능해 유연성이 부족하고, 기아 현상과 프로세스 분류 기준 문제가 남는다.
MLFQ는 CPU 사용 패턴에 따라 큐를 바꾼다
MLFQ(Multi-Level Feedback Queue)는 MLQ에 큐 간 이동을 더한 동적 스케줄링 방식이다. 새 프로세스는 최상위 큐에서 시작하고, CPU를 오래 사용하면 하위 큐로 이동한다.
| 규칙 | 설명 |
|---|---|
| 규칙 1 | 우선순위가 높은 프로세스를 먼저 실행 |
| 규칙 2 | 동일 우선순위는 RR로 실행 |
| 규칙 3 | 새 프로세스는 최상위 큐에 배치 |
| 규칙 4a | Time Quantum을 소진하면 하위 큐로 이동 |
| 규칙 4b | Time Quantum 안에 CPU를 반환하면 현재 큐 유지 |
| 규칙 5 | 주기적으로 모든 프로세스를 최상위 큐로 이동 (Priority Boost) |
I/O 바운드 프로세스와 대화형 프로세스는 짧은 CPU 버스트 뒤 빈번하게 I/O를 수행하므로 상위 큐에 남아 빠른 응답을 받는다. 긴 CPU 사용을 반복하는 CPU 바운드 프로세스는 하위 큐로 내려가 낮은 우선순위로 실행된다.
| 문제 | 해결책 |
|---|---|
| I/O 요청 직전 CPU 반납 | 누적 실행 시간 기반 강등 |
| 영구적 낮은 우선순위 | Priority Boost (주기적 상향) |
| 우선순위 조작 | CPU 사용 시간 정확 측정 |
MLFQ는 I/O 바운드와 CPU 바운드 작업을 함께 최적화하고, 대화형 프로세스의 응답성을 높이며 Priority Boost로 기아 현상을 해결한다. 대신 구현 복잡성이 높고 파라미터 튜닝, Gaming 방지, 오버헤드를 고려해야 한다.
워크로드에 맞춰 고르는 스케줄링 정책
| 알고리즘 | 선점 | 기아 | 응답 시간 | 처리량 | 복잡도 |
|---|---|---|---|---|---|
| FCFS | 비선점 | 없음 | 높음 | 보통 | 낮음 |
| SJF | 둘 다 | 있음 | 낮음 | 높음 | 중간 |
| Round Robin | 선점 | 없음 | 보통 | 보통 | 낮음 |
| 우선순위 | 둘 다 | 있음 | 가변 | 가변 | 중간 |
| MLQ | 가변 | 있음 | 가변 | 높음 | 중간 |
| MLFQ | 선점 | 없음 | 낮음 | 높음 | 높음 |
| 환경 | 권장 알고리즘 | 이유 |
|---|---|---|
| 배치 시스템 | FCFS, SJF | 처리량 중시 |
| 대화형 시스템 | RR, MLFQ | 응답성 중시 |
| 실시간 시스템 | 우선순위 | 마감 시간 준수 |
| 범용 OS | MLFQ | 균형 잡힌 성능 |
FCFS는 단순하지만 Convoy Effect가 문제될 수 있고, SJF는 평균 대기 시간을 줄이는 대신 기아 현상 가능성을 가진다. Round Robin은 공정한 CPU 배분에 적합하며, 우선순위 스케줄링은 중요한 프로세스를 우선 처리해야 하는 환경에 맞는다. MLFQ는 여러 워크로드 특성에 적응적으로 대응하는 방식이다.