From: Sellakumaran Kanagarathnam (sellak_at_windows.microsoft.com)
Date: Tue Jan 27 2004 - 19:40:46 PST
This paper discusses a novel solution for proportional-share resource
allocation. It lets you think about allocation and management in new
ways.
In lottery scheduling, resource rights are represented by lottery
tickets. Each time a resource is available for allocation, lottery is
held and the owner of the winning lottery gets the resource. The values
of the lottery tickets are relative. If a resource is highly contended,
then a ticket could represent a small fraction and vice versa.
Scheduling by lottery is probabilistic. The probability p that a client
holding t tickets will win a given lottery of total T tickets is simply
p = t/T.
The authors then present the basic resource management techniques with
lottery tickets. Tickets can be transferred from one client to another.
An example given is that a client waiting for a reply from an RPC can
give its tickets to the server. Ticket inflation can be used by a
client to increase its share by creating more lottery tickets. Then the
authors introduce a very interesting concept of currency very similar to
actual currency. It leads you into exchange rate, inflation rate and so
on. The currency abstraction is useful for flexibly naming, sharing and
protecting resource rights. A client that does not use all of its
allocated resources will be given compensation tickets until next
quantum so that it gets proper share of the processor.
The authors then go onto describe the implementation. A prototype
lottery scheduler was implemented by modifying the Mach 3.0 microkernel
on a 25MHz MIPS-based DecStation. Lottery scheduler will randomly
select a winning ticket and then search a list of clients to locate the
winner.
Experiments were conducted to evaluate the prototype. Over longer
periods of time, the scheduler allocation seems to be fair (average
ratio of 2.01:1 for a 2:1 ticket allocation). The client-server
computation experiment also showed that the responses matched to that of
the priority of the clients (based on tickets held).
Lotteries can be used to manage many diverse resources such processor
time, I/O bandwidth, access to locks, in general, wherever queuing is
necessary for resource access. The authors discuss synchronization
resources (example mutex implementation) and space-shared resources
(like memory). Lottery scheduling can control the relative waiting
times of threads competing for lock access. The ticket transfers from
blocked threads to fund mutex currency and inheritance ticket transfer
from mutex to thread holding the mutex, solves the priority inversion
problem (high priority thread blocked by a low-priority thread holding
mutex).
This archive was generated by hypermail 2.1.6 : Tue Jan 27 2004 - 19:37:18 PST