Deterministic Processor Scheduling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Deterministic Processor Scheduling

Full text

Pdf (2.86 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 9 , Issue 3 (September 1977) table of contents

Pages: 173 - 204

Year of Publication: 1977

ISSN:0360-0300

Author

Mario J. Gonzalez, Jr.

Division of Mathematics, Computer Sciences and System Design, The University of Texas at San Antonio, San Antonio, Texas

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 84, Citation Count: 41

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/356698.356700 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	Thomas L. Adam , K. M. Chandy , J. R. Dickson, A comparison of list schedules for parallel processing systems, Communications of the ACM, v.17 n.12, p.685-690, Dec 1974 [doi>10.1145/361604.361619]
	2	J. L. Baer, A Survey of Some Theoretical Aspects of Multiprocessing, ACM Computing Surveys (CSUR), v.5 n.1, p.31-80, March 1973 [doi>10.1145/356612.356615]
	3	J. Bruno , E. G. Coffman, Jr. , R. Sethi, Scheduling independent tasks to reduce mean finishing time, Communications of the ACM, v.17 n.7, p.382-387, July 1974 [doi>10.1145/361011.361064]
	4	BUSSELL, B.; FERNANDEZ, E.; AND LEVY, O. "Optimal scheduhng for homogeneous multiprocessors," m Proc. IFIP Congress 74, North-Holland Publ. Co., Amsterdam, Amencan Elsevier, N.Y., 1974, 286-290.
	5	BUTEN, R. E.; AND SHEN, V. Y "A scheduling model for computer systems with two classes of processors," in Proc. 1973 Sagamore Computer Conf, on Parallel Processing, Springer-Verlag, N.Y., 1973, 130-138.
	6	CHANDY, K. M.; AND DICKSON, J. R. "Scheduhng umdentical processors in a stochastic environment," m Proc. IEEE COMPCON 1972, IEEE, N Y, 1972, 171-174.
	7	N. F. Chen , C. L. Liu, On a Class of Scheduling Algorithms for Multiprocessors Computing Systems, Proceedings of the Sagamore Computer Conference on Parallel Processing, p.1-16, August 20-23, 1974
	8	CLARK, D. Scheduhng ~ndependent tasks on non-~dent~cal parallel machines to m~n~m~ze mean flow-t~me, Dept. of Computer Science, Carnegie-Mellon Univ., Pittsburgh, Pa , June 1974.
	9	Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
	10	COFFMAN, E G., JR.; AND GRAHAM, R. L "Ophmal scheduhng for two processor systems," Acta Informat~ca 1 (1972), 200-213
	11	CONWAY, R. W.; MAXWELL, W. L.; AND MILLER, L. W. Theory of schedultng, Addzson-Wesley Publ. Co. Inc, Reading, Mass., 1967.
	12	FERNANDEZ, E B.; AND BUSSEL, B. "Bounds on the number of processors and time for mulhprocessor optimal schedule," IEEE Trans. Comp C22, 8 (August 1973), 745-751
	13	FINEBERG, M S ; AND SERLIN, O "Multlprogramming for hybrid computation," in Proc AFIPS 1967 Fall Jt Computer Conf , Thompson Book Co., Washington, D C., 1967, 1-13.
	14	FuJII, M.; KASAMI, T.; AND NINOMIYA, K. "Optimal sequencing of two eqmvalent processors," SIAM J Appl Math. 17, 4 (July 1969), 784-789.
	15	Erratum SIAM J. Appl Math. 20, 1 (Jan. 1971), 141.
	16	M. R. Garey , R. L. Grehem, Bounds on scheduling with limited resources, Proceedings of the fourth ACM symposium on Operating system principles, p.104-111, January 1973
	17	GRAHAM, R. L. "Bounds for certain multiprocessing anomalies," Bell Syst. Tech. J. 45 (1966), 1563-1581.
	18	GRAHAM, R. L "Bounds on certain multlprocessmg anomalies," SIAM J Appl. Math 17, 2 (March 1969), 416-429.
	19	GRAHAM, R L "Bounds on multiprocessing anomahes and packing algorithms," in Proc AFIPS 1972 Spring Jt. Computer Conf., AFIPS Press, Montvale, N.J., 1972, 205-217.
	20	Hu, T. C. ~'Parallel sequencing and assembly line problems," Operations Research 9, 6 (1961), 841-848.
	21	JOHNSON, S. M. "Optimal two- and threestage production schedules with setup times included," Nay. Res. Log. Quart. 1, 1 (March 1954).
	22	D. G. Kafura , V. Y. Shen, Scheduling independent processors with different storage capacities, Proceedings of the 1974 annual conference, p.161-166, January 1974 [doi>10.1145/800182.810397]
	23	KAUFMAN, M.T. "An almost-ophmal algorithm for the assembly line scheduhng hne scheduling problem," IEEE Trans. Comp.C- 23, 11 (Nov. 1974), 1169-1174.
	24	KRONE, M. "Heuristic programming apphed to scheduling models," in Proc Fzflh Annual Princeton Conf. Mathematwal Programming, Princeton Univ. Press, Princeton, N.J., 1971, 193-195
	25	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 [doi>10.1145/321738.321743]
	26	Jane W. S. Liu , Ai-Tsung Yang, Optimal scheduling of independent tasks on heterogeneous computing systems, Proceedings of the 1974 annual conference, p.38-45, January 1974 [doi>10.1145/800182.810377]
	27	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]
	28	MCNAUGHTON, R. "Scheduling with deadlines and loss functions," Management Science 6, 1 (Oct. 1969), 1-12.
	29	MUNTZ, R. R.; AND COFFMAN, E. G. JR. "Optimal preemptive scheduling on twoprocessor systems," IEEE Trans Comp C-18, 11 (Nov. 1969), 1014-1020.
	30	R. R. Muntz , E. G. Coffman, Jr., Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems, Journal of the ACM (JACM), v.17 n.2, p.324-338, April 1970 [doi>10.1145/321574.321586]
	31	RAMAMOORTHY, C V.; AND GONZALEZ, M j. "A survey of techniques for recognizing parallel processable streams m computer programs," In Proc AFIPS 1969 Fall Jt. Computer Conf., AFIPS Press, Montvale, N.J., 1969, 1-15.
	32	RAMAMOORTHY, C. V; CHANDY, K M.; AND GONZALEZ, M.d. "Optimal scheduling strategies In a multlprocessor system," IEEE Trans. Comp. C-21, 2 (Feb. 1972), 137-146.
	33	REDDI, S. S.; AND RAMAMOORTHY, C. V. "Some asp, ects of flow-shop sequencing problem," in t'roc. S~xth Annual Princeton Conf Mathematical Programming, Princeton Unlv. Press, Princeton, N.J., 1972, 650-654.
	34	S. S. Reddi, Analytic and Implementation Considerations of Two-Facility Sequencing in Computer Systems, Proceedings of the Sagamore Computer Conference on Parallel Processing, p.205-206, August 20-23, 1974
	35	RICHARDS, P. T~m~ng properties of mult~processor systems, Tech. Paper, Rep. No. TD-B60- 27, Technical Operations, Inc., Burhngton, Mass. August 1960.
	36	SERLIN, O. "Scheduling of time crltlcalprocesses," in Proc. AFIPS 1972 Spring Jt Computer Conf., AFIPS Press, Montva}e, N.J., 1972, 925-932.
	37	SHEN, V. Y.; AND CHEN, Y.E. "A scheduhng strategy for the flow-shop problem in a system with two classes of processors," in Proc S~xth Annual Princeton Conf. Mathematical Pro- ~ amm~ng, Princeton Univ. Press, Princeton, .J., 1972, 645-649.
	38	Soil J.W. "Scheduling strategies for periodic jobs in a multiprocessor environment," PhD Dissertation, Computer Sciences Dept., Northwestern Umv., Evanston, Ill. August 1974.
	39	J. D. Ullman, Polynomial complete scheduling problems, Proceedings of the fourth ACM symposium on Operating system principles, p.96-101, January 1973
	40	Andrew Chi-Chih Yao, Scheduling Unit-Time Tasks with Limited Resources, Proceedings of the Sagamore Computer Conference on Parallel Processing, p.17-36, August 20-23, 1974
	41	GONZAL~Z, M. J.; ANY SOH, J W. "Periodic job scheduling m a distributed processor system," IEEE Trans. Aerospace and Electronw Systems AES-12, 5 (Sept. 1976), 530-536.
	42	COFFMAN, E G., JR. (Ed.), Computer and JsOb-shop scheduling theory, John Wiley & ons, N.Y., 1976
	43	REDDI, S. S.; AND RAMAMOORTHY, C.V. 'tOn the flow-shop sequencing problem with no walt in process," OperaaonaZ Research Quarterly 23, 3 (Sept 1972), 323-331.
	44	REDDI, S. S.; AND RAMAMOORTHY, C. V. "A scheduling problem," Operational Research Quarterly 24, 3 (Sept. 1973), 441-446.
	45	GILMORE, P. C.; AND GOMORY, R. E. "Sequencing a one state-variable machine: A solvable case of the travehng salesman problem," Operations Research (Sept-Oct 1964), 655-679.
	46	Yoichi Muraoka, Parallelism exposure and exploitation in programs, 1971
	47	KOHLER, WALTER H. "A preliminary evaluation of the critical path method for scheduhng tasks on multiprocessor systems," IEEE Trans Comp. (Dec. 1975), 1235-1238.
	48	Shui Lam , Ravi Sethi, Analysis of a level algorithm for preemptive scheduling, Proceedings of the fifth ACM symposium on Operating systems principles, p.178-186, November 19-21, 1975, Austin, Texas, United States
	49	Edward G. Coffman, Jr., A Survey of Mathematical Results in Flow-Time Scheduling for Computer Systems, Gesellschaft für Informatik e.V., 3. Jahrestagung, p.25-46, October 08-10, 1973
	50	COFFMAN, E. G., JR.; AND SETHI, R. "Algorithms minimizing mean flow time: scheduling length properties," Acta Informatica 1 (1976), 1-14.
	51	EASTMAN, W L.; EVEN, S; AND ISAACS, I. H. "Bounds for the optimal scheduling of n jobs on m processors," Management Science, (Nov. 1964), 268-279.
	52	Peter J. Denning , G. Scott Graham, A note on sub-expression ordering in the execution of arithmetic expressions, Communications of the ACM, v.16 n.11, p.700-702, Nov. 1973 [doi>10.1145/355611.362545]
	53	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	54	KARP, R.M. "Reducibdlty among combinatorial problems," in Complexity of computercomputation, R. E. Miller and J. W. Thatcher (Eds.), Plenum Press, N.Y., 1972, 85-104.

