Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
C. L. Liu, J. W. Layland · Journal of the ACM · 1973
The problem of multiprogram scheduling on a single processor is studied from the viewpoint of the characteristics peculiar to the program functions that need guaranteed service. It is shown that an optimum fixed priority scheduler possesses an upper bound to processor utilization which may be as low as 70 percent for large task sets. It is also shown that full processor utilization can be achieved by dynamically assigning priorities on the basis of their current deadlines. A combination of these two scheduling techniques is also discussed.
Cited by 8,409 works. doi:10.1145/321738.321743 Open-access PDF
Authors
References
- Sequencing Aspects of Multiprogramming
- Bounds for Certain Multiprocessing Anomalies
- Production and Stabilization of Real-Time Task Schedules
- Multiprogram scheduling
- A scheduling philosophy for multiprocessing systems
- Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems
- A Survey of Analytical Time-Sharing Models
- Programming Real-Time Computer Systems
- Multiprogram scheduling
- A policy-driven scheduler for a time-sharing system