위키원
라운드 로빈
라운드 로빈(RR;Round Robin) 또는 라운드 로빈 스케줄링(Round Robin Scheduling)은 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위로 CPU를 할당하는 방식의 CPU 스케줄링 알고리즘이다.
개요
FCFS에서 짧은 프로세스가 피해보는 현상을 완화하는 가장 간단한 방법으로 시간을 측정하고 있다가 어떤 긴 프로세스가 일정 시간 이상을 넘어가는 순간 실행을 강제로 선점시키는 것이다. 이 방법은 긴 프로세스나 입출력 프로세스에 상당히 불리하게 작용한다.[1] 보통 시간 단위는 10ms~100ms 정도인데 시간 단위 동안 수행한 프로세스는 준비 큐의 끝으로 밀려나게 된다. Context Switching의 오버헤드가 큰 반면, 응답시간이 잛아지는 장점이 있어 실시간 시스템에 유리하다.[2]
특징
- 시분할 방식의 시스템에서 효과적이다.
- 할당 시간의 크기는 시스템의 효과적인 동작에 절대적인 영향을 미친다.
- 할당 시간이 크면 FCFS 방식과 같다.
- 할당 시간이 작으면 자주 문맥교환이 바생하므로 오버헤드가 커진다.
동장 방식
선점형 알고리즘 중 가장 간단하다. 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행한다. 한 프로세스가 할당 받은 시간(타임 슬라이스)동안 작업을 하다가 작업을 끝내지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다. RR은 FCFS와 유사하지만, 각 프로세스마다 CPU를 사용할 수 있는 최대시간이 있다. 프로세스는 자기에게 주어진 타임 슬라이스 동안만 작업할 수 있고, 작업이 다 끝나지 않으면 큐의 뒤에 삽입된다.[3]
종류
- 가중치기반 라운드 로빈
가중치기반 라운드 로빈(WRR;Weighted Round-Robin)은 실제 서버에 서로 다른 처리 용량을 지정할 수 있다. 각 서버에 가중치를 부여할 수 있으며, 여기서 지정한 정수값을 통해 처리 용량을 정한다. 기본 가중치는 1이다. 가중치가 있는 라운드 로빈 스케줄링을 사용하면 실제 서버에서 네트워크 접속을 셀 필요가 없고 동적 스케줄링 알고리즘보다 스케줄링의 과부하가 적으므로 더 많은 실제 서버를 운영할 수 있다. 그러나 요청에 대한 부하가 매우 많을 경우 실제 서버사이에 동적인 부하 불균형 상태가 생길수 있다.[4]
- 이기적인 라운드 로빈 스케줄링
이기적인 라운드 로빈 스케줄링(SRR;Selfish Round-Robin Scheduling)은 시간이 지남에 따라 프로세스의 우선순위를 높이는 에이징 기법을 사용한다. 즉, 기본적으로 라운드 로빈스케줄링을 따르지만 오래 기다리는 프로세스의 경우 에이징기법을 통해서 우선순위를 점차 높여준다.
- 가상 라운드 로빈
가상 라운드 로빈(Virtual Round Robin)은 일반 라운드 로빈을 발전 시킨 형태이다. 새로 도착한 프로세스는 일단 준비 큐의 끝으로 진입한다. 준비 큐에 있는 프로세스들은 FCFS 방식으로 스케줄링되고 실행중이던 프로세스의 시간 할당량이 만료되면 다시 준비큐로 들어가 대기한다. 프로세스가 입출력을 요구 했다면 입출력이 완료될 때까지 입출력 큐로 들어가 대기한다. 여기까지가 ㅣㅇㄹ반적인 라운드 로빈이라면 가상 라운드 로빈 이후는 이 이후에 다르게 작동된다. 기존 라운드 로비은 입출력이 끝나면 준비 큐 끝으로 들억자미ㅏㄴ 완료된 프로세스는 보조 큐라고 하는 별도의 FSCF 큐로 진입한다. 이후 다음번 프로세스를 고르는 시점에서 스케줄러는 이 보조 큐에서 대기 중인 프로세스를 준비 큐보다 먼저 실행시키고 실행 시칸을 저번 실행 때 못 채우고 반납한 시간 만큼만 실행하게하여 처리기-중심 프로세스가 역차별을 당하지 않도록 한다.
각주
- ↑ sunday5214, 〈운영체제 정리7.단일처리기 스케줄링〉, 《티스토리》, 2018-12-04
- ↑ hojak99, 〈(운영체제)Round Robin Scheduling(라운드 로빈 스케줄링)〉, 《티스토리》, 2017-09-11
- ↑ 재리, 〈CPU 스케줄링〉, 《네이버 블로그》, 2019-03-19
- ↑ 〈가상 서버 스케줄링 알고리즘〉, 《이글루스》
참고자료
- 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
