Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems

Full text

Pdf (941 KB)

Source

Journal of the ACM (JACM) archive
Volume 17 , Issue 2 (April 1970) table of contents

Pages: 324 - 338

Year of Publication: 1970

ISSN:0004-5411

Authors

R. R. Muntz	Computer Science Department, University of California, Los Angeles, California and Princeton University, Princeton, New Jersey
E. G. Coffman, Jr.	Princeton University, Princeton, New Jersey

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 60, Citation Count: 27

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321574.321586 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	ESTRIN, G. The organization of computer systems--the fixed plus variable structure computer. Proc. 1960 Western Joint Comput. Conf., Vol. 17, pp. 33-40.
	2	David Frederic Martin, Volume i. the automatic assignment and sequencing of computations on parallel processor systems. volume ii. program listings, 1966
	3	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]
	4	RICHARDS, P. Timing properties of multiprocessor systems. Rep. No. TD-B60-27, Tech. Operations, Inc., Burlington, Mass., Aug. 1960.
	5	GRAHAM, R. L. Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. ~5 (1966), 1563-1581.
	6	G. K. Manacher, Production and Stabilization of Real-Time Task Schedules, Journal of the ACM (JACM), v.14 n.3, p.439-465, July 1967 [doi>10.1145/321406.321408]
	7	MARTIN, D., AND ESTRIN, a . Experiments on models of computations and systems. IEEE Trans. EC-16, 1 (Feb. 1967), 59-69.
	8	MARTIN, D., AND ESTRIN, a . Models of computational systems--cyclic to acyclic graph transformation. IEEE Trans. EC-16, 1 (Feb. 1967), 70-79.
	9	Hu, T.C. Parallel sequencing and assembly line problems. Oper. Res. 9, 6 (Nov. 1961), 841-848.
	10	McNAUGHTON, R. Scheduling with deadlines and loss functions. Manage. Sci. 6, 1 (Oct. 1959), 1-12.
	11	COFFMAN, E. G. Bounds on parallel-processing of queues with multiple-phase jobs. Naval Res. Logistics Quart. 14, 3 (Sept. 1967), 345-366.
	12	Leonard Kleinrock, Sequential Processing Machines (S.P.M) Analyzed With a Queuing Theory Model, Journal of the ACM (JACM), v.13 n.2, p.179-193, April 1966 [doi>10.1145/321328.321329]
	13	CRITCHLOW, A .J . Generalized multiprocessing and multiprogramming systems. Proc. AFIPS 1963 Fall Joint Comput. Conf., Vol. 24, pp. 107-126.

