A Multiframe Model for Real-Time Tasks.
AbstractThe well-known periodic task model of Liu and Layland [10] assumes a worst-case execution time bound for every task and may be too pessimistic if the worst-case execution time of a task is much longer than the average. In this paper, we give a multiframe real-time task model which allows the execution time of a task to vary from one instance to another by specifying the execution time of a task in terms of a sequence of numbers. We investigate the schedulability problem for this model for the preemptive fixed priority scheduling policy. We show that a significant improvement in the utilization bound can be established in our model.
Introduction
The well-known periodic task model by Liu and Layland(L&L) [1] assumes a worst-case execution
time bound for every task. While this is a reasonable assumption for process-control-type real-time
applications, it may be overly conservative [4] for situations where the average-case execution
time of a task is significantly smaller than that of the worst-case. In the case where it is critical
to ensure the completion of a task before its deadline, the worst-case execution time is used at
the price of excess capacity. Other approaches have been considered to make better use of system
resources when there is substantial excess capacity. For example, many algorithms have been developed
to schedule best-effort tasks for resources unused by hard-real-time periodic tasks; aperiodic
task scheduling has been studied extensively and different aperiodic server algorithms have been
developed to schedule them together with periodic tasks [6, 7, 8, 9]. In [10], etc., the imprecise
computation model is used when a system cannot schedule all the desired computation. We have
also investigated an adaptive scheduling model where the timing parameters of a real-time task may
be parameterized [3]. However, none of the work mentioned above addresses the scheduleability of
real-time tasks when the execution time of a task may vary greatly but follows a known pattern.
In this paper, we propose a multiframe task model which takes into account such execution time
patterns; we shall show that better schedulability bounds can be obtained.
In the multiframe model, the execution time of a task is specified by a finite list of numbers. By
repeating this list, a periodic sequence of numbers is generated such that the execution time of each
instance (frame or job) of the task is bounded above by the corresponding number in the periodic
sequence. Consider the following example. Suppose a computer system is used to track vehicles by
registering the status of every vehicle every 3 time units. To get the complete picture, the computer
takes 3 time units to perform the tracking execution, i.e., the computer is 100% utilized. Suppose
in addition, the computer is required to execute some routine task which takes 1 time unit and
the task is to be executed every 5 time units. Obviously, the computer cannot handle both tasks.
Routine:
Tracking:

Figure

