walden@dip.eecs.umich.edu (Eugene Marvin Walden) (08/22/90)
Not Available)
Organization: University of Michigan EECS Dept., Ann Arbor, MI
Date: Tue, 21 Aug 90 21:16:18 GMT
It's me again. I've received a few requests for info on real-time systems
and references, so I figured there is enough interest to warrant posting the
info. First, two books to recommend:
_Tutorial: Hard Real-Time Systems_ by Stankovic and Ramamritham
ISBN 0-8186-0819-6
Computer Society Order Number 819
IEEE Catalog Number 88-70419
Order from:
Computer Society of the IEEE
Terminal Annex
Post Office Box 4699
Los Angeles, CA 90080
_Real-Time System Design_ by Shem-Tov Levi and Ashok Agrawala
ISBN 0-07-037491-0
Published by McGraw-Hill
Finally, here are some references that I have compiled over the last year or
so. The starred articles are the ones that were particularly well-written,
IMHO.
References
* [1] Chang, H-Y., and Livny, M., "Distributed Scheduling under Deadline
Constraints: A Comparison of Sender-Initiated and Receiver-Initiated
Approaches," IEEE Real-Time Systems Symposium, 1986.
[2] Cheng, S., Stankovic, J. A., and Ramamrithram, K., "Dynamic
Scheduling of Groups of Tasks with Precedence Constraints in Distributed Hard
Real-Time Systems," IEEE Real-Time Systems Symposium, 1986.
[3] Chu, W. W., "Task Allocation and Precedence Relations for Distributed
Real-Time Systems," IEEE Transactions On Computers, June 1987.
[4] Coulas, M. F., MacEwen, G. H., and Marquis, G., "RNet: A Hard
Real-Time Distributed Programming System," IEEE Transactions on Computers, Aug
1987.
[5] Damm, A., Reisinger, J., Schwabl, W., and Kopetz, H., "The Real-Time
Operating System of MARS," SIGOPS, July 1989.
[6] Goodenough, J. B., and Sha, L., "Real-Time Scheduling Theory and ADA,"
1989 Workshop on Operating Systems for Mission-Critical COmputing, Aug 1989.
[7] Gopinath, P., and Schwan, K., "CHAOS: Why One Cannot Have Only an Operating
System for Real-Time Applications," SIGOPS, July 1989.
*[8] Graham, R. L. et al., "Optimization and Appoximation in Deterministic
Sequencing and Scheduling: A Survey," Ann. Discrete Math., vol 5, 1979.
[9] Jahanian, F., and Mok, A. K-L., "A Graph-Theoretic Approach for Timing
Analysis and its Implementation," IEEE Transactions on Computers, Aug 1987.
* [10] Jensen, E. D. , et al., "Alpha: An Operating System for the
Mission-Critical Integration and Operation of Large, Complex, Distributed Real-
Time Ststems," 1989 Workshop on Operating Systems for Mission-Critical Comput-
ing, Aug 1989.
[11] Kandlur, D. D., Kiskis, D. L., and Shin, K. G.,"HARTOS: A Distributed
Real-Time Operating System," SIGOPS, July 1989.
[12] Kiskis, D., L., "A Dissertation Proposal on the Design,
Implementation, and Application of Synthetic Workloads for Real-Time Systems,"
March 1990.
[13] Krishna, C. M., Shin, K., and Bhandari, I. S., "Processor Tradeoffs in
Distributed Real-Time Systems," IEEE Transactions on Computers, Sept 1987.
* [14] Lehoczky, J. P., Sha, L., and Strosnider, J. K., "Enhanced Aperiodic
Responsiveness in Hard Real-Time Environments," IEEE Real-Time Systems
Symposium, 1987.
* [15] Leinbaugh, D. W., "Guaranteed Response Times in a Hard Real-Time
Environment," IEEE Transactions on Software Engineering, Jan 1980.
[16] Levi, S-T., Tripathi, S. K., Carson, S. D., and Agrawala, A. K., "The
MARUTI Hard Real-Time Operating System," SIGOPS, July 1989.
* [17] Liu, C. L., and Layland, J. W., "Scheduling Algorithms for Multiprogram-
ming in a Hard Real-Time Environment," Journal of the ACM, Jan 1973.
* [18] Liu, J., Lin, K-J., and Natarajan, S., "Scheduling Real-Time, Periodic
Jobs Using Imprecise Results," IEEE Real-Time Systems Symposium, 1987.
[19] Liu, J., Lin, K-J., Liu, C. L., and Gear, C. W. , "Research
on Imprecise Computation in Project QuartZ,"1989 Workshop on Operating Systems
for Mission-Critical Computing, Aug 1989.
[20] Mok, A. K., and Dertouzos, M. L., "Multiprocessor Scheduling in a Hard
Real-Time Environment," Proc. Seventh Texas Conference on Computing Systems,
1978.
[21] Saponas, T. G., and Demuth, R. B., "The Distributed iRMX Operating
System: A Real-Time Distributed Operating System," 1989 Workshop on Operating
Systems for Mission-Critical COmputing, Aug 1989.
* [22] Sha, L., Lehoczky,J. P.,and Rajkumar, R., "Solutions for some Practical
Problems in Prioritized Preemptive Scheduling," IEEE Real-Time Systems Sympo-
sium, 1986.
[23] Shih, W-K., Liu, J. W. S., Chung, J-Y., and Gillies, D. W., "Sched-
uling Tasks with Ready Times and Deadlines to Minimize Average Error," SIGOPS,
July 1989.
* [24] Stankovic, J., "Evaluation of a Flexible Task Scheduling Algorithm for
Distributed Hard Real-Time Systems", IEEE Transactions on Computers, December
1985.
* [25] Stankovic, J. A., "Misconceptions about Real-Time Computing: A Serious
Problem for Next-Generation Systems," IEEE Computer, Oct 1988.
[26] Stankovic, J. A., and Ramamrithram, K., "The Spring Kernel: A New Para-
digm for Real-Time Operating Systems," SIGOPS, July 1989.
* [27] Tokuda, H., and Mercer, C., "ARTS: A Distributed Real-Time Kernel,"
SIGOPS, July 1989.
* [28] Tokuda, H., Wendorf, J. W., and Wang, H-Y., "Implementation of a Time-
Driven Scheduler for Real-Time Operating Systems," IEEE Real-Time Systems
Symposium, 1987.
[29] Woodbury, M. H., and Shin, K. G., "Workload Effects on Fault Latency
for Real-Time Computing Systems," IEEE Real-Time Systems Symposium, 1987.
[30] Woodside, C. M., and Craig, D. W., "Local Non-Preemptive Scheduling
Policies for Hard Real-Time Distributed Systems," IEEE Real-Time Systems Sympo-
sium, 1987.
[31] Zhao, W., Ramamrithram, K., and Stankovic, J. A., "Preemptive Scheduling
Under Time and Resource Constraints," IEEE Transactions on Computers, Aug
1987.
----------------
[] Blazewicz, J., Drabowski, M., and Weglarz, J., "Scheduling
Multiprocessor Tasks to Minimize Schedule Length," IEEE Transactions
on Computers, May 1986.
[] Ma, P. Y. R., Lee, E. Y. S., and Tsuchiya, M., "A Task Allocation Model
for Distributed Computing Systems," IEEE Transactions on Computers,
Jan 1982.
* [] Hu, T. C., "Parallel Sequencing and Assembly Line Problems," Operations
Research, 9, 1961.
[] Towsley, D., "Allocating Programs Containing Branches and Loops Within
a Multiple Processor System," IEEE Transactions on Software
Engineering, Oct. 1986.
[] Eager, D. L., Lazowska, E. D., and Zahorjan, J., "Adaptive Load
Sharing in Homogeneous Distributed Systems," IEEE Transactions on
Software Engineering, May 1986.
[] Dhall, S. K., and Liu, C. L., "On a Real-Time Scheduling Problem,"
Operations Research, Jan. 1978.
[] Kise, H., Ibaraki, T., and Mine, H., "A Solvable Case of the One-
Machine Scheduling Problem with Ready and Due Times," Operations
Research, Jan. 1978.
* [] Garey, M. R., Graham, R. L., and Johnson, D. S., "Performance
Guarantees for Scheduling Algorithms," Operations Research, Jan. 1978.
[] Erschler, J., Fontan, G., Merce, C., and Roubellat, F., "A New Dominace
Concept in Scheduling n Jobs on a Single Machine with Ready Times and
Due Dates," Operations Research, Jan 1983.
[] Simons, B., and Sipser, M., "On Scheduling Unit-Length Jobs with
Multiple Release Time/Deadline Intervals," Operations Research, Jan.
1984.
* [] Manacher, G. K., "Production and Stabilization of Real-Time Task
Schedules," Journal of the ACM, July 1967.
[] Martel, C., "Preemptive Scheduling with Release Times, Deadlines, and
Due Times," Journal of the ACM, July, 1982.
* [] Muntz, R. R., and Coffman, E. G., "Preemptive Scheduling of Real-Time
Tasks on Multiprocessor Systems," Journal of the ACM, April, 1970.
[] Dolev, D., Upfal, E., and Warmuth, M. K., "The Parallel Complexity of
Scheduling with Precedence Constraints," Journal of Parallel and
Distributed Computing, 3, 1986.
[] Mirchandaney, R., and Stankovic, J. A., "Using Stochastic Learning
Automata for Job Scheduling in Distributed Processing Systems," Journal
of Parallel and Distributed Computing, 3, 1986.
[] Ullman, J. D., "NP-Complete Scheduling Problems," Journal of Computer
and System Sciences, Oct. 1975.
[] Zhao, W., and Ramamritham, K., "Simple and Integrated Heuristic
Algorithms for Scheduling Tasks with Time and Resource Constraints,"
Journal of Systems and Software, July 1987.
[] Lo, V. M., "Heuristic Algorithms for Task Assignment in Distributed
Systems," Proceedings of the International Conference on Distributed
Computing Systems, 1984.
[] Elsayed, E. A., "Algorithms for Project Scheduling with Resource
Constraints," International Journal of Production Research, Jan 1982.
[] Lang, T., and Fernandez, E. B., "Scheduling of Unit-Length Independent
Tasks with Execution Constraints," Information Processing Letters, Jan.
1976.
[] Graham, R. L., "The Combinatorial Mathematics of Scheduling,"
Scientific American, March, 1978.
I am sure you have seen a few of these articles. Some of these are very good
while others are, well... not so good. If I had to assemble a packet of papers
on scheduling to include all of the "landmarks," I would include:
Hu
Manacher
Liu-Layland
Leinbaugh
Although they are old, they are really good papers. If you haven't looked
at all of these, I strongly recommend it. I was surprised to find out how most
of the real-time scheduling theory is rooted in Operations Research. Anyway, I
hope this helps.
- Eugene Walden (walden@dip.eecs.umich.edu)
P.S. The University of Michigan just changed all of the Internet addresses
here, so if you have trouble responding, the Internet address of my
account is 141.212.99.5.