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

  1. 본질: 라운드 로빈 (Round Robin, RR)은 Ready 큐의 프로세스에게 동일한 시간 할당량 (Time Quantum)을 순환 배분하고, 시간이 끝나면 타이머 인터럽트로 강제 선점하는 대표적인 시분할 스케줄링이다.
  2. 가치: 실행 시간을 미리 몰라도 모든 프로세스가 일정 주기 안에 CPU (Central Processing Unit)를 한 번씩 받게 만들어, 상호작용형 시스템의 응답성과 공정성을 동시에 확보한다.
  3. 판단 포인트: RR의 품질은 시간 할당량 크기에 크게 좌우되므로, 너무 크면 FCFS (First Come First Served)처럼 굼떠지고 너무 작으면 문맥 교환 (Context Switch) 비용이 폭증한다.

Ⅰ. 개요 및 필요성

라운드 로빈 스케줄링은 준비된 프로세스를 원형 큐처럼 순서대로 돌리되, 각 프로세스가 CPU를 연속 점유할 수 있는 최대 시간을 제한하는 선점형 정책이다. 프로세스가 할당받은 시간 안에 일을 끝내면 빠져나가고, 끝내지 못하면 큐의 뒤로 돌아가 다음 차례를 기다린다. 핵심은 "누구도 CPU를 오래 독점하지 못하게 한다"는 데 있다.

이 방식이 필요해진 배경은 일괄 처리 시스템이 아닌 시분할 (Time-sharing) 환경이다. 사용자 여러 명이 같은 시스템을 함께 쓰는 상황에서 FCFS는 긴 작업 하나가 앞에 서면 뒤의 짧은 입력 처리까지 모두 멈추게 만든다. 반대로 SJF (Shortest Job First)나 SRTF (Shortest Remaining Time First)는 짧은 작업에는 유리하지만, 실행 시간을 미리 알아야 하거나 긴 작업 기아 상태 (Starvation)를 유발할 수 있다. RR은 실행 시간을 몰라도 된다는 현실성과, 차례를 강제로 돌린다는 공정성을 결합한 해법이다.

아래 그림은 RR이 왜 "시분할의 기본형"으로 불리는지 보여 준다.

┌────────────────────────────────────────────────────────────────────┐
│ Round Robin as time-sharing                                       │
├────────────────────────────────────────────────────────────────────┤
│ Ready queue : P2 -> P3 -> P4                                      │
│                  ▲                                                │
│                  │ requeue if quantum expires                     │
│ CPU ---------> [ P1 runs for q ]                                  │
│                  │                                                │
│                  ├─ finishes / blocks -> leave the queue          │
│                  └─ still running -> move to tail                 │
└────────────────────────────────────────────────────────────────────┘

이 구조 덕분에 각 프로세스는 완전히 끝나지 않아도 "잠깐이라도" CPU를 경험한다. 사용자 체감에서는 여러 프로그램이 동시에 반응하는 것처럼 보이며, 운영체제는 이 환상을 타이머와 큐만으로 구현한다.

  • 📢 섹션 요약 비유: RR은 한 사람이 게임기를 끝날 때까지 붙잡게 두는 대신, 모두에게 5분씩 차례를 주고 시간이 다 되면 다음 친구에게 넘기게 하는 규칙과 같다. 모두가 금방 한 번씩은 만질 수 있다는 점이 핵심이다.

Ⅱ. 아키텍처 및 핵심 원리

RR의 동작은 단순하지만, 실제로는 타이머 인터럽트·Ready 큐·디스패처·문맥 교환이 맞물려야 성립한다. 스케줄러는 프로세스를 실행시킬 때 시간 할당량 q를 함께 설정하고, 타이머가 만료되면 현재 프로세스를 중단시켜 문맥을 저장한 뒤 다음 프로세스로 전환한다. 따라서 RR은 단순한 큐 정책이 아니라, 하드웨어 타이머가 보장하는 선점 메커니즘 위에서만 구현된다.

이벤트스케줄러 동작의미
프로세스 디스패치큐의 맨 앞 프로세스를 CPU에 배정차례 시작
시간 할당량 만료현재 문맥 저장 후 큐 뒤로 이동강제 선점
CPU 버스트 종료프로세스 종료 또는 다음 단계로 이동큐에서 제거
I/O (Input/Output) 대기 진입CPU를 스스로 반환짧은 작업이 빠르게 빠져나감
I/O 완료 후 Ready 복귀큐 뒤에 다시 삽입다음 순환에 참여

다음 예시는 q = 2 ms일 때 RR이 어떻게 모든 프로세스의 첫 응답을 빠르게 보장하는지 보여 준다.

