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 tt tickets, the total tickets is TT:

  • the number of lotteries won by a client has a binomial distribution:
  • the probablity this client win: p=t/Tp=t/T
  • the expected number of wins in nn time lotteries: E=npE=np, variance σ2w=np(1−p)σw2=np(1−p), σw/E=√(1−p)/npσw/E=(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/pE(n)=1/p, varience σ2w=(1−p)/p2σw2=(1−p)/p2
  • that is ResponseTime∝1/tResponseTime∝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 ff 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 nn clients in O(n)O(n) time, can ordering by decreasing to reduce average searching time
2. when nn is large, use a tree of partial ticket sums, traversed the winning client leaf node in log(n)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 tt tickets, the probability of being selected by a lottery with total tickets TT and nn clients is p=(1−t/T)n−1p=(1−t/T)n−1