article

Free access

Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment

Authors:

C. L. Liu,

James W. LaylandAuthors Info & Claims

Journal of the ACM (JACM), Volume 20, Issue 1

Pages 46 - 61

https://doi.org/10.1145/321738.321743

Published: 01 January 1973 Publication History

PDF eReader

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

[1]

MANACHER, G.K. Production and stabihzation of real-time task schedules. J. ACM 14,' 3 (July 1967), 439-465.

Crossref

Google Scholar

[2]

MCKINNEY, J M. A survey of analytical time-sharing models. Computing Surveys 1, 2 (June 1969), 105-116.

Crossref

Google Scholar

[3]

CODD, E.F. Multiprogram scheduling. Comm ACM 8, 6, 7 (June, July 1960), 347-350;413-418.

Crossref

Google Scholar

[4]

HET.ImR, J. Sequencing aspects of multiprogramming. J. ACM 8, 3 (July 1961), 426-439.

Crossref

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.

Crossref

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.

Crossref

Google Scholar

[9]

LAMPSON, B.W. A scheduling phdosophy for multiprocessing systems. Comm. ACM 11, 5 (May, 1968), 347-360.

Crossref

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 ff

Google 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

Cited By

View all

Saberikia MFarbeh HFazeli M(2025)Improving energy efficiency and fault tolerance of mission-critical cloud task scheduling: A mixed-integer linear programming approachSustainable Computing: Informatics and Systems10.1016/j.suscom.2024.10106845(101068)Online publication date: Jan-2025
https://doi.org/10.1016/j.suscom.2024.101068
Ortiz LGuasque ABalbastre PSimó J(2024)Allocation algorithms for multicore partitioned mixed-criticality real-time systemsPeerJ Computer Science10.7717/peerj-cs.260910(e2609)Online publication date: 20-Dec-2024
https://doi.org/10.7717/peerj-cs.2609
Ashutosh Kumar Ankit Kumar Singh Ashima Mehta (2024)AI based Operating SystemInternational Journal of Advanced Research in Science, Communication and Technology10.48175/IJARSCT-17449(291-298)Online publication date: 18-Apr-2024
https://doi.org/10.48175/IJARSCT-17449
Show More Cited By

Index Terms

Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Multiprocessing / multiprogramming / multitasking
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

Scheduling algorithms for multiprogramming in a hard-real-time environment
Readings in hardware/software co-design

The 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 ...
Scheduling algorithms for imprecise computation in real-time systems

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 20, Issue 1

Jan. 1973

190 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321738

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1973

Published in JACM Volume 20, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7,219
Total Citations
View Citations
27,985
Total Downloads

Downloads (Last 12 months)2,215
Downloads (Last 6 weeks)315

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Saberikia MFarbeh HFazeli M(2025)Improving energy efficiency and fault tolerance of mission-critical cloud task scheduling: A mixed-integer linear programming approachSustainable Computing: Informatics and Systems10.1016/j.suscom.2024.10106845(101068)Online publication date: Jan-2025
https://doi.org/10.1016/j.suscom.2024.101068
Ortiz LGuasque ABalbastre PSimó J(2024)Allocation algorithms for multicore partitioned mixed-criticality real-time systemsPeerJ Computer Science10.7717/peerj-cs.260910(e2609)Online publication date: 20-Dec-2024
https://doi.org/10.7717/peerj-cs.2609
Ashutosh Kumar Ankit Kumar Singh Ashima Mehta (2024)AI based Operating SystemInternational Journal of Advanced Research in Science, Communication and Technology10.48175/IJARSCT-17449(291-298)Online publication date: 18-Apr-2024
https://doi.org/10.48175/IJARSCT-17449
Liubimov OTurkin ICheranovskiy VVolobuieva L(2024)UAV Mission Computer Operation Mode Optimization Focusing on Computational Energy Efficiency and System ResponsivenessComputation10.3390/computation1212023512:12(235)Online publication date: 27-Nov-2024
https://doi.org/10.3390/computation12120235
Ortiz LGuasque ABalbastre PSimó JCrespo A(2024)Schedulability Analysis in Fixed-Priority Real-Time Multicore Systems with ContentionApplied Sciences10.3390/app1410403314:10(4033)Online publication date: 9-May-2024
https://doi.org/10.3390/app14104033
Migita HNakagoshi YFinnerty POhta COkuhara M(2024)Polling Schedule Algorithms for Data Aggregation with Sensor Phase Control in In-Vehicle UWB NetworksIEICE Transactions on Communications10.23919/transcom.2023EBP3150E107-B:8(529-540)Online publication date: Aug-2024
https://doi.org/10.23919/transcom.2023EBP3150
Cheng AKabcenell AChan JShi XBailis PCrooks NStoica I(2024)Towards Optimal Transaction SchedulingProceedings of the VLDB Endowment10.14778/3681954.368195617:11(2694-2707)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681956
Pang GZhu X(2024)Training efficiency optimization algorithm of wireless federated learning based on processor performance and network condition awarenessEURASIP Journal on Advances in Signal Processing10.1186/s13634-024-01192-62024:1Online publication date: 26-Nov-2024
https://doi.org/10.1186/s13634-024-01192-6
Rajasekaran SNarang SZabreyko AGhobadi M(2024)MLTCP: A Distributed Technique to Approximate Centralized Flow Scheduling For Machine LearningProceedings of the 23rd ACM Workshop on Hot Topics in Networks10.1145/3696348.3696878(167-176)Online publication date: 18-Nov-2024
https://dl.acm.org/doi/10.1145/3696348.3696878
Fischer TFalk H(2024)Towards Analysing Cache-Related Preemption Delay in Non-Inclusive Cache HierarchiesACM Transactions on Embedded Computing Systems10.1145/369576824:1(1-37)Online publication date: 10-Sep-2024
https://dl.acm.org/doi/10.1145/3695768
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations