Proportional Share 스케줄러

• Fair-share 스캐줄러
  • 각 작업이 특정 CPU time의 퍼센트를 보장받는다.
  • turnaround, response time이 최적화 되어 있지 않다.

기본적인 개념

• Tickets
  • 프로세스가 받아야 할 자원의 양을 의미한다.
  • 티켓의 퍼센트가 시스템 자원의 양도량을 의미한다.
• 예시
  두개의 프로세스 A, B가 존재한다.
  프로세스 A는 75티켓을 가지고 있다 -> CPU의 75%를 할당받음
  프로세스 B는 25티켓을 가지고 있다 -> CPU의 25%를 할당받음

A : (W:3) 100 X 3/4 = 75티켓
B : (W:1) 100 X 1/4 = 25티켓

Lottery scheduling

• 스케줄러는 winning ticket을 고른다.

  • winning 프로세스의 상태를 load하고 수행한다.(매 timer intterupt마다)

• 예시
  티켓이 100장 존재
  프로세스 A는 티켓 75장 가지고 있다. : 0~74
  프로세스 B는 티켓 25장을 가지고 있다. : 75~99

해당 작업 2개가 경쟁을 오래 하면 할수록 요구되는 퍼센테이지 값에 유사해질 것이다.

Ticket Mechanism

• Ticket currency
  • 사용자(비유 : 국가)는 그들이 원하는 통화로 그들의 작업에 티켓을 할당한다.
  • 시스템은 통화를 global value로 변환한다.
• 예시
  200개의 티켓이 존재한다.(global currency)
  프로세스 A는 100개의 티켓이 존재한다.
  프로세스 B는 100개의 티켓이 존재한다.

사용자A -> 500(A의 통화)을 A1으로 -> 50(global currency)
-> 500(A의 통화)을 A2으로 -> 50(global currency)

사용자 B -> 10(B의 통화)를 B1으로 -> 100(global currency)

• Ticket transfer
  • 프로세스는 일시적으로 그 티켓을 다른 프로세스로 양도할 수 있다.(A:1000, A1:600, A2:400)
• Ticket inflation
  • 프로세스는 일시적으로 그것이 가지고 있는 티켓의 수를 증가시키거나 감소시킬 수 있다.
  • 만일 프로세스가 더 많은 CPU time이 필요하다면,티켓을 부스트 할 수 있다.

적용

• ex) A,B,C 3가지 프로세스들이 존재하는데 이 프로세스들을 리스트에 유지하자
  head -> JobA(티켓:100(0~99)) -> JobB(티켓:50(100~149)) -> JobC(티켓:250(150~399))

// winner 찾는 알고리즘

typedef struct node{
	int pid;
    int tickets;
    struct node* next;
}node_t;

int counter = 0 
int winner = getrandom(0, totaltickets);

node_t *current = head;

while(current){
	counter = counter + current->tickets;
    if(counter > winner)
    	break;
    current = current -> next
}

• U: unfairness metric
  • 첫 작업이 완수된 시간 / 두번째 작업이 완수된 시간
• 예시
  두가지 작업이 존재하고 각 작업은 10s의 runtime이 존재한다.
  첫 작업은 10s에 끝나고
  두번째 작업은 20s에 끝난다.

U = 10/20 = 0.5
U는 두 작없이 거의 동시에 끝났을 경우에 1에 가까워진다.(ex) 첫작업이 19.5초에 두번째 작업이 20초에 끝났을 경우 U = 19.5/20 = 0.975)

Lottery Fairness

• 두가지 작업이 존재한다.
  • 각 작업은 같은 수의 티켓(100개)을 가지고 있다.

• 작업의 길이가 그리 길지 않을 때는 평균 불공정성이 꽤 심할것이다.

Stride Scheduling

• 각 프로세스의 보폭(stride)

  • (큰 숫자(ex)10000)) / (프로세스의 티켓 수)

• 예시
  큰 수 : 10000
  프로세스 A는 100개의 티켓을 가지고 있다. -> A의 stride는 10000/100 = 100
  프로세스 B는 50개의 티켓을 가지고 있다. -> B의 stride는 10000/50 = 200
  프로세스 C는 250개의 티켓을 가지고 있다. -> C의 stride는 10000/250 = 40

• 만일 프로세스가 수행된다면, pass value(축적된 stride)의 증가량은 그것의 stride값이다.

//해당 수도코드
current = remove_min(queue);
schedule(current);
current -> pass += current -> stride;
insert(queue, current);

• 예시
  어느 시간에서든지 항상 지금까지 가장 낮은 pass value를 가진것을 선택해라

• 만일 어느 시점에 특정한 작업이 pass value = 0 으로 진입하게 된다면 이것은 CPU를 독점하게 될 것 이다.