Response-Time Analysis
- Here task i’s worst-case response time, R, is calculated first and then checked (trivially) with its deadline, R.i <= D.i
For the highest priority task, tis worse case response time will equally its own computational time ( that is, R=C). other tasks will siffer interferences from higher priority tasks; this is the time spent executing higher priority tasks when a low priority task is runnable. so for the general task i :
R.i = C.i = I.i
where i is the interference from higher priority tasks
2iii ICR +=
Where
I is the interference from higher priority tasks
Calculating Response-Time (R)
During R, each higher priority task j will execute a number of
times:
Numbers of releases = [R.i/T.j]
The ceiling function [] gives the smallest integer greater than the fractional
number on which it acts. So the ceiling of 1/3 is 1, of 6/5 is 2, and of 6/3 is 2.
total interferences is given by [R.i/T.j]*C.j
Response Time Equation
R.i = C.i + sum (j=hp(i) [R.i/T.j]*Cj
Where hp(i) is the set of tasks with priority higher than task i
Solve by forming a recurrence relationship:
W.i^n+1 = C.i + sum (j=hp(i) [W.i^n/T.j]*Cj
The set of values w^0, w^1…w^n is monotonically non decreasing.
When the solution to the equation has been found;w^0 must not be greater than R (e.g. 0 or C.i)
Response Time Algorithm
for i in 1..N loop – for each task in turn
n := 0
w.i^n := C.i
loop
calculate new w.i^n+1
if w.i^n+1 = w^n then
R = w.i^n
exit value found
end if
if w.i^n+1 > T.i then
exit value not found
end if
n := n + 1
end loop
end loop
task set d
fig 1 (worst case response time: R.a= 3.
let w^(0,b) = C.b = 2
etc etc (se fig 1 og 2)
Task Set c
fig 1
The combined utilization is 1.0
* This was above the utilization threshold for three tasks (0.78),
therefore it failed the test
* The response time analysis shows that the task set will meet
all its deadlines
Response Time
Analysis
Is sufficient and necessary (exact)
If the task set passes the test, they will
meet all their deadlines;
If they fail the test then, at run-time, a
task will miss its deadline (unless the
computation time estimations
themselves turn out to be pessimistic)
Sporadic Tasks
- Sporadic tasks have a minimum inter-arrival time
- They also require D < T
- The response time algorithm for fixed priority scheduling:
- works perfectly for values of D less than T as long as the stopping criteria
becomes W.i^n+1 > D.i - It also works perfectly well with any priority ordering — hp(i) always gives the
set of higher-priority tasks
Hard and Soft tasks
- In many situations the worst-case figures
for sporadic tasks are considerably higher
than the averages - Interrupts often arrive in bursts and an
abnormal sensor reading may lead to
significant additional computation - Measuring schedulability with worst-case
figures may lead to very low processor
utilizations being observed in the actual
running system
General Guidelines
Rule 1:
All tasks should be schedulable using average execution times
and average arrival rates
Rule 2:
All hard real-time tasks should be schedulable using worst-case
execution times and worst-case arrival rates of all tasks (including
soft)
* A consequent of Rule 1 is that there may be situations in which it
is not possible to meet all current deadlines This condition is
known as a transient overload
* Rule 2 ensures that no hard real-time task will miss its deadline
* If Rule 2 gives rise to unacceptably low utilizations for “normal
execution” then action must be taken to reduce the worst-case
execution times (or arrival rates)
Aperiodic Tasks
These do not have minimum inter-arrival times
* Can run aperiodic tasks at a priority below the
priorities assigned to hard processes. In effect, the
aperiodic tasks run as background activities, and
therefore they cannot steal, in a pre-emptive
system, resources from the hard processes
* This does not provide adequate support to soft
tasks which will often miss their deadlines
* To improve the situation for soft tasks, a server can
be employed
Task Systems with constrained deadlines (D < T)
For D = T, Rate Monotonic Priority Ordering (RMPO) is optimal
- Each task is assigned a (unique) priority based on its period; the shorter the period, the higher the priority (fig task set for RMPO)
For D < T, Deadline Monotonic Priority Ordering (DMPO) is optimal
D.i < D.j -> P.i > P.j
D < T: Example Task Set for Deadline Monotonic Priority Ordering
(fig 1, DMPO)
The task with shortest deadline, get the highest priority: D.i < D.j -> P.i > P.j
When is DMPO
Optimal?
*Deadline monotonic priority ordering (DMPO)
is optimal:
if any task set, Q, that is schedulable by
priority scheme, W, is also schedulable by
DMPO
* The proof of optimality of DMPO involves
transforming the priorities of Q (as assigned
by W) until the ordering is DMPO
* Each step of the transformation will preserve
schedulability
Task Interactions and
Blocking
Priority Inversion:
* If a task is suspended waiting for a
lower-priority task to complete
some required computation, then
the priority model is in some sense,
being undermined
* It is said to suffer Priority Inversion
* If a task is waiting for a lower-
priority task, it is said to be blocked
Priority Inversion
To illustrate an extreme example of priority inversion, consider
the executions of four periodic tasks: a, b, c and d; and two
resources: Q and V
Task Priority Execution Sequence Release Time
a 1 EQQQQE 0
b 2 EE 2
c 3 EVVE 2
d 4 EEQVE 4
Example of Priority Inversion
fig 1
Example of
Priority
Inversion
- d suffers considerable priority inversion
- Blocked by a, but also by b and c
- Blocking by a is inevitable in order to preserve the
integrity of the critical section - Blocking by b and c is unproductive and affects
the schedulability of the system - The result of a purely fixed-priority scheme
Priority
Inheritance
- Assume process p is blocked, waiting for process q.
- Assume the priority of p exceeds that of q
- If we give q the same priority as p for the duration of
the blocking, then p might finish earlier. - This is called priority inheritance
- Process priorities are no longer static
example (fig 1)
Mars Path-Finder
A problem due to priority inversion nearly
caused the lose of the Mars Path-finder mission
* As a shared bus got heavily loaded critical data
was not been transferred
* Time-out on this data was used as an indication
of failure and lead to re-boot
* Solution was a patch that turned on priority
inheritance, this solved the problem
Priority Ceiling
Protocols
Two forms:
* Original Ceiling Priority Protocol (OCPP)
* Immediate Ceiling Priority Protocol (ICPP)
On a Single
Processor
- A high-priority task can be blocked at
most once during its execution by
lower-priority tasks - Deadlocks are prevented
- Transitive blocking is prevented
- Mutual exclusive access to resources is
ensured (by the protocol itself)
OCPP - Original
Ceiling Priority
Protocol
- Each task has a static default priority assigned
(perhaps by the deadline monotonic scheme) - Each resource has a static ceiling value defined, this
is the maximum priority of the tasks that use it - A task has a dynamic priority that is the maximum
of its own static priority and any it inherits due to it
blocking higher-priority tasks - A task can only lock a resource if its dynamic
priority is higher than the ceiling of any currently
locked resource (excluding any that it has already
locked itself)
OCPP Analysis
B.i = max (k=1, k) usage(k,i)*C(k)
*Bi is maximum blocking time, k is nr of critical sections (resources) in the system
* Even though blocking has a ‘single term’ impact, good
design practice is to keep all critical sections small
