Analysis of Cache-Related Preemption Delay in Fixed-Priority Preemptive Scheduling.
AbstractWe propose a technique for analyzing cache-related preemption delays of tasks that cause unpredictable variation in task execution time in the context of fixed-priority preemptive scheduling. The proposed technique consists of two steps. The first step performs a per-task analysis to estimate cache-related preemption cost for each execution point in a given task. The second step computes the worst case response time of each task that includes the cache-related preemption delay using a response time equation and a linear programming technique. This step takes as its input the preemption cost information of tasks obtained in the first step. This paper also compares the proposed approach with previous approaches. The results show that the proposed approach gives a prediction of the worst case cache-related preemption delay that is up to 60 percent tighter than those obtained from the previous approaches.
INTRODUCTION
In real-time systems, tasks have timing constraints that must be satisfied for correct op-
eration. To guarantee such timing constraints, extensive studies have been performed on
schedulability analysis [1, 2, 3, 4, 5, 6]. They, in many cases, make a number of assumptions
to simplify the analysis. One such simplifying assumption is that the cost of task preemption
is zero. In real systems, however, task preemption incurs additional 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 that
focus on practical issues related to task scheduling [7, 8, 9, 10].
However, in addition to the direct costs, task preemption introduces indirect costs due to
cache memory, which is used in almost all computing systems today. In computing 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 preempted task resumes its execution,
it spends a substantial amount of time to reload the cache with the previously displaced
memory blocks. Such cache reloading greatly increases the task execution time, which may
invalidate the result of schedulability analysis that overlooks the cache-related preemption
costs.
To rectify this problem, recent studies addressed the issue of incorporating cache-related
preemption costs into schedulability analysis [12, 13]. These studies assume that each cache
block used by a preempting task replaces from the cache a memory block that is needed by
a preempted task. This pessimistic assumption leads to a loose estimation of cache-related
preemption delay since the replaced memory block may not be useful to any preempted
task. For example, it is possible that the replaced memory block is one that is no longer
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 the unit
of blocks.
needed or one that will be replaced without being re-referenced even when there were no
preemptions.
In this paper, we propose a schedulability analysis technique that considers the usefulness
of cache blocks in computing cache-related preemption delay. The goal is to reduce the
prediction inaccuracy resulting from the above pessimistic assumption. The proposed technique
consists of two steps. In the first step, we perform a per-task analysis to compute
the number of useful cache blocks at each execution point in a given task, where a useful
cache block at an execution point is defined as a cache block that contains a memory block
that may be re-referenced before being replaced by another memory block. The number of
useful cache blocks at an execution point gives an upper bound on cache-related preemption
cost that is incurred when the task is preempted at that point. The results of this
per-task analysis are given in a table that specifies the (worst case) preemption cost for a
given number of preemptions of the task. From this table, the second step derives the worst
case response times of tasks using a linear programming technique [14] and the worst case
response time equation [2, 6].
This paper is organized as follows: In Section II, we survey the related work. Section III
describes our overall approach to schedulability analysis that considers cache-related pre-emption
cost. Sections IV and V detail the two steps of the proposed schedulability analysis
technique focusing on direct-mapped instruction cache memory. Section VI presents the
results of our experiments to assess the effectiveness of the proposed approach. Section VII
describes extensions of the proposed technique to set-associative cache memory and also to
data cache memory. Finally, we conclude this paper in Section VIII.
II. RELATED WORK
A. Schedulability Analysis in Fixed-priority Scheduling
A large number of schedulability analysis techniques have been proposed within the fixed-priority
scheduling framework [2, 3, 4, 6]. Liu and Layland [4] show that the rate monotonic
priority assignment where a task with a shorter period is given a higher priority is optimal
when task deadlines are equal to their periods. They also give the following sufficient
condition for schedulability for a task set consisting of n periodic tasks
where C i is a worst case execution time (WCET) estimate of - i and T i is its period 2 . This
condition states that if the total utilization of the task set (i.e.,
) is lower than the
given utilization bound (i.e., n (2 1=n \Gamma 1)), the task set is guaranteed to be schedulable
under the rate monotonic priority assignment. Later, Lehoczky et al. develop a necessary
and sufficient condition for schedulability based on utilization bounds [3].
Another approach to schedulability analysis is the worst case response time approach [2, 6].
The approach uses the following recurrence equation to compute the worst case response
where hp(i) is the set of tasks whose priorities are higher than that of - i . In the equation,
the term
j2hp(i) d R i
eC j is the total interferences from higher priority tasks during R i and
C i is - i 's own execution time. The equation can be solved iteratively and the iteration
terminates when R i converges at a value. This R i value is compared against - i 's deadline
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 a higher priority than -
to determine the schedulability of - i .
Recently, Katcher et al. [10] and Burns et al. [7, 8] provided a methodology for incorporating
the cost of preemption into schedulability analysis. In these approaches, preemption costs
arising from interrupt handling, task queue manipulation, and context-switching are taken
into account in the schedulability analysis.
In this paper, we are also interested in incorporating the cost of preemption into schedulability
analysis. However, unlike the above studies, our main focus is on indirect preemption
costs due to cache memory, which is increasingly being used in real-time computing systems.
B. Caches in Real-time Systems
Cache memory is used in almost all computing systems today to bridge the ever increasing
speed gap between the processor and main memory. However, due to its unpredictable per-
formance, cache memory has not been widely used in real-time computing systems where the
guaranteed worst case performance is of great importance. The unpredictable performance
comes from two sources: intra-task interference and inter-task interference.
interference occurs when a memory block of a task conflicts in the cache with
another block of the same task. Recently, there has been considerable progress on the
analysis of intra-task interference due to cache memory and interested readers are referred
to [15, 16, 17, 18, 19].
Inter-task interference, which is the main focus of this paper, occurs when memory blocks
of different tasks conflict with one another in the cache. There are two ways to address
the unpredictability resulting from inter-task interference. 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 [20, 21, 22, 23]. In these techniques, each task
is allowed to access only its own partitions and thus we need not consider inter-task in-
terference. There are two different approaches to cache partitioning: hardware-based and
software-based.
In hardware-based approaches, extra address-mapping hardware is placed between the
processor and cache memory to limit the cache access by each task to its own partitions
[20, 21, 22]. On the other hand, in software-based approaches a specialized compiler
and linker are used to map each task's code and data only to its assigned cache
partitions [23]. Cache partitioning improves the predictability of the system by removing
cache-related inter-task interference, but has a number of drawbacks. One common draw-back
of both the hardware and software-based approaches is that they require modification
of existing hardware or software. Another common drawback is that they limit the amount
of cache memory available to individual tasks. Finally, in the case of the hardware-based
approach, the extra address-mapping hardware may stretch the processor cycle time, which
affects the execution time of every instruction.
The other way to address the unpredictability resulting from inter-task interference is to
devise an efficient method for analyzing its timing effects. In [12], Basumallick and Nilsen
extend the rate monotonic analysis explained in the previous subsection to take into account
the inter-task interference. In this approach, the WCET estimate of a task - i is modified
as C 0
is the original WCET estimate of - i computed assuming that the
task executes without preemption and fl i is the worst case preemption cost that the task - i
might impose on preempted tasks. This modification is based on a pessimistic assumption
that each cache block used by a preempting task replaces from the cache a memory block
that is needed by a preempted task. In the approach, the total utilization of a given task set
computed from the modified WCET estimates is compared against the utilization bound
given by Equation (1) to determine the schedulability of the task set.
One drawback of this approach is that it suffers from a pessimistic utilization bound given
by Equation (1), which approaches 0.693 for a large n [4]. Many task sets that have total
utilization higher than this bound can be successfully scheduled by the rate monotonic
priority assignment [3]. To rectify this problem, Busquets-Mataix et al. in [13] propose a
technique based on the response time approach. This technique makes the same pessimistic
assumption that each cache block used by a preempting task replaces from the cache a
memory block that is needed by a preempted task. This assumption leads to the following
equation for computing the worst case response time of a task:
d
e \Theta (C j
is the cache-related preemption cost that task - j might impose on lower priority
tasks. The term fl j is computed by multiplying the number of cache blocks used by task - j
and the time needed to refill a cache block.
Both the utilization bound based and response time based approaches assume that each
cache block used by a preempting task replaces from the cache a memory block that is
needed by a preempted task. This pessimistic assumption leads to a loose estimation of
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
the lower priority task is executed without preemption.
III. OVERALL APPROACH
This section overviews our proposed schedulability analysis technique that aims to minimize
the overestimation of cache-related preemption delay due to the pessimistic assumption
explained in the previous section. For this purpose, the response time equation is augmented
as follows in the proposed
d
where PC i (R i ) is the total cache-related preemption delay of task - i during R i , i.e., the
total cache reloading times of - 1 during R i .
22 t 2231
Fig. 1. Example of PC i (R i ).
The meaning of PC i (R i ) can be best explained by an example such as the one given in

Figure

1. In the example, there are three tasks,
Each arrow in the figure denotes a
point where a task is preempted and each shaded rectangle denotes cache reloading after
the corresponding task resumes execution. With these settings, PC 3 (R 3 ), which is the total
cache-related preemption delay of task - 3 during R 3 , is the total sum of cache reloading
times of - 1 , - 2 and - 3 during R 3 , which corresponds to the sum of shaded rectangles in the
figure.
The augmented response time equation can be solved iteratively as follows.
d
(R 0
. (4)
R k+1
(R k
As before, this iterative procedure terminates when R m
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, we take the following two-step approach.
1. Per-task analysis: We statically analyze each task to determine the cache-related
preemption cost at each execution point. This is the cost the task pays when it is
preempted at the execution point and is upper-bounded by the number of useful cache
blocks at that execution point. Based on this information and information about the
worst case visit counts of execution points, we construct the following preemption cost
table for each task.
# of preemptions 1
cost
In the table, f k is the k-th marginal preemption cost that is the cost the task pays in
the worst case for its k-th preemption over the preemption.
2. Preemption delay analysis: We use a linear programming technique to compute
(R k
i ) from the preemption cost tables of tasks and a set of constraints on the
number of preemptions of a task by higher priority tasks.
The following two sections detail the two steps.
IV. PER-TASK ANALYSIS OF USEFUL CACHE BLOCKS
In this section, we describe a per-task analysis technique to obtain the preemption cost table
of each task. We initially focus on the case of direct-mapped 3 instruction cache memory
in this section. In Section VII, we discuss extensions for set-associative cache memory and
also for data cache memory.
As an example of cache-related preemption cost, consider a direct-mapped cache with four
cache blocks. Assume that the cache has m 3 at time t in cache blocks c 0 ,
Further assume that the following memory block references are
made after t.
3 In a direct-mapped cache, each memory block can be placed exactly in one cache block whose index is
given by memory block number modulo number of blocks in the cache.
In this example, the useful cache blocks at time t are cache blocks c 1 and c 2 since they contain
memory blocks m 5 and m 6 , respectively, that are re-referenced before being replaced.
On the other hand, cache blocks c 0 and c 3 are not useful at time t since they have m 0 and
3 that are replaced by m 4 and m 7 without being re-referenced. If a preemption occurs at
time t, the memory blocks m 5 and m 6 contained in cache blocks c 1 and c 2 may be replaced
by memory blocks of intervening tasks and thus need to be reloaded into the cache after
resumption. The additional time to reload these useful cache blocks is the cache-related
preemption cost at time t. Note that this additional cache reload time is not needed if the
task is not preempted. In the following, we explain a technique for estimating the number
of useful cache blocks at any point in a program.
A. Estimation of the Number of Useful Cache Blocks
Our technique for estimating the number of useful cache blocks is based on data flow
analysis [24] over the task's program expressed in the control flow graph 4 (CFG). To give
4 In a CFG, each node represents a basic block, while edges represent potential flow of control between
basic blocks [25]
in
{ } m x
{ }
m a
{ }
(b) cache state at p
Useful
Useful cache block j
cache block i
(a) control flow to and from p
{ }
Fig. 2. Analysis on the usefulness of cache blocks.
an intuitive idea about this data flow analysis, consider the CFG given in Figure 2. In the
figure, a pair (c; m) denotes a reference to memory block m that is mapped to cache block
c. The CFG has two incoming paths to the execution point p, i.e., in 1 and in 2 , and two
outgoing paths from p, i.e., out 1 and out 2 . If the control flow came through incoming path
in 1 , cache block c i would contain memory block m a at point p since m a is the last reference
to cache block c i before reaching p. Similarly, cache block c i would have memory block m b
at point p if the control has come through the incoming path in 2 . Thus, either m a or m b
may reside in cache block c i at p depending on the incoming path. If either of them is the
first reference to cache block c i in an outgoing path from p, the cache block may be reused
and thus is defined as being useful at point p. The outgoing path out 2 is such a path and
thus cache block c i is defined to be useful at p.
For a more formal description, we define reaching memory blocks (RMBs) and live memory
blocks (LMBs) for each cache block that are similar to reaching definitions and live variables
used in traditional data flow analysis [24]. The set of reaching memory blocks of cache block
c at point p, denoted by RMB c
, contains all possible states of cache block c at point p where
a possible state corresponds to a memory block that may reside in the cache block at the
point. For a memory block to reside in cache block c, first, it should be mapped to cache
block c. Furthermore, it should be the last reference to the cache block in some execution
path reaching p. The set of live memory blocks of cache block c at point p, denoted by
p , is defined similarly and is the set of memory blocks that may be the first reference
to cache block c after p.
With these definitions, a useful cache block at point p can be defined as a cache block
whose RMBs and LMBs have at least one common memory block. In Figure 2, RMB c i
is fm a ; m b g and LMB c i
p is fm a g. Thus, cache block c i is defined to be useful at point p.
In the following, we explain how to compute RMBs of cache blocks at various execution
points of a given program. We initially focus on RMBs at the beginning and end points
of basic blocks 5 . The RMBs at other points can easily be derived from the RMBs at the
basic block boundaries as we will see later.
To formulate the problem of computing RMBs as a data flow problem, we define a set
gen c [B]. This set is either null or contains a single memory block. It is null if basic block
does not have any reference to memory blocks mapped to cache block c. On the other hand,
if the basic block B has at least one reference to a memory block mapped to c, gen c [B]
contains as its unique element the memory block that is the last reference to the cache
block c in the basic block. Note that in the latter case the memory block in gen c [B] is the
one that will reside in the cache block c at the end of the basic block B. Also note that
gen c [B] defined in this manner can be computed locally for each basic block.
As an example, consider the CFG given in Figure 3. The CFG shows instruction memory
block references made in each basic block. Assuming that the instruction cache is direct
mapped and has two blocks, gen c 0 [B 1 ] is fm 2 g since m 2 is the memory block whose reference
is the last reference to c 0 in B 1 . The gen c [B] sets for other basic blocks and cache blocks
can be computed similarly and are given in Figure 3.
With gen c [B] defined in this manner, the RMBs of c just before the beginning of B and
just after the end of B, which are denoted by RMB c
IN [B] and RMB c
OUT [B], respectively,
can be computed from the following two equations.
P a predecessor of B
OUT [B] (5)
gen c [B] if gen c [B] is not null
IN [B] otherwise
The first equation states the memory blocks that reach the beginning of a basic block
can be derived from those that reach the ends of the predecessors of B. The second equa-
5 A basic block is a sequence of consecutive instructions in which flow of control enters at the beginning
and leaves at the end without halt or possibility of branching except at the end [24].
{ }3
c }
{
{ }4
{ }c 1 3
{ }
{ }10 }
c }
Fig. 3. Example of gen c [B].
tion states that RMB c
OUT [B] is equal to gen c [B] if gen c [B] is not null and RMB c
IN [B]
otherwise 6 . These data flow equations can be solved using a well-known iterative approach
[24]. It starts with RMB c
and iteratively converges to the desired values of RMB c
IN 's and RMB c
OUT 's. The iterative
process can be described procedurally as follows.
Algorithm 1: Find RMBs of cache blocks at the beginning and end of each basic block
assuming that gen c [B] has been computed for each basic block B and cache block c.
/* initialize RMB c
IN [B] and RMB c
OUT for all B's and c's */
for each basic block B do
for each cache block c do
begin
6 This equation can be rewritten as
where set kill c [B] is the set of reaching memory blocks of cache block c killed in basic block B. The set
kill c [B] is obtained as follows: (1) it is null if gen c [B] is null, and (2) it is Mc \Gamma gen c [B] if gen c [B] is not
null where Mc is the set of all memory blocks mapped to c in the program. This rewritten form is more
commonly used in traditional data flow analysis.
IN [B] := ;;
OUT [B] := gen c [B];
change := true;
while change do
begin
change := false;
for each basic block B do
for each cache block c do
begin
IN [B] :=
P a predecessor of B
OUT [P ];
oldout := RMB c
OUT [B];
OUT [B] := gen c [B]
else RMB c
OUT [B] := RMB c
IN [B]
if RMB c
OUT [B] 6= oldout then change := true
As we indicated earlier, the RMBs at other points within a basic block can be computed
from the RMBs at the beginning of the basic block. Assume that the basic block has the
following sequence of instruction memory block references.
The references are processed sequentially starting from (c clear that
1 is in cache block c 1 at the point following the reference. No other conflicting memory
blocks can be in c 1 at this point. Therefore, the RMBs of c 1 just after the reference
is simply fm 1 g. However, the RMBs of other cache blocks are the same as those just before
IN [B]. In general, the RMBs of c i after
those of other cache blocks are the same as those before (c
The problem of computing LMBs can be formulated similarly to the case of RMBs. The
difference is that the LMB problem is a backward data flow problem [24] in that the in sets
(i.e., LMB c
IN [B]) are computed from the out sets (i.e., LMB c
OUT [B]) whereas the RMB
problem is a forward data flow problem [24] in that the out sets (i.e., RMB c
OUT [B]) are
computed from the in sets (i.e., RMB c
IN [B]). In the LMB problem, the set gen c [B] is
either a set with only one element corresponding to the memory block whose reference is
the first reference to cache block c in basic block B, or null if none of the references from
B are to memory blocks mapped to c.
Using gen c [B] defined in this manner, the following two equations relate the LMB c
IN [B]
and LMB c
OUT [B].
S a successor of B
IN [S]
IN [B] (6)
gen c [B] if gen c [B] is not null
OUT [B] otherwise
An iterative algorithm similar to the one for computing RMBs can be used to solve this
backward data flow problem. The difference is that the algorithm starts with LMB c
all B's and c's and uses the above two equations instead
of those given in Equation (5).
After we compute LMBs at the beginning and end of each basic block, the LMBs at
other points can be computed analogously to the case of RMBs. The difference is that
the processing of references is backward starting from the end of the basic block rather
than forward starting from the beginning. In the LMB problem, the LMBs of c i before
a reference and those of other cache blocks are the same as those after
After the usefulness of each cache block is determined at each point by computing the
intersection of the cache block's RMBs and LMBs at the point, it is trivial to calculate
the total number of useful cache blocks at the point; we simply have to count the useful
cache blocks at that point. By multiplying this total number of useful cache blocks and the
time to refill a cache block, the worst case cache-related preemption cost at the point can
be computed.
B. Derivation of the Preemption Cost Table
This subsection explains how to construct the preemption cost table of a task whose k-th
entry is the cost the task pays in the worst case for its k-th preemption over the
th preemption. The preemption cost table is constructed from two types of information:
(1) the preemption cost at each point, and (2) the worst case visit count of each point,
which can be directly derived from the CFG of the given program and the loop bound of
each loop in the program. The construction assumes the worst case preemption scenario
since we cannot predict, in advance, where preemptions will actually occur. The worst
case preemption scenario occurs when the first preemption is at the point with the largest
preemption cost (i.e., the point with the largest number of useful cache blocks), and then
the second preemption at the point with the next largest preemption cost, and so on. This
worst case preemption scenario should be assumed for our analysis to be safe.
From the above worst case preemption scenario, the entries of the preemption cost table
are filled in as follows. First, we pick a point p 1 that has the largest preemption cost. We
then fill in the first entry up to the v p 1
-th entry with that preemption cost where v p 1
is
the worst case visit count of p 1 . After that, we pick the point that has the second largest
preemption cost and perform the same steps starting from the (v p 1
1)-th entry. This
process is repeated until the number of entries in the preemption cost table is exhausted.
Assuming that the number of entries in the table is K, the K 0 -th marginal preemption
cost, where K 0 ? K, can be conservatively estimated to be the same as the K-th marginal
preemption cost since the marginal preemption cost is non-increasing.
By applying the per-task analysis explained in this section to all the tasks in the task set,
we can obtain the following set of preemption cost tables, one for each task, where f i;j is
the j-th marginal preemption cost of - i .
# of preemptions 1
cost f 1;1 f 1;2 f 1;3
# of preemptions 1
cost f 2;1 f 2;2 f 2;3
# of preemptions 1
cost f 3;1 f 3;2 f 3;3
# of preemptions 1
cost f n;1 f n;2 f n;3
V. CALCULATION OF THE WORST CASE
PREEMPTION DELAYS OF TASKS
In this section, we explain how to compute a safe upper bound of PC i (R k
used in Equation
(4) in Section III from the preemption cost table. We formulate this problem as an
integer linear programming problem with a set of constraints.
We first define g j;l as the number of invocations of - j that are preempted at least l times
during a given response time R k
. As an example, consider Figure 4 where task - j is invoked
three times during the given R k
. The first invocation of task - j , i.e., - j1 , is preempted
three times, and both the second and third invocations of - j , i.e., - j2 , - j3 , are preempted
once. From the definition of g j;l , g j;1 is 3, g j;2 is 1, and g j;3 is 1. Note that since the highest
priority task - 1 cannot be preempted,
Fig. 4. Definition of g j;l .
If we assume that we know the g j;l values that give the worst case preemption scenario
among tasks, we can calculate the worst case cache-related preemption delay of - i during
(R k
(R k
where f j;l is the l-th marginal preemption cost of - j . Note that this total cache-related
preemption delay of - i includes all the delay due to the preemptions of - i and those of
higher priority tasks during R k
In general, however, we cannot determine exactly which g j;l combination will give the worst
case preemption delay to task - i . For our analysis to be safe, we should conservatively
assume a scenario that is guaranteed to be worse than any actual preemption scenario.
Such a conservative scenario can be derived from constraints that any valid g j;l combination
should satisfy. We give a number of such constraints on g j;l 's in the following. First, g j;l
for a given interval R k
i cannot be larger than the number of invocations of - j during that
interval. Thus, we have
In the formulation, N j is the maximum number of preemptions that a single invocation of
experience during R k
. An upper bound of such an N j value can be calculated as
a=1 d R j
a=1 d R k
are the worst case response times of higher priority tasks -
which should be available when the worst case response time of - i is computed. From this,
the index l of g j;l can be bounded by N j in the formulation.
Second, the number of preemptions of task - j during the given interval R k
i cannot be larger
than the total number of invocations of - during that interval since only the
arrivals of tasks with priorities higher than that of - j can preempt - j . Thus, we have
T a
More generally, the total number of preemptions of - during the given interval R k
cannot be larger than the total number of invocations of - during that interval.
Thus, we have
Na
T a
Note that this constraint subsumes the previous constraint.
The maximum value of PC i (R k
's satisfying the above constraints is a safe upper
bound on the total cache-related preemption delay of task - i during R k
i . This problem can
be formulated as an integer linear programming problem as follows:
maximize
(R k
subject to
Constraint 1
Constraint 2
Na
T a
At each iteration of the iterative procedure explained in Section III, this integer linear
programming problem is solved to compute the PC i (R k
application of this
iterative procedure is given in the Appendix.
VI. EXPERIMENTAL RESULTS
To assess the effectiveness of the proposed approach, we predicted the worst case response
times of tasks from sample task sets using the proposed technique and compared them with
those predicted using previous approaches. For validation purposes, the predicted worst
case response times were also compared with measured response times.
Our target machine is an IDT7RS383 board with 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. Although the
target machine has a timer chip that provides user-programmable timers, their resolution is
too low for our measurement purposes. To accurately measure the execution and response
times of tasks, we built a daughter board that implements a timer with a resolution of one
machine cycle.
For our experiments, we also implemented a simple fixed-priority scheduler based on the
tick scheduling explained in [7]. The scheduler manages two queues: run queue and delay
queue. The run queue maintains tasks that are ready to run and its tasks are ordered by
their priorities. The delay queue maintains tasks that are waiting for their next periods and
its tasks are ordered by their release times. The scheduler is invoked by timer interrupts
that occur every 160,000 machine cycles. When invoked the scheduler scans the delay
queue and all the tasks in the delay queue with release times at or before the invocation
time of the scheduler are moved to the run queue. If one of the newly moved tasks has a
higher priority than the currently running task, the scheduler performs a context switch
between the currently running task and the highest priority task. When a task completes its
execution, it is placed into the delay queue and the next highest priority task is dispatched
from the run queue.
To take into account the overheads 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
to the run queue during R i .
ffl C int is the time needed to service a timer interrupt (413 machine cycles in our exper-
iments).
set Task Period WCET # instruction # useful
memory blocks cache blocks
(unit: machine cycles) (unit: blocks)


I
Task set specifications.
ffl C ql is the time needed to move the first task from the delay queue to the run queue
(142 machine cycles in our experiments).
ffl C qs is the time needed to move each additional task from the delay queue to the run
queue (132 machine cycles in our experiments).
A detailed explanation of this equation is beyond the scope of this paper and interested
readers are referred to [7].
We used three sample task sets in our experiments and their specifications are given in

Table

I. The first column of the table is the task set name and the second column lists
the tasks in the task set. Four different tasks were used: FFT, LUD, LMS, and FIR. The
task FFT performs the FFT and the inverse FFT operations on an array of 8 floating
point numbers using the Cooley-Tukey algorithm [26]. LUD solves 10 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].
FIRData Section
mapped to
non-cacheable
area
LMS
FFT
LUD
Instruction cache
Memory
Scheduler Scheduler
Fig. 5. Code placement for task set T 3
The table also gives in the third and fourth columns the period and the WCET of each
task in the task set, respectively. We used the measured execution times of tasks as their
WCETs since tight prediction of tasks' WCETs and accurate estimation of cache-related
preemption delay are two orthogonal issues. The measured execution time of a task was
obtained by executing the task without preemption. This execution time includes the time
for initializing the task and also the time for two context switches: one context switch to
the task itself and the other from the task to another task upon completion. The table also
gives the total number of instruction memory blocks and the maximum number of useful
cache blocks of each task in the fifth and sixth columns, respectively.
In the experiments, we intentionally placed code for tasks in such a way that caused conflicts
among memory blocks from different tasks although the instruction cache in the target
machine is large enough to hold all the code used by the tasks. This is because we expect
that such a case is typical of large-scale real-time systems. Figure 5 shows such a code
placement for task set T 3 . Furthermore, since we consider the preemption delay related to
instruction caching only (cf. Section VII), we disabled data caching by mapping data and
4,449,284 1,365,026 3,113,858 29,600 3,113,778 29,520 3,104,178 19,920 3,073,229
(unit: machine cycles)


II
Worst case response time predictions and measured response times.
stack segments of tasks to non-cacheable area.

Table

II shows the predicted worst case response time of the lowest priority task in each
task set. Four different methods were used to predict the worst case response time of the
task: A is the method where the worst case preemption cost is assumed to be the cost to
completely refill the cache. C is the method explained in [13]. U is the method where the
worst case preemption cost is assumed to be the cost to completely reload the code used
by a preempted task. Finally, P is the method proposed in this paper where the worst case
preemption cost is assumed to be the cost to reload the maximum number of useful cache
blocks.
In the table, the worst case response time predictions by the above four methods are denoted
by RA , RC , RU , R P , respectively. Also denoted by \Delta M is the predicted worst case cache-related
preemption delay in method M. It is the difference between the worst case response
time predictions by method M with and without cache-related preemption costs.
The results show that the proposed technique gives significantly tighter predictions for
cache-related preemption delay than the previous approaches. This results from the fact
that, unlike the other approaches, the proposed approach considers only useful cache blocks
when computing cache-related preemption costs. In one case (task set T 1 ), the proposed
technique gives a prediction that is 60% tighter than the best of the previous approaches
(1304 cycles vs. 3392 cycles).
However, there is still a non-trivial difference between R P and the measured response time.
This difference results from a number of sources. First, contrary to our pessimistic assumption
that all the useful cache blocks of a task are replaced from the cache between the
time the task is preempted and the time the task resumes execution, not all of them were
replaced on a preemption during the actual execution. Second, many of actual preemptions
occurred at execution points other than the execution point with the maximum number of
useful cache blocks. Finally, the worst case preemption scenario assumed in deriving the
upper bound on the cache-related preemption delay by the linear programming technique
did not occur during the actual execution.
Another point we can note from the results is that the cache-related preemption delay
(i.e., \Delta) occupies only a small portion of the worst case response time (less than 1% for
most cases). This results from the following two reasons. First, the WCETs of tasks were
unrealistically large in our experiments since we disabled data caching. This diminished
the relative impact of the cache-related preemption delay on the worst case response time.
Second, since the target machine uses SRAM as its main memory, the cache refill time is
much smaller than that of most current computing systems, which ranges from 8 cycles
to more than 100 cycles when DRAM is used as main memory [11]. If DRAM were used
instead, the worst case cache-related preemption delay would have occupied a much greater
portion of the worst case response time. Furthermore, since the speed improvement of
processors is much faster than that of DRAMs [11], we expect that the worst case cache-related
preemption delay will occupy an increasingly large portion of the worst case response
time in the future.
To assess the impact of the cache-related preemption delay on the worst case response time
in a more typical setting, we predicted the worst case response time for task set T 1 as we
increase the cache refill time while enabling data caching. Figures 6-(a) and (b) show \Delta and
\Delta=(W orst Case Response Time), respectively, for this new setting. The results show
that as the cache refill time increases, \Delta increases linearly for all the four methods. This
results in a wider gap between the cache-related preemption delay predicted by method P
Cache Refill Time200000A
U
(a)
Cache Refill Time0.5/
(Worst
Case
Response
A
U
(b)
Fig. 6. Cache refill time vs. \Delta and \Delta=(W orst Case Response Time)
and those by the other methods as the cache refill time increases. As a result, the task set is
deemed unschedulable by methods A, C, and U when the cache refill time is more than 40,
190, and 210 cycles, respectively. On the other hand, the task set is schedulable by P even
when the cache refill time is more than 300 cycles. For methods C and U , there are sudden
jumps in \Delta when the cache refill time is about 120 cycles. These jumps occur when an
increase in the worst case response time due to increased cache refill time causes additional
invocations of higher priority tasks. The results also show that as the cache refill time
increases the cache-related preemption delay takes a proportionally larger percentage in
the worst case response time. As a result, even for method P , the cache-related preemption
delay takes about 10% of the worst case response time when the cache refill time is 100
cycles. For other methods, the cache preemption delay takes a much higher percentage of
the worst case response time.
VII. EXTENSIONS
A. Set Associative Caches
In computing the number of useful cache blocks in Section IV, we considered only the
simplest cache organization called the direct-mapped cache organization where each memory
block can be placed in only one cache block. In a more general cache organization called
the n-way set-associative cache organization, each memory block can be placed in any one
of the n blocks in the mapped set whose index is given by memory block number modulo
number of sets in the cache. This set-associative cache organization requires a policy called
the replacement policy that decides which block to replace to make room for a new block
among the blocks in the mapped set. The least recently used (LRU) policy, which replaces
the block that has not been referenced for the longest time, is typically used for that purpose.
In the following, we explain how to compute the maximum number of useful cache blocks
for set-associative caches assuming the LRU replacement policy.
According to our definition in Section IV, the set RMB c
contains all possible states of
cache block c at execution point p. In the case of direct-mapped caches, a possible state
corresponds to a memory block that cache block c may have at execution point p. This
interpretation of a state needs to be extended for set-associative caches since they are
indexed in the unit of cache sets rather than in the unit of cache blocks. A state of a
cache set for an n-way set-associative cache is defined by a vector (m 1 ;m 2
1 is the least recently referenced block and m n the most recently referenced block. In
the following, we formulate the problem of computing RMBs for set-associative caches in
data flow analysis terms. As for direct-mapped caches, we initially focus on RMBs at the
beginnings and ends of basic blocks.
We define the sets RMB c
IN [B] and RMB c
OUT [B] as the sets of all possible states of cache set
c at the beginning and end of basic block B, respectively. The set gen c [B] contains the state
of cache set c generated in basic block B. Its element has up to n distinct memory blocks
that are referenced in basic block B and are mapped to cache set c. More specifically, it is
either empty (when none of the memory blocks mapped to cache set c are referenced in basic
block B) or a singleton set whose only element is a vector (gen c
In the vector, the component gen c
n [B] is the memory block whose last reference in basic
block B is the last reference to the cache set c in B. Similarly, the component gen c
is the memory block whose last reference in B is the last reference to c in B excepting the
references to the memory block gen c
n [B]. In general, gen c
the memory block whose last reference in B is the last reference to c in B excepting the
references to memory blocks gen c
As an example, consider a cache with two sets. Assume that the following memory block
references are made to cache set 0 in a basic block B.
According to the definition of gen c [B], when each cache set has four blocks (i.e., 4-way
set-associative cache), the set gen c 0 [B] is f(m Similarly, when each cache
set has eight blocks (i.e., 8-way set-associative cache), the set gen c0 [B] is f(null, null, null,
With this definition of gen c [B], the sets RMB c
IN [B] and RMB c
OUT [B], whose elements are
now vectors with n memory blocks, are related as follows.
P a predecessor of B
OUT [B] (12)
f(gen c
if gen c
if gen c
if gen c
IN [B]
if gen c [B] is empty
As in the case of direct-mapped caches, the RMBs of cache set c at points other than the
beginning and end of basic block B can be derived from RMB c
IN [B] and the memory block
references within the basic block. Assume that the basic block has the following sequence
of memory block references
reference to memory block m i that is mapped to cache set c i . As before,
the references are processed sequentially starting from (c processings needed for
are as follows. For each element (rmb in the RMB of c i , if
updated to (rmb
since rmb j is now the most recently referenced memory block in the cache set. On the other
is updated to (rmb
Note that it is only the RMB of c i that needs to be updated by the reference
the reference does not affect the states of any other cache sets.
The set LMB c
for set-associative caches contains all possible reference sequences to cache
set c after p and each reference sequence has sufficient information to determine for each
block in cache set c whether it is re-referenced before being replaced. For an n-way set-associative
cache with the LRU replacement policy, such information corresponds to n
distinct memory blocks referenced after p. For this reason, the set gen c [B] for the LMB
problem is defined to be either empty or a singleton set f(gen c
whose components are the first n distinct memory blocks referenced in basic block B and
mapped to cache set c. More specifically, gen c
1 [B] is the memory block whose first reference
in B is the first reference to c in B and gen c
2 [B] is the memory block whose first reference
in B is the first reference to c in B excepting the references to memory block gen c
1 [B] and
so on.
The sets LMB c
IN [B] and LMB c
OUT [B], which correspond to the sets of all possible reference
sequences to cache set c after the beginning and end of basic block B, respectively, are
related as follows.
S a successor of B
IN [S]
f(gen c
if gen c
OUT [B] f(gen c
if gen c
OUT [B] f(gen c
if gen c
OUT [B]
if gen c [B] is empty
After the LMBs at the beginnings and ends of basic blocks are computed, the LMBs at
other points within basic blocks can be computed in an analogous manner to the case of
RMBs.
Once the sets RMB c
p and LMB c
are computed for each execution point p, the calculation
of the maximum number of useful blocks in cache set c at p is straightforward. For each
element (rmb; lmb) in RMB c
, we compute the number of cache hits that would
result if references from the memory blocks in lmb are applied to the cache set state defined
by rmb. We then pick the element (rmb that yields the largest number of
cache hits, which gives the maximum number of useful cache blocks in cache set c at p.
The total number of useful cache blocks at p is computed by summing up the maximum
numbers of useful cache blocks of all the cache sets in the cache. From this information,
the preemption cost table can be constructed as in the case of direct-mapped cache.
B. Data Cache Memory
Until now, we have focused on preemption costs resulting from the use of instruction cache
memory. In this subsection, we explain an extension of the proposed technique needed for
data cache memory.
Unlike instruction references, some data references have addresses that are not fixed at
compile-time. For example, references from a load/store instruction used to implement an
array access have different addresses. These data references complicate a direct application
of the proposed technique to data cache memory since the technique requires that the
addresses of references from each basic block be fixed. Such references also complicate
the WCET analysis of tasks and most WCET analysis techniques take a very conservative
approach to them. Fortunately, this conservative approach greatly simplifies the adaptation
of the proposed technique for data cache memory. We take the extended timing schema
approach [19] as our example in the following discussion.
In the WCET analysis based on extended timing schema approach, if a load/store instruction
references more than one memory block, it is called a dynamic load/store instruction
[29] and two cache miss penalties are assumed for each reference from it; one cache
miss penalty is because the reference may miss in the cache and the other because it may
replace a useful cache block. In the analysis of preemption costs resulting from the use of
data cache memory, if a load/store instruction is not dynamic, references from it can be
handled in exactly the same way as in the case of instruction references since their addresses
in a CFG are fixed. Also, because the extended timing schema approach assumes that all
the references from a dynamic load/store instruction miss in the cache, they cannot contribute
useful cache blocks. Furthermore, since the approach conservatively assumes that
every one of them replaces a useful cache block in deriving the WCET estimate, we can
completely ignore them when computing RMBs and LMBs.
VIII. CONCLUSION
Cache memory introduces unpredictable variation to task execution time when it is used
in real-time systems where preemptions are allowed among tasks. We have proposed a new
schedulability analysis technique that takes such execution time variation into account. The
proposed technique proceeds in two steps. In the first step, a per-task analysis technique
constructs for each task a table called the preemption cost table. This table gives for a
given number of preemptions an upper bound on the cache-related delay caused by them.
Then, the second step computes the worst case response time of each task using a linear
programming technique that takes as its input the preemption cost table obtained in the
first step. Our experimental results showed that the proposed technique gives a prediction of
the worst case cache-related preemption delay that is up to 60% tighter than that obtained
from previous approaches. This improved prediction accuracy results from the fact that
the proposed technique considers only useful cache blocks in deriving the worst case cache-related
preemption delay.
A number of extensions are possible for the analysis technique explained in this paper. For
example, the per-task preemption cost information can be made more accurate. In the
per-task analysis in Section IV, a cache block is considered as useful if it is useful in at least
one path. Many such paths, however, cannot be taken simultaneously as the example in

Figure

shows. In the example, cache block c i is useful only when the flow of control is
from in 1 to out 2 . On the other hand, cache block c j is useful only when the flow of control
is from in 2 to out 1 . These two flows of control are not compatible with each other and
only one of the two cache blocks can be useful at any one time. Nevertheless, both cache
blocks are considered as useful in our data flow analysis. In order to rectify this problem,
preemption cost should be computed on a path basis. Our initial attempt based on this
idea is described in [30].
Another interesting extension to our proposed analysis technique is to consider the intersection
of cache blocks used by a preempted task and those used by the higher priority
tasks that are released while the former task is preempted [12, 13]. For this purpose, the
proposed technique can be augmented as follows: (1) perform the data flow analysis explained
in Section IV for the preempted task and (2) count only the useful cache blocks
that are mapped to the intersection of cache blocks used by the preempted task and those
used by the higher priority tasks released during the preemption. Although this approach
is more accurate than the approach explained in this paper, it requires a large number of
analyses, i.e., one analysis for each preemption instance. We are currently working on an
approximate technique that is similar to the above approach but trades accuracy for low
analysis complexity.


Appendix


Consider a task set consisting of three tasks
preemption cost tables are
given by
# of preemptions 1
cost
# of preemptions 1
cost 6 5 4 4 3 3 2
Note that we do not need the preemption cost table for the highest priority task - 1 since it
cannot be preempted.
The worst case response time of the lowest priority task - 3 can be computed as follows:
(R 0
(R 0
(R 0
The PC 3 (R 0
can be computed by solving the following integer linear programming
problem.
Maximize
(R 0
subject to
Constraint 1
e
R 0T 3
e
Constraint 2
e
e
In the above problem formulation, we use the fact that since task - 1 is the highest priority
task, it cannot be preempted and thus g This also gives N
which is the maximum number of preemptions a single invocation of task - 2 can experience,
can be computed by dividing the worst case response time of - 2 by the period of task - 1 . The
worst case response time of - 2 , which is equal to 49, must have been computed beforehand
and thus is available when we compute the worst case response time of task - 3 . This gives
2. N 3 , which is the maximum number of preemptions of task - 3 , can be computed by
dividing R 0
3 by the periods of tasks - 1 and - 2 (cf. Equation (9)).
After solving this integer linear programming problem, we have (PC 3 (R 0
this gives R 1
3 value is used in the
next iteration to compute R 2
3 ) is obtained by solving the following integer linear programming problem.
Maximize
3;4 \Theta f 3;4
subject to
Constraint 1
e
e
Constraint 2
e
e
The solution to this integer linear programming problem gives (PC 3 (R 1
and this, in turn, gives R 2
When we repeat the same procedure with R 2
we have R 3
Thus, the procedure
converges and R 2
is a safe upper bound on the worst case response time of
task - 3 . Since this worst case response time is smaller than task - 3 's deadline (=400), task
- 3 is schedulable even when cache-related preemption delay is considered.

Acknowledgments

The authors are grateful to Jos'e V. Busquets-Mataix 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.
"Cache Issues in Real-Time Systems,"
"Adding Instruction Cache Effect to Schedulability Analysis of Preemptive Real-Time Systems,"
Linear and Nonlinear Programming.
"Bounding Worst-Case Instruction Cache Performance,"
"Integrating the Timing Analysis of Pipelining and Instruction Caching,"
"Worst Case Timing Analysis of RISC Processors: R3000/R3010 Case Study,"
"Efficient Microarchitecture Modeling and Path Analysis for Real-Time Software,"
"An Accurate Worst Case Timing Analysis Technique for RISC Pro- cessors,"
"SMART (Strategic Memory Allocation for Real-Time) Cache Design,"
"SMART (Strategic Memory Allocation for Real- Time) Cache Design Using the MIPS R3000,"
"Allocating SMART Cache Segments for Schedulability,"
"Software-Based Cache Partitioning for Real-time Applications,"

High Performance Compilers for Parallel Computing.
DFT/FFT and Convolution Algorithm: Theory
Elementary Numerical Analysis.
C Algorithms for Real-Time DSP
"Efficient Worst Case Timing Analysis of Data Caching,"
"Calculating the Worst Case Preemption Costs of Instruction Cache,"
--TR

--CTR
Anupam Datta , Sidharth Choudhury , Anupam Basu, Using Randomized Rounding to Satisfy Timing Constraints of Real-Time Preemptive Tasks, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.705, January 07-11, 2002
Yudong Tan , Vincent J. Mooney, III, WCRT analysis for a uniprocessor with a unified prioritized cache, ACM SIGPLAN Notices, v.40 n.7, July 2005
M. Kandemir , G. Chen , W. Zhang , I. Kolcu, Data Space Oriented Scheduling in Embedded Systems, Proceedings of the conference on Design, Automation and Test in Europe, p.10416, March 03-07,
Hiroshi Nakashima , Masahiro Konishi , Takashi Nakada, An accurate and efficient simulation-based analysis for worst case interruption delay, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea
Mahmut Kandemir , Guilin Chen, Locality-Aware Process Scheduling for Embedded MPSoCs, Proceedings of the conference on Design, Automation and Test in Europe, p.870-875, March 07-11, 2005
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
Hiroyuki Tomiyama , Nikil D. Dutt, Program path analysis to bound cache-related preemption delay in preemptive real-time systems, Proceedings of the eighth international workshop on Hardware/software codesign, p.67-71, May 2000, San Diego, California, United States
I. Kadayif , M. Kandemir , I. Kolcu , G. Chen, Locality-conscious process scheduling in embedded systems, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado
Sheayun Lee , Sang Lyul Min , Chong Sang Kim , Chang-Gun Lee , Minsuk Lee, Cache-Conscious Limited Preemptive Scheduling, Real-Time Systems, v.17 n.2-3, p.257-282, Nov. 1999
Yudong Tan , Vincent J. Mooney III, Timing Analysis for Preemptive Multi-Tasking Real-Time Systems with Caches, Proceedings of the conference on Design, automation and test in Europe, p.21034, February 16-20, 2004
Yudong Tan , Vincent Mooney, Timing analysis for preemptive multitasking real-time systems with caches, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.1, February 2007
Jan Staschulat , Rolf Ernst, Scalable precision cache analysis for preemptive scheduling, ACM SIGPLAN Notices, v.40 n.7, July 2005
Zhang , Chandra Krintz, Adaptive code unloading for resource-constrained JVMs, ACM SIGPLAN Notices, v.39 n.7, July 2004
Johan Strner , Lars Asplund, Measuring the cache interference cost in preemptive real-time systems, ACM SIGPLAN Notices, v.39 n.7, July 2004
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
Sungpack Hong , Sungjoo Yoo , Hoonsang Jin , Kyu-Myung Choi , Jeong-Taek Kong , Soo-Kwan Eo, Runtime distribution-aware dynamic voltage scaling, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
Chang-Gun Lee , Kwangpo Lee , Joosun Hahn , Yang-Min Seo , Sang Lyul Min , Rhan Ha , Seongsoo Hong , Chang Yun Park , Minsuk Lee , Chong Sang Kim, Bounding Cache-Related Preemption Delay for Real-Time Systems, IEEE Transactions on Software Engineering, v.27 n.9, p.805-826, September 2001
Nikil Dutt , Alex Nicolau , Hiroyuki Tomiyama , Ashok Halambi, New directions in compiler technology for embedded systems (embedded tutorial), Proceedings of the 2001 conference on Asia South Pacific design automation, p.409-414, January 2001, Yokohama, Japan
cache memory;fixed-priority scheduling;preemption;schedulability analysis;real-time system