Fair Share Scheduling

New goal: fairness

simple: 모든 process에게 똑같은 CPU time 나눠주기
but, MLFQ는 queue의 종류가 여러가지
We have examined schedulers designed to optimize performance

• Minimum response times
• Minimun turnraound times
  MLFQ achives these goals, but it's complicated
• Non-trivial to implement
• Challenging to parameterize and tune
  What about a simple algorithm that achives fairness?**

Lottery Scheduling

Key idea: give each process a bunch of tickes

• Each time slice, scheduler holds a lottery
• Process holding the winning ticket gets to run
  
  Probabilistic scheduling
• Over time, run time for each process converges to the corret value
  • i.e. the # of tickets it holds

Implementation Advantages

Vary fast scheduler execution

• All the scheduler needs to do is run random()
• No need to manage $O(logN)$ priority queeus

No need to store lots of stae

• Scheduler needs to know the total number of tickets
• No need to track process behavior or history

Automatically balances CPU time across processes

• New processes get some tickets, adjust the overall size of the ticket pool

Easy to prioritize processes

• Give high priority processes many tickets
• Give low priority processes a few tickets

Is Lottery scheduling fair?

Does lottery scheduling achieve fairness?

• Assume two processes with eqaul tickets
• Runtime of processes varies
• Unfairness ratio=1 if both processes finish at the same time
  

Stride scheduling

Randomness is lets us build a simple and approximately fair scheduler

• But fairness is not guaranteed
• 임의의 시간은 fair한 게 아니다 -> interval로 fair하게 하자

Why not build a deterministic, fair scheduler?

Stride scheduling

• Each process is given some tickets
• Each process has a strid = a big of tickets
• Each time a process runs, its pass +=stride
• Scheduler chooses process with the lowest pass to run next

Lingering Issues

티켓을 몇장 줄 것인가? -> 사용자에게 일임 or 동일한 숫자 계속 주기

Why choose lottery over stride scheduling?

• Stride schedulers need to store a lot more state
• How does a stride scheduler deal with new processes?
  • Pass = 0, will dominate CPU until it catches up
    • 제일 간단한 방법이지만, 전체 티켓이 변화하면 pass에도 영향

Both schedulers require tickets assignment

• How do you know how many tickets to assign to each process?
• This is an open problem