text:
\section{Introduction}

For multiprocessor sporadic task systems, the capacity-augmentation factor for global RM is proved to be $2.668$ in this paper. We also provide tighter analysis than the existing result by Bertogna et al. \cite{DBLP:conf/opodis/BertognaCL05} by considering both the total utilization of the task system and the maximum task utilization in the schedulability test.

\subsection{Improved Analysis for Global RM}
\label{sec:global-sporadic}

To get better analysis than the solution in Theorem~\ref{thm:multiprocessor-GRM}, we need a better sufficient test than the naive sufficient test in Lemma~\ref{lemma:gRM-sufficient}. The following lemma provides a sufficient test based on the observations by Baruah et al. \cite{DBLP:journals/rts/BaruahBMS10}, in which the proof is in Appendix B.

\begin{lemma}
\label{lemma:multiprocessor-grm-sporadic-pushforward}
Let $U_k^{\max}$ be $\max_{j=1}^{k} U_j$.
Task $\tau_k$ in a sporadic task system with implicit deadlines  is schedulable by global RM on
$M$ processors if
\begin{align*}
  \forall y \geq 0, \forall 0 \leq \omega_i \leq T_i, \exists t \mbox{ with } 0 < t \leq T_k+y  {\;\; and \;\;} \\
  U_k^{\max} \cdot(T_k+y) +
 \frac{ \sum_{i=1}^{k-1} \omega_i\cdot U_i+ \ceiling{\frac{t-\omega_i }{T_i}} C_i
}{M}\leq t.
\end{align*}
\end{lemma}

The schedulability condition in Lemma~\ref{lemma:multiprocessor-grm-sporadic-pushforward} requires to test all possible $y \geq 0$ and all possible settings of $0 \leq \omega_i \leq T_i$ for the higher priority tasks $\tau_i$ with $i=1,2,\ldots,k-1$. At first glance, it may seem to be difficult to use the \framework{} framework. It requires some further annotation before adopting the framework, as shown in the proof of the following theorem.

\begin{theorem}
  \label{thm:multiprocessor-grm-sporadic-tight}
Let $U_k^{\max}$ be $\max_{j=1}^{k} U_j$.
Task $\tau_k$ in a sporadic task system with implicit deadlines  is schedulable by global RM on
$M$ processors if
\begin{equation}
\label{eq:schedulability-GRM-tight}
(U_k^{\max} +1) \prod_{j=1}^{k-1} (\frac{U_j}{M} + 1)\leq 2,
\end{equation}
or
\begin{equation}
\label{eq:schedulability-GRM-tight-ubound}
\sum_{j=1}^{k-1} \frac{U_j}{M}\leq \ln{\frac{2}{U_k^{\max}  +1}}.
\end{equation}
\end{theorem}
\begin{proof}
  We will show that the schedulability condition in the theorem holds for all possible settings of $y$ and $\omega_i$s.
  Suppose that $y$ and $\omega_i$ for $i=1,2,\ldots,k-1$  are given, in which  $y \geq 0$ and $0 \leq \omega_i \leq T_i$. Let $t_k$ be $T_k+y$. Now, we set $t_i$ to $\omega_i + \floor{\frac{T_k+y-\omega_i}{T_i}}T_i$ for $i=1,2,\ldots,k-1$ and reindex the tasks such that $t_1 \leq t_2 \leq \ldots \leq t_k$. The sufficient schedulability condition in Lemma~\ref{lemma:multiprocessor-grm-sporadic-pushforward} under the given $y$ and $\omega_i$s is to verify the existence of $t_j \in
\setof{t_1, t_2, \ldots t_k}$ such that
\begin{align}
  &U_k^{\max}(T_k+y) + \frac{\sum_{i=1}^{k-1}  \omega_i\cdot U_i+ \ceiling{\frac{t_j-\omega_i }{T_i}} C_i}{M} \\
 \leq & U_k^{\max} t_k + \frac{\sum_{i=1}^{k-1} U_i t_i + \sum_{i=1}^{j-1} C_i}{M}
  \leq t_j.
\end{align}
\jj{bug from here!!!}
  By the definition of $t_i$ and  $y \geq 0$ and the global RM scheduling (i.e., $T_k \geq T_i$), we can conclude that $t_i \geq T_k+y \geq T_i$, which implies that $C_i \leq U_i t_i$.
  Hence, we know that the sufficient test is to verify whether there exists
 $t_j \in
\setof{t_1, t_2, \ldots t_k}$ such that
\begin{align}
  \label{eq:final-grm-k2u-precondition}
U_k^{\max} t_k + \sum_{i=1}^{k-1} \alpha_i U_i t_i + \sum_{i=1}^{j-1} \beta_i U_i t_i
  \leq t_j,
\end{align}
where $\alpha_i = \frac{1}{M}$ and $\beta_i \leq \frac{1}{M}$ for $i=1,2,\ldots,k-1$.
Therefore, we reach the conclusion of the schedulability conditions in Eqs.~\eqref{eq:schedulability-GRM-tight} and \eqref{eq:schedulability-GRM-tight-ubound} by Lemma~\ref{lemma:framework-constrained} and
Lemma~\ref{lemma:framework-totalU-exclusive} under given $y$ and $\omega_i$s.\footnote{The concern that $y$ may be unbounded (so may $t_k$) can be handled by normalizing all the $t_i$ values for higher priority tasks $\tau_i$s to $t_k$ and set $t_k$ to $1$ after the normalization. }

The schedulability test in Eq.~\eqref{eq:final-grm-k2u-precondition} is independent from the settings of $y$ and $\omega_i$s. However, the setting of $y$ and $\omega_i$s affects how the $k-1$ higher priority tasks are indexed. Fortunately, it can be observed that the schedulability tests in Eqs.~\eqref{eq:schedulability-GRM-tight} and \eqref{eq:schedulability-GRM-tight-ubound} are completely independent upon the indexing of the higher priority tasks. Therefore, no matter how $y$ and $\omega_i$s are set, the schedulability conditions in Eqs.~\eqref{eq:schedulability-GRM-tight} and \eqref{eq:schedulability-GRM-tight-ubound} are the corresponding results from the \framework{} framework.
As a result, we can reach the conclusion.
\end{proof}

\begin{corollary}
  \label{col:grm-tight}
  The capacity augmentation factor of global RM for a sporadic system with implicit deadlines is $2.668$.
\end{corollary}
\begin{proof}
  Suppose that $\sum_{\tau_i} \frac{C_i}{M T_i} \leq \frac{1}{b}$ and
  $U_k \leq \max_{\tau_i} U_i \leq
  \frac{1}{b}$.  Therefore, by
  Eq.~\eqref{eq:schedulability-GRM-tight-ubound}, we can guarantee
  the schedulability of task $\tau_k$ if $\frac{1}{b} \leq
  \ln{\frac{2}{1+\frac{1}{b}}}$. This is equivalent to solving $x =
  \ln{\frac{2}{1+x}}$, which holds when $x\approx
  2.668$ by solving the equation numerically. Therefore,
  we reach the conclusion of the capacity augmentation factor
  $2.668$.
\end{proof}

{\bf Remarks:} The utilization bound in Eq.~\eqref{eq:schedulability-GRM-tight-ubound} is analytically better than the best known utilization-based schedulability test $\sum_{j=1}^{k} U_j\leq \frac{M}{2}(1-U_k^{\max})+U_k^{\max}$ for global RM by Bertogna et al. \cite{DBLP:conf/opodis/BertognaCL05}, since $\frac{(1-x)}{2} \leq \ln\frac{2}{1+x}$ when $0 \leq x \leq 1$. The capacity augmentation factor $2.668$ in Corollary \ref{col:grm-tight} is the same as the result by Lundberg \cite{DBLP:conf/rtas/Lundberg02}. As shown in \cite{DBLP:conf/rtas/Lundberg02}, the factor $2.668$ is tight when the number of tasks is sufficiently large.

We would like to point out the incompleteness in the proof in \cite{DBLP:conf/rtas/Lundberg02}. In the proof of the extreme task set, the argument in Page 150 in \cite{DBLP:conf/rtas/Lundberg02} concludes that task $\tau_n$ is more difficult to be schedulable due to the increased interference of task $\tau_{n-1}$ to task $\tau_n$ after the transformation. The argument was not correctly proved since the increased interference has to be analyzed in all time points in the analysis window, whereas the analysis in \cite{DBLP:conf/rtas/Lundberg02} only considers the interference in a specific interval length. Without analyzing the resulting interference in all time points in the analysis window, task $\tau_n$ after transformation may still have chance to finish earlier due to the potential reduction of the interference at earlier time points.

We limit our attention here for the global RM scheduling. Andersson et al. \cite{DBLP:conf/rtss/AnderssonBJ01} propose the RM-US[$\varsigma$] algorithm, which gives the highest priority to tasks $\tau_i$s with $U_i > \varsigma$, and otherwise assigns priorities by using RM. Our analysis here can also be applied for the RM-US[$\varsigma$] algorithm with some modifications in the proofs by setting $\varsigma=\frac{1}{2.668}\approx 0.37482$.

\begin{appProof}{Lemma~\ref{lemma:multiprocessor-grm-sporadic-pushforward}}
  This is proved by contrapositive. If task $\tau_k$ is not schedulable by global RM, we will show that there exist $y \geq 0$ and $0 \leq \omega_i \leq T_i$ such that for all $0 < t \leq T_k+y$, the condition $U_k^{\max} \cdot (T_k+y) +
 \frac{ \sum_{i=1}^{k-1} \omega_i\cdot U_i+ \ceiling{\frac{t-\omega_i }{T_i}} C_i
}{M} > t$ holds. The proof is mainly based on the forwarding algorithm for the analysis of global DM by Baruah et al. in \cite{DBLP:journals/rts/BaruahBMS10}, by making some further annotations.

  If $\tau_k$ is not schedulable, let $z_0$ be the first time that task $\tau_k$ misses its absolute deadline, i.e., $z_0$.  Let $z_1$ be the arrival time of this job of task $\tau_k$.  For notational brevity, let this job be $J_1$, which arrives at time $z_1$ and has not yet been finished at time $z_0$. By definition, we know that $z_0-z_1$ is $T_k$. Due to the scheduling policy and the implicit-deadline setting, removing (1) all the other jobs of task $\tau_k$ (except the one arriving at time $z_1$), (2) all the jobs arriving no earlier than $z_0$,  and (3) lower-priority jobs does not change the unschedulability of job $J_1$. Therefore, all the jobs that are considered for the rest of the proof come from $\tau_1, \tau_2, \ldots, \tau_k$.

  Now, we expand the interval of interest by using a slightly different algorithm from that proposed in \cite{DBLP:journals/rts/BaruahBMS10}, also illustrated with the notations in Figure~\ref{fig:force-forward}, as follows:
 \begin{algorithm}[h]
   \label{alg:feasibility-analysis2}
    \begin{algorithmic}[1]\small
        \FOR {$\ell\leftarrow2,3,...$}
          \STATE let $J_\ell$ denote a job that
          \begin{compactitem}[-]
          \item arrives at some time-instant $z_\ell<z_{\ell-1}$;
          \item has an absolute deadline after $z_{\ell-1}$;
          \item has not completed execution by $z_{\ell-1}$; and
          \item has executed for strictly less than $(z_{\ell-1}-z_\ell)\cdot \hat{U}_\ell$
	 units over the interval $[z_\ell,z_{\ell-1})$, where $\hat{U}_\ell$ is the utilization of the task that generates job $J_\ell$.
          \end{compactitem}

          \IF {there is no such a job}
          \STATE $\ell\leftarrow (\ell-1)$; break;
          \ENDIF
      \ENDFOR
     \end{algorithmic}
     \end{algorithm}

     Suppose that the forwarding algorithm terminates with $\ell$ equals to $\ell^*$. We now examine the schedule in the interval $(z_{\ell^*}, z_0]$. Since $J_1, J_2, \ldots, J_{\ell^*}$ belong to $\tau_1, \tau_2, \ldots, \tau_k$, we know that $\hat{U}_\ell \leq U_k^{\max}$ for $\ell=1,2,\ldots,\ell^*$. Let $\sigma_\ell$ be the total length of the time interval over $(z_\ell, z_{\ell-1}]$ during which $J_\ell$ is executed. By the choice of $J_\ell$, it follows that
     \[
     \sigma_\ell < (z_{\ell-1}-z_{\ell}) \cdot \hat{U}_\ell.
     \]
     Moreover, all the $M$ processors execute other higher-priority jobs (than $J_\ell$) at any other time points in the interval $(z_\ell, z_{\ell-1}]$ at which $J_\ell$ is not executed.
     Therefore, by the above analysis, we know that the maximum amount of time from $z_{\ell^*}$ to $z_0$, in which not all the $M$ processors execute certain jobs, is at most
     \begin{align*}
       \sum_{\ell=1}^{\ell^*} \sigma_\ell &<      \sum_{\ell=1}^{\ell^*} (z_{\ell-1}-z_{\ell}) \cdot \hat{U}_\ell\\
       &\leq
     \sum_{\ell=1}^{\ell^*} (z_{\ell-1}-z_{\ell}) \cdot U_k^{\max} = (z_0-z_{\ell^*}) \cdot U_k^{\max}.
   \end{align*}

   Now, we replace job $J_0$ with job $J_0'$ in the above schedule, where $J_0'$ is released at time $z_{\ell^*}$ with absolute deadline $z_0$ and execution time $(z_0-z_{\ell^*}) \cdot U_k^{\max}$. According to the above analysis, $J_0'$ cannot be finished before $z_{0}$ in the above schedule.
   For each task $\tau_i$ for $i=1,2,\ldots,k-1$, in the above schedule, there may be one \emph{carry-in} job, denoted as $J_i^\flat$, of $\tau_i$ that arrives at time $r_i^\flat$ with $r_i^\flat < z_{\ell^*}$ and has absolute deadline after $d_i^\flat$ with $d_i^\flat > z_{\ell^*}$. According to the termination condition in the construction of $z_{\ell^*}$, if $J_i^\flat$ exists, we know that at least $(z_{\ell^*}-r_i^\flat)\cdot U_i$ amount of execution time has been executed before $z_{\ell^*}$, and the remaining execution time of job $J_i^\flat$ to be executed after $z_{\ell^*}$ is at most
   $(d_i^\flat - z_{\ell^*})\cdot U_i$. If $J_i^\flat$ does not exist, then $d_i^\flat$ is set to $z_{\ell^*}$ for notational brevity. Therefore, the amount of workload $W_i'(t)$ of all the released jobs of task $\tau_i$ for $i=1,2,\ldots,k-1$ to be executed in time interval $(z_\ell^*, z_\ell^*+t)$ is at most
   \begin{equation}
     \label{eq:1}
   W_i'(t)  = (d_i^\flat - z_{\ell^*})\cdot U_i+ \ceiling{\frac{t-(d_i^\flat - z_{\ell^*}) }{T_i}} C_i.
   \end{equation}
   Clearly, this is more precise than the naive time demand function $W_i(t)$ in Eq.~\eqref{eq:W_i-multiprocessor}.

   The assumption of the unschedulability of job $J_0'$ (due to the unschedulability of job $J_0$) under global RM implies that $J_0'$ cannot finish its computation at any time between $z_{\ell^*}$ and $z_0$. This leads to the following (necessary) condition
  $U_k^{\max} (z_0-z_{\ell^*}) +
  \frac{ \sum_{\tau_i \in hp(\tau_k)}W_i'(t) }{M} >  t$ for all $0 < t \leq z_{\ell^*}-z_0$ for the unschedulability of job $J_0'$.   Therefore, by the existence of $y=z_{0}-z_{\ell^*}$ and $\omega_i = d_i^\flat - z_{\ell^*}$ for $i=1,2,\ldots, k-1$ to force the above necessary condition, we reach the conclusion of the proof by contrapositive.
\end{appProof}

\begin{figure}[t]
  \centering
  \scalebox{0.45}{
    \begin{tikzpicture}[x=1cm,font=\sffamily\Large,ultra thick]]

  \draw[->](0,0) -- (19, 0)  node[right]{$x$};

   \draw[-](2,-.1) node[below]{$z_\ell$} -- (2, 1)  -- (5,1) node[pos=.5,above]{$J_\ell$} -- (5,0) ;

    \draw[-](4,-.1) node[below]{$z_{\ell-1}$} -- (4, 1.2)  -- (7,1.2) node[pos=.5,above]{$J_{\ell-1}$};

\draw[-](10,1) node[above]{$J_{3}$} -- (13,1) -- (13,0) ;

 \draw[-](12,-.1) node[below]{$z_2$} -- (12, 1.2)  -- (16,1.2) node[pos=.5,above]{$J_2$} -- (16,0) ;

 \draw[-](15,-.1) node[below]{$z_1$} -- (15, 1)  -- (18,1) node[pos=.5,above]{$J_1$} -- (18,0)node[below]{$z_0$} ;

  \node [ ] at (8,0.6) {$\cdot\cdot\cdot\cdot\cdot$};
    \node [ ] at (1,0.6) {$\cdot\cdot\cdot\cdot\cdot$};
      \end{tikzpicture}  }
  \caption{Notations of the forwarding algorithm for the analysis of global RM.}
  \label{fig:force-forward}
