Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.22/3544
Título: Laxity dynamics and LLF schedulability analysis on multiprocessor platforms
Autor: Lee, Jinkyu
Easwaran, Arvind
Shin, Insik
Palavras-chave: Schedulability analysis
Laxity dynamics
LLF (Least Laxity First)
Multiprocessor platforms
Real-time scheduling
Data: 2012
Editora: Springer
Relatório da Série N.º: Real-Time Systems; Vol. 48, Issue 6
Resumo: LLF (Least Laxity First) scheduling, which assigns a higher priority to a task with a smaller laxity, has been known as an optimal preemptive scheduling algorithm on a single processor platform. However, little work has been made to illuminate its characteristics upon multiprocessor platforms. In this paper, we identify the dynamics of laxity from the system’s viewpoint and translate the dynamics into LLF multiprocessor schedulability analysis. More specifically, we first characterize laxity properties under LLF scheduling, focusing on laxity dynamics associated with a deadline miss. These laxity dynamics describe a lower bound, which leads to the deadline miss, on the number of tasks of certain laxity values at certain time instants. This lower bound is significant because it represents invariants for highly dynamic system parameters (laxity values). Since the laxity of a task is dependent of the amount of interference of higher-priority tasks, we can then derive a set of conditions to check whether a given task system can go into the laxity dynamics towards a deadline miss. This way, to the author’s best knowledge, we propose the first LLF multiprocessor schedulability test based on its own laxity properties. We also develop an improved schedulability test that exploits slack values. We mathematically prove that the proposed LLF tests dominate the state-of-the-art EDZL tests. We also present simulation results to evaluate schedulability performance of both the original and improved LLF tests in a quantitative manner.
Peer review: yes
URI: http://hdl.handle.net/10400.22/3544
ISSN: 0922-6443
Versão do Editor: http://link.springer.com/article/10.1007%2Fs11241-012-9157-x
Aparece nas colecções:ISEP – CISTER – Artigos

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