Skip to content

Lottery Scheduling

Context

  • Try to use economic concepts to resource allocation in computation
  • wf

Goal

Why should we even consider lottery scheduling?

  • Abstraction
    • Now there is a explicit representation of CPU time as tickets
  • Relative
  • Uniform
    • We can apply uniform mechnism for resource allocation for other hardware (e.g. disk, memory, etc...)
  • Modular
  • No starvation

Implementation

  • Implements proportional share scheduling
  • Probabilistically meeting the proportion guaranteed

Takeaway

Extended Features from Lottery Scheduling

  • Transfer
Example: RPC Server

fwoiejfw

  • Inflation
  • Currencies → modularity
  • Compensation
Example: Shell

Shell programs do not need the entire quantum to execute. It might only take a fraction of the allocated time upon winning the lottery. Hence, we can give it compensation tickets (credits) to compensate this process for the CPU time that it doesn't use. We can let is get selected more often since it does not use the entire allocated time when selected.

My Question

  • Can you further explain why lottery scheduling is more superior than other proportional scheduling algorithms such as stride scheduling?
  • Can you explain the "modular" in why?
Back to top