\end{figure}

\subsection{Response Time Bound in Fixed-Priority Scheduling with Arbitrary Deadlines}
\begin{definition}[Last Release]
For a given task $\tau_i$ in the interval
$[\phi,\phi+D_n)$ for any $\phi \ge 0$, $t_i$ denotes the time of the last release of task $\tau_i$.

\begin{lemma}
  \label{lemma:response-time-unschedulability}
Let $X^*$ denote the time at which the $k^{th} job$ of $\tau_n$ misses its deadline.
If the $k^{th}$ job of task $\tau_n$ misses its deadline, then
    \begin{equation*}
\forall \tau_i,\quad kC_n+\sum_{i=1}^{n-1}U_it_i+\sum_{j=1}^{i-1}C_j> t_i
    \end{equation*}
 \end{lemma}
\begin{proof}

\end{proof}
\end{definition}
\begin{definition}[Worst-Case Response Time]
$R_n=X^*-(k-1)T_n$
\end{definition}
\begin{theorem}
The worst-case reponse time $R_n$ of task $\tau_n$ is bounded above by
\begin{align*}
 R_n\le \frac{C_n+\sum_{i=1}^{n-1}C_i-\sum_{i=1}^{n-1}(U_i\sum_{j=i}^{n-1}C_j)}{1-\sum_{i=1}^{n-1}U_i}
\end{align*}
where tasks are indexed with
\begin{equation*}
\forall \tau_i \quad \frac{C_{i+1}}{U_{i+1}}<\frac{C_{i}}{U_{i}}.
\end{equation*}
\end{theorem}
\begin{proof}
We prove this theorem by finding the supremum $R_n$ subject to the conditions in
 Lemma~\ref{lemma:response-time-unschedulability}.
This is a strictly convex problem. Since we have more variables than constraints,
all of the constraints have to be \emph{active} according to the extreme point theorem.
\begin{equation*}
kC_n+\sum_{i=1}^{n-1}U_i(t_1+\sum_{j=1}^{i-1}C_j)= t_1
\end{equation*}
\begin{align*}
t_1&=\frac{kC_n+\sum_{i=1}^{n-1}(U_i\sum_{j=1}^{i-1}C_j)}{1-\sum_{i=1}^{n-1}U_i}\\
&\ge 0 \quad \text{($\sum_{i=1}^nU_i<1$)}
\end{align*}
Then, the response time is bounded by
\begin{equation}
\label{eq:response-time-supermum-k}
R_n\le \frac{kC_n+\sum_{i=1}^{n-1}C_i-\sum_{i=1}^{n-1}(U_i\sum_{j=i}^{n-1}C_j)}{1-\sum_{i=1}^{n-1}U_i}-(k-1)T_n.
\end{equation}
We now prove the maximum in Eq. (\ref{eq:response-time-supermum-k}) occur for $k=1$.
\begin{align*}
\frac{d}{dk}&\left(\frac{kC_n+\sum_{i=1}^{n-1}C_i-\sum_{i=1}^{n-1}(U_i\sum_{j=i}^{n-1}C_j)}{1-\sum_{i=1}^{n-1}U_i}-(k-1)T_n\right)\\
&=\frac{C_i}{1-\sum_{i=1}^{n-1}U_i}-T_n\\
&=T_n(\frac{U_i}{1-\sum_{i=1}^{n-1}U_i}-1)\\
&=T_n(\frac{\sum_{i=1}^{n}U_i-1}{1-\sum_{i=1}^{n-1}U_i})
\end{align*}
which is negative since our assumption $\sum_{i=1}^{n}U_i<1$. Since this function is decreasing, the maximum occurs in the left bound, which means $k=1$.
By substituting $k=1$ in Eq. (\ref{eq:response-time-supermum-k}), this theorem follows.
\end{proof}
\subsection{Response Time Bound in Fixed-Priority Scheduling with Arbitrary Deadlines with unknown $C$}
\begin{lemma}
Let $X^*$ denote the time at which the $k^{th} job$ of $\tau_n$ misses its deadline.
If the $k^{th}$ job of task $\tau_n$ misses its deadline, then
    \begin{equation*}
\forall \tau_i,\quad kC_n+\sum_{i=1}^{n-1}U_it_i+\sum_{j=1}^{i-1}U_jt_j> t_i
    \end{equation*}
 \end{lemma}
\begin{theorem}
If
\begin{equation*}
\prod_{i=1}^{n} (U_i + 1)\le2,
\end{equation*}
then the worst-case reponse time $R_n$ of task $\tau_n$ is bounded above by
\begin{equation*}
R_n\le \frac{C_n}{\frac{2}{\prod_{i=1}^{n-1} (U_i + 1)}-1}.
\end{equation*}
\end{theorem}
\begin{proof}
\begin{equation}
t_{i}U_i= t_{i+1}-t_i.
\end{equation}

\begin{align*}
&kC_n+\sum_{i=1}^{n-1}U_it_i= t_1\\
\Rightarrow &kC_n+t_n-t_1= t_1\\
\Rightarrow &kC_n+t_1\prod_{i=1}^{n-1} (U_i + 1)-t_1= t_1\\
\Rightarrow &t_1=\frac{kC_n}{2-\prod_{i=1}^{n-1} (U_i + 1)}
\end{align*}
\begin{align*}
R_n&\le kC_n+2\sum_{i=1}^{n-1}U_it_i-(k-1)T_n\\
&= kC_n+2(t_1\prod_{i=1}^{n-1} (U_i + 1)-t_1)-(k-1)T_n\\
&=kC_n+\frac{2kC_n(\prod_{i=1}^{n-1} (U_i + 1)-1)}{2-\prod_{i=1}^{n-1} (U_i + 1)}-(k-1)T_n\\
&=\frac{kC_n\prod_{i=1}^{n-1} (U_i + 1)}{2-\prod_{i=1}^{n-1} (U_i + 1)}-(k-1)T_n\\
&=\frac{kC_n}{\frac{2}{\prod_{i=1}^{n-1} (U_i + 1)}-1}-(k-1)T_n\\
\end{align*}
We now prove the maximum in Eq. (\ref{eq:response-time-supermum-k}) occur for $k=1$.
\begin{align*}
\frac{d}{dk}&\left(\frac{kC_n}{\frac{2}{\prod_{i=1}^{n-1} (U_i + 1)}-1}-(k-1)T_n\right)\\
&=\frac{C_n}{\frac{2}{\prod_{i=1}^{n-1} (U_i + 1)}-1}-T_n\\
&=T_n(\frac{U_n}{\frac{2}{\prod_{i=1}^{n-1} (U_i + 1)}-1}-1)\\
&=T_n(\frac{U_n\prod_{i=1}^{n-1} (U_i + 1)}{2-\prod_{i=1}^{n-1} (U_i + 1)}-1)\\
&=T_n(\frac{U_n\prod_{i=1}^{n-1} (U_i + 1)-2+\prod_{i=1}^{n-1} (U_i + 1)}{2-\prod_{i=1}^{n-1} (U_i + 1)})\\
&=T_n(\frac{\prod_{i=1}^{n} (U_i + 1)-2}{2-\prod_{i=1}^{n-1} (U_i + 1)})\\
\end{align*}
\end{proof}
\section{Introduction}
\label{sec:intro}

Given the emerging trend towards building complex cyber-physical
systems that often integrate external and physical devices, many
real-time and embedded systems are expected to handle a large variety
of workloads. Different formal real-time task models have been
developed to accurately represent these workloads with various
characteristics. Examples include the sporadic task
model~\cite{mok1983fundamental}, the multi-frame task
model~\cite{DBLP:dblp_journals/tse/MokC97}, the self-suspending task
model~\cite{suspension}, the directed-acyclic-graph (DAG) task model,
etc. Many of such formal models have been shown to be expressive
enough to accurately model real systems in practice. For example, the
DAG task model has been used to represent many computation-parallel
multimedia application systems and the self-suspending task model is
suitable to model workloads that may interact with I/O devices. For each of these task models, researchers tend to develop different types of techniques that result in schedulability tests with different computation complexity and performance (e.g., different utilization bounds).

\ifbool{techreport}{Over the years, real-time systems researchers have devoted a significant amount of time and efforts to efficiently analyze different task models. Many successful stories have been told. For many of the above-mentioned task models, efficient scheduling and schedulability analysis techniques have been developed (see \cite{DavisSurvey2011} for a recent survey). Unfortunately, for certain complex models such as the self-suspending task model, existing schedulability tests are rather pessimistic, particularly for the multiprocessor case (e.g., no utilization-based schedulability test exists for globally-scheduled multiprocessor self-suspending task systems). }{}

In this paper, we present \framework{}, a general schedulability analysis framework that is fundamentally based on a $k$-point effective schedulability test under fixed-priority scheduling. The key observation behind our proposed $k$-point test is the following. Traditional fixed-priority schedulability tests often have pseudo-polynomial-time (or even higher) complexity. For example, to verify the schedulability of a (constrained-deadline) task $\tau_k$ under fixed-priority scheduling in uniprocessor systems, the time-demand analysis (TDA) developed in \cite{DBLP:conf/rtss/LehoczkySD89}
can be adopted. That is, if
\begin{equation}
  \label{eq:exact-test-constrained-deadline}
\exists t \mbox{ with } 0 < t \leq D_k {\;\; and \;\;} C_k +
\sum_{\tau_i \in hp(\tau_k)} \ceiling{\frac{t}{T_i}}C_i \leq t,
\end{equation}
then task $\tau_k$ is schedulable under the fixed-priority scheduling algorithm, where $hp(\tau_k)$ is the set of the tasks with higher priority than $\tau_k$, $D_k$, $C_k$, and $T_i$ represent $\tau_k$'s relative deadline, worst-case execution time, and period, respectively. TDA incurs pseudo-polynomial-time complexity to check the time points that lie in $(0, D_k]$ for Eq.~\eqref{eq:exact-test-constrained-deadline}.

To obtain sufficient schedulability tests under fixed priority
scheduling with reduced time complexity (e.g., polynomial-time), our
conceptual innovation is based on the observations by \emph{testing only a subset of such points} to
\emph{derive the minimum $C_k$ that cannot pass the
  schedulability tests}. This idea is
implemented in the \framework{} framework by providing a general
$k$-point effective schedulability test, which only needs to test $k$
points under \textit{any} fixed-priority scheduling when checking
schedulability of the task with the $k^{th}$ highest priority in the
system. This $k$-point effective schedulability test can be viewed as
a ``blackbox" interface that can result in sufficient
utilization-based tests.
 We show the generality of \framework{} by applying it to analyze several concrete example task models, including the constrained- and arbitrary-deadline sporadic task models, the multi-frame task model, the self-suspending task model, and the DAG task model. Note that \framework{} is not only applicable to uniprocessor systems, but also applicable to multiprocessor systems.

