Autor(es): Correia, João Francisco de Castro Castanho
Data: 2015
Identificador Persistente: http://hdl.handle.net/10400.22/8210
Origem: Repositório Científico do Instituto Politécnico do Porto
Assunto(s): Sistemas multiprocessador; Escalonamento multiprocessador de tempo-real; Escalonamento semi-particionado; Análise de escalonabilidade; Linux; Multiprocessor Systems; Multiprocessor Real-Time Scheduling; Semi-Partitioned Scheduling; Schedulability Analysis; Arquitecturas, Sistemas e Redes
Nos dias de hoje, os sistemas de tempo real crescem em importância e complexidade. Mediante a passagem do ambiente uniprocessador para multiprocessador, o trabalho realizado no primeiro não é completamente aplicável no segundo, dado que o nível de complexidade difere, principalmente devido à existência de múltiplos processadores no sistema. Cedo percebeu-se, que a complexidade do problema não cresce linearmente com a adição destes. Na verdade, esta complexidade apresenta-se como uma barreira ao avanço científico nesta área que, para já, se mantém desconhecida, e isto testemunha-se, essencialmente no caso de escalonamento de tarefas. A passagem para este novo ambiente, quer se trate de sistemas de tempo real ou não, promete gerar a oportunidade de realizar trabalho que no primeiro caso nunca seria possível, criando assim, novas garantias de desempenho, menos gastos monetários e menores consumos de energia. Este último fator, apresentou-se desde cedo, como, talvez, a maior barreira de desenvolvimento de novos processadores na área uniprocessador, dado que, à medida que novos eram lançados para o mercado, ao mesmo tempo que ofereciam maior performance, foram levando ao conhecimento de um limite de geração de calor que obrigou ao surgimento da área multiprocessador. No futuro, espera-se que o número de processadores num determinado chip venha a aumentar, e como é óbvio, novas técnicas de exploração das suas inerentes vantagens têm de ser desenvolvidas, e a área relacionada com os algoritmos de escalonamento não é exceção. Ao longo dos anos, diferentes categorias de algoritmos multiprocessador para dar resposta a este problema têm vindo a ser desenvolvidos, destacando-se principalmente estes: globais, particionados e semi-particionados. A perspectiva global, supõe a existência de uma fila global que é acessível por todos os processadores disponíveis. Este fato torna disponível a migração de tarefas, isto é, é possível parar a execução de uma tarefa e resumir a sua execução num processador distinto. Num dado instante, num grupo de tarefas, m, as tarefas de maior prioridade são selecionadas para execução. Este tipo promete limites de utilização altos, a custo elevado de preempções/migrações de tarefas. Em contraste, os algoritmos particionados, colocam as tarefas em partições, e estas, são atribuídas a um dos processadores disponíveis, isto é, para cada processador, é atribuída uma partição. Por essa razão, a migração de tarefas não é possível, acabando por fazer com que o limite de utilização não seja tão alto quando comparado com o caso anterior, mas o número de preempções de tarefas decresce significativamente. O esquema semi-particionado, é uma resposta de caráter hibrido entre os casos anteriores, pois existem tarefas que são particionadas, para serem executadas exclusivamente por um grupo de processadores, e outras que são atribuídas a apenas um processador. Com isto, resulta uma solução que é capaz de distribuir o trabalho a ser realizado de uma forma mais eficiente e balanceada. Infelizmente, para todos estes casos, existe uma discrepância entre a teoria e a prática, pois acaba-se por se assumir conceitos que não são aplicáveis na vida real. Para dar resposta a este problema, é necessário implementar estes algoritmos de escalonamento em sistemas operativos reais e averiguar a sua aplicabilidade, para caso isso não aconteça, as alterações necessárias sejam feitas, quer a nível teórico quer a nível práco. Adicionalmente, os métodos de obtenção de resultados também têm de ser melhorados, para que o trabalho de investigação necessário seja feito com maior graciosidade. Nesta dissertação, apresenta-se uma framework concebida num sistema operativo real, neste caso Linux, que implementa uma série de algoritmos de escalonamento semi-particionados em ambiente multiprocessador, de uma forma genérica e modular, para que no futuro, novas adições possam ser incluídas. Documentação detalhada também é fornecida, para que um terceiro também possa tirar partido do que foi desenvolvido. Presente também está, um mecanismo de obtenção de resultados, quer a nível do que é feito durante o escalonamento no que diz respeito a eventos, quer a nível de dados estatísticos. Apesar de no início deste trabalho, uma versão inicial desta framework já ter estado disponível, neste momento tornou-se ainda mais modular, aproveitando algumas das novas características herdadas por uma versão mais recente do núcleo do Linux, e de uma nova organização do código fonte que tinha sido produzido até então, e que, também resultou em novas funcionalidades. Entre estas, destaca-se a capacidade de se poder escolher o algoritmo uniprocessor a ser utilizado durante o escalonamento. Posto isto, possibilitou-se a utilização de algoritmos de prioridades fixas ao nível da tarefa durante o escalonamento a ser realizado. Isto obrigou à conceção de uma nova análise de escalonabilidade que lida diretamente com este caso e tal também é apresentado neste documento. Até agora, apesar deste trabalho ainda necessitar de alguns melhoramentos, resultados posi- tivos foram obdos. Para facilitar enormemente o processo de recolha de resultados, e de melhoramento de produção e/ou testes dos algoritmos implementados, uma ferramenta foi concebida para que, ao consumir os dados produzidos durante o escalonamento, uma representação visual se construa, e isto é feito sobe a forma de um diagrama de Gantt, em que tudo o que é representado é facilmente manipulado/filtrado. Após se terem feitos vários testes, concluiu-se que o trabalho efetuado por todos estes componentes aqui desenvolvidos, mostram-se bastante promissores no que diz respeito à criação de novo trabalho de investigação nesta área.
Nowadays, real time systems grow in importance and complexity. While moving from the uniprocessor to the multiprocessor environment, the tools available can not be directly used from one to the other because the level of complexity is significantly greater. This complexity grows with the number of processors available, and surely, this fact is what is keeping this area of research from advancing quicker, and this is even more true for real time task scheduling. This advancement, from one processor to multiple, promises a number of advantages, such as: doing work that would not be possible in the uniprocessor environment, resulting, in new performance guarantees, lower monetary costs, and less power consumption. Heat generation, imposed a limit in uniprocessor advancement making it an unreliable path to take, and therefore, the mutiIprocessor is, perhaps, the way to go in the future. It is expected that the number of processors in a given chip is going to grow, and this imposes the necessity to develop new technologies to fully exploit the resources available, and real time multiprocessor scheduling is no exception. Different multiprocessor scheduling categories were developed throughout the years. The global scheme uses a global queue that is accessible to all processors. This enables task migrations, high utilization bounds but at the cost of many task preemptions and migrations. To reduce these, the partitioned scheme was created. It allocates tasks to partitions, and these are mapped to processors. Unfortunately, this removes the possibility to migrate tasks, and grants lower utilization bounds. To inherit the advantages of both schemes, the semi-partitioned, or task-splitting scheme was devised, allowing some tasks to execute in several processors, and others to be executed by one. This is done to achieve better scheduling guarantees by balancing the work more efficiently. This dissertation, describes the construction of a framework that implements some of these algorithms. This work aims to deal with the real difficulties found when doing such in a real operating system. Schedulability analysis, which is a must, is also provided for a specific environment that is generated by the framework’s usage, namely, for task-fixed priority algorithms as the uniprocessor scheduling algorithm used in the on-line scheduling procedure. Finally, to improve the research process, a piece of software was been conceived that generates a graphical representation of the scheduling phase. It is shown, that by using these tools, realistic and positive results can be obtained.
