CPU 스케줄링 완전정리: FCFS · SJF · RR · SRTF · 우선순위 · MLQ · MLFQ
스케줄러는 “누가 다음에 CPU를 쓸지”를 결정합니다. 이 글은 작동 원리와 장단점, 별칭, 예시(간트 차트)까지 한 번에 정리합니다.
1) 왜 스케줄링이 필요한가
모든 프로세스는 CPU가 필요할 때 최대한 빨리 쓰고 싶어 합니다. 운영체제는 CPU라는 한정된 자원을 누가, 얼마나, 어떤 순서로 쓸지 결정해야 하죠. 특히 I/O-집중 프로세스와 CPU-집중 프로세스가 섞여 있을 때, I/O 장치를 놀리지 않으면서 CPU도 쉬지 않게 하는 균형이 중요합니다.
2) 핵심 개념(용어)
- CPU-집중(CPU-bound): 복잡한 연산/컴파일/그래픽 처리처럼 CPU 사용 시간이 긴 작업
- I/O-집중(I/O-bound): 비디오 재생·디스크 백업 등 입출력이 잦고 CPU 사용은 짧은 작업
- CPU 버스트: CPU를 실제로 사용한 시간 구간
- I/O 버스트: I/O 장치 완료를 기다리는 구간
- PCB(Process Control Block): 프로세스 제어 블록. 상태, 레지스터, 우선순위 등 스케줄링에 필요한 정보가 들어 있음
- 우선순위( Priority ): 중요도/긴급도. PCB에 기록되어 스케줄링 시 반영
3) 스케줄링 큐: 준비 큐와 대기 큐
- 준비 큐(Ready Queue): “CPU 쓰고 싶어요” 상태의 프로세스들이 줄 서는 곳
- 대기 큐(Wait/Blocked Queue): 특정 I/O 장치를 기다리는 프로세스들의 줄
I/O가 완료되면 인터럽트가 발생하고, OS는 해당 PCB를 찾아 대기→준비 상태로 옮겨 다시 CPU 경쟁에 참여시킵니다.
4) 선점형 vs 비선점형
- 선점형(Preemptive): 실행 중인 프로세스에게서 CPU를 빼앗아 다른 프로세스에 줄 수 있음
- 비선점형(Non-preemptive): 현재 실행 중인 프로세스가 스스로 양보하기 전까지는 끼어들지 못함
5) 평가지표
- 대기시간(Waiting Time) = Ready 큐에서 기다린 총 시간
- 턴어라운드(Turnaround Time) = 완료 시각 − 도착 시각
- 응답시간(Response Time) = 처음 CPU를 얻은 시각 − 도착 시각
- 처리량(Throughput) = 단위 시간당 완료된 작업 수
6) 알고리즘별 정리
6-1. 선입선처리 (FCFS, First-Come First-Served)
비선점 별칭: FIFO
- 방식: 먼저 도착한 순서대로 실행(큐: FIFO)
- 장점: 단순, 직관적, 공정(도착 순)
- 단점: 호위 효과(Convoy Effect) — 긴 작업 하나가 앞에 오면 뒤의 짧은 작업들이 오래 기다림 → 평균 대기시간↑
6-2. 최단작업우선 (SJF, Shortest Job First)
비선점 별칭: SPN(Shortest Process Next)
- 방식: 예상 실행시간이 가장 짧은 프로세스를 먼저 실행
- 장점: 평균 대기시간을 이론적으로 최소화
- 단점: CPU 버스트를 미리 예측해야 함, 긴 작업은 기아(Starvation) 가능
6-3. 라운드 로빈 (RR, Round Robin)
선점
- 방식: 고정된 시간 할당량(Time Quantum)만큼 실행 후 뒤로 보냄
- 장점: 응답성↑, 상호작용 시스템에 적합, 공정
- 단점: 퀀텀이 너무 크면 FCFS처럼 되고, 너무 작으면 문맥교환 오버헤드↑
6-4. 최소잔여시간우선 (SRTF, Shortest Remaining Time First)
선점 별칭: Preemptive SJF
- 방식: 남은 실행시간이 가장 짧은 프로세스를 항상 실행 (새로 더 짧은 작업이 오면 즉시 선점)
- 장점: 평균 대기/응답 시간 매우 우수
- 단점: 버스트 예측 필요, 긴 작업은 기아 위험
6-5. 우선순위 스케줄링 (Priority Scheduling)
선점/비선점 모두 가능
- 방식: 우선순위가 높은 프로세스부터 실행
- 장점: 중요/긴급 작업을 빠르게 처리
- 단점: 낮은 우선순위는 기아 위험 → Aging(대기 시간에 따라 우선순위 점진 상향)으로 완화
6-6. 다단계 큐 (MLQ, Multilevel Queue)
고정 등급 큐
- 방식: 프로세스를 성격별(시스템/인터랙티브/배치 등) 분리된 큐에 고정 배치. 각 큐는 자체 규칙(FCFS, RR 등) 보유
- 장점: 부류별 정책 최적화 쉬움
- 단점: 큐 간 이동이 없어 유연성 부족, 잘못된 분류 시 성능 저하
6-7. 다단계 피드백 큐 (MLFQ, Multilevel Feedback Queue)
동적 등급 큐 현실적 타협안
- 방식: 처음에는 높은 우선순위 큐(작은 퀀텀)에서 시작, CPU를 오래 쓰면 아래 등급 큐로 강등. I/O 중심/짧은 작업은 상위 큐에서 빨리 끝남.
- 장점: 다양한 작업 혼재 환경에서 응답성과 처리량을 균형 있게 확보
- 단점: 큐 개수·각 퀀텀·승급/강등 규칙 등 튜닝이 까다로움
7) 한눈에 보는 예시 & 간트 차트
예시 프로세스 — 도착/버스트/우선순위
P1: 도착 0, 버스트 8, 우선순위 2
P2: 도착 1, 버스트 4, 우선순위 1(높음)
P3: 도착 2, 버스트 2, 우선순위 3(낮음)
FCFS
| P1 | P2 | P3 | 0 8 12 14
SJF (비선점)
| P1 | P3 | P2 | 0 8 10 14
SRTF (선점 SJF)
| P1 | P2 | P3 | P2 | P1 | 0 1 2 4 7 14
RR (퀀텀=2)
| P1 | P2 | P3 | P1 | P2 | P1 | P1 | 0 2 4 6 8 10 12 14
우선순위 (선점)
| P1 | P2 | P1 | P3 | 0 1 5 12 14
지표 비교 (평균)
| 알고리즘 | 평균 대기시간 | 평균 턴어라운드 | 평균 응답시간 |
|---|---|---|---|
| FCFS | 5.67 | 10.33 | 5.67 |
| SJF(비선점) | 5.00 | 9.67 | 5.00 |
| SRTF | 2.67 | 7.33 | 0.00 |
| RR (q=2) | 4.33 | 9.00 | 1.00 |
| 우선순위(선점) | 4.67 | 9.33 | 3.33 |
※ 숫자는 위 예시 입력에 대한 계산 결과입니다(단위: 시간).
8) 자주 하는 질문(FAQ)
Q1. “모드 프로세스”가 맞나요?
“모든 프로세스”를 의미하신 것이라면 네, 모든 프로세스는 CPU가 필요할 때 최대한 빨리 쓰고 싶어 하며, 이를 조정하는 것이 스케줄링입니다.
Q2. SRTF는 RR과 SJF를 합친 건가요?
아니요. SRTF는 SJF의 선점형입니다. 남은 실행시간이 가장 짧은 작업이 항상 우선권을 갖습니다.
Q3. Priority에서 낮은 우선순위가 계속 굶어요…
Aging을 적용해 대기 시간이 길어질수록 우선순위를 자동 상향하면 완화됩니다. 실시간 시스템에서는 우선순위 상속도 고려합니다.
Q4. RR의 시간 할당량은 어떻게 정하나요?
문맥교환 비용보다 충분히 크고, 사용자 체감 지연이 커지지 않는 범위로 설정합니다. 상호작용이 중요하면 더 작게, 처리량이 중요하면 더 크게 잡습니다.
9) 실전 적용 팁
- I/O-집중이 많을 때: SRTF/MLFQ로 짧은 작업을 먼저 처리해 응답성을 확보
- 상호작용(데스크톱/서버 API): RR 또는 MLFQ (짧은 작업 우대 + 응답성 확보)
- 배치성·예측 가능: SJF(또는 비선점 Priority)로 평균 대기시간 최소화
- 기아 방지: Priority + Aging, MLFQ(주기적 승급)
- 정책 혼합: MLQ/MLFQ에서 큐별로 FCFS/RR/우선순위를 혼합해 튜닝
10) 요약 표 (별칭/방식/장단점)
| 알고리즘 | 다른 명칭 | 선점성 | 핵심 방식 | 장점 | 단점/주의 |
|---|---|---|---|---|---|
| 선입선처리 | FCFS, FIFO | 비선점 | 도착 순서대로 실행 | 단순, 공정 | 호위효과로 평균 대기시간↑ |
| 최단작업우선 | SJF, SPN | 비선점 | 예상 실행시간이 가장 짧은 작업 우선 | 평균 대기시간 최소화 | 버스트 예측 필요, 기아 위험 |
| 라운드 로빈 | RR | 선점 | 고정 퀀텀만큼 돌려가며 실행 | 응답성↑, 공정 | 퀀텀 선택 민감, 문맥교환 오버헤드 |
| 최소잔여시간우선 | SRTF, Preemptive SJF | 선점 | 남은 시간이 가장 짧은 작업 즉시 실행 | 평균 대기/응답 매우 우수 | 예측 필요, 긴 작업 기아 |
| 우선순위 | Priority | 둘 다 가능 | 우선순위 큰(또는 작은) 쪽을 먼저 | 중요/긴급 작업 빠른 처리 | 기아 위험 → Aging/상속으로 완화 |
| 다단계 큐 | MLQ | 큐별로 다름 | 부류별로 별도 고정 큐 | 부류 최적화 쉬움 | 큐 이동 없어 유연성↓ |
| 다단계 피드백 큐 | MLFQ | 선점 | CPU 사용 패턴에 따라 승급/강등 | 현실적 균형, 응답성/처리량 조화 | 튜닝 요소 많아 복잡 |
장기 스케줄러(잡 스케줄러): 어떤 프로세스를 메모리로 들일지 결정
중기 스케줄러: 메모리 압박 시 프로세스를 스왑아웃/인으로 조절
단기 스케줄러(CPU 스케줄러): 다음에 CPU를 누구에게 줄지 즉시 결정
© 작성자 — CPU 스케줄링 핵심만 쏙쏙 정리