라운드 로빈 (Round Robin, RR) 스케줄링

핵심 인사이트 (3줄 요약)

  1. 본질: 라운드 로빈 (Round Robin)은 모든 프로세스에게 **동일한 크기의 시간 할당량 (Time Quantum, Time Slice)**을 부여하고, 이 시간이 소진되면 타이머 인터럽트를 통해 강제로 선점(Preempt)하여 Ready 큐의 맨 뒤로 쫓아내는 시분할 시스템의 근간 알고리즘이다.
  2. 가치: 특정 프로세스가 CPU를 장악하여 발생하는 기아 상태(Starvation)나 호위 효과(Convoy Effect)를 완벽히 원천 봉쇄하며, 수많은 사용자(또는 프로세스)에게 **일관되고 예측 가능한 빠른 응답 시간 (Response Time)**을 공평하게 제공한다.
  3. 융합: 타임 퀀텀의 크기가 RR의 모든 것을 결정한다. 퀀텀이 너무 크면 구시대의 FCFS(선착순)로 퇴화하여 응답성이 망가지고, 너무 작으면 잦은 문맥 교환(Context Switch) 오버헤드로 인해 시스템 처리량(Throughput)이 붕괴하는 극단적 트레이드오프를 갖는다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

  • 개념: 도착한 순서대로 프로세스를 처리하되(FCFS 기반), 각 프로세스가 CPU를 사용할 수 있는 최대 시간(Time Quantum, 보통 10~100ms)을 엄격하게 제한하는 선점형(Preemptive) 스케줄링의 대명사다.
  • 필요성: FCFS는 거대한 트럭 하나 때문에 뒤의 수많은 자가용들이 영문도 모른 채 1시간씩 정차해야 했다. 이를 해결하기 위한 SJF/SRTF는 미래를 알아야 한다는 불가능한 전제와 무거운 놈을 굶겨 죽이는 잔인함(기아 상태)을 동반했다. 누구 하나 죽이지 않고, 미래를 예측할 필요도 없이, 그저 "조금씩 평등하게 돌아가며 쓴다"는 무식하지만 완벽하게 공정한 룰이 필요해졌다.
  • 💡 비유: 놀이공원에서 한 아이가 회전목마를 10시간 내내 독점하지 못하게, **"한 사람당 딱 1번(3분)만 타고 내려서, 더 타고 싶으면 줄 맨 뒤로 다시 가!"**라고 통제하는 놀이기구 안전요원의 규칙과 똑같다.
  • 등장 배경: 과거 일괄 처리 시대가 저물고, 수십 명의 대학생이 하나의 메인프레임에 더미 터미널(모니터+키보드)로 접속해 코딩을 하는 **시분할 시스템 (Time-sharing System)**이 상용화되면서 탄생했다. 모든 학생이 "나 혼자 컴퓨터를 쓰고 있네?"라는 착각(환상)을 느끼게 하려면, 1초를 100조각으로 나누어 100명에게 번갈아 던져주는 RR 스케줄링이 필수불가결한 핵심 아키텍처였다.
  [라운드 로빈의 큐(Queue) 순환 동작 메커니즘]

  (타임 퀀텀 q = 10ms 부여)
  
       ┌───────────────── (선점되어 강제로 쫓겨남) ─────────────────┐
       │                                                            │
       ▼                                                            │
  [ Ready Queue (대기열) ]                                          │
  [ P4 ] [ P3 ] [ P2 ] ───── (디스패치) ─────▶ [ CPU (실행) ]       │
   맨 뒤        맨 앞                        [ P1 (10ms 꽉 채움) ] ─┘
                                                                    │
                                                 ▼ (10ms 도달 전 자발적 완료 시)
                                            [ 종료 및 탈출 ]

