Provably Good Scheduling of Sporadic Tasks with Resource Sharing on a Two-type Heterogeneous Multiprocessor Platform (Corrected version)
Ref: HURRAY-TR-110904 Publication Date: 12 to 16, Dec, 2011
Provably Good Scheduling of Sporadic Tasks with Resource Sharing on a Two-type Heterogeneous Multiprocessor Platform (Corrected version)
Ref: HURRAY-TR-110904 Publication Date: 12 to 16, Dec, 2011Abstract:
Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a two-type heterogeneous multiprocessor platform where a task may request at most one of |R| shared resources. There are m1 processors of type-1 and m2 processors of type-2. Tasks may migrate only when requesting or releasing resources. We present a new algorithm, FF-3C-vpr, which offers a guarantee that if a task set is schedulable to meet deadlines by an optimal task assignment scheme that only allows tasks to migrate when requesting or releasing a resource, then FF-3C-vpr also meets deadlines if given processors 4+6*ceil(|R|/min(m1,m2)) times as fast. As far as we know, it is the first result for resource sharing on heterogeneous platforms with provable performance.
Gurulingesh Raravi
Björn Andersson
Konstantinos BletsasDocument:
View
Download15th International Conference On Principles Of Distributed Systems (OPODIS'11), Springer Berlin Heidelberg, Edited: Antonio Fernàndez Anta, Giuseppe Lipari, Matthieu Roy, 7109, pp 528-543.
Toulouse, France.
DOI:10.1007/978-3-642-25873-2_36.
Record Date: 23, Sep, 2011