CS학습2026년 9월 8일

Round Robin: 시분할 시스템을 지탱하는 선점형 스케줄링

Round Robin은 각 프로세스에 동일한 시간 할당량(time quantum)을 부여하고 순환 큐 방식으로 CPU를 배분하는 선점형 스케줄링 알고리즘이다. 시간 할당량이 만료되면 실행 중인 프로세스를 강제로 중단시키고 큐의 맨 뒤로 보내 다음 프로세스에 CPU를 넘긴다. 응답 시간의 공평성을 보장하지만 시간 할당량 설정에 따라 성능이 크게 달라진다.

송민성5분 읽기

1. 개념

Round Robin(RR)은 준비 큐(ready queue)에 있는 프로세스들에게 동일한 크기의 시간 할당량(time quantum, time slice)을 순서대로 부여하는 선점형(preemptive) CPU 스케줄링 알고리즘이다.

각 프로세스는 할당된 시간 동안만 CPU를 사용할 수 있고, 시간이 다 되면 실행 상태에서 강제로 밀려나(preempted) 큐의 맨 뒤로 재배치된다. 이 과정이 모든 프로세스가 종료될 때까지 반복된다.

2. 왜 사용하는가

FCFS(First Come First Served)는 앞선 프로세스의 실행 시간이 길면 뒤따르는 프로세스가 오래 기다리는 호위 효과(convoy effect)가 발생한다. SJF(Shortest Job First)는 평균 대기 시간은 최적화하지만 실행 시간이 긴 프로세스가 영원히 실행되지 못하는 기아 상태(starvation)를 유발할 수 있다.

Round Robin은 모든 프로세스에게 공평하게 CPU 시간을 나눠주기 때문에 응답 시간(response time)을 예측 가능한 범위로 제한할 수 있다. 특히 여러 사용자가 동시에 시스템을 사용하는 시분할 시스템(time-sharing system)에서 상호작용성(interactivity)을 보장하는 데 적합하다.

3. 동작 원리

모든 프로세스는 준비 큐(FIFO 구조)에 도착 순서대로 들어간다.
큐의 맨 앞 프로세스를 꺼내 CPU를 할당하고 타이머를 시간 할당량(quantum)만큼 설정한다.
프로세스가 quantum 이내에 종료되면 정상 종료 처리한다.
quantum이 끝나도 프로세스가 남아있으면 타이머 인터럽트가 발생해 프로세스를 선점하고, 남은 작업량을 유지한 채 큐의 맨 뒤로 다시 넣는다.
큐가 빌 때까지 2~4번을 반복한다.

quantum 크기가 스케줄링 성능을 결정하는 핵심 변수다.

quantum이 너무 크면 사실상 FCFS와 같아져 응답 시간이 길어진다.
quantum이 너무 작으면 문맥 교환(context switch) 오버헤드가 커져 CPU 효율이 떨어진다.

일반적으로 quantum은 문맥 교환 비용보다 충분히 커야 하며, 실무에서는 10ms~100ms 범위가 흔히 쓰인다.

4. 코드 예제

python

from collections import deque

class Process:
    def __init__(self, pid, arrival_time, burst_time):
        self.pid = pid
        self.arrival_time = arrival_time
        self.remaining_time = burst_time
        self.burst_time = burst_time
        self.completion_time = 0
        self.waiting_time = 0
        self.response_time = None  # 최초 실행 시각

def round_robin(processes, quantum):
    # 도착 시간 순으로 정렬
    processes.sort(key=lambda p: p.arrival_time)

    queue = deque()
    time = 0
    completed = []
    n = len(processes)
    idx = 0  # 아직 큐에 들어오지 않은 프로세스 인덱스
    timeline = []  # (pid, start, end) 기록용

    # 첫 프로세스 도착 시각으로 시간 초기화
    if processes:
        time = processes[0].arrival_time

    queue.append(processes[idx])
    idx += 1

    while queue:
        current = queue.popleft()

        # 최초 실행 시각 기록 (응답 시간 계산용)
        if current.response_time is None:
            current.response_time = time - current.arrival_time

        exec_time = min(quantum, current.remaining_time)
        start = time
        time += exec_time
        current.remaining_time -= exec_time
        timeline.append((current.pid, start, time))

        # 현재 시간까지 도착한 새 프로세스를 먼저 큐에 삽입
        while idx < n and processes[idx].arrival_time <= time:
            queue.append(processes[idx])
            idx += 1

        if current.remaining_time > 0:
            queue.append(current)  # 큐의 맨 뒤로 재삽입
        else:
            current.completion_time = time
            current.waiting_time = (
                current.completion_time - current.arrival_time - current.burst_time
            )
            completed.append(current)

        # 큐가 비었지만 아직 도착하지 않은 프로세스가 있는 경우 시간 점프
        if not queue and idx < n:
            time = processes[idx].arrival_time
            queue.append(processes[idx])
            idx += 1

    return completed, timeline


