Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!agate!helios.ee.lbl.gov!ucsd!telesoft!tom
From: tom@telesoft.UUCP (Tom Quiggle @sation)
Newsgroups: comp.realtime
Subject: Re: Recommendations for information/articles on realtime scheduling
Summary: Several references
Message-ID: <340@telesoft.UUCP>
Date: 5 May 89 01:21:31 GMT
References: <8544@siemens.siemens.com> <24843@ames.arc.nasa.gov>
Distribution: usa
Organization: TeleSoft Inc., San Diego, CA
Lines: 87


For uniprocessor systems with predominantly periodic job mixes, Liu and
Layland described the Rate Monotonic algorithm back in 1970, which is
optimal for fixed-priority schemes.  A group out at Carnegie Mellon,
(notably Lui Sha, John Lehoczky, and Ragunathan Rajkumar) has developed
several scheduling protocols based on the  Rate Monotonic algorithm
that show a great deal of promise.  For uniprocessor systems with arbitrary 
arrival times, Dertouzos showed that an Earliest Deadline First algorithm 
is optimal.

  C. L. Lui and J. Layland, Scheduling Algorithms for Multiprogramming
      in a Hard Real-Time Environment, J. ACM, 20(1), 1973.

  L. Sha, R. Rajkumar, and J. P. Lehoczky, Priority Inheritance Protocals:
      An Approach to Real-Time Synchronization, Carnegie Mellon University 
      Tech. Report CMU-CS-87-181, November, 1987

  J. B. Goodenough and A L. Sha, The Priority Ceiling Protocal: A Method 
      for Minimizing the Blocking of High Priority Ada Tasks, in Proceedings 
      of the Second International Workshop on Real-Time Ada Issues, a Special 
      Edition of Ada Letters 8(7), Fall 1988.

  L. Sha, J. P. Lehoczky and R. Rajkumar, Solutions For Some Pratical 
      Problems in Prioritized Preemptive Scheduling, IEEE Real-Time Systems 
      Symposium, 1986.

  A M. Dertouzos, T Control Robotics: The Procedural Control of Physcial 
      Processes, Proceedings of the IFIP Congress, 1974.

Optimal scheduling of periodic tasks with arbitrary communication 
requirements on multiprocessor systems with differing speeds is believed 
to be NP-Hard.  Optimal scheduling of tasks with arbitrary arrival
times on such a system is believed to be impossible.  Several papers 
have discussed partitioning schemes to statically allocate tasks to specific 
processors which are individually scheduled according to a rate monotonic 
or shortest deadline first algorithms.

  S. Davari and S. K. Dahl, An On Line Algorithm for Real-Time Tasks 
     Allolcation, IEEE Real Time Symposium December, 1986.

  J. A. Bannister and K. S. Trivedi, Task Allocation in Fault-Tolerant 
     Distributed Systems, ACTA Informatica, 1983.

  S. K. Dahl and C. L. Lui, On a Real-Time Scheduling Problem,
     Operations Research, 26(1), 1978

Many researchers have developed heuristic algorithms for scheduling
tasks accross multiprocessor or distributed systems.  Some of the more
recent works on adaptave scheduling algorithms I don't seem to have
references for on disk (if you are really interested send me mail).

  C. D. Locke, H. Tokuda, and  E. D. Jensen, A Time-Driven Scheduling
     Model for Real-Time Operating Systems.  Technical Report #????,
     Carnegie Mellon University, 1985.
  
  K. Ramaritham and J. A. Stankovic, Dynamic Task Scheduling in Hard
     Real-Time Distributed Systems, IEEE Software, 1(3), 1984.

  W. Zhao, K. Ramamritham, and J. A. Stankovic, Scheduling Tasks with
     Resource Requirements in Hard Real-Time Systems, IEEE
     Transactions on Software Engineering, SE-12(5), 1987.

  W. Zhao, K. Ramamritham, and J. A. Stankovic, Preemptive Scheduling
     Under Time and Resource Constraints, IEEE Transactions on
     Computers, 36(8), 1987.

  J. Blazewicz, M. Drabowski, and J. Weglarz, Scheduling Multiprocessor 
     Tasks to Minimize Scheduling Length, IEEE Transactions on Computers,
     35(5), 1986.

In general, the proceedings of the IEEE Real-Time Systems Symposia are
good sources for information on real-time scheduling.   The IEEE has also
published a "Tutorial on Hard Real-Time Systems" that is excelent.


Good Luck, and keep us informed of any findings.

-- 
--
Tom Quiggle                     TeleSoft                  (619)457-2700x158

UUNET: ucsd!telesoft!tom                   ARPA:  quigglet@ajpo.sei.cmu.edu

  I worry whoever thought up the term "quality control"
  thought if we didn't control it, it would get out of hand.
         -- Trudy in Jayne Wagner's _The Search for Signs of Intelligent 
	     Life in the Universe_