Thumbnail
Access Restriction
Subscribed

Author Manacher, G. K.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1967
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract A model for multiprocessor control is considered in which jobs are broken into various pieces, called $\textit{tasks}.$ Tasks are executed by single processing units. In this paper the structure controlling the assignment of tasks to processors is the task list, which orders all tasks according to servicing priority. When a processors becomes free, it simply picks up the highest priority task that is executable at that moment.The job and its component tasks are imagined to be interacting with an environment consisting of a set of rigid timing constraints. Such constraints are of two types, called $\textit{start-times}$ and $\textit{deadlines}.$ The interaction is specified by requiring that certain distinguished tasks conform directly to one or more of these constraints. Tasks conforming to a start-time cannot begin until the start-time has passed, and tasks conforming to a deadline cannot proceed beyond the deadline. In our model, all tasks have known $\textit{maximum}$ run-times, but in any particular job execution, task run-times are unknown.It is shown that despite the simplicity of this control scheme some peculiar phenomena result. Most of these phenomena were first noticed by P. Richards in 1960. A simulation study (Appendix I) reveals that they may be very common in practice. In the present paper and a companion paper by R. L. Graham [Bell Syst. Tech. J. 45 (1966), 1563-1581] a coherent theory of task-list control is developed, in which the nature of these peculiarities is brought under systematic study. A number of potentially useful results are derived.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1967-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 14
Issue Number 3
Page Count 27
Starting Page 439
Ending Page 465


Open content in new tab

   Open content in new tab
Source: ACM Digital Library