Real-Time Embedded Systems (Scheduling)

Question 1

What is a real-time system?

Answer 1

• information processing activity which has to respond to externally generated input stimuli within a specified period otherwise risks severe consequences, including failure

Question 2

How is the correctness of a real-time system based on?

Answer 2

• correctness of outputs

- timeliness

Question 3

Difference soft and hard deadline?

Answer 3

• hard: when not meeting deadline, results in a catastrophe

- soft: any other deadline (does not cause harm when not met)

Question 4

What is a reactive system?

Answer 4

• continuous interaction with the environment (as opposed to information processing)

Question 5

What is a safety-critical system?

Answer 5

• a failure may cause injury, loss of lives, significant financial loss

Question 6

What is an embedded system?

Answer 6

• computer system encapsulated in its environment
• combination of hardware and software
• dedicated to a specific purpose

Question 7

When designing a digital process controller the sampling time T plays an important role. Elaborate on the size of T.

Answer 7

• 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

Question 8

Approaches: Real time vs. best effort?

Answer 8

• best effort = low average time

- real time = predictability, bounded worst case time

Question 9

What is the Worst-Case-Execution-Time (WCET)?

Answer 9

Upper bounds of execution times of all tasks (must be known at compile time)

Question 10

Define Predictability

Answer 10

• 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..)

Question 11

When is a schedule said to be feasible?

Answer 11

• if all tasks can be completed according to a set of specified constraints (ie. deadlines)

Question 12

When is a set of tasks said to be schedulable?

Answer 12

• if there exists at least one feasible schedule

Question 13

Define Release-time and Execution-time of tasks

Answer 13

• 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)

Question 14

What is slack-time?

Answer 14

• maximum time a task can be delayed on its activation to complete within its deadline
• slack time = deadline - release time - execution time

Question 15

What is lateness?

Answer 15

• represents delay of task completion with respect to its deadline
• if task completes before deadline, lateness is negative
• lateness = finishing time - deadline

Question 16

Define Start-time and Finishing-Time

Answer 16

• 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)

Question 17

Define Static and Dynamic scheduling algorithms

Answer 17

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

Question 18

EDF Scheduling Algorithm? Optimal?

Answer 18

• 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

Question 19

Modified EDF Scheduling Algorithm?

What is modified ?

Answer 19

• 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!

Question 20

RM Scheduling Algorithm?

Answer 20

• Rate Monotonic Scheduling
• periodic scheduling for inependent tasks
• no precedence constraints
• deadlines equal periods
• smallest period equals highest priority
• static priorities

Question 21

DM Scheudling

Answer 21

• Deadline Monotonic Scheduling
• same as RM but deadlines can be different from periods
• tasks with shorter deadlines have higher priorities (relative deadlines)

Question 22

What is the scheduability test (for EDF)?

Answer 22

• 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

Question 23

Pros and Cons of EDF?

Answer 23

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

Question 24

How is the CPU Utilization U defined? What means U<1 and U>1?

Answer 24

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)

Question 25

Scheduability test for RM?

Answer 25

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.

Question 26

Pros and Cons of RM?

Answer 26

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