Shared resources in multiprocessor real-time systems scheduled by run

Abstract

Um sistema de tempo real crítico é aquele para o qual ao menos uma de suas tarefas deve cumprir os prazos de execução (deadlines ) enquanto o sistema estiver executando. Este requisito faz do algoritmo de escalonamento um elemento chave para a correção do sistema. Idealmente, o algoritmo de escalonamento deve ser eficiente, para não causar sobrecargas adicionais, e ótimo, garantindo que nenhum deadline de suas tarefas seja perdido sempre que isso puder ser assegurado por algum algoritmo de escalonamento. RUN (Reduction to Uniprocessor ) é um algoritmo capaz de escalonar eficientemente e de maneira ótima um conjunto de tarefas periódicas em uma plataforma com múltiplos processadores, quando as tarefas não compartilham outros recursos que não os processadores. Embora já tenha sido demonstrado que o RUN é compatível com o compartilhamento de recursos, a única solução existente impede preempções no acesso aos recursos compartilhados. Ao contrário desta abordagem, que pode ser considerada muito restritiva devido à sua baixa escalonabilidade, utilizamos o MrsP (Multiprocessor resource sharing Proto- col ) como um mecanismo de compartilhamento de recursos mais flexível. Fazer as regras do RUN e MrsP compatíveis entre si foi, portanto, nosso principal objetivo. A solução derivada foi implementada no Linux Textbed for Multiprocessor scheduling in Real-Time systems (Litmus-RT), um sistema operacional de tempo real baseado em Linux. Propusemos uma nova heurística para empacotamento das tarefas e realizamos avaliações experimentais comparando nossa solução com a existente. Os resultados obtidos mostraram que a solução proposta apresentou melhores resultados em escalonabilidade, overhead total e número de migrações e preempções.

A hard real-time system can be defined as the one that at least one of its tasks must meet its deadlines whenever the system is running. This requirement makes the scheduling algorithm a key element for system correctness. Ideally, the scheduling algorithm employed must both exhibit low overhead (efficiency) and ensure that no task deadline is missed whenever this can be ensured by some scheduling algorithm (optimality). RUN (Reduction to Uniprocessor) is an algorithm capable of efficiently and optimally scheduling a set of strictly periodic tasks on a multiprocessor platform when tasks do not share any resources but processors. Although it has already been shown that RUN is compatible with resource sharing, the only existing solution prevents preemptive access to shared resources. Unlike this approach, which can be considered too restrictive due to its poor schedulability, we used MrsP (Multiprocessor resource sharing Protocol) as a more flexible resource sharing mechanism. Making the rules of both RUN and MrsP compatible to each other was thus our main goal. The derived solution was implemented on Linux Textbed for Multiprocessor Scheduling in Real-Time systems (Litmus-RT), namely a Linux-based real-time operating system. We proposed a new task packaging heuristic and performed experimental evaluations comparing our solution with the existing one. The results showed that the proposed solution presented better results in terms of schedulability, total overhead and number of migrations and preemptions.