[다이어그램 해설] 라운드 로빈의 자료 구조는 기본적으로 끝과 시작이 이어진 원형 큐(Circular Queue)의 형태를 띤다. P1은 10ms를 꽉 채워 쓰면 하드웨어 타이머에 의해 목이 잘리고 큐의 맨 뒤(Tail)로 가서 다시 줄을 선다. 만약 P1이 원래 3ms짜리 짧은 가벼운 작업(I/O 바운드)이었다면 10ms를 다 채우기 전에 자발적으로 CPU를 놓고 I/O 큐로 탈출하므로, 다음 타자인 P2에게 퀀텀이 일찍 넘어가게 된다.

  • 📢 섹션 요약 비유: 피자 1판(CPU)을 1명이 다 먹을 때까지 기다리는 게 아니라, 피자를 8조각(타임 퀀텀)으로 잘라 8명에게 한 조각씩 입에 넣어주며 빙빙 도는 식탁입니다. 배가 부르면 스스로 나가고, 부족한 사람은 한 바퀴 돌 때까지 다시 입을 벌리고 기다립니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

RR의 성능을 증명하는 간트 차트 (Gantt Chart)

RR이 어떻게 응답 시간을 파격적으로 방어하는지 FCFS와 비교 시뮬레이션한다.

[시뮬레이션 조건] 도착 순서: P1(24ms) → P2(3ms) → P3(3ms) / RR의 타임 퀀텀 (q) = 4ms

  ┌──────────────────────────────────────────────────────────────────────┐
  │         [1] FCFS (선착순 비선점 - 호위 효과 발생)                    │
  ├──────────────────────────────────────────────────────────────────────┤
  │  0        (P1)                 24    (P2) 27  (P3)  30 ms            │
  │  │██████████████████████████████│█████│█████│                        │
  │  ▶ P2 첫 응답시간: 24 ms (마우스 클릭 후 24ms 뒤에 화면 뜸. 최악)    │
  │  ▶ 평균 응답시간: (0 + 24 + 27) / 3 = 17 ms                          │
  └──────────────────────────────────────────────────────────────────────┘

  ┌──────────────────────────────────────────────────────────────────────┐
  │         [2] Round Robin (타임 퀀텀 q = 4ms 강제 선점)                │
  ├──────────────────────────────────────────────────────────────────────┤
  │  0 P1(4) 4 P2(3) 7 P3(3) 10 P1(4) 14 P1(4) 18 P1(4) ...              │
  │  │█████│████│████│█████│█████│█████│█████│                           │
  │                                                                      │
  │  [시간별 추적]                                                       │
  │  - 0ms: P1 실행 시작.                                                │
  │  - 4ms: P1 퀀텀 소진. 커널이 뺏어서 P2에게 줌. (P1 남은 시간: 20)    │
  │  - 7ms: P2는 3ms만에 자기 일 다 끝내고 자발적 종료. P3에게 넘김.     │
  │  - 10ms: P3도 3ms만에 끝내고 종료. 이제 남은 건 P1뿐.                │
  │  - 10ms~: 이제 P1 혼자 4ms씩 끊어서 큐를 독점하며 연산 마침.         │
  │                                                                      │
  │  ✅ 응답 시간의 기적                                                 │
  │  ▶ P1 응답시간: 0 ms / P2 응답시간: 4 ms / P3 응답시간: 7 ms         │
  │  ▶ 평균 응답시간: (0 + 4 + 7) / 3 = 3.6 ms (약 5배 속도 향상!)       │
  └──────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 이 시뮬레이션이 시분할 시스템의 정수다. 24ms짜리 거대한 괴물(P1)이 앞을 가로막고 있었지만, 스케줄러가 4ms만 허락하고 목덜미를 채서 뒤로 던져버렸다. 덕분에 뒤에서 오들오들 떨고 있던 가벼운 I/O 바운드 프로세스(P2, P3)들은 단 4ms, 7ms 만에 CPU를 맛보고 유유히 작업을 마친 뒤 I/O를 하러 떠났다. 사용자 입장에서는 3개의 프로그램이 동시에 "즉각적으로" 반응하는 것처럼 완벽히 속게 된다.

대기 시간의 상한선 보장 (Deterministic Waiting)

