Proportional Share : 로터리 스케줄링, 스트라이드 스케줄링

비례 지분

 

자기 몫이 있고 몫에 맞도록 스케줄링하는 방법

CPU 타임 중 어느 비율만큼 가지는지 관심을 가집니다.

클라우드 시스템 같은 분야에서 관심이 있는 분야입니다.

 

- 로터리 스케줄링 (Lottery Scheduling) -

각각의 잡이 티켓을 가지고, 그만큼 스케줄링 찬스가 많습니다.

난수를 생성하고 범위에 해당하는 티켓을 가진 잡이 스케줄링 됩니다.

예를 들어 잡 A가 75, B가 25만큼 가지고 있을 때 난수가 81이 생성되면 B가 실행될 것입니다.

 

초반에는 목표 지분과 다를 수 있으나 결국 원하는 비율이 맞춰집니다.

 

티켓 커런시

각 유저에게 자기 잡에게 로컬 커런시 할당은 자유롭게 할 수 있도록 하되,

각각의 글로벌 밸류는 비율에 맞게 존재한다

예를 들어 유저 A는 티켓 100장을 가지고 잡 A1에게 500장, A2에게 500장 할당이 가능.(로컬 커런시)

그러나 각각 글로벌 커런시로는 50장 50장

 

티켓 트랜스퍼

잡이 다른 잡에게 티켓 양보 가능

클라이언트, 서버 환경에서 유용. 클라이언트가 작업을 위해 서버에게 티켓을 양보

 

티켓 인플레이션

순간적으로 티켓을 끌어올릴 수 있음

 

장점:

간단함 - 랜덤, 카운터, 티켓 (카운터에 티켓을 더하고 카운터가 랜덤 숫자보다 크면 승리)

공정함 - Unfairness analysis 결과 잡의 길이가 길어질수록 끝나는 시간의 비율이 1에 가까워짐

 

단, Not determinisitc, 결정적이지 않아서 순서가 매번 달라짐 (난수에 의존)

 

- 스트라이드 스케줄링 (Stride Scheduling) -

deterministic fare share scheduler

스트라이드 / 패스 밸류 두가지 변수 사용

패스 밸류는 가상적인 수행 시간

스트라이드는 티켓들의 공배수를 티켓으로 나눈 값, 잡마다 다름

 

한 번 실행되면 패스 밸류가 스트라이드만큼 증가

스케줄러는 패스 밸류가 가장 적은 작업을 선택

-> 티켓이 많을수록 스트라이드 값이 작고, 패스 밸류가 작게 증가해서 많이 할당됨