Publication
Real-time scheduling with resource sharing on heterogeneous multiprocessors
| dc.contributor.author | Andersson, Björn | |
| dc.contributor.author | Raravi, Gurulingesh | |
| dc.date.accessioned | 2015-01-15T12:33:58Z | |
| dc.date.available | 2015-01-15T12:33:58Z | |
| dc.date.issued | 2014 | |
| dc.description.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 m k 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 τ i , there is a resource set R i ⊆R such that for each job of τ i , during one phase of its execution, the job requests to hold the resource set R i exclusively with the interpretation that (i) the job makes a single request to hold all the resources in the resource set R i and (ii) at all times, when a job of τ i holds R i , no other job holds any resource in R i . Each job of task τ i may request the resource set R i 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, which offers the guarantee that if an implicit-deadline sporadic task set is schedulable on a t-type heterogeneous multiprocessor platform by an optimal scheduling algorithm that allows a job to migrate only when it requests or releases a resource set, then our algorithm also meets the deadlines with the same restriction on job migration, if given processors 4×(1+MAXP×⌈|P|×MAXPmin{m1,m2,…,mt}⌉) times as fast. (Here MAXP and |P| are computed based on the resource sets that tasks request.) For the special case that each task requests at most one resource, the bound of LP-EE-vpr collapses to 4×(1+⌈|R|min{m1,m2,…,mt}⌉). To the best of our knowledge, LP-EE-vpr is the first algorithm with proven performance guarantee for real-time scheduling of sporadic tasks with resource sharing on t-type heterogeneous multiprocessors. | por |
| dc.identifier.doi | 10.1007/s11241-013-9195-z | |
| dc.identifier.issn | 0922-6443 | |
| dc.identifier.issn | 1573-1383 | |
| dc.identifier.uri | http://hdl.handle.net/10400.22/5420 | |
| dc.language.iso | eng | por |
| dc.peerreviewed | yes | por |
| dc.publisher | Springer | por |
| dc.relation.ispartofseries | Real-Time Systems;Vol. 50, Issue 2 | |
| dc.relation.publisherversion | http://link.springer.com/article/10.1007%2Fs11241-013-9195-z | por |
| dc.subject | Heterogeneous multiprocessors | por |
| dc.subject | Real-time scheduling | por |
| dc.subject | Resource sharing | por |
| dc.title | Real-time scheduling with resource sharing on heterogeneous multiprocessors | por |
| dc.type | journal article | |
| dspace.entity.type | Publication | |
| oaire.citation.endPage | 314 | por |
| oaire.citation.startPage | 270 | por |
| rcaap.rights | openAccess | por |
| rcaap.type | article | por |