\noindent\textbf{Related Work.}
\ifbool{techreport}{An extensive amount of research has been conducted over the past forty years on verifying the schedulability of the classical sporadic task model in both uniprocessor and multiprocessor systems (see \cite{DavisSurvey2011} for a survey of such results). Much progress has also been made in recent years on analyzing more complex task models that are more expressive.}{}
There have been several results in the literature with respect to utilization-based, e.g., \cite{liu1973scheduling,HanTyan-RTSS97,journals/tc/LeeSP04,DBLP:conf/rtas/WuLZ05,kuo2003efficient,bini2003rate,RTSS14a}, \ifbool{techreport}{and non-utilization-based, e.g., \cite{DBLP:conf/rtss/ChakrabortyKT02,DBLP:conf/ecrts/FisherB05}, }{}
schedulability tests for the sporadic real-time task model and its generalizations in uniprocessor systems.
\ifbool{techreport}{
The approaches in \cite{DBLP:conf/rtss/ChakrabortyKT02,DBLP:conf/ecrts/FisherB05} convert the stair function $\ceiling{\frac{t}{T_i}}$ in the time-demand analysis into a linear function if $t$ in Eq.~\eqref{eq:exact-test-constrained-deadline} is large enough. The methods in \cite{DBLP:conf/rtss/ChakrabortyKT02,DBLP:conf/ecrts/FisherB05} are completely different from this paper, in which the linear function of task $\tau_i$ starts after $\frac{t}{T_i} \geq k$, in which our method is based on $k$ points, defined individually by $\tau_1, \tau_2, \ldots, \tau_k$.

}{}
Most of the existing utilization-based schedulability analyses focus on the total utilization bound. That is, if the total utilization of the task system is no more than the derived bound, the task system is schedulable by the scheduling policy. For example, the total utilization bounds derived in \cite{liu1973scheduling,HanTyan-RTSS97,DBLP:dblp_journals/tc/BurchardLOS95} are mainly for rate-monotonic (RM) scheduling, in which the results in \cite{HanTyan-RTSS97} can be extended for arbitrary fixed-priority scheduling. Kuo et al. \cite{kuo2003efficient} further improve the total utilization bound by using the notion of divisibility. Lee et al. \cite{journals/tc/LeeSP04} use linear programming formulations for calculating total utilization bounds
when the period of a task can be selected. Moreover, Wu et al. \cite{DBLP:conf/rtas/WuLZ05} adopt the Network Calculus to analyze the total utilization bounds of several task models.

The novelty of \framework{} comes from a different perspective
from these approaches
\cite{liu1973scheduling,HanTyan-RTSS97,journals/tc/LeeSP04,DBLP:conf/rtas/WuLZ05,kuo2003efficient}. We
do not specifically seek for the total utilization bound. Instead, we
look for the critical value in the specified sufficient schedulability
test while verifying the schedulability of task $\tau_k$.
A natural schedulability condition to express
the schedulability of task $\tau_k$ is a hyperbolic bound, (to be
shown in Lemma \ref{lemma:framework-constrained}), whereas the
corresponding total utilization bound can be obtained (in Lemmas
\ref{lemma:framework-totalU-constrained} and
\ref{lemma:framework-totalU-exclusive}).

The hyperbolic forms are the centric features in \framework{} analysis, in which the test by Bini et al. \cite{bini2003rate}  for sporadic real-time tasks and our recent result in \cite{RTSS14a} for bursty-interference analysis are both special cases and simple implications from the \framework{} framework. With the hyperbolic forms, we are then able to provide many interesting observations with respect to the required quantitive features to be measured, like the total utilization bounds, speed-up factors, etc., not only for uniprocessor scheduling but also for multiprocessor scheduling.
For more details, we will provide further explanations at the end of Sec. \ref{sec:framework} after the framework is presented. For the studied task models to demonstrate the applicability of \framework{}, we will summarize some of the latest results on these task models in their corresponding sections.

\noindent\textbf{Contributions.} In this paper, we present a general
schedulability analysis framework, \framework{}, that can be applied
to analyze a number of complex real-time task models, on both
uniprocessors and multiprocessors.
For any
task model, if a corresponding $k$-point effective schedulability test
can be constructed, then a sufficient utilization-based test can be
derived by the \framework{} framework. We show the generality of \framework{} by applying it to several task models, in which the results are better or more general compared to the state-of-the-art:

\begin{enumerate}
\item For uniprocessor constrained-deadline sporadic task systems, the speed-up factor of our obtained schedulability test is 1.76322. This value is the same as the lower bound and upper bound of deadline-monotonic (DM) scheduling shown by Davis et al.~\cite{DBLP:journals/rts/DavisRBB09}. Our result is thus stronger (and requires a much simpler proof), as we show that the same factor holds for a polynomial-time schedulability test (not just the DM scheduler). For uniprocessor arbitrary-deadline sporadic task systems, our obtained utilization-based test works for any fixed-priority scheduling with arbitrary priority-ordering assignment.
\item For multiprocessor DAG task systems under global rate-monotonic (RM) scheduling, the capacity-augmentation
  factor, as defined in ~\cite{Li:ECRTS14} and Sec.~\ref{sec:multiprocessor} in this paper, of our obtained test is
  3.62143. This result is better than the best existing result, which
  is 3.73, given by Li et al.~\cite{Li:ECRTS14}. Our result is also applicable for conditional sporadic DAG task systems \cite{DBLP:conf/ecrts/BaruahBM15}.

\item For multiprocessor self-suspending task systems, we obtain the \textit{first} utilization-based test for global RM.
\item For uniprocessor multi-frame task systems, our obtained utilization bound is superior to the results by Mok and Chen~\cite{DBLP:dblp_journals/tse/MokC97} analytically and Lu et al. \cite{lu2007new} in our simulations. \ifbool{techreport}{The analysis is in Appendix C, whereas the evaluation result is in Appendix D.}{Due to space limitations, the analysis is in Appendix C in the report \cite{DBLP:journals/corr/abs-1501.07084}, whereas the evaluation result is in Appendix D in  \cite{DBLP:journals/corr/abs-1501.07084}.}

\end{enumerate}

Note that the emphasis of this paper is not to show that the resulting tests for different task models by applying the \framework{} framework are better than existing work. Rather, we want to show that the \framework{} framework is general, easy to use, and has relatively low time complexity, but is still able to generate good tests. By demonstrating the applicability of the \framework{} framework to several task models, we believe that this  framework has great potential in analyzing many other complex real-time task models, where the existing analysis approaches are insufficient or cumbersome. To the best of our knowledge, together with \frameworkkq{} to be explained later, these are the first general schedulability analysis frameworks that can be potentially applied to analyze a large set of real-time task models under any fixed-priority scheduling algorithm in both uniprocessor and multiprocessor systems.

\noindent{\bf Comparison to \frameworkkq{}:}
The concept of testing $k$ points only is also the key in
another framework designed by us, called \frameworkkq{}
\cite{DBLP:journals/corr/abs-k2q}.  Even though \frameworkkq{} and \framework{} share the
same idea by testing and evaluating only $k$ points, they are based on
completely different criteria for testing.  In \framework{}, all the testings and
formulations are based on \emph{only the higher-priority task
  utilizations}. In \frameworkkq{}, the testings are based \emph{not
  only on the higher-priority task utilizations, but also on the
  higher-priority task execution times}.  The above difference
in the formulations results in completely different properties and
mathematical closed-forms.  The
natural schedulability condition of \framework{} is a \emph{hyperbolic form} for testing
the schedulability, whereas the natural schedulability condition of \frameworkkq{} is a
\emph{quadratic form} for testing the schedulability or the response
time of a task.

\emph{If one framework were dominated by another or these two frameworks
were just with minor difference in mathematical formulations, it
wouldn't be necessary to separate and present
them as two different frameworks.} Both frameworks are in fact needed
and have to be applied for different cases.  Due to space limitation,
we can only shortly explain their differences,
advantages, and disadvantages in this paper.  For completeness, another
document has been prepared in
\cite{DBLP:journals/corr/framework-compare} to present the similarity,
the difference and the characteristics of these two frameworks in details.

Since the formulation of \framework{} is more restrictive than
\frameworkkq{}, its applicability is limited by the possibility to
formulate the tests purely by using higher-priority task utilizations
without referring to their execution times. There are cases, in which
formulating the higher-priority interference by using only task
utilizations for \framework{} is troublesome. For such cases, further
introducing the upper bound of the execution time by using
\frameworkkq{} is more precise.
\ifbool{techreport}{The above cases can be found in (1)
the schedulability tests for arbitrary-deadline sporadic task systems
in uniprocessor scheduling, (2) multiprocessor global fixed-priority
scheduling when adopting the forced-forwarding schedulability test,
etc.\footnote{ c.f. Sec. 5/6 in \cite{DBLP:journals/corr/abs-k2q} for
  the detailed proofs and Sec. 5/6 in
  \cite{DBLP:journals/corr/framework-compare} for the performance
  comparisons.}}{}
In general, if we can formulate the schedulability
tests into the \framework{} framework by purely using higher-priority
task utilizations, it is also usually possible to formulate it into
the \frameworkkq{} framework by further introducing the task execution
times. In such cases, the same pseudo-polynomial-time (or exponential
time) test is used, and the
utilization bound or speed-up factor analysis
derived from the \framework{} framework is, in
general, tighter and better.

\ifbool{techreport}{
In a nutshell, with respect to quantitive metrics, like utilization bounds or speedup factor analysis, \framework{} is more precise, whereas \frameworkkq{} is
more general. If the exact (or very precise) schedulability test can
be constructed and the test can be converted into \framework{},
e.g., uniprocessor scheduling for
constrained-deadline task sets, then, adopting \framework{} \emph{may} lead to
tight results. By adopting \frameworkkq{}, we may be able to start
from a more complicated test with exponential-time complexity and
convert it to a linear-time approximation with better results than
\framework{}. Although \framework{} is more restrictive than
\frameworkkq{}, both of them are general enough to cover a range of
applications, ranging from uniprocessor systems to
multiprocessor systems.
For more information and comparisons, please refer to \cite{DBLP:journals/corr/framework-compare}.
}
{
}

\section{Sporadic Task and Scheduling Models}
\label{sec:model}

A sporadic task $\tau_i$ is released repeatedly, with each such
invocation called a job. The $j^{th}$ job of $\tau_i$, denoted
$\tau_{i,j}$, is released at time $r_{i,j}$ and has an absolute deadline at time
$d_{i,j}$. Each job of any task $\tau_i$ is assumed to have
execution time $C_i$. Here in this paper, whenever we refer to
the execution time of a job, we mean for the worst-case execution time
of the job since all the analyses we use are safe by only considering the worst-case execution time.  Successive jobs of the same task are
required to execute in sequence. Associated with each task $\tau_i$
are a period $T_i$, which specifies the minimum time between two
consecutive job releases of $\tau_i$, and a deadline $D_i$, which
specifies the relative deadline of each such job, i.e.,
$d_{i,j}=r_{i,j}+D_i$. The utilization of a task $\tau_i$ is defined
as $U_i=C_i/T_i$.

A sporadic task system $\tau$ is said to be an implicit-deadline
system if $D_i = T_i$ holds for each $\tau_i$. A sporadic task system
$\tau$ is said to be a constrained-deadline system if $D_i \leq T_i$
holds for each $\tau_i$.  Otherwise, such a sporadic task system
$\tau$ is an arbitrary-deadline system.

A task is said \emph{schedulable} by a scheduling policy if all of its
jobs can finish before their absolute deadlines.  A task system is
said \emph{schedulable} by a scheduling policy if all the tasks in the
task system are schedulable. A \emph{schedulability test}
expresses sufficient conditions to ensure the feasibility of the
resulting schedule by a scheduling policy.

Throughout the paper, we will focus on fixed-priority preemptive
scheduling. That is, each task is associated with a priority level.
For a uniprocessor system, i.e., except
Sec.~\ref{sec:multiprocessor}, the scheduler always dispatches the
job with the highest priority in the ready queue to be executed. For a
uniprocessor system, it has been shown that RM
scheduling is an optimal fixed-priority scheduling policy for
implicit-deadline systems \cite{liu1973scheduling} and
DM scheduling is an optimal fixed-priority
scheduling policy for constrained-deadline
systems\cite{journals/pe/LeungW82}.

To verify the schedulability of task $\tau_k$ under
fixed-priority scheduling in uniprocessor systems, the time-demand
analysis developed in \cite{DBLP:conf/rtss/LehoczkySD89}
can be adopted, as discussed earlier. That is, if Eq.~\eqref{eq:exact-test-constrained-deadline} holds,

 then task $\tau_k$ is schedulable under the fixed-priority scheduling
algorithm.
For the simplicity of presentation,
we will demonstrate how the framework works using ordinary sporadic real-time task systems
in Sec.~\ref{sec:framework} and Sec.~\ref{sec:application-FP}. We
will demonstrate more applications with respect to multi-frame tasks
\cite{DBLP:dblp_journals/tse/MokC97} in Appendix C\citetechreport{}
and with respect to multiprocessor scheduling in
Sec.~\ref{sec:multiprocessor}.

\vspace{-2mm}
\section{Analysis Flow}
\label{sec:flow}

The proposed \framework{} framework only tests the
schedulability of a specific task $\tau_k$, under the assumption
that the higher-priority tasks are already verified to be schedulable
by the given scheduling policy. Therefore, this framework has to be
applied for each of the given tasks. A task system is schedulable by
the given scheduling policy only when all the tasks in the system can
be verified to meet their deadlines.  The results can be extended to
test the schedulability of a task system in linear time complexity or to allow on-line admission control in constant time complexity if the schedulability
condition (or with some more pessimistic simplifications) is
monotonic. Such extensions are provided in Appendix A for some cases.

Therefore, for the rest of this paper, we implicitly assume that all
the higher-priority tasks are already verified to be schedulable by
the scheduling policy.  We will only present the schedulability test
of a certain task $\tau_k$, that is being analyzed, under the
above assumption. For notational brevity, we implicitly assume that there
are $k-1$ tasks, say $\tau_1, \tau_2, \ldots, \tau_{k-1}$ with
higher-priority than task $\tau_k$. Moreover, we only consider the cases when $k \geq 2$, since $k=1$ is pretty trivial.

\section{\framework{} Framework}
\label{sec:framework}

This section presents the basic properties of the \framework{}
framework for testing the schedulability of task $\tau_k$ in a given
set of real-time tasks (depending on the specific models given in
each application as shown later in this paper). We will first provide examples
to explain and define the \emph{$k$-point effective schedulability
  test}. Then, we will provide the fundamental properties of the
