An efficient scheduling algorithm for the non-preemptive independent multiprocessor platform Online publication date: Sat, 20-Dec-2014
by Ştefan Andrei; Albert M.K. Cheng; Gheorghe Grigoraş; Vlad Rădulescu
International Journal of Grid and Utility Computing (IJGUC), Vol. 3, No. 4, 2012
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.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Grid and Utility Computing (IJGUC):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com
Our Blog 
Follow us on Twitter 
Visit us on Facebook