# Scheduling the Exchange of Context Information for Time-Triggered Adaptive Systems
## 4 Scheduling for Adaptive Time-Triggered Systems
### Establishment of Multi-Schedule Graph
#### 4.5.1 Metascheduler  
Algorithm 1 describes the establishment of the MSG considering context information exchange. The variable \(p\) represents the currently processed context event index in the multi-schedule graph. Algorithm 1 populates a schedule database \(B\) with an object \(D\), which consists of a schedule \(s\) and its corresponding context value \(v\). The value of \(v\) is represented by \(n\) number of bits, which corresponds to the number of context events in the event calendar. The index \(p\) of \(v\) within a schedule database is \(1\leq p\leq 2^{n}\). The algorithm begins by initializing \(B\). The root schedule \(SM_{base}\) is computed by invoking a genetic algorithm using the base application model \(AM_{base}\) and the base platform model \(PM_{base}\). \(AM_{base}\) and \(PM_{base}\) are the initial application and platform model without the occurrence of any context. After which the base schedule and associated context \(p=0\) are entered in \(B\). The insertion of schedules into \(B\) occurs from top to bottom. It means that a parent schedule is first computed before the child schedule. Having computed \(SM_{base}\) at \(p=0\), we select the next context event in a temporally descending order. The schedule for the parent node of any child schedule in the multischedule graph is computed by subtracting the row index \(c\) or its bit pattern \(v\) from the bit pattern or index of the child schedule. The variable \(c\) is the currently processed row of the multi-schedule graph. \(c\) is initialized with the number of bits in the context event vector. The event combinations for the schedules in row \(c\) correspond to all binary numbers from 0 to \(2^{c}-1\), where the \(c^{th}\) bit is set. The value representation of the context event in Figure 5 example is a 5-bit vector. The binary representation \(v\) is derived from its index \(p\), and it is used to express the combination of context event occurrences. For example, the schedule of the parent/predecessor of the highlighted bottom-most schedule with value \(v=10101\) is computed by subtracting the index \(c\) : 10000, which results in \(v=00101\). In the same way, the parent schedule of the schedule with \(v=01101\) is computed by subtracting \(c\) : 01000 to get \(v=00101\). For each context event in the event calendar, we apply it to \(AM_{x}\), \(PM_{x}\), and then invoke the genetic algorithm (Algorithm 2) to solve for a schedule that includes the context communication cost of the context message exchange with only affected nodes. by the number of endsystems \(ne_{v}\), the number of switches \(ns_{v}\), and the number of valid multicast path indexes \(np_{v}\). The above parameters of the application and platform models are input constants for the optimization problem. In addition, there are decision variables for the optimization. Each message must be assigned a path-index \(P\) and a transmission ordering index \(T\). The path-index uniquely identifies a valid multicast communication path among endsystems and switches from a particular source endsystem to one or more destination endsystems. Based on the k-shortest-path problem, the multicast paths can be precomputed before starting the optimization, thus reducing the routing problem to the selection of an optimized path index. The message ordering index is required to determine the sequence of messages using shared switches or endsystems. Further decision variables are the endsystem allocation \(A\) and the relative ordering index \(R\) for each task. The task ordering index is relevant when multiple tasks are assigned to the same endsystems. In contrast to the node being scheduled, \(P\), \(T\), \(A\), and \(R\) are constants of the already scheduled predecessor nodes. In formulating the scheduling problem, we use the subscript \(y\) for the decision variable of the node being scheduled, whereas \(x\) denotes an index of a predecessor node that is already scheduled. The scheduling constraints ensure the satisfaction of the precedence constraints for each path-index.