[OS] 추첨 스케줄링 (비례배분)

이번에는 비례배분 스케줄링에 대해 공부하였다.

 

비례 배분의 개념은 간단한데, 반환 시간이나 응답 시간을 최적화하는 대신 스케줄러가 각 작업에게 CPU의 일정 비율을 보장하는 것이 목적이다.

 

비례 배분 스케줄링의 좋은 예가 추첨 스케줄링으로 알려져있다.

이 스케줄링의 간단한 아이디어는 다음 실행될 프로세스를 추첨을 통해 결정하고, 더 자주 수행되야하는 프로세스에게 당첨기회를 더 많이 주는 것이다.

 

여기서의 핵심 질문은, 어떻게 CPU를 정해진 비율로 배분할 수 있는가? 와 그렇게 하기 위한 중요한 기법은 무엇인가? 이다.

 

기본 개념

추첨권이라는 기본적 개념이 추첨 스케줄링의 근간을 이룬다. 

추첨권은 받아야할 자원의 몫을 나타내는데 사용되며, 프로세스가 소유한 티켓의 개수와 전체 티켓의 비율이 자신의 몫이 될 것이다.

 

예를 들어, 프로세스 A는 75장의 추첨권을, 프로세스 B는 25장의 가지고있다

-> 이말은 A에게 75%, B에게 남은 25%의 CPU를 할당하는 것이 목적이다.

 

추첨권은 0~99의 숫자이다. 뽑힌 추첨권 값에 따라 실행할 프로세스가 결정되고, 스케줄러는 당첨된 프로세스를 실행한다.

A는 0~74, B는 75~99번 추첨권을 가지고있다고 해보자.

 

만약 프로세스가

63 85 70 39 76 17 29 41 36 39 10 99 68 83 63 62 43 0 49 49 이렇게 추첨을 했다고 해보면

너무나도 당연하지만 무작위성이기 때문에 한번 추첨한다고 우리가 원했던 비율을 보장할 수 없다.

하지만 당연하게도 두 작업이 장시간 진행되면, 원하는 비율에 근접할 것이다.

 

추첨 기법

추첨권을 다루는 다양한 기법이 있지만, 그중 한 가지 기법은 추첨권 화폐 개념이다.

이 개념은 사용자가 추첨권을 자신의 화폐 가치로 자유롭게 할당할 수 있도록 허용하며, 시스템은 자동적으로 화폐 가치를 변환한다.

예를들어 사용자 A와 B가 각각 추첨권 100장을 받았다고 가정하자.

사용자 A는 A1과 A2 두 개의 작업을 실행중이고 자신이 정한 화폐로 각각 500장씩 할당하였고,

사용자 B는 하나의 작업을 실행중이며 자신 기준 화폐로 10장 중 10장을 할당하였다.

 

이래도 어차피 시스템은 A의 500장을 50장으로 변환하고, B의 10장을 100장으로 변환하여 전역 추첨권 화폐랑(처음 나눠준) 기준으로 추첨을 한다.

 

다른 유용한 기법은 추첨권 양도이다. 프로세스는 일시적으로 다른 프로세스에게 추첨권을 넘겨줄 수 있고, 이 기능은 클라이언트/서버 환경에서 유용하다. 예를 들어 클라이언트 프로세스가 서버에게 메시지를 보내 자신을 대신해 특정 작업을 해달라고 요청할 때 서버에게 추첨권을 전달하여 작업을 빨리 완료시키고 다시 추첨권을 돌려받는다.

 

마지막으로, 추첨권 팽창이다. 이 기법은 프로세스가 일시적으로 자신의 추첨권 수를 늘리거나 줄일 수 있으므로, 프로세스들이 서로 신뢰할 때 유용하다. 어떤 프로세스가 더 많은 CPU시간이 필요하면 시스템에게 이를 알림으로써 혼자 추첨권의 가치를 상향 조정한다.

 

구현

추첨 스케줄링의 가장 큰 장점은 구현이 단순하다는 점이다.

필요한 것은 난수 발생기, 프로세스들의 집합을 표현하는 자료구조, 추첨권 개수 뿐이다.

 

스케줄링을 위해서 먼저 총 추첨권의 개수에서 한 숫자를 선택해아한다.

만약 300이 선택되었다고 하면 리스트(프로세스 자료구조)를 순회하며 당첨자를 찾아낸다.

위 그림을 보면, A B C 순으로 순회를 하는데 거쳐가는 각 티켓 값들을 더해가며 당첨값과 비교해 C가 300의 당첨자임을 알 수 있다.

 

일반적으로 리스트를 내림차순으로 정렬하면 이 과정이 가장 효율적이다. 리스트를 정렬 시 검색 횟수가 최소화되는 것을 보장하기 때문.

 

불공정 지표

간단한 예제를 통해 불공정 지표에 대해 알아보자.

만약 두 프로세스가 같은 개수의 추첨권을 갖고 있고, 따라서 동일한 실행 시간을 가지고 있다고 가정해본다.

우리는 두 작업을 거의 동시에(공정하게) 종료시키고자 하고, 그래야 맞지만 추첨 스케줄링의 무작위성은 이를 허용하지 않는다.

 

따라서 이 종료시간의 차이를 정량화하기 위해 불공정 지표 U를 정의한다.

이 U값은 첫 번째 작업이 종료된 시간을 두 번째 작업이 종료된 시간으로 나눈 값인데, 당연히 작업 기간이 길지 않다면 이 불공정의 정도가 클 것이다. 이 U값을 통해 추첨 스케줄러는 원하는 결과를 얻기 위해 충분한 기간동안 작업을 실행해야한다는 것을 볼 수 있다.

 

 

추첨권 배분 방식

그러면 어떤 방식으로 추첨권을 작업에 분배할까?

시스템 동작은 추첨권 할당 방식에 따라 크게 달라지기 때문에 이는 중요한 문제이다.

가장 간단한 접근 방식은 사용자에게 배분을 맡기는 것인데, 이는 해결책으로 볼 수 없다. 추첨권 할당 문제 는 여전히 미해결 상태이다.