Tesla version 2025.32.3 (Software update)
Tesla is now rolling out its latest software
update (version 2025.32.3) to Model 3
and Model Y, the two most popular Tesla
models in Norway.
The update means that Tesla uses its
Vision camera system to activate the
airbags in the front of the car - before a
possible accident occurs.
Tesla claims that their new solution
increases safety by activating the airbags
earlier than traditional systems, but the
news is causing a stir among both
owners and other users on social media.
Earliest Deadline First (EDF)
*The runnable tasks are executed in the order determined by
the absolute deadlines of the tasks
* - Denoted by symbol d (remember D is relative deadline of the task)
*The next task to run being the one with the shortest (nearest)
deadline
*Although it is usual to know the relative deadlines of each task
(e.g. 25ms after release), the absolute deadlines are computed
at run time and hence the scheme is described as dynamic
Aims
To look at how EDF scheduled systems are analysed
We introduce:
1. Processor Demand Analysis (PDA)
2. Quick Processor Demand Analysis (QPA)
EDF Scheduling
Always run task with earliest absolute deadline
* Task with relative deadline D, released at time s, has
absolute deadline (d) of s+D
* Will consider
* Utilisation based tests
* Processor demand criteria
* Quick Processor demand Analysis (QPA)
* Blocking
* Servers
Utilization-based Test for EDF
sum(i=1, N) C.i/T.i <= 1
(a much simpler test than that for FPS)
*Superior to FPS (0.69 bound in worst-case); it can support high utilizations.
However,
* Bound only applicable to simple task model
* Although EDF is always as good as FPS, and usually better
* For D < T there is a simple sufficient test:
sum(i=1, N) C.i/D.i <= 1
Fixed Priority
Scheduling(FPS) vs
Earliest Deadline
First (EDF)
- FPS is easier to implement as priorities are static
- EDF is dynamic and requires a more complex run-
time system which will have higher overhead - It is easier to incorporate tasks without deadlines
into FPS; giving a task an arbitrary deadline is more
artificial - It is easier to incorporate other factors into the
notion of priority than it is into the notion of
deadline
FPS v EDF
- During overload situations
- FPS is more predictable; Low priority tasks miss their deadlines first
- EDF is unpredictable; a domino effect can occur in which a large number
of tasks miss deadlines - But EDF gets more out of the processor!
Schedulability
For D < T, Deadline Monotonic Priority Ordering (DMPO) is optimal
Schedulability
* From a schedulability point of view EDF is always
better (or as good as) Fixed Priority scheduling
* For single processor
* For most task model
* Proof: similar to proof that Deadline Monotonic
priority assignment is optimal *
1. Start with layout of task execution from a
successful priority ordering (ie one that leads
to success)
2. Transpose into EDF order
3. Show that schedulability is retained
For D < T, Deadline Monotonic Priority Ordering (DMPO) is optimal
Processor
Demand
Analysis for
EDF
Arbitrary EDF system
(D less than or greater than T) is schedulable if:
- Load at time t is less than t, for all t
-There is a bound or how big t needs to be
- Load expressed as h(t)
-Only points in time that refer to actual task deadlines need be checked
= a necessary andsufficient test for EDF
PDA, T=D
At time t the number of jobs that need to be completed is given by
h(t) = sum(i=1, N) [t/T.i]*C.i
-The floor function gives the smaller integer than the fractional number on
which it acts. So the floor of 1/3 is 0, of 6/5 is 1, and of 6/3 is 2.
-So (for N=1), if T=10, t=19 then h(t) = C
If t=20 then h(t) = 2C
If t=21 then h(t) = 2C
PDA – arbitrary Di
h(t) = sum(i=1, N) [t/T.i]*C.i
If D>T then floor function is constrained to have minimum 0
-v-t> 0,h(t) <= t
PDA, D<T
Need to add (T-D) to t to get the right number of releases:
h(t) = sum(i=1, N) [t/T.i]*C.i
So if T=10, D=8, t=17 then h(t) = C
If t=18 then h(t) = 2C
If t=20 then h(t) = 2C
Upper Bound for PDA
- Need to compute the busy period for all tasks
- Starting together at the same time
- This time is usually fixed at 0
- If no deadline miss in first busy period then none afterwards
Upper Bound for PDA
x^0 = sum (i=1, N) C.i
W^j+1 = sum(i=1, N) [W^j/T.i] * C.i
This is the processor busy period
and is bounded for U no greater than 1
Upper Bound for PDA
l.a = max {D.1…D.N, (sum(i=1, N) T.i-D.i)*C.i/T.i)/1-U
U is the utilisation of the task set, note upper bound not defined for U=1
L = min(L.a, L.b)
Examples
fig (side 17 & 18 & 19)
QPA Test
- Refers to Quick Processor demand Analysis (QPA)
- Start at L, and work backwards towards 0 checking only a necessary
subset of the deadlines, L = t, h(t) = h(h(t))
1. If at time t, h(t) > t then unschedulable
2. else let t equal h(t) - If h(t) = t then let t equal t-1 (or largest absolute deadline < t)
3. If t < smallest D, then schedulable - Typically QPA requires only 1% of the effort of PDA but is equally
necessary and sufficient
Example - PDA
fig side 21
EDF and Blocking
When considering shared resources and blocking, there is a direct analogy between RDF and FPS. Where FPS suffers priority inversion, EDF suffers deadline inversion. This is when a task requires a resource that is currently locked by another task with a longer deadline.
Not surprisingly inheritance and ceiling protocols have been developed for EDF, but as with earlier comparisons, the EDF schemes are somewhat more complex.
Example - QPA
22
fig side 22
EDF and Blocking
Probably thecurrently best known scheme for EDF is Baker’s Stock Resource (SRP)
This works in a very similar way to the immediate ceiling priority protocol
(TCPP) for FPS (indeed SRP influenced the development of ICPP).
Each fask, under SRP, is assigned a preemption level. Preemption levels reflect the relative deadlines of the tasks, the shorter the deadline the higher the preemption level;
,,
When a task is released, it can only preempt the currently executing task if its absolute deadline is shorter and its preemption level is highest ceiling of the currently locked resources.”
EDF and Blocking
the result of applying this protocol is identical to applying ICPP (on a single processor). tasks suffer only a single block(it is as they are released), deadlocks are prevented and a simple formula is available for calculating theblocking time which is represented by the term B. the blocking term, once calculated, can be incorporated intp PDA and QPA:
-v-t > 0 (sum(i=1, N) [t + T.i -D.i]) * C.i + B <= t
* There is a new Deadline-floor protocol that is equivalent to SRP but easier to
implement and understand!
EDF and Servers
- There are equivalent servers under EDF to those defined for FPS: periodic
server, deferrable server and sporadic server - There are also EDF-specific servers
If, for example, an aperiodic task arrives at time 156 and wants 5ms of
computation from a server with budget 2ms and period 10ms.
Task will need 3 allocations, and hence is given an absolute deadline of 186.
EDF scheduling rules are then applied.
Summary
-Utilisation bound for EDF (and Least Laxity) is 1.0.
(100%) for the simple task model
-On a single processor EDF is nearly always better than Fixed Priority dispatching
-General EDF systems can
be analysed by PDA
* All task are analysed together,
checking all deadlines before
end of busy period
-Improved analysis
provided by QPA
* From L to 0 checking only where necessary
-Resource sharing protocols and Servers
also available for EDF
