김덕우

CPU 스케줄링이란 어떤 프로세스에게 CPU를 할당할 지 결정하는 방식을 말한다. 다양한 스케줄링 알고리즘 중 대표적인 라운드 로빈 스케줄링에 대해서 살펴보려 한다.

< 목차 >

1. 라운드 로빈 스케줄링 - 의미

2. 라운드 로빈 스케줄링 - 장점

3. 라운드 로빈 스케줄링 - 단점

4. 라운드 로빈 스케줄링 - 사례

5. 다른 기법과 비교1 - SJF

6. 다른 기법과 비교2 - FCFS

1. 라운드 로빈 스케줄링 의미

라운드 로빈 스케줄링(Round Robin Scheduling)은 다른 스케줄링 알고리즘과 달리 시분할 시스템의 성질을 가장 잘 활용한 점이 특징이다. 

기본적으로 라운드 로빈 스케줄링은 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간을 특정 시간으로 제한하는데, 이러한 제한 시간을 할당시간(time quantum)이라고 한다.

스케줄러는 사용시간을 초과한 프로세스에게서 CPU를 회수한 다음, 준비 큐에 대기하고 있는 다른 프로세스에게 CPU를 새로 할당한다.

이 때, CPU를 회수당한 프로세스는 준비 큐의 맨 뒤에 다시 차례를 기다린다.

2. 장점

1. 여러 종류의 이질적인 프로세스가 같이 실행되는 환경에서 효과적이다.

예를들어 n개의 프로세스가 준비 큐에 대기하고 있고 할당시간이 q라고 가정하면,

모든 프로세스는 적어도 (n-1)q 시간 안에는 프로세스를 한번 할당 받는다.

선입선출 스케줄링의 경우 먼저 들어온 프로세스의 작업이 오래 끝날때까지 후속 프로세스가 오래 기다리는 경우가 발생한다.

이에 비해 라운드 로빈의 경우 할당 시간이 정해져 있기 때문에 비교적 공평하게 CPU 점유 기회를 얻는다.

2. 대화형 프로세스의 빠른 응답시간을 보장할 수 있다.

대화형 프로세스의 경우, 사용자의 입력에 대응하여 즉각적인 출력을 내보내는 것이 중요하다.

라운드 로빈은 할당 시간의 제한으로 응답시간(준비 큐에 들어온 시간 ~ 첫 번째 CPU를 획득한 시간)이 짧은 편이기 때문에 사용자에게 즉각적인 피드백을 보내기에 유용하다.

3. 효율성과 형평성의 균형을 갖췄다.

CPU 버스트(사용자 프로그램이 I/O를 수행한 후 다음 I/O를 수행하기까지 CPU를 직접 가지고 명령을 수행하는 일련의 단계)가 짧은 프로세스는 작업을 빨리 마무리할 수 있기 때문에 효율적이다.

반면 CPU 버스트가 긴 프로세스도 비교적 빨리 CPU 점유 기회를 얻을 수 있기 때문에 형평성을 갖춘 방식이다.

3. 단점

할당시간을 너무 짧게 설정하면 문맥교환의 오버헤드가 증가해 시스템의 효율이 떨어질 수 있다. 

예를들어 프로세스 A의 CPU 버스트 시간이 '10'이라고 가정하자.

할당시간을 각각 10, 5, 1로 설정할 경우 문맥 교환 발생횟수는 아래와 같다.

- 할당시간 10 -> 문맥교환 발생 x

- 할당시간 5 -> 문맥교환 1회 발생

- 할당시간 1 -> 문맥교환 10회 발생

할당시간이 10이면 A가 최초로 CPU를 할당 받았을 때 작업을 완료할 수 있다.

반면 할당시간이 1이라면 A가 한번에 CPU를 점유할 수 있는 최대 시간이 1이므로, 총 10회의 CPU할당이 필요하다.

4. 사례

프로세스 P1, P2, P3가 순서대로 준비 큐에 도착했고, 할당시간은 10인 경우의 CPU 스케줄링을 생각해보자

각 프로세스의 CPU버스트 시간은 아래와 같다

라운드 로빈 스케줄링을 적용하면 결과는 아래와 같다

P1의 경우 맨 처음 CPU를 할당 받지만 할당시간(10) 내에 작업을 완료하지 못하였고,

준비큐 맨 뒤로 가서 대기한 후, 다시 CPU를 할당 받는 과정을 2번 반복했다.

5. 다른 기법과 비교 - 최단 작업 우선 스케줄링

1. 최단작업 우선 스케줄링

CPU 버스트가 짧은 작업이 CPU 버스트가 긴 선행작업이 마무리 될때까지 오랜 시간 기다리는 현상을 콘보이 현상(Convoy effect)라고 한다.

최단 작업 우선(Shortest-Job First:SJF) 스케줄링은 CPU버스트가 가장 짧은 프로세스에 CPU를 우선적으로 할당하는 방식으로 콘보이 현상을 해결한다.

하지만 CPU 버스트가 짧은 프로세스가 계속해서 준비 큐에 도착할 경우 CPU 버스트가 긴 프로세스는 무한정 기다리는 문제가 발생한다.

즉 효율성을 높이면서 형평성을 희생하는 것이다.

2. 라운드 로빈 스케줄링

라운드 로빈의 경우 보다 공정한 방식으로 스케줄링한다. 

프로세스가 CPU를 사용하는 시간에 비례해서 소요시간과 대기시간이 결정되기 때문이다.

즉, 할당시간의 제한으로 CPU 버스트가 긴 프로세스도 비교적 짧은 시간 내에 CPU를 점유할 수 있다.

6. 다른 기법과 비교 - 선입선출 스케줄링

1. 선입선출 스케줄링

선입선출(First-Come-First-Served:FCFS) 스케줄링은 준비 큐에 먼저 도착한 순서대로 프로세스에게 CPU를 할당하는 방식이다. 

평균 대기시간과 평균 소요시간 측면에서 좋은 결과를 보인다는 장점이 있지만,

프로세스 간 대기시간이나 소요 시간의 편차가 매우 크다.

단적인 예로 100개의 프로세스가 준비 큐에 대기중이라면 100번 째 프로세스는 앞선 99개의 프로세스가 마무리 될 때까지 대기해야 한다.

2. 라운드 로빈 스케줄링

라운드 로빈 스케줄링은 평균 대기시간과 평균 소요시간이 FCFS 보다 비효율적이다. 

하지만, 대기시간이나 처리시간의 편차가 프로세스 마다 크지 않다.

100째 프로세스는 앞선 99개 프로세스의 작업이 모두 완료될 때까지 기다릴 필요가 없으며,

할당시간이 10이라고 할 경우 99회 x 10 시간만큼 기다린다면 CPU를 할당받을 수 있다. 

* 본 포스팅은 저서 '운영체제와 정보기술의 원리(반효경/이화여자대학교출판문화원)'을 참고하여 작성했습니다.