HomePublicationsJournal Paper

Real-Time Scheduling with Resource Sharing on Heterogeneous Multiprocessors
Ref: CISTER-TR-140102       Publication Date: Mar 2014

Abstract:
Consider the problem of scheduling a task set of implicit-deadline sporadic tasks to meet all deadlines on a t-type heterogeneous multiprocessor platform where tasks may access multiple shared resources. The multiprocessor platform has mk processors of type-k, where k € {1, 2, ..., t}. The execution time of a task depends on the type of processor on which it executes. The set of shared resources is denoted by $R$. For each task Ti, there is a resource set Ri (which is a subset of R) such that for each job of task Ti, during one phase of its execution, the job requests to hold the resource set Ri exclusively with the interpretation that (i) the job makes a single request to hold all the resources in the resource set Ri and (ii) at all times, when a job of task Ti holds Ri, no other job holds any resource in Ri. Each job of task Ti may request the resource set Ri at most once during its execution. A job is allowed to migrate when it requests a resource set and when it releases the resource set but a job is not allowed to migrate at other times. Our goal is to design a scheduling algorithm for this problem and prove its performance.
We propose an algorithm, LP-EE-vpr, for scheduling an implicit-deadline sporadic task set on a t-type heterogeneous multiprocessor platform that allows a job to migrate only when it requests or releases a resource set. We also prove its speed competitive ratio. To the best of our knowledge, LP-EE-vpr is the first algorithm with proven speed competitive ratio for real-time scheduling of sporadic tasks with resource sharing on t-type heterogeneous multiprocessors.

Björn Andersson

,

Gurulingesh Raravi

Document:

View
PDF Download
PDF