┌────────────────────────────────────────────────────────────────────┐
│ Example timeline with q = 2 ms                                    │
├────────────────────────────────────────────────────────────────────┤
│ jobs : P1(5 ms), P2(3 ms), P3(1 ms) all arrive at t=0             │
│                                                                    │
│ time : 0    2    4    5    7    8    9                             │
│ CPU  : | P1 | P2 | P3 | P1 | P2 | P1 |                             │
│                                                                    │
│ first response time                                                │
│   P1 = 0 ms, P2 = 2 ms, P3 = 4 ms                                 │
│                                                                    │
│ rule : unfinished job returns to tail, finished job leaves        │
└────────────────────────────────────────────────────────────────────┘

이때 중요한 성질은 대기 상한선을 대략 계산할 수 있다는 점이다. 준비 큐에 n개 프로세스가 있고 모두 같은 우선순위라면, 한 프로세스가 선점된 뒤 다시 CPU를 얻기까지 기다리는 시간은 대체로 (n - 1) × q 범위 안에서 이해할 수 있다. 즉 RR은 평균 성능 최적화보다는, "언제쯤 다시 차례가 오는가"를 예측 가능하게 만든다는 장점이 크다.

  • 📢 섹션 요약 비유: RR은 회전문을 통과하는 규칙과 같다. 누구도 문을 붙잡고 오래 서 있을 수 없고, 한 바퀴 돌면 다시 차례가 오기 때문에 기다림이 무한정 늘어나지 않는다.

Ⅲ. 비교 및 연결

RR을 다른 스케줄링과 비교하면, 이 알고리즘이 최적화보다 공정성에 무게를 둔다는 점이 분명해진다. FCFS는 구조가 단순하지만 긴 작업이 전체를 막아 응답 시간이 악화되고, SJF/SRTF는 평균 대기 시간은 줄이지만 실행 시간 예측과 기아 상태 문제가 있다. RR은 이론적 최단 평균 대기 시간을 포기하는 대신, 누구나 빠르게 첫 응답을 받도록 설계된다.

정책선점 여부강한 목표장점약점
FCFS (First Come First Served)아니오단순성구현이 가장 쉽다긴 작업이 전체를 막는다
SJF (Shortest Job First)아니오평균 대기 시간 절감짧은 작업에 유리늦게 온 짧은 작업이 기다린다
SRTF (Shortest Remaining Time First)예평균 성능 최적화짧은 작업 응답 우수예측 필요, 기아 위험
RR (Round Robin)예공정한 시간 분할응답성, 기아 방지평균 반환 시간은 비효율 가능
MLFQ (Multilevel Feedback Queue)예응답성과 적응성 동시 확보RR보다 현실 친화적정책과 튜닝이 복잡

RR은 현대 운영체제에서 단독으로만 쓰이지는 않는다. 대신 다단계 피드백 큐 (Multilevel Feedback Queue, MLFQ) 내부에서 각 큐를 돌리는 기본 메커니즘으로 자주 쓰인다. 즉 "차례대로 짧게 나눠 준다"는 RR의 철학은 유지하되, 우선순위·I/O 성향·최근 CPU 사용량을 함께 고려하는 형태로 발전한 것이다.

또한 RR은 "작업 길이를 몰라도 되는 공정한 분배"라는 점에서 서버 스레드 스케줄링, 라운드 로빈 부하분산, 시분할 자원 배분 등 다른 분야로 철학이 확장된다. 다만 운영체제의 RR은 타이머 기반 선점과 문맥 교환을 전제로 하므로, 단순한 순번 배분과는 구별해서 이해해야 한다.

  • 📢 섹션 요약 비유: FCFS가 한 명씩 끝날 때까지 상담하는 창구라면, RR은 모두에게 3분씩 돌아가며 상담하는 창구다. 문제를 가장 빨리 끝내는 방식은 아닐 수 있어도, 누구도 "내 차례가 아예 안 온다"는 불안은 덜하다.

Ⅳ. 실무 적용 및 기술사 판단

실무에서 RR을 쓸지 판단할 때 가장 먼저 보는 것은 응답성 목표와 시간 할당량의 크기다. 터미널, GUI (Graphical User Interface), 웹 요청처럼 짧은 상호작용이 많다면 RR 계열 정책이 유리하다. 반면 긴 계산 작업만 몰려 있는 배치 환경에서는 지나친 선점이 캐시와 문맥 교환 비용만 늘릴 수 있어, 더 긴 슬라이스나 다른 정책이 더 적합하다.

시간 할당량은 RR의 핵심 조절점이다. 너무 크면 사실상 FCFS처럼 동작해 뒤 프로세스의 첫 응답이 늦어진다. 너무 작으면 매 퀀텀마다 문맥 저장·복원, 캐시 웜업, Translation Lookaside Buffer (TLB) 재사용 저하가 반복되어 CPU가 일보다 자리 교체에 바빠진다. 따라서 보통은 문맥 교환 시간보다 충분히 크고, 짧은 CPU 버스트 다수를 한 번에 처리할 만큼은 짧은 값을 찾는다.

아래 의사결정 흐름은 RR 계열 적용 여부를 빠르게 가르는 기준이다.

