Proportional Share Scheduling

• Tickets
  • Ticket 수에 비례해서 CPU 권한을 분배한다.
  • Ticket이 많을수록 CPU 권한을 얻을 확률이 높다.

Fairness

• Fairness란, CPU 권한을 똑같이 분배하는 것이 아니라 Starvation을 줄이는 것이다.
  ⠀⠀
• $U$ : Unfairness Metric

⠀⠀ ⠀⠀ $U = \frac{First⠀Job⠀Complete⠀Time}{Second⠀Job⠀Complete⠀Time}$

⠀⠀ ⠀$U$가 1에 가까울수록 Fairness

• Example
  작업 A, B 모두 10초의 Runtime을 가지고, A → B 순서로 수행되어 A는 10초, B는 20초에 종료된다.

  $U = \frac{10}{20} = 0.5$

Lottery Scheduling

• CPU의 권한을 놓고 경쟁하는 모든 Ticket 세트에서 무작위로 선택한다.

Features

• 이 방식의 Scheduling은 확률적으로 공평하다.
• 각 Ticket은 선택될 확률이 동일하다.
• 작업에 대한 예상 리소스 할당은 작업이 보유한 티켓 수에 비례한다.
• Starvation을 예방하기 위해 모든 작업은 하나 이상의 Ticket을 가진다.
• 실제 할당 비율이 예상 비율과 정확히 일치한다고 보장할 수는 없다.

Key Mechanism of Lottery Scheduling

위의 그림과 같은 형태로 뽑은 Ticket에 해당하는 작업을 찾는다. 하지만 Ticket의 개수가 많은 것부터 순서대로 나열되어 있을 경우에 Winner를 찾는 속도가 더 빠를 것이다.

• Example
  작업 A, B는 모두 100개의 Ticket을 가지며, 둘 다 R의 Runtime이 소요된다.

Pros and Cons of Lottery Scheduling

Pros

• 간단하고 구현이 간편하다.
• 행동을 쉽게 이해할 수 있다.
• 중간에 프로세스가 추가되는 경우 (Dynamic Operation)도 처리 가능하다.

Cons

• 확률을 보장해줄 수 없다.
• 짧은 작업은 정확도가 낮다.
• Response Time 가변성이 높다.

Stride Scheduling

• Stride = 임의의 큰 수 / 프로세스의 Ticket 수
  ⠀⠀
• Pass = Stride의 증가량
  가장 Pass 값이 작은 프로세스가 실행되고, 실행된 프로세스의 Pass값은 해당 프로세스의 Stride만큼 증가한다. 이 과정을 반복해준다.
  ⠀⠀
• Example

결과를 계산해보면 초기의 비율
A : B : C = 100 : 50 : 250 = 2 : 1 : 5
와 같음을 알 수 있다.

규칙에 따라 증가하므로 Deterministic Fair

Pros and Cons of Stride Scheduling

Pros

• 확률이 보장된다.
• 짧은 작업의 정확도도 높다.
• Response Time 가변성이 낮다.

Cons

• 중간에 프로세스가 추가되는 경우 (Dynamic Operation) 처리가 어렵다.
  → Resource Monopoly Problem
• 변수가 많아 메모리를 많이 필요로 한다.

Monopoly Problem

세 가지 작업의 Pass가 20,000인 상황에서 새로운 작업 D가 새로 실행되는 경우 (Dynamic Operation)