12-04-2012, 01:16 PM
Real-Time Scheduling
Real-Time Scheduling.ppt (Size: 1.3 MB / Downloads: 291)
Outline
Real-time systems
Real-time scheduling algorithms
Fixed-priority algorithm (RM)
Dynamic-priority algorithm (EDF)
Real-Time Systems
Definition
Systems whose correctness depends on their temporal aspects as well as their functional aspects
Performance measure
Timeliness on timing constraints (deadlines)
Speed/average case performance are less significant.
Key property
Predictability on timing constraints
Real-Time Workload
Job (unit of work)
a computation, a file read, a message transmission, etc
Attributes
Resources required to make progress
Timing parameters
Real-Time Task
Task : a sequence of similar jobs
Periodic task (p,e)
Its jobs repeat regularly
Period p = inter-release time (0 < p)
Execution time e = maximum execution time (0 < e < p)
Utilization U = e/p
Deadlines: Hard vs. Soft
Hard deadline
Disastrous or very serious consequences may occur if the deadline is missed
Validation is essential : can all the deadlines be met, even under worst-case scenario?
Deterministic guarantees
Soft deadline
Ideally, the deadline should be met for maximum performance. The performance degrades in case of deadline misses.
Best effort approaches / statistical guarantees
Schedulability
Property indicating whether a real-time system (a set of real-time tasks) can meet their deadlines
Real-Time Scheduling
Determines the order of real-time task executions
Static-priority scheduling
Dynamic-priority scheduling
RM (Rate Monotonic)
Optimal static-priority scheduling
It assigns priority according to period
A task with a shorter period has a higher priority
Executes a job with the shortest period