corresponding utilization-based tests. Throughout this section, we
will implicitly use sporadic task systems defined in
Sec.~\ref{sec:model} to simplify the presentation. The concrete
applications will be presented in Secs.~\ref{sec:application-FP} - \ref{sec:multiprocessor}.

The $k$-point effective schedulability test is a sufficient
schedulability test that verifies only $k$ time points, defined by the
$k-1$ higher-priority tasks and task $\tau_k$. For example, instead of
testing all the possible $t$ in the range of $0$ and $D_k$ in
Eq.~\eqref{eq:exact-test-constrained-deadline}, we can simply test
only $k$ points. It may seem to be very pessimistic to only test
$k$ points. However, if these $k$ points are \textit{effective},\footnote{As to be clearly illustrated later, the $k$ points can be considered effective if they can define certain extreme cases of task parameters. For example, the ``difficult-to-schedule'' concept first introduced by Liu and Layland~\cite{liu1973scheduling} defines $k$ effective points that are used in Example \ref{example-1}. In their case~\cite{liu1973scheduling}, the selected set of the $k$ points was ``very'' effective because the tested task $\tau_k$ becomes unschedulable if $C_k$ is increased by an arbitrarily small value $\varepsilon$.} the resulting
schedulability test may be already good. We now demonstrate two
examples.

\begin{example}
\label{example-1}
  {\bf Implicit-deadline task systems}: Suppose that the tasks are indexed by
  the periods, i.e., $T_1 \leq \cdots \leq
  T_k$. When $T_k \leq 2T_1$, task $\tau_k$ is schedulable by RM if
  there exists $j \in \setof{1,2,\ldots,k}$ where
\begin{equation}
  \label{eq:precodition-schedulability-sporadic}\small
  C_k + \sum_{i=1}^{k-1} C_i + \sum_{i=1}^{j-1} C_i = C_k + \sum_{i=1}^{k-1} T_i U_i + \sum_{i=1}^{j-1} T_i U_i \leq T_j.
\end{equation}\normalsize  \endproof
\end{example}
That is, in the above example, it is sufficient to only test $T_1,
T_2, \ldots, T_k$. The case defined in the above example is utilized
by Liu and Layland \cite{liu1973scheduling} for deriving the least
utilization upper bound $69.3\%$ for RM scheduling. We can
make the above example more generalized as follows:

\begin{example}
\label{example-2}
{\bf Implicit-deadline task systems with given ratios of periods}:
Suppose that $f T_i \leq T_k$ for a given integer $f$ with $f \geq 1$
for any higher-priority task $\tau_i$, for all $i=1,2,\ldots,k-1$.
Let $t_i$ be
$\floor{\frac{T_k}{T_i}}T_i$. Suppose that the $k-1$ higher
priority tasks are indexed such that $t_1 \leq t_2 \leq \cdots \leq
t_{k-1} \leq t_k$, where $t_k$ is defined as $T_k$.  Task $\tau_k$ is
schedulable under RM if there exists $j$ with $1 \leq j \leq k$ such that
\begin{equation}
  \label{eq:precodition-schedulability-sporadic-f}
 C_k + \sum_{i=1}^{k-1} t_i U_i + \sum_{i=1}^{j-1} C_i \leq  C_k +
 \sum_{i=1}^{k-1} t_i U_i + \sum_{i=1}^{j-1} \frac{1}{f} t_i U_i\leq t_j,
\end{equation}
where the first inequality in
Eq.~\eqref{eq:precodition-schedulability-sporadic-f} is due to the
fact $C_i = T_i U_i \leq \frac{1}{f} t_i U_i$.  That is, in the above example, it is sufficient to only test
$\floor{\frac{T_k}{T_1}}T_1, \floor{\frac{T_k}{T_2}}T_2, \ldots,
\floor{\frac{T_k}{T_{k-1}}}T_{k-1}, T_k$.
  \endproof
\end{example}

With the above examples, for a given set $\setof{t_1, t_2, \ldots
  t_k}$, we now define the $k$-point effective schedulability test as follows:
\begin{definition}
  \label{def:kpoints}
  A $k$-point effective schedulability test is a sufficient
  schedulability test of a fixed-priority scheduling policy, that verifies the existence of $t_j \in \setof{t_1, t_2, \ldots t_k}$ with $0 < t_1 \leq t_2 \leq \cdots \leq t_k$ such that \begin{equation}
    \label{eq:precodition-schedulability}
    C_k + \sum_{i=1}^{k-1} \alpha_i t_i U_i + \sum_{i=1}^{j-1} \beta_i t_i U_i \leq t_j,
  \end{equation}
  where $C_k > 0$, $\alpha_i > 0$, $U_i > 0$, and $\beta_i >0$ are dependent upon the setting
  of the task models and task $\tau_i$.
\end{definition}
 For Example~\ref{example-1}, the effective values in
$\setof{t_1, t_2, \ldots t_k}$ are $T_1, T_2, \ldots, T_k$, and
$\alpha_i=\beta_i=1$ for each task $\tau_i$. For
Example~\ref{example-2}, the effective values in $\setof{t_1,
  t_2, \ldots t_k}$ are with $\alpha_i=1$ and $\beta_i \leq
\frac{1}{f}$ for each task $\tau_i$.

Moreover, we only consider non-trivial cases,
in which $C_k >0$, $t_k > 0$, $0 < \alpha_i$, $0 < \beta_i$, and $0 < U_i \leq 1$ for $i=1,2,\ldots,k-1$.
The definition of the $k$-point last-release schedulability test
$C_k + \sum_{i=1}^{k-1} \alpha_i t_i U_i + \sum_{i=1}^{j-1}
\beta_i t_i U_i \leq t_j$
in Definition \ref{def:kpoints} only slightly differs from the
test
$C_k +
\sum_{i=1}^{k-1} \alpha_i t_i U_i + \sum_{i=1}^{j-1} \beta_i C_i \leq
t_j$
in the \frameworkkq{} framework \cite{DBLP:journals/corr/abs-k2q}.
However, since the tests are different, they are used for different
situations.

With these $k$ points, we are able to define the corresponding
coefficients $\alpha_i$ and $\beta_i$ in the $k$-point effective
schedulability test of a scheduling algorithm. The elegance of the
\framework{} framework is to use only the parameters $\alpha_i$ and
$\beta_i$ to analyze whether task $\tau_k$ can pass the
schedulability test. Therefore, the \framework{} framework provides
corresponding utilization-based tests \emph{automatically} if the $k$-point effective
schedulability test and the corresponding parameters $\alpha_i$ and
$\beta_i$ can be defined, which will be further demonstrated in
the following sections with several applications.

We are going to present the properties
resulting from the $k$-point effective schedulability test under given
$\alpha_i$ and $\beta_i$.  In the following lemmas, we are going to
seek the extreme cases for these $k$ testing points under the given
setting of utilizations and the defined coefficients $\alpha_i$ and
$\beta_i$.  To make the notations clear, these extreme testing points
are denoted as $t_i^*$ for the rest of this paper.  The procedure will
derive $k-1$ extreme testing points, denoted as $t_1^*, t_2^*, \ldots,
t_{k-1}^*$, whereas $t_k^*$ is defined as $t_k$ plus a slack variable (to be defined in the proof of Lemma~\ref{lemma:framework-constrained}) for notational
brevity.
Lemmas~\ref{lemma:framework-constrained} to \ref{lemma:framework-totalU-exclusive} are useful to analyze the utilization bound, the hyperbolic bound, etc., for given scheduling strategies, when
$\alpha$ and $\beta$ can be easily defined based on the scheduling policy, with
$0 < t_k$ and
$0 < \alpha_i \leq \alpha$, and $0 < \beta_i \leq \beta$ for any
$i=1,2,\ldots,k-1$.

\begin{lemma}
\label{lemma:framework-constrained}
For a given $k$-point effective schedulability test of a scheduling
algorithm, defined in
Definition~\ref{def:kpoints},
in which $0 < t_k$ and $0 < \alpha_i \leq \alpha$, and $0 < \beta_i \leq \beta$ for any
$i=1,2,\ldots,k-1$, task $\tau_k$ is schedulable by the scheduling
algorithm if the following condition holds
\begin{equation}
\label{eq:schedulability-constrained}
\frac{C_k}{t_k} \leq \frac{\frac{\alpha}{\beta}+1}{\prod_{j=1}^{k-1} (\beta U_j + 1)} - \frac{\alpha}{\beta}.
\end{equation}
\end{lemma}
\begin{proof}
  If $\frac{\frac{\alpha}{\beta}+1}{\prod_{j=1}^{k-1} (\beta U_j + 1)}
  - \frac{\alpha}{\beta} \leq 0$, the condition in
  Eq.~\eqref{eq:schedulability-constrained} never holds since $C_k > 0$, and the
  statement is vacuously true.  We focus on the  case $\frac{\frac{\alpha}{\beta}+1}{\prod_{j=1}^{k-1}
    (\beta U_j + 1)} - \frac{\alpha}{\beta} > 0$.

  We prove this lemma by showing that the condition in
  Eq.~\eqref{eq:schedulability-constrained} leads to the satisfactions of the
  schedulability condition listed in
  Eq.~(\ref{eq:precodition-schedulability}) by using contrapositive.
  By taking the negation of the schedulability condition in
  Eq.~(\ref{eq:precodition-schedulability}), we know that if task
  $\tau_k$ is \emph{not schedulable} by the scheduling policy, then
  for each $j=1,2,\ldots, k$
  \begin{equation}
    \label{eq:lp-init-constraints}
    C_k + \alpha \sum_{i=1}^{k-1} t_i U_i + \beta\sum_{i=1}^{j-1} t_i U_i \geq
    C_k + \sum_{i=1}^{k-1} \alpha_i t_i U_i + \sum_{i=1}^{j-1} \beta_i t_i U_i > t_j,
  \end{equation}
  due to $0 < \alpha_i \leq \alpha$, and $0 < \beta_i \leq \beta$ for any
$i=1,2,\ldots,k-1$
  To enforce the condition in
  Eq.~\eqref{eq:lp-init-constraints}, we are going to
  show that $C_k$ must have some lower bound. Therefore, if $C_k$ is
  no more than this lower bound, then task $\tau_k$ is schedulable by the
  scheduling policy.

  For the rest of the proof, we replace $>$ with $\geq$ in
  Eq.~\eqref{eq:lp-init-constraints}, as the infimum and the minimum
  are the same when presenting the inequality with $\geq$.  Moreover,
  we also relax the problem by replacing the constraint $t_{j+1} \geq
  t_j$ with $t_j \geq 0$ for $j=1,2,\ldots,k-1$. Therefore, the
  unschedulability for satisfying Eq.~\eqref{eq:lp-init-constraints}
  implies that $C_k > C_k^*$, where $C_k^*$ is
  defined in the following optimization problem:
  \begin{subequations}\label{eq:lp-init}
\small  \begin{align}
    \mbox{min\;\;} & C_k^* \label{eq:precodition-schedulability-objective}\\
    \mbox{s.t.\;\;} &     C_k^* + \sum_{i=1}^{k-1} \alpha t_i^* U_i + \sum_{i=1}^{j-1} \beta t_i^* U_i \geq t_j^* &\forall j=1,\ldots, k-1,     \label{eq:precodition-schedulability-negation-0}\\
    &    t_j^* \geq 0\;&\forall j=1,\ldots, k-1,     \label{eq:precodition-schedulability-negation-1}\\
     &     C_k^* + \sum_{i=1}^{k-1} (\alpha +\beta) t_i^* U_i  \geq t_k,     \label{eq:precodition-schedulability-negation-2}
  \end{align}
  \end{subequations}
  where $t^*_1, t^*_2, \ldots, t^*_{k-1}$ and $C_k^*$ are variables; and $\alpha$, $\beta$ are constants.

  Let $s \geq 0$ be a slack variable such that $C_k^* +
  \sum_{i=1}^{k-1} (\alpha +\beta) t_i^* U_i = t_k+s$.  Therefore, $C_k^* =
   t_k+s -\sum_{i=1}^{k-1} (\alpha +\beta) t_i^* U_i$. By replacing $C_k^*$ in Eq.~\eqref{eq:precodition-schedulability-negation-0}, we have
 \begin{align}
   & t_k+s - (\sum_{i=1}^{k-1} \alpha t_i^*U_i + \sum_{i=1}^{k-1} \beta t_i^*U_i) + \sum_{i=1}^{k-1} \alpha t_i^*U_i + \sum_{i=1}^{j-1} \beta t_i^*U_i\nonumber\\
    =\; & t_k+s- \sum_{i=j}^{k-1} \beta t_i^* U_i
    \geq t_j^*, \;\;\;\forall j=1,\ldots, k-1. \label{eq:precodition-schedulability-negation}
  \end{align}
  For notational brevity, let $t_k^*$ be $t_k+s$.
 Therefore, the linear programming in Eq.~\eqref{eq:lp-init} can be rewritten as follows:
\begin{subequations}
    \label{eq:lp-framework-constrained}
  \begin{align}
    \mbox{min } &
    t_k^* -\sum_{i=1}^{k-1} (\alpha +\beta) t_i^* U_i\\
    \mbox{s.t.} \;\;&
t_k^*-\beta \sum_{i=j}^{k-1} t_i^* U_i \geq t_j^*,
      & \forall 1 \leq j \leq k - 1 \label{eq:lp-framework-constrained-constraints}\\
&t_j^* \geq 0
      & \forall 1 \leq j \leq k - 1 \label{eq:lp-framework-constrained-boundaryconstraints}\\
&t_k^* \geq t_k \label{eq:lp-framework-constrained-slack-constraints}
  \end{align}
  \end{subequations}

  The remaining proof is to solve the above linear programming to obtain the minimum $C_k^*$ if $\frac{\frac{\alpha}{\beta}+1}{\prod_{j=1}^{k-1} (\beta U_j + 1)} - \frac{\alpha}{\beta} > 0$.
