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

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
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
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,205
Total Citations
View Citations
27,765
Total Downloads

Downloads (Last 12 months)2,157
Downloads (Last 6 weeks)279

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
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
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
Pereira DGhosh SDey S(2024)Multi-Stream Scheduling of Inference Pipelines on Edge Devices - a DRL ApproachACM Transactions on Design Automation of Electronic Systems10.1145/367737829:6(1-36)Online publication date: 11-Jul-2024
https://dl.acm.org/doi/10.1145/3677378
Da Silva Barros TFerre DGiroire FAparicio-Pardo RPerennes S(2024)Scheduling Machine Learning Compressible Inference Tasks with Limited Energy BudgetProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673106(961-970)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673106
McDonald BMueller FShrivastava ASui Y(2024)OpenMP-RT: Native Pragma Support for Real-Time Tasks and Synchronization with LLVM under LinuxProceedings of the 25th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3652032.3657574(119-130)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3652032.3657574
Takado KYokoyama TYoo M(2024)A Real-Time Operating System for Physical and Logical Time-Triggered Distributed ComputingProceedings of the 2024 6th Asia Pacific Information Technology Conference10.1145/3651623.3651635(78-85)Online publication date: 29-Jan-2024
https://dl.acm.org/doi/10.1145/3651623.3651635
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