RR 알고리즘의 가장 큰 학술적 특징은 **"어떤 최악의 상황에서도 내가 CPU를 잡기까지 기다려야 하는 최대 시간을 수식으로 개런티(보장)할 수 있다"**는 것이다.

  • 준비 큐에 프로세스가 N 개 있고, 타임 퀀텀이 q 라고 할 때,

  • 어떤 프로세스도 CPU를 뺏긴 후 다음 자기 차례가 돌아오기까지 최대 (N-1) * q 시간 이상을 기다리지 않는다.

  • 예: 큐에 프로세스 5개, q=10ms. 내가 맨 뒤로 쫓겨나도 내 앞에 4명만 10ms씩 쓰고 나면 40ms 뒤에는 무조건 내 순서가 돌아온다. (기아 상태 원천 차단)

  • 📢 섹션 요약 비유: 식당 번호표 100번을 뽑은 사람이 FCFS에서는 "언제 들어갈지 몰라요"라는 답을 듣지만, RR(퀀텀 1분제) 식당에서는 "내 앞에 99명이 1분씩만 먹고 쫓겨날 거니까, 최악의 경우라도 딱 99분 뒤엔 무조건 한 입 먹어볼 수 있습니다"라고 확정적(Deterministic)인 대답을 들을 수 있습니다.

Ⅲ. 융합 비교 및 다각도 분석 (Comparison & Synergy)

타임 퀀텀(Time Quantum, q) 크기가 부르는 치명적 나비효과

RR 설계의 전부이자 끝은 'q' 값을 몇 ms로 정할 것인가 하는 문제다. 이것이 튜닝의 모든 것이다.

타임 퀀텀 (q) 상태부작용 (Trade-off)비유 및 결과
q가 너무 클 때 (예: 무한대, 1초 이상)RR의 선점 효과 상실. 사실상 FCFS(선착순)로 퇴화함. 호위 효과 재발생.앞사람이 1시간 내내 독점. 마우스 클릭하면 1초 뒤에 움직이는 답답함 발생.
q가 중간일 때 (예: 10~100ms)황금 비율. (현대 OS의 기본 튜닝 값 범위)적절한 응답성 유지, 견딜 만한 문맥 교환 비용
q가 너무 작을 때 (예: 1ms 미만)잦은 교체로 문맥 교환 오버헤드 (디스패치 지연) 폭주. CPU가 연산은 안 하고 교체 작업만 하느라 캐시(TLB) 박살.1초에 1천 번씩 일어서라고 강요. 배식보다 자리 바꾸는 데 에너지를 다 써서 다 같이 굶어 죽음 (스래싱).

80% 룰 (Rule of Thumb)

전통적인 운영체제 설계 지침에 따르면, 타임 퀀텀은 시스템에 들어오는 CPU 버스트의 약 80%가 한 번의 퀀텀 안에 끝나도록(짧게 처리되도록) 충분히 커야 한다. 즉, I/O 바운드 같은 가벼운 프로세스들이 한 번 CPU를 잡았을 때 잘리지 않고 끝까지 치고 빠질 수 있도록 여유(예: 10ms)를 주어야 큐가 빨리 비워지고 시스템이 쾌적해진다.

  [퀀텀 크기에 따른 문맥 교환 오버헤드 시각화 (프로세스 100ms 요구)]
  
  (1) q = 100ms
  [██████████ 100ms 순수 연산 완료 ██████████]  ← 문맥 교환 0번 (최고의 처리량)
  
  (2) q = 50ms
  [████ 50ms ████](교체)[████ 50ms ████]      ← 문맥 교환 1번 (조금 손해)
  
  (3) q = 10ms (최악)
  [█10](교체)[█10](교체)[█10](교체)[█10](교체)... ← 문맥 교환 9번 발생!! 
   >> 배보다 배꼽(오버헤드)이 더 커져서 시스템 CPU 이용률 수직 낙하.
  • 📢 섹션 요약 비유: 시험 시간(q)을 3시간 주면 아이들이 딴짓(FCFS)을 하고, 1분씩 주고 뺏기를 반복하면 이름 쓰다가 시험이 끝납니다(문맥 교환 오버헤드). 쉬운 문제(80%의 짧은 버스트)를 넉넉히 풀 수 있는 10~20분짜리 단원 평가로 쪼개는 것이 선생님(커널)의 노하우입니다.

Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)

