Abstract: We propose and analyze a proportional share resource allocation algorithm for realizing real-time performance in time-shared operating systems. In a proportional share system, 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 (1) they provide a natural means of seamlessly integrating real- and non-real-time processing requirements in a general purpose operating system, (2) they are easy to implement (and in particular, easier than more traditional forms of real-time support such as periodic tasks), (3) they provide a simple and effective means of precisely controlling the real-time performance of a process including uniform, predictable degradation in times of system overload, and (4) they provide a natural means of policing processes so that process that use more of a resource than they request have no ill-effect on well-behaved processes.
We present our algorithm and its analysis 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 in the idealized system and the service time it actually receives in the real system is bounded by the size q of a time quantum. This demonstrates that our algorithm is capable of guaranteeing real-time response times to processes. Moreover, we also show that these bound are the best obtainable in a proportion share system and hence that our algorithm provides optimal performance. Lastly, 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 operating systems. The experimental results shows that our implementation perform within the theoretical bounds and hence supports real-time execution in a general purpose operating system.
(Note that this on-line version of the paper is an expanded and more complete version than the one appearing in the conference proceedings. To get a copy of the paper as it appeared in the proceedings click here.)