"CPU 스케줄링은 멀티프로그래밍의 핵심이다."
메모리에 여러 프로세스가 올라와 있을 때, 다음에 CPU를 줄 프로세스를 어떻게 고를 것인가? 이 결정이 곧 CPU 스케줄링이다. 알고리즘의 선택이 시스템 전체 성능을 좌우한다.
목표
- CPU-I/O Burst Cycle의 개념을 이해
- 선점형과 비선점형 스케줄링의 차이를 구분
- 스케줄링 성능 기준 5가지를 파악
- 주요 스케줄링 알고리즘과 특성을 비교
- 다중 처리기 환경에서의 스케줄링 이슈를 이해
5.1 기본 개념
CPU-I/O Burst Cycle
프로세스는 실행 중에 CPU 연산과 I/O 대기를 반복한다. 이를 CPU-I/O Burst Cycle이라 한다.
프로세스 실행 흐름:
[CPU Burst] → [I/O Burst] → [CPU Burst] → [I/O Burst] → ... → 종료
연산 중 I/O 대기 연산 중 I/O 대기- CPU Burst : CPU가 연산을 수행하는 구간
- I/O Burst : I/O 완료를 기다리며 CPU를 쓰지 않는 구간
CPU Burst 시간의 분포는 일반적으로 짧은 burst가 압도적으로 많고, 긴 burst는 드물다. 이 특성이 스케줄링 알고리즘 설계의 근거가 된다.
빈도
│
│ ████
│ ████
│ ████ ███
│ ████ ███ ██
│ ████ ███ ██ ██ █
└──────────────────────► CPU Burst 시간
짧음 긺CPU 스케줄러
단기 스케줄러(CPU 스케줄러) 는 Ready Queue에서 다음에 실행할 프로세스를 선택해 CPU를 할당한다.
스케줄링이 발생하는 4가지 상황:
| 상황 | 설명 | 유형 |
|---|---|---|
| ① Running → Waiting | I/O 요청 등으로 대기 상태로 전환 | 비선점 |
| ② Running → Ready | 인터럽트 발생으로 Ready로 전환 | 선점 |
| ③ Waiting → Ready | I/O 완료 후 Ready로 복귀 | 선점 |
| ④ Terminated | 프로세스 종료 | 비선점 |
선점형 vs 비선점형
| 구분 | 비선점형 (Non-preemptive) | 선점형 (Preemptive) |
|---|---|---|
| 개념 | CPU를 받으면 스스로 반납할 때까지 유지 | OS가 강제로 CPU를 빼앗을 수 있음 |
| 전환 시점 | ①④ 상황에서만 발생 | ①②③④ 모든 상황에서 발생 |
| 장점 | 구현 단순, 문맥 교환 적음 | 응답성 높음, 기아 방지 가능 |
| 단점 | 응답성 낮음 | 문맥 교환 오버헤드, 공유 데이터 동기화 필요 |
| 예시 알고리즘 | FCFS, SJF(비선점) | RR, SRTF, Priority(선점) |
Dispatcher
스케줄러가 "누구에게 줄지"를 결정하면, Dispatcher가 실제로 CPU를 넘기는 작업을 수행한다.
Dispatcher의 역할:
- 문맥 교환 (Context Switch)
- 사용자 모드로 전환
- 프로그램 카운터를 새 프로세스의 실행 위치로 설정
Dispatch Latency : Dispatcher가 한 프로세스를 멈추고 다른 프로세스를 시작하는 데 걸리는 시간. 이 시간은 최소화해야 한다.
5.2 스케줄링 기준
좋은 스케줄링 알고리즘을 평가하는 5가지 기준이다.
| 기준 | 설명 | 목표 |
|---|---|---|
| CPU 이용률 (Utilization) | CPU가 유휴 상태 없이 일한 비율 | 최대화 |
| 처리량 (Throughput) | 단위 시간당 완료된 프로세스 수 | 최대화 |
| 총처리 시간 (Turnaround Time) | 프로세스 제출부터 완료까지의 총 시간 | 최소화 |
| 대기 시간 (Waiting Time) | Ready Queue에서 대기한 총 시간 | 최소화 |
| 응답 시간 (Response Time) | 요청 후 첫 응답이 나올 때까지의 시간 | 최소화 |
모든 기준을 동시에 만족하는 완벽한 알고리즘은 없다. 상황에 따라 기준의 우선순위가 달라진다.
5.3 스케줄링 알고리즘
예시에 사용할 프로세스
이후 모든 알고리즘 예시는 아래 3개 프로세스를 사용한다. (도착 시간은 모두 0)
| 프로세스 | CPU Burst 시간 |
|---|---|
| P1 | 24ms |
| P2 | 3ms |
| P3 | 3ms |
FCFS (First-Come, First-Served)
가장 먼저 도착한 프로세스에게 CPU를 할당하는 방식이다. 비선점형.
도착 순서: P1 → P2 → P3
| ────────── P1 ────────── | P2 | P3 |
0 24 27 30| 프로세스 | 대기 시간 |
|---|---|
| P1 | 0ms |
| P2 | 24ms |
| P3 | 27ms |
| 평균 | 17ms |
만약 도착 순서가 P2 → P3 → P1 이라면?
| P2 | P3 | ────────── P1 ────────── |
0 3 6 30평균 대기 시간: (0 + 3 + 6) / 3 = 3ms
호위 효과 (Convoy Effect) : CPU Burst가 긴 프로세스 하나 때문에 뒤에 오는 짧은 프로세스들이 오랫동안 대기하는 현상. FCFS의 대표적인 단점이다.
SJF (Shortest-Job-First)
CPU Burst가 가장 짧은 프로세스를 먼저 실행하는 방식이다. 평균 대기 시간이 가장 짧다 (최적).
Burst 순서: P2(3) → P3(3) → P1(24)
| P2 | P3 | ────────── P1 ────────── |
0 3 6 30| 프로세스 | 대기 시간 |
|---|---|
| P1 | 6ms |
| P2 | 0ms |
| P3 | 3ms |
| 평균 | 3ms |
SJF의 문제점
- 다음 CPU Burst 시간을 정확히 알 수 없다. 실제로는 과거 Burst 시간을 기반으로 예측한다.
- 지수 평균(Exponential Averaging) 으로 예측:
τ(n+1) = α × t(n) + (1-α) × τ(n)
t(n) : 실제 n번째 CPU Burst 시간
τ(n) : n번째 예측 값
α : 가중치 (0 ≤ α ≤ 1)SRTF (Shortest-Remaining-Time-First)
SJF의 선점형 버전이다. 새 프로세스가 도착할 때마다 남은 Burst 시간이 더 짧은 프로세스에게 CPU를 넘긴다.
| 프로세스 | 도착 시간 | Burst 시간 |
|---|---|---|
| P1 | 0 | 8ms |
| P2 | 1 | 4ms |
| P3 | 2 | 9ms |
| P4 | 3 | 5ms |
| P1 | ─ P2 ─ | ─── P4 ─── | ───── P1 ───── | ──────── P3 ──────── |
0 1 5 10 17 26| 프로세스 | 대기 시간 |
|---|---|
| P1 | (0-0) + (10-1) = 9ms |
| P2 | 1-1 = 0ms |
| P3 | 17-2 = 15ms |
| P4 | 5-3 = 2ms |
| 평균 | 6.5ms |
RR (Round-Robin)
각 프로세스에게 동일한 시간(Time Quantum, 타임 슬라이스)을 할당하고 순환하는 방식이다. 선점형. 시분할 시스템에 적합하다.
Time Quantum = 4ms, 도착 순서: P1 → P2 → P3
| P1 | P2 | P3 | P1 | P1 | P1 | P1 | P1 |
0 4 7 10 14 18 22 26 30| 프로세스 | 대기 시간 |
|---|---|
| P1 | 30 - 24 = 6ms |
| P2 | 4 - 3 = 1ms (4에 시작해서 7에 완료, 대기 4ms) → 4ms |
| P3 | 7 - 3 = 4ms (7에 시작해서 10에 완료, 대기 7ms) → 7ms |
| 평균 | (6 + 4 + 7) / 3 = 5.67ms |
Time Quantum 크기의 영향
| Quantum 크기 | 특성 |
|---|---|
| 너무 크면 | FCFS와 동일해짐 |
| 너무 작으면 | 문맥 교환 오버헤드가 커져 비효율 |
| 일반적으로 | 10~100ms, CPU Burst의 80%가 quantum보다 짧게 설정 |
RR은 평균 대기 시간은 SJF보다 길 수 있지만, 응답 시간이 균등하다는 장점이 있다.
Priority Scheduling (우선순위 스케줄링)
각 프로세스에 우선순위를 부여하고, 우선순위가 높은 프로세스를 먼저 실행한다. 선점형·비선점형 둘 다 가능.
| 프로세스 | Burst 시간 | 우선순위 |
|---|---|---|
| P1 | 10ms | 3 |
| P2 | 1ms | 1 (가장 높음) |
| P3 | 2ms | 4 |
| P4 | 1ms | 5 |
| P5 | 5ms | 2 |
| P2 | P5 | ── P1 ── | P3 | P4 |
0 1 6 16 18 19평균 대기 시간: (6 + 0 + 16 + 18 + 1) / 5 = 8.2ms
기아 (Starvation) 문제
우선순위가 낮은 프로세스가 높은 우선순위 프로세스에 계속 밀려 영원히 실행되지 못하는 현상이다.
해결책: 에이징 (Aging)
시간이 지날수록 프로세스의 우선순위를 점진적으로 높여주는 방식이다.
대기 시간이 길어질수록
우선순위 낮음 ──────────────────► 우선순위 높아짐
에이징 적용Multilevel Queue (다단계 큐)
Ready Queue를 여러 개의 큐로 분리하고, 각 큐마다 다른 스케줄링 알고리즘을 적용하는 방식이다.
┌─────────────────────────────┐ ← 최고 우선순위
│ Foreground Queue (RR) │ 대화형 프로세스
├─────────────────────────────┤
│ Background Queue (FCFS) │ 배치 프로세스
└─────────────────────────────┘ ← 최저 우선순위- 프로세스는 생성 시 특정 큐에 영구적으로 배정됨
- 큐 간에는 고정 우선순위 방식 또는 시간 할당 방식 사용
- 단점 : 프로세스가 큐 사이를 이동할 수 없어 기아 발생 가능
Multilevel Feedback Queue (다단계 피드백 큐)
다단계 큐에서 큐 간 이동을 허용하는 방식이다. 현대 OS에서 가장 일반적으로 사용한다.
큐 0 (Quantum=8) ──► 완료 못하면 큐 1로 강등
큐 1 (Quantum=16) ──► 완료 못하면 큐 2로 강등
큐 2 (FCFS) ──► CPU Burst가 긴 프로세스 처리- CPU Burst가 짧은 프로세스 → 높은 큐에서 빠르게 처리
- CPU Burst가 긴 프로세스 → 점차 하위 큐로 이동
- 에이징 적용 가능: 하위 큐에서 오래 기다리면 상위 큐로 승격
가장 유연하면서 복잡한 알고리즘이다. 매개변수(큐 수, quantum 크기, 승격/강등 기준)를 어떻게 설정하느냐에 따라 성능이 달라진다.
5.4 알고리즘 비교 정리
| 알고리즘 | 선점형 | 평균 대기 시간 | 특징 |
|---|---|---|---|
| FCFS | X | 높을 수 있음 | 구현 단순. Convoy Effect 발생 가능 |
| SJF | X | 최적 (이론) | 실제 Burst 시간 예측 불가 |
| SRTF | O | 최적 (이론) | SJF 선점형 버전. 잦은 문맥 교환 |
| RR | O | 중간 | 응답 시간 균등. Quantum 크기가 핵심 |
| Priority | 선택 | 가변 | 기아 발생 가능 → Aging으로 해결 |
| Multilevel Queue | 선택 | 가변 | 큐 간 이동 불가 |
| Multilevel Feedback Queue | O | 가변 | 가장 범용적. 현대 OS 채택 |
5.5 다중 처리기 스케줄링
CPU가 여러 개인 환경에서는 스케줄링이 더 복잡해진다.
부하 균등화 (Load Balancing)
모든 CPU가 균등하게 일하도록 프로세스를 분배하는 것이다.
- Push Migration : 주기적으로 부하를 확인해 바쁜 CPU에서 한가한 CPU로 프로세스를 밀어냄
- Pull Migration : 한가한 CPU가 바쁜 CPU의 대기 프로세스를 당겨옴
프로세서 친화성 (Processor Affinity)
프로세스는 한 CPU에서 실행되다가 다른 CPU로 이동하면 캐시를 다시 채워야 하는 비용이 발생한다.
- 연성 친화성 (Soft Affinity) : OS가 가능하면 같은 CPU에서 실행하려 하지만 보장하지는 않음
- 강성 친화성 (Hard Affinity) : 프로세스가 특정 CPU에서만 실행되도록 강제
NUMA (Non-Uniform Memory Access)
CPU마다 로컬 메모리가 있고, 다른 CPU의 메모리(원격 메모리)에 접근할 때는 더 느리다.
CPU 0 ─── 로컬 메모리 0 CPU 1 ─── 로컬 메모리 1
│ │
└──────────── 버스 ────────────┘
(원격 접근 시 느림)스케줄러는 가능하면 프로세스를 자신의 로컬 메모리가 있는 CPU에 배정해야 성능이 좋다.
정리
| 절 | 핵심 내용 |
|---|---|
| 5.1 | CPU-I/O Burst Cycle. 선점형(OS가 강제 회수) vs 비선점형(스스로 반납). Dispatcher |
| 5.2 | 5가지 기준: CPU 이용률·처리량 최대화 / 총처리·대기·응답 시간 최소화 |
| 5.3 FCFS | 도착 순서대로. 구현 단순. Convoy Effect |
| 5.3 SJF/SRTF | 평균 대기 시간 최적. Burst 예측 필요. SRTF는 선점형 |
| 5.3 RR | Time Quantum 기반 순환. 응답 시간 균등. Quantum 크기가 성능 결정 |
| 5.3 Priority | 우선순위 기반. 기아 발생 → Aging으로 해결 |
| 5.3 MLQ/MLFQ | 다단계 큐. MLFQ는 큐 간 이동 허용. 현대 OS의 표준 |
| 5.5 | 부하 균등화(Push/Pull), 프로세서 친화성(Soft/Hard), NUMA |
