From: Cliff Schmidt (cliff_at_bea.com)
Date: Wed Jan 28 2004 - 04:38:44 PST
This paper describes a system for scheduling resource allocation as an
alternative to systems in use today that can only coarsely control allocation
based on something like an arbitrary priority number. The system is
described as "proportional-share resource management", since consumption
is proportional to allocated shares. It is also described as being
probabilistically fair, since a client can have an expectation of its chances
of "winning" a resource, but without a guarantee in any particular attempt.
The relationship of tickets, currencies, and compensations was not completely
clear to me until it was described in more detail in the implementation
section. Although some concepts, such as ticket inflation and funding of
currencies were never fully explained. The method of efficiently picking a
winning ticket was clear -- basically selecting a random number between zero
and n-1, where n is the total number of tickets participating in the lottery.
This can also be optimized by moving the clients with the greatest number of
tickets to the front of the list to reduce the average search length.
The lottery system appeared at first to me to just be another system to solve
the same problem; however, I was impressed with how the lottery system
handled particular cases, such as the following:
- "compensation tickets" gives more tickets to clients in proportion to the
time that they yield the resource earlier than their allotment. This allows
the client to get relatively more chances at acquiring a resource that they
are going to give up sooner than another client would.
- "ticket transfers" allow a client to give their tickets to another client.
There are two interesting examples of this: 1) when a client is blocked while
making an RPC call, for instance, they can transfer their tickets to the
server that they are waiting on, which promotes the chances that this other
process that it depends on will acquire the resources it needs to do the work
and return. 2) lock funding allows a client or clients, which are waiting on
a lock, to transfer their tickets to the client that holds the lock, which
will improve the chances for the client to finish its work and release the
lock sooner.
- "space-shared resources" apply an inverse version of the lottery concept by
simply probabilistically choosing the client with the fewer tickets when
trying to pick a client to relinquish a unit of a resource.
The paper also makes a point of trying to convince the reader that, as robust
as this mechanism is, the implementation is extremely lightweight -- they
even go to the point of including the 10 RISC instructions to generate a
random number in the appendix.
This archive was generated by hypermail 2.1.6 : Wed Jan 28 2004 - 04:38:49 PST