Page 134 - DCAP608_REAL TIME SYSTEMS

Unit 13: Working of Priority-driven Scheduling of Periodic Tasks

Notes
Example: Consider a system of n tasks 1, 2, . . . , n, with the ith task ôi characterized by
a worst-case execution requirement Ci, a relative deadline parameter Di , and a minimum inter-
arrival separation parameter Ti . Without loss of generality, assume that the tasks are indexed in
decreasing order of priority. RTA allows for the exact computation of the worst-case response
time of each task, by representing the response-time of each job of each task as the solution to a
recurrence equation. For example, if Di d” Ti (“i), it has been shown that the worst-case response
time of ôi is equal to the smallest t satisfying the following equality:

t
t C C
i j
j i T j
This equation is easily solved using standard techniques for the solution of recurrence equations,
in time pseudo-polynomial in the representation of the task system. Despite this pseudo-
polynomial time complexity, RTA has very efficient implementations in practice that renders it
quite suitable for feasibility analysis of Fixed Priority (FP) systems. However, there are certain
real-time design scenarios during which there are drawbacks to using RTA: The computational
complexity of these algorithms may render them unsuitable for use in interactive real-time
system design environments. During a process of interactive system design and rapid system
prototyping, the system designer typically makes a large number of calls to a feasibility-analysis
algorithm, since proposed designs are modified according to the feedback offered by the
feasibility-analysis algorithm (and other analysis techniques). In such scenarios, a pseudo-
polynomial algorithm for computing the task set feasibility may be unacceptably slow; instead,
it may be acceptable to use a faster algorithm that provides an approximate, rather than exact,
analysis. (The computation of exact response times is especially expensive when the deadline Di
is allowed to be larger than the period Ti, and/or when resource-sharing may lead to limited
priority inversion and blocking; for such systems, several recurrences of the form Equation (1),
one for each job of ôi within the “first busy period,” must be solved in order to compute the exact
response time.

Notes If jobs of a task self suspend during their execution, the task no longer behaves like
a periodic task: in some intervals it may demand more time than a periodic task.

One of the features of the worst-case response time that is easily seen from Equation (1) above is
that it is not a continuous function of system parameters. Informally speaking, this is a
consequence of the ceiling function: for certain values of t, an infinitesimally small increase in
some Tj will cause t/Tj to increase by one and the right-hand side of Equation (1) to consequently
increase by an amount not smaller than Cj. Discontinuities like these are a major hurdle to a
process of incremental, interactive system design. Ideally, such a de sign process would allow
for the interactive exploration of the state space of possible designs; this would be greatly
facilitate d if making minor changes to a design (equivalently, moving small distances in the
state space of possible system designs) results in minor changes to system properties.

Self Assessment

Fill in the blanks:
6. ……………… test is more complex than the schedulable utilization test, but more general.
7. When a group of tasks share a common resource (such as a processor, a communication
medium,. . . ), a scheduling policy is necessary to ……………… access to the shared resource.

LOVELY PROFESSIONAL UNIVERSITY 129