[OSTEP-9] Lottery Scheduling

개요

• 비례 배분 스케줄러 혹은 공정 배분 스케줄러는 각 작업에 대해 CPU 의 일정 비율을 보장하는 것이 목적임
• 비례 배분 스케줄링의 좋은 예가 Lottery Scheduling(추첨 스케줄링) 이며 다음 실행될 프로세스를 추첨을 통해 결정함

 

특정 비율로 CPU 를 배분하는 스케줄러를 어떻게 설계할 수 있는가? 그렇게 하기 위해서 중요한 기법은 무엇인가

기본 개념: 추첨권이 당신의 몫을 나타낸다.

• 추첨권이라는 기본적인 개념이 추첨 스케줄링의 근간을 이룸
• 추첨권은 프로세스가 받아야 할 자원의 몫을 나타내는데 사용됨

추첨권 스케줄링의 큰 장점 중 하나는 무작위성임. 결정이 필요할 때, 이러한 무작위 방식은 강력하고 쉬운 방식임

1. LRU는 좋은 교체 알고리즘이지만 반복되는 순차적인 접근 패턴을 보이는 오버헤드에 대해서는 최악의 성능을 보임. 반면 무작위 방식에서는 그러한 최악의 경우가 발생하지 않음

2. 관리해야 할 상태정보가 거의 없기 때문에 매우 가벼움. 전통적인 공정 배분 스케줄링 알고리즘에서는 각 프로세스가 사용한 CPU 양을 기록해야 함. 이 정보는 각 프로세스를 실행시킬 때마다 갱신됨, 반면 무작위 추천 방식에서는 프로세스의 상태 정보만 필요함

3. 무작위 추첨 방식은 매우 빠름. 난수 발생 시간이 빠르기만 하면 결정 역시 빠르게 되고, 속도가 요구되는 많은 경우에 사용 될 수 있음

추첨 기법

• 추첨권 화폐의 개념은 사용자가 추첨권을 자신의 화폐 가치로 추첨권을 자유롭게 할당 할 수 있도록 허용함
  • 시스템은 자동적으로 화폐가치를 변환함
• 추첨권 양도를 통해 프로세스는 추첨권을 다른 프로세스에 넘겨 줄 수 있음, 이 기능은 클라이언트/서버 환경에서 특히 유용하게 사용이 됨. 클라이언트 프로세스는 서버에 메세지를 보내 자신을 대신해 특정 작업을 해달라고 요청함. 작업이 빨리 완료될 수 있도록 클라이언트는 서버에게 추첨권을 전달
• 추첨권 팽창을 통해 프로세스는 일시적으로 자신이 소유한 추첨권의 수를 늘리거나 줄일 수 있음. 서로 신뢰하는 프로세스들이 상호 경쟁하는 시나리오에서는 의미가 없음.

구현

추첨 스케줄링의 가장 큰 장점은 구현이 단순하단것임. 난수 발생기, 프로세스들의 집합을 표현하는 자료구조. 추첨권의 전체 개수 뿐. 리스트를 사용하여 프로세스를 관리한다고 가정하고 A,B 및 C 세 개의 프로세스로 구성되고 각자 몇 장의 추첨권을 가졌을 때

int counter = 0;
int winnder = getrandom(0, totaltickets);

node_t * current = head

while(current) {
  counter = counter + current->ticket;
  if(counter > winner)
    break;
  current = current -> next;
}

예제

• CPU를 공유하는 두개의 작업의 수행 시간을 살펴보자, 각 프로세스는 같은 개수의 추첨권(100) 을 가지고있으며, 동일한 실행 시간을 갖는다.
• 추첨 스케줄링의 무작위성 때문에 한 작업이 다른 작업보다 먼저 종료될 수 있음. 이 차이를 정량화하기 위해 불공정지표 U 를 정의함

 

• U 는 첫번째 작업이 종료된 시간을 두 번째 작업이 종료된 시간으로 나눈 값.
  • 예를들어 첫번째 작업이 10 에 종료되고 두번째 작업은 20에서 종료되었을 때 U = 10/20 (0.5)임
• 그래프를 보면 작업의 길이가 짧아질 수록 불공정도는 심해지는 것을 볼 수 있음

왜 결정론적 (Determinisitic) 방법을 사용하지 않는가

• 무작위성을 이용하면 스케줄러를 단순하게 만들 수 있지만. 정확한 비율을 보장할 수 없음. 짧은 기간만 실행되는 경우는 더 그럼. 이를 해결하려고 보폭 스케줄링 방법이 나옴

보폭 스케줄링

• 시스템의 각 작업은 보폭을 가지고 있음. 보폭은 자신이 가지고 있는 추첨권 수에 반비례하는 값임
• 이 값을 통해서 우선순위를 조정할 수 있으며 추첨권의 개수와 정확히 비례한 실행 시간을 보장할 수 있음

그럼 왜 추첨 스케줄링 방식을 사용함?

• 추첨 스케줄링은 상태정ㅂ가 필요없음. 위 보폭 스케줄링의 예에서 스케줄링 중간에 새로운 작업이 시스템에 도착했다고 상상해보자. 그럼 pass 값은 0이 되야할까?

요약

• 둘다 개념적으로 흥미롭지만 여러 이유로 CPU 스케줄러로서 널리 사용되고 있지않다
• 한 가지 이유는 이러한 접근 방식이 입출력과 맞물렸을 때. 제대로 동작하지 않는다는 것.
• 비례 배분 스케줄러는 추첨권 할당량을 비교적 정확하게 결정할 수 있는 환경에서 유용하게 사용됨.
  • 가상화 데이터 센터에서 Window 가상머신에 CPU 사이클의 1/4를 할당하고 나머지는 Linux 시스템에 할당하고 싶은 경우 비례 배분이 간단하고 효과적임