9. Scheduling: Proportional Share

 

 

Proportional Share Scheduler == Fair share scheduler 

• trunaround time 이나 response time에 관심 x
• 각각의 process에 가중치 할당이 가능하고, 이 가중치에 비례해서 cpu 타임을 부여함
• 위의 조건이 충족되면, >Fair 하다< 라고 할 수 있음

 

 

Basic Concept - Ticket

• 가중치를 나타내는 방법 중 하나
• ex) process A가 75 tickets을 가지면, 75%의 cpu 를 부여함 
• process B 가 25 tickets을 가지면, 25%의 cpu를 부여함
• A와 B의 가중치는 3 : 1 비율

 

 

Lottery scheduling

• scheduler가 random하게 winning ticket을 하나 고름
• 이후 그 number를 가진 process가 다음에 scheduling 되는 방식 

• A 가 0~74 = 75개 ticket, B가 75~99 = 25개, 0~99 중 하나를 골라 그걸 가진 process를 scheduling 함

=> scheduling decision이 많아야만, 원래 비율(3 : 1)에 가깝게 cpu를 나눠줄 수 있게 된다.

 

 

Lottery scheduling implementation

int counter = 0;  // winner를 가진 process를 찾기 위한 변수

int winner = getrandom(0, totaltickets);  // 랜덤으로 winner 선택

node_t *current = head;

while(current) {
	counter = counter + current -> tickets; // 현재 process의 tickets 수를 더하고
    if(counter > winner) // 만약 counter가 winner보다 크면
    	break; // 그 process가 winner를 가진 process, break
    current = current -> next; // 작으면, 다음 process로 넘어감
}

 

• U = unfairness metric => fair 한 지, 아닌 지를 판단하는 metric
• first job이 끝난 시간 / second job이 끝난 시간 
• 일단 가중치를 제외한 예시를 생각해보자

• first job, second job이 동시 도착(A가 살짝먼저), 실행시간 10s로 동일 할 때, FCFS면 
• U = 10 / 20 = 0.5
• 만약 first job, second job을 RR 방식으로 1s 씩 time slice를 하면
• U = 19 / 20 

=> U가 1에 가까울수록 fair 하다고 할 수 있다.

 

 

Lettery Fairness Study

• process의 length가 짧으면 random 함수를 충분히 수행하지 못해,  unfariness가 낮아진다(U가 1에서 멀어짐)

 

 

Stride Scheduling

• lottery의 단점을 보완함 
• 임의의 큰 수 / 각 process의 tickets 수 

• 임의의 큰 수를 10000 이라고 했을 때,
• A tickets 100개 => stride_A = 100
• B tickets 50개 => stride_B = 200
• C tickets 250개 => stride_C = 40

# a pseudo code implementation

current = remove_min(queue);
// Ready queue에 있던 job을 빼서 schduler에 넘겨줌
/* stride가 가장 작은 job을 선택 해서 가중치를 맞춰준다.
=> stride가 작다 == 가중치가 높다 => 가중치가 높은 job을 더 많이 선택할 수 있게 함 */

schedule(current); // 위에서 선택한 job을 scheduling

current->pass += current->stride; 
/* pass_value에 stride 값을 계속 누적 시킴
=> job들마다 누적 된 값들을 비교하여 작은 것을 선택 할 수 있게 함*/

insert(queue, current); // 한 번 scheduling 한 job을 다시 Ready queue에 넣어줌

 

• 위의 방식대로 하면, 가중치를 맞출 수는 있으나 중간에 새롭게 생긴 job이 문제가 된다.
• 새로운 job의 pass_value를 0으로 하면, 그 job이 cpu를 독점하는 문제가 생기므로
• 새로운 job의 pass_value를 미리 있던 job들의 pass_value 값 중 가장 작은 것으로 초기화 시켜준다.