Real-time Task-Splitting scheduling algorithms framework

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á

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.