This paper proposes an analysis method to check the schedulability of a set of sporadic tasks under earliest deadline first (EDF) scheduler. The sporadic task model consists of subtasks with precedence constraints, arbitrary arrival times and deadlines. In order to determine the schedulability, we present an approach to find exact worst case response time (WCRT) of subtatsks. With the technique presented in this paper, we exploit the precedence relations between subtasks in an accurate way while taking advantage of the deadline of different subtasks. Another nice feature of our approach is that it avoids calculation time overhead by exploiting the concept of deadline busy period. Experimental results show that this consideration leads to a significant improvement compared with existing work.
I. INTRODUCTION
There are many industrial embedded systems consisting of millions of lines of code, and containing many tasks, where some tasks may have realtime constraints. Looking closer at these systems, independent tasks may consist of subtasks that exhibit strong dependencies. Subtask dependencies are necessary for realizing some control activities. That is, some subtasks have to respect a processing order due to message exchange between subtasks or usage of various resources. A significant problem in such systems is that missing deadlines can cause disastrous failures. One desirable approach to avoid timingrelated errors in such complex systems is to use exact worst case response time (WCRT) analysis to provide a reliable guarantee.
Spuri
[1]
derived WCRT for sporadically periodic tasks (independent task instances that arrive within a certain period for a time interval, and then does not rearrive for a longer period) with arbitrary deadlines where tasks are scheduled using a preemptive earliest deadline first (EDF) scheduler. Another approach proposed by Zhang and Burns
[2]
obtains necessary and sufficient conditions for EDF schedulability of a set of sporadic tasks. Within a sporadic task subtasks interarrival time is greater than or equal to the task period. The proposed schedulability conditions reduce the calculation overhead of previous results. Zhang et al.
[3]
model WCRT under preemptive fixed priority, for another extension of sporadic tasks. The sporadic task model introduces a bound on the number of task arrivals allowed in a specific time window. Further, they allow a different number of task arrivals for different time windows. However, the approaches in
[1

3]
did not consider the precedence constraints among subtasks.
A different approach proposed in
[4

7]
derives WCRT analysis for a sort of sporadic task with precedenceconstrained subtasks where task activation results in activation of all subtasks at the same time. That is, all subtasks arrive simultaneously as an external event occurs. To consider the precedence constraints between subtasks, the authors model a sporadic task by a directed acyclic graph (DAG). These approaches adopt a technique for transforming the DAG of the task under analysis to a simple chain by modification of the deadline of the subtasks. This technique is still somehow an approximation of the response times, because in some particular cases, transformation of a graph to a chain, and consequently introducing an artificial deadline for subtasks, is not able to exploit sufficiently the priorities among subtasks.
This paper extends the aforementioned results to a larger class of sporadic task models. Our proposed sporadic task allows an arbitrary arrival time and arbitrary deadline of subtasks with acyclic precedence constraints, i.e., within a sporadic task, subtasks include acyclic precedence constraints and arrive at arbitrary time instances with arbitrary deadlines. Subtasks are implemented upon a uniprocessor platform and are scheduled under a preemptive EDF scheduler such that subtasks with precedence constraints are scheduled according to their precedence relations, while subtasks with no precedence relations are scheduled according to the EDF algorithm. In contrast to approaches in
[4

7]
, to acquire WCRTs precisely, no deadline modification is allowed and the analysis is performed on the original sporadic graph.
Since by adopting offsetbased techniques, the corresponding analysis of a distributed system or a multiprocessor system can be transformed to an equivalent single processor analysis, our approach can be easily adopted for schedulability analysis of distributed systems or multiprocessors. In this case, task executions and message transmissions are modeled as preemptive/nonpreemptive tasks executed in a single processor. In the study of schedulability of a distributed realtime system, compared with the approach proposed by Palencia and Harbour
[8]
, our contribution is shown to have significant improved performance by a factor that grows larger with processor utilization.
This paper starts by introducing related works in Section II, and the computational model in Section III. The proposed WCRT analysis is described in Section VI. A case study is presented in Section V. Finally, our conclusions are stated in Section VI.
II. RELATED WORKS
In the past, periodic and sporadic task scheduling has received considerable attention. A wellknown result for periodic tasks is that the preemptive EDF algorithm is optimal in the sense that it will successfully generate a processor schedule for any periodic task system that can be scheduled
[9]
. In contrast to periodic tasks, a sporadic task is invoked at arbitrary times but with a specified minimum time interval between invocations. Kim and Naghibzadeh
[10]
showed the optimality of nonpreemptive EDF, for the scheduling of a set of sporadic tasks with relative deadlines equal to their periods. The authors proposed the feasibility condition for a set of sporadic tasks with relative deadlines equal to their respective periods.
[2]
obtains the necessary and sufficient conditions for EDF schedulability of sporadic tasks, where subtasks’ interarrival time is greater than or equal to the task period.
[3]
considered WCRT for a sort of sporadic task model where a bounded number of tasks arrive in a specific time window. Spuri
[1]
proposed WCRT analysis of sporadically periodic task sets with arbitrary timing requirements scheduled under EDF. In this approach, sporadically periodic tasks are identified by two periods: an inner period and an outer period. The outer period is the worstcase interarrival time between bursts and the inner period is the worstcase interarrival time between task instances within a burst
[1]
. However, the computational model in the abovementioned works does not cover dependency among subtasks of a sporadic task. A common form of dependency arises when one subtask produces the communication data of another consumer subtask to proceed with its computations. Further, even when no explicit data exchanges are involved, subtasks might be required to run in certain orders.
The approaches proposed by Zhao et al.
[4
,
5]
, concerns WCRT analysis for a set of independent sporadic tasks, scheduled under nonpreemptive EDF scheduling and with fixed priority scheduling, respectively. Each sporadic task is represented by a graph to indicate subtask dependencies. The main idea is to transform the graph to a canonical chain by modification of the deadline of subtasks appropriately so that each subtask in the obtained canonical chain has a deadline larger than its predecessors. The idea of a graph to chain transformation was inspired by the approaches proposed by Harbour et al.
[6
,
7]
. This approach uses the graph to chain transformation to provide a theoretical framework for analyzing task sets scheduled through a fixed priority preemptive scheduler. However,
[4

7]
cover simultaneous arrival of subtasks only.
In the study of task level precedence constraints, the meaning of a precedence constraint is applicable in practice only to tasks that have the same rate. Mangeruca et al.
[11]
generalizes the concept of precedence constraints between tasks to allow tasks to have different rates. Moreover, they consider integer linear problem formalization of the problems of optimum priority/ deadline assignment for preemptive EDF scheduling under precedence constraints.
Computational model of a sporadic task. (a) Task τ_{1} specification, (b) timeline of activation time and deadline of subtasks.
An illustration of the equivalent deadline–d busy period with a regular busy period. (a) Busy period which includes execution of τ_{p,q} with a latter absolute deadline the d_{a,b}. The rectangle illustrates the execution of τ_{p,q}.(b) deadline–d busy period starts with subtasks released at time interval(t_{B}+S_{p,q},t_{B}+E_{p,q}).
As for distributed hard realtime systems, Spuri
[12]
adapted the Holistic analysis technique to the systems that were scheduled under the EDF.
In this work, the analysys requires global knowledge of the task routes to predict the worstcase endtoend delay of a task. Later,
[8
,
13

15]
improved the estimations of WCRTs by developing the offsetbased technique. The fundamental principle behind it is that, given the offset information of the tasks at a communication resource, the authors transform a distributed system to an equivalent uniprocessor. In this case, estimations depend only on the load that the analyzed task encounters. Another extension was proposed by Redell
[16]
, which allows each task to have one or more immediate successors. The main problem with these techniques is that they take into account the precedence relations between tasks only indirectly, causing pessimistic resuls to quickly increase along with the system scale. In Section V, we show the outperformmance of our work compared with the work in
[8]
.
III. SYSTEM MODEL AND NOTATIONS
Definition. Sporadic Task (τ_{i}):
Sporadic task τ
_{i}
consists of
n_{i}
number of preemptive subtasks τ
_{i}
= {τ
_{i,1}
, …, τ
_{i,ni}
} with precedence constraints and arbitray timing requirements. The interarrival time of of each task is separated by a minimum time
T_{i}
. Each task activation at time
t
results in activation of all subtasks, each one at time
t_{i,j}
=
t
+
O_{i,j}
, where
O_{i,j}
denotes the arrival time relative to the activation of the task,
Fig. 1
Each subtask has an execution time
C_{i,j}
, and relative deadline
D_{i,j}
. The absolute deadline
d_{i,j}
of subtask τ
_{i,j}
requested at time
t_{i,j}
equals
d_{i,j}
=
t_{i,j}
+
D_{i,j}
. The relative deadline of task τ
_{i}
is denoted by
D_{i}
, where
D_{i}
equals
D_{i}
= max
_{j}
(
O_{i,j}
+
D_{i,j}
).
Definition. Busy Period:
the time interval delimited by two successive idle times, during which the CPU is not idle. Let us denote the length of the longest busy period by
L
and the starting instance of the longest busy period by
t_{B}
.
Definition. Deadlined Busy Period:
A processor busy period in which only the subtasks with an absolute deadline smaller than or equal to
d
execute.
Definition. Worstcase Response Time (WCRT)(R_{i,j}):
maximum possible delay between arrival time and completion time of subtask τ
_{i,j}
on each activation time of the subtask τ
_{i,j}
inside the longest busy period:
Procedure 1 determines the order of scheduling of subtasks:
IV. RESPONSE TIME ANALYSIS
According to the generalization of an original result described by Liu and Layland
[9]
we simply need to study the schedule of tasks in the most demanding arrival pattern, the longest busy period. As noted in Section III, the length of the longest busy period in our model is denoted by
L
and the starting instance of the longest busy period by
t_{B}
. When the schedulability of periodic tasks under EDF is considered, from
[17]
we have: the completion time of a task’s instance with absolute deadline
d
, must be the end of a busy period in which all executed instances have absolute deadlines less than or equal to
d
(which is defined as deadline –
d
busy period). If we are able to examine all such periods, by taking the maximum length we can find the WCRT of a task
[17]
. Let us consider the validity of the above argument for our proposed task model with precedence constrained subtasks. To do so, using a simple example illustrated in
Fig. 2
a, we shall demonstrate that it suffices to consider the worstcase scenario of the subtask τ
_{a,b}
with absolute deadline
d
that was released at
r
unit times after
t_{B}
, inside a deadline –
d
busy period. Consider a busy period where the coincidence of some subtasks τ
_{p,q}
, with
D_{p,q}
>
d
occurs at
t_{B}
. Assume that the subtask τ
_{p,q}
with
D_{p,q}
>
d
is executed before starting instance of execution of the analyzed subtask τ
_{a,b}
, as shown in
Fig. 2
a. Even though τ
_{a,b}
with an earlier absolute deadline is released earlier than τ
_{p,q}
, due to the highest urgency of the predecessors of τ
_{a,b}
and their exposed precedence relations, it is possible that τ
_{p,q}
would be executed earlier. However, we show that it is possible to avoid the conservative analysis of such busy periods by introducing an equivalent deadline –
d
busy period. Let us denote the phase between the starting instance of execution of the subtask τ
_{p,q}
with
t_{B}
, by S
_{p,q}
and the phase between the period can be examined that starts at arrival of those subtasks.
In this case, the subtask τ
_{a,b}
would be released at time
r
'=
r
–
E _{p,q}
, see
Fig. 2
b because in both of the cases, the response time of subtask τ
_{a,b}
is identical. This means that, if execution of subtask τ
_{p,q}
with
D_{p,q}
>
d
occurs before starting the instance of execution of analyzed subtask τ
_{a,b}
, as shown in
Fig. 2
a, the considered deadline –
d
busy period would be finished at time
t_{B}
+ S
_{p,q}
.
An example of a critical instance given a deadline –d busy period with maximum length of 10. (a) Directed acyclic graph of tasks τ_{1} and τ_{1} and characteristics of each corresponding subtask, (b) the absolute deadline of subtask τ_{a,b} is d = 10, t_{B} is the beginning of the busy period.
A scenario to obtain complete activations of task τ_{k} up to time t.
Thus we are interested in deadline –
d
busy periods with a length greater than or equal to
r
.
In a scenario where the model is composed of periodic tasks (as proposed in
[1]
) or the task model is defined as sporadic tasks with simultaneous arrival time of subtasks (as proposed in
[5]
) scheduled under EDF, the worstcase busy period occurs in the synchronous busy period, where all tasks arrive simultaneously. However, since in our model each task consists of subtasks with arbitrary release times and timing requirements, we must take into account that the critical instance may not be obtained by the occurrence of all tasks at the starting instance of the busy period. Let us consider the coincidence of which subtasks of
t_{B}
would result in the critical instance. Consider subtasks of the task τ
_{k}
that possibly delay execution of τ
_{a,b}
. Each such subtask falls in the category Set
_{k}
^{H}
, which is composed of subtasks with
D_{k,l}
≤
d
. According to the definition of the deadline –
d
busy period, only the subtasks of task τ
_{k}
,
k
≠
a
that are included in Set
_{k}
^{H}
are considered to delay the execution of the subtask τ
_{a,b}
by arriving inside a deadline –
d
busy period. Thererore, a deadline –
d
busy period could be constructed by releasing one subtask of each task with
D_{k,l}
≤
d
at
t_{B}
. However, we do not know which subtask coincident to
t_{B}
corresponds to the critical instant for the analysis of the subtask τ
_{a,b}
. Therefore, in the procedure of considering the critical instance of subtask τ
_{a,b}
, we must study all possible deadline –
d
busy period created by choosing one higher priority subtask in each task to occur at time
t
=
t_{B}
.
Fig. 3
illustrates an example showing that to construct the critical instance of τ
_{a,b}
in a deadline –
d
busy period, we must consider all cases, where a higher priority subtask of each task occurs at
t_{B}
.
Consider a system consisting of three sporadic tasks. namely τ
_{1}
, τ
_{2}
, and τ
_{a}
. The task τ
_{a}
consists of one subtask τ
_{a,b}
with
O_{a,b}
= 4 and
D_{a,b}
= 6 where it tis released at 4 unit times after
t_{B}
, as shown in
Fig. 3
. The sporadic graph of tasks τ
_{1}
, τ
_{2}
and the characteristics of corresponding subtasks are shown in
Fig. 3
a. The timeline of the activation time and deadline of subtask τ
_{a,b}
is shown in
Fig. 3
b. For simplicity, let us assume that the computation time for each subtask of every task is one unit. In this case, it is easy to show that the longest deadline –
d
busy period con be obtained by releasing τ
_{1}
and τ
_{2}
at
t_{B}
. Hence, the response time of subtask τ
_{a,b}
equals
C
_{1,1}
+
C
_{1,2}
+
C
_{1,4}
+
C
_{2,1}
+
C
_{2,2}
+
C
_{a,b}
— 4 =
2
. Let us assume another scenario defined in the same way, except that the computation time of subtask τ
_{1,3 }
equals 7. In this case, releasing the subtask τ
_{1,3}
at
t_{B}
and releasing the task τ
_{2}
at time
t_{B}
would lead to the longest deadline —
d
busy period. Hence, the response time of subtask τ
_{a,b}
equals
C
_{1,3}
+
C
_{2,1}
+
C
_{2,2}
+
C
_{a,b}
— 4 =
6
.
Theorem 1 helps us to find the worstcase scenario where τ
_{a,b}
is released at time
t_{B}
≤
r
<
t_{B}
+
L
:
Theorem 1:
The worstcase response time of subtask τ
_{a,b}
with a release time at
t_{B}
≤
r
<
t_{B}
+
L
and absolute deadline
d
, is found in a deadline —
d
busy period of subtask τ
_{a,b}
where the first activation of some subtask τ
_{k,l}
, of task τ
_{k}
, k ≠
a
, with
D_{k,l}
≤
d
coincides with
t
=
t_{B}
and task activations of τ
_{k}
occur periodically with their maximum rate inside the busy period.
Proof:
Let
t
_{1}
>
t_{B}
be the imstant at which a subtask τ
_{k,l}
,
k
≠
a
with absolute deadline
d_{k,l}
is activated the first time inside the busy period, and let
d_{k,l}
≤
d
. Suppose that we move
t
_{1}
to coincide with
t
=
t_{B}
in this circumstance; it is possible that an activation of successor subtasks of subtask τ
_{k,l}
, denoted by τ
_{k,j}
, with an absolute deadline after instant
d
may have been moved earlier to have a deadline before or at
d
; thus it would possibly increase the response time of the analyzed subtask.
Based on Theorem 1, in the procedure of finding the critical instance of subtask τ
_{a,b}
released at time
t_{B}
≤
r
<
t_{B}
+
L
, we must study all possible deadline —
d
busy periods created by choosing one higher priority subtask in each task ot occur at time
t
=
t_{B}
. Given all possible deadline —
d
busy periods, the largest response time of subtask τ
_{a,b}
accounts for its WCRT, denoted by
R_{i,j}
.
In the rest of this paper, the coincident subtask of task τ
_{k}
to
t_{B}
is denoted by τ
_{k,l}
. Through the analysis expressed in Eqs. (2)—(10) we shall assume that task τ
_{a}
consists of one subtask, τ
_{a,b}
, only. In the latter part of this section, we will extend the analysis to consider the response time of τ
_{a,b}
where the task τ
_{a}
includes a sporadic graph with precedence constraints.
Let us first consider a complete activation of task τ
_{k}
that occurs in the time interval [
t_{B}
,
t
], where
t
>
t_{B}
.
An example of calculating the required time to schedule task τ_{k} up to t.
This activation occurs before
t
, so that
t
–'activation time' ≥
T_{k}
and 'activation time' –
t_{B}
≥ 0. We denote the total number of complete activations of task τ
_{k}
that occur in the time interval [
t_{B}
,
t
], by
N_{k,l}
(
t
). As has been noted earlier, in our analysis, we assume that the subtask τ
_{k,l}
has been released at
t_{B}
. From
Fig. 4
, it is easy to see that
N_{k,l}
(
t
) could be obtained by
where
ρ_{k,l}
represents the phase between
t_{B}
and the first activation of task τ
_{k}
inside the busy period. Hence, we have
ρ_{k,l}
=
T
–
O_{k,l}
if
O_{k,l}
> 0, and
ρ_{k,l}
= 0 otherwise. The total time required to schedule activations of task τ
_{k}
that occurred completely in the time interval [
t_{B}
,
t
] equals:
Fig. 5
represents a scenario for the alignment of the task τ
_{k}
arrival pattern after
t_{B}
. The upper part of this figure corresponds to the activation and deadline of subtask τ
_{a,b}
, and the lower part represints the activation of subtasks of task τ
_{k}
. In
Fig. 4
,
N_{k,2}
(
t
^{'}
) = 0, because
t
^{'}
–
t
_{2}
<
T_{k}
. Further, since
t
^{"}
–
t
_{2}
>
T_{k}
,
t
_{2}
–
t_{B}
> 0 and also
t
^{"}
–
t
_{3}
>
T_{k}
,
t
_{3}
–
t_{B}
> 0, we have
N_{k,2}
(
t
^{"}
) = 2.
It should be noted that in the above discussion, we only find the time required to execute
N_{kl}
(
t
) activations of task τ
_{k}
. However, among those, activations of task τ
_{k}
. released after
d
–
D_{k}
would not contribute to the response time of analyzed subtask
[17]
. Thus, at each given time interval [
t_{B}
,
t
], only activations of task τ
_{k}
with deadlines before or at
d
, can contribute to the response time of analyzed subtask. At each given time interval [
t_{B}
,
t
],
C_{k,l}
(
t
) is bounded by
G_{k,l}
(
d
), which is given by following equation:
Therefore, the contribution of
N_{k,l}
(
t
) complete activations of task τ
_{k}
to the response time of the analyzed subtask, at each given time interval [
t_{B}
,
t
], is given by:
To see this, redoing the example in
Fig. 5
, let us assume that
D
_{k,1}
=
D
_{k,3}
=
T_{k}
,
D
_{k,2}
=3·
T_{k}

O
_{k,2}
and hence
D_{k}
=3·
T_{k}
. In this case, we have
C
_{k,2}
(
t"
)=2.
G_{k,2}
(
d
)= 0 and consequently,
W_{k,l}
(
t",d
)=0.
Eq. (4) only obtains the contribution of complete activations of task τ
_{k}
that occur inside the time interval [
t_{B}
,
t
]. The problem that remains is to obtain the contribution of activations that do not interfere with the response time of the subtask under analysis, completely.
We shall categorize those contributions of task τ
_{k}
into two sets. Set A: activations included in this set occur completely inside the time interval [
t_{B}
,
t
], but they have a deadline greater than
d
. Thus those activations do not interfere with the response time of τ
_{a,b}
, completely. For example, in
Fig. 5
, consider
D_{k,}
_{1}
=
D_{k,}
_{3}
=
T_{k}
,
D_{k,}
_{2}
= 3 ·
T_{k}
–
O_{k,}
_{2}
. In this case, we have
W_{k,}
_{2}
(
t''
,
d
) = 0 , but activations of task τ
_{k}
that occurred at times
t
_{2}
and
t
_{3}
consist of some subtasks that would delay the response time of τ
_{a,b}
: subtasks τ
_{k,1}
^{2}
, τ
_{k,1}
^{3}
. We shall define
to obtain the total computation time of the subtasks of activations of task τ
_{k}
in Set A by
where max(
E_{k}
) represents the summation of computation time of the subtasks of activations in Set A that have an absolute deadline less than or equal to
d
and activation time before or at
t
, so that all their predecessors also have an absolute deadline less than or equal to
d
and activation time before or at
t
. In
Fig. 5
, consider
D_{k,}
_{1}
=
D_{k,}
_{3}
=
T_{k}
,
D_{k,}
_{2}
= 3 ·
T_{k}
–
O_{k,}
_{2}
, we have
Set B: activations included in this set do not occur completely inside the time interval [
t_{B}
,
t
]. This set may consist of two members only. The first one is the first activation that occurs immediately before
t_{B}
, where
O_{k,l}
≠ 0 , for example, activation of task τ
_{k}
occurred at time
t
_{1}
, in
Fig. 5
. The second member of Set B is the last activation, where
t–′activation time′
<
T_{k}
. Consider time interval [
t_{B}
,
t
′] in
Fig. 5
: activation of task τ
_{k}
occurs at time
t
_{2}
and corresponds to this element. We shall define
to account for the total computation time of the subtasks of activations of task τ
_{k}
in Set B by:
where max(
E_{k}
) is defined as for Eq. (5). Finally, we shall define
δ_{k,l}
(
t,d
) to obtain the total computation time of the subtasks of activations of task τ
_{k}
in Set A and Set B by
So far, we have studied the contribution of task τ
_{k}
to the response time of τ
_{a,b}
that has been released until time
t
. In general, the study of response time of a subtask τ
_{a,b}
with deadline
d
is an iterative procedure. The basic idea is that in each step, the obtained busy period must be the end of the execution of all instances of all tasks with deadlines less than or equal to
d
that have been released in the previous steps. Toward this, we shall define
LN
_{a,b}
(
t,d
)
^{(k)}
to represent the length of the resulting busy period in the k
^{’th}
iteration of response time analysis of subtask τ
_{a,b}
with deadline
d
, where
t
is substituted with the length of the obtained busy period in the previous step.
LN
_{a,b}
(
t,d
)
^{(k)}
is obtained by the iterative equation, Eq. (9). This equation represents the iterative procedure, where at each step the length of a busy period is given by the summation of execution times obtained in Eqs. (4) and (7). We shall initiate this iterative procedure by Eq. (8). In Eq. (8),
c_{k,l}
represents the execution time of the subtask coincident to
t_{B}
. The iteration is halted where the computations converge.
The response time of subtask τ
_{a,b}
where it occurs at time
t_{B}
≤
r
<
t_{B}
+
L
is
The problem that remains to be solved is to determine the response time of subtask τ
_{a,b}
, where task τ
_{a}
includes a sporadic graph with precedence constraints. Consider a scenario where τ
_{a,b}
is released at
r
. In this case, the response time of τ
_{a,b}
is influenced by the order of execution of all subtasks of task τ
_{a}
that must be scheduled before τ
_{a,b}
. Further, this sequence of subtasks of task τ
_{a}
may not be the same as the sequence of subtasks in another scenario where τ
_{a,b}
is released at
r
′. Therefore, it is of great importance to determine the order of subtasks of task τ
_{a}
that must be scheduled before τ
_{a,b}
for each release time of τ
_{a,b}
.
In order to find the correct response time of subtask τ
_{a,b}
, we shall use Procedure 1 to determine the correct sequence of subtasks of task τ
_{a}
that must be scheduled before τ
_{a,b}
. This procedure would let us to consider the correct sequence of subtasks of task τ
_{a}
that must be scheduled before τ
_{a,b}
and consequently the correct response time of subtask τ
_{a,b}
. To show this, let us denote the current subtask of task τ
_{a}
of which its response time has been considered by τ
_{a,q}
and the next chosen subtask by τ
_{a,p}
. Consider a scenario where τ
_{a,b}
is released at
r
. In this case, τ
_{a,q}
and all the subtasks of task τ
_{a}
that have been considered by Eqs. (8) or (9) will be dropped from the sporadic graph of task τ
_{a}
, by Procedure 1. When τ
_{a,p}
is chosen as the analyzed subtask by Procedure 1, it must have the minimum deadline among all subtasks of task τ
_{a}
that arrived at or before the completion of execution of τ
_{a,q}
, but they have no predecessors. This fact is in accordance with the definition of scheduling mentioned in Section III.
Response time comparison of subtasks with offset = 0.
V. COMPARISON WITH EXISTING TECHNIQUES
We have compared the results of our proposed analysis, with the results obtained by Palencia and Harbour
[8]
. This approach transforms a distributed system schedulability analysis to an equivalent analyzable uniprocessor schedulability test, by using task offsets. Since tasks are preemptive, without loss of generality, we applied the static offset technique on a set of chains of subtasks, where each node in a chain represents a preemptive subtask.
Fig. 6
shows the obtained average response time by our analysis and obtained average response time by the static offset technique proposed in
[8]
. We ran our simulation on a task set consisting of 20 tasks, each one including five subtasks. The average response time corresponded to five subtasks of an analyzed task. The xaxis represents the processor utilization which varies with the changing execution time of the subtasks in the task set. The deadline of subtasks in the task set is generated randomly, except the 2nd subtask of each task in the first scenario and 2nd and 4th subtask in the second scenario. In the first scenario, the deadline of the 2nd subtask of each of the 20 tasks is generated so that it is greater than the deadline of the analyzed task. In the second scenario, the deadline of the 2nd and 4th subtask of each of the 20 tasks is generated so that it is greater than the deadline of the analyzed task. For the first scenario, it can be seen that the average response time obtained by the static offset technique is between 3 to 5 times larger than that of our results. The reason is that the static offset technique accounts for the execution time of the 3rd, 4th, and 5th subtasks of the interfering tasks in the task set where they do not contribute to the response time of the analyzed subtasks. In fact, it accounts for the execution time of each interfering subtask assuming that the corresponding predecessors have a deadline less than the analyzed subtask. This is a result that is shown to be flawed by
[7]
in the case of fixed priority scheduling. As for the second scenario, it can be seen that the difference between the average response times is tighter. However, our simulation same results as the first scenario. The obtained smaller average response times by the static offset method is due to accounting for the execution time of the 3rd and 5th subtasks of the interfering tasks in the task set. However, in our constructed scenario, since the task offsets are set to zero, by the definition of the deadline busy period, they do not contribute to the response time of the analyzed subtasks.
In order to evaluate the pessimism of the admission controllers of our analysis and the static offsetbased method implemented on a uniprocessor, we conducted simulations to identify the lowest utilization at which deadlines are missed. We perform our simulation on a set of 30 tasks with 5 subtasks per task, in one processor, for the case in which the task offsets are zero. Task sets were generated randomly, and the subtask specifications do not represent worstcase scenarios. We add a new task, denoted by τ
_{a}
, with 5 subtasks with randomly generated deadlines, accordingly. We increased the utilization of the task set by increasing the execution time of subtasks uniformly, until deadline misses were observed.
Fig. 7
presents the results of our analysis where the yaxis represents the utilization and xaxis represents 5 states. Under state 1 (2, 3, 4, 5) each task has the first (and second, third, fourth, and fifth, respectively) subtask in its corresponding chain with a deadline greater than D
_{a}
. Each bar in
Fig. 7
presents the results from the simulations of the lowest utilization at which the deadline misses were observed for different task states in the system.
Our analysis test vs. static offsetbased technique with different states of deadlines of subtasks within tasks.
It can be observed that for our analyzed task model, the new task τ
_{a}
can be admitted for all utilizations in the first 4 states. In the 5th state, τ
_{a}
can be admitted for utilizations below 90%. In addition, for the first 4 states, the maximum utilization of the task set at which τ
_{a}
can be admitted, by the static offset based method, fluctuates between 80% in the 4th state and 100% in the 3rd state. As previously mentioned, the drawback of the static offsetbased analysis is that it accounts for the execution time of each interfering subtask assuming that the corresponding predecessors have a deadline less than D
_{a}
. The 2nd, 3rd, and 4th state can be similarly described, indeed. However, in the 5th state, both methods have the same results.
In another experiment, we consider a scenario where the task sets represent the worstcase scenario. In this case, all the subtasks with a deadline less than or equal to D
_{a}
have a deadline less than or equal to the minimum deadline of the subtasks of task τ
_{a}
.
Fig. 8
presents the results of our analysis where the Y axis represents the utilization and xaxis represents 10 states. The first 5 states are tested as explained for
Fig. 7
. State 6 represents a scenario where the 1st and 3rd subtask have a deadline strictly greater than D
_{a}
. State 7 represents a scenario where the 1st and 4th subtask have a deadline strictly greater than D
_{a}
. State 8 represents a scenario where the 2nd and 4th subtask have a deadline strictly greater than D
_{a}
in state 9 and 10, subtasks 1st, 4th and 5th and 2nd, 4th and 5th, respectively, have a deadline strictly greater than D
_{a}
. In this case, due to the drawback pointed out for the last experiments, it can be seen that the maximum task set utilization obtained by the offset based technique degrades significantly.
Our analysis test vs. static offsetbased technique with different states of deadline of subtasks within tasks in the worst case.
VI. CONCLUSIONS
In this paper, we studied the exact WCRT analysis of sporadic tasks that are modeled by DAG and scheduled under preemptive EDF scheduling. The objective is to obtain precise WCRTs of a generalized sporadic task model with arbitrary timing requirements that have not been considered in previous works. A nice feature of our work is that it exploits the precedence constraints between subtasks in an accurate way while taking advantage of the deadlines of subtasks. We find via simulation results that our methodology provides accurate results comparable with existing works.
Acknowledgements
This work was supported by University of Ulsan, School of Excellence in Electrical Engineering.
Spuri M.
2006
“Analysis of deadline scheduled realtime systems”
Institut National de Recherche en Informatique et en Automatique (INRIA)
Le Chesnay, France
Report no. 2772
Zhang F.
,
Burns A.
2009
“Schedulability analysis for realtime systems with EDF scheduling”
IEEE Transactions on Computers
58
(9)
1250 
1258
Zhang Y.
,
Krecker D. K.
,
Gill C.
,
Lu C.
,
Thaker G. H.
2008
“Practical schedulability analysis for generalized sporadic tasks in distributed realtime systems”
in Proceedings of the Euromicro Conference on RealTime Systems
Prague, Czech
223 
232
Zhao H. X.
,
Midonnet S.
,
George L.
2005
“Worst case response time analysis of sporadic graph tasks with fixed priority scheduling on a uniprocessor”
in Proceedings of the 11th IEEE International Conference on Embedded and RealTime Computing Systems and Applications
Hong Kong, China
23 
29
Zhao H. X.
,
George L.
,
Midonnet S.
2006
“Worst case response time analysis of sporadic graph tasks with EDF scheduling on a uniprocessor”
in Proceedings of the 12th IEEE International Conference on Embedded and RealTime Computing Systems and Applications
Sydney, Australia
271 
278
Harbour M. G.
,
Klein M. H.
,
Lehoczky J. P.
1994
“Timing analysis for fixedpriority scheduling of hard realtime systems”
IEEE Transactions on Software Engineering
20
(1)
13 
28
Harbour M. G.
,
Klein M. H.
,
Lehoczky J. P.
1991
“Fixed priority scheduling periodic tasks with varying execution priority”
in Proceedings of the 12th RealTime Systems Symposium
San Antonio: TX
116 
128
Palencia J. C.
,
Harbour M. G.
2002
“Offsetbased response time analysis of distributed systems scheduled under EDF”
in Proceedings of the 5th Euromicro Conference on RealTime Systems
Porto, Portugal
3 
12
Liu C. L.
,
Layland J. W.
1973
“Scheduling algorithms for multiprogramming in a hardrealtime environment”
Journal of the ACM
20
(1)
46 
61
Kim K. H.
,
Naghibzadeh M.
1980
“Prevention of task overruns in realtime nonpreemptive multiprogramming systems”
in Proceedings of the International Symposium on Computer Performance Modelling, Measurement and Evaluation
Toronto, Canada
267 
276
Mangeruca L.
,
Baleani M.
,
Ferrari A.
,
SangiovanniVincentelli A.
2007
“Uniprocessor scheduling under precedence constraints for embedded systems design”
ACM Transactions on Embedded Computing Systems
article no. 6
7
(1)
Spuri M.
1996
“Holistic analysis for deadline scheduled realtime distributed systems”
Institut National de Recherche en Informatique et en Automatique (INRIA)
Le Chesnay, France
Report no. 2873
Pellizzoni R.
,
Lipari G.
2005
“Improved schedulability analysis of realtime transactions with earliest deadline scheduling”
in Proceedings of the 11th IEEE Real Time on Embedded Technology and Applications Symposium
San Francisco: CA
66 
75
Palencia J. C.
,
Harbour M. G.
1999
“Exploiting precedence relations in the schedulability analysis of distributed realtime systems”
in Proceedings of the 20th IEEE RealTime Systems Symposium
Phoenix: AZ
328 
339
Palencia J. C.
,
Harbour M. G.
1998
“Schedulability analysis for tasks with static and dynamic offsets”
in Proceedings of the 19th IEEE RealTime Systems Symposium
Madrid, Spain
26 
37
Redell O.
2004
“Analysis of treeshaped transactions in distributed real time systems”
in Proceedings of the 16th Euromicro Conference on RealTime Systems
Catania, Italy
239 
248
Tindell K.
1994
“Adding timeoffsets to schedulability analysis”
Department of Computer Science, University of York
England