Return to search

Optimal Multiprocessor Real-Time Scheduling via Reduction to Uniprocessor

Submitted by Santos Davilene (davilenes@ufba.br) on 2013-01-25T12:25:33Z
No. of bitstreams: 1
TESE - Paul Regnier.pdf: 1122807 bytes, checksum: 968bc4ff6e54e1d57a2a511a607af27d (MD5) / Made available in DSpace on 2013-01-25T12:25:33Z (GMT). No. of bitstreams: 1
TESE - Paul Regnier.pdf: 1122807 bytes, checksum: 968bc4ff6e54e1d57a2a511a607af27d (MD5) / Neste trabalho de doutorado, propõe-se RUN (Redução para Uniprocessor), um novo algoritmo de escalonamento para conjunto de tarefas periódicas com deadlines implícitas em sistemas multiprocessador de tempo real, nos quais as tarefas possuem restrições tanto no domínio do tempo quanto no domínio de valores. RUN apresenta as seguintes propriedades relevantes:

- RUN é ótimo no sentido que ele produz um escalonamento correto, no qual todas as restrições temporais são atendidas, de qualquer sistemas de tarefas utilizando até 100% dos processadores da plataforma de tempo real;

- RUN usa o conceito-chave do escalonamento do tempo ócio, chamado de escalonamento por dualidade, segundo o qual, em algum instante t, o escalonamento de uma tarefa utiliza tanto o conhecimento de seu tempo de execução restante, bem como o seu tempo ócio restante;

- RUN baseia-se na diminuição do número de tarefas a ser escalonadas pela suas agregações em supertasks, os quais chamamos de servidores, com taxa acumulada não superior a 1. Cada servidor é responsável por escalonar o seu conjunto de tarefas clientes, de acordo com alguma política de escalonamento;

- RUN utiliza o princípio original de justiça global (Gfair), de acordo com o qual cada servidor de um conjunto de tarefas T é garantido de executar por um tempo proporcional à taxa acumulada das tarefas de T entre cada duas deadlines das tarefas de T;

- RUN reduz o problema do escalonamento de um conjunto de tarefas em/m/ processadores no problema equivalente do escalonamento de um ou mais conjuntos de tarefas diferentes em sistemas monoprocessador;

- RUN supera significativamente os algoritmos ótimos existentes em termos de preempções com um limite superior de O(log m) preempções média por jobs em/m/ processadores. / Salvador

Identiferoai:union.ndltd.org:IBICT/oai:192.168.11:11:ri/8152
Date25 January 2013
CreatorsRegnier, Paul Denis Etenne
ContributorsLima, George Marconi de Araújo
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis
Sourcehttp://wiki.dcc.ufba.br/PMCC/PaulRegnier, reponame:Repositório Institucional da UFBA, instname:Universidade Federal da Bahia, instacron:UFBA
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0021 seconds