beautifulsoups.dev
Published on

운영체제 스케줄링 알고리즘 라운드 로빈으로 이해하는 CPU 시간 나누기

Authors

서버에서 여러 요청이 동시에 들어오거나, 데스크톱에서 브라우저 탭을 수십 개 띄워도 시스템이 “그럭저럭” 반응하는 이유는 운영체제가 CPU를 공정하게 나눠 쓰도록 스케줄링하기 때문입니다. 그런데 공정함만으로는 충분하지 않습니다. 너무 자주 바꿔치기하면 문맥 교환(context switch) 비용으로 성능이 떨어지고, 너무 오래 쥐고 있으면 특정 작업이 굼떠 보입니다.

이 균형점을 가장 직관적으로 보여주는 알고리즘이 라운드 로빈(Round Robin, RR) 입니다. “모두에게 같은 시간만큼”이라는 단순한 규칙이지만, 타임 퀀텀 설정에 따라 체감 성능이 크게 달라지고, I/O 중심 작업과 CPU 중심 작업이 섞일 때의 결과도 달라집니다.

아래에서는 라운드 로빈의 동작 원리부터, 직접 시뮬레이션 코드, 흔한 함정과 튜닝 포인트까지 개발자 관점에서 깊게 정리합니다.

라운드 로빈이 해결하려는 문제

FCFS(선입선출)의 한계: 콘보이 효과

FCFS(First-Come First-Served)는 먼저 온 프로세스가 끝날 때까지 CPU를 사용합니다. 구현은 쉽지만, 긴 작업 하나가 앞에 서면 뒤의 짧은 작업들이 줄줄이 대기하는 콘보이 효과(convoy effect) 가 발생합니다. 사용자 입장에서는 “시스템이 멈춘 것 같은” 느낌을 주죠.

RR의 목표: 반응성(Responsiveness)

라운드 로빈은 프로세스가 CPU를 짧게 사용하고, 시간이 끝나면 강제로 다음 프로세스로 넘어갑니다(선점형). 이 방식은 특히 다음 상황에 유리합니다.

  • 대화형(Interactive) 작업: UI, 셸, 웹 요청 처리 등
  • 다수의 짧은 작업이 섞인 환경
  • “공정성”이 중요한 멀티태스킹

핵심 개념 3가지

1) 타임 퀀텀(Time Quantum, Time Slice)

각 프로세스가 한 번에 CPU를 사용할 수 있는 최대 시간입니다.

  • 프로세스가 퀀텀 안에 끝나면: 완료 후 큐에서 제거
  • 퀀텀을 다 쓰면: 남은 작업을 들고 준비 큐(Ready Queue) 뒤로 이동

2) 준비 큐(Ready Queue)

CPU를 받을 준비가 된 프로세스들이 줄 서 있는 큐입니다. 라운드 로빈은 보통 FIFO 큐로 구현합니다.

3) 문맥 교환(Context Switch)

프로세스를 바꿀 때 레지스터, 프로그램 카운터, 스택 포인터 등 실행 상태를 저장/복원하는 비용입니다.

  • 퀀텀이 너무 작으면 문맥 교환이 과도해져 오히려 느려짐
  • 퀀텀이 너무 크면 FCFS와 비슷해져 반응성이 떨어짐

라운드 로빈 동작 방식 한 번에 이해하기

예시로 프로세스 3개가 있고, CPU 버스트(실행 시간)가 다음과 같다고 해봅시다.

  • P1: 8ms
  • P2: 5ms
  • P3: 2ms
  • 타임 퀀텀 q = 2ms

스케줄링 흐름은 다음처럼 됩니다.

  1. P1 2ms 실행 (잔여 6ms) → 큐 뒤로
  2. P2 2ms 실행 (잔여 3ms) → 큐 뒤로
  3. P3 2ms 실행 (잔여 0ms) → 종료
  4. P1 2ms 실행 (잔여 4ms) → 큐 뒤로
  5. P2 2ms 실행 (잔여 1ms) → 큐 뒤로
  6. P1 2ms 실행 (잔여 2ms) → 큐 뒤로
  7. P2 1ms 실행 (잔여 0ms) → 종료
  8. P1 2ms 실행 (잔여 0ms) → 종료

