05. 운영체제 - CPU Virtualization - Stride scheduling (4)

Proportional Share Scheduler

앞선 게시물의 스케줄링 기법들은 그냥 실행 가능한 job들에 대해 turn-around time과 response time을 고려하여 CPU time을 적절하게 할당해주는 방식이다.

이번 게시물에서는 job이 자신이 사용하고자 하는 CPU 점유율을 얘기하면, 설정된 점유율에 비례해서 스케줄링을 해주는 방식을 다룬다. 

이러한 Fair-share 스케줄러는 앞선 스케줄러의 turn-around time / response time 과는 다른 기준을 사용하여 디자인해야한다. 즉 현재 동작하는 프로세스들이 요구하는 지분만큼 CPU를 사용할 수 있도록 보장해주는 것이 필요하다.

 

Basic Concept

기본적인 아이디어는 티켓이다.

티켓은 프로세스가 받아야하는 리소스의 지분을 나타낸다. 

프로세스가 가지고 있는 티켓의 비율만큼 프로세스는 리소스를 할당받게된다.

예를 들어 A와 B 두 프로세스가 있을 때, A는 75장의 티켓을 갖고있고 B는 25장의 티켓을 갖고있다면 A는 75%만큼 CPU를 할당받을 것이고 B는 25%만큼 CPU를 할당받을 것이다.

Lottery scheduling

Lottery scheduling은 말 그대로 복권처럼 랜덤으로 뽑아서 당첨시키는 방식으로 프로세스를 스케줄링하는 방식이다.

스케줄러는 전체 티켓 중 랜덤으로 티켓을 하나 뽑고, 해당 티켓을 보유하고 있는 프로세스를 스케줄링한다.

각 프로세스는 자신이 소유하고있는 티켓의 범위를 갖고있고, 이 범위 안의 숫자가 뽑히면 스케줄링된다.

더 많은 티켓, 즉 더 넓은 범위의 티켓을 갖고있는 프로세스는 더 당첨될 확률이 높을 것이기 때문에, 이를 반복하다보면 결국은 각 프로세스가 요구한 CPU 지분만큼 CPU time이 배분된다.

이 방식은 길게 동작하는 프로세스에 대해서는 좋은 방법이지만, undeterministic하기 때문에 짧은 프로세스에서는 unfair할 수 있다.

Stride scheduling

위의 Lottery scheduling은 사실상 랜덤에 의존하는 것이기 때문에 undeterministic하다는 문제점이 있었다. 이번에 다룰 Stride scheduling은 deterministic한 Proportional share 스케줄링 방식이다.

 

우선 전체 티켓의 개수가 정해져있고, 각 프로세스의 Stride는 다음과 같이 정의된다.

• Stride = 총 티켓의 개수 / 프로세스가 발급받은 티켓의 개수

따라서 전체 티켓이 10000개이고, 프로세스 A가 100개의 티켓을 발급받으면 A의 stride는 100, 프로세스 B가 50개의 티켓을 발급받으면 B의 stride는 200이다.

각 프로세스는 자신이 얼마나 진행해왔는지를 나타내는 값인 counter (pass value 라고도 함)를 유지하고, 스케줄링되어 실행될 때마다 자신의 pass value에 stride를 더한다.

그리고 스케줄러는 가장 작은 pass value를 갖는 프로세스를 스케줄링한다. 

 

Stride scheduling의 의미를 이해해보면 다음과 같다.

Stride는 보폭이라는 뜻이다. stride는 전체 티켓을 자신의 티켓으로 나누므로, 티켓을 적게 가지고 있을수록 stride, 즉 보폭은 커진다. 

스케줄링을 받을 때마다 pass value에 보폭을 더해나가고, 가장 작은 pass value를 갖는 프로세스가 스케줄링되므로 모든 프로세스의 pass value는 비슷하게 유지된다. 

그러면 똑같은 pass value에 도달하기 위해 보폭이 크면 더 적은 수의 걸음을 가도 되므로 더 적은 CPU share를 할당받게되고, 보폭이 작으면 같은 거리를 가더라도 더 많은 수의 걸음을 가야하므로 더 많은 CPU share를 할당받게된다. 

이는 결국 처음에 프로세스들이 요구한 CPU 점유율에 따라 나눠가진 티켓 비율에 맞게 할당되는 것과 같다. 

이를 간단한 수도코드로 나타내면 다음과 같다.

current_process = remove_min(queue); // 최소 pass value를 갖는 프로세스를 골라
schedule(current_process); // 스케줄링한다.
current_process->pass_value += current_process->stride; // stride만큼을 pass value에 더해준다.
insert(queue, current); // 다시 프로세스 큐 (priority queue)에 프로세스를 넣는다.

이때 사용되는 queue는 min heap 등을 사용하여 pass value에 따라 정렬해두어 구현할 수 있다.

그리고 새롭게 들어오는 job의 pass value를 0으로 설정하면, 해당 job이 CPU를 독점하는 상황이 발생할 수 있으므로, 현재 프로세스들의 pass value 중 최솟값으로 초깃값을 설정하는 방식으로 해결할 수 있다.

Example

위와 같이 각 프로세스들이 자신이 요구한 점유율에 맞게 CPU를 할당받는 것을 볼 수 있다. 

(빨간색 프로세스가 3번 CPU를 점유할 때 파란색은 2번 점유하고 노란색은 1번 점유하게됨)