Processing
Sam Siewert
Introduction
Processing i/p data & producing o/p data for a s/m response in
real time
Does not necessarily require large CPU resources
But rather careful use of CPU resources
The mantra of real-time s/m correctness is that the s/m must not
only produce the required o/p response for a given i/p, but it
must also do so in a timely manner
Deadline in real-time s/m
Relative time after a service requested by which time the s/m
must produce a response
Sam Siewert 2
Introduction
Processing in video or video real-time s/m is considered high
quality if the service continuously provided o/p
Neither too early not too late
Without too much latency
Without too much jitter b/w the frames
In digital control applications, the ideal s/m has a constant time
delay b/w sensor sampling &actuator o/p
Responses should not be generated too long or too early after a
service request
Sam Siewert 3
Preemptive Fixed-Priority Policy
RM LUB Test
Used to determine whether a proposed set of services is feasible
The proposed set of services can be scheduled given a fixed & known amount of CPU resource
Liu & Layland proposed this simple feasibility test
RM LUB is defined as
Where U:Utility of the CPU resource achievable1
m
Ci:ExecutionU
time (ofCiservice
/ Ti ) i.m(2 m 1)
m:Total [Link] services
i 1 in the system sharing common CPU resources.
Ti:Release period of service i.
Guarantees that all Service Releases can meet Deadlines
4
Preemptive Fixed-Priority Policy
Critical instant assumes that in the worst case, all services might
be requested at the same time
To observe all services, we at least need to diagram the service
execution over a period equal to or greater than the largest
period in the set of services
To really understand the use of the s/m, we must diagram the
execution over the LCM of all periods for the proposed set of
services or LSM time
Sam Siewert 5
Preemptive Fixed-Priority Policy
For a s/m, can all C’s fit in the largest T over LCM time ?
Given services S1 ,S2 with periods T1 ,T2 and execution times C1 ,C2
E.g. T1=2, T2=5, C1=1, C2= 1
Assume T2 > T1 and if prio (S1) > prio (S2), then
C.I. T2 / T1 C1 C2 T2 T2 / T1 C1 C2 T2
U 1 / 2 1 / 5 0.7 S1
1
U 0.7 2(2 2 1) 0.83 S2
T2
T1
Sam Siewert 6
Can You Safely Exceed LUB?
YES!
In some cases, but RM LUB will never pass an infeasible system
RM LUB is a SUFFICIENT Feasibility Test
RM LUB is NOT a NECESSARY and SUFFICIENT Feasibility Test
(Systems with Harmonic Periods can often have U=1.0 and be feasible!)
Example Where RM LUB is Safely Exceeded:
Given: Services S1, S2 with periods T1 and T2 and C1 and C2, Assume T2 > T1
E.g. T1=2, T2=5, C1=1, C2= 2, then if prio(S1) > prio(S2), note that:
U 1 / 2 2 / 5 0.9 C.I. T2 / T1 C1 C2 T2 T2 / T1 C1 C2 T2
1
U 0.9 2(2 1) 2 S1
U 0.9 0.83 S2
T2
T1
Sam Siewert 7
RM Priority Assignment Policy
RM Policy:
Given: services S1, S2 with periods T1 and T2 and C1 and C2 with T2 > T1
E.g. T1=2, T2=5, C1=1, C2=2, then if prio(S1) > prio(S2), note that:
S1 Makes Deadline if prio(S1) > prio(S2)
S1
S2
T2
T1
Sam Siewert D1 D1 D2 8
RM Priority Assignment Policy
Consider Alternative Policy:
Given: services S1, S2 with periods T1 and T2 and C1 and C2 with T2 > T1
E.g. T1=2, T2=5, C1=1, C2=2, then if prio(S2) > prio(S1), note that:
S1 Misses Deadline if prio(S2) > prio(S1)
S1
S2
T2
T1
Conclusion:
If {Sn} feasible with prio(S2) > prio(S1), then {Sn} is also always
feasible given prio(S1) > prio(S2), but converse is not necessarily
TRUE!!
Therefore, prio(S1) > prio(S2) is OPTIMAL
Sam Siewert 9
Relationship Between Sufficient and N&S
Fesibility Tests
All Service Sets
Safe & Unsafe
Safe Service
Set
Passing N&S
Safe Service
Set Passing
Test
Sufficient
Test
Sam Siewert 10
Two types of feasibility tests are,
• Sufficient condition:To say that A is
sufficient for B is to say that A cannot occur
without B,or whenever A occurs,B occurs.
The logical relation between them is
expressed as “If A then B” or “A only if
B”or “B only if A”or “AB.
• Necessary & Sufficient conditions:To say
that A is necessary & sufficient for B is to
say two things:1)A is necessary for B and11
RM LUB Derivation
Finding RM Safe Upper Bound (LUB):
If system feasible over LCM with RM policy, then by Theorem Two
(Briand and Roy), it is safe!
Note that there can be up to T2 / T1 releases of S 1 during T2!
C.I.
S1 #1 #2 #3
S2
T2
T1
LUB Derivation Strategy:
Case 1: C1 short enough to fit all 3 releases in T2 (fits S2 critical time zone)
Case 2: C1 too large to fit last release in T2 (doesn’t fit S2 critical time zone)
Examine U in both cases to find common U bound.
Sam Siewert 12
RM LUB Derivation
Case 1 (All 3 C1 releases fit in T2):
C1 T2 T1 T2 / T1 (I.e, C1 is small enough to fit into fractional 3rd T 1 shown below as )
C2 T2 C1 T2 / T1 (I.e, C2 = T2 - Interference from C1 releases)
C1 C2 C.I.
U
T1 T2 S1 #1 #2 #3
S2
T2
T1
Plugging C2 Expression into U: C1 T2 C1 T2 / T1
U
T1 T2
U monotonically decreases
T /T
with increasing C1 when (T2>T1) U 1 C1 1 / T1 2 1
T2
Sam Siewert 13
Proof that U Monotonically
Decreases in Case-1
Value of Maximum Occurances of Period-1 During Period-2 Over Period-2
1.9
1.8
1.7
1.6
1.5
1.4
1.3
1.2
1.1
1
1 2 3 4 5 6 7 8
T2
Sam Siewert 14
RM LUB Derivation
Case 2 (Last C1 release does not fit in T2):
C.I.
S1 #1 #2 #3
C1 T2 T1 T2 / T1
C2 T1 T2 / T1 C1 T2 / T1 S2
C1 C2 T2
U
T1 T2
T1
Plugging C2 Expression into U: C1 T1 T2 / T1 C1 T2 / T1
U
T1 T2
U monotonically increases U T1 / T2 T2 / T1 C1 1 / T1 1 / T2 T2 / T1
with increasing C1 when (T2>T1)
Sam Siewert 15
RM LUB Derivation
Given Cases 1 and 2 (T1=2, T2=5) T1= 2 T2= 5
Case 1 Case 2
Case 2 C1 U C1 U
Case 1 Intersection 0
0.1
1
0.99
0
0.1
0.8
0.81
C1 T2 T1 T2 / T1 0.2 0.98 0.2 0.82
C1 T2 T1 T2 / T1
C1 T2 T1 T2 / T1 C2 T1 T2 / T1 C1 T2 / T1 0.3 0.97 0.3 0.83
C2 T1 T2 / T1 C1 T2 / T1 0.4 0.96 0.4 0.84
C2 T2 C1 T2 / T1 C1 C2
C1 C2 U 0.5 0.95 0.5 0.85
U
U
C1 C2
1.0 T1 T2
T1 T2 0.6
0.7
0.94
0.93
0.6
0.7
0.86
0.87
T1 T2 0.8 0.92 0.8 0.88
U 0.9
1
0.91
0.9
0.9
1
0.89
0.9
LUB =? Note: we want the LUB for any
given T2 and T1, not the ones
C1 assumed here in particular, so the
T /T general LUB could be something
Case 1: U 1 C1 1 / T1 2 1 other than 0.9, and must be found in
T2
terms of T1 and T2 only for general
Case 2: U T1 / T2 T2 / T1 C1 1 / T1 1 / T2 T2 / T1 LUB.
Sam Siewert 16
RM LUB Derivation
Intersection of Case 1 & 2 is Least Upper Bound
Plug In Intersection for C1 and C2 into U to get expression in terms of T1 and
T2 only: U 1 T1 / T2 T2 / T1 T2 / T1 T2 / T1 T2 / T1
(Substitute for both C1 and C2 in U expression and simplify)
f 1 f
Let I T2 /Tand f T2 / T1 Tso,
1 2 / T1 U 1
T
2 1 / T
I is the integer number of times that T1 occurs during T2
f is the fractional time of the last release for T 1 during T2, noting that if f =0,
then T1 and T2 are harmonic, and therefore U=1, an uninteresting ideal case.
Substituting I and f into the U expression above and simplifying, we get:
U 1 T1 / T2 T2 / T1 T2 / T1 T2 / T1 T2 / T1
(noting that 1+floor(N+/-0.d) = ceiling(N+/-0.d) when f non-zero)
U 1 T1 / T2 1 T2 / T1 T2 / T1 T2 / T1 T2 / T1
U 1 T1 / T2 1 T2 / T1 T2 / T1 T2 / T1 T2 / T1
f 1 f
So, U 1 T1 / T2 1 f f , Re-arranged to obtain: U 1
T2 / T1
Sam Siewert 17
RM LUB Derivation
f 1 f
U 1 Can also be expressed as:
T2 / T1
By adding and subtracting the same
f 1 f
U 1 denominator term to get:
T2 / T1 T2 / T1 T2 / T1
f 1 f smallest I is 1, and LUB for U
U 1
f f2
U 1
I f occurs when I is minimized, so:
1 f
Now taking the derivative of U w.r.t. f, and solving for extreme, we get:
dU / df
1 f 1 2 f f f 2 1
0
1 f 2
Solving for f, we get: f 21/ 2 1
And, plugging f back into U, we get: U 22 1 The RM LUB!
1/ 2
Sam Siewert 18
RM LUB Scenario for 2 Services
(With T1=2, T2=3, We Show U=0.83 Worst-Case Graphically)
Given Case 1: U T1 / T2 T2 / T1 C1 1 / T1 1 / T2 T2 / T1
T /T
And Case 2: U 1 C1 1 / T1 2 1 RM LUB (T 1 =2, T 2 =3)
T2
1
0.95
T 1= 2 T 2= 3 0.9
0.85
Case 1 Case 2 0.8
C1 U C2 C1 U C2 0.75
0 1 3 0 0.666667 2 0.7
0.65
0.1 0.983333 2.8 0.1 0.683333 1.9 0.6
0.2 0.966667 2.6 0.2 0.7 1.8 0.55
0.3 0.95 2.4 0.3 0.716667 1.7 0.5
U
0.4 0.933333 2.2 0.4 0.733333 1.6 0.45
0.5 0.916667 2 0.5 0.75 1.5 0.4
0.35
0.6 0.9 1.8 0.6 0.766667 1.4 0.3
0.7 0.883333 1.6 0.7 0.783333 1.3 0.25
0.8 0.866667 1.4 0.8 0.8 1.2 0.2
0.9 0.85 1.2 0.9 0.816667 1.1 0.15
0.1
1 0.833333 1 1 0.833333 1
0.05
1.1 0.816667 0.8 1.1 0.85 0.9 0
1.2 0.8 0.6 1.2 0.866667 0.8
1.3 0.783333 0.4 1.3 0.883333 0.7
0 0.5 1 1.5
1.4 0.766667 0.2 1.4 0.9 0.6 C1
1.5 0.75 0 1.5 0.916667 0.5
Sam Siewert 19
RM FAQ
• Where in the paper does it say that T must equal D?
– T=D is in section 4 above Theorem 1 in Liu and Layland paper
• Why does Floor(x.d)+1 = Ceiling(x.d)?, because if x=1 or any integer, this
is not true.
– Floor(x.d) + 1 = Ceiling(x.d) iff x is not an integer value, which is always true
if T2 is not a multiple of T1
• If T2 > T1, but T2 is a multiple of T1 (if T1 and T2 are harmonic), then U=1,
and doesn’t this violate the RM LUB?
– Yes, it does, but remember the RM LUB is only sufficient, not N&S, and
therefore it will pessimistically fail service sets that can actually be scheduled
– The RM LUB will correctly fail all service sets than in fact can’t be scheduled,
so it is sufficient
• Why Not Just Use EDF Scheduling Policy if it Can Achieve 100% Utility
and Be Shown to Meet Deadlines?
– What Happens When EDF is Overloaded?
Sam Siewert 20
Dynamic Priority Issues
• Earliest Deadline First Policy (aka Deadline Driven Scheduling)
– Can Be High Overhead - Every time the Ready Queue is Updated, the
Scheduler Must Re-assign all Priorities According to Each Service’s Time
Remaining to Deadline and Perform a Priority Preemption.
– Overload Failure Modes Non-Deterministic - In an Overload Scenario,
EDF Can Have Difficult to Predict and Cascading Multi-Service Failures
• Overload with RM Policy is Deterministic - the Lowest Priority Service Will
Fail First and The Number of Services Failing From Lowest Priority Up Can
be Determined by Duration of Over-run and Priority of Over-running Service
– Over-run Interference Has Known Impact on Lower Priority Services
– Over-runs Will Be Preempted By Higher Priority Services if Allowed to Continue
• Overload with EDF Policy is Non-Deterministic
– Time to Deadline for an Over-running Service is Zero or Negative?
– Over-running Service Will Maintain High Priority Based on Time to Deadline
– Additional Services that Over-run Due to Interference Also Have Elevated Priority
– Chaining Priority Amplification and Over-runs Can Cause Cascading Failure
• Over-run Termination Policy May Help (Worst Case Interference Margin)
– Difficult to Debug Dynamic Priority When Deadlines Are Missed
Sam Siewert 21
RM Fixed Prio Overload
Si+1 Prio(Si+n) > Prioi (Si)
Si Si = over-running service
Prio(Si-n) < Prioi (Si)
Si-1
Sam Siewert 22
EDF Dynamic Prio Overload
Si = over-running service
Terminate Si = over-running service
Si
Prio(Si-n) < Prioi (Si)
Si-1 Si-1 = over-running service Terminate Si-1 = over-running service
Si-1
Prio(Si-1-n) < Prioi (Si-1)
Si-2
Si-2 = over-running service
Si-1
Prio(Si-2-n) < Prioi (Si-2)
Si-2
Sam Siewert 23
Dynamic Priority Issues Cont’d
• Least Laxity First Policy
– Can Be High Overhead - Every time the Ready Queue is Updated, the Scheduler Must
Re-assign all Priorities According to Each Service’s (Time Remaining to Deadline -
Execution Time Remaining) and Perform a Priority Preemption.
– Execution Time Remaining Hard to Estimate - Compared to EDF, Least Laxity First is
More Difficult to Implement Since Execution Time Remaining for All Services Must Be
Estimated to Re-assign Priorities
– Overload Failure Modes Better, But Still Non-Deterministic - In an Overload Scenario,
LLF May Behave More Favorably Since it Encodes the Concept of Dispatching the
Service with the Most Pressing Need for the CPU Resource (I.e. Remaining Execution
Time is Factored In)
• Over-run Invalidates Estimates of Execution Time Remaining
• Suffers Same Potential Cascading Priority Amplification and Interference on Over-runs
• Over-run Termination Policy May Help
– Difficult to Debug Dynamic Priority When Deadlines Are Missed
Sam Siewert 24
Example #1
(RM Policy Failure)
Example 1 T1 2 C1 1 U1 0.5 LCM = 70
T2 5 C2 1 U2 0.2
T3 7 C3 2 U3 0.285714 Utot = 0.985714
RM Schedule
S1 ????????
S2 ????????
S3 LATE
EDF Schedule
S1
S2
S3
TTD
S1 2 X 2 X 2 X 2 X 2 X
S2 5 4 X X X 5 4 3 X X
S3 7 6 5 4 3 2 X 7 6 5
LLF Schedule
S1
S2
S3
Laxity
S1 1 X 1 X 1 X 1 X 1 X
S2 4 3 X X X 4 3 2 X X
S3 5 4 3 2 2 1 X 5 4 3
Sam Siewert 25