실무 시나리오

  1. 리눅스 O(1) 스케줄러의 타임 슬라이스 설계: 과거 리눅스 커널 2.6 초기의 O(1) 스케줄러는 철저한 우선순위 기반 라운드 로빈(RR)의 변형이었다. Active 배열과 Expired 배열을 나누어, 타임 슬라이스를 다 쓴 프로세스는 Expired 큐로 보내버림으로써 RR의 구조적 한계인 "N개의 큐를 순회하며 발생하는 검색 오버헤드"를 상수 시간 O(1)으로 해결한 엔지니어링의 극치였다.
  2. 리버스 프록시 (Nginx/HAProxy)의 부하 분산(Load Balancing) RR 알고리즘: 라운드 로빈 철학은 CPU를 넘어 네트워크 부하 분산의 업계 표준이 되었다. Nginx에서 여러 대의 백엔드 서버 그룹으로 트래픽을 분산시킬 때, 디폴트 전략이 바로 "1번 서버, 2번 서버, 3번 서버, 다시 1번 서버..."로 차례대로 던져주는 라운드 로빈이다. 가중치 라운드 로빈(Weighted RR)을 쓰면 성능이 두 배 좋은 서버에는 퀀텀(티켓)을 2개 줘서 2번 보낼 수도 있다.
  ┌──────────────────────────────────────────────────────────────────────┐
  │     Nginx 로드 밸런싱에서의 RR vs Weighted RR 아키텍처               │
  ├──────────────────────────────────────────────────────────────────────┤
  │                                                                      │
  │   [클라이언트 요청 트래픽] ────────────────▶ [ Nginx LB ]            │
  │                                             │                        │
  │   [ 1. 순수 라운드 로빈 (RR) ]               ▼ 분배                  │
  │   요청1 ─▶ 서버A (사양: 8코어)                                       │
  │   요청2 ─▶ 서버B (사양: 2코어) 🚨 B가 곧 뻗어버림                    │
  │   요청3 ─▶ 서버C (사양: 4코어)                                       │
  │   요청4 ─▶ 서버A ...                                                 │
  │                                                                      │
  │   [ 2. 가중치 기반 라운드 로빈 (Weighted RR) ]                       │
  │   (가중치 설정: A=4, B=1, C=2)                                       │
  │   요청 1~4 ─▶ 전부 서버 A로 몰아줌 (능력껏)                          │
  │   요청 5   ─▶ 서버 B (1개만 소화)                                    │
  │   요청 6~7 ─▶ 서버 C (2개 소화)                                      │
  │                                                                      │
  │   * 실무 판단: 이기종 클러스터에서는 단순 RR을 쓰면 절대 안 되며,    │
  │              반드시 인스턴스 사양에 비례하는 가중치 RR을 세팅해야 함.│
  └──────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] RR이 가장 욕을 먹는 지점은 "프로세스(또는 서버)의 능력과 무게를 전혀 고려하지 않고 공산당처럼 똑같은 시간(트래픽)을 배분한다"는 점이다. 무거운 서버와 가벼운 서버가 섞인 실무 인프라에서는 이 평등주의가 곧 시스템의 붕괴를 낳는다. 따라서 실무 아키텍처에서는 무조건 RR을 진화시킨 가중치 부여 RR (Weighted Round Robin)이나 동적 응답시간 기반의 Least Connection 라우팅으로 하이브리드 세팅을 해야 한다.

  • 📢 섹션 요약 비유: 유치원생 1명과 스모 선수 1명에게 똑같이 피자 1판씩을 할당(순수 RR)하면 유치원생은 배가 터지고 선수는 굶주립니다. 각자의 위장 크기(가중치)에 맞게 피자 조각 수를 차등 분배(Weighted RR)하는 것이 자본주의(실무)의 스케줄링입니다.