if __name__ == "__main__":
    procs = [
        Process(pid="P1", arrival_time=0, burst_time=10),
        Process(pid="P2", arrival_time=1, burst_time=4),
        Process(pid="P3", arrival_time=2, burst_time=6),
    ]

    result, timeline = round_robin(procs, quantum=3)

    print("실행 순서 (pid, 시작, 종료):")
    for pid, start, end in timeline:
        print(f"  {pid}: {start} ~ {end}")

    print("\n프로세스별 통계:")
    for p in sorted(result, key=lambda x: x.pid):
        print(
            f"  {p.pid} | 완료 시각: {p.completion_time} | "
            f"대기 시간: {p.waiting_time} | 응답 시간: {p.response_time}"
        )

    avg_wait = sum(p.waiting_time for p in result) / len(result)
    print(f"\n평균 대기 시간: {avg_wait:.2f}")

실행하면 quantum=3일 때 P1, P2, P3가 3ms 단위로 번갈아 실행되면서 대기 시간과 응답 시간이 출력된다.

5. 시간 복잡도 또는 성능 특성

각 프로세스를 큐에서 꺼내고 다시 넣는 연산은 O(1)이다 (deque 기반).
전체 스케줄링 과정은 프로세스 수를 n, 각 프로세스의 실행 시간 합을 T라 할 때 총 문맥 교환 횟수는 O(T / quantum)에 비례한다.
평균 대기 시간(average waiting time)은 quantum 크기와 프로세스들의 실행 시간 분포에 따라 달라지며, 일반적으로 SJF보다 크지만 FCFS보다는 작거나 비슷하다.
문맥 교환 오버헤드는 quantum이 작아질수록 선형적으로 증가한다. quantum이 무한대에 가까우면 FCFS와 동일한 성능을 보인다.

6. 실무 사용 사례

리눅스 커널의 CFS(Completely Fair Scheduler) 이전 버전인 O(1) 스케줄러는 Round Robin 개념을 기반으로 우선순위별 시간 할당량을 조정했다.
네트워크 장비의 패킷 큐잉에서 여러 트래픽 플로우에 대역폭을 공평하게 분배할 때 Weighted Round Robin 방식이 사용된다.
웹 서버 앞단의 로드 밸런서(load balancer)에서 여러 백엔드 서버에 요청을 순차적으로 분배하는 기본 알고리즘으로 Round Robin이 쓰인다. (예: Nginx의 기본 upstream 분배 방식)
멀티스레드 환경의 스레드 풀(thread pool) 스케줄링에서 공평한 실행 기회를 보장하기 위해 사용된다.

7. 주의할 점

quantum 값은 시스템 워크로드에 따라 실험적으로 튜닝해야 한다. 고정된 정답은 없다.
I/O 바운드 프로세스가 많은 환경에서는 Round Robin이 CPU 바운드 프로세스에 비해 상대적으로 불리하게 작동할 수 있어, 다단계 큐(Multilevel Queue)나 MLFQ(Multilevel Feedback Queue) 같은 변형이 실무에서 더 많이 쓰인다.
프로세스마다 실행 시간 편차가 크면 평균 대기 시간이 SJF보다 나빠질 수 있다.
문맥 교환 비용을 무시하고 quantum을 지나치게 작게 설정하면 실제 유효 CPU 시간이 오히려 줄어드는 역효과가 생긴다.

8. 핵심 정리

Round Robin은 시간 할당량 기반의 선점형 순환 스케줄링으로, 모든 프로세스에게 공평한 CPU 접근 기회를 보장해 응답 시간을 예측 가능하게 만든다. quantum 크기가 성능을 좌우하는 핵심 파라미터이며, 너무 크면 FCFS와 다를 바 없고 너무 작으면 문맥 교환 오버헤드가 지배적이 된다. 실무에서는 순수 Round Robin보다 우선순위와 결합한 MLFQ 형태로 확장되어 사용되는 경우가 많다.