Title: An efficient scheduling algorithm for the non-preemptive independent multiprocessor platform

Authors: Ştefan Andrei; Albert M.K. Cheng; Gheorghe Grigoraş; Vlad Rădulescu

Addresses: Department of Computer Science, Lamar University, Beaumont, TX, USA ' Computer Science Department, University of Houston, Houston, TX, USA ' Department of Computer Science, Cuza University of Iaşi, Iaşi, Romania ' Department of Computer Science, Cuza University of Iaşi, Iaşi, Romania

Abstract: Given a task set T, determining the number of processors leading to a feasible schedule for T is an important problem in the real-time embedded systems community. For periodic and independent task sets, the utilisation rate represents a lower bound on the number of processors. Estimation on the lower bound of the number of processors for a single-instance task set was recently presented by Andrei et al. The contribution of this paper is twofold. First, given a single-instance, non-preemptive and independent task set, we improve the lower bound on the number of processors described by Andrei et al., such that there exist no feasible schedules on a multiprocessor platform with fewer processors than this new lower bound. Second, we provide an improved efficient algorithm that finds a feasible schedule of a single-instance non-preemptive and independent task set on a multiprocessor platform, compared to the one from Andrei et al.'s, accompanied by a correctness and complexity result.

Keywords: scheduling algorithms; non-preemptive multiprocessor platforms; independent multiprocessor platforms; lower bounds; processor numbers; real-time embedded systems.

DOI: 10.1504/IJGUC.2012.051422

International Journal of Grid and Utility Computing, 2012 Vol.3 No.4, pp.215 - 223

Received: 22 May 2011
Accepted: 23 Sep 2011
Published online: 20 Dec 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article