This page was generated using an imperfect translator. Text may be poorly positioned and mathematics will be barely readable. Illustrations will not show at all. If possible, view the PostScript or PDF versions of these notes.
17-1 Scheduling *
* 17-1
Goal: assign priorities so that deadlines met.
Outline:
Rate monotonic priority assignment.
Hand priority assignment.
Static scheduling for a cyclic executive.
Source
Burns & Wellings, "Real-Time Systems and Programming Languages," second edition. New
York: Addison-Wesley, 1997, chapter 13, pp. 399-440.
17-1 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from l*
*sli17. 17-1
17-2 *
* 17-2
Definitions
Scheduling is said to be effective if it guarantees deadlines will be met.
A system is called pure periodic if
- all events are periodic
- all events' deadlines are equal to their period
- worst-case execution times are available for all event handlers.
A distinct priority assignment is one in which no two events have same priority.
17-2 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from l*
*sli17. 17-2
17-3 Rate Monotonic Priority Assignment (RMPA) *
* 17-3
Method for assigning priorities with goal of meeting deadlines.
Rate monotonic priority assignment does not_ guarantee deadlines will be met.
A pure periodic system has a rate monotonic priority assignment when
- each event triggers an interrupt at a distinct strong priority level
- priority order is the same as frequency order
(highest priority has shortest period, etc.).
17-3 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from l*
*sli17. 17-3
17-4 Rate Monotonic Priority Assignment Example *
* 17-4
Assign priorities using RMPA for the pure-periodic events described in the table be-
low:
Event Handler Event
Name_____Run_Time_____Period____
A 5 s 30 s
B 4 s 22 s
C 30 s 100 s
Rate Monotonic Priority Assignment:
Event Handler Event Strong
Name_____Run_Time_____Period____Priority___
A 5 s 30 s 2
B 4 s 22 s 3
C 30 s 100 s 1
17-4 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from l*
*sli17. 17-4
17-5 *
* 17-5
Effectiveness of Rate Monotonic Priority Assignment
RMPA is not effective on all pure periodic systems.
Two results useful for determining effectiveness:
RMPA is effective iff there exists an effective distinct strong-priority assignment.
That is, if RMPA is not effective : : :
: : :then neither is any other assignment of distinct strong priorities.
17-5 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from l*
*sli17. 17-5
17-6 *
* 17-6
Safe-Load Test: RMPA is effective if the following relation holds:
X th(e) i 1__ j
______< jEj 2 jEj 1 ;
e2E tb(e)
where E is the set of event names (e.g., E = f A; B; C g),
jEj is the number of events (e.g., jEj = 3, called N in class),
th(e) is the handler run time for event e,
and tb(e) is the period of event e.
17-6 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from l*
*sli17. 17-6
17-7 *
* 17-7
Effectiveness Test Examples
Determine if the RMPA scheduling for the pure-periodic events described in the table
below is effective.
Event Handler Event Priority Load
Name_____Run_Time_____Period_________________________
A 5 s 10 s 3 0.5000
B 4 s 12 s 2 0.3333
C 2 s 15 s 1 0.1333
29 ? 1=3
Applying the safe-load test: ___ ss 0:9667 < 3(2 1) ss 0:7798
30
The relation does not hold, therefore RMPA may not be effective in this case.
To determine if it is effective, compute response time by hand:
Response time of C is 20 s, including two A's and two B's.
Since response time exceeds period (its assumed deadline), scheduling not effective.
Because RMPA scheduling is not effective here, no other priority scheme effective.
17-7 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from l*
*sli17. 17-7
17-8 Rate Monotonic Priority Assignment Example II *
* 17-8
Determine if the RMPA scheduling for the pure-periodic events described in the table
below is effective.
Event Handler Event Priority
Name_____Run_Time_____Period_______________
A 5 s 10 s 3
B 4 s 15 s 2
C 6 s 30 s 1
Applying the safe-load test:
29_ ss 0:9667 ?< 3(21=3 1) ss 0:7798
30
As before test fails, meaning must compute response times to determine effective-
ness.
Response time for C is 29 s, 3 A's plus 2 B's.
Response time for B is 9 s.
Response time for A is 5 s.
Since all deadlines met, scheduling effective.
17-8 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from l*
*sli17. 17-8
17-9 Rate Monotonic Priority Assignment Example III *
* 17-9
Determine if the RMPA scheduling for the pure-periodic events described in the table
below is effective.
Event Handler Event Priority
Name_____Run_Time_____Period_______________
A 4 s 10 s 3
B 3 s 15 s 2
C 5 s 30 s 1
Applying the safe-load test:
23_ ss 0:7667 ?< 3(21=3 1) ss 0:7798
30
Test passes, so there is no need to compute response times.
17-9 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from l*
*sli17. 17-9
17-10 Manual Priority Assignment *
* 17-10
Theorem below shows efficient method to search for priority assignments.
Let E be a set of pure periodic events, and L 2 E. Consider all possible distinct
strong priority assignments in which L has the lowest priority. Either L meets its
deadlines in all of these assignments or L meets its deadlines in none of these assign-
ments.
In other words, : : :
: : :the response time of the lowest-priority event : : :
: : :does not change if the other priorities are rearranged.
Application
When assigning priorities by hand, assign lowest priority first.
The event will not affect higher priority events' handlers : : :
: : :and assignment of higher priorities can ignore lowest.
17-10 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from*
* lsli17. 17-10
17-11 *
* 17-11
Static Scheduling
Idea: determine run times in advance.
Static schedule is non-reactive (not reacting to external event).
Plan schedule so that preemption not necessary (maybe not possible).
Result:
Table of handler start times.
Table covers a period of time called a major cycle.
OS starts handlers based on table.
Major cycle designed to repeat.
17-11 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from*
* lsli17. 17-11
17-12 *
* 17-12
Static Scheduling Method
Express periods as integers. (Possibly clock ticks.)
Set table length to least-common multiple (LCM) of periods.1
Put handler start times in table so that deadlines met.
If LCM of periods too large then, if possible, adjust periods : : :
: : :or use dynamic scheduling.
_______________________
1 The LCM of a set of integers is the smallest integer that is a positive multiple of all the *
*integers. For example, LCM f10; 15; 20g = 60 =
6 10 + 4 15 + 3 20.
17-12 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from*
* lsli17. 17-12
17-13 Deadlines and Static Scheduling *
* 17-13
Deadline in a dynamically scheduled system based on event time.
No explicit event time in static system.
For problems in class use an assumed event time:
event e with period tb(e) will occur with period tb(e) : : :
: : :but with whatever phase needed to ensure that deadlines met.
For example, let tb (A) = 10 s.
It might occur at t = 0; 10 s; 20 s; : :o:r t = 1; 11 s; 21 s; : :::: :
: : :or any other phase that would allow deadlines to be met.
This timing assumption is not applied to dynamically scheduled systems : : :
: : :because they can react to external events.
17-13 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from*
* lsli17. 17-13
17-14 Static Scheduling Example *
* 17-14
Compute a static schedule for the following system:
Event Handler Event
Name_____Run_Time______Period___
A 4 s 10 s
B 3 s 15 s
C 5 s 30 s
LCM = 30, so table covers 30 s.
Table:
Time____Action__________________
0 s Start A
4 s Start B
10 s Start A
17 s Start B (2 s early)
20 s Start A
24 s Start C
Note that the second occurrence of B is 2 s early.
17-14 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from*
* lsli17. 17-14
17-15 Static Scheduling Using a Cyclic Executive *
* 17-15
Possible disadvantages of static scheduling as described above:
Large number of timer expirations (specified in table).
A cyclic executive reduces the number of timer interrupts : : :
: : :by running handlers in bunches called bins.
17-15 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from*
* lsli17. 17-15
17-16 Cyclic Executive Bins *
* 17-16
Bin: Code (maybe handler or daemon) that calls event-specific handlers.
These perform function of handlers in earlier problems.
Handlers within a bin run one after the other (without pause).
First handler in bin runs when bin starts, second when first ends, etc.
Notation:
Bin 1: B1 = (A; B; C; A).
Indicates that handlers for A, B, C, and A (again) will run when B1 runs.
Bin 2: B2 = (A; D; A; C).
Indicates that handlers for A, D, A (again), and C will run when B2 runs.
17-16 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from*
* lsli17. 17-16
17-17 Cyclic Executive Bins *
* 17-17
Bin Timing
Bin starts at fixed interval. (Based on OS timer).
Execution of bin called minor cycle.
Time between bin starts also called minor cycle.
Different bins may run in consecutive minor cycles, some may repeat.
For example: B1; B2; B1; B3 (note that B1 used twice.)
Time period in which sequence repeats called a major cycle (as with static schedule).
17-17 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from*
* lsli17. 17-17
17-18 Cyclic Executive Design *
* 17-18
No special method. Use guidelines below.
Minor cycle:
Typically of fixed size (which must divide major cycle).
Longer than longest handler. (May need to divide handlers into parts.)
Try to set minor cycle to greatest common divisor of longer periods.
If major cycle chosen correctly, minor cycle multiple of shorter periods.
17-18 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from*
* lsli17. 17-18
17-19 *
* 17-19
Cyclic Executive Tradeoffs
Advantages of Cyclic Executive
- Easier to assure timing than dynamic scheduling.
- Fewer interrupts or other scheduler actions needed than ordinary static schedul-
ing.
Disadvantages of Cyclic Executive
Not useful when periods vary widely. (E.g., 1 s, 3 ms .).
Not reactive, must assume phase of periodic events.
Difficult to achieve exact start times for all handlers. (E.g., when bin has more than one
handler.)
Cannot be used with non-periodic events.
Cannot easily be used with long running handlers.
17-19 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from*
* lsli17. 17-19
17-20 *
* 17-20
Cyclic Executive Example
Set up a cyclic executive for the pure periodic events described in table below:
Event Handler Event
Name_____Run_Time______Period___
A 4 s 10 s
B 3 s 15 s
C 5 s 30 s
Set major cycle to 30 s, set minor cycle to 15 s.
B1 = (A; B; A) and B2 = (B; A; C).
The timing above would meet deadlines if the events occurred in the following way:
Event A: t = 3 s; 7 s; 17 s; 27 s; : :.:
Event B: t = 0 s; 15 s; 30 s; : :.:
Event C: t = 22 s; 52 s; : :.:
17-20 EE 4770 Lecture Transparency. Formatted 9:40, 14 April 1999 from*
* lsli17. 17-20
| David M. Koppelman - koppel@ee.lsu.edu | Modified 14 Apr 1999 9:40 (14:40 UTC) |