Uma abordagem orientada a sistemas para otimização de escalonamento de processos em grades computacionais (2013)
- Authors:
- Autor USP: GABRIEL, PAULO HENRIQUE RIBEIRO - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- Subjects: SISTEMAS DISTRIBUÍDOS; OTIMIZAÇÃO MATEMÁTICA (MODELOS); APRENDIZADO COMPUTACIONAL; COMPUTAÇÃO BIOINSPIRADA
- Keywords: Algoritmos de aproximação; Approximation-based algorithms; Distributed systems; Escalonamento de processos; Escalonamento orientado a sistemas; Grades computacionais; Grid computing; Mathematical optimization model; Modelo de otimização matemática; Process scheduling; Sistemas distribuídos; System-centric scheduling
- Language: Português
- Abstract: Um dos maiores desafios envolvidos no projeto de grades computacionais é o escalonamento de processos, o qual consiste no mapeamento de processos sobre os computadores disponíveis, a fim de reduzir o tempo de execução de aplicações ou maximizar a utilização de recursos. A literatura na área de Sistemas Distribuídos trata, geralmente, esses dois objetivos separadamente, dando origem às abordagens de escalonamento orientado a aplicações e orientado a recursos, respectivamente. Mais recentemente, uma nova abordagem, denominada escalonamento orientado a sistemas, tem recebido destaque, buscando otimizar ambos objetivos simultaneamente. Seguindo essas abordagens, algoritmos heurísticos e de aproximação têm sido propostos. Os heurísticos buscam por soluções de maneira eficiente sem, contudo, apresentar garantias quanto à qualidade das soluções obtidas. Em contrapartida, os algoritmos de aproximação provêm tais garantias, contudo são mais difíceis de serem projetados, o que justifica o fato de haver apenas versões simplificadas desses algoritmos para cenários de escalonamento de processos. A falta de algoritmos de aproximação adequados para abordar o problema de escalonamento de processos e a necessidade de soluções que atendam o escalonamento orientado a sistemas motivaram esta tese de doutorado que apresenta a proposta do Min Heap-based Scheduling Algorithm (MHSA), um algoritmo de aproximação para o problema de escalonamento de processos orientado a sistemas. Esse algoritmo foibaseado em um modelo de otimização matemática proposto no contexto desta tese. Esse modelo considera os comportamentos de processos e recursos a fim de quantificar a qualidade de soluções de escalonamento. O funcionamento do MHSA envolve a construção de uma árvore min-heap, em que os nós representam computadores e as chaves de ordenação correspondem aos tempos de fila, i.e., ocupação dos computadores. Apesar de esse algoritmo primordialmente reduzir o tempo de execução (ou makespan) de aplicações, essa estrutura em árvore permite que qualquer computador que ocupe o nó raiz receba cargas, o que favorece a ocupação de recursos e, portanto, sua orientação a sistemas. Esse algoritmo tem complexidade assintótica de pior caso igual a O(\'log IND. 2 m\'), em que m corresponde ao número de computadores do sistema. Sua razão de aproximação foi estudada para ambientes distribuídos heterogêneos com e sem a presença de comunicação entre processos, o que permite conhecer, a priori, o nível mínimo de qualidade alcançado por suas soluções. Experimentos foram conduzidos para avaliar o algoritmo proposto e compará-lo a outras propostas. Os resultados confirmam que o MHSA reduz o tempo dispendido na obtenção de boas soluções de escalonamento
- Imprenta:
- Publisher place: São Carlos
- Date published: 2013
- Data da defesa: 26.04.2013
-
ABNT
GABRIEL, Paulo Henrique Ribeiro. Uma abordagem orientada a sistemas para otimização de escalonamento de processos em grades computacionais. 2013. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2013. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-03072013-095702/. Acesso em: 02 jan. 2026. -
APA
Gabriel, P. H. R. (2013). Uma abordagem orientada a sistemas para otimização de escalonamento de processos em grades computacionais (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-03072013-095702/ -
NLM
Gabriel PHR. Uma abordagem orientada a sistemas para otimização de escalonamento de processos em grades computacionais [Internet]. 2013 ;[citado 2026 jan. 02 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-03072013-095702/ -
Vancouver
Gabriel PHR. Uma abordagem orientada a sistemas para otimização de escalonamento de processos em grades computacionais [Internet]. 2013 ;[citado 2026 jan. 02 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-03072013-095702/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
