A proportional share resource allocation algorithm for real-time, time-shared systems
|
| Washington D.C. December 04-December 06 |
I. Stoica, Dept. of Comput. Sci., Wisconsin Univ., Madison, WI, USA
H. Abdel-Wahab, Dept. of Comput. Sci., Wisconsin Univ., Madison, WI, USA
K. Jeffay, Dept. of Comput. Sci., Wisconsin Univ., Madison, WI, USA
S.K. Baruah, Dept. of Comput. Sci., Wisconsin Univ., Madison, WI, USA
J.E. Gehrke, Dept. of Comput. Sci., Wisconsin Univ., Madison, WI, USA
C.G. Plaxton, Dept. of Comput. Sci., Wisconsin Univ., Madison, WI, USA
We propose and analyze a proportional share resource allocation algorithm for realizing real-time performance in time-shared operating systems. Processes are assigned a weight which determines a share (percentage) of the resource they are to receive. The resource is then allocated in discrete-sized time quanta in such a manner that each process makes progress at a precise, uniform rate. Proportional share allocation algorithms are of interest because: they provide a natural means of seamlessly integrating real and non-real-time processing; they are easy to implement; they provide a simple and effective means of precisely controlling the real-time performance of a process; and they provide a natural means of policing so that processes that use more of a resource than they request have no ill-effect on well-behaved processes. We analyze our algorithm in the context of an idealized system in which a resource is assumed to be granted in arbitrarily small intervals of time and show that our algorithm guarantees that the difference between the service time that a process should receive and the service time it actually receives is optimally bounded by the size of a time quantum. In addition, the algorithm provides support for dynamic operations, such as processes joining or leaving the competition, and for both fractional and non-uniform time quanta. As a proof of concept we have implemented a prototype of a CPU scheduler under FreeBSD. The experimental results shows that our implementation performs within the theoretical bounds and hence supports real-time execution in a general purpose operating system.
Index Terms:
resource allocation; proportional share resource allocation algorithm; real-time system; idealized system; real-time performance; time-shared operating systems; service time; optimally bounded; dynamic operations; CPU scheduler; FreeBSD; general purpose operating system
Citation:
I. Stoica, H. Abdel-Wahab, K. Jeffay, S.K. Baruah, J.E. Gehrke, C.G. Plaxton, "A proportional share resource allocation algorithm for real-time, time-shared systems," rtss, pp.288, 17th IEEE Real-Time Systems Symposium (RTSS '96), 1996
Usage of this product signifies your acceptance of the
Terms of Use.
|
|
|
|
|
|
|
|