Basic Concepts

Question 1

What is real-time systems?

Answer 1

A real-time system is a system that reacts to events in the environment by performing predefined actions within specified time intervals.

Question 2

What the “time” part of real-time means?

Answer 2

The correctness of the system depends not only on the logical result of the computation but also on the time at which the results are produced.

Question 3

What the “real” part of real-time means?

Answer 3

It indicates that the reaction of the systems to external events must occur during their evolution. As a consequence, the system time (internal time) must be measured using the same time scale used for measuring the time in the controlled environment (external time).

Question 4

Which are the three real-time tasks categories?

Answer 4

• Hard: if producing the result after deadline may cause catastrophic consequences on the system under control.
• Firm: if producing the result after its deadline is useless for the system, but does not cause any damage.
• Soft: if producing the results after its deadline has still some utility for the system, although causing a performance degradation.

Question 5

Cite examples of hard real-time tasks.

Answer 5

Safety-critical systems tasks:

• sensory data acquisition;
• data filtering and prediction;
• data fusion and image processing;
• actuator servoing;
• low-level control of critical system components;
• action planning for systems that toghtly interact with the environment.

Question 6

Cite examples of firm real-time tasks.

Answer 6

Networked applications and multimedia systems tasks:

• video playing;
• audio/video encoding and decoding;
• on-line image processing;
• sensory data transmission in distributed systems.

Question 7

Cite examples of soft real-time tasks.

Answer 7

Tasks related to system-user interactions:

• the command interpreter of the user interface;
• handling input data from the keyboard;
• displaying messages on screen;
• representation of system state variables;
• graphical activities;
• saving report-data.

Question 8

The correctness of the result in real-time systems depends on…

Answer 8

value and its time of delivery.

Question 9

Speed of real-time system depends on…

Answer 9

environment and nature.

Question 10

When real-time is needed and standard computing can’t attend the demand?

Answer 10

When fast processing, average and performance testing are not enough, and the worst case needs guarantees. Be on time, all the time and proof it.

Question 11

What are the basic proprieties of real-time systems should have?

Answer 11

Timeliness (result correct in time), predictability (the consequences of systems behavior should be predictable for any scheduling decision), efficiency, robustness, fault-tolerant, maintainability.

Question 12

Which is the temporal definition of a periodic task?

Answer 12

Temporal definition of periodic tasks:

• Ti = period of task i
• Ri = release time, relative from start of period time at which task i may start to execute
• Di = deadline interval, relative from start of period time at which task i must be completed
• Ci = worst case execution time

Question 13

Define utilization.

Answer 13

Utilization is a portion of CPU used by the execution of a task set.

Ui = Ci/Ti

Utilization of a task set is the sum of all individual tasks utilization.

Question 14

What is active task?

Answer 14

It is a task that can potentially execute on the processor independently on its actual availability.

Question 15

What is a ready task?

Answer 15

Task ready is a task waiting for the processor.

Question 16

What is a running task?

Answer 16

Running task is a task in execution.

Question 17

What is preemption?

Answer 17

Preemption is the operation of suspending the running task and inserting it into the ready queue.

Question 18

What is the importance/advantages of preemption?

Answer 18

1. Tasks performing exception handling may need to preempt existing tasks so that responses to exceptions may be issued in timely fashion.
2. When tasks have different levels of criticality (expressing task importance), preemption permits executing the most critical tasks as soon as they arrive.
3. preempting scheduling typically allows higher efficiency, in the sense that it allows executing a real-time task sets with higher processor utilization.

Question 19

What are the disadvantages of preemption?

Answer 19

Preemption destroys program locality and introduces a runtime overhead that inflates the execution time of tasks.

Question 20

What is a feasible schedule?

Answer 20

A schedule is feasible if all tasks can complete meeting their constraints (ex. deadline).

Question 21

What is a schedulable task set?

Answer 21

A task set is schedulable if there exists at least one algorithm that can produce a feasible schedule.

Question 22

What is a feasible task set?

Answer 22

It does not exist. There are feasible schedule or scheadulable task set but no feasible task set.

Question 23

Which is the necessary schedulability condition?

Answer 23

U <=1
If it does not hold, it is not schedulable.
If it holds, it can or cannot be schedulable.

Question 24

What the Graham Theorem says?

Answer 24

If a task set is optimally scheduled on a multiprocessor with some priority assignment, a fixed number of processors, fixed execution times, and precedence constraints, then increasing the number of processors, reducing execution times, or weakening the precedence constraints can increase the schedule length.

Question 25

Shows an example of scheduling anomalie

Answer 25

``` J1(3) J9(9) J2(2) J8(4) [depends on J4] J3(2) J7(4) [depends on J4] J4(2) J6(4) [depends on J4] J5(4) [depends on J4] Three processors: optimal schedule ``` * increasing number of processors: 4 processors -> schedule length increases * computation times reduced: reduced by 1 unit of time -> schedule length increases * precedence constraints weakened: remove precedence on tasks 7 and 8 -> schedule length increases

Question 26

What is schedule?

Answer 26

Schedule is an assignment of a given set of tasks to the | processor, so that each task is executed until completion.

Question 27

What is the difference between necessary and sufficient schedulability condition?

Answer 27

Necessary condition: If it does NOT hold, the task set is not schedulable. If it holds, we can't say anything. It can or cannot be schedulable. Sufficient condition: If it HOLDS, the task set is schedulable. If it does not hold, we can't say anything. It can or cannot be schedulable.

Question 28

What is the difference between fixed and dynamic priority scheduling? Explain them.

Answer 28

Fixed Task Priority Scheduling: each task has its own priority and it is the same during its lifetime. Dynamic Task Priority Scheduling is when tasks priorities may change during their lifetime. There are two types of Dynamic task priority, as follows: 1. Fixed Job Priority: jobs of one task may have different priorities, but each job has single fixed priority. 2. Dynamic Job Priority: Job priority may change over time.

Question 29

What is the decision mode on First Come First Served (FCFS) algorithm? Which job has the highest priority?

Answer 29

The decision mode is non-preemptive - -----------------------|(-----------)-----------------------------> t1 - ------------------------------|-----(-------)---------------------> t2 - ---------------------------------|------------(---)---------------> t3 - ----------------------------------|----------------(----------)---> t4 Highest priority job is the one which has been longest in ready queue.

Question 30

What is the decision mode on Round Robin (RR) algorithm? Which job has the highest priority?

Answer 30

The decision mode is preemptive - ----------------|(--)(--)----(--)-------> t1 - ----------------------|---(--)---------> t2 - ---------------------------|------(--)-> t3 All jobs have the same priority.

Question 31

At which point in time does the scheduler select the next executing job for non-preemptive scheduling?

Answer 31

There are no jobs in the ready queue: at job release. | There are jobs in the ready queue: at job completion.

Question 32

At which point in time does the scheduler select the next executing job for preemptive scheduling?

Answer 32

There are no jobs in the ready queue: at job release There are jobs in the ready queue: - at job release - at job completion - timer event (e.g. RR, offline scheduling table...)