## 3 SSF-EDF Schedulability Analysis
### Upper Bound  
Before derivation, we need to classify the job. Carry-in jobs are jobs that arrive before \(t_{0}\) and are not completed before \(t_{0}\). The total processor time requirement caused by these jobs is denoted by \(R_{c}\). Other jobs are regular jobs. The total processor time requirement caused by this job is denoted by \(R_{c}\). The sum of these two time demands is the \(Q\big{(}t_{0},A_{i,j}+D_{i}\big{)}\) that we need. The study of [PERSON] et al. shows that \(\Delta\times\mathrm{LOAD}(\Lambda)\) can calculate the upper bound of \(R_{r}\)[11; 12]. LOAD and DBF are defined as follows:  
\[ \begin{split}\mathrm{DBF}(\tau_{i},\Delta t)\stackrel{{ \mathrm{def}}}{{=}}&\max\left(0,\left(\left\lfloor\frac{ \Delta t-D_{i}}{T_{i}}\right\rfloor+1\right)E_{i}\right),\\ \mathrm{LOAD}(\Lambda)\stackrel{{\mathrm{def}}}{{= }}&\max\limits_{\Omega T>0}\left(\frac{\sum_{\tau_{i}\in\Lambda} \mathrm{DBF}(\tau_{i},\Delta t)}{\Delta t}\right).\end{split}  \tag{17}\]  
Let us calculate the upper bound of \(R_{c}\) again. **Lemma 1**. : _The remaining execution requirement at time \(t_{0}\) for any carry-in job is lower than \(\Delta\delta_{\max}(\Lambda)\)._  
Proof. : Let us analyze the carry-in job \(\tau_{p,q}\) whose arrival time is \(A_{p,q}<t_{0}\) and whose execution is not completed at time \(t_{0}\) (see Figure 2). Let \(\varphi_{p,q}=t_{0}-A_{p,q}\). Let \(E^{\prime}_{p,q}\) be the execution time of \(\tau_{p,q}\) within time interval \(\big{[}A_{p,q},t_{0}\big{)}\). \(J_{v}\) continues to use the same definition as in Section 3.1. \(W\big{(}A_{p,q},t_{0}\big{)}\) can be calculated from \(S_{m}\varphi_{p,q}-\sum_{\alpha=1}^{m-1}\big{(}S_{m}J_{v}-S_{v}J_{v}\big{)}\). Since job \(\tau_{p,q}\) did not complete execution at time \(t_{0}\), we can conclude  
\[E^{\prime}_{p,q}>S_{m}\varphi_{p,q}-\sum_{v=1}^{m-1}\big{(}S_{m}J_{v}-S_{v}J_{ v}\big{)}. \tag{18}\]  
Since \(W\big{(}A_{p,q},t_{0}\big{)}=W\big{(}A_{p,q},A_{i,j}+D_{i}\big{)}-W\big{(}t_{ 0},A_{i,j}+D_{i}\big{)}\), there is  
\[W\big{(}A_{p,q},A_{i,j}+D_{i}\big{)}-W\big{(}t_{0},A_{i,j}+D_{i}\big{)}=E^{ \prime}_{p,q}. \tag{19}\]  
It is given by (18) and (19)  
\[W\big{(}A_{p,q},A_{i,j}+D_{i}\big{)}-W\big{(}t_{0},A_{i,j}+D_{i}\big{)}>S_{m} \varphi_{p,q}-\sum_{v=1}^{m-1}\big{(}S_{m}J_{v}-S_{v}J_{v}\big{)}. \tag{20}\]  
According to the definition of \(t_{0}\) (see (15)), it must satisfy  
\[W\big{(}t_{0},A_{i,j}+D_{i}\big{)}>\mu\Delta. \tag{21}\]  
Since \(t_{0}\) is the earliest time \(t\) satisfying such conditions, any time \(t\) before \(t_{0}\) does not satisfy the above formula, i.e.,  
\[W\big{(}A_{p,q},A_{i,j}+D_{i}\big{)}\leq\mu(\Delta+\varphi_{p,q}). \tag{22}\]  
We immediately have  
\[\mu(\Delta+\varphi_{p,q})-\mu\Delta>W\big{(}A_{p,q},A_{i,j}+D_{i}\big{)}-W \big{(}t_{0},A_{i,j}+D_{i}\big{)}. \tag{23}\]This is given by (20) and (23)  
\[ \begin{split}\mu(\Delta+\varphi_{p,q})-\mu\Delta&>S_{m} \varphi_{p,q}-\sum_{v=1}^{m-1}\left(S_{m}I_{v}-S_{v}I_{v}\right),\\ \mu\varphi_{p,q}&>S_{m}\varphi_{p,q}-\sum_{v=1}^{m-1 }\frac{S_{m}-S_{v}}{s_{1}}s_{1}I_{v}.\end{split}  \tag{24}\]  
By combining (6), we have  
\[\mu\varphi_{p,q}>S_{m}\varphi_{p,q}-\lambda(\pi)\sum_{v=1}^{m-1}s_{1}I_{v}. \tag{25}\]  
With the exception of the case wherein all processors are busy, the carry-in job \(\tau_{p,q}\) must be executed on one of the processors. Since \(\tau_{p,q}\) is not completed before \(t_{0}\), the worst execution time of \(\tau_{p,q}\) is not less than the execution time in \(\left[A_{p,q},t_{0}\right)\). Among them, the execution time of \(\tau_{p,q}\) in \(\left[A_{p,q},t_{0}\right)\) is at least \(\sum_{v=1}^{m-1}s_{1}I_{v}\). Thus, we have  
\[E^{\prime}_{p,q}\geq\sum_{v=1}^{m-1}s_{1}I_{v}. \tag{26}\]  
It is given by (25) and (26) that  
\[\mu\varphi_{p,q}>S_{m}\varphi_{p,q}-\lambda(\pi)E^{\prime}_{p,q}. \tag{27}\]  
It is also given by (13) and (27) that  
\[