이번에는 Proportional-share 또는 fair-share sheduler라고 알려진 scheduler에 대해서 알아볼 것이다.
Proportional-share scheduler는 turnaround time, response time을 최적화하는 것이 아닌 프로세스들의 CPU 사용 시간을 균등하게 배분하는 것을 목적으로 한다.
lottery scheduling으로 잘 알려져 있다.
간단한 예시로 복권에 당첨되고 싶으면 복권을 자주, 여러장 사면 된다는 내용이다.
Basic Concept: Tickets Represent Your Share
lottery scheduling에서 사용되는 ticket이라는 중요한 개념이 있다.
sheduler는 총 ticket의 수를 알고있고, ticket은 프로세스가 가질 수 있는 resource의 몫이다. 그리고 이 각각의 프로세스가 가진 ticket의 비중이 시스템에서의 resource 몫을 나타낸다.
예를들어 75%의 ticket을 가진 A 프로세스와, 25%의 ticket을 가진 B프로세스가 있다고하자.
lottery scheduling은 확률적으로 동작한다.
따라서 A와B를 무작위(Randomness)로 실행할 때 ticket이 더 많은 A가 더 자주 실행되고, B는 그보다 더 적게 실행 될 것이다.
무작위 실행의 장점
- 전통적인 알고리즘이 갖는 corner-case behavior를 피할 수 있다.
- 예를들어 LRU replacement policy에 대해 생각해보자. LRU replacement policy에서는 순환하는 작업에 대해서는 최악의 결과를 내놓는다.
하지만 무작위로 실행하는 경우 이 문제가 없다.
- state를 추적할 필요가 없다.
- 전통적인 알고리즘에서는 진행중인 프로세스를 업데이트할 필요성 때문에 프로세스가 얼마만큼의 CPU를 사용하고 있는지를 추적할 필요가 있다. 하지만 무작위로 실행하는 경우에는 이럴 필요가 없다.
- 무작위 실행은 빠르다.
Ticket Mechanism
lottery scheduling에도 ticket을 다양하고, 효과적으로 활용하기 위한 mechanism들이 존재한다.
그 중 하나는 ticket currency라고 불리는 개념이다.
currency는 프로세스에서 ticket을 발행하는데 사용될 수 있다.
그래서 scheduler가 currency로 사용자에게 ticket을 발행하고, 사용자는 또 다른 currency로 자신의 프로세스에 ticket을 발행할 수 있다. 이렇게 각각의 currency로 발행한 ticket은 global 즉 시스템이 가진 ticket으로 활용된다.
예를들어 2명의 사용자 A와 B에게는 각각 100장과 200장의 티켓이 주어진다. 사용자 A는 2개의 프로세스를 실행 중이며 A의 자체 currency로 각각의 프로세스에 50장의 티켓을 제공합니다. B는 한 가지 프로세스를 진행하고 있으며, 200장의 티켓을 모두 B의 currency로 제공한다. 이제 각 프로세스의 티켓 예약 시 글로벌 통화로 전환된다. 즉, A의 프로세스는 각각 50장의 티켓이 있고 B의 프로세스는 200장의 티켓이 있으며 이를 기반으로 일정이 수행된다.
또다른 mechanism은 ticket transfer라고 불리는 개념이다.
ticket transfer를 통해 프로세스가 다른 프로세스에게 ticket을 양도할 수 있다. 특히 이 방법은 client/server 구조에서 특히 유용하다. client가 요청을 보내면서 ticket도 같이 보내면 server가 요청과 함께 ticket을 받아서 프로세스의 퍼포먼스를 높일 수 있다. 그리고 작업이 완료되면 다시 ticket을 client에게 보내면 된다.
마지막으로 ticket inflation이 있다.
ticket inflation으로 프로세스가 자신이 가진 ticket의 수를 일시적으로 늘리거나, 줄일 수 있다.
ticket inflation은 프로세스 그룹이 서로 신뢰하는 환경에 적용될 수 있다. 어떤 프로세스가 더 많은 CPU 점유 시간이 필요하다는 것을 알게 되면 다른 프로세스와의 통신 없이 시스템에 필요한 사항을 반영하기 위한 방법으로 ticket inflation을 활용할 수 있다.
출처 : OSTEP
