[Chapter 5. CPU 스케줄링] 스케줄링 알고리즘(라운드 로빈, 다단계 큐, 다단계 피드백 큐)

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

스케줄링 알고리즘

---

라운드 로빈 스케줄링 (Round-Robin Scheduling)

RR 스케줄링이라고도 한다.

FIFO 스케줄링에서 선점이 추가된 스케줄링이라고 볼 수 있다.

 

구현 : 원형 큐(circular queue)

 

준비 큐를 원형 큐로 간주하고, 새로운 프로세스들은 원형 큐의 꼬리에 추가된다.

이 큐에서 순환식으로 한 프로세스에게 작은 단위의 시간량(타임 퀀텀, time quantum)만큼씩 CPU를 할당한다.

* 타임 퀀텀은 타임 슬라이스와 같은 개념이다. (10ms ~ 100ms)

 

즉, 실행 상태의 프로세스가 타임 퀀텀이 지나면 선점되는 것이다. (선점형 스케줄링)

 

 

과정

1. 준비 큐에서 첫 번째 프로세스를 선택한다.

2. 한번의 타임 퀀텀 이후 인터럽트를 걸도록 타이머(timer)를 설정한다.

 

3-1. 프로세스의 CPU 버스트 타임이 한 번의 타임 퀀텀보다 짧다면 프로세스 자신이 CPU를 자발적으로 방출한다.

 

3-2. 프로세스의 CPU 버스트 타임이 한 번의 타임 퀀텀보다 길다면

        타이머가 끝나고 운영체제가 인터럽트를 발생시켜 문맥 교환이 일어나고, 실행하던 프로세스는 준비 큐의 꼬리에 넣어진다.

        그 후 CPU 스케줄러는 준비 큐의 다음 프로세스를 선택해 CPU를 할당한다.

 

 

이론상으로는 n개의 프로세스가 1/n의 속도로 동시에 실행되는 셈이다.

준비 큐에 n개의 프로세스가 있고, 타임퀀텀이 q라고 할 경우,

문맥 교환 시간을 고려하지 않는다면 각 프로세는 (n-1)*q 시간 이내에 CPU를 할당받는다.

 

평균 반환 시간과 평균 대기 시간이 SJF 스케줄링보다 길지만,

모든 프로세스가 CPU를 할당의 기회를 공정하게 얻기 때문에 기아상태는 발생하지는 않는다.

 

 

단점

1. 문맥 교환이 잦게 일어나, 그것에 대한 오버헤드로 처리율(throughput)이 감소한다.

* 오버헤드(overhead) : 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간, 메모리 등

 

타임 퀀텀이 짧아질수록 문맥 교환 횟수가 늘어난다.

 

2. 타임 퀀텀의 크기에 성능이 큰 영향을 받는다.

타임 퀀텀의 크기가 너무 크다면 FIFO 스케줄링과 동일하게 될 것이며, (한 타임 퀀텀 동안 프로세스의 실행이 완료됨)

너무 작다면 문맥 교환이 너무 많이 일어나 프로세스의 실행이 느려질 것이다. (반환율은 증가, 처리율은 감소)

 

---

평균 반환 시간도 타임퀀텀의 크기에 영향을 받는다.

* 반환 시간 : 프로세스가 생성되어 작업을 마치고 종료될 때까지 걸린 시간

 

그렇다면 타임 퀀텀의 크기를 증가시킬수록 평균 반환 시간은 짧아질까?

 

 

CPU 버스트 타임이 10인 3개의 프로세스 A, B, C가 있다고 하자.

 

1. 타임 퀀텀이 1인 경우

평균 반환 시간 = (28 + 29 + 30) / 3 = 29

 

2. 타임 퀀텀이 10인 경우

평균 반환 시간 = (10 + 20 + 30) / 3 = 20

 

위의 두 예시에서는 타임 퀀텀의 크기를 증가시켰을 때 평균 반환 시간이 짧아진 것을 확인할 수 있다.

