복권 스케줄링

Lottery scheduling

복권 스케줄링은 운영체제의 프로세스를 위한 확률론적 스케줄링 알고리즘이다.프로세스에는 각각 복권 몇 장이 할당되며, 스케줄러는 다음 프로세스를 선택하기 위해 무작위 복권을 추첨한다.티켓의 배포가 균일할 필요는 없다; 절차를 더 많이 부여하면 상대적으로 더 높은 선택 기회를 제공한다.이 기법은 다음으로 최단 작업 및 공정 공유 스케줄링과 같은 다른 스케줄링 알고리즘에 근사치를 적용할 수 있다.

복권 스케줄링은 기아 문제를 해결한다.각 공정마다 최소 1장의 복권을 주는 것은 스케줄링 운영 시 선정될 확률을 0이 아닌 것으로 보장한다.

실행

복권 스케줄링 구현은 큰 실 풀 사이에 수십억 장의 복권이 배포될 수 있다는 점을 고려해야 한다.각 인덱스가 티켓을 나타내고 각 위치에 해당 티켓에 해당하는 스레드가 포함된 배열을 갖는 것은 매우 비효율적일 수 있다.복권 예약은 선제적이거나 비선호적일 수 있다.

외부 링크