[OSTEP] CPU 가상화 : 비례 배분 스케줄러

1. 비례 배분의 개념

비례 배분(Proportional Share)란 용어 그대로 스케줄러가 각 작업에게 CPU를 비례하여 배분하는 것이다. 반환 시간이나 응답 시간을 최적화하는 대신 공정하게 배분하는 것이 목적이기 때문에 공정 배분(fair share)이라고도 한다.

 

비례 배분 스케줄러에서 캐치해야 할 핵심 질문은 '어떻게 CPU를 특정 비율로 배분할 수 있는가'이다. 

2. 추첨 스케줄링

(1) 기본 개념

추첨 스케줄링(lottery scheduling)은 다음 실행될 프로세스를 추첨을 통해 결정한다. 그리고 프로세스가 받아야 할 자원의 몫을 '추첨권'이라는 개념을 통해 나타낸다. 즉, 많은 추첨권을 갖고 있는 프로세스는 더 많은 당첨 기회를 얻게 되는 것이다. 

 

추첨 스케줄링의 가장 큰 특징은 무작위성이다. 당연히 무작위성은 원하는 비율을 정확하게 보장하지는 않는다. 그럼에도 무작위성은 전통적인 결정 방식에 비하여 다음과 같은 장점을 갖는다.

• 무작위 방식은 전통적인 방식이 잘 해결하지 못하는 특이 사항을 잘 대응한다
• 무작위 추첨 방식은 관리해야 할 상태 정보가 거의 없어 매우 가볍다
• 무작위 추첨 방식은 매우 빠르다

추첨 스케줄링의 가장 큰 장점은 구현이 단순하다는 것이다. 난수 발생기, 프로세스 집합을 표현하는 자료 구조, 추첨권의 전체 개수만 있으면 된다. 다음 구현 코드를 이해해보자.

여기서 잘 생각해보면 리스트를 내림차순으로 정렬시켰을 때 위 과정이 가장 효율적이 됨을 알 수 있다.

(2) 추첨권을 다루는 기법

• 추첨권 화폐 : 사용자가 추첨권을 자신의 화폐 기준으로 각 작업에 자유롭게 할당할 수 있다는 개념이다. 시스템은 자동적으로 사용자 화폐를 글로벌 화폐로 변환한다.
• 추첨권 양도 : 프로세스는 추첨권 양도를 통해 일시적으로 다른 프로세스에게 추첨권을 넘겨줄 수 있다. 예를 들어 특정 프로세스가 대기 중이면 자신의 추첨권을 다른 프로세스가 사용할 수 있도록 양도하여 자원의 활용도를 높일 수 있다.
• 추첨권 팽창 : 특정 프로세스가 일시적으로 자신 소유의 추첨권 수를 늘이거나 줄이는 것이다. 프로세스들이 경쟁하는 상황이 아닌 상호 신뢰하는 상황에서 유용한데, 예를 들어 장기간 대기하는 프로세스가 CPU를 더 자주 사용할 수 있도록 하여 공정성을 높일 수 있다.

(3) 추첨권 배분 방식

추첨권은 프로세스들에게 어떻게 나누어 주어야 할까? 사용자가 가장 잘 알고 있다는 가정 하에 사용자에게 추첨권을 나누어 준 후 알아서 실행시키고자 하는 작업들에게 배분하는 방식을 상정해 볼 수 있다. 그러나 이는 어떤 일을 해야 하는지 제시하고 있지 않아 다른 방식을 생각해 볼 필요가 있을 것이다.

3. 결정론적 방법 - 보폭 스케줄링

추첨 스케줄링은 프로세스들이 장시간 실행될수록 원하는 비율을 달성할 확률이 높아진다. 반대로 말하면 짧은 기간만 실행되는 경우에는 정확한 비율을 보장하기가 더욱 힘들게 된다. 여기서 보폭 스케줄링이 등장한다.

 

보폭 스케줄링(stride scheduling)은 보폭과 pass값으로 어느 프로세스를 실행시킬지 결정한다. 구체적으로는 가장 작은 pass값을 가진 프로세스를 선택하고, 다만 이 pass 값은 프로세스를 실행시킬때 마다 보폭만큼씩 증가시키는 과정을 거치게 된다.  여기서 보폭은 추첨권 수에 반비례 하는 값이다. 즉, 많은 추첨권을 갖고 있으면 보폭이 작아져 pass값의 갱신이 작은 양만큼 이루어진다. 결국 보폭 스케줄링은 정해진 비율에 따라 CPU를 배분할 수 있다.

 

다만 보폭 스케줄링은 상태 정보를 갖고 있어야 한다는 점을 기억하자. 추첨 스케줄링은 정확한 비율을 보장하기는 힘들지만 상태 정보가 필요없어 새 프로세스를 추가하는 경우 등에서 골치아픈 계산을 할 필요가 없어진다.