Proportional Share (fair share)

Proportional Share (fair share)

turnaround time, response time을 고려하지 않고 특정 퍼센트만큼의 CPU 실행시간을 보장해줌

 

Lottery scheduling

티켓이 많은 job이 실행될 확률이 더 높다.

A: 0~74 B: 75~99

랜덤으로 0~99 중에 하나 뽑아서 그 숫자를 갖는 job을 실행

 

ticket currency

A, B가 각각 100 티켓을 가지고 있다.

A의 job은 2개, 각 job에 500의 티켓을 줌

B의 job은 1개, 그 job에 10의 티켓을 줌

500 -> 50

10 -> 100

 

ticket transfer

client 가 server에게 ticket을 줘서 server 작업이 빨리 끝나게 하는 경우

 

ticket inflation

티켓을 뻥튀기하거나 줄여버림

 

benefit

구현이 간단함

 

unfair

같은 job, 같은 ticket, 같은 run time

U = C1/C2

C1: 일찍 끝난 일의 완료 시간

C2: 늦게 끝난 일의 완료 시간

C1=10, C2=20 => U=0.5 (불공평)

C1=20, C2=20 => U=1 (공평)

 

assigning ticket

돈 -> 클라우드 컴퓨팅

우선순위 -> real time system

 

Stride scheduling

stride = ticket의 역수

1. pass value가 작은 작업을 먼저 실행

2. stride만큼 pass value를 증가시킴

 

A, B, C의 티켓이 각각 100, 50, 250이면

stride: 100, 200, 40 (공배수 10000)

위 표에서 실행된 횟수는 A:B:C=2:1:5