### Production and Stabilization of Real-Time Task SchedulesProduction and Stabilization of Real-Time Task Schedules

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

Source: ACM Digital Library