End-to-end scheduling in hard real-time multiprocessor systems.
Reza Etemadi · 1996
An end-to-end approach for scheduling hard real-time periodic transactions in a multiprocessor or distributed system is presented. Each transaction consists of a chain of tasks, where each task is allocated to a processor based on its resource requirements. A transaction may visit a processor several times and it may fork subtransactions and later join them. Assuming fixed priority scheduling on processors, an upper bound for the end-to-end delay of transactions is introduced. The problem is to determine the priority of each task such that the end-to-end deadline for each transaction is met. A priority assignment is feasible if the corresponding upper-bound for each transaction is less than or equal to the actual deadline of the transaction. Heuristic algorithms for priority assignment in a periodic flow-shop model are introduced and their ability to find a feasible schedule are compared to existing heuristic algorithms by using empirical methods. The heuristic algorithms developed for the flow-shop model are extended to support a more complex problem domain (i.e., when revisiting transactions or transactions with subtransactions exist in the system). The effect of revisiting and subtransactions on the relative performance of the extended algorithms is studied through empirical methods. For a real world example the extended algorithms are used to find priorities for difficult tasks in the signal processing module of a towed array sonar system.