## 3 Backward Reachability-Based Schedulability Test
### Backward Reachability-Based Case Analysis
The condition for this picture is \(\exists j\
eq i:\ (C_{j}\leq D_{i}<2\cdot C_{j}\wedge C_{i}>D_{j}-C_{j}\wedge( \forall k\
eq j\wedge k\
eq i:\ C_{j}<C_{k}<D_{i}))\). We resume the above reasoning regarding Cases 1-8 as follows. **Lemma 1**. : _If \(i=n\), then \(T\) is unsafe if \(\ \forall j\
eq i:\ (D_{i}<C_{j})\) or \(\exists j\
eq i:\ (C_{j}\leq D_{i}<2\cdot C_{j}\wedge C_{i}>D_{j}-C_{j})\)._  
The last six pictures in Figure 1 show the cases where the red task \(i\) is the greatest task: \(i=1\) (Picture 9) and the cases where the red task \(i\) is the middle task: \(1<i<n\) (pictures 10-14). **Case 9. **  
\(i<j\) and \(i<k\): \(re^{k}\preceq r^{el}\preceq r^{i}\preceq b^{i}\)--all jobs are released before the last release of the red job. This case is unsafe. Every task \(j>i\) can start its job before (or in) state \(r^{i}\), since there are \(m\) processors. Since none of them complete their jobs before \(b^{i}\), the \(i\) job goes into the bad state due to its late release and non-preemptivity. The condition for this picture is \(\forall j\
eq i:\ D_{i}<C_{j}\). **Case 10. **  
\(k<i<j-re^{k}\preceq re^{j}\preceq r^{i}\preceq b^{i}\)--all jobs are released before the last release of the red job. This case is unsafe. We have exactly the same case as the previous one: again, each task \(j<i\) starts its job before (or in) state \(r^{i}\), and \(i\) job misses its deadline because there is no free processor to execute it. The condition for this picture is \(\forall j\
eq i:\ D_{i}<C_{j}\). **Case 11. **  
\(i<j\): \(re^{k}\preceq r^{j}_{p}\preceq r^{i}\preceq e^{j}_{p}\preceq re^{j}\preceq b^{i}\)--the green job is released after the last release of the red job. This case is safe. Let there be a green task \(j>i\) that releases and starts its job in state \(re^{j}\) between \(r^{i}\) and \(b^{i}\). However, this is an impossible situation, since the red task must start its job at \(re^{j}\) due to the fixed priority. The following pictures 12-14 consider only the cases where (blue) tasks with lower priority than the red task release and start executing their jobs before \(r^{i}\). The condition for this picture is \(\exists j>i:\ (D_{i}\geq C_{j}\wedge(\forall k\
eq j\wedge k\
eq i:\ C_{k}\geq C_{j}))\). **Case 12. **  
\(j<i<k\): \(re^{k}\preceq r^{j}_{p}\preceq r^{i}\preceq e^{j}_{p}\preceq re^{j}\preceq b^{i}\)--the green job is released after the last release of the red job. This case is safe for the same reason as Case 2. The condition for this picture is \(\exists j<i:\ (D_{i}\geq 2\cdot C_{j}\wedge(\forall k\
eq j\wedge k\
eq i:\ C_{k} \geq D_{j}+C_{j}))\). **Case 13. **  
\(j<i<k\): \(e^{k}_{p}\preceq r^{j}_{p}\preceq r^{i}\preceq e^{j}_{p}\preceq re^{k}\preceq re ^{j}\preceq b^{i}\)--as Case 2--but the last blue release occurs after the previous green execution state. This case is unsafe for the same reason as Case 6. The condition for this picture is \(\exists j<i:\ (C_{j}\leq D_{i}<2\cdot C_{j}\wedge C_{i}>D_{j}-C_{j}\wedge(\forall k<i: \ D_{i}\leq C_{k}\leq 2\cdot C_{j}))\). **Case 14**. \(j<i<k\): \((re^{k}\sim e^{i}_{p})\preceq r^{j}_{p}\preceq(e^{i}_{p}=f^{i}_{p})\preceq r^{i }\preceq re^{j}\preceq b^{i}\)--as Case 2--but the last red release is after the previous green execution state and the previous red completion is at the previous green execution state. This case is unsafe for the same reason as Case 3. The condition for this picture is \(\exists j<i:\ (C_{j}\leq D_{i}<2\cdot C_{j}\wedge C_{i}>D_{j}-C_{j}\wedge(\forall k<i: \ C_{k}\geq D_{j}+C_{j}))\). We resume the above reasoning regarding Cases 9-14 as follows. **Lemma 2**. : _If \(i<n\), then \(T\) is unsafe iff \(\forall j\
eq i:\ (D_{i}<C_{j})\) or \(\exists j<i:\ (C_{j}\leq D_{i}<2\cdot C_{j}\wedge C_{i}>D_{j}-C_{j})\)._