17. Real-Time Scheduling Flashcards
1
Q
Cyber-Physical Systems
A
- Sense the physical world with sensors
- Perform sensor fusion and enact a control strategy
- Use actuators to interact with the physical world
2
Q
Safety-Critical System
A
- A system that can jeopardize the safety of one or more people
3
Q
Predictability (RTS)
A
- The difference between a system’s BCET and WCET
- A system is more predictable if WCET - BCET is small
4
Q
Tardiness
A
- The difference between the completion of a real-time job and its deadline
5
Q
Utilization Bound
A
- The cap after which adding a new job in the system will lead to some job missing its deadline
6
Q
Real-Time Task Model
A
- T_i: the period at which a new job of a task tau_i is released
- C_i: the WCET of a job of task tau_i
- D_i: the deadline of a job of task tau_i relative to its release time (assumed D_i = T_i)
7
Q
Static Priority Scheduling
A
- Statically assign a priority to each task tau_i in the system
8
Q
Rate Monotonic Scheduling (RM)
A
- Invocation: at the completion of a job or when a new job is released (preemptive)
- Policy: select the job with the shortest period
9
Q
RM Schedulability Test
A
- An m-task set is schedulable under RM if the sum of the ratios of WCET / period <= m * (2^{1/m} - 1)
- If the condition does not hold, the test yields no conclusion
- Any task-set with utilization <= ln(2) or ~0.69 is schedulable under RM
10
Q
Dynamic Priority Scheduling
A
- Re-compute task priorities at the occurrence of scheduling events
11
Q
Earliest Deadline First (EDF)
A
- Invocation: at the completion of a job or when a new job is released (preemptive)
- Policy: select the job with the closest deadline
- Optimal for preemptive real-time tasks on a single processor
12
Q
EDF Schedulability Test
A
- A task-set is schedulable under EDF if the sum of the ratios of WCET / period <= 1
13
Q
Flaw of EDF
A
- The behavior of EDF is undefined if the job has already missed its deadline
