[운영체제] CPU 스케줄링 - 라운드로빈 알고리즘

운영체제 수업 내용의 CPU 스케줄링 정책 중, 선점 스케줄링 정책과 라운드 로빈 알고리즘에 대해 정리해보았습니다.

 

선점 스케줄링 정책(preemptive scheduling policy)

선점 스케줄링 정책은 CPU 스케줄링의 한 종류로, 실행 중인 프로세스에 인터럽트를 걸고 다른 프로세스에 CPU를 할당할 수 있는 스케줄링 방식입니다. 현재 실행 중인 프로세스가 완료되지 않았더라도 다른 프로세스가 CPU를 선점하여 실행될 수 있도록 하기 때문에, 여러 개의 프로세스를 동시에 실행할 수 있으며, 우선순위가 높은 프로세스가 먼저 실행되도록 할 수 있습니다.

선점 방식은 높은 우선순위의 프로세스를 우선 처리해야 하는 경우에 유용하기 때문에, 일반적으로 실시간 시스템과 시분할 시스템에서 사용됩니다. 시분할 시스템에서 선점 스케줄링 방식을 사용하면 프로세스들이 동시에 실행되는 것처럼 보이지만, 사실은 매우 짧은 시간 동안 CPU를 할당받아 실행됩니다. 이렇게 CPU를 분할하여 여러 프로세스를 실행하면, 사용자는 빠른 응답 시간과 빠른 프로그램 실행 시간을 경험할 수 있습니다. 

 

선점 스케줄링은 많은 장점을 가지고 있습니다. 우선순위가 높은 프로세스가 먼저 처리되기 때문에, 중요한 작업을 빠르게 처리하여 사용자에게 빠른 응답성을 제공할 수 있습니다. 또한, 여러 개의 프로세스를 동시에 실행할 수 있기 때문에, CPU를 최대한 활용할 수 있고, 각 프로세스에 일정 시간 동안 CPU를 할당해주는 Round Robin 알고리즘을 사용하면, 프로세스들이 공정하게 CPU 시간을 나눠가지게 됩니다.

 

반면에, 선점 스케줄링 방식을 사용하면 프로세스 간의 전환이 빈번하게 일어나기 때문에, 상태를 저장하고 복원하는 오버헤드가 발생할 수 있다는 단점도 가지고 있습니다. 그렇기 때문에 선점 스케줄링 정책을 적용할 때는 문맥 교환에 따른 오버헤드를 고려헤야 하고, 운영 체제 자체는 문맥 교환이 매우 빠르게 실행되도록 만들어져야 합니다. 

 

또한, 선점 스케줄링에서는 프로세스 간의 경쟁이 발생하기 때문에, 데드락과 같은 문제가 발생할 수 있고, 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스에 의해 블록킹되는 경우, 우선순위 역전 문제가 발생할 수 있습니다. 이러한 문제를 해결하기 위해 Aging 기법을 적용하기도 합니다. Aging 기법은 우선순위가 낮은 프로세스들이 오래 기다리는 것을 방지하기 위해, 해당 프로세스의 우선순위를 점차적으로 높여가는 방식입니다. 이를 통해 일정 시간 동안 실행되지 못한 프로세스들이 우선순위가 높아져서 더 높은 CPU 시간을 할당받을 수 있습니다.

 

대표적인 선점 스케줄링 알고리즘으로는 RR(Round Robin) 스케줄링, SRT(Shortest Remaining Time) 스케줄링, 다단계 피드백 큐 스케줄링 등이 있습니다. 

 

Round Robin 스케줄링

라운드 로빈(Round Robin) 스케줄링은 선점 스케줄링 정책을 사용하는 CPU 스케줄링의 한 종류로, 프로세스가 도착한 순서대로 프로세스들을 디스패치하지만 정해진 시간 할당량이나 시간 간격에 의해 실행을 제한하는 방식입니다. 

이 스케줄링 방식에서 각 프로세스는 일정 시간 동안 동일한 할당 시간을 부여받습니다. 시간 할당량은 일반적으로 10ms에서 100ms 사이의 값을 사용합니다. 할당 시간 안에 디스패치된 프로세스가 종료되지 못하면 해당 프로세스는 중지되고, 다른 프로세스가 CPU를 할당받게 됩니다. 이때, 중지된 프로세스는 준비 상태로 전이되어 준비 큐의 마지막으로 들어가게 되며, 자신의 상태를 저장하여 나중에 CPU를 다시 할당받게 되면 저장되어있는 이전 상태부터 진행하게 됩니다. 

 

이 방식은 각 프로세스에 일정 시간 동안 CPU 시간을 공정하게 나눠주기 때문에, 모든 프로세스들이 동등하게 CPU 시간을 할당받을 수 있다는 장점이 있습니다. 또한, 프로세스의 응답 시간을 일정하게 유지할 수 있습니다. 프로세스가 CPU 시간을 할당받을 때마다, 다른 프로세스에게 CPU가 할당되므로 응답 시간이 고르게 분포됩니다.

 

반면에, 라운드 로빈 스케줄링에서는 할당 시간이 작을수록 프로세스 간 전환이 빈번하게 일어나게 되어 오버헤드가 발생할 수 있습니다. 반대로, 할당 시간이 크면 응답 시간이 길어지게 되어 사용자 경험에 나쁜 영향을 미칠 수 있습니다. (시간 할당량이 각 프로세스의 실행시간보다 큰 경우에는 FCFS 스케줄링과 동일해짐)

 

따라서, 시간 할당량을 어떻게 정하는지에 따라 라운드 로빈 스케줄링의 성능이 달라지는 점을 고려하여, 오버헤드의 비율이 크지 않도록 하면서 프로세스가 한 번에 처리할 양을 처리할 수 있는 정도가 될 수 있도록 할당 시간을 적절하게 설정하여 사용하는 것이 중요합니다.

 

