[운영체제] Round Robin (RR) 스케줄링 알고리즘

Round Robin (RR) 스케줄링 알고리즘 이란?

 

Round Robin (RR) 스케줄링은 타임 슬라이스 또는 타임 퀀텀이라고 불리는 

 

고정된 시간 단위 동안 모든 준비 상태의 프로세스에 

 

CPU 시간을 순차적으로 할당하는 방법이다.

 

이 방법은 각 프로세스가 공평하게 CPU 시간을 받도록 설계되었다.

 

 

 

RR 스케줄링의 기본 원리

타임 슬라이스 설정

각 프로세스는 타임 슬라이스만큼 CPU 시간을 받는다.

 

타임 슬라이스는 보통 몇 밀리초에서 몇 초 사이다.

 

 

순환 큐 사용

준비 상태의 프로세스는 순환 큐에 들어가 타임 슬라이스가 지나면 큐의 뒤로 이동한다.

 

 

콘텍스트 스위칭

타임 슬라이스가 끝나면 현재 프로세스는 작업을 중단하고 다음 프로세스로 전환한다.

 

이때 콘텍스트 스위칭이 발생한다.

 

 

 

 

RR 스케줄링의 장점

공평성

모든 프로세스가 동일한 CPU 시간을 받기 때문에 하나의 프로세스가 자원을 독점하는 것을 방지한다.

 

응답 시간 개선

사용자와 상호 작용하는 프로세스가 빠르게 응답할 수 있도록 한다.

 

 

 

단점과 고려사항

 

오버헤드

RR은 빈번한 콘텍스트 스위칭으로 인해 오버헤드가 발생할 수 있다.

 

이는 특히 타임 슬라이스가 너무 짧을 때 두드러진다.

 

 

타임 슬라이스 최적화

타임 슬라이스의 길이는 성능에 큰 영향을 미친다.

 

너무 길면 FIFO와 유사해지고, 너무 짧으면 오버헤드가 증가한다.

 

 

기아 현상 방지

RR은 기본적으로 공평하지만, I/O 집중적인 작업을 하는 프로세스는 CPU 시간이 낭비될 수 있다.

 

 

 

 

RR 스케줄링 예제

 

타임 슬라이스가 10초인 시스템이라고 가정하고 평균 대기시간을 계산해 보자.

프로세스 1을 p1, 프로세스 2를 p2, 프로세스 3을 p3이라고 해보자.

p1의 Burst time은 25초, p2의 Burst time은 4초, p3의 Burst time은 10초이다.

 

이 프로세스들은 동시에 큐에 들어왔고 실행순서는 P1, P2, P3라고 가정해 보자.

 

 

P1은 큐에 들어오자마자 실행되기 때문에 대기시간이 0초이다.

P1은 타임슬라이스 10초만큼 실행하다가 시간을 초과했기 때문에 

 

p2에게 CPU를 뺏기고 P1의 남은 작업은 가장 뒤로 이동한다.

 

 

 

p2는 p2이 실행하는 10초를 기다렸기 때문에 대기시간은 10초가 된다.

p2는 Burst time이 4초이기 때문에, 4초가 지나면 p3에게 cpu를 양보하고 작업을 마친다.

p3는 p1과 p2의 실행이 완료될 때까지 14(10 + 4) 초를 기다렸다. p3의 대기시간은 14초이다.

p3는 Burst time인 10초 동안 실행하고 작업을 마친다.

 

다음으로 p1이 다시 실행되는데 p1 은 p2와 p3의 실행이 완료될 때까지 14초를 기다렸다.

 

현재 p1은 Burst time이 15초로 타임슬라이스보다 크기 때문에 

 

타임슬라이스 값인 10초만 실행한다.

그리고 Burst time이 5초인 p1이 큐의 마지막으로 이동하는데 

대기 중인 프로세스가 없기 때문에 바로 p1이 실행된다. (대기시간 0)

이제 이 대기 시간으로 평균 대기 시간을 구해보자.

 

 

p1의 첫 번째 대기시간은 0초, p2의 대기시간 10초, p3의 대기시간 14초

p1의 두 번째 대기시간 14초, p1의 세 번째 대기시간 0초를 더하면 38초이고 

이를 프로세스 개수인 3으로 나누면 

 

평균 대기시간이 12.67 초로 나온다. (FIFO 알고리즘은 18초가 나온다.)

다른 상황에서는 FIFO 알고리즘과 RR 알고리즘의 대기시간이 비슷할 수도 있다.

평균대기시간이 비슷하다면, RR 알고리즘이 더 비효율적인 방식이다.

RR은 콘텍스트 스위칭이 있기 때문에 컨텍스트 스위칭 시간이 더 추가되기 때문이다.

 

 

 

RR 알고리즘의 성능은 타임 슬라이스 값에 따라 크게 달라진다. 

 

두 가지 상황으로 알아보자.

먼저 타임슬라이스가 큰 경우부터 살펴보자.

이론적으로 타임슬라이스가 무한대라고 가정하면 

 

먼저 들어온 프로세스의 작업이 종료될 때까지 실행하니까 FIFO 알고리즘이 되어버린다.

타임 슬라이스가 5초인 시스템에서 웹브라우저와 뮤직 플레이어를 실행시키면,

 

웹 브라우저가 5초 동작하다가 멈추고

 

음악이 5초 재생되다가 멈추고 다시 웹 브라우저가 5초 동작하니 굉장히 끊기게 될 것이다.


이번에는 타임슬라이스가 작은 경우를 살펴보자.

타임 슬라이스를 1밀리 초로 아주 작은 값으로 설정하면 

 

웹 브라우저와 뮤직 플레이어가 동시에 동작하는 것처럼 느껴진다.

하지만, 타임 슬라이스를 이렇게 너무 작게 설정해 버리면 

 

콘텍스트 스위칭이 너무 자주 일어나게 되고 타임 슬라이스에서 실행되는 프로세스의 처리량보다 

 

컨텍스트 스위칭을 처리하는 양이 훨씬 커져서 배보다 배꼽이 더 커지는 상황이 발생한다.

 

이러한 상황을 "오버헤드가 너무 크다"라고 표현한다.

최적의 타임슬라이스를 결정하는 방법은 사용자가 느끼기에 

 

여러 프로세스가 버벅거리지 않고 동시에 실행되는 것처럼 느껴지면서 

 

오버헤드가 너무 크지 않는 값을 찾아야 하는 것이다.

실제로 Windows Os는 타임슬라이스가 20ms, Unix는 100ms로 굉장히 짧다.

 

 

 

결론

 

RR 스케줄링은 대화형 시스템에서 효과적이며,

 

타임 슬라이스의 적절한 설정이 중요하다.

 

이 스케줄링 방식은 시스템의 요구에 따라 탄력적으로 조정되어야 하며,

 

다양한 작업 부하를 고려하여 최적화되어야 한다.

 

RR은 다른 스케줄링 알고리즘과 비교하여 특히 실시간 응답성이 요구되는 환경에서 유리할 수 있다.