이렇게 하면 긴 작업(P1)이 CPU를 독점하지 못하고, 짧은 작업(P3)은 빠르게 끝나서 사용자 체감이 좋아집니다.

코드로 보는 라운드 로빈 시뮬레이션

말로만 보면 감이 오지만, 직접 숫자를 돌려보면 타임 퀀텀의 영향이 더 선명합니다. 아래는 파이썬으로 만든 간단한 RR 시뮬레이터입니다.

from collections import deque

def round_robin(processes, quantum):
    """processes: [(name, burst_time), ...]"""
    q = deque([(name, burst, 0) for name, burst in processes])  # (name, remaining, executed)
    t = 0
    timeline = []

    while q:
        name, remaining, executed = q.popleft()
        run = min(quantum, remaining)
        timeline.append((t, t + run, name))
        t += run
        remaining -= run
        executed += run

        if remaining > 0:
            q.append((name, remaining, executed))

    return timeline


def print_timeline(timeline):
    for start, end, name in timeline:
        print(f"{start:>3}~{end:<3} : {name}")


processes = [("P1", 8), ("P2", 5), ("P3", 2)]
for quantum in [1, 2, 4]:
    print(f"\n== quantum={quantum} ==")
    tl = round_robin(processes, quantum)
    print_timeline(tl)

이 코드는 평균 대기 시간/턴어라운드 타임까지는 계산하지 않지만, 퀀텀이 작을수록 프로세스가 더 자주 섞여 실행된다는 점을 직관적으로 보여줍니다.

원한다면 다음을 확장해보세요.

  • 각 프로세스의 완료 시점(Completion time)
  • Turnaround time = 완료 시점 - 도착 시점
  • Waiting time = turnaround - burst
  • 응답 시간(Response time) = 첫 실행 시작 시점 - 도착 시점

라운드 로빈은 특히 응답 시간을 낮추는 데 강점이 있습니다.

타임 퀀텀은 어떻게 정해야 할까

타임 퀀텀은 라운드 로빈의 성능을 좌우하는 핵심 파라미터입니다.

퀀텀이 너무 작을 때

  • 장점: 반응성 극대화(자주 CPU를 돌려줌)
  • 단점: 문맥 교환 오버헤드 증가 → 실제 유효 CPU 시간 감소
  • 증상(트러블슈팅 관점)
    • CPU 사용률은 높은데 처리량(throughput)이 기대보다 낮음
    • 프로파일링 시 스케줄러/커널 오버헤드 비중이 커짐

퀀텀이 너무 클 때

  • 장점: 문맥 교환 감소 → 처리량 증가 가능
  • 단점: 긴 작업이 오래 점유 → 대화형 작업이 굼떠짐
  • 증상
    • UI/요청 응답이 “간헐적으로” 뚝뚝 끊김
    • 짧은 작업이 뒤에서 오래 기다림

실전 감각: “문맥 교환 비용보다 충분히 큰” 퀀텀

일반적으로 퀀텀은 문맥 교환 비용(수 µs~수십 µs 수준)보다 훨씬 크게 잡습니다. 다만 현대 OS는 순수 RR만 쓰기보다는, 우선순위/가중치 기반 스케줄링과 섞어 쓰는 경우가 많습니다.

  • 대화형 중심: 퀀텀을 상대적으로 작게(응답성)
  • 배치/연산 중심: 퀀텀을 크게(처리량)

RR이 항상 정답은 아닌 이유

CPU-bound vs I/O-bound 혼합

  • I/O-bound 프로세스는 CPU를 조금 쓰고 곧바로 I/O 대기 상태로 빠집니다.
  • RR에서는 이런 프로세스가 자주 “짧게” 실행되고 잘 빠져나가서 체감이 좋습니다.
  • 반면 CPU-bound 프로세스는 매번 퀀텀을 꽉 채우고 뒤로 밀려, 완료까지 라운드가 많이 필요합니다.

즉, RR은 대화형/I-O 작업에 유리하지만, CPU-bound 작업이 많으면 평균 완료 시간이 늘어날 수 있습니다.

