Production and Stabilization of Real-Time Task Schedules

ABSTRACT

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 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 start-times and 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 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.

REFERENCES

• 1: OCttSNE, B.P. Controlling a multiproeessor system. Bell Labs. Rec. 44 (Feb. 1966), 59-62.
• 2: GRAHAM, R. L. Bounds for certain multiproeessing anomalies Bet Syst. Tzch. J. Zg (1966), 1563 1581.
• 3: RICHARDS, P. Timing properties of multipreeessor systems. Tech. Paper, Rep. No. TD- B60-27, Tech. Operations, Inc., Burlington, iass., Aug. 1960.
• 4: RoY, B. Los Problmes d'Ordonnancement. 5'Ionographe de Recherche Oprat.ionnelle No. 2, Duned, Paris: 1964. (This monograph discusses relative and absolute irMng constraints in considerable detail.)
• 5: J. Heller, Sequencing Aspects of Multiprogramming, Journal of the ACM (JACM), v.8 n.3, p.426-439, July 1961 [doi>10.1145/321075.321086]
• 6: WIST, JErmM D, StHne properties of schedules for large projects wL, h limited resources. Oper. Res. 12,3 (May-June 1964), 395-418.
• 7: E. F. Codd, Multiprogram scheduling: parts 1 and 2. introduction and theory, Communications of the ACM, v.3 n.6, p.347-350, June 1960 [doi>10.1145/367297.367317]
• 8: McNAuGHTON, R. Scheduling with deadlines and loss functions. Manage. Sci. 6 1 (Oct. 1954), 1-12
• 9: HELD, MIOHAEL, AND KAIcP, IhCtt,tD i. A dynamic programming approach to sequeneproblems, or. SIAM I0, 1 (March 1962), 196-210. (This article includes an excellent bibliography.)
• 10: D. J. Farber , R. E. Griswold , I. P. Polonsky, SNOBOL , A String Manipulation Language, Journal of the ACM (JACM), v.11 n.1, p.21-30, Jan. 1964 [doi>10.1145/321203.321207]
• 11: FULKENS(IN, D.R. Scheduling in project networks. Prec. IBM Scientific Computing Syrup. on Combinatorial Problems, March 16-18, 1966, pp. 73-92. (See especially his response to questimt posed by J. Edmonds in the discussion.)
• 12: ROTHKOFF', M. Sehe(hfling independent tasks on one or more processors. Interim Teeh. Rep. No. 2, Operations Res. Certer, MIT, Cambridge, Mass., Jan. 1964.
• 13: BIRKOFF, G. Lattice Theory. Amer. Math. Soc. Colloq. Publications, Vol. XXV. Amer. Math. See., Providence, R. I., 1940.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

General Terms:
Algorithms, Measurement, Performance, Reliability, Theory, Verification