C. L. Liu
Abstract
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.
- 1 MANACHER, G.K. Production and stabihzation of real-time task schedules. J. ACM 14,' 3 (July 1967), 439-465. Google Scholar
- 2 MCKINNEY, J M. A survey of analytical time-sharing models. Computing Surveys 1, 2 (June 1969), 105-116. Google Scholar
- 3 CODD, E.F. Multiprogram scheduling. Comm ACM 8, 6, 7 (June, July 1960), 347-350;413-418. Google Scholar
- 4 HET.ImR, J. Sequencing aspects of multiprogramming. J. ACM 8, 3 (July 1961), 426-439. Google Scholar
- 5 GRAHAM, R.L. Bounds for certain multiprocessmg anomalies. Bell System Tech. J. 45, 9 (Nov. 1966), 1563-1581.Google Scholar
- 6 OSCHNER, B.P. Controlling a multiprocessor system. Bell Labs Record 44, 2 (Feb. 1966), 59-62.Google Scholar
- 7 MUNTZ, R. R., AND COFFM~N, E. G., JR. Preemptive scheduling of real-time tasks on multiprocessor systems. J. ACM 17, 2 (Apr 1970), 324-338. Google Scholar
- 8 BERNSTEIN, A. J., AND SHARP, J.C. A policy-driven scheduler for a time-sharing system. Comm. ACM 14, 2 (Feb. 1971), 74-78. Google Scholar
- 9 LAMPSON, B.W. A scheduling phdosophy for multiprocessing systems. Comm. ACM 11, 5 (May, 1968), 347-360. Google Scholar
- 10 MARTIN, j. Progrj~m,ng Real-T~me Computer Systems, Prentice-Hall, Englewood Cliffs, N.J., 1965.Google Scholar
- 11 JZRAVCn, D.H. Software deslgn techniques for automatic checkout. IEEE Trans. AES-$, 6 (Nov. 1967), 93~~.Google Scholar
- 12 MARTIN, J. Op. clt., p. 35 ffGoogle Scholar
- 13 Lzu, C.L. Scheduling algorithms for hard-real-time multiprogramming oi a single processor. JPL Space Programs Summary 37-60, Vol. II, Jet Propulsion Lab., Calif. Inst. of Tech., Pasadena, Calif., Nov. 1969.Google Scholar
Index Terms
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
Recommendations
Scheduling algorithms for multiprogramming in a hard-real-time environment
Readings in hardware/software co-designThe problem of multiprogram scheduling on a single processor is studied from the viewpoint of the characteristics peculiar to the program function that need guaranteed service. It is shown that an optimum fixed priority scheduler possesses an upper ...
Approximation algorithms for scheduling real-time jobs with multiple feasible intervals
Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job is constrained to execute from start to completion in one of its feasible intervals. A job fails if the job remains incomplete at the end of the last feasible ...
Comments