lamaster@ames.arc.nasa.gov (Hugh LaMaster) (05/03/89)
I am looking for a few good sources on realtime scheduling. I am looking for something that goes beyond obvious simplistic approaches (but not elegantly simple approaches which are particularly prized). An added bonus would be information on mapping complex realtime problems into processes which may be on dedicated hardware, or may share a faster processor with other processes, with the scheduler then required to guarantee that certain processes get enough CPU time soon enough. Information on how to solve problems like this and how the scheduler capabilities interact with the potential solution space are of interest. Is there any reference out there on realtime scheduling that people really like? The answer to any realtime problem is always "buy more hardware" - I am looking for something which tries to answer the question: "What is the least expensive/complex/etc. SYSTEM (hardware and software) that I can buy to solve a particular problem. [This assumes that (the debatable point: please debate it separately :-) ) "realtime" is a subject which has some generalizations to it, and is not entirely a collection of special cases.] Hugh LaMaster, m/s 233-9, UUCP ames!lamaster NASA Ames Research Center ARPA lamaster@ames.arc.nasa.gov Moffett Field, CA 94035 Phone: (415)694-6117
tom@telesoft.UUCP (Tom Quiggle @sation) (05/05/89)
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_