Multiprocessor fixed-priority scheduling with restricted interprocessor migrations

Issue title: Real-Time Systems (Euromicro RTS-03)

Article type: Research Article

Authors: Baruah, Sanjoy K. | Carpenter, John

Affiliations: The University of North Carolina, Department of Computer Science, CB 3175 Chapel Hill, NC 27599-3175, USA

Note: [] Corresponding author. E-mail: baruah@cs.unc.edu

Abstract: The priority-driven scheduling of periodic and sporadic task systems upon identical multiprocessor platforms is considered, under the restrictions that (i) each job may be assigned exactly one priority throughout its lifetime, and (ii) each job may execute upon only a single processor. It is shown that feasibility-analysis under these restrictions is intractable (NP-hard in the strong sense). A scheduling algorithm is presented that satisfies these restrictions, and that has a worst-case utilization bound comparable to the worst-case utilization bounds of partitioned scheduling algorithms, and of scheduling algorithms that retain the priority-assignment restriction but allow arbitrary interprocessor migration.

Keywords: Real-time scheduling, multiprocessors, earliest deadline first, restricted interprocessor migration, fixed priorities

Journal: Journal of Embedded Computing, vol. 1, no. 2, pp. 169-178, 2005