선점형 CPU 스케줄링 완전 정리: 라운드 로빈, SRTF, 다단계

선점형 스케줄링의 개념

선점형(Preemptive) 스케줄링이란, 현재 CPU를 점유하고 있는 프로세스가 있더라도,
더 높은 우선순위의 프로세스나 조건을 만족하는 다른 프로세스가 도착하면 현재 프로세스를 중단하고 CPU를 강제로 회수하는 방식입니다.

이는 실시간성 향상과 응답 시간 단축을 위한 핵심 스케줄링 전략이며,
대부분의 현대 운영체제에서 채택하고 있습니다.

---

1. 라운드 로빈 (Round Robin, RR)

개념

• 각 프로세스는 동일한 시간 할당량(Time Quantum)을 부여받아 CPU를 사용합니다.
• 지정된 시간이 지나면 CPU를 강제로 반납하고 큐의 끝으로 이동합니다.
• FCFS + 선점형의 성격을 가지고 있으며, 인터랙티브 시스템에 적합합니다.

---

예시

타임 퀀텀: 2

프로세스	도착 시간	실행 시간
P1	0	5
P2	1	3
P3	2	8
P4	3	6

 

실행 순서 (시간 단위)

P1 → P2 → P3 → P1 → P4 → P2 → P3 → P4 → P3 → P4 → P3
0    2    4    6    8   10   11   13   15   17   18   20

---

각 프로세스별 대기 시간, 반환 시간

프로세스	시작 시간	종료 시간	대기 시간	반환 시간
P1	0	20	15	20
P2	1	11	6	10
P3	2	20	12	18
P4	3	19	6	16

• 평균 대기 시간 = 9.75
• 평균 반환 시간 = 15.25

---

장점

• 공정한 시간 분배
• 응답 시간이 빠르고, 인터랙티브 환경에 적합

단점

• 타임 퀀텀이 너무 작으면 오버헤드 증가
• 너무 크면 FCFS처럼 작동
• 짧은 작업이 오래 걸릴 수 있음

---

2. SRTF (Shortest Remaining Time First)

개념

• SJF(Shortest Job First)의 선점형 확장 버전
• 현재 실행 중인 프로세스보다 남은 실행 시간이 더 짧은 프로세스가 도착하면 CPU를 선점합니다.

---

예시

프로세스	도착 시간	실행 시간
P1	0	8
P2	1	4
P3	2	2
P4	3	1

 

실행 순서 (시간 단위)

P1 → P2 → P3 → P4 → P2 → P2 → P2 → P1 → P1 → P1 → P1
0    1    2    3    4    5    6    7    8    9   10   11

---

각 프로세스별 대기 시간, 반환 시간

프로세스	종료 시간	대기 시간	반환 시간
P1	15	7	15
P2	8	3	7
P3	4	0	2
P4	5	1	2

• 평균 대기 시간 = 2.75
• 평균 반환 시간 = 6.5

---

장점

• 평균 대기 시간이 매우 낮음
• 빠른 작업이 먼저 처리되어 응답성이 높음

단점

• 실행 시간을 정확히 예측해야 함
• 기아 상태 발생 가능성 있음
• 구현이 복잡함

---

3. 다단계 큐 (Multilevel Queue)

개념

• 프로세스들을 우선순위에 따라 여러 개의 큐로 나누고,
  각 큐는 서로 다른 스케줄링 방식을 가질 수 있습니다.
• 큐 간에도 우선순위가 정해져 있어, 높은 우선순위 큐가 항상 먼저 실행됩니다.

---

예시

프로세스	도착 시간	실행 시간	큐 유형
P1	0	5	시스템
P2	1	3	사용자
P3	2	2	시스템
P4	3	1	사용자

• 시스템 큐: 우선순위 1, RR 적용
• 사용자 큐: 우선순위 2, FCFS 적용

실행 순서

시스템 큐(P1 → P3) → 사용자 큐(P2 → P4)

---

각 프로세스별 대기 시간, 반환 시간

프로세스	종료 시간	대기 시간	반환 시간
P1	5	0	5
P3	7	3	5
P2	10	6	9
P4	11	7	8

 

 

• 평균 대기 시간 = 4.0
• 평균 반환 시간 = 8.0

 

---

장점

• 프로세스 유형별 유연한 처리 가능
• 시스템 구조와 서비스 품질(QoS)에 따라 구성 가능

단점

• 구현 복잡
• 낮은 우선순위 큐는 기아 상태 발생 가능성 있음

---

성능 비교 요약

알고리즘	평균 대기 시간	평균 반환 시간	응답 시간	구현 용이	기아 가능성
Round Robin	9.75	15.25	빠름	보통	낮음
SRTF	2.75	6.50	빠름	복잡	있음
Multilevel Queue	4.00	8.00	큐 기준	복잡	있음

 

---

면접 대비 자주 묻는 질문과 예시 답변

Q1. Round Robin에서 타임 퀀텀이 짧으면 어떤 문제가 생기나요?
A. 컨텍스트 스위칭 횟수가 증가하여 CPU 오버헤드가 커지고, 전체적인 처리 효율이 낮아질 수 있습니다.

Q2. SRTF는 왜 효율적인 알고리즘인가요?
A. 가장 짧은 작업을 먼저 처리하므로 전체 대기 시간과 반환 시간을 최소화할 수 있습니다.

Q3. Multilevel Queue에서 큐 간 우선순위가 고정되면 어떤 문제가 발생할 수 있나요?
A. 낮은 우선순위 큐의 프로세스가 오랜 시간 CPU를 배정받지 못해 **기아 상태(Starvation)**에 빠질 수 있습니다.

---

정리

선점형 스케줄링은 실시간 처리와 사용자 응답성을 높이기 위해, 실행 중인 프로세스를 중단시키고 CPU를 더 적합한 프로세스에 할당하는 구조입니다.

• Round Robin은 공정성과 응답성이 중요할 때 적합하며,
• SRTF는 이론상 평균 대기 시간이 가장 낮지만 구현이 어렵고,
• Multilevel Queue는 시스템에 맞춰 유연하게 설계할 수 있다는 장점이 있습니다.

운영체제 및 실시간 시스템을 설계할 때 각 알고리즘의 특성과 단점을 잘 고려해야 안정성과 성능을 모두 확보할 수 있습니다.