Intra-Type Migrative Scheduling of Implicit-Deadline Sporadic Tasks on Two-Type Heterogeneous Multiprocessor
Ref: HURRAY-TR-110402 Publication Date: 19 to 23, Jun, 2011
Intra-Type Migrative Scheduling of Implicit-Deadline Sporadic Tasks on Two-Type Heterogeneous Multiprocessor
Ref: HURRAY-TR-110402 Publication Date: 19 to 23, Jun, 2011Abstract:
Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a two-type heterogeneous multiprocessor platform. Each processor is either of type-1 or type-2 with each task having different execution time on each processor type. Jobs can migrate between processors of same type (referred to as intra-type migration) but cannot migrate between processors of different types. We present a new scheduling algorithm namely, LP-Relax(THR) which offers a guarantee that if a task set can be scheduled to meet deadlines by an optimal task assignment scheme that allows intra-type migration then LP-Relax(THR) meets deadlines as well with intra-type migration if given processors 1/THR as fast (referred to as speed competitive ratio) where THR <= 2/3.
Gurulingesh Raravi
Björn Andersson
Konstantinos BletsasDocument:
View
Download10th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2011).
Nymburk, Czechia.
Record Date: 1, Apr, 2011