Mapping of Applications to Execution Platforms

Question 1

What is the preceeding step of mapping?

Answer 1

Specification/Tasks

Question 2

What is the task of mapping (general)?

Answer 2

• find a mapping of applications to processors
• appropriate scheduling techniques (if not fixed)
• find a target architecture
  other objectives:
• keeping deadlines / maximize performance
• minimize cost / energy consumption

Question 3

Real-time scheduling? what are typical constraints?

Answer 3

• find a mapping of tasks on a timeline

- resource constraint, dependency constraints, deadlines

Question 4

Difference between hard and soft deadlines?

Answer 4

Hard: violating deadline results in catastrophe
Soft: All other time constraints

Question 5

There are periodic, aperiodic tasks. What are sporadic tasks?

Answer 5

Tasks requesting the processor at unpredictable times are called sporadic, if there is a minimum speration between the times at which they request the processor

Question 6

Preemptive vs non-preemptive schedulers?

Answer 6

• preemptive: tasks can be interrupted while running -> good when responsetime to external event have to be short or some task have ling execution times
• non-preemptive: tasks always run to completion -> response time for external events may be long

Question 7

What is a time-triggered system? (implementation level, adv. / disadv.)

Answer 7

• static scheduling, a dispatcher is activated by the synchronized clock tick. It uses the Task-Descriptor List (TDL) and performs the action that has been planned
• advantage: easy to check if timing constraints are met
• disadvantage: response to sporadic event may be poor

Question 8

What is lateness?

Answer 8

lateness = (completion time - deadline)

typical cost function for scheduling: minimize lateness

Question 9

Difference: absolut and relative deadlines?

Answer 9

Absolut Deadlines: absolut time, ‘wallclock’-time

Relative Deadlines: refers to a relative starting point of a task

Question 10

What is laxity / slack?

Answer 10

It is the spare/buffer time between finishing a task and the deadline ( I = deadline - WCET )

Question 11

What is the EDD scheduling?

Answer 11

• Earliest Due Date (EDD): execute task with earliest due date (deadline) first for non-periodic tasks wanting to start at same time-instance
• it is optimal in respect to minimizing the maximum lateness (Jackson’s Rule)

Question 12

What is scheuling by EDF opposed to EDD?

Answer 12

• Earliest Deadline First Algorithm (opposed to Earliest Due Date) is for the dynamic case (not all task want to execute at the beginning)
• each time a new ask wants to execute it is inserted into a queue which is sorted by their absolute deadlines
• the currently running task might get preempted

Question 13

What is scheduling by LL or LST?

Answer 13

• aperiodic tasks
• scheduling with priority on minimizing least laxity (LL) or least slack time first (LST)
• Calculated by: deadline - current time - execution time left for task
• for running task the slack time does not change, for all inactive task the slack time decreases

Question 14

Properties of LL/LST?

Answer 14

• big overhead (constantly computing laxity and calls for scheduler)
• many context switches
• detects missed deadlines early
• is also an optimal scheduling for mono-processor systems
• dynamic priorities -> cannot be used on fixed-priority OS

Question 15

How is ‘optimality’ for periodic tasks defined?

Answer 15

A scheduler is defined to be optimal if it will find a schedule if one exist

Question 16

Necessary conditions for utilization of a processor (for real time systems)?

Answer 16

• the utilization must be smaller than the number of processors with U = sum( job_time/job_period)

Question 17

Rate-Monotonic scheduling, Assumptions?

Answer 17

• all task that have hard deadlines are periodic
• all tasks are independent
• d = p for all tasks
• c (tasktime) is constant and is known
• time for context switching is negligible

u = sum( c / p ) < n*(2^(1/n) - 1) = average utilization, lower than this value -> RM finds schedule

Question 18

Rate-Monotonic policy for scheduling?

Answer 18

• the task with shortest period has highest priority (static priorities)
• lower priority tasks squeeze in between the time of the highest priority task
• works only if utilization is low enough

Question 19

Rate-Monotonic: What is the worst case when task shall be scheduled? What is that case called?

Answer 19

It is called a critical instant of a task. It happens when the task is released which results in the largest response time.

• > for any task the critical instant occurs if that task is simultaneously released with all higher-priority tasks
  (ie. All task starting at time 0 is the worst case scenario)

Question 20

How is scheduability with Rate-Monotonic checked?

Answer 20

• Scheduability is checked at the critical instants

- if all tasks are are scheduable at their critical instants, they are schduable at all release times

Question 21

EDF vs RMS?

Answer 21

EDF has dynamic priorities while RMS has static priorities.
EDF can only be used in OS which allow dynamic priorities. EDF also uses the full computational power of the processor. RMS just up to
U = sum( c / p ) < n*(2^(1/n) - 1) -> there are idle times

Question 22

How to handle sporadic tasks in scheduling?

Answer 22

• if sporadic tasks are connected to interrupts the execution time of other tasks would become unpredicatable
• -> introduction of sporadic task server, periodically checking for sporadic tasks
• -> sporadic tasks turned into periodic tasks