Both PERC and MPI/RT propose to accept responsibility for reliable
execution of dynamic real-time workloads. In both environments, a workload
is proposed to the system, the system analyzes the proposed workload, and
the system either accepts or rejects the workload. Once a workload has
been accepted, real-time constraints are "guaranteed" to be satisfied.
In comments describing PERC implementation techniques, we point out that
real-time threads can be scheduled either through the use of a static
cyclic schedule, or a dynamic static priority schedule, or a hybrid between
the two. (Dynamic priority implementations would also be acceptable.) The
current MPI/RT draft supports two modes of operation: time-driven and
event-driven. (I'm intentionally ignoring priority-driven for now).
In the MPI/RT meeting, Arkady suggested that his hope was that we would
come to some sort of agreement as to how each mode of operation should be
handled separately at first, and that we would later tackle the problem of
mixing them together. I told him individually, and now in public, that I'd
like to see some thought given to how the modes would eventually mix. (I
have a sense that one reason it may be difficult to reach consensus on
certain design issues is because we don't have a good understanding of the
inherent implementation complexities associated with particular API features.)
These are my thoughts regarding one possible implementation of a
mixed-model admissions test. I welcome feedback and suggestions for
improvement.
Assumptions:
1. A static cyclic schedule has already been constructed
2. The static schedule was constructed so as to minimize the durations
of CPU time that are allocated to static tasks. e.g. the static
cyclic scheduler prefers:
_______ ________
________|___A___|________|____B___|_________
0 10 20 30 40 50
over:
_______ ________
________|___A___|____B___|__________________
0 10 20 30 40 50
3. Our job, given an existing static schedule and a proposed workload
of dynamic tasks, is to decide whether to accept responsibility for
execution of the dynamic tasks.
The analysis is based on the techniques used by Liu-Layland to derive the
standard RMA result. To illustrate the analysis, consider the following
static cyclic schedule, of duration 70
____ ____ ________
[__A_|____|_B__|_______|____C___|__]
0 10 20 30 45 65
1. At the time the static schedule is constructed, we precompute some
tables which characterize the ways in which this static schedule
might interfere with dynamic tasks. In particular, we consider that
the Liu-Layland critical instant might occur at time 0, time 20, or
time 45 so we build interference graphs for each of those cases:
Available CPU Time for Critical Point A
30 | .
| ____/
20 | /
| /
10 | __/
| /
0 |_/
|_._._._._._._.
0 20 40 60
10 30 50 70
Available CPU Time for Critical Point B
30 | .
| /
20 | __/
| ____/
10 | /
| /
0 |_/
|_._._._._._._.
0 20 40 60
10 30 50 70
Available CPU Time for Critical Point C
30 | .
| /
20 | /
| __/
10 | /
| __/
0 |___/
|_._._._._._._.
0 20 40 60
10 30 50 70
Now, what we really want to know is the worst-case
interference imposed by the existing static schedule on execution
of dynamic real-time tasks. In this case, the worst-case interference
is represented by the third graph. In more complicated cases, it is
possible that the worst-case interference graph would need to be
computed by merging the above graphs. The general technique is to
define the function as the minimum of the values of the individual
graphs for each possible value of the x coordinate. Note that this
chart can be repeated to allow analysis of dynamic workloads with
task periods that exceed the length of the cyclic schedule.
Worst-Case Available CPU Time
30 | .
| /
20 | /
| __/
10 | /
| __/
0 |___/
|_._._._._._._.
0 20 40 60
10 30 50 70
2. Note that, in terms of the "Worst-Case Available CPU Time" illustrated
above, the dynamic tasks will, at worst, be able to run only during
times represented by upward slanting graph segments. Suppose
a certain dynamic workload can be sheduled in Y time in the absence of
interference from statically scheduled tasks. On the above graph,
find the rightmost x coordinate that maps to the given Y and call this
X. The worst-case amount by which this event will be delayed by
interference from statically scheduled tasks is X-Y.
3. Sort the proposed dynamic workload in terms of decreasing execution
frequency. In order from highest to lowest priority, examine each
task:
a) Compute its "raw" completion time in terms of its WCET and the
WCET and frequencies of all higher "priority" tasks.
If its completion time adjusted for static schedule interference
does not satisfy the task's latency requirement, reject the
workload as unschedulable.
b) Add this task into the "interference" workload that is used to
compute completion times for all lower priority tasks.
Some observations:
1. This assumes tasks (message transmissions) can be preempted at arbitrary
times. If this is not the case, more detailed bookkeeping is required.
2. This ignores the overhead of distributed dynamic scheduling. If multiple
nodes desire to transmit dynamic messages during time slots not reserved
in the static schedule, there is a certain (in some cases
nondeterministic)
overhead associated with contention resolution protocols.
3. This analysis can be easily modified to support deadlies shorter than
periods, such as is the case with so-called "emergency messages."
I'd like discussion and comments on this... I do not propose this as the
ultimate solution.
-- Kelvin Nilsen, President voice: 515-296-0897 NewMonics Inc. fax: 515-296-9910 2501 N. Loop Dr., Suite 614A http://www.newmonics.com Ames, IA 50010 email: kdn@newmonics.com