Abstract:
This dissertation is concerned with a detailed analysis of the off-line scheduling problem for a time-triggered real-time system. Such systems are used in various critical areas such as telephone switching systems, aviation and automobile control, space control and in powerplants. In technical terms, the considered problem amounts to a periodic preemptive scheduling problem with cyclic precedence constraints on a network of non-uniform processors, where not only program threads, but also communication mechanisms have to be scheduled in such a way that the cyclic information flow between program threads is achieved in accordance with the specification. The theoretical and practical approaches known from the literature do not scale to the relevant problem sizes and consider only restricted cases of the problem. This motivates the analysis of the scheduling problem presented here. We introduce a three-layer model: 1. Configuration. On this level we model all aspects of the problem which are independent of timing, in particular hardware configuration and distribution of system bandwidth. 2. Low Level Scheduling Constraints. This level subsumes all scheduling decisions which are independent of the the cyclic precedence graph, e.g. mutual exclusion constraints, preemption, and replication, as well as application specific overheads. 3. High Level Scheduling Constraints. On this level we describe the scheduling problem with respect to the cyclic precedence constraints. Based on a formal mathematical model we specify the requirements for correct cyclic information flow. As the problem in its full generality is NP-hard for several reasons, it is not feasible in practice to achieve an optimal solution. Consequently, we argue that “definite cycles” in the precedence graph are the main source of complexity. We show the following result: When the precedence graph does not contain definite cycles, then every combined solution of the configuration problem and the low level
