FL4G{##st4rbuucks##}

proportional share란? : 모든 작업의 반환시간이나 응답시간을 최적화하는 대신 scheduler가 일정비율의 CPU 사용시간을 보장하는 것이 목적

lottery scheduling

CPU 사용 시간을 비례적으로 제공하기 위해 ticket이라는 개념을 사용한다.

모든 프로세스는 ticket을 나눠 가진다.

예시를 통해 이해해보자.

프로세스 A는 75장의 ticket을 가지고 프로세스 B는 25장의 ticket을 가진다.

scheduler는 0부터 99까지의 수 중 하나를 랜덤하게 고른다.

만약 그 수가 0에서 74사이의 수라면 프로세스 A를 실행시키고 75에서 99사이의 수라면 프로세스 B를 실행시키는 방식이다.

이 방식을 통해 두 프로세스는 보유한 ticket의 수에 비례해 CPU를 사용할 수 있다.

ticket currency의 개념이 있다.

local ticket currency를 global currency로 전환해줄 수 있다. 다음 그림을 보고 이해하자.

User A는 두 프로세스에게 각각 500장의 ticket을 할당했고 User B는 한 프로세스에게 10장의 ticket을 할당했다.

그렇다고 해서 scheduler가 이 세작업을 500 : 500 : 10의 비율로 실행시키는 것이 아니라는 것이다.

User A의 두 프로세스는 global currency 기준으로 50장씩의 ticket을 나눠가지고 User B의 프로세스는 100장의 global currency ticket을 가지게 된다.

이외에도 프로세스가 다른 프로세스에게 ticket을 넘겨줄 수 있는 ticket transfer 기능도 있다. 이 기능은 서로 작업을 번갈아가며 수행하는 경우가 많은 server-client 프로세스 간에 많이 사용된다.

프로세스가 일시적으로 자신이 보유한 ticket의 양을 부풀려버리는 ticket inflation 기능도 있다. 일시적으로 CPU 기능을 많이 필요로 할 때 주로 사용되며 여러 프로세스 간 높은 신뢰가 형성된 상태에서 유용하다. 그렇지 않다면 한 프로세스가 CPU를 독점할 수도 있다.

구현방식은 다음과 같다.

프로세스의 티켓 수를 저장하는 노드가 연결리스트로 연결되어있다고 생각하고 아래의 코드를 살펴보자.

U : unfairness metric

두 작업이 동시에 시작될 때 첫번째 작업이 종료된 시각을 두번째 작업이 종료된 시간으로 나눈 값이다.

이 값이 1에 가까울 수록 공정한 scheduler라고 할 수 있다.

위에서 설명한 방식으로 proportional share를 구현했을때 작업이 충분히 길어야지만 공정한 scheduler의 모습을 보인다는 것을 알 수 있다.

즉, 무작위성을 이용하면 짧은 기간만 실행되는 경우 fairness를 보장할 수 없다.

이를 보완하기 위해 나온 개념이 stride scheduling이다.

stride scheduling

$$stride = big\_value / ticket$$

scheduler는 프로세스가 실행되면 해당 프로세스의 pass 값을 stride만큼 증가시킨다.

pass 값은 모든 프로세스가 0부터 시작하며 time slice가 시작될 때 pass값이 가장 낮은 프로세스가 먼저 실행된다.

(모든 프로세스가 동시에 시스템에 도착했을 때를 가정)