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

摘要

Given a task set T, determining the number of processors leading to a feasible schedule for Tis 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.