## 3 Backward Reachability-Based Schedulability Test
### Backward Reachability-Based Case Analysis  
To determine the safety (schedulability) of a real-time system under the above conditions, it is important to consider 14 key cases, as shown in Figure 1. In pictures, for every task \(j\), the bold lines represent decreasing values of \(D_{j}^{\prime}\) (the time remaining until the deadline of a released job) and dashed lines represent decreasing or standing values of \(C_{j}^{\prime}\) (the time remaining until a job completion). We call these lines _the lifelines_ of the corresponding task. The release of a job is indicated by a filled square for the deadline initial value \(D_{j}\) and a filled circle for the execution initial value \(C_{j}\). The completion of a job is marked with an empty circle (\(C_{j}^{\prime}=0\)), and the job deadline is marked with an empty square (\(D_{j}^{\prime}=0\)). If the exact release or completion time of a job is not important, the job lifeline does not end in a square or circle. We consider four types of jobs and their corresponding tasks w.r.t. their lifelines: red, green, blue, and gray jobs/tasks. * The red job \(i\) is a bad job that goes to bad state \(b^{i}\) with a red lifeline. Its release occurs in state \(r^{i}\). The previous release and execution of the red task occurs in state \(e_{p}^{i}\) or \(re_{p}^{i}\), with completion in state \(f_{p}^{i}\). The green job \(j\) is a job with the last release and execution in state \(re^{j}\) before bad state \(b^{i}\) and with completion after the bad state. It has a green lifeline. Its previous release is in state \(r^{j}_{p}\) and its previous starting execution point is in state \(e^{j}_{p}\). * THe blue job \(k\) with the blue lifeline is the last one before state \(re^{j}\), which is released and starts executing in state \(re^{k}\) and finishes after bad state \(b^{i}\). All other jobs of the other tasks start even earlier and are supposed to be completed after bad state \(b^{i}\). They are irrelevant for our analysis except for the fact that they occupy \(m-2\) processors until the bad state. * The gray job with the gray lifeline represents the red or blue job. It is started for execution in state \(e^{l}\) and is completed in state \(f^{l}\). The vertical light red line in the pictures represents a bad state: the moment when the time until the deadline is less than the execution time (the diagonal square) but job execution has not started (the horizontal execution lifeline). The vertical light green line marks the impossible state when (1) at least two jobs are released but neither has started or (2) the priority is violated. This state cannot be reached from the initial state, hence conditions imposed on the deadline and time of execution for pictures with green lines are a criterion for safe (schedulable) real-time systems. Briefly speaking, every picture without the green line shows that there is a sequence of job releases that results in a missed deadline and every picture with the green line shows that every reverse sequence of transitions from a bad state results in an impossible system state that cannot be reached from the initial state (in fact, for each case there is only one possible reverse sequence). The picture cases describe all the relevant combinations of the relative occurrence of release/start states for the red, green, and blue jobs (\(r^{i}\), \(b^{i}\), \(re^{i}_{p}\), \(e^{j}_{p}\), \(f^{i}_{p}\), \(re^{j}\), \(e^{j}_{p}\), \(r^{k}\), \(e^{k}_{p}\), \(e^{l}\), \(f^{l}\)) and their priorities (\(i>j\) and \(i>k\), \(i<j\) and \(i<k\), \(k<i<j\), and the case \(j<i<k\) is included in case \(i<j\)), since the number of processors is one less than the number of tasks. Let state \(s\) be earlier than \(s^{\prime}\) (\(s\preceq s^{\prime}\)) if there is a finite path from \(s\) to \(s^{\prime}\) (\((s,s^{\prime})\in R^{T*}\)). When the order of states on a path does not matter, we write \(s\sim s^{\prime}\), and states with the same position on a path are considered equal \(s=s^{\prime}\).