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.
Keywords
Computer multitaskingComputer scienceScheduling (production processes)Fixed-priority pre-emptive schedulingEarliest deadline first schedulingParallel computingFair-share schedulingDistributed computingDynamic priority schedulingRate-monotonic schedulingAlgorithmReal-time computingQuality of serviceMathematical optimizationComputer networkMathematics
Affiliated Institutions
Related Publications
Production and Stabilization of Real-Time Task Schedules
A model for multiprocessor control is considered in which jobs are broken into various pieces, called tasks . Tasks are executed by single processing units. In this paper the st...
A policy-driven scheduler for a time-sharing system
The services received by a process from a time-sharing operating system can be characterized by a resource count ∑ w i R ij where R ij is the number of units of service received...
Supporting real-time applications in an Integrated Services Packet Network
This paper considers the support of real-time applications in an Integrated Services Packet Network (ISPN). We first review the characteristics of real-time applications. We obs...
Revolutionizing Supply Chain Management: Real-time Data Processing and Concurrency
In the contemporary business landscape, effective supply chain management (SCM) is paramount for organizations seeking to thrive amidst evolving market dynamics and heightened c...
Publication Info
- Year
- 1973
- Type
- article
- Volume
- 20
- Issue
- 1
- Pages
- 46-61
- Citations
- 8233
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
8233
OpenAlex
Cite This
C. L. Liu,
J. W. Layland
(1973).
Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment.
Journal of the ACM
, 20
(1)
, 46-61.
https://doi.org/10.1145/321738.321743
Identifiers
- DOI
- 10.1145/321738.321743