9. Scheduling : Proportional Share

Proportional Share(or fair-share) scheduling : 반환 시간이나 응답 시간을 고려하는 대신에, 각각의 프로세스가 일정 비율의 CPU타임을 할당받을 수 있게 보장하는 스케줄링

 

9.1 Basic Concept: Tickets Represent Your Share

 - 각각의 프로세스가 가진 티켓의 비율만큼 CPU타임을 할당받게 됨

 - 스케줄러가 총 티켓 수를 알고 있다는 가정이 필요

---

 <예시>

 프로세스 A가 가진 티켓 : 0번부터 74번 / 프로세스 B가 가진 티켓 : 75번부터 99번 ==> (75% : 25%)

출처 : Operating Systems_Three Easy Pieces

 randomness에 의존 --> 따라서, 프로세스들의 작업 시간이 길어질수록, CPU타임 할당 비율은 각 프로세스가 가진 티켓의 비율에 근접해짐

---

9.2 Ticket Mechanisms

 - ticket currency

  <예시>

---

출처 : Operating Systems_Three Easy Pieces

---

  : 즉, 각 프로세스가 가진 전체 티켓을 고려하여 global currency를 맞춰 줌

 

 - ticket transfer

  : 주로 클라이언트-서버 구조에서, 클라이언트가 서버에 요청을 할 때 티켓을 전달함으로써 해당 요청이 빠르게 수행되게끔 함

 

 - ticket inflation

 

9.3 Implementation

출처 : Operating Systems_Three Easy Pieces

 - 다음과 같은 세 작업이 존재

 - winner로 뽑을 숫자를 랜덤으로 pick한 후, counter 값이 winner 값보다 커질 때까지 갱신

 - 예 : 300이 랜덤으로 픽됨 --> counter 값은 맨 첨에 A의 토탈 티켓 값을 더해 줌(counter==100) --> winner 값인 300보다 작으므로 counter값 갱신 --> B의 토탈 티켓 값인 50 더해 줌(counter==150) --> 아직도 winner보다 작으므로 counter 값 갱신 --> C의 값인 250 더해 줌 --> winner 값보다 counter가 커지게 됨 --> break;하고 C를 수행해 줌

 

9.6 Why Not Deterministic?

 - 단점 : ticket 매커니즘은 randomness에 의존하므로 언제나 각 작업이 가진 티켓의 비율과 각 작업이 할당받는 CPU 타임의 비율이 같다는 보장이 없다.

 - 그래서 고안된 것이 stride scheduling이다.

 - 각 작업이 가진 티켓 비율에 반비례하는 값을 stride로 설정하고, pass value를 갱신해 나가며 pass value가 가장 작은 작업 수행

 - 예 : 위 그림의 A, B, C작업이 가진 티켓의 개수를 10000에다가 나눠 줌(A : 100, B : 200, C : 40) --> pass value의 초기값은 0 --> A의 pass value는 100씩 더해지고, B는 200씩, C는 40씩 더해지는데, 이 때 pass value가 가장 낮은 작업을 선택하고 CPU를 할당해준 후, pass value를 갱신해 나가는 방식

출처 : Operating Systems_Three Easy Pieces

 - 장점 : 이 방식은 lottery 스케줄링의 randomness 문제를 해결해 줌

 - 단점 : 중간에 새로운 작업이 들어오면 pass value가 가장 작을 수밖에 없고, 그 작업이 CPU를 독점하게 됨

 

 

-출처-

<OPERATING SYSTEMS three easy pieces>

 

REMZI H. ARPACI-DUSSEAU

ANDREA C. ARPACI-DUSSEAU

UNIVERSITY OF WISCONSIN-MADISON