라운드 로빈(Round Robin, RR)은 각 프로세스에 '퀀텀(Quantum)'이라 불리는 고정된 시간 할당량을 부여하는 선점형 CPU 스케줄링 알고리즘입니다. 일반적으로 도착 시간이 모두 0인 경우를 가정하지만, 이 글에서 다루는 변형 방식은 프로세스가 서로 다른 시점에 도착하는 상황을 처리합니다. 이 경우 준비 큐(Ready Queue)가 동적으로 변하기 때문에 스케줄링이 훨씬 더 복잡해집니다.
선점형 스케줄링에서는 실행 중인 프로세스가 중단되어 다시 준비 큐로 돌아갈 수 있습니다. 라운드 로빈은 모든 프로세스에게 CPU 시간을 균등하게 분배함으로써 공정성을 보장하고, 기아(Starvation) 현상을 방지하면서 대화형 시스템에서 우수한 응답 시간을 유지합니다.
도착 시간이 다를 때 라운드 로빈의 동작 방식
프로세스들의 도착 시간이 서로 다를 경우, 알고리즘은 다음 단계에 따라 동작합니다.
- 프로세스는 자신의 도착 시간 순서대로 준비 큐에 진입합니다.
- CPU는 준비 큐의 맨 앞 프로세스를 퀀텀 시간만큼 실행합니다.
- 퀀텀 안에서 실행이 끝나면 해당 프로세스는 종료됩니다.
- 실행이 완료되지 않으면 준비 큐의 맨 뒤로 이동합니다.
- 새로 도착한 프로세스는 준비 큐에 합류하여 자신의 차례를 기다립니다.
- 문맥 교환(Context Switching)을 통해 선점된 프로세스의 상태가 저장됩니다.
주요 특징
- 기아 현상 방지: 모든 프로세스가 반드시 CPU 시간을 할당받습니다.
- 공정한 스케줄링: 모든 프로세스에게 동일한 퀀텀이 부여됩니다.
- 우수한 응답 시간: 대화형 및 실시간 시스템에 적합합니다.
- 문맥 교환 오버헤드: 퀀텀이 작을수록 문맥 교환 비용이 증가합니다.
예제 1: 퀀텀 = 2
도착 시간과 실행(Burst) 시간이 서로 다른 세 개의 프로세스를 살펴보겠습니다.
| 프로세스 | 도착 시간 | 실행 시간 |
|---|---|---|
| P1 | 0 | 4 |
| P2 | 1 | 3 |
| P3 | 2 | 7 |
간트 차트 — 라운드 로빈 (퀀텀 = 2)
| P1 (0~2) | P2 (2~4) | P3 (4~6) | P1 (6~8) | P2 (8~9) | P3 (9~14) |
단계별 실행 과정
| 시간 | 실행 프로세스 | 준비 큐 | 동작 내용 |
|---|---|---|---|
| 0~2 | P1 | P1 | P1이 2단위 실행, t=1에 P2 도착 |
| 2~4 | P2 | P2, P1 | P2가 2단위 실행, t=2에 P3 도착 |
| 4~6 | P3 | P3, P1 | P3가 2단위 실행 |
| 6~8 | P1 | P1, P2, P3 | P1이 남은 2단위를 실행하고 종료 |
| 8~9 | P2 | P2, P3 | P2가 남은 1단위를 실행하고 종료 |
| 9~14 | P3 | P3 | P3가 남은 5단위를 실행하고 종료 |
평균 시간 계산
| 프로세스 | 도착 | 실행 | 완료 | 반환 시간 | 대기 시간 |
|---|---|---|---|---|---|
| P1 | 0 | 4 | 8 | 8 | 4 |
| P2 | 1 | 3 | 9 | 8 | 5 |
| P3 | 2 | 7 | 14 | 12 | 5 |
평균 반환 시간(Turnaround Time) = (8 + 8 + 12) / 3 = 9.33
평균 대기 시간(Waiting Time) = (4 + 5 + 5) / 3 = 4.67
예제 2: 퀀텀 = 4
이번에는 더 큰 퀀텀 크기를 적용해 결과를 비교해 보겠습니다.
| 프로세스 | 도착 시간 | 실행 시간 |
|---|---|---|
| P1 | 2 | 8 |
| P2 | 0 | 7 |
| P3 | 1 | 9 |
간트 차트 — 라운드 로빈 (퀀텀 = 4)
| P2 (0~4) | P3 (4~8) | P1 (8~12) | P2 (12~15) | P3 (15~20) | P1 (20~24) |
| 프로세스 | 도착 | 실행 | 완료 | 반환 시간 | 대기 시간 |
|---|---|---|---|---|---|
| P1 | 2 | 8 | 24 | 22 | 14 |
| P2 | 0 | 7 | 15 | 15 | 8 |
| P3 | 1 | 9 | 20 | 19 | 10 |
평균 반환 시간(Turnaround Time) = (22 + 15 + 19) / 3 = 18.67
평균 대기 시간(Waiting Time) = (14 + 8 + 10) / 3 = 10.67
결론
도착 시간이 다른 환경에서의 라운드 로빈 스케줄링은 동적으로 유입되는 프로세스를 처리하면서도 공정한 CPU 자원 배분을 제공합니다. 특히 퀀텀 크기는 성능에 결정적인 영향을 미칩니다. 퀀텀이 작으면 응답 시간은 빨라지지만 문맥 교환 오버헤드가 커지고, 반대로 퀀텀이 크면 처리량(Throughput)은 향상되지만 공정성이 떨어질 수 있습니다. 따라서 시스템의 특성과 요구 사항에 맞는 적절한 퀀텀 크기를 선택하는 것이 중요합니다.
