Static multiprocessor scheduling of periodic real-time tasks with precedence constraints and communication costs

Hawaii, USA January 04-January 07

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/HICSS.1995.375468

28th Hawaii International Conference ...

	This Article
	PURCHASE ARTICLE: $0 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by S. Ronngren Articles by B.A. Shirazi

	ASCII Text	x
	S. Ronngren, B.A. Shirazi, "Static multiprocessor scheduling of periodic real-time tasks with precedence constraints and communication costs," Hawaii International Conference on System Sciences, pp. 143, 28th Hawaii International Conference on System Sciences (HICSS'95), 1995.

	BibTex	x
	@article{ 10.1109/HICSS.1995.375468, author = {S. Ronngren and B.A. Shirazi}, title = {Static multiprocessor scheduling of periodic real-time tasks with precedence constraints and communication costs}, journal ={Hawaii International Conference on System Sciences}, volume = {0}, year = {1995}, issn = {1060-3425}, pages = {143}, doi = {http://doi.ieeecomputersociety.org/10.1109/HICSS.1995.375468}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Hawaii International Conference on System Sciences TI - Static multiprocessor scheduling of periodic real-time tasks with precedence constraints and communication costs SN - 1060-3425 SP EP A1 - S. Ronngren, A1 - B.A. Shirazi, PY - 1995 KW - processor scheduling; real-time systems; resource allocation; multiprocessing systems; communication complexity; static multiprocessor scheduling; periodic real-time tasks; precedence constraints; communication costs; task allocation; multiprocessor architecture; timing constraints; NP-complete; scheduling methods; large task sets; exclusion relation; precedence relations; mutual exclusion; heuristic scheduling algorithms; clustering VL - 0 JA - Hawaii International Conference on System Sciences ER -

S. Ronngren, Dept. of Comput. Sci. Eng., Texas Univ., Arlington, TX, USA

B.A. Shirazi, Dept. of Comput. Sci. Eng., Texas Univ., Arlington, TX, USA

The problem of allocating and scheduling real-time tasks, with precedence constraints and communication costs on a multiprocessor architecture in order to meet the timing constraints is known to be NP-complete. Due to the growing complexity of real-time applications there is a need to find scheduling methods that can handle large task sets in a reasonable time. Also, scheduling methods should consider precedence and exclusion relations in order to support parallelism within tasks and to resolve mutual exclusion situations. In this paper four heuristic scheduling algorithms are developed and evaluated. In particular clustering vs. non-clustering techniques are investigated with some interesting results.

Index Terms:

processor scheduling; real-time systems; resource allocation; multiprocessing systems; communication complexity; static multiprocessor scheduling; periodic real-time tasks; precedence constraints; communication costs; task allocation; multiprocessor architecture; timing constraints; NP-complete; scheduling methods; large task sets; exclusion relation; precedence relations; mutual exclusion; heuristic scheduling algorithms; clustering

Citation:

S. Ronngren, B.A. Shirazi, "Static multiprocessor scheduling of periodic real-time tasks with precedence constraints and communication costs," hicss, pp.143, 28th Hawaii International Conference on System Sciences (HICSS'95), 1995

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.