1: Schedule of the Vehicle Tracking System
However, if the tracking task can be relaxed so that it requires only 1 time unit to execute every
other period, then the computer should be able to perform both the tracking and routine tasks (see
the timing diagram in figure 1).
This solution cannot be obtained by the L&L model since the worst-case execution time of the
tracking task is 3, so that the periodic task set in the L&L model is given by f(3; 3); (1; 5)g (the first
component in a pair is the execution time and the second the period). This task set has utilization
factor of 1:2 and is thus unscheduleable. Also notice that we cannot replace the tracking task by a
pair of periodic tasks f(3; 6); (1; 6)g since a scheduler may defer the execution of the (3;
that its first execution extends past the interval [0,3], while in fact it must be finished by time=3.
In this paper, we shall investigate the schedulability of tasks for our multiframe task model
under the preemptive fixed priority scheduling policy. For generality, we allow tasks to be sporadic
instead of periodic. A sporadic task is one whose requests may not occur periodically but there is
a minimum separation between any two successive requests from the same task. A periodic task
is the limiting case of a sporadic task whose requests arrive at the maximum allowable rate. We
shall establish the utilization bounds for our model which will be shown to subsume the L&L result
[1]. To obtain these results, however, we require the execution times of the multiframe tasks to
satisfy a fairly liberal constraint. It will be seen that the schedulability bounds can be improved
substantially if there is a large variance between the peak and non-peak execution time of a task.
Using the multiframe model, we can safely admit more real-time tasks than the L&L model.
The paper is organized as follows. Section 2 presents our multiframe real-time task model,
defines some terminology, and prove some basic results about scheduling multiframe tasks. Section
3 investigates the schedulability bound of the fixed priority scheduler for the multiframe model.
Section 4 is the conclusion.
2 The Multiframe Task Model
For the rest of the paper, we shall assume that time values have the domain the set of non-negative
real numbers. All timing parameters in the following definitions are non-negative real numbers.
We remark that all our results will still hold if the domain of time is the non-negative integers.
real-time task is a tuple (\Gamma; P ), where \Gamma is an array of N execution
times is the minimum separation time, i.e., the ready
times of two consecutive frames (requests) must be at least P time units apart. The execution time
of the ith frame of the task is C ((i\Gamma1) mod N) , where 1 - i. The deadline of each frame is P after
its ready time.
For example, is a multiframe task with a minimum separation time of 2. Its
execution time alternates between 2 and 1. When the separation between two consecutive ready
times is always P and the ready time of the first frame of a task is at time=0, the task reduces to
a periodic task.
In the proofs to follow, we shall often associate a multiframe task whose \Gamma has only one element
(i.e., N=1) with a periodic task in the L&L model which has the same execution time and whose
period is the same as the minimum separation of the multiframe task. For example, task
((1); 5) has only one execution time and its corresponding L&L task is (1; 5). We shall call a
periodic task in the L&L model an L&L task, and whenever there is no confusion, we shall call a
multiframe task simply a task.
Consider a task which has more than one execution time. Let
We shall call C m the peak execution time of task T . We shall call the pair
corresponding L&L task of the multiframe task T .
For a set S of n tasks fT
We call U
the peak utilization factor of S.
We call U
the maximum average utilization factor of S:
Given a scheduling policy A, we call U m
A the utilization bound of A if for any task set S, S is
scheduleable by A whenever U m - U m
A ,
We note that U m is also the utilization factor of S's corresponding L&L task set.
Example 1 Consider the task set 5)g. Its corresponding L&L task
set S 0 isfT 0
5)g. The peak utilization factor of S is U 1:2. The maximum
average utilization factor of S is U
A pessimistic way to analyze the scheduleability of a multiframe task set is to consider the
schedulability of its corresponding L&L task set. This, however, may result in rejecting many task
sets which actually are scheduleable. For example, the task set in Example 1 will be rejected if we
use the L&L model, whereas it is actually scheduleable by a fixed priority scheduler under RMA
(Rate Monotonic Assignment), as we shall show later.
respect to a scheduling policy A, a task set is said to be fully utilizing the
processor if it is scheduleable by A, but increasing the execution time of any frame of any task will
result in the modified task set being unscheduleable by A.
We note that U m
A is the greatest lower bound of all fully utilizing task sets with respect to the
scheduling policy A.
Lemma 1 For any scheduling policy A, U m
A - 1.
Proof. We shall prove this by contradiction. Suppose there is an U m
A larger than 1, we arbitrarily
form a task set
A where C m
i is the peak
execution time of T i . So we have \Sigma n
When the peak frames of all the tasks start at the
same time, they cannot be all finished within P by any scheduler, which violates the definition of
A . So U m
A cannot exceed 1. QED.
Suppose A is a scheduling policy which can be used to schedule both multiframe and
L&L task sets. Let the utilization bound of A be U m
A for multiframe task sets. Let the utilization
bound of A for the corresponding L&L task sets be U c
A . Then U m
A .
Proof. Proof is by contradiction. Consider a task set S of size n. Suppose U m - U c
A and the set
is unscheduleable. Its corresponding L&L task set S 0 has the same utilization factor as U m . S 0 is
scheduleable.
Suppose the ith frame of task T j miss its deadline at time t j . For every task T
locate the time point t k which is the ready time of the latest frame of T k such that t k - t j . We
transform the ready time pattern as follows. In the interval from 0 to t k , we push the ready times
of all frames toward t k so that the separation times of all consecutive frames are all equal to P k .
We now set all execution times to be the peak execution time. If t some k, we add
more peak frames of T k at its maximum rate in the interval between t k and t j . The transformed
ready time pattern is at least as stringent as the original case. So the ith frame of T j still misses
its deadline. However, the transformed case is actually a ready time pattern of S 0 which should be
scheduleable, hence a contradiction QED.
Is the inequality in Lemma 2 strict? Intuitively, if U m of a task set is larger than U c
A and there
is not much frame-by-frame variance in the execution times of the tasks in the set, then the task set
is unlikely to be scheduleable. However, if the variance is sufficiently big, then the same scheduling
policy will admit more tasks. This can be quantified by determining the utilization bound for our
task model. We shall show how to establish an exact bound if the execution times of the tasks
satisfy a rather liberal restriction.
be the maximum in an array of execution times (C
array is said to be AM (Accumulatively Monotonic) if \Sigma m+j
is said to be AM if its array of
execution times is AM.
Intuitively, an AM task is a task whose total execution time for any sequence of L - 1 frames
is the largest among all size-L frame sequences when the first frame in the sequence is the frame
with the peak execution time. For instance, all tasks in Example 1 are AM. We note that tasks in
multimedia applications usually satisfy this restriction.
In the following section, we assume that all tasks satisfy the AM property. It will be seen that
without loss of generality, we can assume that the first component of the array of execution time
of every task is its peak execution time, i.e., C m =C 0
Fixed Priority Scheduling
In this section, we shall show that, for the preemptive fixed-priority scheduling policy, the multiframe
task model does have a higher utilization bound than the L&L model if we consider the
execution time variance explicitly. The utilization bound for the L&L model is given by the following
theorem in the much cited paper [1].
Theorem 1 (Theorem 5 from [1]) For L&L task sets of size n, the utilization bound of the
preemptive fixed priority schuduling policy is n(2 1=n \Gamma 1).
Definition 5 The critical instance of a multiframe task is the period when its peak execution time
is requested simultaneously with the peak execution times of all higher priority tasks, and all higher
priority tasks request execution at the maximum rate.
Theorem 2 For the preemptive fixed priority scheduling policy, a multiframe task is scheduleable
if it is scheduleable in its critical instance.
Proof. Suppose a task T scheduleable in its critical instance. We shall prove that
all its frames are scheduleable regardless of their ready times.
First, we prove that the first frame of T k is scheduleable. Let T k be ready at time t and its first
frame finishes at t end . We trace backward in time from time=t to locate a point t 0 when none of
the higher priority tasks was being executed. t 0 always exists, since at time 0 no task is scheduled.
Let us pretend that T k 's first frame becomes ready at time t 0 . It will still finish at time t end . Now
let us shift the ready time pattern of each higher priority task such that its frame which becomes
ready after t 0 now becomes ready at t 0 . This will only postpone the finish time of T k 's first frame
to a point no earlier than t end , say t
end . In other words, T end - t 0
end . Then for each higher priority
task, we shift the ready time of every frame after t 0 toward time=0, so that the separation between
two consecutive frames is always the minimum separation time. This will further postpone the
finish time of T k 's first frame to no earlier than T 0
end . In other words, t 0
end . Now,
we shift all higher priority tasks by by frames until the peak frame starts at t 0 . Since \Gamma k is AM,
this shifting has the effect of postponing the finish time of T k to t 000
end . By construction,
the resulting request pattern is the critical instance for T k . Since T is scheduleable in its critical
instance, we have t 000
first frame is scheduleable.
Next, we prove that all other frames of T k are also scheduleable. This is done by induction.
Induction base case: The first frame of T k is scheduleable.
Induction step: Suppose first i frames of T k are scheduleable. Let us consider the (i+1)th frame
and apply the same argument as before. Suppose that this frame starts at time t and finishes at
t end . Again, we trace backward from t along the time line until we hit a point t 0 when no higher
priority tasks is being executed. t 0 always exists, since no higher priority task is being executed
at the finish time of the ith frame. Let the (i + 1)th frame start at time t 0 . It will still finish
at time t end . Now shift the requests of each higher priority task such that its frame which starts
after t 0 now starts at t 0 . This will only postpone the finish time of T k 's (i 1)th frame to a point
in time no earlier than t end , say t
end . Then for each higher priority task, we
shift the ready time of every frame after t 0 toward time=0 so that the separation time between
any two consecutive frames is always the minimum separation time of the task. This will further
postpone the finish time of T k 's (i 1)th frame to no earlier than T 0
end . In other words,
end . Now for all higher priority tasks, we shift them by frames until the peak frames start
at t 0 . Again, since \Gamma is AM, this further postpones the finish time of T k 's (i 1)th frame to t 000
end . This last case is actually the critical instance for T k . Since T k is scheduleable in
its critical instance, we have t 000
1)th frame is
also scheduleable. We have thus proved the theorem. QED.
We shall say that a task passes its critical instance test if it is scheduleable in its critical instance.
Corollary 1 A task set is scheduleable by a fixed priority scheduler if all its tasks pass the critical
instance test.
From now on, we can assume, without loss of generality that C 0 is the peak execution time of
a task without affecting the schedulability of the task set. This is because we can always replace
a task T whose peek execution time is not in the first frame by one whose execution time array is
obtained by rotating T 's array so that the peek execution time is C 0 . From the argument in the
proof of theorem 2, it is clear that such a task replacement does not affect the result of the critical
instance test.
Example 2 Task set f((2; 1); 3); ((3); 7)g is scheduleable under rate-monotonic assignment. U
tasks pass their critical instance test. However, its corresponding
L&L task set f(2; 3); (3; 7)g is unscheduleable under any fixed priority assignment.
Example 3 The L&L task set f(3; 3); (1; 5)g with utilization factor 1:2 is obviously unscheduleable
by any scheduling policy. However, if the requirement of the first task is relaxed such that every
other frame needs only 1 time unit, the task set becomes scheduleable by RMA. This is because
the relaxed case is given by the multiframe task set f((3; 1); 3); ((1); 5)g which passes the critical
instance test.
We remark that the Example 3 above specifies the vehicle tracking system mentioned at
the beginning of this paper. From the above argument, we can now establish its schedulability.
These examples also show that even if the total peak utilization exceeds 1, a task set may still be
schedulable. Of course, the average utilization must not be larger than 1 for scheduleability.
The complexity of the scheduleability test based on Corollary 1 is O(P ), where P is the biggest
period.
Theorem 3 If a feasible priority assignment exists for some multiframe task set, the rate-monotonic
priority assignment is feasible for that task set.
Proof. Suppose a feasible priority assignment exists for a task set. Let T i and T j be two tasks
of adjacent priority in such an assignment with T i being the higher priority one. Suppose that
us interchange the priorities of T i and T j . It is not difficult to see that the resultant
priority assignment is still feasible by checking the critical instances. The rate-monotonic priority
assignment can be obtained from any priority ordering by a finite sequence of pairwise priority
reordering as above. QED.
To compute the utilization bound, we need the following lemma.
Definition 6 Let \Psi(n; ff) denote the minimum of the expression \Sigma
subject to the constraint: 2.
Proof. With the substitution x
Pn , we can compute
minimize \Sigma n
subject to x
This is a strictly convex problem. There is a unique critical point which is the absolute minimum.
The symmetry of the minimization problem in its variables means that all x i 's are equal in the
solution. So we have x
Definition 7 A task set is said to be extremely utilizing the processor if it is scheduleable but
increasing peak execution time of the lowest priority task by any amount will result in a task set
which is unscheduleable.
We shall use U e to denote the greatest lower bound of all extremely utilizing task sets.
It is important to note the distinction between fully utilizing and extremely utilizing task sets.
It is crucial to the proof of Lemma 4 and Lemma 5.
Lemma 4 Consider all task sets of size n satisfying the restriction
r
Proof. From Theorem 2 and Theorem 3, we only need to consider the case where all tasks
start at time 0 and request at their maximum rates thereafter. We can use rate-monotonic priority
assignment and check for scheduleability in the interval from time 0 to P n . Since
we know that only C 0 and C 1 are involved in all the critical instance tests.
First, the utilization bound corresponds to the case where every C 0 =C 1 equals r, since we can
increase C 1 without changing U m . And increasing C 1 will only take more CPU time. So in the
following proof we assume that all the ratios are equal to r.
For any scheduleable and extremely utilizing task set S with U shall prove four
claims.
1: The second request of T must be finished before P n .
Suppose ffi of C 1
i is scheduled after P n , we can derive a new task set S 0 by only changing the
following execution times of T i and T n ,
and arbitrarily reducing other execution times of T i to maintain the AM property of the execution
time arrays. It is easy to show that S 0 is schedulable and also extremely utilizes the processor.
This contradicts the assumption that U e is the minimum of all extremely utilizing task set. So
the second request of any T i should be completed before P n .
2: If
0, we can derive a new task set S 0 by only changing the following execution times of T i
and T n , and arbitrarily reducing other execution times of T i to maintain the AM property of the
execution time arrays.
It is easy to check that S 0 is scheduleable and also extremely utilizes the processor.
This contradicts the assumption that U e is the minimum. So C 0
3: If
n should be finished before P i .
Instead of proving claim 3, we prove the following equivalent claim:
Consider an extreme utilizing task set S satisfying claim 1 and claim 2. If the last part of C 0
finishes between P i and P i+1 , and
does not correspond to the minimal case.
As in claim 2, we can derive a new task set S 0 by only changing the following execution times
of T i and T n , and arbitrarily reducing other execution times of T n to maintain the AM property of
the execution time arrays.
Suppose P j is the smallest value satisfying
According to claim 1 and
claim 2, the second requests of all tasks other than T n are scheduled between P j and P n . Since
we know the first requests of all tasks other than T n are all scheduled before P j .
extremely utilizes the CPU, we know that the part of C n scheduled before P j is larger
than that scheduled after P j . This guarantees that the new task set S 0 is still scheduleable and
extremely utilizes the CPU.
r
Hence, the task set S cannot be the minimal case. This establishes claim 3.
then the second request of T should be completed exactly
at time P i+1 .
If the second request of T completes ahead of P i+1 , the processor will idle between
its completion time and P i+1 , which shows S does not extremely utilize processor. So this cannot
be true.
If ffi of the second request of T derive a new task set S 0 by
only changing the following execution times of T i and T i+1 , and arbitrarily reducing other execution
times of T i to maintain the AM property of the execution time arrays.
Again it is easy to check that S 0 is schedulable and also extremely utilizes the process.
This contradicts the assumption that U e is the minimum.
So the second request of T should be completed exactly at time T i+1 .
From these four claims and Lemma 3, we can conclude:
r
sets of size n, U
r
Proof. Again, we assume all C 0 =C 1 equals r, and all tasks request at the maximum rate. For
any task T i in an extremely utilizing task set with P i
i such that P 0
increase C 0
n by the amount needed to again extremely utilize the processor. This increase is smaller
than C 1
1). Let the old and new utilization factors be U m and U 0m respectively.
Therefore we can conclude that the minimum utilization occurs among task sets in which the longest
period is no larger than twice of the shortest period. This establishes Lemma 5. QED
Theorem 4 Let
sets of size n, the utilization bound is given by
r
r
Proof. By definition, the least upper bound is the minimum of the U e for task sets of size
ranging from 1 to n, and we have min n
r
r
We observe that Liu and Layland's Theorem 1 is a special case of Theorem 4 with
the frame separation time equals the period.
The following tables summarize the relative advantage of using the multiframe model over the
L&L model in determining whether a set of task is scheduleable. The column under UL&L gives
the utilization bound in the L&L model.
5 0.743 13.6 19.5 22.8 24.9 26.3 27.4 28.2 28.9 29.4 34.5
50 0.698 16.7 24.0 28.2 30.8 32.7 34.1 35.2 36.0 36.7 43.3
100 0.696 16.8 24.3 28.5 31.2 33.1 34.5 35.5 36.4 37.1 43.8