Our proof strategy is to solve the linear programming analytically as a function of $t_k^*$. This can be imagined as if $t_k^*$ is given. At the end, we will prove the optimality by considering all possible $t_k^* \geq t_k$.
  This involves three steps:
  \begin{itemize}
  \item Step 1: we analyze certain properties of optimal solutions based on the extreme point theorem for linear programming \cite{luenberger2008linear} under the assumption that $t_k^*$ is given as a constant, i.e., $s$ is known.
  \item Step 2: we present a specific solution in an \emph{extreme point}, as a function of $t_k^*$.
  \item Step 3: we prove that the above extreme point solution gives the minimum $C_k^*$  if $\frac{\frac{\alpha}{\beta}+1}{\prod_{j=1}^{k-1} (\beta U_j + 1)} - \frac{\alpha}{\beta} > 0$.
  \end{itemize}

  {\bf [Step 1:]} In this step, we assume that
  $s$ is given,  i.e., $t_k^*$ is specified as a constant. The original linear
  programming in Eq.~(\ref{eq:lp-framework-constrained}) has $k$
  variables and $2(k-1)+1$ constraints. After specifying the value
  $t_k^*$ as a given constant, the new linear programming without the
  constraint in
  Eq.~\eqref{eq:lp-framework-constrained-slack-constraints} has only
  $k-1$ variables and $2(k-1)$ constraints.  Thus, according to the
  extreme point theorem for linear programming
  \cite{luenberger2008linear}, the linear constraints form a
  polyhedron of feasible solutions. The extreme point theorem states
  that either there is no feasible solution or one of the extreme
  points in the polyhedron is an optimal solution when the objective
  of the linear programming is finite. To satisfy
  Eqs.~\eqref{eq:lp-framework-constrained-constraints}
  and~\eqref{eq:lp-framework-constrained-boundaryconstraints}, we know
  that $t_j^* \leq t_k^*$ for $j=1,2,\ldots,k-1$, due to $t_i^* \geq
  0$, $0 < \beta$, $0 < \alpha$ and $U_i > 0$
  for $i=1,2, \ldots,k-1$. As a result, the objective of the above
  linear programming is $t_k^* -\sum_{i=1}^{k-1} (\alpha +\beta) t_i^* U_i \geq t_k^* -\sum_{i=1}^{k-1} (\alpha +\beta) t_k^* U_i$, which is finite (as a function of $t_k^*$, $\alpha$, and $\beta$) under the assumption $0 < \beta$, $0 < \alpha$ and $0 < \sum_{i=1}^{k-1}U_i \leq 1$.

  According to the extreme point theorem, one of the extreme points is
  the optimal solution of Eq.~\eqref{eq:lp-framework-constrained} for a given $t_k^*$.
  There are $k-1$ variables with $2(k-1)$ constraints in
  Eq.~\eqref{eq:lp-framework-constrained} for a given $t_k^*$. An extreme point must have
  at least $k-1$ \emph{active} constraints in
  Eqs.~\eqref{eq:lp-framework-constrained-constraints} and \eqref{eq:lp-framework-constrained-boundaryconstraints},  in which
  their $\geq$ are set to equality $=$.

We now prove that an extreme point solution is feasible for Eq.~\eqref{eq:lp-framework-constrained} by setting $t_j^*$ either to $0$ or to $t_k^*-\beta \sum_{i=j}^{k-1} t_i^* U_i = t_j^* > 0$ for $j=1,2,\ldots,k-1$.
Suppose for contradiction that there exists a task $\tau_h$ with $0 = t_h^* = t_k^*-\beta \sum_{i=h}^{k-1} t_i^* U_i$.
Let $\omega$ be the
index of the next task after $\tau_h$ with $t_{\omega}^* > 0$ in this extreme point solution, i.e., $t_{h}^* = t_{h+1}^* = \cdots= t_{\omega-1}^*=0$. If $t_i^*=0$ for $h \leq i \leq k-1$, then $\omega$ is set to $k$ and $t_{\omega}^*$ is $t_k^*$. Therefore, the conditions $t_k^*-\beta \sum_{i=h}^{k-1} t_i^* U_i = t_h^*=0$ and  $t_{h+1}^* = \cdots= t_{\omega-1}^*=0$ imply the contradiction that $0=t_h^* = t_k^*-\beta \sum_{i=h}^{k-1} t_i^* U_i = t_k^*-\beta \sum_{i=\omega}^{k-1} t_i^* U_i \geq t_{\omega}^* > 0$ when $\omega \leq k-1$ or $0 = t_h^* =t_k^*-\sum_{i=h}^{k-1} t_i^* U_i  =t_k^*>0$ when $\omega=k$.

By the above analysis and the pigeonhole principle, a feasible extreme point solution of Eq.~\eqref{eq:lp-framework-constrained} can be represented by two sets ${\bf T}_1$ and ${\bf T}_2$ of the $k-1$ higher-priority tasks, in which $t_j^* = 0$ if $\tau_j$ is in ${\bf T}_1$ and $t_k^*-\beta \sum_{i=j}^{k-1} t_i^* U_i = t_j^* > 0$ if task $\tau_j$ is in ${\bf T}_2$. With the above discussions, we have ${\bf T}_1\cup{\bf T}_2=\setof{\tau_1, \tau_2, \ldots, \tau_{k-1}}$ and ${\bf T}_1\cap {\bf T}_2 = \emptyset$.

{\bf [Step 2:]}
For a given $t_k^*$, one special extreme point solution is to put $t_k^* - \beta \sum_{i=j}^{k-1} t_i^* U_i = t_j^*$ for every $j=1,2,\ldots,k-1$, i.e., ${\bf T}_1$ as an empty set. Therefore,
\begin{equation}
\label{eq:periodrelation}
\forall 1 \leq i \leq k - 1, \quad t_{i+1}^* - t_i^* = \beta t_i^* U_i,
\end{equation}
which implies that
\begin{equation}
\label{eq:2ndperiodrelation}
\dfrac{t_{i+1}^*}{t_i^*} = \beta U_i + 1.
\end{equation}
  Moreover,
\begin{equation}
\label{eq:3rdperiodrelation}
 \dfrac{t_i^*}{t_k^*}= \prod_{j=i}^{k-1}\frac{t_j^*}{t_{j+1}^*} = \frac{1}{\prod_{j=i}^{k-1} (\beta U_j + 1)}.
\end{equation}
The above extreme point solution is always feasible in the linear programming of Eq.~\eqref{eq:lp-framework-constrained} since
\begin{equation}
  0 < \dfrac{t_i^*}{t_k^*},  \;\;\;\forall i=1,2,\ldots,k-1.
\end{equation}
By Eq.~\eqref{eq:periodrelation}, we have
  \begin{equation}
\label{eq:alpha+beta}
    (\alpha
    +\beta)U_i t_i^* = (t_{i+1}^*-t_i^*) (\frac{\alpha}{\beta}+1).
  \end{equation}
  Therefore,  in this extreme point solution, the objective function of Eq.~\eqref{eq:lp-framework-constrained} is
  \begin{align}
    &t_k^* - \sum_{i=1}^{k-1} (\alpha
    +\beta)U_it_i^*= t_k^* - (t_k^*-t_1^*) (\frac{\alpha}{\beta}+1)\nonumber\\
 = & t_k^*\left(\frac{t_1^*}{t_k^*}(\frac{\alpha}{\beta}+1)-\frac{\alpha}{\beta}\right) \overset{1}{=}
 t_k^*\left(\frac{\frac{\alpha}{\beta}+1}{\prod_{j=1}^{k-1} (\beta U_j + 1)}-\frac{\alpha}{\beta}\right),
  \end{align}
where the last equality $\overset{1}{=}$ is due to Eq.~\eqref{eq:3rdperiodrelation} when $i$ is $1$.

{\bf [Step 3:]} From Step 1, a feasible extreme point solution is with ${\bf T}_1\cup{\bf T}_2=\setof{\tau_1, \tau_2, \ldots, \tau_{k-1}}$ and ${\bf T}_1\cap {\bf T}_2 = \emptyset$.
 As a result, we can simply drop all the tasks in ${\bf T}_1$ and use the remaining tasks in ${\bf T}_2$ by adopting the same procedures from Eq.~\eqref{eq:periodrelation} to Eq.~\eqref{eq:alpha+beta} in Step 2. The resulting objective function of this extreme point solution for the linear programming in
    Eq.~\eqref{eq:lp-framework-constrained} is $t_k^*(\frac{\frac{\alpha}{\beta}+1}{\prod_{\tau_j \in {\bf T}_2} (\beta U_j + 1)} - \frac{\alpha}{\beta}) \geq t_k^*(\frac{\frac{\alpha}{\beta}+1}{\prod_{j=1}^{k-1} (\beta U_j + 1)}-\frac{\alpha}{\beta})$ due to the fact that $\prod_{\tau_j \in {\bf T}_2} (\beta U_j + 1) \leq \prod_{j=1}^{k-1} (\beta U_j + 1)$.

    Therefore, for a given $s \geq 0$, i.e., $t_k^* \geq t_k$, all the other extreme points of
    Eq.~\eqref{eq:lp-framework-constrained} were dominated by the one
    specified in Step 2.
  By the above analysis, if   $\frac{\frac{\alpha}{\beta}+1}{\prod_{j=1}^{k-1} (\beta U_j +
      1)}-\frac{\alpha}{\beta} > 0$, we know that
    $(t_k+s)(\frac{\frac{\alpha}{\beta}+1}{\prod_{j=1}^{k-1} (\beta
      U_j + 1)}-\frac{\alpha}{\beta})$ is an increasing function of
    $s$, in which the minimum happens when $s$ is $0$. As a result, we
    reach the conclusion of the lemma.
\end{proof}

We now provide two extended lemmas based on
Lemma~\ref{lemma:framework-constrained}, used for given $\alpha$ and
$\beta$ when $\alpha_i \leq \alpha$ and $\beta_i \leq \beta$ for
$i=1,2,\ldots,k-1$. Their proofs are in Appendix B.

\begin{lemma}
\label{lemma:framework-totalU-constrained}
For a given $k$-point effective schedulability test of a scheduling
algorithm, defined in
Definition~\ref{def:kpoints},
in which $0 < t_k$ and $0 < \alpha_i \leq \alpha$ and $0 < \beta_i \leq \beta$ for any
$i=1,2,\ldots,k-1$, task $\tau_k$ is schedulable by the scheduling
algorithm if
\begin{equation}
\label{eq:schedulability-totalU-constrained}
\frac{C_k}{t_k} + \sum_{i=1}^{k-1}U_i \leq \begin{cases}
  1, & (\alpha+\beta)^{\frac{1}{k}} < 1\\
  (k-1)\frac{\left((1+\frac{\beta}{\alpha})^{\frac{1}{k-1}}-1\right)}{\beta}, & (\alpha+\beta)^{\frac{1}{k}} < \alpha\\
\frac{(k-1)((\alpha+\beta)^{\frac{1}{k}}-1)+((\alpha+\beta)^{\frac{1}{k}}-\alpha)}{\beta}  & \mbox{ otherwise}.
\end{cases}
\end{equation}
\end{lemma}

\begin{lemma}
\label{lemma:framework-totalU-exclusive}
For a given $k$-point effective schedulability test of a scheduling
algorithm, defined in
Definition~\ref{def:kpoints},
in which $0 < t_k$ and $0 < \alpha_i \leq \alpha$ and $0 < \beta_i \leq \beta$ for any
$i=1,2,\ldots,k-1$,
task $\tau_k$ is schedulable by the scheduling
algorithm if
\begin{equation}
\label{eq:schedulability-totalU-exclusive}
\beta \sum_{i=1}^{k-1}U_i \leq \ln(\frac{\frac{\alpha}{\beta}+1}{\frac{C_k}{t_k}+\frac{\alpha}{\beta}}).
\end{equation}
\end{lemma}

We also construct the following Lemma~\ref{lemma:framework-general},  c.f. Appendix B for the proof, as the most powerful method for a concrete task system.
Throughout the paper, we will not build theorems and corollaries based on
Lemma~\ref{lemma:framework-general}\ifbool{techreport}{ but we will
  evaluate how it performs in the experimental section.}{, the
  performance evaluation can be found in the report \cite{DBLP:journals/corr/abs-1501.07084}.}

\begin{lemma}
\label{lemma:framework-general}
For a given $k$-point effective schedulability test of a fixed-priority scheduling
algorithm, defined in
Definition~\ref{def:kpoints}, task $\tau_k$ is schedulable by the scheduling algorithm,
in which $0 < t_k$ and $0 < \alpha_i$ and $0 < \beta_i$ for any
$i=1,2,\ldots,k-1$,
 if
the following condition holds
\begin{equation}
\label{eq:schedulability-general}
0 < \frac{C_k}{t_k} \leq 1 -  \sum_{i=1}^{k-1}  \frac{U_i(\alpha_i
  +\beta_i)}{\prod_{j=i}^{k-1} (\beta_jU_j + 1)}.
\end{equation}
\end{lemma}

\noindent{\bf{\large Remarks and how to use the framework}:}
After presenting the \framework{} framework, here, we explain how to use the \framework{} framework and summarize how we
plan to demonstrate its applicability in several task models in the following sections.
The \framework{} framework relies on the users to index the tasks properly and define $\alpha_i$ and $\beta_i$ as constants for $i=1,2,\ldots,k-1$ based on Eq.~\eqref{eq:precodition-schedulability}. The set $\setof{t_1, t_2, \ldots, t_{k-1}}$ in Definition~\ref{def:kpoints} is used only
for the users to define those constants, where $t_k$ is usually defined to be the interval length of the original schedulability test, e.g., $D_k$ in Eq.~\eqref{eq:exact-test-constrained-deadline}.
Therefore, the \framework{} framework can only be applicable when $\alpha_i$ and $\beta_i$ are well-defined. These constants
depend on the task models and the task parameters.

The choice of good parameters $\alpha_i$ and $\beta_i$ affects the
quality of the resulting schedulability bounds in Lemmas~\ref{lemma:framework-constrained} to \ref{lemma:framework-totalU-exclusive}.
However, deriving the \emph{good}  settings of $\alpha_i$ and $\beta_i$ is actually not the focus of this paper. The framework does not care how the parameters $\alpha_i$ and $\beta_i$ are obtained. The framework simply derives the bounds according to the given parameters $\alpha_i$ and $\beta_i$, regardless of the settings of $\alpha_i$ and $\beta_i$. The correctness of the settings of $\alpha_i$ and $\beta_i$ is not verified by the framework.

