Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.22/5420
Título: Real-time scheduling with resource sharing on heterogeneous multiprocessors
Autor: Andersson, Björn
Raravi, Gurulingesh
Palavras-chave: Heterogeneous multiprocessors
Real-time scheduling
Resource sharing
Data: 2014
Editora: Springer
Relatório da Série N.º: Real-Time Systems;Vol. 50, Issue 2
Resumo: 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.
Peer review: yes
URI: http://hdl.handle.net/10400.22/5420
DOI: 10.1007/s11241-013-9195-z
ISSN: 0922-6443
1573-1383
Versão do Editor: http://link.springer.com/article/10.1007%2Fs11241-013-9195-z
Aparece nas colecções:ISEP – CISTER – Artigos

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
ART15_CISTER_2014.pdf2,31 MBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.