스케줄링 : 비례 배분

비례 배분 혹은 공정 배분이라고도 하는 유형의 스케줄러가 존재한다.

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

**추첨권(티켓)**이라는 개념을 통해서 추첨 스케줄링을 구현한다.

추첨권은 프로세스(혹은 사용자)가 받아야 할 자원의 몫을 나타내는 데 사용된다.

프로세스가 소유한 티켓의 개수와 전체 티켓에 대한 비율이 자신의 몫을 나타낸다.

e.g. A가 75장, B가 25장이 있다면 A에게 75%의 CPU를 할당한다.

추첨권 스케줄링은 무작위성을 이용한 방법이다.

• 전통적인 방식이 잘 해결하지 못하는 특이 상황을 잘 대응한다.
  • LRU-반복되는 순차적인 접근 패턴을 보이는 오버헤드에 대해서 최악의 성능
  • 무작이 방식에서는 해결됨.
• 관리해야할 정보가 많이 없어 매우 가볍
  • 전통적인 방식은 각 프로세스가 사용한 CPU 양을 기록해야한다.
• 매우 빠르다
  • 단순 난수 발생만 하면 되므로 빠르다.

물론 원하는 비율을 정확하게 보장하지는 않아도, 장시간 실행되었을 때 원하는 비율을 달성할 가능성이 높아진다.

추첨 기법

추첨권을 다루는 다양한 기법이 존재한다.

추첨권 화폐(ticket currency)