The ignorance of the settings of $\alpha_i$ and $\beta_i$ actually leads to the elegance and the generality of the framework, which works as long as Eq.~\eqref{eq:precodition-schedulability} can be successfully constructed for the sufficient schedulability test of task $\tau_k$ in a fixed-priority scheduling policy.
With the availability of the \framework{} framework, the hyperbolic bounds or utilization bounds can be automatically derived by adopting  Lemmas \ref{lemma:framework-constrained} to \ref{lemma:framework-totalU-exclusive} as long as the safe upper bounds $\alpha$ and $\beta$  to cover all the possible settings of $\alpha_i$ and $\beta_i$ for the schedulability test in Eq.~\eqref{eq:precodition-schedulability} can be derived, regardless of the task model or the platforms.

The other approaches in \cite{journals/tc/LeeSP04,DBLP:dblp_journals/tc/BurchardLOS95,HanTyan-RTSS97} also have similar observations by testing only several time points in the TDA schedulability analysis based on Eq.~\eqref{eq:exact-test-constrained-deadline} in their problem formulations. Specifically, the problem formulations in \cite{DBLP:dblp_journals/tc/BurchardLOS95,HanTyan-RTSS97} are based on non-linear programming by selecting several good points under certain constraints. Moreover, the linear-programming problem formulation in \cite{journals/tc/LeeSP04} considers $U_i$ as variables and $t_i$ as constants and solves the corresponding linear programming analytically.
However, as these approaches in
\cite{journals/tc/LeeSP04,DBLP:dblp_journals/tc/BurchardLOS95,HanTyan-RTSS97} seek for the total utilization bounds, they have limited applications and are less flexible. For example, they are typically not applicable directly when considering sporadic real-time tasks with arbitrary deadlines or multiprocessor systems. Here, we are more flexible in the  \framework{} framework.
For task $\tau_i$, after $\alpha_i$ and $\beta_i$ or their safe upper bounds $\alpha$ and $\beta$ are derived, we completely drop out the dependency to the periods and models inside \framework{}.

\ifbool{techreport}{
\begin{figure*}[t]
} {
\begin{figure}[t]
}
	\begin{center}
\ifbool{techreport}{
      \begin{tikzpicture}[scale=1.2,transform shape]
} {
      \begin{tikzpicture}[scale=0.75,transform shape]
}

        \path \practica {1}{\underline{\bf Demonstrated Applications:}
          \begin{tabular}{ll}
          Sec. 5.1:& Constrained-deadline sporadic tasks\\
          Sec. 5.2:& Arbitrary-deadline sporadic tasks\\
          App. C\ifbool{techreport}{}{ \cite{DBLP:journals/corr/abs-1501.07084}}:& Multiframe tasks\\
          Sec. 6.1:& Multiprocessor DAG\\
          Sec. 6.2:& Multiprocessor self-suspension\\
          \end{tabular}
        };
        \path (p1.west)+(1.8,-3.2) node(p2)[materia, rounded rectangle,text width=6em]{{\bf $U_i, \forall i < k$\\$\alpha_i, \forall i<k$\\$\beta_i, \forall i <k$\\$C_k, t_k$}};
        \path (p2.north)+(1.5,0.45) node[text width=16em]{Derive parameters\\by \underline{Definition 1}};
        \path (p2.east)+(2,0) node(p3)[practica,fill=blue!20,text width=5em,text centered]{\large{\bf \framework{}\\ framework}};

        \path (p3.east)+(2.5,+3) node(p4)[practica,fill=green!30,minimum width=6em,text width=5em,text centered]{Hyperbolic bound};
        \path (p4.south)+(0.8,-1) node(p5)[practica,fill=green!30,minimum width=6em,text width=5em,text centered]{Other utilization bounds};
        \path (p5.south)+(0,-1) node(p6)[practica,fill=green!30,minimum width=6em,text width=5em,text centered]{Extreme points test};

        \path [line, ->] (p1.west) -- +(-0.3,0) node[black, rotate=90, yshift=0.3cm, xshift=-1.6cm]{\footnotesize{define $t_i, \forall i < k$ and order $k-1$ tasks}} -- + (-0.3, -3.2) -- (p2.west);
        \path [line, ->] (p2.east) -- (p3.west);
        \path [line, ->] (p3.east)+(0,0.3) -- node[rotate=60,yshift=0.3cm,black]{Lemma 1} (p4.west);
        \path [line, ->] (p3.east)+(0,0) -- node[rotate=35,yshift=0.3cm,black]{Lemmas 2\&3} (p5.west);
        \path [line, ->] (p3.east)+(0,-0.3) -- node[rotate=5,yshift=0.3cm,black]{Lemma 4} (p6.west);
      \end{tikzpicture}
	\end{center}
\vspace{-2mm}
\caption{The \framework{} framework. }
\label{fig:framework}
\ifbool{techreport}{
\end{figure*}
} {
\end{figure}
}

We will demonstrate the applicability and generality of \framework{} by using the most-adopted sporadic real-time task model in Sec.~\ref{sec:application-FP}, multi-frame tasks in Appendix C\citetechreport{}
and multiprocessor scheduling in Sec.~\ref{sec:multiprocessor}, as illustrated in Figure~\ref{fig:framework}.
In all these cases, we can find reasonable settings of $\alpha$ and $\beta$ to provide better results or new results for schedulability tests, with respect to the utilization bounds, speed-up factors, or capacity augmentation factors, compared to the literature.  More specifically, (after certain reorganizations), we will greedily set $t_i$ as $\floor{\frac{t_k}{T_i}}T_i$ in all of the studied cases.\footnote{Setting $t_i$ as $\floor{\frac{t_k}{T_i}}T_i$ is actually the same in \cite{journals/tc/LeeSP04} for the sporadic real-time task model with implicit deadlines and the multi-frame task model when $T_i$ is given and $U_i$ is considered as a variable.}
Table \ref{tab:alpha-beta} summarizes the $\alpha_i$ and $\beta_i$ parameters derived in this paper, as well as an earlier result by Liu and Chen in \cite{RTSS14a} for self-suspending task models and deferrable servers.

\begin{table*}[t]
\renewcommand{\arraystretch}{1.5}
  \centering
  \scalebox{0.8}{
  \begin{tabular}{|p{7cm}|c|c|p{4cm}|}
    \hline
    \hline
    Model & $\alpha_i$ & $\beta_i$ & c.f.\\
    \hline
    \hline
  Uniprocessor Sporadic Tasks& $\alpha_i=1$ & $0 < \beta_i \leq 1$ & Theorem~\ref{theorem:sporadic-general} and Corollary~\ref{col:arbitrary-general}\\
    \hline
   Multiprocessor Global RM for Different Models & $0 < \alpha_i \leq
   \frac{2}{M}$ & $0 < \beta_i\leq \frac{1}{M}$ &
   Theorems~\ref{thm:multiprocessor-DAG} -
   \ref{thm:multiprocessor-suspension}\\
    \hline
  Uniprocessor  Multi-frame Tasks& $0 < \alpha_i \leq 1$ & $0 < \beta_i\leq \frac{\phi_i(2)-\phi_i(1)}{\phi_i(1)}$ & \ifbool{techreport}{Theorem~\ref{thm:multiframe}}{Theorem 7 in \cite{DBLP:journals/corr/abs-1501.07084}}\\

    \hline
   Uniprocessor Self-Suspending Tasks& $0 < \alpha_i\leq 2$ & $0 < \beta_i\leq 1$ & Theorems 5 and 6 in \cite{RTSS14a}, implicitly\\
    \hline
  \end{tabular}
}
  \caption{\small The applicability of \framework{} for different task models: their $\alpha_i$ and $\beta_i$ parameters, where $M$ is the number of processors in global RM scheduling and  $\phi_i(\ell)$ is the maximum of the sum of the execution time of
    any $\ell$ consecutive frames of task $\tau_i$ in the multi-frame model.}
  \label{tab:alpha-beta}
\end{table*}

\section{Applications for Fixed-Priority Scheduling}
\label{sec:application-FP}

This section provides demonstrations on how to use the \framework{}
framework to derive efficient schedulability analysis for sporadic
task systems in uniprocessor systems. We will consider
constrained-deadline systems first in
Sec.~\ref{sec:application-constrained}
and explain how to extend to
arbitrary-deadline systems in Sec.~\ref{sec:application-arbitrary}. For the rest of this section, we will implicitly assume $C_k > 0$.

\subsection{Constrained-Deadline Systems}
\label{sec:application-constrained}

For a specified fixed-priority scheduling algorithm, let $hp(\tau_k)$ be the set
of tasks with higher priority than $\tau_k$. We now classify the task
set $hp(\tau_k)$ into two subsets:
\begin{itemize}
\item $hp_1(\tau_k)$ consists of the higher-priority tasks with periods
  smaller than $D_k$.
\item $hp_2(\tau_k)$ consists of the higher-priority tasks with periods
  larger than or equal to $D_k$.
\end{itemize}

For any $0 < t \leq D_k$,
we know that a safe upper bound on the interference due to higher-priority tasks is given by
\[
\sum_{\tau_i \in hp(\tau_k)} \ceiling{\frac{t}{T_i}}C_i = \sum_{\tau_i \in hp_2(\tau_k)} C_i + \sum_{\tau_i \in hp_1(\tau_k)} \ceiling{\frac{t}{T_i}}C_i .
\]
As a result, the schedulability test in
Eq.~\eqref{eq:exact-test-constrained-deadline}  is equivalent to the
verification of the existence of $0 < t \leq D_k$ such that
\begin{equation}
  \label{eq:exact-test-constrained-deadline-2}
 C_k + \sum_{\tau_i \in hp_2(\tau_k)} C_i + \sum_{\tau_i \in hp_1(\tau_k)} \ceiling{\frac{t}{T_i}}C_i \leq t.
\end{equation}
We can then create a virtual sporadic task $\tau_k'$ with execution
time $C_k'=C_k + \sum_{\tau_i \in hp_2(\tau_k)} C_i$, relative
deadline $D_k'=D_k$, and period $T_k'=D_k$. It is
clear that the schedulability test to verify the schedulability of
task $\tau_k'$ under the interference of the higher-priority tasks
$hp_1(\tau_k)$ is the same as that of task $\tau_k$ under the
interference of the higher-priority tasks $hp(\tau_k)$.

Therefore, with the above analysis, we can use the \framework{}
framework in Sec.~\ref{sec:framework} as in the following theorem.

