CPU 스케줄링 알고리즘 완벽 가이드: FCFS부터 MLFQ까지
CPU 스케줄링 알고리즘 완벽 가이드: FCFS부터 MLFQ까지
이전 글에서 가상 메모리와 페이지 교체 알고리즘을 다루었다. 이번 글에서는 운영체제의 또 다른 핵심 축인 CPU 스케줄링(CPU Scheduling)을 깊이 있게 정리한다.
단일 CPU에서 수십~수백 개의 프로세스가 동시에 실행되는 것처럼 보이는 이유, 그 비밀이 바로 CPU 스케줄링이다. “어떤 프로세스에게 CPU를 줄 것인가”라는 단순한 질문에 대한 답은, 시스템의 처리량(Throughput), 응답 시간(Response Time), 공정성(Fairness)을 결정짓는다. FCFS의 Convoy Effect, SJF의 기아(Starvation), Round Robin의 타임 퀀텀 트레이드오프, 그리고 현대 운영체제가 실제로 사용하는 MLFQ까지 — 면접에서 빈출되는 핵심 개념을 Gantt 차트와 계산 과정으로 정리한다.
1. CPU 스케줄링의 개념과 필요성
1.1 CPU 스케줄링이란
CPU 스케줄링은 Ready Queue에 있는 프로세스 중 어떤 프로세스에게 CPU를 할당할 것인지 결정하는 정책이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
CPU 스케줄링의 핵심 구조:
┌─────────┐ ┌─────────┐ ┌─────────┐
│ Process │ │ Process │ │ Process │
│ A │ │ B │ │ C │
└────┬────┘ └────┬────┘ └────┬────┘
│ │ │
▼ ▼ ▼
┌────────────────────────────────────────┐
│ Ready Queue │
│ [A] → [B] → [C] → ... │
└──────────────────┬─────────────────────┘
│
┌──────▼──────┐
│ Scheduler │ ← 누구에게 CPU를 줄까?
│ (스케줄러) │
└──────┬──────┘
│
┌──────▼──────┐
│ Dispatcher │ ← 실제 Context Switch 수행
└──────┬──────┘
│
┌──────▼──────┐
│ CPU │
│ (실행 중) │
└─────────────┘
1.2 프로세스 상태 전이와 스케줄링 시점
CPU 스케줄링이 발생하는 시점을 프로세스 상태 전이 다이어그램으로 이해해야 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
프로세스 상태 전이 다이어그램:
①
[New] ──────────────→ [Ready] ◄──────────── [Waiting]
│ ④ ▲
│ │
② │ │ ③
▼ │
[Running] ──────────────────┘
│
⑤ │
▼
[Terminated]
스케줄링이 발생하는 시점:
① New → Ready : 새 프로세스가 Ready Queue에 진입
② Ready → Running : 스케줄러가 프로세스 선택 (dispatch)
③ Running → Waiting : I/O 요청 등으로 대기 상태 전환
④ Waiting → Ready : I/O 완료 등으로 Ready 상태 복귀
⑤ Running → Ready : 타이머 인터럽트 (선점)
비선점형(Non-Preemptive) 스케줄링은 ③, ⑤에서만 발생하고, 선점형(Preemptive) 스케줄링은 모든 시점에서 발생할 수 있다.
1.3 스케줄링 성능 척도 (Scheduling Criteria)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
┌────────────────────┬───────────────────────────────────────────────────┐
│ 성능 척도 │ 설명 │
├────────────────────┼───────────────────────────────────────────────────┤
│ CPU 이용률 │ 전체 시간 중 CPU가 유휴 상태가 아닌 비율 │
│ (CPU Utilization) │ 목표: 40~90% (일반적) │
├────────────────────┼───────────────────────────────────────────────────┤
│ 처리량 │ 단위 시간당 완료한 프로세스 수 │
│ (Throughput) │ 높을수록 좋음 │
├────────────────────┼───────────────────────────────────────────────────┤
│ 총 처리 시간 │ 프로세스 제출 ~ 완료까지 전체 시간 │
│ (Turnaround Time) │ = Waiting Time + Burst Time │
├────────────────────┼───────────────────────────────────────────────────┤
│ 대기 시간 │ Ready Queue에서 대기한 총 시간 │
│ (Waiting Time) │ 작을수록 좋음 │
├────────────────────┼───────────────────────────────────────────────────┤
│ 응답 시간 │ 요청 제출 ~ 첫 응답까지의 시간 │
│ (Response Time) │ 대화형 시스템에서 특히 중요 │
└────────────────────┴───────────────────────────────────────────────────┘
계산 관계:
Turnaround Time = Completion Time - Arrival Time
Waiting Time = Turnaround Time - Burst Time
Response Time = First Run Time - Arrival Time
1.4 Dispatcher (디스패처)
스케줄러가 “누구에게 CPU를 줄지” 결정하면, 디스패처가 실제로 CPU를 넘기는 작업을 수행한다.
디스패처의 역할:
- Context Switch: 현재 프로세스의 PCB 저장 → 선택된 프로세스의 PCB 복원
- Mode Switch: 커널 모드 → 사용자 모드 전환
- Program Counter 설정: 선택된 프로세스의 적절한 위치로 점프
Dispatch Latency: 디스패처가 하나의 프로세스를 멈추고 다른 프로세스를 실행하기까지 걸리는 시간. 이것이 바로 Context Switch 비용이다.
2. Context Switch의 비용
2.1 Context Switch란
Context Switch는 CPU가 한 프로세스에서 다른 프로세스로 전환할 때 발생하는 작업이다. “공짜 점심은 없다” — Context Switch에는 실질적 비용이 따른다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Context Switch 과정:
프로세스 A 실행 중 프로세스 B 실행 시작
─────────────┐ ┌─────────────
│ │
│ ① A의 상태 저장 │
│ - 레지스터 값들 │
│ - PC (Program │
│ Counter) │
│ - SP (Stack │
│ Pointer) │
│ - 플래그 레지스터 │
│ → PCB_A에 저장 │
│ │
│ ② B의 상태 복원 │
│ - PCB_B에서 로드 │
│ - 레지스터 복원 │
│ - PC 설정 │
│ - 메모리 맵 전환 │
│ │
└────────────────────┘
Context Switch
(순수 오버헤드 구간)
2.2 Context Switch 비용의 구성
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
직접 비용 (Direct Cost):
┌──────────────────────────────────────────────────┐
│ ① 레지스터 저장/복원 : ~수십 ns │
│ ② 메모리 맵 전환 (TLB) : TLB flush → ~수백 ns │
│ ③ 커널 스택 전환 : ~수십 ns │
│ ④ 스케줄러 실행 : O(1) ~ O(log n) │
└──────────────────────────────────────────────────┘
간접 비용 (Indirect Cost) — 더 크다!
┌──────────────────────────────────────────────────┐
│ ① TLB Miss 증가 : 새 프로세스의 TLB 항목이 │
│ 없으므로 Page Table 조회 │
│ ② CPU 캐시 오염 : L1/L2/L3 캐시에 이전 │
│ (Cache Pollution) 프로세스의 데이터 → Miss율↑ │
│ ③ Branch Predictor 무효화: 분기 예측 이력 초기화 │
│ ④ 파이프라인 플러시 : CPU 파이프라인 비움 │
└──────────────────────────────────────────────────┘
총 비용: 직접 비용 ~1-10μs + 간접 비용 ~수십 μs
→ Context Switch가 빈번하면 전체 성능 크게 저하
2.3 프로세스 vs 스레드 Context Switch
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
프로세스 Context Switch:
┌─────────────────────────────────────────┐
│ ✓ 레지스터 저장/복원 │
│ ✓ 메모리 주소 공간 전환 (페이지 테이블 교체) │
│ ✓ TLB 전체 플러시 │
│ ✓ 캐시 오염 (주소 공간이 달라 캐시 무효화) │
│ 비용: 높음 (~수십 μs) │
└─────────────────────────────────────────┘
스레드 Context Switch (같은 프로세스 내):
┌─────────────────────────────────────────┐
│ ✓ 레지스터 저장/복원 │
│ ✗ 메모리 주소 공간 전환 불필요 │
│ ✗ TLB 플러시 불필요 │
│ ✗ 캐시 오염 적음 (같은 주소 공간) │
│ 비용: 낮음 (~수 μs) │
└─────────────────────────────────────────┘
→ 스레드가 프로세스보다 Context Switch 비용이 훨씬 적다
→ 이것이 멀티스레딩의 핵심 장점 중 하나
2.4 Java에서의 Context Switch
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
* Java 스레드의 Context Switch 관련 고려사항
*/
public class ContextSwitchDemo {
// 1. 스레드 수가 CPU 코어 수를 초과하면 Context Switch 발생
// CPU 코어 수 확인
int cores = Runtime.getRuntime().availableProcessors();
// 2. ExecutorService에서 적절한 스레드 풀 크기 설정
// CPU-bound 작업: 코어 수와 같거나 +1
ExecutorService cpuBound = Executors.newFixedThreadPool(cores + 1);
// I/O-bound 작업: 코어 수 × (1 + 대기시간/서비스시간)
// 예: 대기 50ms, 서비스 10ms → cores × 6
ExecutorService ioBound = Executors.newFixedThreadPool(cores * 6);
// 3. synchronized 블록에서의 컨텍스트 스위치
private final Object lock = new Object();
public void criticalSection() {
synchronized (lock) {
// 락을 획득하지 못한 스레드는 BLOCKED 상태로 전환
// → Context Switch 발생
// → 락 해제 시 다시 RUNNABLE로 전환
// → 또 Context Switch 발생
doWork();
}
}
// 4. 가상 스레드 (Java 21+) — Context Switch 비용 최소화
public void virtualThreadExample() {
// 가상 스레드: OS 스레드가 아닌 JVM이 관리하는 경량 스레드
// OS 레벨 Context Switch 없이 JVM 내부에서 전환
try (var executor = Executors.newVirtualThreadPerTaskExecutor()) {
for (int i = 0; i < 10000; i++) {
executor.submit(() -> {
// I/O 대기 시 OS 스레드를 반납 → 다른 가상 스레드가 사용
// OS Context Switch 없이 수만 개의 동시 작업 가능
performIOOperation();
});
}
}
}
private void doWork() { /* ... */ }
private void performIOOperation() { /* ... */ }
}
3. 비선점형 스케줄링 알고리즘
3.1 FCFS (First-Come, First-Served)
가장 단순한 스케줄링: 먼저 도착한 프로세스가 먼저 CPU를 받는다. 비선점형이므로 한번 CPU를 받으면 완료될 때까지 실행한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
FCFS 예제:
프로세스 도착 시간 CPU Burst
─────────────────────────────
P1 0 24
P2 0 3
P3 0 3
도착 순서 P1 → P2 → P3 (도착 시간 동일, 입력 순서 기준):
Gantt Chart:
┌──────────────────────────┬─────┬─────┐
│ P1 │ P2 │ P3 │
└──────────────────────────┴─────┴─────┘
0 24 27 30
Waiting Time:
P1 = 0
P2 = 24
P3 = 27
Average Waiting Time = (0 + 24 + 27) / 3 = 17.0
도착 순서 P2 → P3 → P1:
Gantt Chart:
┌─────┬─────┬──────────────────────────┐
│ P2 │ P3 │ P1 │
└─────┴─────┴──────────────────────────┘
0 3 6 30
Waiting Time:
P2 = 0
P3 = 3
P1 = 6
Average Waiting Time = (0 + 3 + 6) / 3 = 3.0
→ 도착 순서에 따라 평균 대기 시간이 17.0 vs 3.0으로 극적 차이!
Convoy Effect (호위 효과)
FCFS의 가장 큰 문제점이다. 면접에서 반드시 설명할 수 있어야 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Convoy Effect:
CPU-bound 프로세스 (긴 작업)가 먼저 CPU를 점유하면,
뒤에 있는 I/O-bound 프로세스 (짧은 작업)들이 모두 대기해야 한다.
┌──────────────────────────────────────────┐
│ 큰 트럭(P1)이 좁은 도로를 천천히 달리면, │
│ 뒤에 있는 빠른 승용차(P2, P3)들이 │
│ 모두 트럭의 속도에 맞춰야 하는 상황. │
│ │
│ 🚛 ← P1 (CPU burst = 100ms) │
│ 🚗 ← P2 (CPU burst = 2ms) [대기 중] │
│ 🚗 ← P3 (CPU burst = 3ms) [대기 중] │
│ 🚗 ← P4 (CPU burst = 1ms) [대기 중] │
└──────────────────────────────────────────┘
결과:
- CPU 이용률 ↓ (I/O 장치가 유휴 상태)
- 처리량 ↓
- 평균 대기 시간 ↑↑
3.2 SJF (Shortest Job First) — 비선점형
CPU Burst가 가장 짧은 프로세스에게 먼저 CPU를 할당한다. 이론적으로 최적의 평균 대기 시간을 보장한다 (비선점형 기준).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
SJF (Non-Preemptive) 예제:
프로세스 도착 시간 CPU Burst
─────────────────────────────
P1 0 7
P2 2 4
P3 4 1
P4 5 4
Gantt Chart (비선점이므로 P1 완료 후 선택):
┌─────────────┬───┬─────────┬─────────┐
│ P1 │P3 │ P2 │ P4 │
└─────────────┴───┴─────────┴─────────┘
0 7 8 12 16
시간 0: P1만 도착 → P1 실행
시간 7: P1 완료. Ready Queue에 P2(4), P3(1), P4(4)
→ Burst 가장 짧은 P3 선택
시간 8: P3 완료. Ready Queue에 P2(4), P4(4)
→ 동일하면 먼저 도착한 P2 선택
시간 12: P2 완료 → P4 선택
Waiting Time:
P1 = 0 - 0 = 0
P2 = 8 - 2 = 6
P3 = 7 - 4 = 3
P4 = 12 - 5 = 7
Average Waiting Time = (0 + 6 + 3 + 7) / 4 = 4.0
SJF의 근본적 문제: CPU Burst 예측
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
문제: CPU Burst 시간을 미리 알 수 없다!
해결: 지수 평균 (Exponential Averaging)으로 예측
τ(n+1) = α × t(n) + (1 - α) × τ(n)
τ(n+1) : 다음 CPU Burst의 예측값
t(n) : 직전 실제 CPU Burst 시간
τ(n) : 직전 예측값
α : 가중치 (0 ≤ α ≤ 1, 일반적으로 α = 0.5)
예시 (α = 0.5, 초기 예측값 τ₀ = 10):
┌──────┬──────────┬──────────┬──────────────────────────────┐
│ n │ 실제 t(n) │ 예측 τ(n)│ 계산 │
├──────┼──────────┼──────────┼──────────────────────────────┤
│ 0 │ - │ 10 │ 초기값 │
│ 1 │ 6 │ 10 │ τ₁ = 0.5×6 + 0.5×10 = 8.0 │
│ 2 │ 4 │ 8.0 │ τ₂ = 0.5×4 + 0.5×8.0 = 6.0 │
│ 3 │ 6 │ 6.0 │ τ₃ = 0.5×6 + 0.5×6.0 = 6.0 │
│ 4 │ 4 │ 6.0 │ τ₄ = 0.5×4 + 0.5×6.0 = 5.0 │
│ 5 │ 13 │ 5.0 │ τ₅ = 0.5×13 + 0.5×5.0 = 9.0 │
│ 6 │ 13 │ 9.0 │ τ₆ = 0.5×13 + 0.5×9.0 = 11.0│
│ 7 │ 13 │ 11.0 │ τ₇ = 0.5×13 + 0.5×11 = 12.0 │
└──────┴──────────┴──────────┴──────────────────────────────┘
α = 0 : 예측값이 절대 변하지 않음 (과거만 반영)
α = 1 : 직전 실제 값만 사용 (현재만 반영)
α = 0.5: 과거와 현재를 균형 있게 반영 (일반적)
4. 선점형 스케줄링 알고리즘
4.1 SRTF (Shortest Remaining Time First)
SJF의 선점형 버전이다. 새로운 프로세스가 도착했을 때, 현재 실행 중인 프로세스의 남은 시간보다 새 프로세스의 Burst가 더 짧으면 선점한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
SRTF 예제:
프로세스 도착 시간 CPU Burst
─────────────────────────────
P1 0 7
P2 2 4
P3 4 1
P4 5 4
Gantt Chart:
┌─────┬─────┬───┬─────┬───────────┬─────┐
│ P1 │ P2 │P3 │ P2 │ P4 │ P1 │
└─────┴─────┴───┴─────┴───────────┴─────┘
0 2 4 5 7 11 16
시간 0: P1(남은 7) 실행
시간 2: P2(4) 도착. P1 남은=5. 4 < 5 → P2 선점!
시간 4: P3(1) 도착. P2 남은=2. 1 < 2 → P3 선점!
시간 5: P3 완료. P4(4) 도착.
Ready: P1(남은 5), P2(남은 2), P4(4)
→ P2(2)가 가장 짧음 → P2 실행
시간 7: P2 완료. Ready: P1(5), P4(4) → P4 실행
시간 11: P4 완료 → P1 실행
시간 16: P1 완료
Waiting Time:
P1 = (0-0) + (11-2) = 9 (0~2 실행, 2~11 대기, 11~16 실행)
→ Turnaround=16, Burst=7, Waiting=16-0-7=9
P2 = (2-2) + (5-4) = 1
→ Turnaround=7-2=5, Burst=4, Waiting=5-4=1
P3 = 0
→ Turnaround=5-4=1, Burst=1, Waiting=0
P4 = 7-5 = 2
→ Turnaround=11-5=6, Burst=4, Waiting=2
Average Waiting Time = (9 + 1 + 0 + 2) / 4 = 3.0
비교: SJF(비선점형)의 AWT = 4.0 → SRTF가 더 좋다!
→ SRTF는 이론적 최적 (Optimal)이지만, Context Switch 비용 증가
4.2 Round Robin (RR)
Time Quantum(시간 할당량)을 정하고, Ready Queue의 프로세스들이 돌아가며(Round Robin) CPU를 사용한다. 대화형(Interactive) 시스템에 가장 적합한 알고리즘이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Round Robin 동작 원리:
Time Quantum = q
┌─────────────────────────────────────────────┐
│ Ready Queue (FIFO) │
│ │
│ [P1] → [P2] → [P3] → [P4] → ... │
│ │
│ 1. 큐의 맨 앞 프로세스에게 CPU를 q만큼 할당 │
│ 2-a. q 내에 완료 → 다음 프로세스 선택 │
│ 2-b. q 내에 미완료 → 큐의 맨 뒤로 이동 │
│ 3. 반복 │
└─────────────────────────────────────────────┘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Round Robin 예제 (Time Quantum = 4):
프로세스 도착 시간 CPU Burst
─────────────────────────────
P1 0 24
P2 0 3
P3 0 3
Gantt Chart:
┌──────┬─────┬─────┬──────┬──────┬──────┬──────┬──────┬──────┐
│ P1 │ P2 │ P3 │ P1 │ P1 │ P1 │ P1 │ P1 │ P1 │
└──────┴─────┴─────┴──────┴──────┴──────┴──────┴──────┴──────┘
0 4 7 10 14 18 22 26 30
시간 0~4 : P1 실행 (남은 20), 큐: [P2, P3, P1]
시간 4~7 : P2 실행 (3 < 4이므로 완료), 큐: [P3, P1]
시간 7~10 : P3 실행 (3 < 4이므로 완료), 큐: [P1]
시간 10~30: P1 실행 (남은 20, 혼자이므로 계속 실행)
Waiting Time:
P1 = (10 - 4) = 6 (0~4 실행, 4~10 대기, 10~30 실행)
P2 = 4
P3 = 7
Average Waiting Time = (6 + 4 + 7) / 3 = 5.67
비교: FCFS(P1→P2→P3) AWT = 17.0 → RR이 훨씬 좋다!
FCFS(P2→P3→P1) AWT = 3.0 → 이 경우는 FCFS가 낫다.
Time Quantum의 트레이드오프
이 부분은 면접에서 매우 자주 출제된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
Time Quantum 크기의 영향:
q가 너무 크면 (q → ∞):
┌──────────────────────────────────────┐
│ → FCFS와 동일하게 동작 │
│ → Convoy Effect 발생 가능 │
│ → 응답 시간 ↑↑ │
│ → Context Switch ↓ (오버헤드 적음) │
└──────────────────────────────────────┘
q가 너무 작으면 (q → 0):
┌──────────────────────────────────────┐
│ → "Processor Sharing" │
│ → n개 프로세스가 각각 1/n 속도의 │
│ 자기만의 CPU를 가진 것처럼 동작 │
│ → 응답 시간 ↓ (매우 빠름) │
│ → Context Switch ↑↑ (오버헤드 심각!) │
└──────────────────────────────────────┘
적절한 q의 선택:
┌──────────────────────────────────────────────┐
│ 경험적 규칙: │
│ - q는 전체 CPU Burst의 80%가 q보다 짧도록 설정 │
│ - 일반적으로 10ms ~ 100ms │
│ - Context Switch 시간의 10배 이상이어야 효율적 │
│ │
│ 예: Context Switch = 10μs이면 │
│ q ≥ 100μs (= 0.1ms) 이상이어야 함 │
│ (그래야 유효 작업 비율이 90% 이상) │
└──────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────┐
│ │
│ 평균 Turnaround Time │
│ ▲ │
│ │ ╲ │
│ │ ╲ │
│ │ ╲ ╱╲ │
│ │ ╲ ╱ ╲ │
│ │ ╲ ╱ ╲ │
│ │ ╲╱ ────── │
│ │ │
│ └──────────────────────────────────── ─→ q │
│ 작음 큼 │
│ (Context Switch (FCFS처럼 최적의 │
│ 오버헤드 심각) 동작) q 존재 │
└──────────────────────────────────────────────────────┘
4.3 Priority Scheduling (우선순위 스케줄링)
각 프로세스에 우선순위(Priority)를 부여하고, 우선순위가 가장 높은 프로세스에게 CPU를 할당한다. SJF는 Priority Scheduling의 특수한 경우이다 (CPU Burst가 짧을수록 우선순위가 높음).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Priority Scheduling 예제 (숫자가 작을수록 높은 우선순위):
프로세스 CPU Burst 우선순위
─────────────────────────────
P1 10 3
P2 1 1 ← 최고 우선순위
P3 2 4
P4 1 5
P5 5 2
Gantt Chart:
┌───┬───────┬────────────┬────┬───┐
│P2 │ P5 │ P1 │ P3 │P4 │
└───┴───────┴────────────┴────┴───┘
0 1 6 16 18 19
Waiting Time:
P1 = 6, P2 = 0, P3 = 16, P4 = 18, P5 = 1
Average Waiting Time = (6 + 0 + 16 + 18 + 1) / 5 = 8.2
Starvation (기아 현상) — 핵심 문제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Starvation (기아):
높은 우선순위 프로세스가 계속 도착하면,
낮은 우선순위 프로세스는 영원히 CPU를 받지 못할 수 있다.
Ready Queue:
┌──────────────────────────────────────┐
│ [우선순위 1] [우선순위 1] [우선순위 2] │ ← 계속 높은 우선순위가 도착
│ ... │
│ [우선순위 99] │ ← 영원히 실행 안 됨!
└──────────────────────────────────────┘
실제 사례:
1973년 MIT에서 IBM 7094 셧다운 시,
1967년에 제출되어 6년간 실행되지 못한 프로세스가 발견되었다!
Aging (에이징) — 기아 해결책
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Aging 기법:
시간이 지남에 따라 대기 중인 프로세스의 우선순위를 점진적으로 높인다.
시간 경과에 따른 우선순위 변화 (숫자 작을수록 높은 우선순위):
시간 0 : P_low의 우선순위 = 100 (매우 낮음)
시간 +1s : P_low의 우선순위 = 99
시간 +2s : P_low의 우선순위 = 98
...
시간 +90s: P_low의 우선순위 = 10 → 이제 실행될 기회 획득!
구현:
┌────────────────────────────────────────────────┐
│ 매 시간 단위마다: │
│ for each process P in Ready Queue: │
│ if P is not running: │
│ P.priority = P.priority - 1 (높이기) │
│ │
│ → 충분히 오래 기다린 프로세스는 결국 최고 우선순위에 │
│ 도달하여 실행됨 → Starvation 해결! │
└────────────────────────────────────────────────┘
5. MLFQ (Multi-Level Feedback Queue)
5.1 현대 운영체제의 스케줄러
MLFQ는 Linux, macOS, Windows 등 현대 운영체제가 실제로 사용하는 스케줄링 알고리즘의 기반이다. 면접에서 “실제 OS는 어떤 스케줄링을 사용하나요?”라는 질문에 반드시 답할 수 있어야 한다.
5.2 Multi-Level Queue (MLQ) — MLFQ의 전신
먼저 단순한 Multi-Level Queue를 이해하자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Multi-Level Queue:
각 프로세스를 유형별로 영구적으로 분류하여 서로 다른 큐에 배치한다.
┌─────────────────────────────────────────────┐
│ Queue 0 (최고 우선순위): System Processes │
│ → 항상 먼저 실행 │
├─────────────────────────────────────────────┤
│ Queue 1: Interactive Processes │
│ → Queue 0이 비어야 실행 │
├─────────────────────────────────────────────┤
│ Queue 2: Batch Processes │
│ → Queue 0, 1이 비어야 실행 │
├─────────────────────────────────────────────┤
│ Queue 3 (최저 우선순위): Student Processes │
│ → Queue 0, 1, 2가 비어야 실행 │
└─────────────────────────────────────────────┘
문제: 프로세스가 한번 배치되면 다른 큐로 이동 불가
→ Starvation 가능
→ 프로세스의 행동 변화에 적응 불가
5.3 MLFQ의 동작 원리
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
MLFQ (Multi-Level Feedback Queue):
핵심 차이: 프로세스가 큐 사이를 이동할 수 있다! ("Feedback")
┌─────────────────────────────────────────────────────┐
│ Queue 0 (최고 우선순위, q = 8ms) [Round Robin] │
│ 새로 도착한 프로세스는 모두 여기서 시작 │
│ ┌───┬───┬───┐ │
│ │P1 │P5 │P7 │ │
│ └─┬─┴───┴───┘ │
│ │ q(8ms) 내 미완료 시 → 아래로 강등 │
├─────▼───────────────────────────────────────────────┤
│ Queue 1 (중간 우선순위, q = 16ms) [Round Robin] │
│ ┌───┬───┐ │
│ │P2 │P4 │ │
│ └─┬─┴───┘ │
│ │ q(16ms) 내 미완료 시 → 아래로 강등 │
├─────▼───────────────────────────────────────────────┤
│ Queue 2 (낮은 우선순위, q = 32ms) [Round Robin] │
│ ┌───┬───┐ │
│ │P3 │P6 │ │
│ └─┬─┴───┘ │
│ │ q(32ms) 내 미완료 시 → 아래로 강등 │
├─────▼───────────────────────────────────────────────┤
│ Queue 3 (최저 우선순위) [FCFS] │
│ ┌───┐ │
│ │P8 │ ← CPU-bound 프로세스가 결국 여기에 도달 │
│ └───┘ │
└─────────────────────────────────────────────────────┘
5.4 MLFQ의 핵심 규칙
1
2
3
4
5
6
7
MLFQ 5대 규칙:
Rule 1: Priority(A) > Priority(B) → A 실행
Rule 2: Priority(A) = Priority(B) → Round Robin
Rule 3: 새 프로세스는 최상위 큐에 배치
Rule 4: 프로세스가 주어진 Time Quantum을 모두 사용하면 한 단계 강등
Rule 5: 일정 주기(S)마다 모든 프로세스를 최상위 큐로 이동 (Priority Boost)
5.5 MLFQ의 동작 시나리오
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
시나리오 1: Short I/O-bound 프로세스
P_io가 도착 → Queue 0에 배치
P_io가 2ms 실행 후 I/O 요청 (q=8ms 미만)
I/O 완료 → Queue 0에 다시 배치 ← 강등 없음!
P_io가 3ms 실행 후 I/O 요청
...반복
결과: I/O-bound 프로세스는 항상 최상위 큐에 머무름
→ 빠른 응답 시간 보장!
시나리오 2: Long CPU-bound 프로세스
P_cpu가 도착 → Queue 0에 배치
P_cpu가 8ms 실행 (q=8ms 모두 사용) → Queue 1로 강등
P_cpu가 16ms 실행 (q=16ms 모두 사용) → Queue 2로 강등
P_cpu가 32ms 실행 (q=32ms 모두 사용) → Queue 3(FCFS)로 강등
결과: CPU-bound 프로세스는 점점 낮은 큐로 이동
→ 긴 작업은 배경에서 처리
시나리오 3: 행동 변화 (CPU-bound → I/O-bound)
P가 Queue 3에서 CPU 작업 중
→ Priority Boost 발생!
P가 Queue 0으로 이동
→ 이제 I/O 작업 패턴이면 Queue 0에 유지
결과: 프로세스의 행동 변화에 적응 가능!
5.6 Priority Boost — Starvation 방지
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Priority Boost (우선순위 부스트):
문제: MLFQ에서도 CPU-bound 프로세스는 Queue 3에서 Starvation 가능
해결: 주기적으로(매 S초마다) 모든 프로세스를 Queue 0으로 이동
시간 →
┌─────────────────┐ ┌─────────────────┐ ┌──────
│ 일반 운영 │ │ 일반 운영 │ │
│ Q0: P1 P2 │ │ Q0: P1 P2 │ │
│ Q1: P3 │ │ Q1: P3 │ │
│ Q2: P4 P5 │ │ Q2: P4 P5 │ │
│ Q3: P6 P7 P8 │ │ Q3: P6 P7 P8 │ │
└────────┬────────┘ └────────┬────────┘ └──────
│ │
Priority Boost! Priority Boost!
모든 프로세스를 모든 프로세스를
Queue 0으로 Queue 0으로
S의 선택:
S가 너무 크면 → Starvation 여전히 발생
S가 너무 작으면 → CPU-bound가 항상 높은 우선순위 유지
→ I/O-bound와 구분 불가
일반적으로 S = 수십 ms ~ 수 초
5.7 Gaming Prevention — 악용 방지
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Gaming (악용) 문제:
악의적 프로세스가 Time Quantum을 다 쓰기 직전에
의도적으로 I/O를 호출하여 강등을 회피할 수 있다.
P_gaming의 행동:
Queue 0에서 7.9ms 실행 (q=8ms)
→ 의도적 I/O 호출 (0.1ms짜리)
→ I/O 완료 후 Queue 0에 다시 배치! ← 강등 회피!
→ 반복: 사실상 CPU를 독점
해결: 누적 사용 시간 추적 (Accounting)
┌─────────────────────────────────────────────┐
│ 프로세스가 해당 큐에서 사용한 CPU 시간을 누적 │
│ 누적 시간 ≥ Time Quantum → 강등 │
│ │
│ P_gaming: │
│ 1차: 7.9ms 실행 + I/O → 누적 = 7.9ms │
│ 2차: 0.1ms 실행 → 누적 = 8.0ms ≥ q(8ms) │
│ → 강등! 악용 불가! │
└─────────────────────────────────────────────┘
6. 실제 운영체제의 스케줄러
6.1 Linux의 CFS (Completely Fair Scheduler)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
CFS (Completely Fair Scheduler):
Linux 2.6.23 (2007)부터 기본 스케줄러.
핵심 아이디어: 모든 프로세스에게 "공정하게" CPU 시간을 분배
핵심 개념 - vruntime (virtual runtime):
┌───────────────────────────────────────────────────┐
│ vruntime = 프로세스가 실제로 CPU를 사용한 시간 │
│ × (nice 값에 따른 가중치) │
│ │
│ CFS는 항상 vruntime이 가장 작은 프로세스를 선택 │
│ → vruntime이 작다 = CPU를 덜 사용했다 = 불공평하다 │
│ → 그 프로세스에게 CPU를 준다! │
└───────────────────────────────────────────────────┘
자료구조: Red-Black Tree
┌───────────────────────────────────────────────────┐
│ │
│ [vruntime: 15] │
│ ╱ ╲ │
│ [vruntime: 8] [vruntime: 22] │
│ ╱ ╲ ╱ ╲ │
│ [vr: 3] [vr: 12] [vr: 18] [vr: 30] │
│ ↑ │
│ └─ 최소 vruntime → 이 프로세스가 다음에 실행! │
│ │
│ 삽입/삭제/최솟값 조회: O(log n) │
└───────────────────────────────────────────────────┘
nice 값과 가중치:
┌──────────────────────────────────────────┐
│ nice = -20 (최고 우선순위): 가중치 88761 │
│ nice = 0 (기본): 가중치 1024 │
│ nice = +19 (최저 우선순위): 가중치 15 │
│ │
│ vruntime 증가 속도: │
│ nice가 높은(낮은 우선순위) 프로세스 │
│ → vruntime이 빠르게 증가 │
│ → 더 적은 CPU 시간 할당 │
│ │
│ nice가 낮은(높은 우선순위) 프로세스 │
│ → vruntime이 천천히 증가 │
│ → 더 많은 CPU 시간 할당 │
└──────────────────────────────────────────┘
6.2 Linux EEVDF (Earliest Eligible Virtual Deadline First)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
EEVDF (Linux 6.6, 2023~ 부터 CFS 대체):
CFS의 한계를 보완한 새로운 스케줄러.
CFS의 문제:
┌───────────────────────────────────────┐
│ - 응답 지연(latency)이 예측 불가능 │
│ - 짧은 작업이라도 긴 작업과 동일 취급 │
│ - sleeper fairness 처리의 복잡성 │
└───────────────────────────────────────┘
EEVDF의 해결:
┌───────────────────────────────────────────────────┐
│ 각 프로세스에 "가상 데드라인(Virtual Deadline)"을 │
│ 부여하고, 데드라인이 가장 빠른 프로세스를 선택 │
│ │
│ Virtual Deadline = 현재 시간 + (Time Slice / 가중치) │
│ │
│ 장점: │
│ - 짧은 작업이 자연스럽게 빨리 스케줄됨 │
│ - latency가 예측 가능해짐 │
│ - CFS의 복잡한 휴리스틱 제거 │
└───────────────────────────────────────────────────┘
6.3 Windows의 스케줄러
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Windows 스케줄러:
┌────────────────────────────────────────────────────┐
│ 32개의 우선순위 레벨 (0~31) │
│ │
│ 16~31: Real-Time 클래스 (고정 우선순위) │
│ 1~15: Variable 클래스 (동적 우선순위) │
│ 0: Idle 스레드 (시스템 유휴 시에만 실행) │
│ │
│ Variable 클래스의 동적 우선순위 조정: │
│ - I/O 완료 시: 우선순위 ↑ (Boost) │
│ - 포그라운드 프로세스: 우선순위 ↑ + 긴 Time Quantum │
│ - Time Quantum 소진 시: 우선순위 ↓ │
│ - 오래 대기 시: Priority Boost (Starvation 방지) │
└────────────────────────────────────────────────────┘
7. 스케줄링 알고리즘 비교 종합
7.1 알고리즘 특성 비교표
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
┌──────────────┬──────────┬────────────┬────────────┬──────────────┐
│ 알고리즘 │ 선점 여부 │ Starvation │ Convoy │ 적합한 환경 │
│ │ │ │ Effect │ │
├──────────────┼──────────┼────────────┼────────────┼──────────────┤
│ FCFS │ 비선점 │ 없음 │ 있음 │ 배치 시스템 │
├──────────────┼──────────┼────────────┼────────────┼──────────────┤
│ SJF │ 비선점 │ 있음 │ 없음 │ 이론적 최적 │
├──────────────┼──────────┼────────────┼────────────┼──────────────┤
│ SRTF │ 선점 │ 있음 │ 없음 │ 이론적 최적 │
├──────────────┼──────────┼────────────┼────────────┼──────────────┤
│ Round Robin │ 선점 │ 없음 │ 없음 │ 대화형 시스템 │
├──────────────┼──────────┼────────────┼────────────┼──────────────┤
│ Priority │ 둘 다 │ 있음 │ 없음 │ 실시간 시스템 │
├──────────────┼──────────┼────────────┼────────────┼──────────────┤
│ MLFQ │ 선점 │ 해결(Boost)│ 없음 │ 범용 OS │
├──────────────┼──────────┼────────────┼────────────┼──────────────┤
│ CFS │ 선점 │ 없음(공정) │ 없음 │ Linux │
└──────────────┴──────────┴────────────┴────────────┴──────────────┘
7.2 성능 비교 (동일 프로세스 세트)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
프로세스 세트:
P1(Burst=10), P2(Burst=1), P3(Burst=2), P4(Burst=1), P5(Burst=5)
모두 시간 0에 도착, 도착 순서: P1 → P2 → P3 → P4 → P5
FCFS:
┌──────────┬───┬────┬───┬───────┐
│ P1 │P2 │ P3 │P4 │ P5 │
└──────────┴───┴────┴───┴───────┘
0 10 11 13 14 19
AWT = (0+10+11+13+14)/5 = 9.6
SJF:
┌───┬───┬────┬───────┬──────────┐
│P2 │P4 │ P3 │ P5 │ P1 │
└───┴───┴────┴───────┴──────────┘
0 1 2 4 9 19
AWT = (9+0+1+2+4)/5 = 3.2 ← 최적!
RR (q=2):
┌────┬───┬────┬───┬────┬────┬────┬────┬────┬────┐
│ P1 │P2 │ P3 │P4 │ P5 │ P1 │ P5 │ P1 │ P1 │ P1 │
└────┴───┴────┴───┴────┴────┴────┴────┴────┴────┘
0 2 3 5 6 8 10 12 14 16 19
단, P2(1ms), P4(1ms)는 q 내 완료
실제 Gantt (q=2):
┌────┬───┬────┬───┬────┬────┬────┬────┬────┐
│ P1 │P2 │ P3 │P4 │ P5 │ P1 │ P5 │ P1 │ P1 │
└────┴───┴────┴───┴────┴────┴────┴────┴────┘
0 2 3 5 6 8 10 12 14 19
P1: 0-2, 8-10, 12-14, 14-19 → WT = (8-2)+(12-10)+(14-14) = 6+2+0 = 8
P2: 2-3 → WT = 2
P3: 3-5 → WT = 3
P4: 5-6 → WT = 5
P5: 6-8, 10-12 → WT = 6 + (10-8) = 6+2 = 8..
간략 계산:
P1: Turnaround=19, Burst=10, WT=9
P2: Turnaround=3, Burst=1, WT=2
P3: Turnaround=5, Burst=2, WT=3
P4: Turnaround=6, Burst=1, WT=5
P5: Turnaround=12, Burst=5, WT=7
AWT = (9+2+3+5+7)/5 = 5.2
요약:
FCFS = 9.6 | SJF = 3.2 | RR(q=2) = 5.2
SJF가 이론적 최적, RR은 공정성 보장, FCFS는 비효율적
8. 멀티프로세서 스케줄링
8.1 멀티코어 시대의 스케줄링
현대 CPU는 멀티코어가 기본이다. 멀티프로세서 환경에서는 추가적인 고려사항이 필요하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
멀티프로세서 스케줄링 접근법:
1. 비대칭 멀티프로세싱 (Asymmetric Multiprocessing)
┌─────────────────────────────────────────┐
│ 하나의 마스터 프로세서가 모든 스케줄링 결정 │
│ 나머지 프로세서는 사용자 코드만 실행 │
│ 장점: 데이터 공유 문제 없음, 구현 단순 │
│ 단점: 마스터가 병목 │
└─────────────────────────────────────────┘
2. 대칭 멀티프로세싱 (Symmetric Multiprocessing, SMP)
┌─────────────────────────────────────────┐
│ 각 프로세서가 독자적으로 스케줄링 결정 │
│ 공유 Ready Queue 또는 프로세서별 개별 큐 │
│ 장점: 병목 없음 │
│ 단점: 동기화 필요, 캐시 친화성 고려 │
│ → 현대 OS의 표준 방식 │
└─────────────────────────────────────────┘
8.2 Cache Affinity (캐시 친화성)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Cache Affinity:
프로세스를 이전에 실행했던 CPU에 다시 배치하면
캐시 히트율이 높아져 성능이 향상된다.
┌────────────────────────────────────────────┐
│ CPU 0에서 P1 실행: │
│ CPU 0의 캐시에 P1의 데이터 적재 │
│ │
│ Context Switch 후 P1이 CPU 1에서 재실행: │
│ CPU 1의 캐시에 P1의 데이터 없음! │
│ → Cold Start, 캐시 미스 빈발 │
│ → 성능 저하 │
│ │
│ Context Switch 후 P1이 CPU 0에서 재실행: │
│ CPU 0의 캐시에 P1의 데이터가 아직 있을 가능성│
│ → Warm Cache, 캐시 히트율 높음 │
│ → 성능 향상! │
└────────────────────────────────────────────┘
구현 방식:
- Soft Affinity: 가능하면 같은 CPU에 배치 (Linux 기본)
- Hard Affinity: 반드시 지정된 CPU에서만 실행
(Linux: sched_setaffinity() 시스템 콜)
8.3 Load Balancing (부하 분산)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Load Balancing 전략:
┌──────────────────────────────────────────────┐
│ Push Migration: │
│ 주기적으로 각 CPU의 부하를 확인 │
│ 과부하 CPU → 유휴 CPU로 프로세스 이동 │
│ │
│ CPU 0 [■■■■■■■■] ──push──→ CPU 1 [■■] │
│ (과부하) (여유) │
└──────────────────────────────────────────────┘
┌──────────────────────────────────────────────┐
│ Pull Migration: │
│ 유휴 CPU가 바쁜 CPU에서 프로세스를 가져옴 │
│ │
│ CPU 0 [■■■■■■■■] ←─pull── CPU 1 [ ] │
│ (과부하) (유휴) │
└──────────────────────────────────────────────┘
Trade-off:
Load Balancing ↔ Cache Affinity
→ 부하 분산을 위해 프로세스를 이동하면 캐시 친화성이 깨짐
→ 현대 OS는 두 요소를 모두 고려하여 균형점을 찾음
9. Java/Spring에서의 스케줄링 연계
9.1 Java 스레드와 OS 스케줄링
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
* Java 스레드는 OS 네이티브 스레드에 1:1 매핑된다 (HotSpot JVM).
* 따라서 Java 스레드의 스케줄링은 OS 스케줄러가 담당한다.
*/
public class JavaThreadScheduling {
// 1. 스레드 우선순위 → OS 우선순위로 매핑
public void threadPriority() {
Thread t1 = new Thread(() -> cpuIntensiveWork());
Thread t2 = new Thread(() -> cpuIntensiveWork());
// Java 우선순위: 1 (MIN) ~ 10 (MAX), 기본값 5 (NORM)
t1.setPriority(Thread.MAX_PRIORITY); // 10
t2.setPriority(Thread.MIN_PRIORITY); // 1
// 주의: OS마다 우선순위 매핑이 다르므로
// Java 우선순위가 반드시 보장되지 않는다!
// Linux: 일반적으로 Java 우선순위를 무시 (CFS는 nice 기반)
// Windows: Java 우선순위를 Windows 우선순위로 매핑
t1.start();
t2.start();
}
// 2. yield() — 자발적 CPU 양보
public void yieldExample() {
Thread t = new Thread(() -> {
for (int i = 0; i < 1000000; i++) {
doWork(i);
if (i % 100 == 0) {
// 현재 Time Slice를 포기하고 Ready Queue로 돌아감
// 힌트일 뿐, OS 스케줄러가 무시할 수 있음
Thread.yield();
}
}
});
t.start();
}
// 3. sleep() vs yield() vs wait()
// sleep(ms): TIMED_WAITING 상태. 지정 시간 후 RUNNABLE로 전환
// → Context Switch 발생
// yield(): RUNNABLE 유지. 같은 우선순위의 다른 스레드에게 기회 양보
// → Context Switch 발생할 수도 안 할 수도 있음
// wait(): WAITING 상태. notify()/notifyAll() 호출까지 대기
// → Context Switch 발생
private void cpuIntensiveWork() { /* ... */ }
private void doWork(int i) { /* ... */ }
}
9.2 스레드 풀과 스케줄링 효율
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
* 스레드 풀 크기와 CPU 스케줄링의 관계
*/
public class ThreadPoolSchedulingRelation {
/**
* CPU-bound 작업:
* 스레드 수 = 코어 수 + 1
* → Context Switch를 최소화하면서 하나의 코어가 유휴 상태일 때를 대비
*/
public ExecutorService cpuBoundPool() {
int cores = Runtime.getRuntime().availableProcessors();
return new ThreadPoolExecutor(
cores + 1, // corePoolSize
cores + 1, // maxPoolSize
0L, TimeUnit.SECONDS,
new LinkedBlockingQueue<>(),
new ThreadFactory() {
final AtomicInteger count = new AtomicInteger(0);
@Override
public Thread newThread(Runnable r) {
Thread t = new Thread(r, "cpu-worker-" + count.getAndIncrement());
t.setDaemon(false);
return t;
}
}
);
}
/**
* I/O-bound 작업:
* 스레드 수 = 코어 수 × (1 + W/S)
* W = 대기 시간 (Waiting Time)
* S = 서비스 시간 (Service Time, CPU 사용 시간)
*
* 예: DB 쿼리 (W=50ms, S=5ms) → cores × 11
* 예: HTTP 호출 (W=200ms, S=10ms) → cores × 21
*/
public ExecutorService ioBoundPool() {
int cores = Runtime.getRuntime().availableProcessors();
double waitTime = 50.0; // ms
double serviceTime = 5.0; // ms
int optimalThreads = (int) (cores * (1 + waitTime / serviceTime));
return Executors.newFixedThreadPool(optimalThreads);
}
/**
* 가상 스레드 (Java 21+):
* OS 스레드 스케줄링 부담을 크게 줄인다.
*
* 전통적 스레드: 1 Java Thread = 1 OS Thread
* → 10,000 스레드 = 10,000 OS 스레드 → Context Switch 폭발
*
* 가상 스레드: N 가상 스레드를 M OS 스레드에 매핑 (N >> M)
* → 10,000 가상 스레드 ≈ cores개의 OS 스레드
* → OS Context Switch 최소화
*/
public ExecutorService virtualThreadPool() {
return Executors.newVirtualThreadPerTaskExecutor();
}
}
9.3 Spring의 @Async와 스케줄링
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
@Configuration
@EnableAsync
public class AsyncConfig implements AsyncConfigurer {
/**
* Spring @Async의 기본 SimpleAsyncTaskExecutor는
* 매 요청마다 새 스레드를 생성한다 → OS 스케줄러 부하 증가!
*
* 반드시 ThreadPoolTaskExecutor로 변경해야 한다.
*/
@Override
public Executor getAsyncExecutor() {
ThreadPoolTaskExecutor executor = new ThreadPoolTaskExecutor();
int cores = Runtime.getRuntime().availableProcessors();
executor.setCorePoolSize(cores * 2); // 기본 스레드 수
executor.setMaxPoolSize(cores * 4); // 최대 스레드 수
executor.setQueueCapacity(500); // 큐 용량
executor.setThreadNamePrefix("async-"); // 스레드 이름 접두사
// Rejection Policy: 큐와 최대 스레드 모두 가득 찼을 때
// CallerRunsPolicy: 호출 스레드에서 직접 실행 (백프레셔)
executor.setRejectedExecutionHandler(
new ThreadPoolExecutor.CallerRunsPolicy()
);
executor.initialize();
return executor;
}
}
@Service
public class NotificationService {
// @Async 메서드는 별도 스레드에서 실행
// → OS 스케줄러가 이 스레드의 CPU 할당을 결정
@Async
public CompletableFuture<Void> sendNotification(String userId, String message) {
// I/O-bound 작업: 외부 API 호출
// 이 스레드가 I/O 대기 중이면 OS 스케줄러가
// 다른 스레드에게 CPU를 할당 (Context Switch)
notificationApi.send(userId, message);
return CompletableFuture.completedFuture(null);
}
}
10. 면접 빈출 질문 정리
Q1. 선점형 스케줄링과 비선점형 스케줄링의 차이를 설명하세요.
비선점형(Non-Preemptive): 프로세스가 CPU를 할당받으면, 자발적으로 반납(종료 또는 I/O 요청)할 때까지 CPU를 점유한다. 다른 프로세스가 강제로 뺏을 수 없다. FCFS, SJF(비선점형)이 해당한다.
선점형(Preemptive): 운영체제가 실행 중인 프로세스로부터 CPU를 강제로 회수할 수 있다. 타이머 인터럽트, 더 높은 우선순위 프로세스의 도착 등이 선점의 트리거가 된다. Round Robin, SRTF, Priority(선점형)이 해당한다.
현대 운영체제는 대부분 선점형 스케줄링을 사용한다. 비선점형은 하나의 프로세스가 CPU를 독점하여 다른 프로세스가 무한 대기하는 상황을 만들 수 있기 때문이다. 다만 선점형은 Context Switch 비용이 추가로 발생하며, 공유 자원 접근 시 동기화 문제를 고려해야 한다.
Q2. Convoy Effect란 무엇이며, 어떻게 해결할 수 있나요?
Convoy Effect는 FCFS 스케줄링에서 발생하는 문제이다. CPU Burst가 매우 긴 프로세스(CPU-bound)가 먼저 CPU를 점유하면, 뒤에 대기 중인 짧은 프로세스(I/O-bound)들이 모두 길게 대기하게 된다. 마치 좁은 도로에서 느린 트럭 뒤에 빠른 차들이 줄 서는 것과 같다.
이로 인해 CPU 이용률과 I/O 장치 이용률이 모두 떨어진다. I/O-bound 프로세스가 CPU를 기다리느라 I/O 요청을 하지 못해, I/O 장치도 유휴 상태가 되기 때문이다.
해결 방법: SJF(짧은 작업 우선), Round Robin(타임 퀀텀으로 분할), MLFQ(CPU를 많이 쓰는 프로세스를 낮은 큐로 강등) 등 선점형 또는 짧은 작업을 우선시하는 알고리즘을 사용하면 된다.
Q3. Starvation(기아)이란 무엇이며, Aging은 어떻게 이를 해결하나요?
Starvation은 특정 프로세스가 무한히 CPU를 할당받지 못하는 현상이다. 주로 Priority Scheduling에서 발생한다. 높은 우선순위 프로세스가 계속 도착하면, 낮은 우선순위 프로세스는 영원히 Ready Queue에서 대기한다. SJF에서도 짧은 프로세스가 계속 도착하면 긴 프로세스에 Starvation이 발생한다.
Aging은 대기 시간에 비례하여 프로세스의 우선순위를 점진적으로 높이는 기법이다. 예를 들어, 매 1초마다 대기 중인 프로세스의 우선순위를 1씩 높인다. 충분히 오래 대기하면 결국 최고 우선순위에 도달하여 CPU를 할당받게 된다. MLFQ에서는 Priority Boost(주기적으로 모든 프로세스를 최상위 큐로 이동)로 같은 효과를 달성한다.
Q4. Round Robin의 Time Quantum 크기에 따른 트레이드오프를 설명하세요.
Time Quantum(q)이 너무 크면 FCFS와 동일하게 동작하여 Convoy Effect가 발생할 수 있고, 응답 시간이 길어진다. 극단적으로 q가 무한대이면 완전한 FCFS이다.
q가 너무 작으면 Context Switch가 너무 빈번하게 발생하여 유효 작업 시간 대비 오버헤드가 과도해진다. 예를 들어 q = 1μs이고 Context Switch = 10μs이면, CPU의 90%가 Context Switch에 낭비된다. 극단적으로 q가 0에 수렴하면 “Processor Sharing”이 되지만 현실적이지 않다.
적절한 q의 경험적 규칙: CPU Burst의 80%가 q 내에 완료되도록 설정한다. 일반적으로 10ms~100ms이며, Context Switch 비용의 최소 10배 이상이어야 효율적이다.
Q5. MLFQ의 동작 원리와 장점을 설명하세요.
MLFQ는 여러 단계의 Ready Queue를 두고, 프로세스의 행동 패턴에 따라 큐 간 이동(Feedback)을 허용하는 알고리즘이다.
동작: 새 프로세스는 최상위 큐(가장 높은 우선순위, 짧은 Time Quantum)에 배치된다. Time Quantum을 다 사용하면 한 단계 아래 큐로 강등된다. Time Quantum 내에 I/O를 요청하면 같은 큐에 유지된다. Starvation 방지를 위해 주기적으로 모든 프로세스를 최상위 큐로 올린다(Priority Boost).
장점: 사전 정보 없이도 I/O-bound(짧은 작업)와 CPU-bound(긴 작업)를 자동으로 구분한다. I/O-bound 프로세스는 높은 큐에서 빠른 응답을 받고, CPU-bound 프로세스는 낮은 큐에서 긴 Time Quantum으로 효율적으로 처리된다. 프로세스의 행동이 변하면(CPU → I/O) 자동으로 적응한다. 이것이 Linux, macOS, Windows 등 실제 OS 스케줄러의 기반이 되는 이유이다.
Q6. Context Switch 비용에 대해 설명하세요. 프로세스와 스레드의 차이는?
Context Switch 비용은 직접 비용과 간접 비용으로 나뉜다.
직접 비용: 레지스터 저장/복원, 커널 스택 전환, 스케줄러 실행 등 (~수 μs).
간접 비용(더 크다): TLB 플러시(새 프로세스의 주소 변환 캐시가 없어 Page Table 조회 필요), CPU 캐시 오염(L1/L2/L3 캐시에 이전 프로세스 데이터 → Miss율 증가), Branch Predictor 무효화, 파이프라인 플러시 등 (~수십 μs).
프로세스 Context Switch: 메모리 주소 공간이 다르므로 페이지 테이블 교체와 TLB 전체 플러시가 필요하다. 캐시 오염도 심하다.
스레드 Context Switch(같은 프로세스 내): 메모리 주소 공간을 공유하므로 페이지 테이블 교체 불필요, TLB 플러시 불필요, 캐시 오염도 적다. 따라서 스레드 Context Switch가 프로세스보다 훨씬 빠르며, 이것이 멀티스레딩의 핵심 장점 중 하나이다.
Q7. Linux CFS는 어떻게 동작하나요?
CFS(Completely Fair Scheduler)는 Linux의 기본 스케줄러로, 모든 프로세스에게 공정하게 CPU 시간을 분배하는 것을 목표로 한다.
핵심 개념은 vruntime(virtual runtime)이다. 각 프로세스가 실제로 CPU를 사용한 시간에 nice 값(우선순위)에 따른 가중치를 곱한 값이다. CFS는 항상 vruntime이 가장 작은 프로세스(=CPU를 가장 적게 사용한 프로세스)를 선택하여 CPU를 할당한다.
자료구조로 Red-Black Tree를 사용하여 삽입/삭제/최솟값 조회를 모두 O(log n)에 처리한다. nice 값이 높은(낮은 우선순위) 프로세스는 vruntime이 빠르게 증가하여 적은 CPU를 받고, nice 값이 낮은(높은 우선순위) 프로세스는 vruntime이 천천히 증가하여 더 많은 CPU를 받는다.
CFS의 장점은 Starvation이 발생하지 않는다는 것이다. 모든 프로세스가 결국 CPU를 받으며, 받는 비율만 우선순위에 따라 달라진다. 2023년 Linux 6.6부터는 CFS를 개선한 EEVDF로 대체되고 있다.
Q8. CPU-bound와 I/O-bound 프로세스에 대해 설명하고, 스케줄링과의 관계를 설명하세요.
CPU-bound 프로세스: CPU 연산 시간이 긴 프로세스. 과학 계산, 영상 인코딩, 머신러닝 학습 등. CPU Burst가 길고 I/O Burst가 짧거나 없다.
I/O-bound 프로세스: I/O 대기 시간이 긴 프로세스. 웹 서버, DB 쿼리, 파일 처리 등. CPU Burst가 짧고 I/O Burst가 빈번하다.
스케줄링과의 관계: I/O-bound 프로세스에게 높은 우선순위를 주는 것이 전체 시스템 성능에 유리하다. I/O-bound가 짧은 CPU 사용 후 빨리 I/O를 시작하면, CPU와 I/O 장치가 동시에 활용되어 전체 처리량이 높아진다. 반면 CPU-bound가 CPU를 독점하면 I/O 장치가 유휴 상태가 된다.
MLFQ는 이를 자동으로 달성한다. I/O-bound는 Time Quantum 내에 CPU를 반납하므로 높은 큐에 유지되고, CPU-bound는 Time Quantum을 다 쓰므로 낮은 큐로 강등된다.
Q9. 스레드 풀의 크기를 어떻게 결정하나요? OS 스케줄링과 어떤 관계가 있나요?
CPU-bound 작업: 스레드 수 = CPU 코어 수 + 1. 코어 수보다 많으면 Context Switch만 증가하고 성능이 오히려 떨어진다. +1은 하나의 스레드가 페이지 폴트 등으로 잠시 중단될 때를 대비한다.
I/O-bound 작업: 스레드 수 = 코어 수 × (1 + W/S) (W=대기시간, S=서비스시간). I/O 대기 동안 CPU가 유휴 상태가 되므로, 대기시간이 길수록 더 많은 스레드가 필요하다. 예를 들어 DB 쿼리(W=50ms, S=5ms)이면 코어의 11배.
OS 스케줄링과의 관계: 스레드 수가 코어 수를 초과하면 OS 스케줄러가 Context Switch를 수행한다. CPU-bound에서 스레드를 과다 생성하면 유효 작업 없이 Context Switch 비용만 증가한다. Java 21의 가상 스레드는 수만 개의 동시 작업에서도 소수의 OS 스레드만 사용하여 Context Switch를 최소화한다.
Q10. 실시간(Real-Time) 스케줄링이란 무엇이며, 일반 스케줄링과 어떻게 다른가요?
실시간 스케줄링은 작업의 데드라인(Deadline)을 보장하는 것이 목표인 스케줄링이다.
Hard Real-Time: 데드라인을 절대로 놓쳐서는 안 된다. 자동차 에어백, 의료 장비, 항공 시스템. 데드라인 위반 = 시스템 실패.
Soft Real-Time: 데드라인을 가끔 놓쳐도 성능 저하만 발생. 멀티미디어 스트리밍, VoIP. 프레임 하나 놓치면 화면이 잠깐 끊기는 정도.
일반 스케줄링(CFS 등)은 공정성과 처리량을 목표로 하지만, 실시간 스케줄링은 예측 가능한 응답 시간을 목표로 한다. Linux에서는 실시간 프로세스(SCHED_FIFO, SCHED_RR)가 일반 프로세스(SCHED_OTHER)보다 항상 먼저 스케줄된다. 실시간 프로세스는 CFS의 vruntime 계산에서 제외되며, 고정 우선순위를 가진다.
마무리
CPU 스케줄링은 운영체제의 핵심이자, 시스템 성능을 좌우하는 근본적인 정책이다.
- FCFS는 단순하지만 Convoy Effect가 치명적이다.
- SJF/SRTF는 이론적 최적이지만 CPU Burst 예측이 불가능하다.
- Round Robin은 공정하지만 Time Quantum 선택이 성능을 좌우한다.
- Priority Scheduling은 유연하지만 Starvation이 발생한다.
- MLFQ는 위 알고리즘들의 장점을 결합하여 실제 OS의 기반이 된다.
- CFS/EEVDF는 Linux가 실제로 사용하는 공정한 스케줄러이다.
백엔드 개발자로서 스레드 풀 크기 결정, 가상 스레드 활용, @Async 설정 등에서 CPU 스케줄링 지식이 직접적으로 활용된다. 또한 Context Switch 비용을 이해해야 동시성 프로그래밍에서의 성능 최적화를 올바르게 할 수 있다.