On the Duality between Resource Reservation and Proportional Share Resource Allocation

I. Stoica, H. Abdel-Wahab, and K. Jeffay
Proceedings, Multimedia Computing and Networking 1997
SPIE Proceedings Series, Volume 3020
San Jose, CA, February 1997
pages 207-214.

ABSTRACT: We describe a new framework for resource allocation that unifies the well-known proportional share and resource reservation policies. Each client is characterized by two parameters: a weight that represents the rate at which the client "pays" for the resource, and a share that represents the fraction of the resource that the client should receive. A fixed rate corresponds to a proportional share allocation, while a fixed share corresponds to a reservation. Furthermore, rates and shares are duals of each other. Once one parameter is fixed the other becomes fixed as well. If a client asks for a fixed share then the level of competition for the resource determines the rate at which it has to pay, while if the the rate is fixed, level of competition determines the service time the client should receive. To implement this framework we use a new proportional share algorithm, called Earliest Eligible Virtual Deadline First, that achieves optimal accuracy in the rates at which process execute. This makes it possible to provide support for highly predictable, real-time services. As a proof of concept we have implemented a prototype of a CPU scheduler under the FreeBSD operating system. The experimental results show that our scheduler achieves the goal of providing integrated support for batch and real-time applications.

Get a PostScript - or- a PDF copy of this paper.

Back to the Multimedia Neworking Research at UNC page, or...
Back to the Real-Time Systems Research at UNC page.