Some notes taking from reading the paper ‘Lottery Scheduling: Flexible Proportional-Share Resource Management’.

Intro

challenges of CPU scheduler

  • real-time:
    • hard: industrial control
    • soft: audio, video
  • multi-process
  • fairness
  • priorities
  • CPU utilization
  • isolation
  • overhead
  • starvation avoidance (SJF)

history of CPU schedulers

  • general-purpose schemes (mostly rely on priority)
    • does not provide the encapsulation and modularity properties required for large software systems
  • fair share & microeconomic
    • overheads limit them to relatively coarse control over long-running computations
  • proportional-share (lottery scheduling)
    • resourse consumption rates of active computetions are proportional to the relative shares that they are allocated
    • provides responsive control over the relative execution rates of computations
    • excellent support for modular resource management

problems: proportional share scheduler

lottery scheduling

a randomized resource allocation mechanism, each allocation is determined by holding a lottery, the resource is granted to the client with the winning ticket

the ticket

  • abstract: quantify resource rights independently of machine details
  • relative: the fraction of a resource they represent varies dynamically in proportion to the contention for that resource
  • uniform: right for heterogeneous resources can ve homogeneously represented as tickets

statistics

  • scheduling by lottery is probabilistically fair
  • suppose a client has \(t\) tickets, the total tickets is \(T\):
    • the number of lotteries won by a client has a binomial distribution:
      • the probablity this client win: \(p = t/T\)
      • the expected number of wins in \(n\) time lotteries: \(E = np\), variance \(\sigma_w^2 = np(1-p)\), \(\sigma_w/E = \sqrt{(1-p)/np}\)
    • the times of lotteries required until the client’s first win has a geometric distribution:
      • expected number of time $n$ that a client wait before first win: \(E(n) = 1/p\), varience \(\sigma^2_w = (1-p)/p^2\)
      • that is \(ResponseTime \propto 1/t\)
  • any client with non-zero num of tickets will eventually win a lottery -> solve the problem of starvation

Modular resource management

ticket transfer

  • ex: a client needs to block pending a reply from an RPC, it can transfer its tickets to that server
  • solves the conventional priority inversion problem

ticket inflation

  • an alternative of transfer: a client can escalate its resource rights by creating more lottery tickets
  • but it will violated desirable modularity and load insulation properties
  • very useful among mutually trusting clients: can be used to adjust resource allocations without explicit communication

ticket currencies

  • a unique currency can be used to denominate tickets within each trust boundary
  • cause inflation, but can maintain an exchange rate between local currency and a base currency

compensation tickets

  • A client which consumes only a fraction \(f\) of its allocated resource quantum can be granted a compensation ticket that inflates its value by 1 until the client starts its next quantum.

Implementation

  • scheduling quantum: 100 ms
  • random number: in 10 RISC instructions

lotteries

  1. search a list of \(n\) clients in \(O(n)\) time, can ordering by decreasing to reduce average searching time
  2. when \(n\) is large, use a tree of partial ticket sums, traversed the winning client leaf node in \(log(n)\)

ticket active & deactive

  • a ticket is active while it is being used by a thread to compete in a lottery
  • when a thread is removed from the run queue, its tickets are deactived
  • the tickets are reactived when the thread rejoin the running queue

ticket transfer

  • creating a new ticket denominated in the client’s currency, and using it to fund the server’s currency

Experiments

  • dynamic ticket inflationcontrol
  • client/server ticket transmission

system overhead

  • the overhead imposed by our prototype lottery scheduler is comparable to that of the standard Mach time-sharing policy.

Managing diverse resource

locks

  • The mutex transfers its inheritance ticket to the thread which currently holdsthe mutex.
  • When a thread releases a lottery-scheduled mutex, it holds a lottery among the waiting threads to determine the next mutex owner.
  • then the thread moves the mutex inheritance ticket to the winner

space-shared resource(memory)

  • use an inverse lottery, in which a “loser” is chosen to relinquish a unit of a resource that it holds.
  • suppose a client holds \(t\) tickets, the probability of being selected by a lottery with total tickets \(T\) and \(n\) clients is $$p = \frac{(1-t/T)}{n-1}$$