비례 배분(Proportional Share) 스케줄러
- 공정 배분(fair share) 스케줄러라고도 한다.
- 반환 시간이나 응답 시간을 최적화하는 대신 스케줄러가 각 작업에게
CPU의 일정 비율을 보장하는 것이 목적이다.
기본 개념: 추첨권
- 추첨권은 프로세스가 받아야 할 자원의 몫을 나타내는 데 사용된다.
- 프로세스가 소유한 티켓의 개수와 전체 티겟에 대한 비율이 자신의 몫을 나타낸다.
추첨권 스케줄링의 장점
무작위성이 가능하여 특이 상항에 더 잘 대응한다.- 관리해야 할 상태 정보가 거의 없기에 매우 가볍다.
- 난수 발생 시간에 비례하므로 매우 빠르다.
추첨 기법
추첨권 화폐(ticket currency)개념으로 사용자가 추첨권을 자신의 화폐 가치로 자유롭게 할당할 수 있도록 허용한다. 시스템은 자동적으로 화폐 가치를 변환한다.
- A,B가 각 100장의 추첨권, 사용자 A는 A1과 A2 두 개의 작업에 자신이 정한 추첨권 500개를 할당하였다(전체 1000개). 사용자 B는 자신의 기준 화폐 10장 중 10개를 하나의 작업에 실행하였다. 결국 A는 전역 기준 추첨권 50개, B는 100개로 변환되어 추첨된다.
추첨권 양도(ticket transfer)에서 프로세스는 일시적으로 추첨권을 다른 프로세스에게 넘겨줄 수 있다. 클라이언트/서버 환경에서 특히 유용하다.
- 클라이언트는 서버에게 메시지를 보내 자신을 대신해 특정 작업을 해달라고 요청한다. 작업이 빨리 완료될 수 있도록 클라이언트는 서버에게 추첨권을 전달하고 서버가 자신의 요청을 수행하는 동안 서버의 성능은 극대화된다.
추첨권 팽창(ticket infaltion)에서 프로세스는 일시적으로 자신이 소유한 추첨권의 수를 늘이거나 줄일 수 있다. 화폐 팽창 기법은 프로세스들이 욕심이 많은 프로세스가 없고 서로 신뢰할 수 있을 때 유용하다.
구현
int counter = 0; // 당첨자를 발견했는지 추적하는 데 사용
int winner = getrandom(0, totaltickets); // 난수 발생기
node_t *current = head; // 작업목록을 탐색하는 데 사용
while (current)
{
counter = counter + current->tickets
if (counter > winner)
break ; // 당첨자 발견
cureent = current->next;
}
- 리스트를 내림차순으로 정렬해 놓으면 검색 횟수가 최소화되는 것을 보장한다.
추첨권 배분 방식
작업들에게 추첨권을 몇 개씩 분배해야 하는가?
- 시스템 동작이 추첨권 할당 방식에 따라 달라지기에 상당히 어려운 문제이다.
- 잘 알려진 방식은 각 사용자에게 추첨권을 나누어 준 후 사용자가 알아서 실행시키고자 하는 작업들에게 추첨권을 배분하는 방식이다.
- 위의 경우에도 어떤 일을 해야 하는지 전혀 제시하지 못한다. 주어진 작업 집합에 대한 추첨권 할당 문제는 여전히 미해결 상태다.
보폭 스케줄링(stride scheduling)
- 무작위성을 이용하면 스케줄러를 단순하게 만들 수 있지만, 정확한 비율을 보장할 수는 없다.
- 전체 추첨권 갯수를 각자의 추첨 갯수로 나누면 각 작업의 보폭(stride)를 구할 수 있다.
- 프로세스가 실행될 때마다 pass라는 값을 보폭만큼 증가시켜 얼마나 CPU를 사용하였는지 추적하여 각 스케줄링 주기마다 정확한 비율로 CPU를 배분하는 것이다.
current = remove_min // pass 값이 최소인 클라이언트로 선택
schedule(current); // 자원을 타임 퀀텀만큼 선택된 프로세스에게 할당
current->pass += current->stride // 다음 pass 값을 보폭 값을 이용하여 갱신
insert(queue, current); // 다시 큐에 저장한다.
- 새로운 프로세스가 시스템에 도착했을 때 pass값은 얼마가 되어야 하는가? 0으로 된다면 CPU를 독점하게 될것이다.
- 추첨 스케줄링에서는 프로세스 상태(CPU 사용 현황, pass값)을 유지할 필요가 업식에 새 프로세스를 쉽게 추가할 수 있다.
결론
- 추첨권 스케줄링과 보폭 스케줄링은 같은 목적을 결정적 방법으로 달성한다.
- CPU 스케줄러로 널리 사용되고 있지 않은 이유는 이러한 접근 방식이 입출력과 맞물렸을 때, 제대로 동작하지 않는다는 것이다.
- 또 다른 이유는 추첨권 할당이라는 어려운 문제가 미해결 상태로 남아있다.
- 비례 배분 스케줄러는 추첨권 할당량을 비교적 정확하게 결정할 수 있는 환경에서 유용하게 사용된다.
- 가상화 데이터 센터에서 Windows 가상 머신에 CPU 사이클의 1/4를 할당하고 나머지는 Linux 시스템에 할당하고 싶은 경우 비례 배분이 간단하고 효과적이다.
참고자료