[OS] RR(Round Robin) 스케줄링 이란?

서론

[OS] 프로세스 응답 시간(Response Time) 측정 방법

[OS] 프로세스 응답 시간(Response Time) 측정 방법

이전 글에서 Shortest Job First(SJF) 스케줄링 기법을 적용했을 때 응답 시간을 구하는 방법을 살펴보았다.

해당 예제의 경우 평균 응답 시간은 5초였다. 그러나 응답 시간이 5초라는 것은 매우 비효율적이었고, 그래서 이번 글에서는 이러한 단점을 보완하기 위해 나온 RR(Round Robin) 스케줄링 기법을 알아보고자 한다.

RR(Round Robin) 스케줄링 이란?

Round Robin 스케줄링 기법은 특정 작업이 CPU를 할당 받아 끝날 때까지 일을 수행하는 것이 아니라, 정해진 시간(time slice)만큼 일을 수행하고 다른 작업으로 CPU를 위임하는 스케줄링 기법이다.

 

이해를 돕기위해 위 그림의 예제를 통해 살펴보자.

• 위 프로세스의 경우 A,B,C 모두 0초에 도착한 프로세스이며 모두 5만큼의 작업량을 가지고 있다.

 

먼저, 위 그림 예제인 SJF 스케줄링 기법의 경우에는 A,B,C 3개의 작업은 일이 끝나기 전까지는 다른 작업으로 CPU를 위임하지 않는다.

그래서 SJF 스케줄링 기법의 응답 시간(Reponse Time)은 (0 + 5 + 10) / 3 = 5sec 였다.

• Tresponse(응답 시간) = Tfirstrun(프로세스 시작 시간) - Tarrival(프로세스 도착 시간)

그러면 RR 스케줄링 기법은 어떻게 동작할까? 이번 글에서는 위 그림을 예제를 가지고 RR 스케줄링 기법으로 처리해보고자 한다.

• 또한, 정해진 시간(time slice)은 1초로 설정했다고 가정한다.

RR(Round Robin) 스케줄링 흐름

SJF 스케줄링과 달리 3개의 프로세스가 일이 끝날 때까지 CPU를 독점하는 것이 아니라 1초 마다 CPU를 나눠쓰면서 정해진 일을 수행하는 것을 확인할 수 있다. 이번에는 RR 스케줄링 기법을 사용했을 때의 응답 시간을 알아보자.

	프로세스 시작 시간	프로세스 도착 시간	응답 시간
A	0	0	0
B	1	0	1
C	2	0	2

위 표를 기반으로 해당 프로세스의 평균 응답 시간을 구하면 다음과 같다.

• (0 + 1 + 2) / 3 = 1sec

SJF 스케줄링에 비하면 평균 응답 시간을 4초나 줄인 것을 알 수 있다. 그러면 응답 시간을 더 줄이기 위해서는 어떻게 해야할까?

위에서 정한 정해진 시간(Time Slice)를 낮추면 응답 시간을 더 줄일 수 있을 것이다.

 

만약 Time Slice를 0.1초로 설정했다고 가정하면 프로세스 B는 0.1초만에 반응할 것이므로 사용자 입장에서는 굉장히 반응 속도가 빠르다고 느낄 수 있다.

 

하지만, Time Slice를 마냥 줄이는 것은 좋지 않은 방법이다. 그 이유는 Trap 이 발생할 때마다 커널이 개입해야 하고, 레지스터도 지속적으로 변경되어야 한다. 이러한 것들은 결국 Overhead 비용이 커지게 되며 전체 성능에 악영향을 줄 수 있기 때문이다.

• 위에서 언급한 Trap은 소프트웨어 인터럽트로 프로그램 내부에서 일어나는 인터럽트이다. 예외 발생과 시스템 콜 등이 존재한다.

다시 말하면 간단한 작업을 수행하는 일에 Time Slice를 너무 작게하면 오히려 성능이 저하될 수 있다는 것이다.

 

성능 저하의 근거로 SJF 스케줄링과 RR 스케줄링의 반환 시간(Turnaround Time)을 비교해보자.

• 반환 시간은 (완료시간 - 도착 시간)으로 구한다.

SJF 스케줄링 기법으로 구한 반환 시간을 구해보면

• 프로세스 A의 반환 시간 : 5 - 0 = 5
• 프로세스 B의 반환 시간 : 10 - 0 = 10
• 프로세스 C의 반환 시간 : 15 - 0 = 15
• 평균 반환 시간 : (5 + 10 + 15) / 3 = 10

이번에는 RR 스케줄링 기법으로 구한 반환 시간을 구해보면

• 프로세스 A의 반환 시간 : 13 - 0 = 13
• 프로세스 B의 반환 시간 : 14 - 0 = 14
• 프로세스 C의 반환 시간 : 15 - 0 = 15
• 평균 반환 시간 : (13 + 14 + 15) / 3 = 14

이처럼 SJF을 수행했을 때에 비해서 반환 시간이 4초나 나빠진 것을 확인할 수 있다.

그래서 응답 시간을 최소화하는 RR 스케줄링 기법이 모든 기준에서 항상 좋은 기법이라고 단정지을 수 없다.

 

이번 글을 통해서 알 수 있는 Round Robin 스케줄링의 특징은 다음과 같다.

RR 스케줄링 기법 특징

• SJF는 성능위주, 그래서 Unfair 하지만 Round Robin은 CPU를 공평하게 사용하기 때문에 Fair 하다는 특징이 있다.
• 그러나 성능 면에서 응답 시간(Response Time)은 좋지만 반환 시간(Turn-around Time)은 비효율적이라는 특징이 있다.