시스매

라운드 로빈

5 min read

2025-09-25 22:48

Tags: 알고리즘

라운드 로빈 (round robin)

  • 모든 참가자가 서로 한 번씩 만나는 대진 방식으로, 공정성을 보장하는 가장 기본적인 리그전 형식이다.
    • 이름의 유래는 ‘순회 편지(round robin)‘에서 시작
      • 17세기 프랑스에서는 청원서에 서명한 사람들의 순서 때문에 주동자가 색출되어 처벌받는 일이 잦았음.
      • 이를 피하고자 청원서 중앙의 원을 중심으로 서명을 방사형으로 돌려가며 적어 누가 먼저 서명했는지 알 수 없게 함
      • 여기서 ‘robin’은 리본(ribbon)의 변형된 형태로, 서명을 리본처럼 둥글게 배치했다는 의미
    • 특정 대상이 독점하는 것을 막고, 모두에게 최소한의 기회를 보장하여 전체의 안정성과 효율성을 높이려는 철학
  • 운영체제 스케줄링에서는 각 프로세스에 동일한 시간 할당량(Time Quantum)을 부여하여 응답 시간을 단축하고 기아 상태를 방지

운영체제 CPU 프로세스 스케줄링 (Process Scheduling)

  • 여러 프로세스가 CPU를 공평하게 나누어 쓰도록 하는 스케줄링 알고리즘
  1. 준비 큐 (Ready Queue):
    • 실행을 기다리는 프로세스들이 선입선출] 방식의 큐에 줄을 섭니다.
  2. 시간 할당량 (Time Quantum or Time Slice):
    • 스케줄러는 큐의 가장 앞에 있는 프로세스에 CPU를 할당하고, 정해진 ‘시간 할당량’만큼 실행시킵니다.
    • 이 시간은 보통 10~100밀리초(ms)로 매우 짧습니다.
  3. 실행과 반납:
    • 만약 프로세스가 시간 할당량을 다 쓰기 전에 실행을 마치면, 스스로 CPU를 반납하고 큐에서 빠져나옵니다.
    • 시간 할당량을 모두 사용했지만 아직 실행이 끝나지 않았다면,
      • 프로세스는 강제로 CPU를 빼앗기고(선점형, Preemptive), 준비 큐의 맨 뒤로 가서 다음 차례를 기다립니다.
  4. 반복: 스케줄러는 다시 큐의 가장 앞에 있는 다음 프로세스에 CPU를 할당하며 이 과정을 반복합니다.
  • 시간 할당량이 너무 클 경우:
    • 거의 선입선출(FIFO) 방식처럼 작동
    • 하나의 프로세스가 CPU를 너무 오래 독점하여 다른 프로세스들의 대기 시간이 길어지고, 시스템의 응답성이 떨어집니다.
  • 시간 할당량이 너무 작을 경우:
    • 문맥 교환(Context Switching)이 너무 자주 발생합니다.
    • 현재 실행 중인 프로세스의 상태를 저장하고 다음 프로세스의 상태를 불러오는 작업으로, 상당한 오버헤드(추가 비용)를 유발.
    • 너무 잦은 문맥 교환은 CPU가 실질적인 작업보다 프로세스 전환에 더 많은 시간을 쓰게 만들어 시스템 전체의 효율성을 떨어뜨립니다.
  • 따라서 최적의 시간 할당량을 설정하는 것이 중요하며,
    • 일반적으로 프로세스가 한 번의 CPU 버스트(CPU를 집중적으로 사용하는 시간)를 마칠 수 있는 길이의 80% 정도로 설정하는 것이 이상적

그래프 뷰

백링크