CITED BY 27

	D. G. Kafura , V. Y. Shen, An Algorithm to Design the Memory Configuration of a Computer Network, Journal of the ACM (JACM), v.25 n.3, p.365-377, July 1978
	K. M. Chandy , P. F. Reynolds, Scheduling partially ordered tasks with probabilistic execution times, ACM SIGOPS Operating Systems Review, v.9 n.5, p.169-177, November 1975
	J. L. Baer, A Survey of Some Theoretical Aspects of Multiprocessing, ACM Computing Surveys (CSUR), v.5 n.1, p.31-80, March 1973
	Guo-Jie Li , Benjamin W. Wah, Optimal granularity of parallel evaluation of AND trees, Proceedings of 1986 ACM Fall joint computer conference, p.297-306, November 1986, Dallas, Texas, United States
	K. L. Krause , V. Y. Shen , H. D. Schwetman, Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems, Journal of the ACM (JACM), v.22 n.4, p.522-550, Oct. 1975
	C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973
	Teofilo F. Gonzalez , Donald B. Johnson, A New Algorithm for Preemptive Scheduling of Trees, Journal of the ACM (JACM), v.27 n.2, p.287-312, April 1980
	Shui Lam , Ravi Sethi, Analysis of a level algorithm for preemptive scheduling, ACM SIGOPS Operating Systems Review, v.9 n.5, p.178-186, November 1975
	Teofilo Gonzalez , Sartaj Sahni, Preemptive Scheduling of Uniform Processor Systems, Journal of the ACM (JACM), v.25 n.1, p.92-101, Jan. 1978
	C. L. Liu , James W. Layland, Scheduling algorithms for multiprogramming in a hard-real-time environment, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
	D. G. Kafura , V. Y. Shen, Scheduling independent processors with different storage capacities, Proceedings of the 1974 annual conference, p.161-166, January 1974
	Edward C. Horvath , Shui Lam , Ravi Sethi, A Level Algorithm for Preemptive Scheduling, Journal of the ACM (JACM), v.24 n.1, p.32-43, Jan. 1977
	Mario J. Gonzalez, Jr., Deterministic Processor Scheduling, ACM Computing Surveys (CSUR), v.9 n.3, p.173-204, Sept. 1977
	N. S. Losapio , William G. Bulgren, Simulation of dispatching algorithms in a multiprogramming environment, Proceedings of the ACM annual conference, p.903-913, August 01-01, 1972, Boston, Massachusetts, United States
	Ken Fuchs , Dennis Kafura, Memory-constrained task scheduling on a network of dual processors, Journal of the ACM (JACM), v.32 n.1, p.102-129, Jan. 1985
	Clement T. Yu , Keh-Chang Guh , David Brill , Arbee L. P. Chen, Partition Strategy for Distributed Query Processing in Fast Local Networks, IEEE Transactions on Software Engineering, v.15 n.6, p.780-793, June 1989
	K. Ramamritham , J. A. Stankovic , W. Zhao, Distributed Scheduling of Tasks with Deadlines and Resource Requirements, IEEE Transactions on Computers, v.38 n.8, p.1110-1123, August 1989
	K. L. Krause , V. Y. Shen , H. D. Schwetman, A task-scheduling algorithm for a multiprogramming computer system, ACM SIGOPS Operating Systems Review, v.7 n.4, p.112-118, October 1973
	Qiuhua Cao , John A. Stankovic, Dual face phased array radar scheduling with multiple constraints, Proceedings of the 5th ACM international conference on Embedded software, September 18-22, 2005, Jersey City, NJ, USA
	B. M. Carlson , L. W. Dowdy, Static Processor Allocation in a Soft Real-Time Multiprocessor Environment, IEEE Transactions on Parallel and Distributed Systems, v.5 n.3, p.316-320, March 1994
	Joseph Y. -T. Leung , Haibing Li , Michael Pinedo , Jiawei Zhang, Minimizing total weighted completion time when scheduling orders in a flexible environment with uniform machines, Information Processing Letters, v.103 n.3, p.119-129, July, 2007
	J. Santos , E. Ferro , J. Orozco , R. Cayssials, A Heuristic Approach to the Multitask-Multiprocessor AssignmentProblem using the Empty-Slots Method and Rate Monotonic Scheduling, Real-Time Systems, v.13 n.2, p.167-199, Sept. 1997
	Dennis Kafura, Scheduling tasks with critical sections, Proceedings of the 1977 annual conference, p.381-385, January 1977
	Yumei Huo , Joseph Y. -T. Leung , Xin Wang, Online scheduling of equal-processing-time task systems, Theoretical Computer Science, v.401 n.1-3, p.85-95, July, 2008
	Alain Quilliot, Preemptive scheduling and antichain polyhedra, Discrete Applied Mathematics, v.156 n.17, p.3267-3275, October, 2008
	Omri Serlin, Scheduling of time critical processes, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada
	Pieter Bellens , Josep M. Perez , Felipe Cabarcas , Alex Ramirez , Rosa M. Badia , Jesus Labarta, CellSs: Scheduling techniques to better exploit memory hierarchy, Scientific Programming, v.17 n.1-2, p.77-95, January 2009