Table

1: Utilization Bound Percentage Improvement
CONCLUSION AND FUTURE RESEARCH 17

Table

1 shows the percentage improvement of our bound over the Liu and Layland bound.
Specifically, the table entries denote 100   (U m =UL&L \Gamma 1), for different combination of r (the ratio
of the peak execution time to the execution time of the second frame) and n (the number of tasks
in the task set). For example, suppose we have a system capable of processing one Gigabyte of data
per second, and a set of tasks each of which needs to process one Megabyte of data per second.
Using a utilization bound of ln 2, we can only allow 693 tasks. By Theorem 4, we can allow at
least 863 tasks (over 24% improvement) when r - 3.
As r increases, the bound improvement increases. Actually, as r ! 1, a simple calculation
shows that the bound ! 1. This says that our model excels when the execution time of the task
varies sharply.
It is also interesting to compare the maximum average utilization with L&L bound. However,
the maximum average utilization factor may be arbitrarily low even if the maximum utilization
factor is very high. One simple example is f((10; 5; 10)g. So, we take instead the
average of the first two frames of the task. In Table 2 we calculate 100   ( 1
r ))=U L&L ,
which is the ratio of the biggest possible maximum average utilization factor to Liu and Layland
bound.

Table

3 shows we can still maintain good overall system utilization when task execution
time varies.
4 Conclusion and Future Research
In this paper, we give a multiframe model for real-time tasks which is more amenable to specifying
tasks whose execution time varies from one instance to another. In our model, the execution times
of successive instances of a task is specified by a finite array of numbers rather than a single number
which is the worst-case execution time of the classical Liu and Layland model.
Using the new model, we derive the utilization bound for the preemptive fixed priority scheduler,
under the assumption that the execution time array of the tasks satisfies the AM (Accumulative
CONCLUSION AND FUTURE RESEARCH
3 0.780 83.5 77.4 74.3 72.3 71.0 70.0 69.3 68.8 68.3 64.1
5 0.743 85.2 79.7 76.7 74.9 73.7 72.8 72.1 71.6 71.2 67.3
100 0.696 87.6 82.8 80.3 78.7 77.6 76.8 76.2 75.8 75.4 71.9

Table

2: Ratio of maximum average to L&L bound
Monotonic) property. This property is rather liberal and is consistent with common encoding
schemes in multimedia applications, where one of the execution times in an array "dominates" the
others. We show that significant improvement in the utilization bound over the Liu and Layland
model results from using our model. This is useful in dynamic applications where the number of
tasks can vary and the figure of merit for resource allocation is the number of tasks that the system
can admit without causing timing failures.
Work is under way to apply this model to real-life applications such as video stream scheduling
and will be reported in the future.



