Process Timing Requirements
Period: interval between process activations.
Initiation interval: reciprocal of period.
Initiation time: time at which process becomes ready.
Deadline: time at which process must finish.
Timing violations.
What happens if a process doesn’t finish by its deadline?
Hard deadline: system fails if missed.
Soft deadline: user may notice, but system doesn’t necessarily fail.
Example: Space Shuttle software error A software timing error
delayed shuttle’s first launch:
• Primary control system PASS and backup system BFS.
• BFS failed to synchronize with PASS.
• Change to one routine added delay that threw off start time calculation.
• 1 in 67 chance of timing problem.
© G. Khan COE718: Embedded System Design – Real-time Scheduling Page: 11
Process Model
• The application is assumed to consist of a fixed set of
processes.
• Processes are completely independent of each other.
• All system's overheads, context-switching times and so
on are ignored (i.e. assumed to have zero cost)
• All processes are periodic, with known periods.
• All processes have a deadline equal to their period
(that is, each process must complete before
it is next released)
• All processes have a fixed worst-case execution time.
© G. Khan COE718: Embedded System Design – Real-time Scheduling Page: 12
Scheduling Periodic & Aperiodic Tasks
Aperiodic Task Scheduling
Periodic Task Scheduling
© G. Khan COE718: Embedded System Design – Real-time Scheduling Page: 13
Real-time Scheduling Techniques
• Fixed-Priority Scheduling (FPS)
• Earliest Deadline First (EDF)
FPS: Fixed-Priority Scheduling
▪ This is the most widely used approach.
▪ Each process has a fixed, (static) priority that is computed
before execution.
▪ The runnable processes are executed in the order
determined by their priority.
▪ In real-time systems, the “priority” of a process is derived
from its temporal requirements, not its importance to the
correct functioning of the system or its integrity.
© G. Khan COE718: Embedded System Design – Real-time Scheduling Page: 14
FPS: Fixed-Priority Scheduling
Rate Monotonic Priority Assignment
• Each process is assigned a (unique) priority based on its
period; the shorter the period, the higher the priority
• For two processes i and j:
T i T j Pi P j
• An optimal priority assignment means: if any process set
can be scheduled (using preemptive priority-based
scheduling) with a fixed-priority assignment scheme,
then the given process set can also be scheduled with a
rate monotonic assignment scheme
• Priority 1 is the lowest (least) priority
© G. Khan COE718: Embedded System Design – Real-time Scheduling Page: 15