Section 1
Introduction
Since its
conception in 1973, rate monotonic theory has made a significant contribution
to real-time applications programming.
Using rate monotonic theory, a given task set may be analyzed to determine
which tasks in the task set will meet their deadlines. Moreover, the rate monotonic algorithms have
been shown to be optimal in the sense that if a task set is schedulable by any
other algorithm, then it is schedulable by the rate monotonic algorithms [3, p.
51].
The purpose of
this paper is not to introduce new results, but rather to present an overview
of the theory as it applies to the Ada programming language. Section 2 presents a brief introduction to
the precepts of rate monotonic analysis. The assumptions that rate monotonic theory
makes are presented.
The original
assumptions made by rate monotonic theory are quite restrictive; much work has
been done to relax these assumptions.
Section 3 presents this work, grouping each result obtained with the
assumption (or assumptions) that it relaxes.
Finally, section
4 presents two paradigms for the creation of periodic tasks in Ada. The advantages and disadvantages of each are
discussed.
Section 2
Rate Monotonic Analysis
History
Real-time system
correctness depends not only on logical correctness, but on timing constraints
as well. Systems designers, therefore,
must suitably schedule all tasks so that each meets its deadline. This scheduling was typically accomplished in
one of two manners: either a cyclical scheduler or a prioritized scheme. A cyclical scheduler proved very difficult to
maintain during system updates, while assigning tasks priorities based solely
on their perceived importance caused deadlines to be needlessly missed [5, p.
2].
Rate monotonic
scheduling theory was introduced in 1973 by Lui and Layland [4] to address
these problems. To make the analysis
possible, however, five assumptions concerning the task set had to be made. Unfortunately, these assumptions eliminated
most task sets from consideration.
Further development has since produced means for relaxing some of these
assumptions [3, 6, 7, 9].
An Overview
Originally, rate
monotonic analysis was developed as a means of scheduling periodic tasks
alone. A periodic task is defined as a
task with a periodic request rate and a hard deadline immediately preceding the
next periodic request.
The fundamental
precept of rate monotonic analysis is, then, the assignment of priorities to
tasks according to the period with which they occur. That is, those tasks with a shorter period
(and hence a higher request rate) receive a higher priority. Lui and Layland have shown that this
scheduling protocol is optimal in the sense that if a task set is schedulable
(that is, it is possible to schedule the task set in such a way that all
deadlines will be met), then it is also schedulable by the rate monotonic
protocol [4, p. 51].
In some systems,
this strict ordering of tasks by period may not be acceptable. For example, a system may depend on a longer
period, and hence lower priority, task meeting its deadline. In these cases, it is possible to do a period
transformation on the critical task, raising its priority by splitting the
longer task into several shorter (and hence higher priority) tasks [5, p.
9-10].
Lui and Laylund
provided the following theorem to test whether or not a task set is shedulable
[4, p. 54]. It should be noted that the
bound provided by this theorem is rather pessimistic; a task set that fails to
meet the bound in this theorem may still be schedulable. This theorem is still useful, however, as a
quick check for a given task set.
Theorem 1: A set of n
tasks, with fixed priority order, is schedulable if
where 
is the execution time
required for task i and 
is the period of task i.
Lehoczky, Sha,
and Ding have exactly characterized the schedulability of any task set with the
following theorem, stated by Sha and Goodenough [5, p. 5-6]:
Theorem 2: A set of n
independent periodic tasks scheduled by the rate monotonic algorithm will
always meet its deadlines, for all task phasings, if and only if
where and are defined as in the
previous theorem, and 
Assumptions of Rate Monotonic
Analysis
In order to make
the schedulability analysis possible, five assumptions need to be made
concerning the task set. These
assumptions are as follows [4, p. 48]:
1. The
requests for all tasks for which hard deadlines exist are periodic, with
constant interval between requests.
2. Deadlines
consist of run-ability constraints only -- i.e. each task must be completed
before the next request for it occurs.
3. The
tasks are independent in that requests for a certain task do not depend on the
initiation or the completion of requests for other tasks.
4. Run-time
for each task is a constant for that task and does not vary with time. Run-time here refers to the time which is
taken by a processor to execute the task without interruption.
5. Any
aperiodic tasks in the system are special; they are initialization or failure
recovery routines; they displace periodic tasks while they themselves are being
run, and do not themselves have hard, critical deadlines.
These
assumptions are indeed restrictive; however, as mentioned previously, work has
been done to relax them.
Section 3
Refinements of Rate Monotonic Analysis
Since 1973,
several advancements in the theory of rate monotonic scheduling have been
made. The impositions made by the
assumptions of rate monotonic theory on the task set were unacceptable for most
systems. Therefore, efforts to improve
the theory have been focused on the relaxation of the assumptions.
This section
presents the five assumptions made of the task set by rate monotonic theory,
along with an overview of efforts to relax each assumption.
The First Assumption
The requests for all tasks for which hard
deadlines exist are periodic, with constant interval between requests.
This assumption
eliminates most real-time systems from consideration by eliminating sporadic
events (a sporadic event is defined as an aperiodic event with a hard
deadline).
Initial attempts
to relax this assumption involved creating a periodic task to poll aperiodic
events. This approach, although
implementation is trivial, suffers from an unnecessarily long average response
time [9, p. 4][6, p. 4].
Further attempts
produced the priority exchange protocol [1, p. 4][6, p. 5][9, p. 6-10]. In this scheme, a periodic task is created to
process sporadic events. If no sporadic
events have been requested at the onset of the server task, then the server
exchanges its high priority with a lower priority periodic task. That is, the server allows a lower priority periodic
task to execute until completion or the arrival of a sporadic request, which
ever comes first. If the periodic task
executes to completion and still no sporadic requests have occurred, then the
server will allow the next periodic task to execute until completion or the
arrival of a sporadic request. This
continues until the priority of the server degenerates to background. In the event of a sporadic request, the
request is processed at the current priority level of the server until
completion or the depletion of the server's allotted execution time, which ever
comes first. Replenishment of the
server's execution time occurs periodically.
While the
priority exchange protocol has the advantage of fast average response times, it
suffers from implementation complexity and unnecessary accruement of run-time
overhead [6, p. 5][9, p. 16].
An attempt to
lessen the impact of the priority exchange protocol on run-time overhead then
produced the deferrable server protocol [1, p. 4][5, p. 11][6, p. 5][9, p.
6-10]. As with the priority exchange
protocol, a periodic server task is created to process sporadic requests. If no sporadic requests are pending at server
onset, the deferrable server is suspended until a sporadic request
arrives. When this occurs, if the
server's allotted time is not depleted, the task executing is preempted. As with the priority exchange protocol, the
server's allotted execution time is replenished periodically.
The deferrable
server has low implementation complexity and accrues little run-time
overhead. Unfortunately, the protocol
violates the fourth assumption of rate monotonic theory [6, p. 5].
The shortcomings
of the priority exchange and deferrable server protocols where overcome in 1989
by Sprunt, Sha, and Lohoczky with the introduction of the sporadic server
protocol [9]. The sporadic server
protocol [1, p. 4][5, p. 12-13][6, p. 5][8][9, p. 11-18], like the priority
exchange and deferrable server protocols, requires the creation of a periodic
task to service sporadic requests. If,
at the onset of the server, no sporadic requests are pending, the server
preserves its allotted time at high priority (in the same manner as the
deferrable server). Then, as the
deferrable server, it preempts any lower priority periodic task upon the
arrival of a sporadic request. The
fundamental difference between the deferrable server and the sporadic server is
the manner in which each server is replenished.
Where the full amount of the deferrable server's allotted execution time
is replenished at the beginning of each period, the amount of execution time
consumed by each sporadic request is replenished one full period after it was
consumed.
The sporadic
server does not accrue as much run-time overhead or require the implementation
complexity of the priority exchange protocol.
The replenishment scheme of the sporadic server does not periodically
require processing while no sporadic requests are made, as the deferrable
server's replenishment scheme does.
Although the sporadic server violates the same assumption as the
deferrable server, Sprunt, Sha, and Lohoczky have demonstrated the
schedulability of the sporadic server in a rate monotonic run-time system [9,
p. 23-24] (for alternative applications of the sporadic server, see [8, p.
3-5]).
With the
sporadic server, then, the assumption that requests for all tasks for which
hard deadlines exist are periodic is relaxed.
The remaining component of the first assumption, that all tasks have a
constant interval between requests, can be addressed either by taking the
minimum possible task period (this will result in a lowering of processor
utilization in the average case) or by employing a mode change (see The Fourth Assumption) [6, p. 7-9].
The Second Assumption
Deadlines consist of run-ability
constraints only -- i.e. each task must be completed before the next request
for it occurs.
With this
assumption, the run-time executive is free from monitoring the periods of all
tasks. An alternative would be to have
the run-time executive buffer all requests and for each task initiate one
request every period.
The Third Assumption
The tasks are independent in that
requests for a certain task do not depend on the initiation or the completion
of requests for other tasks.
This assumption
eliminates from consideration those task sets that employ either inter-task
communication, semaphores, or input/output.
Clearly, this assumption is unacceptable for most real-time systems. Understandably, there has been no small
amount of effort given to the relaxation of this assumption. While the advances are substantial, the
theory is not yet complete.
With the
introduction of semaphores comes the problem of unbounded priority
inversion. Priority inversion is defined
as the blocking of a higher priority task by a lower priority task. Unbounded priority inversion can occur when a
high priority task and a low priority task share a common semaphore. For illustration, consider tasks H, M,
and L; H being the highest priority task, M a medium priority task, and L
the lowest priority task. Assume that H and L share a common resource guarded by a semaphore. Suppose further that L enters its critical section, locking the semaphore. Assume now that H attempts to enter its critical section and is blocked. The arrival of task M would now preempt L,
forcing task H to wait not only for
the completion of task L's critical
section, but also for task M (and any
other intermediate priority tasks). In
this manner, a high priority task may be blocked for an indefinitely long period
of time.
To address this
problem, the priority inheritance protocol was developed [1, p. 5][3, p.
13-14][5, p. 14][7, p. 4-6][9, p. 26].
Under the priority inheritance protocol, if a lower priority task blocks
a higher priority task, the lower priority task inherits the priority of the
higher priority task for the duration of its critical section.[1]
Using this scheme, Sha, Ragunathan, and Lehoczky have demonstrated that
if there are m semaphores that can be
used to block a job J, then J can be suspended for at most the
duration of m critical sections [7,
p. 6] (see [7, p. 5-6] for a complete listing of properties of the priority
inheritance protocol).
Unfortunately,
priority inversion is not the only problem that semaphores introduce. Deadlocking needs to be addressed as
well. Priority inheritance alone will
not prevent deadlocks; the ceiling priority protocol was developed to eliminate
deadlocks [1, p. 6][3, p. 15-16][5, p. 14-16][6, p. 6][7, p. 6-14]. Under this protocol, every semaphore is given
a ceiling priority defined to be the priority of the highest priority task that
can lock the semaphore. The following
rules, then, must be followed [7, p. 9-10]:
1. Suppose
that J has the highest priority among
the jobs ready to run and is assigned the processor, and let S* be the semaphore with the
highest priority ceiling of all semaphores currently locked by jobs other than
job J. Before job J enters its critical section, it must first obtain the lock on
semaphore S guarding the shared data
structure. Job J will be blocked, and the lock on S denied, if the priority of job J is not higher than the priority ceiling of semaphore S*. In this case, job J is said to be blocked by the job which holds the lock on S*. Otherwise, job J will obtain the lock on semaphore S and enter its critical section.
When a job J exits its
critical section, the binary semaphore associated with the critical section
will be unlocked and the jobs, if any, that are unblocked by J become ready to run. The highest priority job that is ready to run
will be assigned the processor.
2. A
job J uses its assigned priority,
unless it is in its critical section and blocks higher priority jobs. If job J
blocks higher priority jobs, J
inherits PH, the highest
priority of the jobs blocked by J. When J
exits its (outermost) critical section, it resumes its original priority. Priority inheritance is transitive. Finally, the operations of priority
inheritance and resumption of original priority must be indivisible.
3. A
job J, when it does not attempt to
enter a critical section, can preempt another job JL if its priority is higher than the priority,
inherited or assigned, at which job JL
is executing.
When the
priority inheritance and ceiling priority protocols are followed, the theorems
in Section 1 may be modified to allow for the blocking time introduced by task
synchronization [5, p. 15]:
Theorem 3: A set of n
periodic tasks using the priority ceiling protocol can be scheduled by the rate
monotonic algorithm, for all task phasings, if the following condition is
satisfied:
where and are the execution time
and period of task i (as in the
theorems in Section 1) and 
is the longest
duration of blocking time that task i
can experience.
As with the
corresponding theorem in Section 1, the bound is rather pessimistic. It is possible that a task set that fails the
test in the above theorem is schedulable.
A more realistic bound is given in the next theorem [5, p. 15-16]:
Theorem 4: A set of n
periodic tasks using the priority ceiling protocol can be scheduled by the rate
monotonic algorithm for all task phasings if the following condition is
satisfied:
where , , and are defined as in
theorem 3, and
Two differences
between this theorem and its analog in section 1 merit mention. First, the theorem in section 1 is an exact
characterization, this theorem is not. Secondly,
the sum in the theorem in section 1 is over 
, the sum in this theorem is over 
.
Finally, this
assumption precludes the use of input and output. Both inputting and outputting to/from an
external device requires the suspension of the task making the request. The time spent in such a suspension will be
termed idle time. There are subtle differences between idle
time and blocking time (in the sense of the ceiling priority protocol). Blocking time is dependent on the length of a
limited number of critical sections and is governed by that property of the
ceiling priority protocol that strictly bounds the number of critical sections
in lower priority tasks for which each higher priority task must wait. Idle time depends on the amount of time
needed to process an input or output request.
The priority ceiling protocol governs which task is given the processor
while a higher priority task is blocked.
The protocol governing which task is given the processor during a higher
priority task's idle time is different.
For these reasons, idle time may not be considered blocking time in the
above two theorems.
Klien and Ralya,
in their paper An Analysis of
Input/Output Paradigms for Real-Time Systems [3], begin to deal with this
issue. The introduction of idle time
into tasks scheduled with the rate monotonic algorithm may create any of the
following difficulties [3, p. 19-27]:
1. Idle time will have a direct impact on the
requesting task's schedulability. In
this respect, idle time may be considered as blocking time (however, for the
requesting task only).
2. Idle time has an effect on the blocking
time components of higher priority processes. This can occur when the completion of an
input or output request made by a lower priority task causes an interrupt
during the execution of a higher priority task.
3. Idle time may also affect the blocking
properties of the process that experiences inactivity. This effect is the result of applying the
priority ceiling protocol to input and output devices. A task will become suspended if it requests
an input or output transaction while any other input or output routine with a
priority ceiling higher than the priority of the task in question is active.
4. Idle time can also affect lower priority
processes. Deferring the execution
of a higher priority process can cause a lower priority process to miss a
deadline [3, p. 15].
To deal with
these issues, Klien and Ralya introduce a constant into the inequality given in
theorem 1. The computation of this
constant is straightforward in the synchronous case [3, p. 23]; in the
asynchronous case, however, the computation is more involved and is derived
from a pessimistic paradigm [3, p. 33].
The Fourth Assumption
Run-time for each task is a constant for
that task and does not vary with time.
Run-time here refers to the time which is taken by a processor to
execute the task without interruption.
Tasks which have
a varying run-time can be analyzed by considering their worst case run-time and
the average case run-time. The
assumption that tasks cannot be interrupted can be relaxed with the techniques
used in relaxing the first and third assumptions.
Often, in
real-time systems, a mode change is required.
This could involve the removal or addition of tasks to the task set or a
dramatic change in the amount of time required to process a currently existing
task. Such operations, clearly, violate
this assumption. The relaxation of this
assumption to allow mode changes can be realized (assuming the ceiling priority
protocol is in effect) if the following protocol is observed [6, p. 7-9]:
1. For
each unlocked semaphore S whose
priority ceiling needs to be raised, S's
ceiling is raised immediately and indivisibly.
2. For
each locked semaphore S whose
priority ceiling needs to be raised, S's
priority ceiling is raised immediately and indivisibly after S is unlocked.
3. For
each semaphore S whose priority
ceiling needs to be lowered, S's
priority ceiling is lowered when all the tasks which may lock S, and which have priorities greater
than the new priority ceiling of S,
are deleted.
4. If
task 
's priority is higher than the priority ceilings of locked
semaphores 
, which it may lock, the priority ceilings of must first be raised
before adding task .
5. A
task , which needs to be deleted, can be deleted immediately upon
the initiation of a mode change, and its processor time reclaimed, if it has
not begun to execute. If has initiated, then it
may be deleted only after completion.
6. A
task may be added into the system only if sufficient processor capacity exists.
This protocol
preserves the ceiling priority protocol's properties of freedom from deadlock
and the guarantee that a higher priority task may be blocked by a lower
priority task at most once. If both task
sets are schedulable, then all tasks will meet their deadlines across the mode
switch [6, p. 9].
The Fifth Assumption
Any aperiodic tasks in the system are
special; they are initialization or failure recovery routines; they displace
periodic tasks while they themselves are being run, and do not themselves have
hard, critical deadlines.
This assumption
may be relaxed by employing the techniques used in relaxing the first and third
assumptions.
Section 4
Ada Programming Issues
The assumptions
of rate monotonic theory restrict the form a periodic task may take. This section presents two periodic task[2] paradigms.
For each paradigm, applicable coding restrictions and limitations are
discussed.
The Ada Language
Reference Manual specifies only that a delay statement will cause a delay at
least as long as the given expression [10, 9.6.1]. Moreover, there is no requirement that a
scheduling decision be made upon completion of the delay. The paradigms presented in this section
require both that the delay be for exactly the amount of time specified and
that at the completion of any given delay, a scheduling decision be made.
It is not
possible, without the capability of dynamically changing priorities, to implement a sporadic server under either
of the following two paradigms. This can
be seen by considering the case of an aperiodic request occurring when the
sporadic server's execution time is not completely exhausted, and there is not
enough time left to process the event.
If the aperiodic handler is given a lower priority than the periodic
task set, then it must remain in rendezvous with the sporadic server to attain
the high priority needed for it to begin its execution. In this case, however, the sporadic server
task is not capable of suspending the aperiodic handler when its time is
exhausted. If the aperiodic handler is
given a higher priority than the periodic task set, then it will continue to
preempt periodic tasks after the sporadic server's time is exhausted. An approximation of the sporadic server is
given in [8]. This implementation is
consistent with both paradigms.
Paradigm 1
The approach of
the first paradigm is to create an additional
task, termed a dispatcher, to
regulate the periodic tasks. This is
acheived with an entry call to each periodic task, at the beginning of each of
its periods. The dispatcher, to function
properly, must have the highest priority.
Following is an example of a dispatcher:
task body MY_DISPATCHER is
begin
loop
MY_PERIODIC_TASK_1.DO_IT;
delay
(DELAY_1); -- DELAY_1 may be an
expression
MY_PERIODIC_TASK_2.DO_IT;
delay
(DELAY_2); -- DELAY_2 may be an
expression
end
loop;
end MY_DISPATCHER;
Every periodic
task, under this paradigm, has a single accept
statement inside a loop. Such a task
would have the following form:
task body MY_PERIODIC_TASK is
entry
DO_IT;
begin
loop
accept
DO_IT;
end
loop;
end MY_PERIODIC_TASK;
Pardigm
1 Coding Restrictions
Little variation
from the above form will be permissible for periodic tasks. Specifically, the following constructions,
when used in periodic tasks, are shown to be either completely inconsistent
with the assumptions of rate monotonic theory or allowable only with
restrictions:
Multiple
accept statements.
Abort statements.
Delay statements.
Exception
handlers.
Input
and output.
Pragma
shared statements.
Rendezvous.
Multiple accept statements are completely inconsistent with rate
monotonic theory. The language does not
define the order in which the accept statements are handled. It is possible that a task might wait on one
entry while requests for the other entry queue up. This violates the second assumption.
Since an abort statement causes the deletion of
a task from the task set, its use must be governed by the mode change protocol
detailed in section 2.
Ada allows a delay statement to occur in three
distinct contexts: within a selective wait, within a timed entry call, and
inline with other code. A selective wait
with a delay alternative is not allowable.
Should the delay condition become open, the task will begin execution
beyond the control of the rate monotonic run-time. A timed entry call is allowable so long as
the principles of the ceiling priority protocol are not violated (this assumes
that rendezvous are governed according to the ceiling priority protocol -- see
the paragraph in this section dealing with rendezvous). A delay statement inline with other
statements is not allowable, since it would introduce blocking not governed by
the ceiling priority protocol.
The handling of exceptions may not involve the
termination of a task, unless the mode change protocol is followed. Any additional overhead caused by the
handling of exceptions must be accounted for in the analysis.
Input and output must be governed by the protocol
discussed in [3].
Pragma shared introduces blocking time into a task's
execution. Hence, this construction is
permissible only if this blocking time is governed by the ceiling priority
protocol.
Ada rendezvous (except the accept statement used by the dispatcher
to control the periodic task), will necessarily introduce blocking time into
one or both of the tasks in question.
All blocking must be governed by the ceiling priority protocol. While it is possible that some
implementations will have provisions for the use of the rendezvous for
inter-task communication, it is more likely that most implementations will
restrict inter-task communication to semaphores (that is, rendezvous will be
allowed only with a semaphore task).
Paradigm
1 Considerations
Questions
concerning the methods of implementing input/output, inter-task communication,
the handling of aperiodic events, and resource contention naturally arise. This section addresses these concerns,
followed by a critique of this model.
Task interaction
with external devices presents complications in the theory as well as in the
computations. Close adherence to the
protocol presented in [3] is required.
If this paradigm is being used, one additional restriction must be added
to input/output requests: no request may be made while in rendezvous with the
dispatcher task. Such a rendezvous would
cause suspension of the dispatcher task for the duration of the input/output
request.
Inter-task
communication and resource contention both require the use of a semaphore. Since this will introduce blocking time, the
ceiling priority protocol must be followed.
As the priority inheritance and ceiling priority protocols are typically
issues of the run-time executive, discussion will not be presented here.
The handling of
aperiodic requests may be accomplished either by employing the modified
sporadic server discussed in [8] or by polling.
While polling requires less implementation effort, its response time is
often undesirably slow. The modified
sporadic server has a faster response time (albeit not as fast as a true
sporadic server) and a more complex implementation.
This paradigm
has the advantages of a simple means of task control and tolerance of varying
execution times of periodic tasks. Both
advantages are due to the existence of the high priority dispatcher task, which
may preempt lower priority tasks which for some reason have not yet
completed. This guarentees that higher
priority tasks will start their periods at the proper time (the next paradigm
does not share this advantage).
Paradigm 2
In this model,
periodic tasks are governed by the placing of a delay statement inline within
each task body. For each task, the
length of the delay is set equal to the execution time of the task in question
subtracted from the task's period.
Unlike the first paradigm, under this model there is no centralized
control of tasks. Following is the form
of a periodic task under this model:
task body MY_PERIODIC_TASK is
begin
loop
delay
(DELAY_1); -- DELAY_1 may be an
expression.
end
loop;
end MY_PERIODIC_TASK;
Paradigm
2 Coding Restrictions
As with paradigm
1, certain Ada tasking constructions, if used in conjunction with this model,
violate the principles of rate monotonic scheduling. Specifically, the following constructions are
shown to be either completely inconsistent with rate monotonic theory, or
applicable in only a restricted sense:
Multiple
accept statements.
Rendezvous.
Abort
statements.
Delay
statements.
Exception
handling.
Input/Output.
Pragma
shared statements.
Multiple accept statements violate the principles of rate monotonic
theory; see paradigm 1 coding restrictions.
The Ada rendezvous necessarily introduces
blocking time into one or both of the tasks in question. All blocking time, to remain consistent with
rate monotonic principles, must be governed by the ceiling priority protocol. As most current Ada implementations do not
govern rendezvous in a manner consistent with rate monotonic theory, inter-task
communication will be restricted to semaphores.
The abort statement, as previously
discussed, causes the termination of the task in question. Such a mode change must be governed by the
protocol in [6, p. 7-9].
Delay statements (other than those used to regulate periodic
tasks) introduce blocking time that is not governed by the priority ceiling
protocol. Their use is therefore
prohibited.
The handling of exceptions may not cause a task to
terminate unless the mode change protocol is followed. Any additional execution time that exception
handling adds to the task must be accounted for in the analysis.
The use of input or output devices must be governed by the protocol presented in [3].
The use of
shared variables (pragma shared)
introduces blocking time into the task in question. This blocking time must be governed by the
ceiling priority protocol.
Paradigm
2 Considerations
As with the
previous paradigm, inter-task communication will most probably be accomplished
with semaphores. The blocking time
introduced must be governed by the priority ceiling protocol. All input and output must be governed be the
protocol in [3].
This paradigm
suffers from an intolerance of periodic tasks with varying execution
times. An applications programmer who
chooses this model is faced with the choice of using either fixed or dynamic
delay times.
Fixed delay
times will lead to period shifting as periodic tasks vary their execution
times. Suppose, for example, that an
applications programmer creates a periodic task with period 10ms and normal
execution time 2ms, with execution time 3ms if, say, an external event arrives. He then uses a fixed delay statement at the
end of this task with value 8ms. Now
suppose further that during the execution of this task, the external event
arrives, causing an extra 1ms of execution time. This will cause a period shift of 1ms; that
is, the next period will begin 1ms late.
The alternative
is to dynamically change the delay length, computing it from the system clock.[3]
This approach, however, accrues needless run-time overhead.
This paradigm,
while simpler to implement than the previous paradigm, is too simplistic for
most real-time applications.
Bibliography
[1] A. Burns
Scheduling
Hard Real-Time Systems: A Review
Technical Report CS13-88
Department of Computing,
University of Bradford
1988
[2] J.
B. Goodenough, Lui Sha
The
Priority Ceiling Protocol: A Method for
Minimizing the Blocking of High-Priority Ada Tasks
CMU/SEI-88-SR-4
Carnegie-Mellon University
1988
[3] Mark
H. Klien, Thomas Ralya
An
Analysis of Input/Output Paradigms for Real-Time Systems
CMU/SEI-90-TR-19
Carnegie-Mellon University
1990
[4] C.
L. Liu, James W. Layland
Scheduling
Algorithms for Multiprogramming in a Hard-Real-Time Envirnment
Journal of the Association
for Computing Machinery, Vol. 20, No. 1, January 1973
[5] Lui
Sha, John B. Goodenough
Real-Time
Scheduling Theory and Ada
CMU/SEI-89-TR-14
Carnegie-Mellon University
1989
[6] Lui
Sha, Mark H. Klein, John B. Goodenough
Rate
Monotonic Analysis for Real-Time Analysis
CMU/SEI-91-TR-5
Carnegie-Mellon University
1991
[7] Lui
Sha, Ragunathan Rajkumar, John P. Lehoczky
Priority
Enheritance Protocols
CMU-CS-87-181
Carnegie-Mellon University
1987