Reconfigurable computing
Small Embedded Systems
Unit 5.9 Priority Assignment for Real Time Systems
Introduction
An RTOS requires that tasks be assigned a priority
Approaches to Prioritisation
Rate monotone scheduling
Conditions under which correctness is guaranteed
How are Task Priorities Chosen?
Analysis is normally based on periodic tasks
Key parameters:
n: number of tasks that have a real time requirement
Ci: worst case execution time of task i
Di: time from trigger to deadline for task i
Ti: time between triggers for task i
trigger1
time
Task A running
Task A running
Task A idle
Task A idle
deadline1
trigger2
deadline2
trigger3
TA
DA
CA
How are Task Priorities Chosen?
Analysis is normally based on periodic tasks
Key parameters:
n: number of tasks that have a real time requirement
Ci: worst case execution time of task i
Di: time from trigger to deadline for task i
Ti: time between triggers for task I
A key figure that helps the scheduler is:
Ui: utilization: the fraction of the available time Di that is required for Ci, the worst case execution time of task i
How are Task Priorities Chosen?
To keep the analysis simple, we assume that the deadline for a task is equal to the next trigger point
Most periodic real time systems have this property
trigger1
time
Task A running
Task A running
Task A idle
Task A idle
TA
deadline1
trigger2
deadline2
trigger3
DA
Scheduling Example
Suppose we have only one task to execute:
Task 1:
Triggers at 3 ms intervals
Requires 1 ms computation time to get its result
Utilisation is 1/3 = 0.33
The graph shows which task the processor is executing:
Task 1
Idle
3
Time (ms)
6
9
12
15
Scheduling Example
Suppose we have only one task to execute:
Task 2:
Triggers at 15 ms intervals
Requires 5 ms computation time to get its result
Utilisation is 5/15 = 0.33
The graph shows which task the processor is executing:
Idle
3
Time (ms)
6
9
12
15
Task 2
Scheduling Example
Now suppose that task 1 and task 2 have to run on the same processor
If we have a naïve schedule and let each task run to completion, we have:
The second time task 1 executed it missed its deadline
Task 2 had and kept the processor, even though it was nowhere near its deadline
Task 1
Idle
3
Time (ms)
6
9
12
15
Task 2
Deadline missed
Scheduling Example
Suppose we give the scheduler the ability to switch one task out before it has finished in order to give the processor to another task:
Pre-emptive scheduling
Which task has the right to pre-empt another task?
Priority based scheduling
Task 1
Idle
3
Time (ms)
6
9
12
15
Task 2
Task 2 switched out
All tasks meet all deadlines
Priority Assignment
We can see intuitively that task 1 had a “greater need” for the processor
How do we systematize that intuition?
Task 1
Idle
3
Time (ms)
6
9
12
15
Task 2
Task 2 switched out
Priority Assignment
We can see intuitively that task 1 had a “greater need” for the processor
How do we systematize that intuition?
Two main approaches:
Static priority scheduling
Priorities are fixed at outset and don’t change
Rate monotonic: tasks are ranked by their trigger frequency: highest frequency gets top priority
Dynamic priority scheduling
Priorities change during execution
Earliest deadline first: Whichever task has the nearest deadline gets top priority
Which task that is can change from cycle to cycle
Rate Monotone Scheduling
Milestone in the development of real time systems
Provides a set of conditions under which it is mathematically provable that a schedule will be found
The condition is sufficient but not necessary:
If the condition is met, the problem is schedulable and a correct schedule will be found by RMS
If the condition is not met then the problem may or may not be schedulable
Rate Monotone Scheduling
For a set of n periodic tasks with deadline equal to trigger period, the schedule is guaranteed to exist and will be found by the RMS scheduler if
Priority is set according to trigger rate
(highest rate = top priority)
Sum of task utilisations is below a threshold given by:
n: number of tasks that have a real time requirement
Ci: worst case execution time of task i
Ti: time between triggers for task i
Rate Monotone Scheduling
For large n, this tends to a limit of ln(2) = 0.69
Rate Monotone Scheduling Example
3 tasks are to be scheduled
Worst case execution time C and trigger period T are:
Assign priorities according to rate (1/T)
Task C T Priority U
1 20 90
2 30 150
3 75 350
Rate Monotone Scheduling Example
3 tasks are to be scheduled
Worst case execution time C and trigger period T are:
Assign priorities according to rate (1/T)
Compute utilisation for each task (C/T)
Task C T Priority U
1 20 90 Top
2 30 150 Medium
3 75 350 Lowest
Rate Monotone Scheduling Example
3 tasks are to be scheduled
Worst case execution time C and trigger period T are:
Assign priorities according to rate (1/T)
Compute utilisation for each task (C/T)
Sum utilisation of the tasks
Utotal = 0.222+0.200+0.214 = 0.636
Compare to guarantee threshold
Task C T Priority U
1 20 90 Top 0.222
2 30 150 Medium 0.200
3 75 350 Lowest 0.214
Rate Monotone Scheduling Example
3 tasks are to be scheduled
Worst case execution time C and trigger period T are:
Utotal = 0.222+0.200+0.214 = 0.636
Full calculation of guarantee bound (n=3 tasks):
Easy-to-remember guarantee bound:
No matter how many tasks, ln(2) = 0.69
Task C T Priority U
1 20 90 Top 0.222
2 30 150 Medium 0.200
3 75 350 Lowest 0.214
Specialist processors for real time systems
Some manufacturers provide processors that are aimed at real time safety critical systems
Example: ARM Cortex-R series
Features include:
Dual core lockstep CPUs
Processing of instructions is duplicated across two CPUs and the results compared
Provides fault tolerance (parallel reliability)
Specialist processors for real time systems
Some manufacturers provide processors that are aimed at real time safety critical systems
Example: ARM Cortex-R series
Features include:
Tightly coupled memory
Region of fast SRAM memory whose access time does not vary. Variables needed by critical routines are placed here.
This contrasts with a cache memory hierarchy, whose access time is fast if data is in cache or slow if not. Whether or not data is in cache is not predictable a priori.
Real time systems must plan for worst case execution time. Memory that is sometimes fast is no help.
Summary
An RTOS requires that tasks be assigned a priority
Rate monotone scheduling is a simple mechanism to select task priority and provides mathematical guarantees for certain classes of real time system
/docProps/thumbnail.jpeg