우선순위가 필요한 상황

  • 실시간(Real-time) 작업
  • 지연에 민감한 오디오 처리
  • 특정 중요 작업(예: 시스템 데몬)

이런 경우는 단순 공정성보다 우선순위/데드라인이 중요해 RR만으로는 부족합니다.

트러블슈팅 포인트: “공정한데 느리다”가 나오는 순간

라운드 로빈을 적용했는데도 시스템이 느리게 느껴진다면, 다음을 점검해볼 수 있습니다.

1) 문맥 교환 폭증 여부 확인

  • 퀀텀이 너무 작거나
  • runnable 상태 프로세스가 과도하게 많거나
  • 락 경합/스레드 폭증으로 스케줄링 압력이 증가했을 수 있습니다.

개발/운영 환경에서는 이런 문제를 쿠버네티스에서 특히 자주 체감합니다. 예를 들어 CrashLoopBackOff로 컨테이너가 반복 재시작되면, 프로세스 생성/종료와 함께 스케줄링 부담도 커질 수 있습니다. 관련해서는 쿠버네티스 입문자가 겪는 CrashLoopBackOff 에러 원인 5가지와 해결법도 함께 참고하면 원인 파악에 도움이 됩니다.

2) 스레드 수가 과도한지 점검

애플리케이션 레벨에서 스레드를 무작정 늘리면 “CPU를 더 쓰겠지”가 아니라 “스케줄링 오버헤드를 더 쓰겠지”가 될 수 있습니다.

  • 워커 풀 크기 제한
  • 비동기 I/O 전환
  • 큐 기반 백프레셔(backpressure)

3) 관측 가능한 재현 코드(MCVE)로 문제를 좁히기

스케줄링 문제는 환경/부하/동시성에 따라 재현이 어려운 경우가 많습니다. 이럴수록 최소 재현 코드(MCVE)가 중요합니다. 팀 내 공유나 외부 질문을 할 때는 스택오버플로우 질문 잘하는 법 재현 가능한 코드 MCVE로 답변율 올리기의 체크리스트 방식이 유용합니다.

Best Practice: 라운드 로빈을 이해할 때 같이 챙길 것

1) “선점형”의 의미를 정확히 잡기

라운드 로빈은 타임 퀀텀 만료 시 강제로 CPU를 뺏습니다. 이는 동시성 버그(경쟁 조건, 락 경합)와도 연결됩니다. 선점이 일어날 수 있는 지점을 염두에 두면 멀티스레드 디버깅이 쉬워집니다.

2) 성능 지표를 분리해서 보자

  • 처리량(Throughput): 단위 시간당 완료 작업 수
  • 평균 대기 시간(Waiting time)
  • 응답 시간(Response time): 사용자 체감과 직결

RR은 응답 시간을 낮추는 데 강점이 있지만, 처리량이 최우선인 배치 작업에는 다른 선택이 더 나을 수 있습니다.

3) “큐” 관점으로 사고하기

RR은 결국 Ready Queue를 어떻게 돌리는가의 문제입니다. 큐의 길이가 길어질수록(프로세스/스레드가 많을수록) 각 작업이 다시 CPU를 받기까지의 간격이 늘어납니다. 그래서 애플리케이션 설계에서도 “불필요하게 runnable을 늘리지 않는 것”이 중요합니다.

결론: 라운드 로빈은 단순하지만 튜닝이 전부다

라운드 로빈 스케줄링은 모든 프로세스에 동일한 타임 퀀텀을 주고 CPU를 번갈아 배분하는, 가장 직관적인 선점형 스케줄링 방식입니다. 대화형 작업에서 뛰어난 반응성을 제공하지만, 퀀텀이 너무 작으면 문맥 교환 오버헤드로 느려지고, 너무 크면 FCFS처럼 굼떠집니다.

정리하면 다음 3가지를 기억하면 좋습니다.

  • RR의 핵심은 타임 퀀텀이며, 체감 성능을 좌우한다.
  • 문맥 교환 비용과 응답성 사이의 균형이 필요하다.
  • “공정함”이 항상 “최적”은 아니다. 워크로드 특성(CPU-bound/I-O-bound)에 맞춰 판단해야 한다.
Discuss on Twitter • View on GitHub