[운영체제] RR(Round Robin) 스케줄링

RR 스케줄링

RR(Round Robin / 라운드 로빈) 스케줄링은 대화형 시스템에서 사용되는 선점 스케줄링 방식이다. 이 알고리즘은 프로세스가 도착한 순서대로 프로세스를 디스패치하지만 정해진 시간 할당량(또는 시간 간격)에 의해 실행을 제한한다. 즉, 시간 할당량을 매 프로세스에 주고 할당된 시간 안에 완료되지 못한 프로세스는 준비 큐의 맨 뒤에 배치되도록 하여 CPU를 독점하지 않고 공평하게 이용될 수 있게 한다.

 

RR 스케줄링의 예

예를 들어, 아래와 같이 4개의 프로세스가 주어지고 시간 할당량은 3으로 가정하자.

도착시간     0 1 2 3
프로세스     A B C D
CPU 사이클  6 3 1 4 

처음에는 프로세스 A만 도착했으므로 바로 디스패치하여 실행시킨다. 시간 할당량 3이 지날 동안 프로세스 A는 계속 실행 중이고 준비 큐에는 프로세스 B,C,D가 순서대로 도착하여 기다리고 있다. 따라서 RR 스케줄링 알고리즘은 프로세스 A를 준비 큐의 맨 뒤로 배치시키고 다음 차례인 프로세스 B를 디스패치하여 실행시킨다.

 

시간 할당량 3이 지나는 동안 프로세스 B도 마침 종료를 하게되어 다음 순서인 프로세스 C를 디스패치하여 실행시킨다. 프로세스 C는 1만큼의 시간 만에 종료되어 바로 다음 순서인 프로세스 D를 디스패치하여 실행시킨다.

 

다시 시간 할당량 3이 지나도 프로세스 D는 종료하지 못하여 RR 스케줄링은 프로세스 D를 준비 큐의 맨 뒤로 배치시키고, 다음 차례인 프로세스 A를 디스패치하여 실행시킨다.

 

시간 할당량 3이 지나면 A도 종료가 되고, 마지막으로 프로세스 D를 디스패치하여 실행시키면 1만큼 지난 뒤 종료된다. 최종 결과는 아래와 같다.

0     3     6   7   10   13  14
|  A  |  B  | C | D |  A  | D |

각 프로세스가 준비 큐에 있었던 시간인 대기시간은, 프로세스 A는 3부터 10 사이인 7이 되고, 프로세스 B는 1(도착시간 기준)부터 3 사이인 2로, 프로세스 C는 2부터 6사이인 4, 프로세스 D는 3부터 7사이와 10부터 13 사이이므로 4+3=7이 된다.

그리고 반환시간은 프로세스 A는 13-0=13, 프로세스 B는 6-1=5, 프로세스 C는 7-2=5, 프로세스 D는 14-3=11이다. 아래는 프로세스의 대기시간과 반환시간을 정리한 것이다.

프로세스 A B C D
대기시간 7 2 4 7
반환시간 13 5 5 11

따라서 평균 대기시간은 (7+2+4+7)/4=5 이고, 평균 반환시간은 (13+5+5+11)/4=8.5가 된다.

 

성능 

RR 스케줄링 알고리즘의 성능은 평균 CPU 소요시간에 대한 시간 간격의 길이에 따라 달라진다. 간격이 너무 큰 경우에는 FCFS 정도로 성능이 낮아질 것이다. 간격이 너무 짧은 경우 잦은 문맥 교환이 작업 수행을 방해하여 오버헤드가 크게 증가할 것이다.

 

따라서 가장 적절한 시간 간격은 시스템 형태에 달려 있다. 대화형 환경에서 사용자가 간단한 요청을 한 경우라면 시스템은 빠른 응답시간을 요구한다. 하지만 일괄처리 시스템이라면 응답시간은 중요한 것이 아니고 오버헤드가 중요한 요인이 된다.

 

적절한 시간 간격을 결정하는 데는 일반적인 규칙 두 가지가 있다. 첫째는 80%의 CPU 사이클을 처리할 수 있도록 하는 것이고, 둘째는 한 번의 문맥 교환에 걸리는 시간보다 100배 정도는 길어야 한다. 이런 규칙은 몇몇 시스템에 채택되어 사용되고 있으나 변동 가능하다.

 

요약

RR (Round Robin) 스케줄링

• 선점 스케줄링 알고리즘
• 준비 큐에 도착한 순서에 따라 디스패치하지만
• 정해진 시간 할당량에 의해 실행을 제한
• 시간 할당량 안에 완료되지 못한 프로세스는 준비 큐의 맨 뒤에 배치 • 대화형 운영체제에 유용

장점

• CPU를 독점하지 않고 공평하게 이용
• 대화형 운영체제에 유용

단점

• 시간 할당량이 너무 크면 FCFS 스케줄링과 같아짐
• 시간 할당량이 너무 작으면 문맥 교환에 따른 오버헤드가 크게 증가함

 

Reference

운영체제 / KNOUPress, press.knou.ac.kr/goods/textBookView.do?condCmdtCode=9788920017322

운영체제 - 한국방송통신대학교 출판문화원