라운드 로빈

라운드 로빈(RR;Round Robin) 또는 라운드 로빈 스케줄링(Round Robin Scheduling)은 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간 단위로 CPU를 할당하는 방식의 CPU 스케줄링 알고리즘이다.

개요

FCFS에서 짧은 프로세스가 피해 보는 현상을 완화하는 가장 간단한 방법으로 시간을 측정하고 있다가 어떤 긴 프로세스가 일정 시간 이상을 넘어가는 순간 실행을 강제로 선점시키는 것이다. 이 방법은 긴 프로세스나 입출력 프로세스에 상당히 불리하게 작용한다. 보통 시간 단위는 10ms~100ms 정도인데 시간 단위 동안 수행한 프로세스는 준비 큐의 끝으로 밀려나게 된다. Context Switching의 오버헤드가 크지만, 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리하다.

특징

• 시분할 방식의 시스템에서 효과적이다.
• 할당 시간의 크기는 시스템의 효과적인 동작에 절대적인 영향을 미친다.
• 할당 시간이 크면 FCFS 방식과 같다.
• 할당 시간이 작으면 자주 문맥 교환이 발생하므로 오버헤드가 커진다.

동장 방식

선점형 알고리즘 중 가장 간단하다. 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행한다. 한 프로세스가 할당받은 시간(타임 슬라이스)동안 작업을 하다가 작업을 끝내지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다. RR은 FCFS와 유사하지만, 프로세스마다 CPU를 사용할 수 있는 최대시간이 있다. 프로세스는 자기에게 주어진 타임 슬라이스 동안만 작업할 수 있고, 작업이 다 끝나지 않으면 큐의 뒤에 삽입된다.

스케줄링 종류

가중 라운드 로빈 스케줄링

가중 라운드 로빈 스케줄링(WRR;Weighted Round-Robin Scheduling)은 실제 서버에 서로 다른 처리 용량을 지정할 수 있다. 각 서버에 가중치를 부여할 수 있으며, 여기서 지정한 정숫값을 통해 처리 용량을 정한다. 기본 가중치는 1이다. 가중치가 있는 라운드 로빈 스케줄링을 사용하면 실제 서버에서 네트워크 접속을 셀 필요가 없고 동적 스케줄링 알고리즘보다 스케줄링의 과부하가 작으므로 더 많은 실제 서버를 운영할 수 있다. 그러나 요청에 대한 부하가 매우 많을 경우 실제 서버 사이에 동적인 부하 불균형 상태가 생길 수 있다.

이기적인 라운드 로빈 스케줄링

이기적인 라운드 로빈 스케줄링(SRR;Selfish Round-Robin Scheduling)은 시간이 지남에 따라 프로세스의 우선순위를 높이는 에이징 기법을 사용한다. 즉, 기본적으로 라운드 로빈 스케줄링을 따르지만 오래 기다리는 프로세스의 경우 에이징기법을 통해서 우선순위를 점차 높여준다.

가상 라운드 로빈 스케줄링

가상 라운드 로빈 스케줄링(Virtual Round Robin Scheduling)은 일반 라운드 로빈을 발전시킨 형태이다. 새로 도착한 프로세스는 일단 준비 큐의 끝으로 진입한다. 준비 큐에 있는 프로세스들은 FCFS 방식으로 스케줄링 되고 실행 중이던 프로세스의 시간 할당량이 만료되면 다시 준비 큐로 들어가 대기한다. 프로세스가 입출력을 요구했다면 입출력이 완료될 때까지 입출력 큐로 들어가 대기한다. 여기까지가 일반적인 라운드 로빈이라면 가상 라운드 로빈 이후는 이 이후에 다르게 작동된다. 기존 라운드 로빈은 입출력이 끝나면 준비 큐 끝으로 들어가지만 완료된 프로세스는 보조 큐라고 하는 별도의 FSCF 큐로 진입한다. 이후 다음번 프로세스를 고르는 시점에서 스케줄러는 이 보조 큐에서 대기 중인 프로세스를 준비 큐보다 먼저 실행시키고 실행 시 칸을 저번 실행 때 못 채우고 반납한 시간 만큼만 실행하게 하여 처리기-중심 프로세스가 역차별을 당하지 않도록 한다.

데피싯 라운드 로빈 스케줄링

데피싯 라운드 로빈 스케줄링(Deficit Round Robin Scheduling)은 가중 라운드 로빈에서의 패킷 수와 달리 패킷 길이를 고려해서 서비스를 받도록 고안된 스케줄링 방법이다. 각 큐(Queue)는 데피싯 계수라는 변수를 가지고 있으며, 이 값은 처음에 0으로 초기화된다. 각 큐는 데피싯 계수에 양자(Quantum) 크기가 더해진 후 데피싯 만큼 라운드 로빈 형태로 서비스를 받는다. 따라서 패킷 크기가 작다면, 여러 패킷이 한 번 라운드에 서비스될 수도 있고, 패킷 길이가 길면 여러 라운드를 거쳐 한 패킷이 서비스될 수도 있다. 서비스가되면 데피싯 계수는 패킷 크기만큼 빠진 후 저장된다.

참고자료

• SiriusJ, 〈Round-Robin(RR)이란?, CPU-Scheduling들〉, 《티스토리》, 2016-04-18
• sunday5214, 〈운영체제 정리7.단일처리기 스케줄링〉, 《티스토리》, 2018-12-04
• hojak99, 〈(운영체제)Round Robin Scheduling(라운드 로빈 스케줄링)〉, 《티스토리》, 2017-09-11
• 〈가상 서버 스케줄링 알고리즘〉, 《이글루스》
• sizin, 〈알고리즘의 종류〉, 《티스토리》, 2015-10-18
• 코쾅이, 〈(운영체제)스케줄링 알고리즘〉, 《네이버 블로그》, 2019-08-04
• 재리, 〈CPU 스케줄링〉, 《네이버 블로그》, 2019-03-19
• 지니넷, 〈DRR (Deficit Round Robin)〉, 《티스토리》, 2009-11-16