Task Partitioning and Priority Assignment for Hard Real-time Distributed Systems
Ricardo Garibay-Martínez, Geoffrey Nelissen, Luís Lino Ferreira, Luís Miguel Pinho · 2013
The partitioning of fixed-priority hard real-time tasks and messages in a distributed system is a well known NPhard problem. Therefore, there are no methods that provide an optimal solution in polynomial time. In this paper, we propose the Distributed using Optimal Priority Assignment (DOPA) heuristic, which simultaneously solves the problem of assigning task to processors and assigning priorities to tasks. DOPA makes use of Audsley’s Optimal Priority Assignment (OPA) algorithm to assign priorities to tasks and messages. However, in order to use the OPA algorithm for task sets with dependencies, we first transform the task set into a set of independent tasks by imposing intermediate deadlines. The experimental results show how the utilisation of the OPA algorithm increases in average the number of schedulable tasks and messages in a distributed system when compared to the utilisation of the Deadline Monotonic (DM) priority assignment usually used in other works. Task Partitioning and Priority Assignment for Hard Real-time Distributed Systems Ricardo Garibay-Martinez, Geoffrey Nelissen, Luis Lino Ferreira, Luis Miguel Pinho CISTER/INESC-TEC, ISEP Polytechnic Institute of Porto, Portugal {rgmz, grrpn, llf, lmp}@isep.ipp.pt Abstract—The partitioning of fixed-priority hard real-time tasks and messages in a distributed system is a well known NP-hard problem. Therefore, there are no methods that provide an optimal solution in polynomial time. In this paper, we propose the Distributed using Optimal Priority Assignment (DOPA) heuristic, which simultaneously solves the problem of assigning task to processors and assigning priorities to tasks. DOPA makes use of Audsley’s Optimal Priority Assignment (OPA) algorithm to assign priorities to tasks and messages. However, in order to use the OPA algorithm for task sets with dependencies, we first transform the task set into a set of independent tasks by imposing intermediate deadlines. The experimental results show how the utilisation of the OPA algorithm increases in average the number of schedulable tasks and messages in a distributed system when compared to the utilisation of the Deadline Monotonic (DM) priority assignment usually used in other works.The partitioning of fixed-priority hard real-time tasks and messages in a distributed system is a well known NP-hard problem. Therefore, there are no methods that provide an optimal solution in polynomial time. In this paper, we propose the Distributed using Optimal Priority Assignment (DOPA) heuristic, which simultaneously solves the problem of assigning task to processors and assigning priorities to tasks. DOPA makes use of Audsley’s Optimal Priority Assignment (OPA) algorithm to assign priorities to tasks and messages. However, in order to use the OPA algorithm for task sets with dependencies, we first transform the task set into a set of independent tasks by imposing intermediate deadlines. The experimental results show how the utilisation of the OPA algorithm increases in average the number of schedulable tasks and messages in a distributed system when compared to the utilisation of the Deadline Monotonic (DM) priority assignment usually used in other works. Keywords—real-time; distributed systems; task allocation; priority assignment; intermediate deadlines; holistic analysis.