\begin{theorem}
\label{theorem:sporadic-general}
Task $\tau_k$ in a sporadic task system with constrained deadlines is
schedulable by the fixed-priority scheduling algorithm if
\begin{equation}
\label{eq:schedulability-sporadic-any-a}
(\frac{C_k'}{D_k}+1) \prod_{\tau_j \in hp_1(\tau_k)} (U_j + 1)\leq 2
\end{equation}
or
\begin{equation}
\label{eq:schedulability-sporadic-any-b}
\frac{C_k'}{D_k}+  \sum_{\tau_j \in hp_1(\tau_k)}U_j\leq  k(2^{\frac{1}{k}}-1).
\end{equation}
\end{theorem}
\begin{proof}
For notational brevity, suppose that there are $k-1$ tasks in
$hp_1(\tau_k)$.\footnote{When $hp_2(\tau_k)$ is not empty, there are $k-1-|hp_2(\tau_k)|$ tasks in $hp_1(\tau_k)$.
To be notationally precise, we can denote the number of tasks in $hp_1(\tau_k)$ by a new symbol $k^*$. Since  $k^* \leq k$, we know $k^*(2^{\frac{1}{k^*}}-1) \geq  k(2^{\frac{1}{k}}-1)$ as a safe bound in Eq.~\eqref{eq:schedulability-sporadic-any-b}. However, this may make the notations too complicated. We have decided to keep it as $k-1$ for the sake of notational brevity. }
Now, we index the higher-priority tasks in
$hp_1(\tau_k)$ to form the corresponding $\tau_1, \tau_2, \ldots,
\tau_{k-1}$. The $k-1$ higher-priority tasks in $hp_1(\tau_k)$ are
ordered to ensure that the arrival times, i.e., $\floor{\frac{D_k}{T_i}}T_i$,  of the last jobs no later than $D_k$
are in a non-decreasing order.  That is, with the above indexing of
the higher-priority tasks in $hp_1(\tau_k)$, we have
$\floor{\frac{D_k}{T_i}}T_i \leq
\floor{\frac{D_k}{T_{i+1}}}T_{i+1}$ for $i=1,2,\ldots,k-2$.
Now, we set $t_i$ as $\floor{\frac{D_k}{T_i}}T_i$ for
$i=1,2,\ldots,k-1$, and $t_k$ as $D_k$. Due to the fact that $T_i \leq D_k$
for
$i=1,2,\ldots,k-1$, we know that $t_i > 0$.

Therefore,
for a given $t_j$ with $j=1,2,\ldots,k$, the demand requested up to time $t_j$ is at most
\begin{align}
  & C_k + \sum_{\tau_i \in hp_2(\tau_k)} C_i + \sum_{\tau_i \in hp_1(\tau_k)} \ceiling{\frac{t_j}{T_i}}C_i\nonumber\\
  = & C_k' +  \sum_{i=1}^{k-1} \ceiling{\frac{t_j}{T_i}}C_i
  \leq   C_k' + \sum_{i=1}^{k-1} \frac{t_i}{T_i}C_i +  \sum_{i=1}^{j-1} C_i,\nonumber
\end{align}
where the inequality comes from the indexing policy defined above,
i.e., $\ceiling{\frac{t_j}{T_i}} \leq \frac{t_i}{T_i}+1$ if $j
> i$  and $\ceiling{\frac{t_j}{T_i}} \leq
\frac{t_i}{T_i}$ if $j \leq i$.
Since $T_i < D_k$ for any task $\tau_i$ in $hp_1(\tau_k)$, we know
  that $t_i \geq T_i$.
Instead of testing all the $t$ values in
Eq.~(\ref{eq:exact-test-constrained-deadline-2}), we only apply the
test for these $k$ different $t_i$ values, which is equivalent to the
test of the existence of $t_j$ such that
\begin{equation}
\label{eq:k-point-sporadic}
  C_k'
  + \sum_{i=1}^{k-1} t_i U_i + \sum_{i=1}^{j-1}  \frac{T_i}{t_i}  t_i U_i \leq t_j.
\end{equation}
Therefore, we reach the schedulability in the form of Eq.~\eqref{eq:precodition-schedulability} under the setting of $\alpha_i$ to $1$ and $\beta_i$ to $\frac{T_i}{t_i} \leq 1$ (due to $t_i \geq T_i$), for $i=1,2,\ldots,k-1$.  By taking $\beta_i \leq 1$ and $\alpha_i = 1$ for
  $i=1,2,\ldots,k-1$ in Lemmas~\ref{lemma:framework-constrained}
  and~\ref{lemma:framework-totalU-constrained}, we reach the
  conclusion.
\end{proof}

When RM priority ordering is applied for an implicit-deadline
task system, $C_k'$ is equal to $C_k$ and $\frac{C_k'}{D_k}$ is equal
to $U_k$. For such a case, the condition in
Eq.~\eqref{eq:schedulability-sporadic-any-a} is the same as the
hyperbolic bound provided in \cite{bini2003rate}, and the condition in
Eq.~\eqref{eq:schedulability-sporadic-any-b} is the same as least
utilization upper bound in \cite{liu1973scheduling}.

The schedulability test in
Theorem~\ref{theorem:sporadic-general} may seem pessimistic at first glance. We evaluate the quality of the
schedulability test in Theorem~\ref{theorem:sporadic-general} by
quantifying the speed-up factor with respect to the optimal schedule
(i.e., EDF scheduling in such a case). We show that the speed-up
factor of the schedulability test in
Eq.~\eqref{eq:schedulability-sporadic-any-a} is $1.76322$, which is
the same as the lower bound and upper bound of DM as shown in
\cite{DBLP:journals/rts/DavisRBB09}. The speed-up factor of DM,
regardless of the schedulability tests, obtained by Davis et
al. \cite{DBLP:journals/rts/DavisRBB09} is the same as our result. Our
result is thus stronger, as we show that the factor already holds when
using the schedulability test in Eq.~\eqref{eq:schedulability-sporadic-any-a} in the following theorem.

\begin{theorem}
  \label{thm:speedup-DM}
  The speed-up factor of the schedulability test in
  Eq.~\eqref{eq:schedulability-sporadic-any-a} under DM scheduling for
  constrained-deadline tasks is $1.76322$ with respect to EDF.
\end{theorem}

The proof of Theorem~\ref{thm:speedup-DM} in the Appendix B, which is much simpler than the proof in \cite{DBLP:journals/rts/DavisRBB09}, can also be considered as an alternative proof of the speed-up factor of DM.

\begin{corollary}
  \label{col:implicit-general-ratio}
  Suppose that $f \cdot T_i \leq D_k$ for any higher priority task
  $\tau_i$ in $hp_1(\tau_k)$, where $f$ is a positive integer.  Task $\tau_k$
  in a constrained-deadline sporadic task system is schedulable by the fixed-priority
  scheduling algorithm if
\begin{equation}
\label{eq:schedulability-sporadic-implicit-ratio-a}
(\frac{C_k'}{f \cdot D_k}+1) \prod_{\tau_j \in hp_1(\tau_k)} (\frac{U_j}{f} + 1)\leq \frac{f+1}{f}
\end{equation}
or
\begin{equation}
  \label{eq:schedulability-sporadic-implicit-ratio-b}
\frac{C_k'}{D_k}+  \sum_{\tau_j \in hp_1(\tau_k)}U_j\leq f k\left(\left({\frac{f+1}{f}}\right)^{\frac{1}{k}}-1\right).
\end{equation}
\end{corollary}
\begin{proof}
  This is based on the same proof as Theorem~\ref{theorem:sporadic-general}, by taking the fact that $\frac{t_i}{T_i} = \frac{\floor{\frac{D_k}{T_i}}T_i}{T_i} \geq f$.
  In the $k$-point effective schedulability test, we can set
  $\alpha_i$ to $1$, $\beta_i = \frac{T_i}{t_i} \leq \frac{1}{f}$.

  Therefore, we have $\alpha_i \leq \alpha=1$,
  $\beta_i\leq\beta=\frac{1}{f}$, and $\frac{\alpha}{\beta}$ is $f$.
  By adopting
  Lemma~\ref{lemma:framework-constrained}, we know that task $\tau_k$
  is schedulable under the scheduling policy if
\ifbool{techreport}{
\[}{$}
 (\frac{C_k'}{D_k} + f) \prod_{{\tau_j \in hp_1(\tau_k)}} (\frac{U_j}{f} + 1)\leq f+1,
\ifbool{techreport}{
\]}{$}
  which is the same as the condition in
  Eq.~\eqref{eq:schedulability-sporadic-implicit-ratio-a} by dividing
  both sides by $f$. By using a similar argument and applying
  Lemma~\ref{lemma:framework-totalU-constrained}, we can reach the
  condition in Eq.~\eqref{eq:schedulability-sporadic-implicit-ratio-b}.
\end{proof}
\ifbool{techreport}{
Note that the right-hand side of
Eq.~\eqref{eq:schedulability-sporadic-implicit-ratio-b} converges to $f
\ln(\frac{f+1}{f})$ when $k$ goes to $\infty$.}{}

\subsection{Arbitrary-Deadline Systems}
\label{sec:application-arbitrary}

We now further explore how to use the proposed framework to perform
the schedulability analysis for arbitrary-deadline task sets.
The
exact schedulability analysis for arbitrary-deadline task sets under
fixed-priority scheduling has been developed in
\cite{DBLP:conf/rtss/Lehoczky90}. The schedulability analysis is to
use a \emph{busy-window} concept to evaluate the worst-case response
time. That is, we release all the higher-priority tasks together with
task $\tau_k$ at time $0$ and all the subsequent jobs are released as
early as possible by respecting to the minimum inter-arrival time. The
busy window finishes when a job of task $\tau_k$ finishes before the
next release of a job of task $\tau_k$. It has been shown in
\cite{DBLP:conf/rtss/Lehoczky90} that the worst-case response time of
task $\tau_k$ can be found in one of the jobs of task $\tau_k$ in the
busy window.

Therefore, a simpler sufficient schedulability test for a task
$\tau_k$ is to test whether the length of the busy window is within
$D_k$.  If so, all invocations of task $\tau_k$ released in the busy
window can finish before their relative deadline. Such an observation
has also been adopted in \cite{conf:/rtns09/Davis}. Therefore, a
sufficient test is to verify whether\footnote{This analysis is pretty pessimistic.
But, as our objective in this paper is to show the applicability and generality of \framework{},
how to use \framework{} to get tighter analysis for arbitrary-deadline task systems is not our focus in this paper. Some evaluations can be found in \cite{DBLP:journals/corr/framework-compare}.  }
\begin{equation}
  \label{eq:sufficient-test-arbitrary-deadline}
\exists t \mbox{ with } 0 < t \leq D_k {\;\; and \;\;} \ceiling{\frac{t}{T_k}}C_k +
\sum_{\tau_i \in hp(\tau_k)} \ceiling{\frac{t}{T_i}}C_i \leq t.
\end{equation}
If the condition in Eq.~\eqref{eq:sufficient-test-arbitrary-deadline} holds,
it implies that the busy window (when considering task $\tau_k$) is no
more than $D_k$, and, hence, task $\tau_k$ has worst-case response
time no more than $D_k$.

If $D_k \leq T_k$, the analysis in
Sec.~\ref{sec:application-constrained} can be directly applied. If
$D_k > T_k$, we need to consider the length of the busy-window for
task $\tau_k$ as shown above. For the rest of this section, we will
focus on the case $D_k > T_k$.
We can rewrite
Eq.~\eqref{eq:sufficient-test-arbitrary-deadline} to use a more
pessimistic condition by releasing the workload
$\ceiling{\frac{D_k}{T_k}}C_k$ at time $0$. That is, if
\begin{equation}
  \label{eq:sufficient-test-arbitrary-deadline-pessimistic}
\exists t \mbox{ with } 0 < t \leq D_k {\;\; and \;\;} \ceiling{\frac{D_k}{T_k}}C_k +
\sum_{\tau_i \in hp(\tau_k)} \ceiling{\frac{t}{T_i}}C_i \leq t,
\end{equation}
then, the length of the busy window for task $\tau_k$ is no more than
$D_k$. Again, similar to the strategy
we use in Sec.~\ref{sec:application-constrained}, we classify the
tasks in $\tau_i \in hp(\tau_k)$ into two sets $hp_1(\tau_k)$ and
$hp_2(\tau_k)$ with the same definition.

Similarly, we can then create a virtual sporadic task $\tau_k'$ with
execution time $C_k' = \ceiling{\frac{D_k}{T_k}}C_k + \sum_{\tau_i \in
  hp_2(\tau_k)} C_i$, relative deadline $D_k'=D_k$, and period $T_k'=D_k$.
For notational brevity, suppose that there are $k-1$ tasks in
$hp_1(\tau_k)$.  Now, we index the higher-priority tasks in
$hp_1(\tau_k)$ to form the corresponding $\tau_1, \tau_2, \ldots,
\tau_{k-1}$.  In the above definition of the busy window concept,
$\floor{\frac{D_k}{T_i}}T_i$ is the arrival time of the last job
of task $\tau_i$ released no later than $D_k$. The $k-1$ higher-priority
tasks in $hp_1(\tau_k)$ are ordered to ensure that the
arrival times of the last jobs before $D_k$ are in a non-decreasing
order.  Moreover, $t_k$ is the specified testing point $D_k$.  Instead
of testing all the $t$ values in
Eq.~\eqref{eq:sufficient-test-arbitrary-deadline-pessimistic}, we only
apply the test for these $k$ different $t_i$ values, which is
equivalent to the test of the existence of $t_j$ such that
Eq.~\eqref{eq:k-point-sporadic} holds, where $\alpha_i \leq 1$ and
$\beta_i = \frac{T_i}{t_i} \leq 1$ for $i=1,2,\ldots,k-1$, similar to the proof of Theorem~\ref{theorem:sporadic-general}.
\ifbool{techreport}{

Therefore, we can then use the \framework{} framework, i.e., Lemmas
\ref{lemma:framework-constrained} to
\ref{lemma:framework-totalU-exclusive} to test the schedulability of
task $\tau_k$. }{}
The following corollary comes from a similar argument as in
Sec.~\ref{sec:application-constrained}.
\begin{corollary}
\label{col:arbitrary-general}
Task $\tau_k$ in a sporadic arbitrary-deadline task system is schedulable by the
fixed-priority scheduling algorithm if
Eq.~\eqref{eq:schedulability-sporadic-any-a} or
\eqref{eq:schedulability-sporadic-any-b} holds,
in which there are $k-1$ higher priority tasks in $hp_1(\tau_k)$ and $C_k'$ is defined as $\ceiling{\frac{D_k}{T_k}}C_k + \sum_{\tau_i
  \in hp_2(\tau_k)} C_i$.
\end{corollary}

\begin{corollary}
  \label{col:utilization-RM-arbitrary}
  Suppose that $f \cdot T_i \leq D_k$ for any higher task $\tau_i$ in the
  task system and $f\cdot T_k \leq D_k$, where $f$ is a positive integer.  Task $\tau_k$
  in a sporadic task system is schedulable by using RM, i.e., $T_i \leq T_{i+1}$, if
\begin{equation}
\label{eq:schedulability-arbitrary-rm-ratio-a}
(\frac{U_k}{f}+1) \prod_{j=1}^{k-1} (\frac{U_j}{f} + 1)\leq \frac{f+1}{f}
\end{equation}
or
\begin{equation}
  \label{eq:schedulability-arbitrary-rm-ratio-b}
\sum_{j=1}^{k}U_j \leq  f k\left(\left({\frac{f+1}{f}}\right)^{\frac{1}{k}}-1\right).
\end{equation}
\end{corollary}
\begin{proof}
  Based on the above assumption $f \cdot T_i \leq D_k$ for any higher task $\tau_i$ in the
  task system, $f\cdot T_k \leq D_k$, and the rate
  monotonic scheduling, we can safely set $\alpha_i$ to $1$, $\beta_i$
  to $\frac{1}{f}$, and $C_k'$ to $f \cdot C_k$. Note that $\frac{C_k'}{f\cdot t_k} \leq \frac{U_k}{f}$ in this case. Therefore, by
  adopting Lemma~\ref{lemma:framework-constrained} and
  Lemma~\ref{lemma:framework-totalU-constrained}, we reach the
  conclusion, as in the proof of Corollary~\ref{col:implicit-general-ratio}.
\end{proof}

\section{Application for Multiprocessor Scheduling}
\label{sec:multiprocessor}

It may seem, at first glance, that the \framework{} framework only
works for uniprocessor systems. We demonstrate in this section how to
use the framework in multiprocessor global RM scheduling when considering
implicit-deadline, DAG, and self-suspending task systems. The methodology can also be extended to
handle constrained-deadline systems.

In multiprocessor global scheduling, we consider that the system has
$M$ identical processors, each with the same
computation power. Moreover, there is a global queue and a global
scheduler to dispatch the jobs. We consider only global RM scheduling,
in which the priority of the tasks is defined based on RM. At any
time, the $M$-highest-priority jobs in the ready queue are dispatched
and executed on these $M$ processors.

Global RM in general does not have good utilization bounds.
 However, if we constrain the total utilization
$\sum_{\tau_i} \frac{C_i}{M T_i} \leq \frac{1}{b}$
and the maximum utilization $\max_{\tau_i} \frac{C_i}{T_i} \leq
\frac{1}{b}$, it is possible to provide the schedulability guarantee
of global RM by setting $b$ to $3-\frac{1}{M}$ \cite{DBLP:conf/rtss/AnderssonBJ01,DBLP:conf/rtss/Baker03,DBLP:conf/opodis/BertognaCL05}. Such a factor $b$ has
been recently named as a \emph{capacity augmentation factor} \cite{Li:ECRTS14}.

We will use the following
time-demand function $W_i(t)$ for the simple sufficient schedulability analysis:
\begin{equation}
  \label{eq:W_i-multiprocessor}
W_i(t) = (\ceiling{\frac{t}{T_i}}-1)C_i + 2C_i,
\end{equation}
which can be imagined as if the \emph{carry-in} job is fully carried into the analysis interval \cite{DBLP:conf/rtss/GuanSYY09}.
That is, we allow the first release of task $\tau_i$ to be inflated by a
factor $2$, whereas the other jobs of task $\tau_i$ have the same
execution time $C_i$.
Again, we consider testing the schedulability of task $\tau_k$ under
global RM, in which there are $k-1$ higher-priority tasks $\tau_1,
\tau_2, \ldots, \tau_{k-1}$.  We have the following schedulability
condition for global RM.
\begin{lemma}
\label{lemma:gRM-sufficient}
Task $\tau_k$ is schedulable under
  global RM on $M$ identical processors, if
  \begin{equation}
    \label{eq:gRM-sufficient}
\exists t \mbox{ with } 0 < t \leq T_k {\;\; and \;\;} C_k +\sum_{i=1}^{k-1}
\frac{W_i(t)}{M} \leq t,
  \end{equation}
  where $W_i(t)$ is defined in Eq.~\eqref{eq:W_i-multiprocessor}.
\end{lemma}
\begin{proof}
  This has been shown in Sec. 3.2 (The Basic Multiprocessor Case)
  in \cite{DBLP:conf/rtss/GuanSYY09}.
\end{proof}

\begin{theorem}
\label{thm:multiprocessor-GRM}
Task $\tau_k$ in a sporadic implicit-deadline task system is
schedulable by global RM on $M$ processors if
\begin{equation}
\label{eq:schedulability-GRM}
 (\frac{C_k}{T_k}+2)\prod_{j=1}^{k-1} (\frac{U_j}{M} + 1)\leq 3,
\end{equation}
or
\begin{equation}
\label{eq:schedulability-augmentation-GRM}
\sum_{j=1}^{k-1} \frac{U_j}{M}\leq \ln{\frac{3}{\frac{C_k}{T_k}+2}}.
\end{equation}
\end{theorem}
\begin{proof}
  Let $t_i$ be $\floor{\frac{T_k}{T_i}}T_i$ for $i=1,2,\ldots,k$, and
  reindex the tasks such that $t_1 \leq t_2 \leq \ldots \leq t_k$.  By
  testing only these $k$ points in the schedulability test in
  \eqref{eq:gRM-sufficient} results in a $k$-point effective
  schedulability test with $\alpha_i \leq \frac{2}{M}$ and $\beta_i
  \leq \frac{1}{M}$. Therefore, we can adopt the \framework{}
  framework. By Lemma~\ref{lemma:framework-constrained} and
  Lemma~\ref{lemma:framework-totalU-exclusive}, we have concluded the
  proof.
\end{proof}

Note that Theorem~\ref{thm:multiprocessor-GRM}  is not superior to the known analysis for
sporadic task systems \cite{DBLP:conf/rtss/AnderssonBJ01,DBLP:conf/rtss/Baker03,DBLP:conf/opodis/BertognaCL05},  as the schedulability condition in Lemma~\ref{lemma:gRM-sufficient} is too pessimistic. This is only used as the basis  to analyze a sporadic task set
with DAG tasks in Sec.~\ref{sec:global-DAG} and self-suspending tasks in Sec.~\ref{sec:global-SSS} when adopting global RM, in which we will demonstrate similar structures as used in Theorem~\ref{thm:multiprocessor-GRM}. We also demonstrate a tighter test in Appendix F\citetechreport{}
for improving the schedulability test of global RM for sporadic tasks.

\subsection{Global RM for DAG Task Systems}
\label{sec:global-DAG}

For multiprocessor scheduling, the DAG task model has been recently studied \cite{DBLP:conf/ecrts/BonifaciMSW13}. The utilization-based analysis can be found
 in \cite{Li:ECRTS14} and \cite{DBLP:conf/ecrts/BonifaciMSW13}.
Each task $\tau_i\in {\bf T}$ in a DAG task system is a parallel task.
Each task is characterized by its execution pattern, defined by a set
of directed acyclic graphs (DAGs). The execution time of a job of task
$\tau_i$ is one of the DAGs. Each node (subtask) in a DAG represents a
sequence of instructions (a thread) and each edge represents a
dependency between nodes.  A node (subtask) is \emph{ready} to be
executed when all its predecessors have been executed.  We will only
consider two parameters related to the execution pattern of task
$\tau_i$:
\begin{compactitem}
\item \emph{total execution time (or work)} $C_i$ of task $\tau_i$: This is
  the summation of the execution times of all the subtasks
  of task $\tau_i$ among all the DAGs of task $\tau_i$.
\item \emph{critical-path length} $\Psi_i$ of task $\tau_i$: This is the length of
  the critical path among the given DAGs, in which each node is
  characterized by the execution time of the corresponding
  subtask of task $\tau_i$.
\end{compactitem}
The analysis is based on the two given parameters $C_i$ and
$\Psi_i$. Therefore, we can also allow flexible DAG structures. That
is, jobs of a task may have different DAG structures, under the total
execution time constraint $C_i$ and the critical path length
constraint $\Psi_i$. Therefore, the model can also be applied for conditional sporadic DAG task systems \cite{DBLP:conf/ecrts/BaruahBM15}.
With the above definition, we have the following lemma, in which the proof is
Appendix B\citetechreport{}.

\begin{lemma}
  \label{lemma:gRM-DAG-sufficient}
  Task $\tau_k$ in a sporadic DAG system with implicit deadlines is schedulable under global RM on $M$ identical
  processors, if
  \begin{equation}
    \label{eq:gRM-DAGsufficient}
\exists t \mbox{ with } 0 < t \leq T_k {\;\; and \;\;} \Psi_k+\frac{C_k-\Psi_k}{M}+
\sum_{i=1}^{k-1}
\frac{W_i(t)}{M}\leq t,
  \end{equation}
  where $W_i(t)$ is defined in Eq.~\eqref{eq:W_i-multiprocessor}.
 \end{lemma}

\begin{theorem}
\label{thm:multiprocessor-DAG}
Task $\tau_k$ in a sporadic DAG system with implicit deadlines is schedulable by global RM on
$M$ processors if
\begin{equation}
\label{eq:schedulability-DAG}
 (\frac{\Psi_k}{T_k}+2) \prod_{j=1}^{k} (\frac{U_j}{M} + 1)\leq 3
\end{equation}
or
\begin{equation}
\label{eq:schedulability-DAG-augmentation-GRM}
\sum_{j=1}^{k} \frac{U_j}{M}\leq \ln{\frac{3}{\frac{\Psi_k}{T_k}+2}}.
\end{equation}
\end{theorem}
\begin{proof}
Based on Lemma~\ref{lemma:gRM-DAG-sufficient}, which is very similar
to Lemma~\ref{lemma:gRM-sufficient}, we can perform a
similar transformation as in Theorem~\ref{thm:multiprocessor-GRM}, in
which $\alpha_i \leq
  \frac{2}{M}$ and $\beta_i \leq \frac{1}{M}$. By adopting
  Lemma~\ref{lemma:framework-constrained}, we know that if
\begin{equation}
\label{eq:schedulability-DAG-weaker}
 (\frac{\Psi_k + \frac{C_k-\Psi_k}{M}}{T_k}+2) \prod_{j=1}^{k-1} (\frac{U_j}{M} + 1)\leq 3,
\end{equation}
then task $\tau_k$ is schedulable. Due to the fact that $C_k-\Psi_k
\leq C_k$, we know that $(\frac{\Psi_k + \frac{C_k-\Psi_k}{M}}{T_k}+2)
\leq (\frac{\Psi_k + \frac{C_k}{M}}{T_k}+2) \leq
(\frac{\Psi_k}{T_k}+2) \cdot (\frac{U_k}{M} + 1)$. Therefore, if the
condition in Eq.~\eqref{eq:schedulability-DAG} holds, the condition in
Eq.~\eqref{eq:schedulability-DAG-weaker} also holds, which implies the
schedulability. With the result in Eq.~\eqref{eq:schedulability-DAG},
we can use the same procedure as in
Lemma~\ref{lemma:framework-totalU-exclusive} to obtain
Eq.~\eqref{eq:schedulability-DAG-augmentation-GRM}.
\end{proof}

\begin{corollary}
  The capacity augmentation factor of global RM for a sporadic DAG system with implicit deadlines is $3.62143$.
\end{corollary}
\begin{proof}
  Suppose that $\sum_{\tau_i} \frac{C_i}{M T_i} \leq \frac{1}{b}$ and
  $\frac{\Psi_k}{T_k} \leq \max_{\tau_i} \frac{\Psi_i}{T_i} \leq
  \frac{1}{b}$.  Therefore, by
  Eq.~\eqref{eq:schedulability-DAG-augmentation-GRM}, we can guarantee
  the schedulability of task $\tau_k$ if $\frac{1}{b} \leq
  \ln{\frac{3}{2+\frac{1}{b}}}$. This is equivalent to solving $x =
  \ln{\frac{3}{2+x}}$, which holds when $x\approx
  3.62143$ by solving the equation numerically. Therefore,
  we reach the conclusion of the capacity augmentation factor
  $3.62143$.
\end{proof}

\subsection{Global RM for Self-Suspending Tasks}
\label{sec:global-SSS}

The self-suspending task model extends the sporadic task model by allowing tasks to suspend themselves.
An overview of work on scheduling self-suspending task systems can be
found in \cite{RTSS14a}.
\ifbool{techreport}{In \cite{RTSS14a}, a general interference-based analysis framework was developed that can be applied to derive sufficient utilization-based tests for self-suspending task systems on uniprocessors.}{}

Similar to sporadic tasks, a  self-suspending task releases jobs sporadically. Jobs alternate between computation and suspension phases. We assume that each job of $\tau_i$ executes for at most $C_i$ time units (across all of its execution phases) and suspends for at most $S_i$ time units (across all of its suspension phases). We assume that $C_i+S_i \leq T_i$ for any task $\tau_i \in \tau$; for otherwise deadlines would be missed. The self-suspending model is general: we place no restrictions on the number of phases per-job and how these phases interleave (a job can even begin or end with a suspension phase). Different jobs belong to the same task can also have different phase-interleaving patterns.
For many applications, such a general self-suspending model is needed due to the unpredictable nature of I/O operations.
We have the following lemma, in which the proof is in Appendix B\citetechreport{}.
\begin{lemma}
  \label{lemma:gRM-suspension-sufficient}
  Task $\tau_k$ in a  self-suspending system with implicit deadlines  is schedulable under global RM on $M$ identical
  processors, if
  \begin{equation}
    \label{eq:gRM-suspension-sufficient}
\exists t \mbox{ with } 0 < t \leq T_k {\;\; and \;\;} C_k+S_k +\sum_{i=1}^{k-1}
\frac{W_i(t)}{M} \leq t,
  \end{equation}
  where $W_i(t)$ is defined in Eq.~\eqref{eq:W_i-multiprocessor}.
\end{lemma}

\begin{theorem}
\label{thm:multiprocessor-suspension}
Task $\tau_k$ in a sporadic self-suspending system with implicit deadlines  is schedulable by global RM on
$M$ processors if
\begin{equation}
\label{eq:schedulability-suspension}
(\frac{C_k+S_k}{T_k}+2) \prod_{j=1}^{k-1} (\frac{U_j}{M} + 1)\leq 3.
\end{equation}
\end{theorem}
\begin{proof}
By Lemma~\ref{lemma:gRM-suspension-sufficient}, we can perform a
similar transformation as in Theorem~\ref{thm:multiprocessor-GRM} with $\alpha_i \leq
  \frac{2}{M}$ and $\beta_i \leq \frac{1}{M}$.
\end{proof}

\vspace{-0.05in}
\section{Conclusion}
\vspace{-0.05in}

With the presented applications, we believe that the general schedulability analysis \framework{}  framework for fixed-priority scheduling has high potential to be adopted for analyzing other task models in real-time systems. We constrain ourselves by demonstrating the applications for simple scheduling policies, like global RM in multiprocessor scheduling. The framework can be used, once the $k$-point effective scheduling test can be constructed. Although the emphasis of this paper is not to show that the resulting tests for different task models by applying the \framework{} framework are better than existing work, some analysis results by applying the  \framework{}  framework have been shown superior to the state of the art.
For completeness, another document has been prepared in
\cite{DBLP:journals/corr/framework-compare} to present the similarity,
the difference and the characteristics of \framework{} and
\frameworkkq{}. With our frameworks, some difficult
schedulability test and response time analysis problems may be solved
by building a good (or exact) exponential-time test and applying these
frameworks.

Appendix D\citetechreport{} provides some case studies with evaluation
results of some selected utilization-based schedulability
tests. Appendix E\citetechreport{} further provides some additional
properties that come directly from the \framework{} framework.  More
applications can be found in partitioned scheduling \cite{DBLP:journals/corr/Chen15k}, non-preemptive
scheduling \cite{DBLP:conf/ecrts/BruggenCH15}, etc.

\begin{spacing}{0.9}
\noindent{\small
{\bf Acknowledgement}: This paper has been supported by DFG, as
    part of the Collaborative Research Center SFB876
    (http://sfb876.tu-dortmund.de/), and the priority program
    "Dependable Embedded Systems" (SPP 1500 -
    http://spp1500.itec.kit.edu). We would also like to thank Dr. Vincenzo
    Bonifaci for his valuable input to improve the presentation of the paper.
}
\end{spacing}

\footnotesize

\vspace{-0.05in}
\ifbool{techreport}{
\begin{spacing}{0.98}
}{
\begin{spacing}{0.85}
\vspace{-0.03in}
}
\def-0.3pt{-0.3pt}
\bibliographystyle{abbrv}

redpajama_set_name: RedPajamaArXiv


To ensure consistency of manufacture we offer a screening service - both in the EU and the Country of manufacture.
This service can be as simple as a visual check and photographic report or it can be more in-depth such as limited safety, materials or EMC testing. The service is driven by your requirements.