Planificación de sistemas de tiempo real crí­tico mediante técnicas no convencionales

Abstract

[EN] In the scheduling of hard real time systems it is key to find a temporal plan in which tasks can be executed before the deadline expires. Different types of scheduling algorithms can be used to achieve this goal. In addition to finding a feasible plan, it is often beneficial, out of all existing feasible plans, to find one that minimises some time parameter of the system. There are many scheduling algorithms that are able to find a correct scheduling of the set of tasks, but it is not so common to find algorithms that optimise other parameters to improve the performance of the system in terms of stability, power consumption, etc. Existing heuristics can improve the performance but without ensuring an optimal result. In this work we explore unconventional scheduling techniques based on integer linear programming to solve scheduling in mono processor systems with the objective of minimising the worst-case response time of the system tasks and the assignment of tasks to processors in multiprocessor systems with the objective of minimising the interference produced by the access to common hardware resources.

[ES] En la planificación de sistemas de tiempo real crí­tico es clave encontrar un plan temporal en el que las tareas pueden ejecutarse antes de que venza el plazo establecido. Para lograr este objetivo se pueden utilizar diferentes tipos de algoritmos de planificación. Además de encontrar un plan factible, muchas veces es beneficioso, de todos los planes factibles existentes, encontrar aquel que minimiza algún parámetro temporal del sistema. Existen muchos algoritmos de planificación que son capaces de encontrar una planificación correcta del conjunto de tareas. Pero no es tan común encontrar algoritmos que optimicen otros parámetros para mejorar el funcionamiento del sistemas en términos de estabilidad, consumo de potencia, etc. Los heurí­sticos existentes puede mejorar el comportamiento pero sin asegurar un resultado óptimo. En este trabajo exploramos las técnicas de planificación no convencionales basadas en programación lineal entera para resolver la planificación en sistemas mono procesador con el objetivo de minimizar el peor tiempo de respuesta y el cambio de contexto de las tareas del sistema y la asignación de tareas a procesadores en sistemas multiprocesador con el objetivo de minimizar la interferencia producida por el acceso a recursos hardware comunes.