## 3 SSF-EDF Schedulability Analysis
### Lower Bound  
Consider that \(\tau_{i,j}\) first misses the deadline at \(A_{i,j}+D_{i}\). Assume that under SSF-EDF scheduling, there are exactly \(v\) processors in \(\big{[}A_{i,j},A_{i,j}+D_{i}\big{)}\) whose execution time is denoted by \(J_{v}\), \(0\leq v\leq m\). For example, \(J_{1}\) represents the time at which only one processor is executing, and \(J_{2}\) represents the time at which two processors are executing. Please note that the value of \(J_{0}\) is not necessarily zero, because there are situations where all processors are idle. However, this work has already assumed that \(\tau_{i,j}\) missed the deadline. Thus, within \(\big{[}A_{i,j},A_{i,j}+D_{i}\big{)}\), at least one processor will be processing \(\tau_{i,j}\). In this case, the value of \(J_{0}\) must be zero. Above, we have mentioned the need to consider the effects of processors of different speeds. Let the execution time \(J_{v}\) of the \(v\) processors being executed be multiplied by the sum \(S_{v}\) of the speeds of these processors. We have obtained the actual workload performed by \(v\) processors through \(J_{v}S_{v}\). For example, there are two tasks assigned to the processors \(s_{1}=1\) and \(s_{2}=2\), respectively. Let the execution time \(J_{2}=t\), and then the actual workload is \(3t\). Then, we can write  
\[W\big{(}A_{i,j},A_{i,j}+D_{i}\big{)}=\sum_{v=1}^{m}S_{v}J_{v}. \tag{7}\]  
Figure 2: A job \(\tau_{i,j}\) arrives at \(A_{i,j}\) and misses its deadline at time \(A_{i,j}+D_{i}\). Because of \(\sum_{v=1}^{m}S_{v}J_{v}=S_{m}J_{m}+\sum_{v=1}^{m-1}S_{v}J_{v}\) and \(S_{m}J_{m}=S_{m}\Big{(}D_{i}-\sum_{v=1}^{m-1}J_{v}\Big{)}\), we obtain  
\[ \begin{split} W\big{(}A_{i,j},A_{i,j}+D_{i}\big{)}& =S_{m}D_{i}-\sum_{v=1}^{m-1}(S_{m}J_{v}-S_{v}J_{v})\\ &=S_{m}D_{i}-\sum_{v=1}^{m-1}\frac{S_{m}-S_{v}}{s_{1}}s_{1}J_{v}. \end{split}  \tag{8}\]  
As defined by \(\lambda(\pi)\) in Section 2.2, when \(1\leq v\leq m-1\), it is obvious that  
\[\lambda(\pi)\geq\frac{S_{m}-S_{v}}{s_{1}}. \tag{9}\]  
From (8) and (9) above, we can draw a conclusion  
\[W\big{(}A_{i,j},A_{i,j}+D_{i}\big{)}\geq S_{m}D_{i}-\lambda(\pi)\sum_{v=1}^{m- 1}s_{1}I_{v}. \tag{10}\]  
Due to the nature of SSF-EDF, except when all processors are busy, during time interval \(\big{[}A_{i,j},A_{i,j}+D_{i}\big{)}\), \(\tau_{i,j}\) will be assigned to a processor with speed \(s_{i}\), \(s_{i}\geq s_{1}\). Then, the worst execution time \(E_{i}\geq\sum_{v=1}^{m-1}s_{1}J_{v}\) of \(\tau_{i,j}\). Moreover, since \(\tau_{i,j}\) missed the deadline, it cannot receive more execution time than \(E_{i}\); otherwise, \(\tau_{i,j}\) can finish before the deadline, which contradicts the previous assumption. Therefore, we obtain  
\[E_{i}>\sum_{v=1}^{m-1}s_{1}J_{v}. \tag{11}\]  
Combining (10) and (11) gives  
\[ \begin{split} W\big{(}A_{i,j},A_{i,j}+D_{i}\big{)}& >S_{m}D_{i}-\lambda(\pi)E_{i},\\ \frac{W\big{(}A_{i,j},A_{i,j}+D_{i}\big{)}}{D_{i}}& >S_{m}-\lambda(\pi)\delta_{i},\\ \frac{W\big{(}A_{i,j},A_{i,j}+D_{i}\big{)}}{D_{i}}& >S_{m}-\lambda(\pi)\delta_{\text{max}}(\Lambda).\end{split}  \tag{12}\]  
Let  
\[\mu=S_{m}-\lambda(\pi)\delta_{\text{max}}(\Lambda). \tag{13}\]  
From (12) and (13), it follows that  
\[W\big{(}A_{i,j},A_{i,j}+D_{i}\big{)}>\mu D_{i}. \tag{14}\]  
We can find many time points \(t\) that satisfy condition \(t_{0}\leq A_{i,j}\). \(t_{0}\) is the earliest one among all time points \(t\) that satisfy the condition. At \(t_{0}\), \(W\big{(}A_{i,j},A_{i,j}+D_{i}\big{)}>\mu\big{(}A_{i,j}+D_{i}-A_{i,j}\big{)}\) still holds. This leads to \(W\big{(}t_{0},A_{i,j}+D_{i}\big{)}>\mu\big{(}A_{i,j}+D_{i}-t_{0}\big{)}\). Hence, the lower bound of \(Q\big{(}t_{0},A_{i,j}+D_{i}\big{)}\) has been deduced. Let \(\Delta=A_{i,j}+D_{i}-t_{0}\). Then, we obtain  
\[W\big{(}t_{0},A_{i,j}+D_{i}\big{)}>\mu\Delta. \tag{15}\]  
According to the previous assumption, job \(\tau_{i,j}\) misses the deadline \(A_{i,j}+D_{i}\). That is, the total workload \(W\) is less than or equal to the time requirement \(Q\).