Scheduling algorithms for multiprogramming in a hard-real-time environment
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Response times can be almost certainly guaranteed up to a load factor of about 80% under rate monotonic scheduling.
“In a typical scheduling method called rate monotonic scheduling (RMS) [29], it has been shown that response times can be almost certainly guaranteed up to a load factor of about 80%.”
From Asset Management Method of Industrial IoT Systems for Cyber-Security Countermeasures (2021) · cites this paper as [29]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Bounds for Certain Multiprocessing Anomalies
Graham, R. (1966) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1966.tb01709.x · Cited by 1,661 · see citing works
Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems
Muntz, R. R., & Coffman, E. G. (1970) · Journal of the ACM · doi:10.1145/321574.321586 · Cited by 156 · see citing works
A scheduling philosophy for multiprocessing systems
Lampson, B. (1968) · Communications of the ACM · doi:10.1145/363095.363144 · Cited by 102 · see citing works
A Survey of Analytical Time-Sharing Models
McKinney, J. M. (1969) · ACM Computing Surveys · doi:10.1145/356546.356549 · Cited by 96 · see citing works
Production and Stabilization of Real-Time Task Schedules
Manacher, G. K. (1967) · Journal of the ACM · doi:10.1145/321406.321408 · Cited by 87 · see citing works
Programming Real-Time Computer Systems
Ernst, H. M., & Martin, J. L. (1966) · Mathematics of Computation · doi:10.2307/2003621 · Cited by 63 · see citing works
Codd, E. F. (1960) · Communications of the ACM · doi:10.1145/367297.367317 · Cited by 44 · see citing works
A policy-driven scheduler for a time-sharing system
Bernstein, A. J., & Sharp, J. C. (1971) · Communications of the ACM · doi:10.1145/362515.362520 · Cited by 33 · see citing works
Sequencing Aspects of Multiprogramming
Heller, J. (1961) · Journal of the ACM · doi:10.1145/321075.321086 · Cited by 28 · see citing works
Codd, E. F. (1960) · Communications of the ACM · doi:10.1145/367349.367356 · Cited by 17 · see citing works
Software Design Techniques for Automatic Checkout
Jirauch, D. H. (1967) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.1967.5408666 · Cited by 6 · see citing works
Certification of Algorithm 46: Exponential of a complex number
Relph, A. P. (1962) · Communications of the ACM · doi:10.1145/367766.368184 · Cited by 1 · see citing works
Flagged first, then by citations
Research works printed but not linked: 1
- RECEIVED MARCH 1970; REVISED JANUARY 1972 Journal of the Associatlon ior Cornputmg Machinery, Vol. 20, No. I, January 1973
Cited by
Sorted by citations
Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised
Davis, R. I., Burns, A., Bril, R. J., & Lukkien, J. J. (2007) · Real-Time Systems · doi:10.1007/s11241-007-9012-7 · Cited by 786 · see citing works
Differential Privacy Techniques for Cyber Physical Systems: A Survey
Hassan, M. U., Rehmani, M. H., & Chen, J. (2020) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2019.2944748 · Cited by 564 · see citing works
Energy-driven scheduling algorithm for nanosatellite energy harvesting maximization
Slongo, L. K., Martínez, S. V., Eiterer, B. V. B., Pereira, T. G., Bezerra, E. A., & Paiva, K. V. (2018) · Acta Astronautica · doi:10.1016/j.actaastro.2018.03.052 · Cited by 30 · see citing works
Asset Management Method of Industrial IoT Systems for Cyber-Security Countermeasures
Matsumoto, N., Fujita, J., Endoh, H., Yamada, T., Sawada, K., & Kaneko, O. (2021) · Information · doi:10.3390/info12110460 · Cited by 13 · see citing works
“In a typical scheduling method called rate monotonic scheduling (RMS) [29], it has been shown that response times can be almost certainly guaranteed up to a load factor of about 80%.”
Method
- Authors
- Liu, C. L., & Layland, J. W.
- Affiliations
- University of Illinois Urbana-Champaign (US)
- California Institute of Technology (US)
- Venue
- Journal of the ACM
- Published
- 1973-01
- Volume
- 20
- Issue
- 1
- Pages
- 46-61
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2109488193
- Cited by
- 8,433
- References
- 12
- Citations by year
- 2026: 137 · 2025: 103 · 2024: 112 · 2023: 138 · 2022: 139 · 2021: 153 · 2020: 188 · 2019: 222 · 2018: 232 · 2017: 242 · 2016: 269 · 2015: 308 · 2014: 347 · 2013: 314 · 2012: 321
- FWCI
- 4.75
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Journal of the ACM (publishedVersion)
- Funders
- National Aeronautics and Space Administration
- Topics
- Physical Sciences › Computer Science › Hardware and Architecture › Real-Time Systems Scheduling
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Hardware and Architecture › Embedded Systems Design Techniques
- Keywords
- multiprogramming, hard real-time systems, scheduling algorithms, fixed-priority scheduling, CPU utilization, guaranteed service, single machine scheduling, task sets
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
