Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.


Lottery Scheduling: Flexible Proportional-Share Resource Management (A Report)

No description

Zenith Arnejo

on 22 September 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Lottery Scheduling: Flexible Proportional-Share Resource Management (A Report)

Lottery Scheduling: Flexible Proportional-Share
Resource Management

Carl A. Waldspurger; William E. Weihl
MIT Laboratory for Computer Science

Presentor: Zenith Arnejo
Problem Statement
Existing Solutions
Proposed Solution
Detailed Approach
Solution Prototype
Testing & Results
Scheduling of limited resources to concurrent requests is faced with the following issues:
client requests varying in importance and computation rates
regulation of long-running requests
allocation of resources to important requests

Existing Solutions
Fair share
Tasks are given
absolute priority
"A task with higher priority
is given absolute precedence over
a task with lower priority"
Difficult to compose or abstract
inter-module priority relationships
"Allocate resources so that
clients get fair machine shares
over long periods of time"
CPU usage is equally distributed among clients
Algorithms for monitoring and priority adjustments are complex
"use auctions to
allocate resource among
bidding clients"
Bids = funds = resource rights
bidding causes significant overhead
Proposed Solution: Lottery Scheduling
- a randomized resource allocation mechanism
- provides efficient, responsive control on relative
computation execution rates
- supports modular resource management
Lottery Ticket
- encapsulates client's resource rights
- first-class object
- characterized as:
Lottery Draw
- random selection of winning tickets
probability that a
client will win
number of lotteries won
by a client
number of lotteries required
for a client's first win
Detailed Approach:
Implement resource management
policies using lottery tickets

Ticket Transfers
Ticket Inflation
Ticket Currencies
Compensation Tickets
- transfer ticket from one
client to another
- temporary transfer
- ticket distribution

- an alternative to explicit ticket transfer
- a client can escalate its resource rights
by creating more lottery tickets
- requires mutually trusting clients
- express resource rights in units that
are local to each group of mutually
trusting clients
- using currency exchange rates, effects
of inflation is conserved in the module
- a client which consumes only a fraction f of its
allocated resource quantum can be granted a
compensation ticket inflating its value by 1/f
until the client starts its next quantum
- in order to maintain right proportion of clients
to its share of the processor
Solution Prototype
- Mach 3.0 microkernel; 25MHz MIPS-based DECStation 5000/125; 100ms scheduling quantum
- randomly select winning ticket,
then search list of clients to
locate client holding the ticket
Mach Kernel Interface
mach_msg system call

" A transfer can be implemented by creating a new ticket denominated in the client's currency, and using it to fund server's currency"
allows resource management using tickets
Compensation Tickets
2 Threads: A & B each with 400 base units
A uses entire 100ms while B uses only 20ms of processor share;
thus, equal proportion share violated
Solution: inflate B for the after processor yield
A = 400 base units; B = 2000 base units
User Interface
- command-line control
- commands are:
> create & destroy tickets
(mtkt, rmtkt)
> fund & unfund currency
(fund, unfund)
> obtain information
(lstkt, lscur)
> execute command w/ funding

Testing & Results
- quantify prototype ability to flexibly, responsively, and efficiently control the relative execution rates of computations
- measure accuracy with which lottery scheduler could control the relative execution rates
Flexible Control
- observe behavior of the dynamic control of ticket inflation
Client-Server Computation
- measure throughput and response time of ticket allocation in a multi-threaded server-multiple client setup
Multimedia Applications
- measure efficiency of control of video display rates given 2 or more video viewers
Load Insulation
- observe performance of scheduling after adding new tasks
Lottery Scheduling isn't limited to a particular type of resource
In general, a lottery can be used to allocate resource wherever queueing is necessary for resource access
Lottery Scheduling can be used for:
> Resource Synchronization
> Space-Shared Resource
> Multiple Resources
Lottery Scheduling is

> Efficient & responsive over relative execution rates of computations

> Able to facilitate modular resource & diverse resource management

> Simple & easy; can be added to OS

Full transcript