하지만 다음의 예시도 보면, 타임 퀀텀을 증가시키더라도 평균 반환 시간은 반드시 개선되는 것은 아님을 알 수 있다.

 

3. 타임 퀀텀이 3인 경우

평균 반환 시간 = (28 + 29 + 30) / 3 = 29

 

 

아래 그림은 타임 퀀텀에 따른 평균 반환 시간을 나타낸 그래프이다.

타임 퀀텀이 3에서 5로 증가할 때 평균 반환 시간도 같이 증가하는 것을 볼 수 있다.

 

 

대부분의 프로세스들이 한 타임 퀀텀 내에 하나의 CPU 버스트를 끝낸다면 평균 반환 시간은 개선된다.

따라서 경험적으로 타임 퀀텀은 프로세스들의 CPU 버스트들 중 80% 정도보다 길도록 조정하는 것이 좋다.

 

다단계 큐 스케줄링 (Multilevel Queue Scheduling)

우선순위마다의 별도의 준비 큐를 형성하여 스케줄링하는 방법이다.

 

프로세스들은 프로세스의 특성(대화형, 배치(background) 등)에 따라 우선순위가 부여되어 한 개의 큐에 영구적으로 할당되는데

각 큐에는 그의 성격에 맞는 스케줄링 알고리즘을 별도로 적용할 수 있다. (FCFS, RR 등)

 

항상 가장 높은 우선순위 큐의 프로세스에게 CPU를 먼저 할당해준다.

 

 

한 프로세스가 실행하고 있던 도중에 인터럽트가 발생, 비자발적으로 문맥 교환이 일어나 준비 큐로 돌아왔다고 하자.

 

인터럽트를 처리한 후 다시 스케줄링을 하려고 할 때

기존 수행 중이었던 프로세스가 있는 큐보다 높은 단계의 큐에 새로운 프로세스가 하나라도 있다면

바로 그 프로세스에 CPU를 할당해주어야 한다.

 

즉, 다단계 큐 스케줄링은 선점형 스케줄링의 일종이다.

 

다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)

다단계 큐 스케줄링에서는 프로세스들이 영구적으로 하나의 준비 큐에 할당되었다.

이와는 다르게, 다단계 피드백 큐 스케줄링에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다.

 

다단계 큐 스케줄링 + 동적인 프로세스 우선순위 변화

 

 

우선 프로세스가 처음으로 시스템에 진입했을 때에는 최상위 큐에 삽입한다.

 

만약 실행 중인 프로세스가 자꾸 모든 타임 슬라이스를 소진하여 CPU 시간을 너무 많이 사용한다면

한 단계씩 밑으로 내려보내, 하위 큐의 뒤로 삽입한다. (CPU-bound 프로세스)

 

만약 하위 큐에 있는 프로세스가 타임 슬라이스를 다 소진하지 않고 대기 상태로 돌아가면서 CPU를 반납한다면

상위 큐에 삽입하여 위로 거슬러 올라가도록 한다. (I/O bound 프로세스)

 

따라서 하위 큐로 갈수록 CPU-bound 프로세스임을 볼 수 있으며,

가장 하위 큐는 FCFS로 스케줄링을 실행한다.

 

 

하지만 이렇게만 진행한다면 하위 큐에서는 기아 상태가 발생할 수 있다.

그리하여 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동시키는 노화(에이징, Aging) 기법을 통해 기아 상태를 예방한다.

 

 

다단계 피드백 큐는 가장 일반적인 CPU 스케줄링 알고리즘이나,

다음의 요소들을 모두 고려하여야 하기 때문에 이 스케줄링 방법을 적용할 때는 매우 복잡한 판단을 내려야 한다.

 

1. 큐의 개수
2. 각 큐를 위한 스케줄링 알고리즘
3. 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
4. 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
5. 프로세스가 서비스를 필요로 할 때 프로세스가 들어갈 큐를 결정하는 방법