--R

Scheduling Algorithms for Multiprogramming in a Hard- Real-Time Environment
Fundamental Design Problems of Distributed systems for the Hard-Real-Time Envi- ronment
Load Adjustment in Adaptive Real-Time Systems
The Rate Monotonic Scheduling Algorithm - Exact Characterization and Average Case Behavior
Assigning Real-Time Tasks to Homogeneous Multiprocessor Systems
The Deferrable Server Algorithm for Enhanced Aperiodic Responsiveness in Hard Real-Time Environments
A Practical Method for Increasing Processor Utilization
Aperiodic Servers in a Deadline Scheduling Environment
Aperiodic Task Scheduling for Hard Real-Time Systems
Scheduling Periodic Jobs That Allow Imprecise Results
--TR

--CTR
Tei-Wei Kuo , Li-Pin Chang , Yu-Hua Liu , Kwei-Jay Lin, Efficient Online Schedulability Tests for Real-Time Systems, IEEE Transactions on Software Engineering, v.29 n.8, p.734-751, August
Marek Jersak , Rafik Henia , Rolf Ernst, Context-Aware Performance Analysis for Efficient Embedded System Design, Proceedings of the conference on Design, automation and test in Europe, p.21046, February 16-20, 2004
Jrn Migge , Alain Jean-Marie , Nicolas Navet, Timing analysis of compound scheduling policies: application to posix1003.1b, Journal of Scheduling, v.6 n.5, p.457-482, September/October
Samarjit Chakraborty , Thomas Erlebach , Simon Knzli , Lothar Thiele, Schedulability of event-driven code blocks in real-time embedded systems, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
Sanjoy K. Baruah, Dynamic- and Static-priority Scheduling of Recurring Real-time Tasks, Real-Time Systems, v.24 n.1, p.93-128, January
Chang-Gun Lee , Lui Sha , Avinash Peddi, Enhanced Utilization Bounds for QoS Management, IEEE Transactions on Computers, v.53 n.2, p.187-200, February 2004
Michael A. Palis, The Granularity Metric for Fine-Grain Real-Time Scheduling, IEEE Transactions on Computers, v.54 n.12, p.1572-1583, December 2005
Tarek F. Abdelzaher , Vivek Sharma , Chenyang Lu, A Utilization Bound for Aperiodic Tasks and Priority Driven Scheduling, IEEE Transactions on Computers, v.53 n.3, p.334-350, March 2004
Christopher D. Gill , David L. Levine , Douglas C. Schmidt, The Design and Performance of a Real-Time CORBA SchedulingService, Real-Time Systems, v.20 n.2, p.117-154, March 2001
Chin-Fu Kuo , Tei-Wei Kuo , Cheng Chang, Real-Time Digital Signal Processing of Phased Array Radars, IEEE Transactions on Parallel and Distributed Systems, v.14 n.5, p.433-446, May
Lui Sha , Tarek Abdelzaher , Karl-Erik rzn , Anton Cervin , Theodore Baker , Alan Burns , Giorgio Buttazzo , Marco Caccamo , John Lehoczky , Aloysius K. Mok, Real Time Scheduling Theory: A Historical Perspective, Real-Time Systems, v.28 n.2-3, p.101-155, November-December 2004
utilization bound;task model;scheduling;real-time