Bounding Cache-Related Preemption Delay for Real-Time Systems.
AbstractCache memory is used in almost all computer systems today to bridge the ever increasing speed gap between the processor and main memory. However, its use in multitasking computer systems introduces additional preemption delay due to the reloading of memory blocks that are replaced during preemption. This cache-related preemption delay poses a serious problem in real-time computing systems where predictability is of utmost importance. In this paper, we propose an enhanced technique for analyzing and thus bounding the cache-related preemption delay in fixed-priority preemptive scheduling focusing on instruction caching. The proposed technique improves upon previous techniques in two important ways. First, the technique takes into account the relationship between a preempted task and the set of tasks that execute during the preemption when calculating the cache-related preemption delay. Second, the technique considers the phasing of tasks to eliminate many infeasible task interactions. These two features are expressed as constraints of a linear programming problem whose solution gives a guaranteed upper bound on the cache-related preemption delay. This paper also compares the proposed technique with previous techniques using randomly generated task sets. The results show that the improvement on the worst-case response time prediction by the proposed technique over previous techniques ranges between 5 percent and percent depending on the cache refill time when the task set utilization is 0.6. The results also show that as the cache refill time increases, the improvement increases, which indicates that accurate prediction of cache-related preemption delay by the proposed technique becomes increasingly important if the current trend of widening speed gap between the processor and main memory continues.
Introduction
In a real-time computing system, tasks have timing constraints in terms of deadlines that
must be met for correct operation. To guarantee such timing constraints, extensive research
has been performed on schedulability analysis [1, 2, 3, 4, 5, 6]. In these studies, various
assumptions are usually made to simplify the analysis. One such simplifying assumption
is that the cost of task preemption is zero. This assumption, however, does not hold
in general in actual systems invalidating the result of the schedulability analysis. For
example, task preemption incurs costs to process interrupts [7, 8, 9, 10], to manipulate task
queues [7, 8, 10], and to actually perform context switches [8, 10]. Many of such direct
costs are addressed in a number of recent studies on schedulability analysis that focus on
practical aspects of task scheduling [7, 8, 9, 10].
In addition to the direct costs, task preemption introduces a form of indirect cost due to
cache memory, which is used in almost all computer systems today. In computer systems
with cache memory, when a task is preempted a large number of memory blocks 1 belonging
to the task are displaced from the cache memory between the time the task is preempted
and the time the task resumes execution. When the task resumes execution, it spends a
substantial amount of its execution time reloading the cache with the memory blocks that
were displaced during preemption. Such cache reloading greatly increases preemption delay,
which may invalidate the result of schedulability analysis that overlooks this indirect cost.
There are two ways to address the unpredictability resulting from the above cache-related
preemption delay. The first way is to use cache partitioning where cache memory is divided
into disjoint partitions and one or more partitions are dedicated to each real-time task [12,
13, 14, 15]. In the cache partitioning techniques, each task is allowed to access only its own
partition and thus cache-related preemption delay is avoided. However, cache partitioning
1 A block is the minimum unit of information that can be either present or not present in the cache-main
memory hierarchy [11]. We assume without loss of generality that memory references are made in block
units.
has a number of drawbacks. One drawback is that it requires modification of existing
hardware, software, or both. Another drawback is that it limits the amount of cache
memory that can be used by individual tasks.
The second way to address the unpredictability resulting from the cache-related preemption
delay is to take into account its effects in the schedulability analysis. In [16], Basumallick
and Nilsen propose one such technique. The technique uses the following schedulability
condition for a set of n tasks, which extends the well-known Liu and Layland's schedulability
condition [4].
In the condition, U is the total utilization of the task set and C i and T i are the worst case
execution time (WCET) and period of - i , respectively 2 . The additional term fl i is an upper
bound on the cache-related preemption cost that - i imposes on preempted tasks.
One drawback of this technique is that it suffers from a pessimistic utilization bound, which
approaches 0.693 for a large n [4]. Many task sets that have total utilization higher than
this bound can be successfully scheduled [3]. To rectify this problem, Busquets-Mataix et
al. in [17] propose a technique based on the response time approach [2, 6]. In this technique,
the incorporated into the response time equation as follows
d
e \Theta (C j
where R i is the worst case response time of - i and hp(i) the set of tasks whose priorities are
higher than that of - i . This recursive equation can be solved iteratively and the resulting
worst case response time R i of task - i is compared against its deadline D i to determine the
schedulability.
These notations will be used throughout this paper along with D i that denotes the deadline of - i where
We assume without loss of generality that - i has higher priority than -
Main Memory Cache Memory
preempt preempt
preempt preempt
(a) Cache mapping (b) Worst case preemption scenario
's response time:
preempt
Fig. 1. Overestimation of cache-related preemption delay.
The used in both techniques is computed by multiplying the number of cache
blocks used by task - i and the time needed to refill a cache block. This estimation is based
on a pessimistic assumption that each cache block used by - i replaces from the cache a
memory block that is needed by a preempted task. This pessimistic assumption leads to
overestimation of the cache-related preemption delay since it is possible that the replaced
memory block is one that is no longer needed or one that will be replaced without being
re-referenced even when there were no preemptions.
The above overestimation is addressed by Lee et al. in [18]. They use the concept of useful
cache blocks in computing the cache-related preemption delay where a useful cache block
is defined as a cache block that contains a memory block that may be re-referenced before
being replaced by another memory block. Their technique consists of two steps. The first
step analyzes each task to estimate the maximum number of useful cache blocks in the
task. Based on the results of the first step, the second step computes an upper bound on
the cache-related preemption delay using a linear programming technique. As in Busquets-
Mataix et al.'s technique, this upper bound is incorporated into the response time equation
to compute the worst case response time.
Although Lee et al.'s technique is more accurate than the techniques that do not consider
the usefulness of cache blocks, it is still subject to a number of overestimation sources. We
explain these sources using the example in Fig. 1. In the example, there are three tasks,
we assume without loss of generality that - i has higher priority than
has the highest priority and task - 3 the lowest priority. Suppose that
main memory regions used by the three tasks are mapped to the cache as in Fig. 1-(a).
Also, suppose that the maximum number of useful cache blocks of - 2 and - 3 is 5 and 2,
respectively, and that the time needed to refill a cache block is a single cycle. In this setting,
the linear programming method used in Lee et al.'s technique would give a solution where
preempted three times by - 1 , and - 3 is preempted twice by - 2 during - 3 's response
time R 3 resulting in a preemption delay of 3 \Theta 5
The above solution, however, suffers from two types of overestimation. First, when a task
is preempted, not all of its useful cache blocks are replaced from the cache. For example,
when - 2 is preempted by - 1 , only a small portion of - 2 's useful cache blocks can be replaced
from the cache corresponding to those that conflict with cache blocks used by - 1 , i.e., the
cache blocks framed by thick borders in Fig. 1-(a). Second, the worst case preemption
scenario given by the solution may not be feasible in the actual execution. For example,
cannot be preempted three times by - 1 since - 2 has the WCET of only 20 and thus, the
first invocation of - 2 can certainly be completed before the second invocation of - 1 .
To rectify these problems, this paper proposes a novel technique that incorporates the
following two important features. First, the proposed technique takes into account the relationship
between a preempted task and the set of tasks that execute during the preemption
when calculating the maximum number of useful cache blocks that should be reloaded after
the preemption. Second, the technique considers phasing of tasks to eliminate many
infeasible task interactions. These two features are expressed as constraints of the linear
programming problem whose solution bounds the cache-related preemption delay. In this
paper, we focus on the cache-related preemption delay resulting from instruction caching.
Analysis of data cache-related preemption delay is an equally important research issue and
can be handled by the method explained in [18].
This paper also compares the proposed technique with previous techniques. The results
show that the proposed technique gives up to 60% tighter prediction of the worst case response
time than the previous techniques. The results also show that as the cache refill
time increases, the gap between the worst case response time prediction made by the proposed
technique and those by previous techniques increases. Finally, the results show that
as the cache refill time increases, the cache-related preemption delay takes a proportionally
large percentage in the worst case response time, which indicates that accurate prediction
of cache-related preemption delay becomes increasingly important if the current trend of
widening speed gap between the processor and main memory continues [11].
The rest of the paper is organized as follows: The next section describes in detail Lee
et al.'s technique, which serves as the basis for our proposed technique. In Section III,
we describe the overall approach of the proposed technique along with constraints that
are needed to incorporate scenario-sensitive preemption cost. More advanced constraints
that take into account task phasing are discussed in Section IV. In Section V, we discuss
an optimization that aims to reduce the amount of computation needed in the proposed
technique. Section VI presents the results of our experiments to assess the effectiveness of
the proposed technique. Finally, we conclude this paper in Section VII.
II. Linear Programming-based Analysis of
Cache-related Preemption Delay
In this section, we describe in detail Lee et al.'s linear programming-based technique for
analyzing cache-related preemption delay.
In the technique, the response time equation is given as follows
where the PC i (R i ) term is a guaranteed upper bound on the cache-related preemption
delay of - i during a given response time R i . The term includes not only the delay due to
preemptions but also the delay due to the preemptions of higher priority tasks. The
response time equation can be solved iteratively as follows:
d
(R 0
R k+1
(R k
This iterative procedure terminates when R m
m and this converged R i
value is compared against - i 's deadline to determine the schedulability of - i .
To compute PC i (R k
i ) at each iteration, the technique uses a two step approach. In the first
step, each task is analyzed to estimate the maximum number of useful cache blocks that the
task may have during its execution. The estimation uses a data flow analysis technique [19]
that generates the following two types of information for each execution point p and for
each cache block c:
1. the set of memory blocks that may reside in the cache block c at the execution point
p and
2. the set of memory blocks that may be the first reference to the cache block c after
the execution point p.
The cache block c is defined to be useful at point p if the above two sets have any common
element, which means that there may be an execution where the memory block in cache
block c at p is re-referenced. The total number of useful cache blocks at p determines the
additional cache reloading time that is incurred if the task is preempted at p. Obviously,
the worst case preemption occurs when the task is preempted at the execution point with
the maximum total number of useful cache blocks and this case gives the worst case cache-related
preemption cost for the task. The final result of the first step is a table called the
preemption cost table that gives for each task - i the worst case preemption cost f i
3 .
The second step uses the preemption cost table and a linear programming technique to
derive an upper bound on PC i (R i ) that is required at each iteration of the response time
calculation. This step first defines g j as the number of preemptions of - j during R i . If the g j
values that give the worst case preemption scenario among tasks are known, the worst case
cache-related preemption delay of - i during interval R i , i.e., PC i (R i ), can be calculated as
follows:
This total cache-related preemption delay of - i includes all the delay due to the preemptions
of - i and those of higher priority tasks. Note that the highest priority task - 1 is not included
in the summation since it can never be preempted.
In general, however, the exact g j values that give the worst case preemption delay of - i
cannot be determined. Thus, for the analysis to be safe, a scenario that is guaranteed to
be worse than any actual preemption scenario should be assumed. Such a conservative
scenario can be derived from the following two constraints that any valid g j combination
should satisfy.
3 The technique defines a more general preemption cost f i;j , which is the cost task - i pays in the worst
case for its j-th preemption over the (j \Gamma 1)-th preemption. However, since in most cases the execution
point with the maximum total number of useful cache blocks is contained within a loop nest, the generalized
preemption cost has little effect because f is the product of the iteration
bounds of all the containing loops.
First, the total number of preemptions of - during R i cannot be larger than the
total number of invocations of -
Second, the total number of preemptions of - j during R i cannot be larger than the number
of invocations of - j during R i multiplied by the maximum number of times that any single
invocation can be preempted by higher priority tasks
e \Theta
d
Note that since the technique computes the worst case response times from the highest
priority task to the lowest priority task, the worst case response times of -
that is, R 1 are available when R i is computed.
To summarize, in Lee et al.'s technique, the problem of computing a safe upper bound on
formulated as a linear programming problem in which the objective function
value
maximized while satisfying the above two constraints.
As a side note, linear programming is increasingly being used in the real-time research area
because of its strong theoretical ground. For example, it is used to bound the worst case
execution time of a task [20]; to bound the interference of program execution by DMA
operation [21]; and to bound the number of retries in lock-free real-time systems [22].
III. Overall Approach
One problem with Lee et al.'s technique is that the preemption cost of a task is fixed
regardless of which tasks execute during the task's preemption. This may result in severe
overestimation of cache-related preemption delay when only a few cache blocks are shared
among tasks. For example, if the cache blocks used by a preempted task and those used
by the tasks that execute during the preemption are disjoint, the preemption cost of this
particular preemption would be zero. Nevertheless, Lee et al.'s technique assumes that
the preemption cost is still the time needed to reload all the useful cache blocks of the
preempted task.
To address this problem, the technique proposed in this paper takes into account the relationship
between a preempted task and the set of tasks that execute during the preemption
in computing the preemption cost. For this purpose, the proposed technique categorizes
preemptions of a task into a number of disjoint groups according to which tasks execute
during preemption. The number of such disjoint groups is when there are k higher
priority tasks. For example, if there are three higher priority tasks - 1 , - 2 , and - 3 for a
lower priority task - 4 , the number of possible preemption scenarios of - 4 is 7 (=
corresponding to f- 1 g, f- 2 g, f- 3 g, f- according to
the set of tasks that execute during - 4 's preemption. For task - j , we denote by P j \Gamma1 the set
of all of its possible preemption scenarios by the higher priority tasks
that set P j \Gamma1 is equal to the power set [23] of the set f- excluding the empty
set since for task - j to be preempted, at least one higher priority task must be involved. In
addition, we denote by p j (H) the preemption of task - j during which the tasks in set H
execute. For example, denotes the preemption of - 4 during which tasks - 1 and
The preemption costs of tasks for different preemption scenarios are given by the following
augmented preemption cost table for this example.
blocks
U U
U
U
U
U
U U U U
c 6
c 7
execution points
cache
blocks
U
Fig. 2. Calculation of scenario-sensitive preemption cost.
To compute f j (H), the preemption cost of scenario p j (H), the following three steps are
taken based on the information about the set of useful cache blocks, which can be obtained
through the analysis explained in [18]. First, for each execution point in task - j , we compute
the intersection of the set of useful cache blocks of - j at the execution point and the set
of cache blocks used by tasks in H. Second, we determine the execution point in - j with
the largest elements (i.e., useful cache blocks) in the intersection. Finally, we compute
the (worst case) preemption cost of this preemption scenario by multiplying the number of
useful cache blocks in that intersection and the cache refill time.
As an example, consider Fig. 2 that shows the set of useful cache blocks (denoted by U's in
the figure) for all the execution points of a lower priority task - 4 and the sets of cache blocks
used by higher priority tasks - 1 , - 2 , and - 3 . In this example, the worst case preemption cost
of - 4 for the case where tasks - 1 and - 3 execute during preemption (i.e., f 4 (f-
multiplied by the cache refill time. This preemption cost is determined by the execution
point shaded in the figure, which has the largest number of useful cache blocks that conflict
with the cache blocks used by - 1 and - 3 .
Since there are preemption scenarios for k higher priority tasks, we need
to compute the same number of preemption costs in the worst case. This may require an
enormous amount of computation when k is large. The computational requirement can be
reduced substantially by noting that we do not need to consider the higher priority tasks
whose cache blocks do not conflict with the cache blocks used by the task for which the
preemption cost is computed. For example, in Fig. 2 since none of the cache blocks used by
conflict with those used by - 4 , we do not need to consider the preemption scenarios that
include - 2 when computing the preemption costs of - 4 . Instead, the preemption costs for
scenarios that include - 2 can be derived from those that do not include - 2 by noting that
A. Problem formulation
To formulate the problem of computing a safe upper bound of PC i (R i ) as a linear programming
problem based on the augmented preemption costs f j (H)'s, we define a new variable
j (H) that denotes the number of preemptions of - j by task set H, that is, the number of
preemptions of scenario p j (H). The corresponding objective function is
This objective function states that the cache-related preemption delay of - i during R i is the
sum of delay due to preemptions of - i and those of higher priority tasks during R i where the
delay due to preemptions of a task is defined as the sum of the counts of mutually disjoint
preemption scenarios of that task multiplied by the corresponding preemption costs.
As in Lee et al.'s technique, we cannot determine the exact g j (H) values that give the worst
case preemption delay and thus we should use various constraints on the g j (H)'s to bound
the objective function value. In the next subsection, we give two such constraints that are
extensions of Lee et al.'s original constraints. Then, in Section C, we discuss an advanced
constraint that relates the invocations of a higher priority task and the preemptions of
lower priority tasks where the higher priority task is involved. In Section IV, we give
more advanced constraints that consider phasing of tasks to eliminate many infeasible task
preemption scenarios. Finally, in Section V, we discuss an optimization that reduces the
computational requirement of the proposed technique.
B. Extensions of Lee et al.'s constraints
This subsection describes extensions (based on scenario-sensitive preemption cost) of the
two constraints used in Lee et al.'s technique. The extended constraints are given in terms
of g j (H)'s and, as we will see later, subsume Lee et al.'s original two constraints.
The first constraint of Lee et al.'s technique, which states that the total number of preemptions
of during R i cannot be larger than the total number of invocations
of during R i , can be straightforwardly extended using g j (H)'s as follows:
g k (H) -
Note that since
k (H) is equal to g k , the above constraint is equivalent to the first
constraint of Lee et al.'s technique.
Similarly, the second constraint, which originally states that the total number of preemptions
of - j during R i cannot be larger than the number of invocations of - j during R i multiplied
by the maximum number of times that any single - j invocation can be preempted
by higher priority tasks can be extended as follows:
e \Theta d R j
This constraint states that the number of preemptions of - j during which a higher priority
executes is bounded by the number of invocations of - j multiplied by the maximum
number of times that any single - j invocation can be preempted by - k . To show that this
constraint subsumes the second constraint of Lee et al.'s technique, we sum up both sides
of the constraints for
e \Theta
j (H) and
j (H), we have
e \Theta
d
This shows that the new constraint subsumes the second constraint of Lee et al.'s technique.
In addition, since the number of preemptions of - j during which a higher priority task - k
executes is bounded by the number of - k invocations, we have
By combining Constraints (4) and (5), we have
e \Theta d
Since the new constraints described in this subsection are either equivalent to or more stringent
than the original two constraints of Lee et al.'s technique and f j (H) is always less than
or equal to f j for all H in resulting objective function value
is always smaller than or equal to the objective function value
of Lee et al.'s tech-
(a) Cache mapping (b) Preemption cost table
(c) Task invocations
Task
R 4
Fig. 3. Example task set.
nique yielding a tighter prediction of cache-related preemption delay.
As an example, consider the task set in Fig. 3 that consists of four tasks - 1 , - 2 , - 3 , and
is the highest priority task and - 4 the lowest one. Assume that the tasks are
mapped to cache memory as shown in Fig. 3-(a), where the useful cache blocks of tasks - 1 ,
are denoted by numbers 1, 2, 3, and 4, respectively. The cache mapping and
distribution of useful cache blocks of the tasks give the preemption cost table in Fig. 3-(b)
assuming that the cache refill time is a single cycle 4 .
Assume that we are interested in computing the cache-related preemption delay during the
response time of task - 4 , denoted by R 4 in Fig. 3-(c). Also assume that during R 4 , there
4 In this example, to simplify the explanation, we assume that the set of useful cache blocks of each task
shown in Fig. 3-(a) includes the set of useful cache blocks of any other execution point in the task. This
assumption does not hold in general as the example in Fig. 2 illustrates.
are four invocations of - 1 , three invocations of - 2 , and two invocations of - 3 , whose response
times are denoted in the figure by R 1 , R 2 , and R 3 , respectively. Note that these response
times are available when we compute R 4 since we calculate the response times from the
highest priority task to the lowest priority task.
From the first constraint, i.e., Constraint (3), we have the following three inequalities:X
d
R 4
Similarly, from the second constraint, i.e., Constraint (6), we have the following inequalities:
e \Theta d
R 4
g 3
e \Theta d R 3
g 3
e \Theta d R 3
g 4
- min(d R 4
e \Theta d R 4
g 4
- min(d R 4
e \Theta d R 4
g 4
- min(d R 4
e \Theta d R 4
2:
The maximum objective function value that satisfies the above two sets of constraints is
and the values of g j (H)'s that give the maximum are as follows.
For comparison purposes, if Lee et al.'s technique were used instead, the maximum objective
function value would be 54, which is significantly larger than that given by the proposed
technique. This maximum objective function value is derived from
preemption costs f are determined from
the number of useful cache blocks of the tasks shown in Fig. 3-(a). Note that the solution
corresponds to the case where all the nine invocations of tasks - 1 , - 2 , and - 3 preempt task
which has the largest preemption cost. The constraints used areX
d
R 4
R 4
e \Theta d
R 4
e \Theta (d R 3
e \Theta (d R 4
C. Advanced constraints on the relationship between task invocations and preemption

Although the new constraints are more stringent than those of Lee et al.'s technique, they
cannot eliminate all infeasible preemption scenarios. In fact, even the combination of the
g j (H) values that gives the maximum objective function value in our previous example
is infeasible since it requires at least eight invocations of - 1 whereas there are only four
invocations of - 1 in the example (cf. Fig. 3-(c)). Among the eight required invocations,
four invocations are from g 3 (f- 1 meaning that there are four preemptions of - 3 during
which only - 1 executes. The other four required invocations are from g 4 (f- 1
that there are four preemptions of - 4 during which only - 1 executes.
The reason why our earlier constraints cannot eliminate the above infeasible preemption
scenario is that they cannot relate the invocations of a higher priority task and the preemptions
of lower priority tasks where that higher priority task is involved. For the example in
Fig. 3, it can be trivially shown that the sum of the number of preemptions of - 2 , - 3 , and
during which only - 1 executes is bounded by the number of - 1 invocations giving the
following constraint,
which eliminates the infeasible preemption scenario.
At first sight, it appears that the above problem can be solved by bounding the number
of preemptions of lower priority tasks - during which a higher priority task
executes by the number of invocations of that higher priority task - j , which can be
expressed by the following constraint:
g k (H) - d R i
This constraint, when cast into our example in Fig. 3, is translated into the following
constraint when - 1 is the higher priority task involved:
This particular constraint, and Constraint (7) in general, however, is not safe meaning
that a valid preemption scenario may not satisfy it because a single invocation of a higher
priority task can be involved in more than one preemption of lower priority tasks, and thus
can be counted multiple times in the summation on the left-hand side of Constraint (7). For
example, when - 3 is preempted by - 2 and - 2 is, in turn, preempted by - 1 , the invocation of
doubly counted, first in g 2 (f- 1 g) and second in g 3 (f- In general, an invocation
of - k can be doubly counted in g j (H) and g.
We capture this observation by a symmetric relation [23] which we call the DC (standing for
doubly counted) relation denoted by dc
$. This relation associates two preemption scenarios
g. For our example
with four tasks - 1 , - 2 , - 3 , and - 4 , all the possible pairs of preemption scenarios related by
dc
are as follows:
Using this relation, safe constraints can be derived as follows: Consider a combination of
preemption scenarios where a higher priority task is involved. If no pair of preemption
scenarios in the combination is related by dc
$, the sum of the number of the preemptions in
the combination can be bounded by the number of invocations of the higher priority task.
For example, the following constraint that eliminated the infeasible preemption scenario,
is safe since no pairs of the preemption scenarios that appear on the left-hand side are
related by dc
$.
On the other hand, the following constraint is not safe because it has both p 3 (f-
are related by dc
$.
e:
The set of all possible safe constraints that can be derived by the above rule is as follows
when the higher priority task involved is
R 4
R 4
e:
(a) Maximum number of
preemptions of by preemptions of by
(b) Minimum number of
R
R
Fig. 4. Example of infeasible task phasing.
The other constraints for the cases where the higher priority task involved is - 2 or - 3 can
be derived similarly.
IV. Advanced Constraints on Task Phasing
Among the two problems with Lee et al.'s technique explained in the introduction, the
first problem was addressed in the previous section by introducing a scenario-sensitive
preemption cost. This section addresses the second problem, namely, the problem that
the technique does not consider phasing among tasks and thus may allow many infeasible
preemption scenarios. For example, the technique assumes that the number of preemptions
of a lower priority task where a higher priority task is involved can potentially range from
zero to the number of invocations of the higher priority task.
However, as Fig. 4-(a) illustrates, some of the invocations of a higher priority task (denoted
by - j in the figure) cannot be involved in any preemption of a lower priority task (denoted
by - k in the figure) even when we assume the worst case response time (denoted by R k
in the figure) for the lower priority task. Similarly, as Fig. 4-(b) illustrates, some of the
invocations of the higher priority task will inevitably be involved in preemptions of the lower
priority task even when we assume the best case response time B k for the lower priority
task. In this section, we incorporate these constraints and others about task phasing into
the framework developed in the previous section.
First, we define the following four numbers between two tasks - j and - k (j !
priorities are higher than that of - i for which the worst case response time R i is being
jk , and N 0
jk . Let I be the set of all intervals of length R i in the
hyperperiod formed by - j and - k , that is, in LCM(T least common multiple of
number M jk is the maximum number of preemptions of the lower priority
during which the higher priority task - j executes over all intervals in I. Similarly,
N jk is the minimum number of preemptions of the lower priority task - k during which the
higher priority task - j executes over the same set of intervals. On the other hand, M 0
jk is
the maximum number of times that instances of the lower priority task - k are overlapped
with an instance of the higher priority task - j . More technically, it is the maximum number
of level-k busy periods [24] that have both - j and - k over all intervals in I. Finally, N 0
jk is
the minimum number of times that instances of the lower priority task - k are overlapped
with an instance of the higher priority task - j , i.e., the minimum number of level-k busy
periods that have both - j and - k over all intervals in I.
Assume that the worst case response times of - j and - k are R j and R k , respectively, both
of which are available when we compute R i . Likewise, assume that the best case response
times of - j and - k are B j and B k , respectively, for which the best case execution times of
can be used. Then, the above four numbers are given as follows:
d
where d
min x=1
d
d y
where d
where d
min x=1
d d y
where d
The derivation of the above is lengthy and is not presented here. Interested readers are
referred to an extended version of this paper [25].
The first two numbers, M jk and N jk , can be used to bound the number of preemptions of
The other two numbers, M 0
jk and N 0
jk , can be used to bound the number of preemptions of
certain types. First, M 0
jk can be used to bound the number of preemptions in which both
execute (of course, without being multiply counted using the technique explained
in the previous section). On the other hand, N
jk can be used to bound the number of
preemptions in which either only - j or only - k executes. For example, the number of
preemptions in which - j executes but - k does not is bounded by d R i
jk . Likewise, the
number of preemptions in which - k executes but - j does not is bounded by d
jk .
In the following, we give examples of constraints that use M 0
jk and N 0
jk . Assume that there
are four tasks - 1 , - 2 , - 3 , and - 4 and that - 1 and - 2 correspond to - j and - k in the above
constraints, respectively.
In our example, there are ten possible preemption scenarios of - 3 and
Among them, there are three preemption scenarios during which both - 1 and - 2 execute:
are related
by dc
and thus are subject to being multiply counted, only one of them can participate
in the summation of the number of preemptions. This restriction leads to the following two
inequalities:
Similarly, there are three preemption scenarios during which - 1 executes but - 2 does not:
are related by dc
$, we
have the following two inequalities:
Finally, there are three preemption scenarios during which - 2 executes but - 1 does not:
are related by dc
$, we
have the following two inequalities:
V. Optimization Based on Task Set Decomposition
One potential problem of the proposed technique is that it requires a large amount of
computation when there are a large number of tasks since the number of variables used
is O(2 n ) where n is the number of tasks in the task set. This section discusses a simple
optimization based on task set decomposition that can drastically reduce the amount of
Fig. 5. Example of task decomposition.
computation required.
Consider the example in Fig. 5 that shows the cache blocks used by four tasks
and - 4 . In the figure, we notice that although cache blocks are shared between - 1 and - 2
and also between - 3 and - 4 , there is no overlap between the cache blocks used by - 1 and - 2
and those used by - 3 and - 4 . This means that neither - 1 nor - 2 affects the cache-related
preemption delay of either - 3 or - 4 , and vice versa. Based on this observation, we can
decompose a given task set into a collection of subsets in such a way that no two tasks
from two different subsets share a cache block between them. Then the tasks in each subset
can be analyzed independently of tasks in other subsets using the constraints given in the
previous two sections.
For our example in Fig. 5, the given task set is decomposed into two subsets: and
g. When we calculate the worst case response time of the lowest priority task - 4 using
the iterative procedure explained in Section II, the tasks in one subset can be analyzed
independently of the tasks in the other subset and the two results can be combined as
follows:
R k+1
(R k
(R k
(R k
4 ) is the cache-related preemption delay of - 4 due to the interactions between
shared cache blocks and is computed from maximizeX
with constraints involving only - 1 and - 2 . Similarly, PC 2
(R k
4 ) is the cache-related preemption
delay of - 4 due to the interactions between - 3 and - 4 and is computed from maximizeX
with the constraints that involve only - 3 and - 4 .
To maximize the benefit of the optimization explained above, the number of subsets that
can be analyzed independently should be large. An interesting topic for future research is
to devise a scheme that allocates main memory to tasks so that the resulting cache mapping
gives a large number of such subsets.
VI. Experimental Results
In this section, we compare the worst case response time prediction by the proposed technique
with those by previous techniques using a sample task set. Our target machine is
an IDT7RS383 board that has a 20 MHz R3000 RISC CPU, R3010 FPA (Floating Point
Accelerator), and an instruction cache and a data cache of 16 Kbytes each. Both caches are
direct mapped and have block sizes of 4 bytes. SRAM (static RAM) is used as the target
machine's main memory and the cache refill time is 4 cycles.


I
Task set specification.
Task Period WCET
(unit: cycles)
In our experiment, we used a sample task set whose specification is given in TABLE I.
In the table, the first column lists the tasks in the task set. Four tasks were used in our
experiments: FFT, LUD, LMS, and FIR. The FFT task performs the FFT and inverse FFT
operations on an array of 8 floating point numbers using the Cooley-Tukey algorithm [26].
simultaneous linear equations by the Doolittle's method of LU decomposition
[27] and FIR implements a 35 point Finite Impulse Response (FIR) filter [28] on a
generated signal. Finally, LMS is a 21 point adaptive FIR filter where the filter coefficients
are updated on each input signal [28].
The table also gives the period and WCET of each task in the second and third columns,
respectively. Since our target machine uses SRAM as its main memory, its cache refill time
(4 cycles) is much smaller than those of most current computer systems, which range from
8 cycles to more than 100 cycles when DRAM is used as main memory [11]. To obtain
the WCET of each task for more realistic cache refill times, we divide the WCET into
two components. The first component is the execution time of the task when all memory
references are cache hits, and is independent of the cache refill time. It was measured from
our target machine by executing the task with its code and data pre-loaded in the cache.
The second component is the time needed to service cache misses that occur during the
task's execution and is dependent on the cache refill time. This component is computed
by multiplying the total number of cache misses and the cache refill time t ref ill . In our
experiment, the total number of cache misses was obtained by the following procedure:
1. Two different execution times were measured for each task: one with its code and data
pre-loaded in the cache and the other without such pre-loading, which are denoted by
2. By dividing the difference between T 1 and T 2 by the 4 cycle cache refill time of the
target machine, we computed the total number of cache misses during the task's
execution.
We used three different cache mappings for the code used by the four tasks as shown in
LUD LMS
FFT
cache mapping 1 cache mapping 2 cache mapping 3
Fig. 6. Three different cache mappings of tasks.
Fig. 6. In the first mapping, the code used by each task is mapped to the same cache
region. On the other hand, in the second mapping, the cache regions used by the tasks
are overlapped with each other by about 70%. Finally, in the third mapping, the code
used by each task is mapped into a disjoint region in the cache. We speculate that these
three mappings represent reasonably well the spectrum of possible overlap among the cache
regions used by tasks.


II gives the preemption cost tables for the three mappings. Note that the preemption
costs of the tasks decrease as the overlapping cache regions decrease. This is because
less useful cache blocks are displaced during preemption, and eventually when the cache
regions are disjoint, all the preemption costs are zero.
We used a public-domain linear programming tool called lp solve by Michel Berkelaar
(URL: ftp://ftp.es.ele.tue.nl/pub/lp solve) to solve the linear programming problem
posed by the proposed technique. The total number of constraints for our task set is
and it took less than 3 minutes of user CPU time and 5 minutes of system CPU time to
compute all the data points presented in this section for the proposed technique on a Axil


II
Preemption cost tables for the three cache mappings.
Preemption cost table for cache mapping 1
(unit: cycles)
Preemption cost table for cache mapping 2
(unit: cycles)
Preemption cost table for cache mapping 3
(unit: cycles)
workstation running SunOS 5.4 with a 50 MHz SuperSparc CPU (TI TMS390Z80) and
128 Mbyte main memory.
For our experiments, we also implemented a simple fixed-priority scheduler based on the
tick scheduling explained in [7]. In our implementation, the scheduler is invoked every
160,000 cycles. To take into account the overhead associated with the scheduler, we used
the analysis technique explained in [7]. In this technique, the scheduler overhead S i during
response time R i is given by
where
is the number of scheduler invocations during R i ,
is the number of times that the scheduler moves a task from the delay queue
(where tasks wait for their next invocations) to the run queue during R i ,
ffl C int is the time needed to service a timer interrupt (it measured 413 cycles in our
target machine),
ffl C ql is the time needed to move the first task from the delay queue to the run queue
(it measured 142 cycles in our target machine),
ffl C qs is the time needed to move each additional task from the delay queue to the run
queue (it measured 132 cycles in our target machine).
A detailed explanation of this equation is beyond the scope of this paper and interested
readers are referred to [7].
Fig.s 7-(a) and (b) show the predicted worst case response time of the lowest priority task
- 4 and the percentage of cache-related preemption delay in the worst case response time,
respectively, as the cache refill time increases from 4 cycles to 200 cycles. Three different
techniques were used to predict the worst case response time. First, M is the technique
proposed in this paper, and M 1 , M 2 , and M 3 are its predictions for the three different
cache mappings explained earlier. Second, C is the technique explained in [17] that assumes
that each cache block used by a preempting task replaces from the cache a memory block
needed by a preempted task. Finally, P is Lee et al.'s technique presented in [18] where
the preemption cost is assumed to be the time needed to reload all the useful cache blocks.
Note that unlike the proposed technique, the worst case response time predictions by C
and P are insensitive to cache mapping since the preemption costs assumed by them are
independent of cache mapping.
Cache Refill Time10000000Worst
Case
Response
Time
M3
(a)
Cache Refill Time0.5(Cache-related
Preemption
(Worst
Case
Response
M3
(b)
Fig. 7. Worst case response time and (cache-related preemption delay)/(worst case response
time) vs. cache refill time.
The results in Fig. 7-(a) show that the proposed technique gives significantly tighter prediction
of the worst case response time than the previous techniques. For example, when the
cache refill time is 100 cycles and the second cache mapping is used, the proposed technique
gives a worst case response time prediction that is 60% tighter than the best of the previous
approaches (5,323,620 cycles in M 2 vs. 13,411,402 cycles in P ). This superior performance
of the proposed technique becomes more evident as the cache regions used by the tasks
become less overlapped, that is, as we move from M 1 to M 3 .
In Fig. 7-(a), there are a few jumps in the worst case response time predictions of all the
three techniques. These jumps occur when increase in the worst case response time due to
increased cache refill time causes additional invocations of higher priority tasks resulting in
a number of bumps in Fig. 7-(b).
The results in Fig. 7-(a) also show that as the cache refill time increases, the gap increases
between the worst case response time prediction by M and those by the other two tech-
Cache mapping 1 Cache mapping 2 Cache mapping 36000000Worst
Case
Response
Time
cache refill
(a)
Cache mapping 1 Cache mapping 2 Cache mapping 36000000Worst
Case
Response
Time
cache refill
(b)
Fig. 8. Impact of the different constraint groups on the accuracy of the worst case response
time prediction.
niques. Eventually, the task set is deemed unschedulable by C and P when the cache
refill time is more than 90 and 100 cycles, respectively. On the other hand, the task set is
schedulable by M even when the cache refill time is more than 200 cycles if cache mapping
3 is used.
Finally, the results in Fig. 7-(b) show that as the cache refill time increases, the cache-related
preemption delay takes a proportionally large percentage in the worst case response time.
As a result, even for method M , the cache-related preemption delay takes more than 30%
of the worst case response time when the cache refill time is 100 cycles and cache mapping 2
is used. This indicates that accurate prediction of cache-related preemption delay becomes
increasingly important as the cache refill time increases, that is, if the current trend of
widening speed gap between the processor and main memory continues [11].
To assess the impact of the various constraints used in the proposed technique on the
accuracy of the resultant worst case response time prediction, we classified the constraints
into two groups and calculated the reduction of the worst case response time prediction by
each group. The constraint sets were classified as follows: the three constraints in Section III
that deal with scenario-sensitive preemption cost were classified as Group 1 whereas those
in Section IV that eliminate infeasible task phasing were classified as Group 2.
Figs. 8-(a) and (b) show the reduction of the worst case response time prediction as the two
constraint groups are applied for cache refill times of 60 cycles and 80 cycles, respectively.
For comparison purposes, we also give the worst case response time prediction by technique
. The results show that for both cache refill times when the cache regions used by the
tasks are completely overlapped (i.e., cache mapping 1), most of the reduction comes from
the constraints in Group 2 since in this case scenario-sensitive preemption cost degenerates
to the preemption cost used by technique P . However, as the cache regions used by the
tasks become less overlapped, the impact of the constraints in Group 1 becomes more
significant and eventually when the cache regions are disjoint, all the reduction comes from
the constraints in Group 1 alone since in this case all the scenario-sensitive preemption
costs are zero.
We performed experiments using a number of other task sets and the results were very
similar to those given in this section. Interested readers are referred to [25] where the
results for the other task sets are presented.
VII. Conclusion
In this paper, we have proposed an enhanced schedulability analysis technique for analyzing
the cache-related preemption delay, which is required if cache memory is to be used in multitasking
real-time systems. The proposed technique uses linear programming and has the
following two novel features expressed in terms of constraints in linear programming. First,
the technique takes into account the relationship between a preempted task and the set of
tasks that execute during the preemption when calculating the number of memory blocks
that should be reloaded into the cache after the preempted task resumes execution. Second,
the technique considers phasing of tasks to eliminate many infeasible task interactions.
Our experimental results showed that the incorporation of the two features yields up to
60% more accurate prediction of the worst case response time when compared with the
prediction made by previous techniques. The results also showed that as the cache refill
time increases, the gap increases between the worst case response time prediction by the
proposed technique and those by the previous techniques. Finally, the results showed that
as the cache refill time increases, the cache-related preemption delay takes a proportionally
large percentage in the worst case response time, which indicates that accurate prediction
of cache-related preemption delay becomes increasingly important if the current trend of
widening speed gap between the processor and main memory continues.

Acknowledgments

The authors are grateful to Sam H. Noh for helpful suggestions and comments on an earlier
version of this paper.



--R

"Some Results of the Earliest Deadline Scheduling Al- gorithm,"
"Finding Response Times in a Real-Time System,"
"The Rate Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behavior,"
"Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment,"
"Dynamic Scheduling of Hard Real-Time Tasks and Real-Time Threads,"
"An Extendible Approach for Analyzing Fixed Priority Hard Real-Time Tasks,"
"Effective Analysis for Engineering Real-Time Fixed Priority Schedulers,"
"The Impact of an Ada Run-time System's Performance Characteristics on Scheduling Models,"
"Accounting for Interrupt Handling Costs in Dynamic Priority Task Systems,"
"Engineering and Analysis of Fixed Priority Schedulers,"
Computer Architecture A Quantitative Approach.
"SMART (Strategic Memory Allocation for Real-Time) Cache Design,"
"OS-Controlled Cache Predictability for Real-Time Systems."
"Compiler Support for Software-based Cache Partitioning,"
"Software-Based Cache Partitioning for Real-time Applications,"
"Cache Issues in Real-Time Systems,"
"Adding Instruction Cache Effect to Schedulability Analysis of Preemptive Real-Time Systems,"
"Analysis of Cache-related Preemption Delay in Fixed-priority Preemptive Scheduling,"

"Efficient Microarchitecture Modeling and Path Analysis for Real-Time Software,"
"A Method for Bounding the Effect of DMA I/O Interference on Program Execution Time,"
"A Framework for Implementing Objects and Scheduling Tasks in Lock-Free Real-Time Systems,"
Science Research Associates
"Fixed Priority Scheduling of Periodic Task Sets with Arbitrary Dead- lines,"
"Bounding Cache-related Preemption Delay for Real-time Systems,"
DFT/FFT and Convolution Algorithm: Theory
Elementary Numerical Analysis.
C Algorithms for Real-Time DSP
--TR
Compilers: principles, techniques, and tools
Some Results of the Earliest Deadline Scheduling Algorithm
Dynamic Scheduling of Hard Real-Time Tasks and Real-Time Threads
An extendible approach for analyzing fixed priority hard real-time tasks
C language algorithms for real-time DSP
Compiler support for software-based cache partitioning
Analysis of Cache-Related Preemption Delay in Fixed-Priority Preemptive Scheduling
Computer architecture (2nd ed.)
Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
Elementary Numerical Analysis
Engineering and Analysis of Fixed Priority Schedulers
Effective Analysis for Engineering Real-Time Fixed Priority Schedulers
The Impact of an Ada Run-Time System''s Performance Characteristics on Scheduling Models
Adding instruction cache effect to schedulability analysis of preemptive real-time systems
OS-Controlled Cache Predictability for Real-Time Systems
Efficient microarchitecture modeling and path analysis for real-time software
Analysis of cache-related preemption delay in fixed-priority preemptive scheduling
A Method for Bounding the Effect of DMA I/O Interference on Program Execution Time
A framework for implementing objects and scheduling tasks in lock-free real-time systems

--CTR
Jaudelice C. de Oliveira , Caterina Scoglio , Ian F. Akyildiz , George Uhl, New preemption policies for DiffServ-aware traffic engineering to minimize rerouting in MPLS networks, IEEE/ACM Transactions on Networking (TON), v.12 n.4, p.733-745, August 2004
Accounting for cache-related preemption delay in dynamic priority schedulability analysis, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
Hemendra Singh Negi , Tulika Mitra , Abhik Roychoudhury, Accurate estimation of cache-related preemption delay, Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, October 01-03, 2003, Newport Beach, CA, USA
Jan Staschulat , Rolf Ernst, Scalable precision cache analysis for preemptive scheduling, ACM SIGPLAN Notices, v.40 n.7, July 2005
Chanik Park , Jaeyu Seo , Sunghwan Bae , Hyojun Kim , Shinhan Kim , Bumsoo Kim, A low-cost memory architecture with NAND XIP for mobile embedded systems, Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, October 01-03, 2003, Newport Beach, CA, USA
Jan Staschulat , Rolf Ernst, Multiple process execution in cache related preemption delay analysis, Proceedings of the 4th ACM international conference on Embedded software, September 27-29, 2004, Pisa, Italy
cache memory;fixed-priority scheduling;preemption;schedulability analysis;real-time system