Ⅴ. 기대효과 및 결론 (Future & Standard)

기대효과

RR 스케줄러의 투입으로 무한 대기의 공포(기아 상태)가 종식되었으며, 모든 프로세스가 자신만의 1/N 속도로 구동되는 완벽한 시분할 대화형(Interactive) 컴퓨터 생태계가 개막했다. 마우스를 움직이고 백그라운드에 음악을 틀어둔 채 웹서핑을 하는 현대의 동시성(Concurrency) 경험은 전적으로 RR의 선점형 쪼개기 마법 덕분이다.

결론 및 미래 전망

순수한 기본형 라운드 로빈(RR)은 I/O 바운드와 CPU 바운드를 전혀 구별하지 않고 똑같은 퀀텀을 주는 단점(I/O 바운드가 손해를 보는 현상) 때문에, 현재 윈도우나 리눅스의 메인 스케줄러로 단독 사용되지는 않는다. 대신, 다단계 피드백 큐 (MLFQ) 아키텍처 내부에서 각각의 큐(하위 큐)를 굴리는 서브 알고리즘으로 흡수되어 현대 OS의 뼈대로 굳건히 자리 잡았다. 또한, 앞서 언급한 네트워크 로드 밸런서, DNS 라운드 로빈 등 '트래픽 분산 메커니즘'의 근간으로 그 사상이 영원히 계승되고 있다.

  • 📢 섹션 요약 비유: 라운드 로빈은 발명된 지 50년이 넘은 투박한 옛날 자전거(알고리즘)지만, 그 "바퀴를 쪼개서 골고루 돌린다"는 위대한 철학은 현대의 최고급 벤츠(리눅스 CFS, 네트워크 LB) 안에서도 여전히 핵심 엔진 피스톤으로 힘차게 돌아가고 있습니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭관계 및 시너지 설명
타임 퀀텀 (Time Quantum/Slice)라운드 로빈 스케줄링의 알파이자 오메가로, 이 값을 어떻게 튜닝하느냐에 따라 시스템의 오버헤드와 응답성이 널뛰기한다.
선점형 스케줄링 (Preemptive)타임 퀀텀이 다 된 프로세스를 강제로 큐의 맨 뒤로 쫓아내기 위해 RR이 절대적으로 의존하는 하드웨어 인터럽트 강제 뺏기 메커니즘이다.
문맥 교환 (Context Switch)타임 퀀텀을 너무 작게 쪼개어 RR을 무리하게 돌렸을 때 폭증하여 시스템 처리량을 박살 내버리는 숨겨진 징벌 비용이다.
다단계 피드백 큐 (MLFQ)순수 RR이 가벼운 작업과 무거운 작업을 똑같이 대우하는 부작용을 고치기 위해 큐를 여러 개 층으로 나눈 현대적 진화형이다.
기아 상태 (Starvation)SJF나 우선순위 알고리즘의 고질병인데, 라운드 로빈은 순환 큐 덕분에 이 병에 절대 걸리지 않는 무적의 내성을 갖는다.

👶 어린이를 위한 3줄 비유 설명

  1. 1대의 닌텐도 스위치로 친구 5명이 싸우지 않고 노는 최고의 방법은? 알람시계를 딱 10분 맞춰놓고 10분 땡 치면 무조건 다음 친구에게 패드를 넘기는 거예요.
  2. 이게 바로 컴퓨터의 라운드 로빈(RR) 스케줄링이랍니다. 내 차례가 금방금방 돌아오니까 지루하게 기다릴 필요가 없죠!
  3. 하지만 알람을 1초로 맞춰놓고 바꾸라고 하면? 게임은 하나도 못 하고 패드 주고받는 데 힘을 다 써서(문맥 교환 오버헤드) 아무도 못 놀게 되니까 시간(퀀텀)을 적당히 길게 정하는 게 가장 중요해요!