ACM Home Page
Please provide us with feedback. Feedback
Digital Library logoTake a look at the new version of this page: [ beta version ]. Tell us what you think.
Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
Full text PdfPdf (976 KB)
Source Journal of the ACM (JACM) archive
Volume 20 ,  Issue 1  (January 1973) table of contents
Pages: 46 - 61  
Year of Publication: 1973
ISSN:0004-5411
Authors
C. L. Liu  Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL and Project MAC, Massachusetts Institute of Technology
James W. Layland  Jet Propulsion Laboratory, California Institute of Technology, 4800 Oak Grove Drive, Pasadena, CA
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 216,   Downloads (12 Months): 1278,   Citation Count: 936
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/321738.321743
What is a DOI?

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.


REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

1
2
3
4
 
5
GRAHAM, R.L. Bounds for certain multiprocessmg anomalies. Bell System Tech. J. 45, 9 (Nov. 1966), 1563-1581.
 
6
OSCHNER, B.P. Controlling a multiprocessor system. Bell Labs Record 44, 2 (Feb. 1966), 59-62.
7
8
9
 
10
MARTIN, j. Progrj~m,ng Real-T~me Computer Systems, Prentice-Hall, Englewood Cliffs, N.J., 1965.
 
11
JZRAVCn, D.H. Software deslgn techniques for automatic checkout. IEEE Trans. AES-$, 6 (Nov. 1967), 93~~.
 
12
MARTIN, J. Op. clt., p. 35 ff
 
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.

CITED BY  936

Collaborative Colleagues:
C. L. Liu: colleagues
James W. Layland: colleagues