라운드 로빈 스케줄링 완전 정복: 시간 분할(Time Slice)과 간트 차트 예제

라운드 로빈(Round Robin) 스케줄링이란?

라운드 로빈(RR) 스케줄링은 운영체제에서 가장 널리 사용되는 선점형(preemptive) CPU 스케줄링 기법 중 하나입니다. 준비 큐(ready queue)에 도착한 순서대로 프로세스에게 CPU를 배분하되, 미리 정해진 시간 할당량(time quantum, time slice)만큼만 실행을 허용합니다.

할당된 시간 안에 작업이 끝나지 않으면 해당 프로세스는 강제로 CPU를 반납하고 큐의 맨 뒤로 이동하며, 다음 프로세스가 실행됩니다. 이러한 시간 분할(time sharing) 방식 덕분에 모든 프로세스가 공평하게 CPU를 사용할 수 있고, 시스템의 응답 시간도 짧아집니다.

예제 문제: 프로세스와 버스트 타임

네 개의 프로세스 A, B, C, D가 있으며, 각각의 CPU 버스트 타임(burst time)은 다음과 같습니다.

아래 간트 차트에서 각 실행 구간이 최대 2단위로 나뉘어 있는 것을 볼 수 있습니다. 따라서 이 예제의 유효 시간 할당량(time slice)은 2단위이며, 한 번의 차례에 프로세스는 최대 2단위까지만 실행됩니다.

간트 차트(Gantt Chart)

A   B   C   D   A   C   C   C
0   2   3   5   6   8   10  12  14

윗줄은 각 구간에서 실행되는 프로세스, 아랫줄은 시각(timestamp)을 나타냅니다.

단계별 실행 과정

1차 순회 (첫 번째 차례)

0 ~ 2 : A — A가 처음 2단위를 실행하고 남은 버스트는 2가 됩니다.
2 ~ 3 : B — B는 1단위 만에 실행을 마치고 종료됩니다(종료 시각 3).
3 ~ 5 : C — C가 처음 2단위를 실행하고 남은 버스트는 6이 됩니다.
5 ~ 6 : D — D 역시 1단위 만에 종료됩니다(종료 시각 6).

2차 순회 이후

6 ~ 8 : A — A가 남은 2단위를 실행해 완료됩니다(종료 시각 8).
8 ~ 10 : C — C가 2단위를 더 실행하고 남은 버스트는 4가 됩니다.
10 ~ 12 : C — 대기 중인 다른 프로세스가 없으므로 C가 연속으로 CPU를 사용합니다(남은 버스트 2).
12 ~ 14 : C — C가 마지막 2단위를 실행해 완료됩니다(종료 시각 14).

결과 분석

B와 D는 버스트 타임이 1단위로 짧아 첫 차례에 곧바로 끝나고, A는 두 번의 차례를 거쳐 시각 8에 실행을 마칩니다. C는 버스트 타임이 8단위로 가장 길어 총 네 번의 시간 조각, 즉 전체 8개 구간 중 4구간을 차지하며 시각 14에 종료됩니다.

반환 시간 = 종료 시각 − 도착 시각, 대기 시간 = 반환 시간 − 버스트 타임입니다. 모든 프로세스가 시각 0에 도착했다고 가정하면, 평균 반환 시간은 (8+3+14+6)/4 = 7.75, 평균 대기 시간은 (4+2+6+5)/4 = 4.25가 됩니다.

마무리

이 예제는 라운드 로빈 스케줄링에서 시간 분할이 실제로 어떻게 동작하는지 잘 보여줍니다. 짧은 버스트 타임을 가진 프로세스는 빠르게 완료되고, 긴 작업은 여러 차례에 걸쳐 CPU를 양보하면서 진행됩니다. 참고로 시간 할당량이 너무 크면 FCFS(선입선처리) 방식과 비슷해지고, 너무 작으면 문맥 교환(context switch) 오버헤드가 커지므로, 적절한 시간 할당량을 선택하는 것이 시스템 성능의 핵심입니다.