CITED BY 41

	Richard K. Acree , David T. Croley , Nasr Ullah , Mario J. Gonzalez , Darioush M. Samani, Parallelization and analysis of a linear adaptive filtering algorithm, Proceedings of the 1993 ACM/SIGAPP symposium on Applied computing: states of the art and practice, p.165-172, February 14-16, 1993, Indianapolis, Indiana, United States
	Subrata Dasgupta, The Organization of Microprogram Stores, ACM Computing Surveys (CSUR), v.11 n.1, p.39-65, March 1979
	B. Ramakrishna Rau , Christopher D. Glaeser , Raymond L. Picard, Efficient code generation for horizontal architectures: Compiler techniques and architectural support, ACM SIGARCH Computer Architecture News, v.10 n.3, p.131-139, April 1982
	Jia Xu , David Lorge Parnas, On satisfying timing constraints in hard-real-time systems, ACM SIGSOFT Software Engineering Notes, v.16 n.5, p.132-146, Dec. 1991
	David Landskov , Scott Davidson , Bruce Shriver , Patrick W. Mallett, Local Microcode Compaction Techniques, ACM Computing Surveys (CSUR), v.12 n.3, p.261-294, Sept. 1980
	J.-J. Shieh , C. Papachristou, On reordering instruction streams for pipelined computers, ACM SIGMICRO Newsletter, v.20 n.3, p.199-206, Sep. 1989
	B. R. Rau , C. D. Glaeser, Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing, ACM SIGMICRO Newsletter, v.12 n.4, p.183-198, Dec. 1981
	Stephen W. Turner , Lionel M. Ni , Betty H. C. Cheng, Time and/or space sharing in a workstation cluster environment, Proceedings of the 1994 conference on Supercomputing, p.630-639, December 1994, Washington, D.C., United States
	Dannie Durand , Ravi Jain , David Tseytlin, Applying randomized edge coloring algorithms to distributed communication: an experimental study, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.264-274, June 24-26, 1995, Santa Barbara, California, United States
	Christos H. Papadimitriou , Paris C. Kanellakis, Flowshop scheduling with limited temporary storage, Journal of the ACM (JACM), v.27 n.3, p.533-549, July 1980
	K. H. Kim , Mahmoud Naghibzadeh, Prevention of task overruns in real-time non-preemptive multiprogramming systems, ACM SIGMETRICS Performance Evaluation Review, v.9 n.2, p.267-276, Summer 1980
	Emilio Luque , Ana Ripoll , Porfidio Hernández , Tomás Margalef, Impact of task duplication on static-scheduling performance in multiprocessor systems with variable execution-time tasks, ACM SIGARCH Computer Architecture News, v.18 n.3b, p.439-446, Sept. 1990
	Alan Ross , Herschel H. Loomis, Jr., Computer aided design of microprocessor-based systems, Proceedings of the 15th conference on Design automation, p.227-230, June 19-21, 1978, Las Vegas, Nevada, United States
	B. R. Rau , C. D. Glaeser , E. M. Greenawalt, Architectural support for the efficient generation of code for horizontal architectures, ACM SIGARCH Computer Architecture News, v.10 n.2, p.96-99, March 1982
	J. Xu , D. L. Parnas, On Satisfying Timing Constraints in Hard-Real-Time Systems, IEEE Transactions on Software Engineering, v.19 n.1, p.70-84, January 1993
	James O. Achugbue , Francis Y. Chin, Bounds on Schedules for Independent Tasks with Similar Execution Times, Journal of the ACM (JACM), v.28 n.1, p.81-99, Jan. 1981
	Mary L. Bailey , Jack V. Briner, Jr. , Roger D. Chamberlain, Parallel logic simulation of VLSI systems, ACM Computing Surveys (CSUR), v.26 n.3, p.255-294, Sept. 1994
	T. L. Casavant , J. G. Kuhl, A taxonomy of scheduling in general-purpose distributed computing systems, IEEE Transactions on Software Engineering, v.14 n.2, p.141-154, February 1988
	E. S. H. Hou , N. Ansari , H. Ren, A Genetic Algorithm for Multiprocessor Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.5 n.2, p.113-120, February 1994
	Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999
	Hesham H. Ali , Hesham El-Rewini, Scheduling interval ordered tasks on multiprocessor architecture, Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990's, p.792-797, March 1992, Kansas City, Missouri, United States
	Stephen W. Turner , Lionel M. Ni , Betty H. C. Cheng, Time and/or space sharing in a workstation cluster environment, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
	John W. Chinneck , Vitoria Pureza , Rafik A. Goubran , Gerald M. Karam , Marco Lávoie, A fast task-to-processor assignment heuristic for real-time multiprocessor DSP applications, Computers and Operations Research, v.30 n.5, p.643-670, April 2003
	Soonhoi Ha , Edward A. Lee, Compile-Time Scheduling of Dynamic Constructs in Dataflow Program Graphs, IEEE Transactions on Computers, v.46 n.7, p.768-778, July 1997
	J. Xu, Multiprocessor Scheduling of Processes with Release Times, Deadlines, Precedence, and Exclusion Relations, IEEE Transactions on Software Engineering, v.19 n.2, p.139-154, February 1993
	Randall G. Karl , T. Leo Lo , Daniel C. St. Clair, Effects of nonsymmetric release times on rate monotonic scheduling, Proceedings of the 1993 ACM conference on Computer science, p.52-59, February 16-18, 1993, Indianapolis, Indiana, United States
	M. Al-Mouhamed, Analysis of Macro-Dataflow Dynamic Scheduling on Nonuniform Memory Access Architectures, IEEE Transactions on Parallel and Distributed Systems, v.4 n.8, p.875-888, August 1993
	V. Chaudhary , J. K. Aggarwal, A Generalized Scheme for Mapping Parallel Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.4 n.3, p.328-346, March 1993
	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
	Salvatore Cavalieri , Antonella Di Stefano , Orazio Mirabella, Pre-Run-Time Scheduling to Reduce Schedule Length in the FieldBus Environment, IEEE Transactions on Software Engineering, v.21 n.11, p.865-880, November 1995
	Michael G. Norman , Peter Thanisch, Models of machines and computation for mapping in multicomputers, ACM Computing Surveys (CSUR), v.25 n.3, p.263-302, Sept. 1993
	Houssine Chetto , Maryline Chetto, Some Results of the Earliest Deadline Scheduling Algorithm, IEEE Transactions on Software Engineering, v.15 n.10, p.1261-1269, October 1989
	Yu-Kwong Kwok , Ishfaq Ahmad, Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.506-521, May 1996
	Rachid Guerraoui , Maurice Herlihy , Bastian Pochon, Toward a theory of transactional contention managers, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Yiu-Wing Leung, Processor Assignment and Execution Sequence for Multiversion Software, IEEE Transactions on Computers, v.46 n.12, p.1371-1377, December 1997
	Jack S. N. Jean , Karen Tomko , Vikram Yavagal , Jignesh Shah , Robert Cook, Dynamic Reconfiguration to Support Concurrent Applications, IEEE Transactions on Computers, v.48 n.6, p.591-602, June 1999
	Jia Xu , David Parnas, Scheduling Processes with Release Times, Deadlines, Precedence and Exclusion Relations, IEEE Transactions on Software Engineering, v.16 n.3, p.360-369, March 1990
	Peter Hibbard, Multiprocessor software design, Proceedings of the ACM 1980 annual conference, p.527-536, January 1980
	Hassan Rajaei , Mohammad Dadfar , Pankaj Joshi, Simulation of job scheduling for small scale clusters, Proceedings of the 37th conference on Winter simulation, December 03-06, 2006, Monterey, California
	Qin Zheng , Bharadwaj Veeravalli , Chen-Khong Tham, Fault-tolerant scheduling for differentiated classes of tasks with low replication cost in computational grids, Proceedings of the 16th international symposium on High performance distributed computing, June 25-29, 2007, Monterey, California, USA
	Qin Zheng , Bharadwaj Veeravalli, On the design of communication-aware fault-tolerant scheduling algorithms for precedence constrained tasks in grid computing systems with dedicated communication devices, Journal of Parallel and Distributed Computing, v.69 n.3, p.282-294, March, 2009