이 장에서는 비례 배분(Proportional Share), 공정 배분(fair share)이라고도 하는 유형의 스케줄러에 대해 다룬다. 비례 배분은 스케줄러가 각 작업에게 정해진 비율로 CPU를 배분하는 것을 보장하는 것이 목적이다.
비례 배분 스케줄리의 예시인 추첨 스케줄링(Lottery Scheduling)을 통해 알아보자
핵심 질문: 어떻게 CPU를 정해진 비율로 배분할 수 있는가?
1. 기본 개념: 추천권이 당신의 몫을 나타낸다.
추첨권(티켓) 이라는 기본적인 개념이 사용된다. A가 75개 B가 25개의 티켓을 가지고 있다고 가정하면, A에게 75%, B에게 25%의 CPU를 할당하는 것이 목적이다.
이 경우 추첨권은 0~99의 숫자를 가진다. A는 0~74, B는 75~99 이다. 추첨 값에 따라 실행할 프로세스가 결정된다.
추첨 형식이기 때문에 원하는 비율을 정확히 보장하지는 않지만, 작업이 길어질수록 원하는 비율에 수렴하게 된다.
2. 추첨 기법
추첨권 화폐(ticket currency)
사용자는 자신만의 화폐가치로 추첨권을 자유롭게 할당하고, 시스템은 자동적으로 화폐 가치를 변환한다.
A, B가 각각 100장의 추첨권을 받았다고 가정 했을 때, A는 작업 A1, A2에게 500장씩 추첨권을 할당하고, B는 작업 B1에게 10장의 추첨권을 할당할 있다. 이때, 시스템에서는 A1, A2는 각각 50장, B1은 100장의 추첨권이라는 전역 추첨권으로 화페가치를 변환한다.
추첨권 양도
양도를 통해 프로세스는 일시적으로 추첨권을 다른 프로세스에게 넘겨줄 수 있다. 주로 클라이언트/서버 환경에서 유용하다. 클라이언트가 서버에게 측정 작업을 요청했을 때, 추첨권을 잠시 넘겨주는 방식이다.
추첨권 팽창
프로세스가 일시적으로 자신의 추첨권 개수를 늘리거나 줄일 수 있다. 한 프로세스가 과하게 추첨권을 팽창할 수 있으니, 프로세스들이 서로 신뢰할 때 유용하다. 이 경우, 프로세스가 CPU 시간을 더 많이 필요하다면 다른 프로세스와의 통신 없이 혼자서 추첨권 개수를 늘릴 수 있다,
3. 구현
추첨 스케줄링의 가장 큰 장점은 구현이 단순하다는 것이다.
A는 0~99, B는 100~149, C는 150~399의 티켓을 할당 받는다.. winner에 난수 300이 할당되었다고 하자. 리스트를 앞에서부터 순회하면서 counter의 값을 증가시킨다. A에서는 100, B에서는 150이 된다. C에서는 400이 된다. C에서 counter 값이 난수 300보다 커지므로 C가 당첨자가 된다.
리스트를 내림차순으로 정렬한다면, 검색 횟수를 최적화할 수 있을 것이다.
4. 예제
같은 개수의 티켓을 보유하고 있고, 동일한 실행 시간을 가지는 프로세스 두 개의 수행 시간을 살펴보자. 두 프로세스를 거의 동시에 종료시키는 것이 목표다.
불공정 지표 (U)
불공정 지표는 첫 번째 작업이 종료된 시간을 두 번째 작업이 종료된 시간으로 나눈 값이다. 1에 가까울수록 종료된 시간이 비슷한 공정 스케줄러라고 할 수 있다.
작업 시간이 짧을 때는 스케줄링의 무작위성 때문에 끝난 시간에 차이가 있지만, 작업의 길이가 길어질수록 추첨 스케줄러의 목적에 가까워진다.
5. 추첨권 배분 방식
추첨권을 작업에게 얼만큼씩 분배해야할까? 추첨권 할당 방식에 따라 시스템의 동작이 크게 달라지기 때문에 어려운 문제이다. 각 사용자가 작업에 대해 아주 잘 안다고 가정하면 추첨권 배분을 사용자에게 위임할 수는 있지만, 근본적인 해결책은 아니다.
6. 왜 결정론적 방법을 사용하지 않는가
무작위성 기반의 스케줄링은 정확한 비율을 보장할 수 없는데, 작업 기간이 짧을 수록 더욱 그렇다. 이에 결정론적 공정 배분 스케줄러인 보폭 스케줄러(stride scheduling)이 고안되었다.
작업 A, B, C가 각각 100, 50, 250의 추첨권을 가지고 있다고 가정하면, 각각의 보폭(stride)는 임의의 큰 값을 추첨권 수를 나눈 값을 가진다(100, 200, 40). 임의의 순서대로 수행될 때마다 각각의 보폭으로 나아간다. 그 이후 가장 덜 나아간 작업중에 선택하는 과정을 반복한다.
분배 횟수를 보면, 추첨권의 개수와 정확히 비례한다. 보폭 스케줄링은 각 스케줄링 주기마다 정확한 비율로 CPU를 배분한다. 그렇다면 추첨 스케줄링을 쓸 이유가 없지 않은가?
보폭 스케줄링 과정 중간에 새로운 작업이 들어왔다고 가정하면, pass값을 몇으로 설정해야 할까? 0이라면 해당 작업이 CPU를 독점하게 될것이다. 그러나 추첨 스케줄링에서는 프로세스의 상태(pass 값)이 필요없다. 이처럼 새로운 프로세스 추가에 유리하다.
7. 요약
추첨 스케줄러와 보폭 스케줄러 모두 CPU 스케줄러로서 널리 사용되지는 않는다. 추첨권 할당 문제도 있고 입출력과 맞물렸을 때, 제대로 동작하지 않는다.
비례 배분 스케줄러는 추첨권 할당량을 비교적 정확하게 결정할 수 있는 환경에서 유용하다. 예를 들어 가상화 데이터 센터에서 Window 가상머신에 CPU 사이클의 25%를 할당하고 나머지는 Linux 시스템에 할당하고 싶을 대 효과적이다.
