17th IEEE Real-Time Systems Symposium (RTSS '96) A proportional share resource allocation algorithm for real-time, time-shared systems Washington D.C. December 04-December 06 ISBN: 0-8186-7689-2
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||