Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.22/5411
Título: An optimal boundary fair scheduling
Autor: Nelissen, Geoffrey
Su, Hang
Guo, Yifeng
Zhu, Dakai
Nélis, Vincent
Goossens, Joel
Palavras-chave: Real-time
Scheduling
Optimal
Discrete-time
Multiprocessor
Fairness
Data: 2014
Editora: Springer
Relatório da Série N.º: Real-Time Systems;Vol. 50, Issue 4,
Resumo: Nowadays, many real-time operating systems discretize the time relying on a system time unit. To take this behavior into account, real-time scheduling algorithms must adopt a discrete-time model in which both timing requirements of tasks and their time allocations have to be integer multiples of the system time unit. That is, tasks cannot be executed for less than one time unit, which implies that they always have to achieve a minimum amount of work before they can be preempted. Assuming such a discrete-time model, the authors of Zhu et al. (Proceedings of the 24th IEEE international real-time systems symposium (RTSS 2003), 2003, J Parallel Distrib Comput 71(10):1411–1425, 2011) proposed an efficient “boundary fair” algorithm (named BF) and proved its optimality for the scheduling of periodic tasks while achieving full system utilization. However, BF cannot handle sporadic tasks due to their inherent irregular and unpredictable job release patterns. In this paper, we propose an optimal boundary-fair scheduling algorithm for sporadic tasks (named BF TeX ), which follows the same principle as BF by making scheduling decisions only at the job arrival times and (expected) task deadlines. This new algorithm was implemented in Linux and we show through experiments conducted upon a multicore machine that BF TeX outperforms the state-of-the-art discrete-time optimal scheduler (PD TeX ), benefiting from much less scheduling overheads. Furthermore, it appears from these experimental results that BF TeX is barely dependent on the length of the system time unit while PD TeX —the only other existing solution for the scheduling of sporadic tasks in discrete-time systems—sees its number of preemptions, migrations and the time spent to take scheduling decisions increasing linearly when improving the time resolution of the system.
Peer review: yes
URI: http://hdl.handle.net/10400.22/5411
DOI: 10.1007/s11241-014-9201-0
ISSN: 0922-6443
1573-1383
Versão do Editor: http://link.springer.com/article/10.1007%2Fs11241-014-9201-0
Aparece nas colecções:ISEP – CISTER – Artigos

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
ART10_CISTER_2014.pdf1,82 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.