Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
Journal of the ACMPublished 1 January 1973Open access
C. L. Liu, J. W. Layland
Citations8,334
SJR quartileQ1
SJR score2.25
SNIP3.16
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
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 ScienceEngineering
Bell System Technical JournalBounds for Certain Multiprocessing Anomalies
1,617 Citations1966Ronald Graham
Journal of the ACMPreemptive Scheduling of Real-Time Tasks on Multiprocessor Systems
154 Citations1970Richard R. Muntz, E. G. Coffman
The authors solve the problem of scheduling a set of tasks whose operational precedence structure is representable as an acyclic directed graph and proof of an efficient algori thm for finding the minimal-length preemptive schedule for tree-structured computations.
Communications of the ACMA scheduling philosophy for multiprocessing systems
102 Citations1968Butler Lampson
A collection of basic ideas is presented, which have been involved by various workers over the past four years to provide a suitable framework for the design and analysis of multiprocessing systems.
ACM Computing SurveysA Survey of Analytical Time-Sharing Models
95 Citations1969Jennifer McKinney
The parameters which are considered in the different analytic models provide the system designer with a number of degrees of freedom with which to synthesize a t]me-shared processing system and point out needed research directions.
Journal of the ACMProduction and Stabilization of Real-Time Task Schedules
87 Citations1967Glenn K. Manacher
A coherent theory of task-list control is developed, in which the nature of peculiarities of this control scheme is brought under systematic study and a number of potentially useful results are derived.
Communications of the ACMMultiprogram scheduling
40 Citations1960E. F. Codd
A concise scheduling algorithm is described which tends to minimize the time for executing the entire pending workload (or any subset of it), subject to external constraints such as precedence, urgency, etc.
Communications of the ACMA policy-driven scheduler for a time-sharing system
33 Citations1971A. J. Bernstein, J.C. Sharp
The algorithm has been implemented in a general purpose operating system, and it has provided significantly better service to interactive and to batch jobs than the previous scheduler.
Journal of the ACMSequencing Aspects of Multiprogramming
28 Citations1961Jack Heller
The sequencing or scheduling aspects of multiprogramming are discussed, which have not been studied in mathematical detail in the machine shop scheduling context, but have been discussed under the name of job-lot MSS.
Communications of the ACMMultiprogram scheduling
16 Citations1960E. F. Codd
The scheduling algorithm examines the programs to be scheduled one by one and places their component rectangles in the corresponding load diagrams according to a set of placement rules.
IEEE Transactions on Aerospace and Electronic SystemsSoftware Design Techniques for Automatic Checkout
6 Citations1967Dorothea H. Jirauch
Some of the many problem areas that should be considered in the design of the software for a sophisticated checkout project are discussed.
Communications of the ACMCertification of Algorithm 46: Exponential of a complex number
1 Citations1962A. P. Relph
The procedure was originally programmed in FORTRAN for the Control Data 160 desk-size computer and was limited to te t ra t ion because subroutine recursiveness in CONTROL Data 160 FORTRan has been held down to four levels in the interests of economy.