┌────────────────────────────────────────────────────────────────────┐
│ When RR is a good fit                                              │
├────────────────────────────────────────────────────────────────────┤
│ need predictable response for many interactive tasks?             │
│   ├─ yes -> choose RR or RR inside MLFQ                           │
│   │         ├─ context-switch cost high? -> enlarge quantum       │
│   │         └─ UI latency too high? -> shrink quantum carefully   │
│   └─ no                                                           │
│        ├─ strict deadline required? -> real-time scheduler        │
│        └─ throughput-only batch? -> longer slice / batch policy   │
└────────────────────────────────────────────────────────────────────┘

실무 판단 기준

  1. 응답 시간이 중요한가? 상호작용형 서비스라면 RR 계열이 기본 후보가 된다.
  2. 문맥 교환 비용이 감당 가능한가? 퀀텀이 너무 작으면 처리량이 오히려 감소한다.
  3. 긴 작업의 공정성 보장이 필요한가? RR은 기아를 줄이는 데 강하다.
  4. 하드 실시간 (Hard Real-Time)인가? RR은 deadline 보장용 기본 해법이 아니다.

안티패턴

  • RR이 항상 평균 대기 시간을 최소화한다고 오해하는 것

  • 퀀텀을 사용자 체감 지연만 보고 줄여 문맥 교환 폭증을 만드는 것

  • deadline 기반 문제를 RR 하나로 해결하려는 것

  • 📢 섹션 요약 비유: RR 운영은 회전 초밥집 접시 속도를 정하는 것과 같다. 너무 느리면 뒤 손님이 한참 기다리고, 너무 빠르면 먹기도 전에 접시만 계속 지나가서 오히려 정신없어진다.

Ⅴ. 기대효과 및 결론

RR의 가장 큰 효과는 공정한 응답 기회 보장이다. 긴 작업이 있더라도 다른 프로세스가 완전히 굶지는 않으며, 사용자는 여러 작업이 동시에 진행되는 듯한 체감을 얻는다. 그래서 RR은 시분할 운영체제의 역사에서 "현실적 선점 스케줄링의 출발점"으로 평가된다.

하지만 RR은 만능이 아니다. 평균 반환 시간만 놓고 보면 더 나은 알고리즘이 있을 수 있고, 시간 할당량이 잘못 잡히면 장점이 단점으로 바뀐다. 또한 우선순위, 멀티코어, 캐시 친화도, 에너지 관리까지 고려하는 현대 운영체제는 RR을 단순 원형 그대로 쓰기보다 더 정교한 정책 속에 흡수한다.

정리하면 RR은 CPU 시간을 잘게 나누어 모두에게 돌아가게 만드는 공정성 중심 스케줄링이다. 기억할 핵심은 분명하다. 작업 길이 예측 없이 응답성을 확보하는 데 강하지만, 품질은 결국 시간 할당량 설계에 달려 있다는 점이다.

  • 📢 섹션 요약 비유: RR은 달리기 시합에서 모두에게 일정 거리씩 바통을 건네며 뛰게 하는 계주와 같다. 최고 기록만 노리는 방식은 아닐 수 있지만, 팀원 모두가 경기에 참여하게 만든다.

📌 관련 개념 맵

개념연결 포인트
시간 할당량 (Time Quantum)RR의 공정성과 오버헤드를 함께 결정하는 핵심 파라미터다
선점형 스케줄링 (Preemptive Scheduling)타이머 만료 시 CPU를 강제로 회수해야 RR이 성립한다
문맥 교환 (Context Switch)퀀텀이 작을수록 더 자주 발생하는 직접 비용이다
응답 시간 (Response Time)RR이 특히 개선하려는 사용자 체감 성능 지표다
기아 상태 (Starvation)RR이 완화하는 대표적 문제다
다단계 피드백 큐 (Multilevel Feedback Queue, MLFQ)RR의 철학을 확장해 우선순위 적응성을 더한 구조다

📈 관련 키워드 및 발전 흐름도

batch-oriented scheduling
        │
        ▼
time-sharing requirement
        │
        ▼
timer interrupt + preemption
        │
        ▼
Round Robin scheduling
        │
        ├──────────────▶ response-time improvement
        ├──────────────▶ quantum tuning problem
        └──────────────▶ MLFQ / modern fair schedulers

이 흐름도는 RR이 단순한 고전 알고리즘이 아니라, 시분할 요구에서 출발해 현대 공정성 스케줄러의 토대가 된 과정을 보여 준다.

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

  1. 라운드 로빈은 친구들이 한 대의 컴퓨터를 쓸 때 5분씩 번갈아 가며 차례를 주는 규칙이에요.
  2. 그래서 오래 게임하는 친구가 있어도 다른 친구들이 아주 오랫동안 기다리지는 않아요.
  3. 하지만 차례를 너무 짧게 잘라 버리면 게임보다 자리 바꾸는 시간이 더 많아져서 오히려 재미가 없어져요.