예시

라운드 로빈 알고리즘으로 아래 표의 프로세스들이 수행되는 순서와 순서가 정해지는 과정을 설명해보겠습니다.

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

• 시간 할당량을 임의로 3으로 설정하였습니다.
• 시간할당량이 지났을때 다른 프로세스가 도착했을 경우 새로 도착한 프로세스가 준비 큐에 먼저 들어가는 것으로 임의로 가정했습니다.

시간	수행 프로세스	남은 CPU 사이클
0	A 시작	A프로세스 3남은
3	A끝 B시작	0
6	B끝 C시작	0
7	C끝 A시작	0
10	A끝 D시작	0
12	D끝 E시작	E프로세스 1남음
15	E끝 E시작	0
16	E끝	0

 

먼저, 프로세스 A는 도착하는 즉시 바로 실행되며, 3의 시간할당량 동안 실행됩니다. 이후 시각 2에 B가 도착하여 준비 큐에 B가 들어갑니다. 

시각 3에는 C가 도착하는 동시에 A의 시간할당량이 끝납니다. A 프로세스는 3만큼의 CPU 사이클이 남아있지만 이렇게 동시에 준비 큐에 들어갈 경우 새로운 프로세스가 먼저 도착하는 것으로 가정했기 때문에 C -> A의 순서로 준비 큐에 들어갑니다. 시각 3에 A와 C가 준비 큐에 들어가면서 프로세스 B가 실행됩니다. 

 

시각 5에는 프로세스 D가 도착합니다. 준비 큐에는 C->A->D의 순서로 쌓이게 됩니다.

시각 6에는 프로세스 B의 시간할당량이 끝나게 됩니다. B는 CPU사이클이 3만큼 필요하기 때문에 시간할당량이 끝나면 남은 CPU 사이클이 0이 되며 프로세스가 끝나게 됩니다. 그리고 시각 6에 준비 큐에 있는 프로세스 C가 실행됩니다.

 

프로세스 C는 CPU 사이클이 1이기 때문에 시각 7에 끝나게 되며, 시각 7에는 프로세스 E가 도착합니다. 준비 큐에는 A-> D -> E의 순서로 프로세스가 쌓이게 됩니다. 프로세스 C의 실행이 끝나면 시각 7에 준비 큐에 있던 프로세스 A가 실행됩니다. 

 

시각 10에는 프로세스 A의 실행이 끝나고 프로세스 D가 실행됩니다.

프로세스 D는 CPU 사이클이 2이기 때문에 시각 12에 종료됩니다. 이후 시각 12에 준비 큐에 있던 마지막 프로세스인 프로세스 E가 실행됩니다. 준비 큐에 더이상 다른 프로세스가 남아있지 않기 때문에 프로세스E는 시간할당량인 3 이후에 1만큼 CPU 사이클을 더 사용하고 시각 16에 종료됩니다.

 

아래의 표는 위의 결과에 대한 각 프로세스들의 대기시간과 반환시간을 나타냅니다. 

	A	B	C	D	E
대기시간	4	1	3	5	5
반환시간	10	4	4	7	9

 

프로세스 A는 0에 도착하여 10에 종료되었으므로 반환시간은 (10-0)= 10이고, 3부터 7까지 대기하였으므로 대기시간은 4입니다.

프로세스 B는 2에 도착하여 6에 종료되었으므로 반환시간은 4이고, 2부터 3까지 대기하였으므로 대기시간은 1입니다.

프로세스 C는 3에 도착하여 7에 종료되었으므로 반환시간은 4이고, 3부터 6까지 대기하였으므로 대기시간은 3입니다. 

프로세스 D는 5에 도착하여 12에 종료되었으므로 반환시간은 7이며, 5부터 10까지 대기하였으므로 대기시간은 5입니다. 

프로세스 E는 7에 도착하여 16에 종료되었으므로 반환시간은 9이며, 7부터 12까지 대기하였으므로 대기시간은 5입니다. 

이 프로세스들의 평균 반환시간은 (10+4+4+7+9) / 5 = 6.8입니다.

 

비교 예시  - 비선점 스케줄링 정책 -FCFS 스케줄링 방식

위에서 선점 스케줄링 방식을 골라서 설명했기 때문에, 비선점 스케줄링 정책을 사용하는 알고리즘 중 FCFS 스케줄링 방식을 이용하여 위 예시의 프로세스 반환시간과 평균 반환 시간을 구해보겠습니다.

  FCFS(First-Come First-Served) 스케줄링은 프로세스가 준비 큐에 도착한 순서에 따라 디스 패치되며，일단 한 프로세스가 CPU를 차지하면 그 프로세스의 수행이 완료된 후에 다음 프로세스가 CPU를 차지하고 수행합니다.

시간	수행 프로세스
0	A 시작
6	A끝 B시작
9	B끝 C시작
10	C끝 D시작
12	D끝 E시작
16	E끝

 

	A	B	C	D	E
대기시간	0	4	6	5	5
반환시간	6	7	7	7	9

프로세스 A는 0에 도착하여 6에 종료되었으므로 반환시간은 (6-0)= 6입니다.

프로세스 B는 2에 도착하여 9에 종료되었으므로 반환시간은 7입니다.

프로세스 C는 3에 도착하여 10에 종료되었으므로 반환시간은 7입니다.

프로세스 D는 5에 도착하여 12에 종료되었으므로 반환시간은 7입니다.

프로세스 E는 7에 도착하여 16에 종료되었으므로 반환시간은 9입니다.

이 프로세스들의 평균 반환시간은 (6+7+7+7+9) / 5 = 7.2입니다.