라운드 로빈 스케줄링 (Round-Robin Scheduling)

핵심 개념

라운드 로빈(Round-Robin, RR)은 각 프로세스에게 **동일한 시간 단위(타임 퀀텀)**만큼 CPU를 순환 할당하는 선점형 스케줄링 알고리즘이다. 시분할 시스템에서 모든 프로세스에게 공정한 CPU 시간을 보장하고 응답성을 확보한다. 타임 퀀텀은 일반적으로 10~100ms이다.

비유하면, 피자를 여러 조각으로 나눠 여러 사람이 한 조각씩 돌아가며 먹는 것이다.

동작 원리

1. Ready Queue를 원형 FIFO 큐로 관리
2. 스케줄러가 큐의 첫 번째 프로세스를 선택, 타이머를 1 퀀텀으로 설정
3. 프로세스 실행:
   • CPU 버스트 < 퀀텀: 프로세스가 자발적으로 CPU 반납
   • CPU 버스트 ≥ 퀀텀: 타이머 인터럽트 → 문맥 교환 → 큐의 꼬리로 이동

응답 시간 보장

n개 프로세스, 퀀텀 q일 때 각 프로세스는 최대 (n-1) × q 시간 내에 다시 CPU를 받는다.

예: 5개 프로세스, 퀀텀 20ms → 각 프로세스는 최대 80ms마다 20ms씩 CPU 사용

타임 퀀텀 크기의 영향

퀀텀 크기	효과
너무 큼	FCFS와 동일해짐, 응답성 저하
너무 작음	문맥 교환 오버헤드 급증

• 규칙: 문맥 교환 시간의 약 10% 이하가 되도록 퀀텀 설정
• 권장: CPU 버스트의 80%가 퀀텀보다 짧도록 설정
• 현대 시스템: 퀀텀 10~100ms, 문맥 교환 약 10μs

예시

프로세스	Burst Time
P1	24ms
P2	3ms
P3	3ms

퀀텀 = 4ms:

P1   P2  P3  P1   P1   P1   P1   P1
├────┼───┼───┼────┼────┼────┼────┼────┤
0    4   7  10   14   18   22   26  30

대기 시간: P1=6, P2=4, P3=7
평균 대기 시간 = (6+4+7)/3 = 5.67ms

관련 개념

• CPU 스케줄링 (CPU Scheduling) - 스케줄링의 일반 개념
• FCFS 스케줄링 - 비선점형 기본 스케줄링
• 우선순위 스케줄링 - RR과 결합 가능한 스케줄링
• 컨텍스트 스위치 (Context Switch) - 퀀텀 만료 시 발생하는 전환