Mapping of Applications to Execution Platforms Flashcards
What is the preceeding step of mapping?
Specification/Tasks
What is the task of mapping (general)?
- 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
Real-time scheduling? what are typical constraints?
- find a mapping of tasks on a timeline
- resource constraint, dependency constraints, deadlines
Difference between hard and soft deadlines?
Hard: violating deadline results in catastrophe
Soft: All other time constraints
There are periodic, aperiodic tasks. What are sporadic tasks?
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
Preemptive vs non-preemptive schedulers?
- 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
What is a time-triggered system? (implementation level, adv. / disadv.)
- 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
What is lateness?
lateness = (completion time - deadline)
typical cost function for scheduling: minimize lateness
Difference: absolut and relative deadlines?
Absolut Deadlines: absolut time, ‘wallclock’-time
Relative Deadlines: refers to a relative starting point of a task
What is laxity / slack?
It is the spare/buffer time between finishing a task and the deadline ( I = deadline - WCET )
What is the EDD scheduling?
- 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)
What is scheuling by EDF opposed to EDD?
- 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
What is scheduling by LL or LST?
- 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
Properties of LL/LST?
- 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
How is ‘optimality’ for periodic tasks defined?
A scheduler is defined to be optimal if it will find a schedule if one exist
Necessary conditions for utilization of a processor (for real time systems)?
- the utilization must be smaller than the number of processors with U = sum( job_time/job_period)
Rate-Monotonic scheduling, Assumptions?
- 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
Rate-Monotonic policy for scheduling?
- 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
Rate-Monotonic: What is the worst case when task shall be scheduled? What is that case called?
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)
How is scheduability with Rate-Monotonic checked?
- Scheduability is checked at the critical instants
- if all tasks are are scheduable at their critical instants, they are schduable at all release times
EDF vs RMS?
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
How to handle sporadic tasks in scheduling?
- 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
