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

1973/01/01 by C. L. Liu, J. W. Layland · 18 citations
Computer Science · Engineering · #Distributed and Parallel Computing Systems #Scheduling and Optimization Algorithms #Real-Time Systems Scheduling

paper · pdf · doi:10.1145/321738.321743

openalex publication_date 1973/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

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.

Citations

• Bounds for Certain Multiprocessing Anomalies

Cited by

• Reducing Internet Latency: A Survey of Techniques and Their Merits
• Proof of the Density Threshold Conjecture for Pinwheel Scheduling
• Bounded Priority-Aware Locking for Real-Time Kernels
• Misconceptions about real-time computing: a serious problem for next-generation systems
• Real-time computing: a new discipline of computer science and engineering
• Load adjustment in adaptive real-time systems
• Rate monotonic analysis: the hyperbolic bound
• Real-time scheduling theory and Ada
• The rate monotonic scheduling algorithm: exact characterization and average case behavior
• On the complexity of fixed-priority scheduling of periodic, real-time tasks
• A Simulation Framework for Contention-Free Scheduling on WiGig
• PALMA: A Lightweight Tropical Algebra Library for ARM-Based Embedded Systems
• An Analytical Solution for Probabilistic Guarantees of Reservation Based Soft Real-Time Systems
• Experimental Software Schedulability Estimation For Varied Processor Frequencies
• Automatic Parameter Derivations in k2U Framework
• Feasibility Analysis in the Sporadic DAG Task Model
• Computer multitasking [wikipedia]
• Rate-monotonic scheduling [wikipedia]