![](https://csdnimg.cn/release/download_crawler_static/16256914/bg6.jpg)
14:6 J. Sun et al.
Fig. 3. An example CRT task τ .
Fig. 4. An example FJRT task that cannot be ex-
pressed by a CRT model.
model into a regular substructure of the hypergraph, which can subsequently be used
to construct an equivalent FJRT model for the original CRT model. Finally, we present
the counterexample of the parallel task that can be expressed by the FJRT model but
cannot be expressed by the CRT model.
Definition 2.5 (Concurrent Real-Time Task System [Ejsing-Duun et al. 2013]). A
Concurrent Real-Time Task System ( CRT) S isatupleS = (τ, J, e, d), where
—J is a finite set of jobs,
—e: J → N is a mapping from jobs to worst-case execution times,
—d: J → N is a mapping from jobs to relative deadlines, and
—τ is a configuration defined by the following grammar.
—Configuration: τ ::= T | T τ
—Task: T ::= j | T
1
xT
2
| S
1
S
2
| T
1
+ T
2
| T
ω
—Subtask: S ::= j | S
1
xS
2
| S
1
S
2
| S
1
+ S
2
Here, j ∈ J is a job and x ∈ N, T
1
xT
2
is the sequential composition of tasks T
1
and
T
2
, with interrelease time x, T
1
+ T
2
is the choice between tasks T
1
and T
2
, S
1
S
2
is
the parallel composition of subtasks S
1
and S
2
,andT
ω
is one or more iterations of T .
In contrast to the definition of our FJRT model, the CRT model is inductively defined
by some regular grammar. The grammar of the configuration defines the task system,
which can be viewed as a composition of arbitrarily many independent tasks running in
parallel (intertask parallelism). Moreover, a nondeterministic choice between different
execution paths or subtasks running in parallel can be expressed by the grammar of
tasks and subtasks. Note that the subtasks defined in the CRT are restricted t o not
include any cycles. This article considers only acyclic parallel subtasks in the FJRT
model.
Example 2.6. Figure 3 represents the CRT task τ = ( j
1
30(( j
2
40 j
3
)( j
4
+ j
5
)))
ω
,
where e( j
1
) = 1, d( j
1
) = 20; e( j
2
) = 4, d( j
2
) = 25; e( j
3
) = 6, d( j
3
) = 25; e( j
4
) =
2, d( j
4
) = 25; and e( j
5
) = 4, d( j
5
) = 25. As shown in Figure 3, the vertices in the
graph represent jobs, each labeled with an execution time and a deadline. The arcs in
the graph represent dependencies between jobs and are labeled with their minimum
interrelease time.
The combination of Theorem 2.7 and Example 2.8 proves that our digraph-based
FJRT model is more expressive than the CRT models.
T
HEOREM 2.7. The FJRT model is at least as expressive as the CRT model.
P
ROOF. We prove by induction that each grammar rule listed in Definition 2.5 can
be fully expressed by a substructure of the hypergraph. We do this by first introducing
the prefix and suffix operations for tasks, as follows.
ACM Transactions on Embedded Computing Systems, Vol. 15, No. 1, Article 14, Publication date: February 2016.