Scheduling Pdf 193792 | Rt Embedded Scheduling

Partial capture of text on file.

.
Scheduling for Embedded
Real-Time Systems
FELICE BALARIN REAL-TIME EMBEDDED SYSTEMSare of- scheduling techniques commonly imple-
Cadence Berkeley ten characterized by the need for running mented in applications.
Laboratories several tasks on a limited set of processing
LUCIANO LAVAGNO units. Scheduling these tasks on processors The problem
Politecnico di Torino and so that real-time constraints are met is a dif- The scheduling problem consists of de-
Cadence Berkeley ficult problem. However, designers who ciding the order and/or the execution time
Laboratories have to face a difﬁcult trade-off between ef- of a set of tasks with certain known charac-
PRAVEEN MURTHY ficiency and safety choices have several teristics (periodicity, duration) on a limited
Cadence Design Systems choices available to them. set of processing units. These units have a
ALBERTO SANGIOVANNI- We review some of these approaches and given capability (capacity, processing
VINCENTELLI present the main techniques and their prop- speed) and are subject to a set of constraints
University of California at erties, depending on the characteristics of on the completion time of each task and on
Berkeley the system and of its environment. In partic- the use of the processing units. The sched-
ular, we provide well-developed preruntime uling problem is quite general and must be
(static) scheduling that offers very good op- solved in many domains. In manufacturing,
timization and trade-off possibilities for sys- the tasks may be manufacturing operations
tems with regular input and output streams and the processing units may be machines.
such as those found in digital signal pro- In transportation, the tasks may be flights
cessing applications. Our approach is very and the processing units may be airplanes.
The authors review predictable and reliable, and so it can also We consider a speciﬁc subclass of sched-
several approaches to be a valid choice for control-dominated ap- uling problems: those that arise from sched-
control-oriented and plications with inputs irregularly distributed uling software tasks on a single processor (or
dataﬂow-oriented in time but with stringent safety require- onto a limited number of processors for DSP
software scheduling to ments. The price to be paid in this case is in applications) in reactive, real-time embedded
determine whether a terms of processor usage and code size. Run- computing applications. Most reactive em-
given technique can time (dynamic) scheduling, on the other bedded systems continuously react to envi-
satisfy deadlines, hand, is the preferred (and sometimes the ronmental stimuli and must follow the speed
throughput, and other only) choice for control-dominated systems of the environment. This is in contrast to in-
constraints for with very tight timing constraints. teractive systems, such as a word-processing
embedded real-time We also review present research direc- system that responds to the user (the envi-
systems. tions and point out the need for a more for- ronment) as fast as it can but with no hard-
mal analysis of heuristically chosen time constraints and with batch systems for
JANUARY–MARCH1998 0740-7475/98/$10.00 © 1998 IEEE 71
.
SCHEDULING
D dataﬂow graph in which tasks to be executed, called actors,
A B are nodes and directed edges specify the computation ﬂow
D t(A) = 1 and thus the precedence among tasks. See Figure 1.
D D t(B) = 2 There are two broad areas in which scheduling problems
C D t(C) = 3 arise in digital signal processing: high-level synthesis and
D t(D) = 1 general-purpose DSPs.
D In high-level synthesis, the problem is to synthesize hard-
Figure 1. A dataﬂow graph. t = execution times. ware that will perform the operations as specified in the
dataflow graph. The scheduling problem is to map the
dataﬂow graph, where tasks are atomic in the sense that they
which time is almost irrelevant. “Real time” is slightly more represent very elementary operations, like addition and mul-
speciﬁc than “reactive” because it generally identiﬁes a sys- tiplication, to a number of processing elements such as
tem composed of several distinct, often cooperating, tasks. adders and multipliers. The optimization criteria of interest
In addition, real-time systems are usually assumed to be are the total number of processing elements, the through-
nonterminating; the duration for which they operate is usu- put, and the total amount of memory usage (registers). These
ally long enough that it is effectively inﬁnite. Scheduling in are all conﬂicting goals because to increase throughput, we
this domain consists of ﬁnding an execution order for a set might have to increase pipelining, and this increases the
of mutually exclusive, sometimes suspendable tasks. These number of registers being used. Reducing the number of
tasks are characterized by various parameters such as ex- processing elements will reduce the chip area but might de-
pected activation times (maybe periodic, maybe not), max- crease the throughput because there is less computational
imum required execution times, and deadlines by which power available. While this is an important problem and has
they must be completed after activation. Since the programs been thoroughly investigated in the literature, it is outside
are nonterminating, issues such as memory usage and dead- the scope of this article.
lock avoidance also become very important. For example, With general-purpose DSPs, the sequence of operations
a task might produce data at a faster rate than it is consumed, speciﬁed by the dataﬂow graph may be complex, as in an FFT.
or circular dependencies might arise in which each task is These DSPs are quite popular for applications that do not re-
waiting for another to ﬁnish, resulting in early program ter- quire very high throughput rates such as audio signal pro-
mination—an error in most cases. cessing. Traditionally, to achieve the best throughput and
memory usage in DSPs, programmers used assembly language,
Reactive systems. Designers of reactive systems must a tedious and error-prone task at best. We could specify DSP
carefully resolve conﬂicts between different enabled tasks programs in high-level languages (C or Fortran), but compil-
at runtime. (Enabled tasks have received enough inputs to ers for these languages have not been successful at producing
start computing.) Resolving conflicts implies a nondeter- optimized code that compares well with handwritten assem-
ministic runtime behavior and can lead to very subtle bugs bly language. Block-diagram languages have become more
that may manifest themselves a long time after system de- popular as a speciﬁcation language because they
ployment.
■ are more intuitive than either assembly or high-level
DSP systems.Emphasis on throughput and the interde- languages
pendence among tasks are the main differences between ■ can be based on computation models well-suited for
conventional real-time reactive scheduling problems and expressing DSP systems such as dataﬂow
DSP scheduling problems. The throughput goal is to exe- ■ are much easier to parallelize than imperative lan-
cute the DSP algorithm at a rate faster than the incoming guages like C or Fortran
sample rate.
Task interdependence in reactive real-time applications One of the desirable features required of block diagram
involves specifying task readiness externally by giving their languages is efﬁcient code generation. Scheduling plays a
frequency of occurrence or expected times. This models the key role in meeting the various optimization criteria of
temporal characteristics of the inputs coming from the en- throughput, code size, and buffer sizes. Because the com-
vironment. There may or may not be explicit information putation models (for example, synchronous dataﬂow) im-
on the dependence of the task execution on another task. pose restrictions on the overall control ﬂow of the program,
However in DSP applications the input arrival, or sample, compilers for these block diagram languages can perform
rate is precise, and the completion of other tasks enables optimizations not usually possible for more general models
the tasks that follow. We specify this dependency as a or for imperative languages.
72 IEEE DESIGN & TEST OF COMPUTERS
.
Control-dominated systems These difﬁculties can be very serious problems for systems
We generally classify scheduling policies for real-time sys- that require a high degree of safety and reliability. Indeed,
tems as the choice of a scheduling technique is often the result of a
hard compromise between conﬂicting criteria!
■ static, or preruntime, when tasks execute in a ﬁxed or-
der determined ofﬂine. This order may or may not con- Static scheduling. Probably the simplest and most pop-
tain repetitions designed to cope with different ular scheduling approach is the round-robin method. Tasks
expected activation times and/or deadlines. are checked for readiness in a predetermined order, and
■ dynamic, or runtime,when the order of execution is de- the tasks that are found to be ready are immediately exe-
cided online as the tasks present themselves to the pro- cuted. Round-robin is easy to implement. It is also easy to
cessing units ready to be executed. prove at least some timing guarantees. Every task is checked
for readiness once in a cycle, and thus the time between a
Generally, a dynamic execution policy is based on prior- request for execution and the corresponding execution can
ity; that is, one among the set of ready tasks is dynamically be easily bounded by the execution time of other tasks.
chosen according to a priority order. (Priorities may be seen The problem with round-robin scheduling is that it pro-
as additional information that helps in determining an exe- vides poor service to urgent tasks. It is possible that even the
cution policy that satisﬁes all the constraints.) Priority, in- most urgent task needs to wait for all other tasks to execute
tuitively, is a measure of the urgency of each task and can before it gets its turn. Thus to satisfy the timing constraints,
be determined either manually or automatically, in turn sta- a very fast processing unit may be necessary, which may not
tically at compile time or dynamically at runtime. Moreover, be available. Then round-robin would not produce a feasi-
dynamic scheduling can be preemptive if the currently ex- ble schedule. In addition, if some tasks are rarely enabled,
ecuting task can be suspended when another task of high- the overhead of checking them in every cycle may be sig-
er priority becomes ready, and nonpreemptive otherwise. niﬁcant compared with the actual execution time.
Verifying whether a given scheduling satisﬁes all the dead- A slight improvement on round-robin scheduling is stat-
lines (schedulability analysis) is an extremely hard prob- ic cyclic scheduling. Here again tasks are checked for readi-
lem, even when the execution times of all tasks are precisely ness in a predetermined order, and the tasks that are found
known. to be ready are immediately executed. Tasks may appear
If a schedule satisﬁes the constraints, its quality often de- more than once in the cycle. Hence, more urgent tasks may
pends on the use of the processing units—the percentage appear more often and be serviced more frequently, yield-
of time spent by the processor when executing tasks. A pro- ing better schedulability and processor use than with round-
cessing unit may be poorly used either because it spends robin. However, unless the cycle is made very long
time in computing the schedule itself or because the sched- (incurring a memory penalty), static cyclic scheduling may
ule requires an execution overhead. still suffer an overhead due to the frequent readiness check-
Static scheduling requires almost no CPU power at run- ing of tasks that are rarely executed.
time, implying low overhead. (The time required to compute Designers also use static cyclic scheduling for dataﬂow
the schedule before execution may not be negligible but is systems. However, since in that case the inputs are regular
required only once in a system’s lifetime.) However, static data streams, there is no need to check a task for readiness.
scheduling requires that a task be executed whenever it is A task is (statically) scheduled to run only when its inputs are
expected to be ready or at least tested for readiness cycli- known to be present.
cally. If enabling times are not predictable, too much CPU
time is wasted in simply polling events that are unlikely to Dynamic scheduling. Static priority dynamic schedul-
occur. Thus static scheduling best suits cases in which the ing has received significant interest since the pioneering
1
time that tasks become enabled is well-known in advance. work of Liu and Layland. In their approach, at any point in
We discuss this later in the section on dataﬂow systems. time the task with highest priority among the enabled tasks
In general, dynamic scheduling may be necessary to bet- executes; that is, the scheduling follows a preemptive static
ter use the CPU. In fact, processor use that guarantees priority scheme. Strong schedulability and processor use re-
schedulability in the presence of irregular task activations sults have been proven. Unfortunately, the theoretical re-
is much higher for preemptive static priority scheduling1 sults are valid only when
than for static scheduling. On the other hand, dynamically
scheduled systems are much more difﬁcult to tune and de- ■ each task is assigned a ﬁxed and unique priority. Each
bug than statically scheduled systems. This is because the ex- task is enabled when its execution is requested and dis-
ecution times and execution order are largely unpredictable. abled when it completes its execution.
JANUARY–MARCH1998 73
.
SCHEDULING
parent improvement over RMS is often offset by the costly
The choice of a scheduling runtime overhead of EDF scheduling. Consequently, EDF is
not widely used in embedded systems, despite its attractive
technique is often the result theoretical properties.
of a hard compromise Analysis. Liu and Layland’s seminal work has had a wide
impact on research in real-time computing and embedded
between conﬂicting criteria! systems. Yet, every assumption of their model is often vio-
lated to some extent in the design of embedded systems.
For many high-volume, low-cost embedded systems, task
preemption is too expensive in time and space. The runtime
■ executions of each task are requested periodically, with penalty is due to the context switching overhead. The mem-
a constant and known interval between requests. We ory penalty is due to the unpredictability of stack require-
call this interval a period and use P to denote the peri- ments for storing states of preempted tasks. For these
i
od of task i. reasons, designers often use nonpreemptive schemes, even
■ tasks are independent. That is, requests for execution though elegant theoretical results do not extend easily to
of a certain task do not depend on executions of other them.
tasks. In many systems, requests for task executions do not ar-
■ each task must be completed before the next request rive in regular periods. Still, some constraint on the fre-
for it occurs. If a priority assignment is such that this is quency of requests is usually known. It might be in the form
always true for any task, we say the priority assignment of minimum and maximum times between two requests or
is feasible. A set of tasks is schedulable when a feasible in terms of a minimum and maximum number of requests
priority assignment exists. in a given period of time.
■ each task has a constant and known runtime; that is, Tasks are very rarely independent; much more often they
the processor time it requires for a single execution, as- are reactive. They are enabled by either events in the envi-
suming it is not interrupted. We use T to denote the run- ronment (and the same event might enable several tasks)
i
time of task i. or the execution of other tasks.
The correctness criteria of a task execution are often not
Designers may assign priorities either by hand or let them quite clear. The designer usually has a reasonable set of re-
be determined by an algorithm. For systems satisfying the quirements for the embedded system as a whole but ﬁnds
above-mentioned assumptions, Liu and Layland proposed it difﬁcult to relate these overall constraints to requirements
a particular algorithm for priority assignment, called rate on individual tasks.
monotonic scheduling. RMS is a static priority scheduling A task’s runtime is almost never constant. It may vary with
scheme that assigns priorities according to periods such that different input patterns as well as with the state of the task.
tasks with shorter periods get higher priorities. Modern processor design techniques make things even
Liu and Layland showed that RMS is optimal in the sense worse. The runtime in a pipelined processor or a processor
that if the RMS priority assignment is not feasible, a set of with memory caches may vary even for the same inputs and
tasks is not schedulable. They also discovered the least up- the same internal task state. Considering this lack of pre-
per bound on processor use in a static priority scheme. More dictability and the cost pressure, it is not surprising that em-
precisely, if, for a set of n tasks, the processor use is less than bedded systems often include simple processors based on
n(21/n−1), that set of tasks is schedulable. (In particular, RMS designs that are over a decade old.
priority assignment is feasible.)
Liu and Layland have also found an even stronger uti- Beyond RMS and EDF. Fortunately, the static priority
lization result for a dynamic priority assignment policy called scheduling scheme is amenable to analysis even in more re-
earliest deadline ﬁrst (EDF). The basic assumption of EDF is alistic models in which some of the assumptions of Liu and
that at any point in time the priority of an enabled task is not Layland have been relaxed. For example, Audsley et al.2pro-
ﬁxed; it depends on the time until the next request for that posed an optimal priority assignment algorithm for static pri-
task. According to the EDF policy, the executing task must ority scheduling that is valid for any model for which there
always have the least time remaining until the next request exists a test satisfying the following conditions:
(or equivalently the earliest deadline) among all the enabled
tasks. An EDF-executed set of tasks is schedulable if, and 1. Given a priority assignment, it is possible to check
only if, its processor use is less than 1. Unfortunately, this ap- whether some task isatisﬁes its timing constraints. The
74 IEEE DESIGN & TEST OF COMPUTERS

The words contained in this file might help you see if this file matches what you are looking for:

...Scheduling for embedded real time systems felice balarin systemsare of techniques commonly imple cadence berkeley ten characterized by the need running mented in applications laboratories several tasks on a limited set processing luciano lavagno units these processors problem politecnico di torino and so that constraints are met is dif consists de ficult however designers who ciding order or execution have to face difcult trade off between ef with certain known charac praveen murthy ficiency safety choices teristics periodicity duration design available them alberto sangiovanni we review some approaches given capability capacity vincentelli present main their prop speed subject university california at erties depending characteristics completion each task system its environment partic use sched ular provide well developed preruntime uling quite general must be static offers very good op solved many domains manufacturing timization possibilities sys may operations tems regular input out...

Related files

Share

Help

Related files

Share

Share to social media

Help

Login Area