PSSA: um algoritmo semi-particionado com server shadowing para o escalonamento de tarefas de tempo real periódicas em múltiplos processadores

Abstract

Real-time systems are present in several applications, from critical applications, like automotive and aviation, to non-critical such as multimedia and online games. For critical real-time systems to function correctly, it's necessary to ensure that all tasks execute within pre-defined deadlines. To this end, the system's task scheduler plays a fundamental role, as it determines at each moment which task must be executed so that they can all meet their deadlines. In systems with one processor, the Earliest Deadline First (EDF) scheduler is one of the best options, as it guarantees that all tasks meet their deadlines whenever possible. On systems with more than one processor, the same is not true. This work proposes the Partitioning and Server Shadowing Algorithm (PSSA) scheduler for multiprocessor systems composed of periodic and independent tasks. The idea of the algorithm is to partition tasks between processors and then use EDF scheduling on each processor. When such partitioning is not found, some tasks must execute on more than one processor, while some processors are left with idle capacities. In order to manage the execution of tasks that run on more than one processor, PSSA uses a new approach called server shadowing, according to which the idle parts of real processors are used to create logical processors. When a task runs on a logical processor, it actually runs on one of the real processors that have provided their idle capacity to the logical processor where the task is allocated. The concepts of server shadowing and logical processors gave PSSA the ability to obtain results similar to the best results published to date in terms of the number of migrations and preemptions generated for periodic tasks, as demonstrated through extensive simulations.