Real-Time Embedded Systems (Scheduling) Flashcards
What is a real-time system?
- information processing activity which has to respond to externally generated input stimuli within a specified period otherwise risks severe consequences, including failure
How is the correctness of a real-time system based on?
- correctness of outputs
- timeliness
Difference soft and hard deadline?
- hard: when not meeting deadline, results in a catastrophe
- soft: any other deadline (does not cause harm when not met)
What is a reactive system?
- continuous interaction with the environment (as opposed to information processing)
What is a safety-critical system?
- a failure may cause injury, loss of lives, significant financial loss
What is an embedded system?
- computer system encapsulated in its environment
- combination of hardware and software
- dedicated to a specific purpose
When designing a digital process controller the sampling time T plays an important role. Elaborate on the size of T.
- smaller T approximates analogue behavior better
- but smaller T requires more processor-time and better ADC hardware
- hardware must guarantee that all conversions and processing is possible in time T
Approaches: Real time vs. best effort?
- best effort = low average time
- real time = predictability, bounded worst case time
What is the Worst-Case-Execution-Time (WCET)?
Upper bounds of execution times of all tasks (must be known at compile time)
Define Predictability
- Correctness of prediction of system’s state
- one of most important requirements of ES
- in modern processors harder to achieve (caches, pipelines, branch prediction, interrupt handling, priority inversion of tasks..)
When is a schedule said to be feasible?
- if all tasks can be completed according to a set of specified constraints (ie. deadlines)
When is a set of tasks said to be schedulable?
- if there exists at least one feasible schedule
Define Release-time and Execution-time of tasks
- Release-time: time at which task becomes ready for execution
- execution-time: time necessary for executing task without interruption (in real-time systems only WCET matters)
What is slack-time?
- maximum time a task can be delayed on its activation to complete within its deadline
- slack time = deadline - release time - execution time
What is lateness?
- represents delay of task completion with respect to its deadline
- if task completes before deadline, lateness is negative
- lateness = finishing time - deadline
Define Start-time and Finishing-Time
- Start-time: time at which task starts its execution
- Finishing time: time at which task finishes its execution
(dont judge, this card is just for reasons of completeness)
Define Static and Dynamic scheduling algorithms
Static: Scheduling decisions are based on fixed parameters, assigned to task before their activation
Dynamic: Scheduling decision are based on dynamic parameters that may change during execution
EDF Scheduling Algorithm? Optimal?
- Earliest Deadline First
- aperiodic tasks (and also periodic in some cases)
- priorities based on deadlines (earliest highest prority)
- arbitrary arrival timesof tasks
- independent tasks (ie. no precedence constraints)
Guarantee: If a set of tasks has a feasible schedule, then EDF will schedule these tasks so they complete by their deadline
And schedule is optimal with respect to minimizing maximum lateness
Modified EDF Scheduling Algorithm?
What is modified ?
- EDF*
- with precedence constraints
- turns a set of dependent tasks J into a set of independent tasks J*
- Apply EDF to J*
Modified can be following:
- release times -> tasks must not start execution ealier than minimum finishing time of its predecessors and its own release time ri=max(ri , sum(ri-1+ei-1))
From start to end!
- deadlines -> tasks must finish execution time within its deadline and task must not finish execution later than maximum start time of its successor di=min(di, (di+1-ed+1))
From end to start!
RM Scheduling Algorithm?
- Rate Monotonic Scheduling
- periodic scheduling for inependent tasks
- no precedence constraints
- deadlines equal periods
- smallest period equals highest priority
- static priorities
DM Scheudling
- Deadline Monotonic Scheduling
- same as RM but deadlines can be different from periods
- tasks with shorter deadlines have higher priorities (relative deadlines)
What is the scheduability test (for EDF)?
- assume a list of job which already has a feasible schedule [Jobs j1, j2, j3]
- a new job arrives at time t with execution time c
- if the finish time of already scheduled tasks + execution time of new task is smaller than the deadline it is scheduable
Pros and Cons of EDF?
Pros: - simple and works nicely in theory - simple scheduability test - optimal - best cpu utilization Cons: - difficult to implement in practice. Not very often adopted due to Dynamic priority assignment - non stable: if any instance fails to meet dealine the system is not predictable, any instance of any task may then fail
How is the CPU Utilization U defined? What means U<1 and U>1?
U = E / P
- > ratio of period and execution time E
- set of tasks adds up all Utilizations sum(Ui)
- U <= 1 does not imply scheduability, depends on algorithm (for EDF it is always scheduable)
- U > 1 (overload) some task will fail to meet deadline (always)
Scheduability test for RM?
U <= n*(2^(1/n) - 1) with n is number of tasks
- U converges to 0.69 with n -> infinity
utilization is smaller than scheduable boundary it is scheduable with RM. Otherwise a clear maybe.
Pros and Cons of RM?
Pros: - simple to understand - easy to implement, static prority assignment - stable though some of the lower priority tasks fail to meet deadlines others may meet deadlines Cons: - lower CPU utilization than EDF - requires D=P - only deals with independent tasks
