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.
16-1 Estimating Latency *
* 16-1
Goal:
given information about events and their handlers : : :
: : :estimate response times : : :
: : :or devise scheduling to insure that deadlines are met.
Definitions:
Latency [of an interrupt handler or daemon task to an event]:
Time from event occurrence to start of its handler or daemon task.
Response time [of interrupt handler or daemon task to an event]:
Time from event occurrence to response. In class response assumed
to be generated at completion of event's handler.
Let an event occur at t1 , its handler start at t2 and finish at t3 : : :
: : :then the latency is t2 t1 and response time t3 t1 .
Run time [of interrupt handler or daemon task]:
The time needed to run1 on an unloaded system.
Actual run time [of interrupt handler or daemon task]:
The time needed to run in a particular situation (considering other
CPU activity, etc.).
_______________________________
1 For handlers (which run something like operating system subroutines), run time is total run *
*time. For
daemons (which are tasks managed like any other tasks the OS is running) it's the amount of *
*run time
needed to generate a response. After the response the daemon will wait for another event, i*
*n contrast to
a handler which actually finishes execution. At a subsequent event a waiting daemon moves fr*
*om the wait
state (if the event is handled by a daemon), while a "fresh" call to a handler is made (if t*
*he event is handled
by a handler).
16-1 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16.*
* 16-1
16-2 *
* 16-2
Worst-case latency [of an int. handler or daemon task to an event]:
The longest possible latency given constraints on when events can
occur, etc.
Worst-case response time [of an int. handler or daemon task to an
event]:
The longest possible response time given constraints on when events
can occur, etc.
Worst-case run time [of an int. handler or daemon task to an event]:
The longest possible actual run time given constraints on when
events can occur, etc.
For a particular____event, response time is always latency plus actual run
time.
However,_____the worst-case response time is not necessarily the worst-case
latency plus the worst-case actual run-time.
Unless otherwise stated, all latencies, actual run times, and response times
are worst case.
16-2 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16.*
* 16-2
16-3 *
* 16-3
Classes of problems:
- One-shot.
Assume that each event can occur at most once.
- Periodic exhaustive.
Events periodic, solution found exhaustively.
- Periodic statistical.
Events periodic, solution found using statistical methods.
16-3 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16.*
* 16-3
16-4 *
* 16-4
Events, Event Types, and Interrupts
An event is some occurrence in the process.
For example, temperature exceeding a threshold.
(This is the definition used throughout the semester.)
An event type is a kind of event.
As a result of an event, which is of a certain event type, an interrupt is
requested; as a result a handler is run.
For example, consider a system where CDT marks trigger interrupts:
Event type: a clock mark passing under the mark reader of the coded
displacement transducer.
Event: at t = 30 the clock mark passes under the mark reader of the
coded displacement transducer.
Interrupt: the interruption caused by this event.
Handler: the CDT code that is run for this interrupt.
Each of these four terms has a different meaning, for brevity they some-
times will be used interchangeably.
16-4 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16.*
* 16-4
16-5 Archetypical Problems *
* 16-5
Timing Estimation Problem:
Given:
- Events. When the events can occur.
- Handlers and tasks for events. How long these will run.
Handlers and tasks generate a response by the end of their run.
- Scheduling algorithm, interrupt system, and related details.
Find:
- Worst-case response time for each event.
Scheduling Problem:
Given:
- Events. When the events can occur.
- Deadlines for responses to these events.
- Handlers and tasks for events. How long these will run.
- Some details of interrupt hardware and scheduling.
Find:
- Scheduling priorities, algorithm, or other details so that deadlines are
met.
16-5 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16.*
* 16-5
16-6 Trivial Example Problem *
* 16-6
A RTS must react to a single event. Exactly 5 s after the event oc-
curs the NMI-request line will be asserted. (The delay is due to a
slow sensor response.) The handler for this event requires 100 s
to generate a response to the event. The following are the timings
of other system functions: context save, 100 ns ; task switch, 50 s;
scheduler run time, 100 s; worst-case instruction completion, 50 ns ;
masking and jump to address specified in IVT, 20 ns . Find the worst-
case response time.
Solution:
The following occurs from event to response:
Total_Time/_s___________Time/_s_________Activity______________________________________*
*___
0.00 0.00 The event.
5.00 5.00 Time for sensor to generate request.
5.05 .05 Instruction completion.
5.07 .02 Mask and jump.
5.17 .10 Save context.
105.17 100.00 Run handler.
Note: In most problems the following times are ignored:
Context save, instruction completion, mask and jump.
16-6 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16.*
* 16-6
16-7 One-Shot Events *
* 16-7
An event type is said to be one-shot if it can occur no more than
once and if it can occur at any time.
A system is said to have one-shot events if all event types are one-
shot.
In most systems an event can occur more than once, however: : :
: : :the solution technique to be presented can be applied to prob-
lems in which the time for an event to re-occur is sufficiently large.
General solutions will be provided for these cases:
- Pure strong-priority interrupt selection.
This is similar to priority scheduling in a task-preemptive OS
with an infinite quantum.
- Pure weak-priority interrupt selection.
This is similar to priority scheduling in a non-task-preemptive
OS with an infinite quantum.
- Both strong- and weak-priority interrupt selection.
Problems will include these cases, and variations on these cases.
(So that the general solutions will have to be modified.)
16-7 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16.*
* 16-7
16-8 Pure Strong Priority, One-Shot Events *
* 16-8
This covers two possible sets of conditions:
Interrupts:
- Responses are generated by interrupt handlers.
- There is no more than one event and handler for each interrupt level.
- Interrupts can only be masked by other interrupts.
There are no tasks or other unrelated activities which can mask inter-
rupts.
- Only the run time of the interrupt handlers is significant.
Tasks:
- Responses are generated by tasks, with exactly one task per event.
- Priority scheduling is used with at most one task per priority level.
- The OS is task-preemptive.
- Only tasks specified in the problem need be considered.
(No other tasks will preempt or be selected before the tasks needed for
responses.)
- The quantum is infinite.
16-8 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16.*
* 16-8
16-9 *
* 16-9
Interrupt Latency of Pure Strong Priority, One-Shot Events
Let
E be the set of event types
(e.g., E = fbutton3 ; tempAlarm ; eventX ; 3; Ag),
all events in E be one shot,
th (e) be the run time of handler for e 2 E ,
p(e) be the strong priority level of the handler for e 2 E ,
no two events have the same strong priority,
then worst case latency for event e 2 E is
X
th (i).
p(ii2E)>p(e)
In words: sum of run times of all higher priority interrupts.
Worst-case latency is encountered by e if: : :
: : :at the same time as e: : :
: : :one or more higher priority events occur: : :
: : :and all other higher priority events occur before e gets to run.
16-9 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16.*
* 16-9
16-10 Pure Strong Priority, One-Shot Example Problem *
* 16-10
Find the response time for all events in a system using pure-strong-
priority interrupts and one-shot events. The events and interrupt
handlers are described below.
Event_______Priority_______Run_Time_________
A 3 10 s
B 7 15 s
C 1 8 s
Solution:
Worst-case latency for A: th (B) = 15 s.
Response time of A is th (B) + th (A) = 25 s.
Worst-case latency for B is 0.
Response time of B is th (B) = 15 s.
Worst-case latency for C: th (A) + th (B) = 25 s.
Response time of C is th (A) + th (B) + th (C) = 33 s.
16-10 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-10
16-11 Pure Weak Priority, One-Shot Events *
* 16-11
This covers two possible sets of conditions:
Interrupts:
- Responses are generated by interrupt handlers.
" All interrupts share a single IRQ input.
" Interrupt to run determined by polling sequence.
- Interrupts only masked by other interrupts.
(I.e., no tasks or other unrelated activities mask interrupts.)
- Only handler run time is significant.
E.g., context-switch and service-routine time can be ignored.
Tasks:
- Responses generated by tasks.
- Exactly one task per event.
- Priority scheduling used, at most one task per priority level.
" The OS is not__ task-preemptive.
- Only tasks specified in problem considered.
(No other tasks will preempt or be selected before the tasks needed for
responses.)
- The quantum is infinite.
Items that differ from the pure-strong-priority case are printed using
slanted type and diamonds for bullets.
16-11 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-11
16-12 *
* 16-12
Interrupt Latency of Pure Weak Priority, One-Shot Events
Let
E be a set of one-shot event types
(e.g., E = fbutton3 ; tempAlarm ; eventX ; 3; Ag),
th (e) be the run time of the handler for event e 2 E ,
p(e) be weak priority level of handler for e 2 E .
and no two events have the same weak priority,
then worst case latency for event e 2 E is
0 1
B X C
@ th (i)A + maxi2E th (i).
p(ii2E)>p(e) p(i)
16-13 Pure Weak Priority, One-Shot Example Problem *
* 16-13
Find the worst-case response time for all events in a system using
pure-weak-priority interrupts and one-shot events. The events and
interrupt handlers are described below.
Event_______Priority_______Run_Time_________
A 3 10 s
B 7 15 s
C 1 8 s
Solution:
Latency for A: th (B) + th (C) = 23 s.
Response time of A is th (B) + th (C) + th (A) = 33 s.
Latency for B is th (A) = 10 s.
Response time of B is th (A) + th (B) = 25 s.
Latency for C: th (A) + th (B) = 25 s.
Response time of C is th (A) + th (B) + th (C) = 33 s.
Notes:
A and C cannot simultaneously have worst-case response times.
Highest weak priority level does_not____ guarantee lowest response time. (This
will be seen in an example below.)
16-13 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-13
16-14 Strong and Weak Priority, One-Shot Events *
* 16-14
This covers two possible sets of conditions:
Interrupts:
- Responses are generated by interrupt handlers.
" An IRQ input can be used by any number of events.
" The interrupt to service determined by polling sequence: : :
: : :using a different sequence for each strong priority level.
- Interrupts can only be masked by other interrupts.
There are no tasks or other unrelated activities which can mask inter-
rupts.
- Only handler run time is significant.
Tasks:
- Responses are generated by tasks, exactly one task per event.
" Scheduling done in two rounds, both use priority scheduling.
" First round is task-preemptive, second round is non-task-preemptive.
- Only tasks specified in the problem need be considered.
(No other tasks will preempt or be selected before the tasks needed for
responses.)
- The quantum is infinite.
Diamonds (") indicate differences with pure-weak-priority.
16-14 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-14
16-15 Interrupt Latency of Strong and Weak Priority, One-Shot Events *
* 16-15
Let
E be a set of event types
(e.g., E = fbutton3 ; tempAlarm ; eventX ; 3; Ag),
all events in E be one shot,
th (e) be the run time of the handler for event e 2 E ,
p1 (e) be the strong priority level of the handler for event e 2 E ,
p2 (e) be weak priority level of handler for e 2 E .
Then worst-case latency for event e 2 E is
X X
th (i) + th (i) + maxi2E th (i).
p i2E i2E p1 (i)=p1 (e)
1 (i)>p1 (e) p1p(i)=p1 (e) p2 (i)p2 (e)
In words:
Sum of the run times of: : :
: : :all higher strong-priority and weak-priority handlers: : :
: : :plus longest run time of: : :
: : :the lower weak-priority handlers: : :
: : :that are at the same strong priority level as e.
16-15 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-15
16-16 *
* 16-16
This worst-case latency is encountered by e if:
The longest-run-time handler at the same strong priority level: : :
: : :starts to run just before e: : :
: : :and all higher priority interrupts occur before e's handler starts.
16-16 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-16
16-17 Strong and Weak Priority, One-Shot Example Problem *
* 16-17
Find the worst-case response time for all events in a system using
strong and weak priority interrupts and one-shot events. The events
and interrupt handlers are described below.
Event Strong Weak Run
____________Priority________Priority_______Time______
A 3 1 10 s
B 2 3 15 s
C 2 2 8 s
D 2 1 50 s
E 1 2 1 s
F 1 1 2 s
Solution:
Event A
Event order: A occurs any time.
Latency for A: 0 s.
Response time of A is th (A) = 10 s.
Event B
Possible event order: D, B, A.
Latency for B is tl(B) = th (A) + th (D) = 60 s.
Response time of B is tl(B) + th (B) = 75 s.
Event C
Possible event order: D, C, B, A.
Latency for C: tl(C) = th (A) + th (B) + th (D) = 75 s.
Response time of C is tl(C) + th (C) = 83 s.
16-17 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-17
16-18 *
* 16-18
Example, continued.
Event Strong Weak Run Time
____________Priority_______Priority_______________Time_____
A 3 1 10 s
B 2 3 15 s
C 2 2 8 s
D 2 1 50 s.
E 1 2 1 s.
F 1 1 2 s.
Event D
Possible event order: B, D, C, A.
Latency for D: tl(D) = th (A) + th (B) + th (C) = 33 s.
Response time of D is tl(D) + th (D) = 83 s.
Event E
Possible event order: F , E, A, B, C, D.
X
Latency for E: tl(E) = th (e) = 85 s.
e2fA;B;C;D;F g
Response time of E is tl(E) + th (E) = 86 s.
Event F
Possible event order: E, F, A, B, C, D.
X
Latency for F : tl(F ) = th (e) = 84 s.
e2fA;B;C;D;Eg
Response time of F is tl(F ) + th (F ) = 86 s.
16-18 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-18
16-19 Example Problem Solution Details *
* 16-19
Simulator Output Format
Output divided into sections divided by lines like:
================= B Worst-Case Latency and Run Time ====================
Each section demonstrates worst-case behavior for a different event.
Handler timing given in lines like:
Handler for F (1) finished: lat. 99., dur. 2., resp. 101.
which indicates that occurrence 1 of event F had a latency of 99, actual run time (duratio*
*n) of 2,
and a response time of 101.
This timing information is shown for all events, only a few of which suffer worst-case dela*
*ys. (The
event suffering worst-case delays is indicated in the section heading, but watch for multip*
*le occurrence
of the same event.)
Each section heading is printed at t = 4 (mod 1000), the first event in each section occu*
*rs at time
t = 5 - (mod 1000) and the event suffering worst case latency and response time occurs *
*at time
t = 5 (mod 1000), where - is a very small time interval.
Simulator Output
** Time: 4
================= B Worst-Case Latency and Run Time ====================
** Time: 5.
Interrupt D (0) requested.
Handler for D (0) starting.
** Time: 5
Interrupt B (0) requested.
** Time: 6
Interrupt A (0) requested.
Handler for D (0) preempted.
Handler for A (0) starting.
** Time: 16
Handler for A (0) finished: lat. 0, dur. 10, resp. 10
Handler for D (0) resumed.
** Time: 65.
Handler for D (0) finished: lat. 0., dur. 60., resp. 60.
Handler for B (0) starting.
** Time: 80.
Handler for B (0) finished: lat. 60., dur. 15., resp. 75.
** Time: 1,004
================= C Worst-Case Latency and Run Time ====================
** Time: 1,005.
Interrupt D (1) requested.
Handler for D (1) starting.
** Time: 1,005
Interrupt C (0) requested.
16-19 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-19
16-20 *
* 16-20
** Time: 1,006
Interrupt A (1) requested.
Handler for D (1) preempted.
Handler for A (1) starting.
** Time: 1,007
Interrupt B (1) requested.
** Time: 1,016
Handler for A (1) finished: lat. 0, dur. 10, resp. 10
Handler for D (1) resumed.
** Time: 1,065.
Handler for D (1) finished: lat. 0., dur. 60., resp. 60.
Handler for B (1) starting.
** Time: 1,080.
Handler for B (1) finished: lat. 58., dur. 15., resp. 73.
Handler for C (0) starting.
** Time: 1,088.
Handler for C (0) finished: lat. 75., dur. 8., resp. 83.
** Time: 2,004
================= D Worst-Case Latency and Run Time ====================
** Time: 2,005.
Interrupt B (2) requested.
Handler for B (2) starting.
** Time: 2,005
Interrupt D (2) requested.
** Time: 2,006
Interrupt A (2) requested.
Handler for B (2) preempted.
Handler for A (2) starting.
** Time: 2,007
Interrupt C (1) requested.
** Time: 2,016
Handler for A (2) finished: lat. 0, dur. 10, resp. 10
Handler for B (2) resumed.
** Time: 2,030.
Handler for B (2) finished: lat. 0., dur. 25., resp. 25.
Handler for C (1) starting.
** Time: 2,038.
Handler for C (1) finished: lat. 23., dur. 8., resp. 31.
Handler for D (2) starting.
** Time: 2,088.
Handler for D (2) finished: lat. 33., dur. 50., resp. 83.
** Time: 3,004
================= E Worst-Case Latency and Run Time ====================
** Time: 3,005.
Interrupt F (0) requested.
Handler for F (0) starting.
** Time: 3,005
Interrupt E (0) requested.
** Time: 3,006
Interrupt A (3) requested.
Handler for F (0) preempted.
Handler for A (3) starting.
** Time: 3,007
16-20 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-20
16-21 *
* 16-21
Interrupt B (3) requested.
** Time: 3,008
Interrupt C (2) requested.
** Time: 3,009
Interrupt D (3) requested.
** Time: 3,016
Handler for A (3) finished: lat. 0, dur. 10, resp. 10
Handler for F (0) resumed.
Handler for F (0) preempted.
Handler for B (3) starting.
** Time: 3,031
Handler for B (3) finished: lat. 9, dur. 15, resp. 24
Handler for F (0) resumed.
Handler for F (0) preempted.
Handler for C (2) starting.
** Time: 3,039
Handler for C (2) finished: lat. 23, dur. 8, resp. 31
Handler for F (0) resumed.
Handler for F (0) preempted.
Handler for D (3) starting.
** Time: 3,089
Handler for D (3) finished: lat. 30, dur. 50, resp. 80
Handler for F (0) resumed.
** Time: 3,090.
Handler for F (0) finished: lat. 0., dur. 85., resp. 85.
Handler for E (0) starting.
** Time: 3,091.
Handler for E (0) finished: lat. 85., dur. 1., resp. 86.
** Time: 4,004
================= F Worst-Case Latency and Run Time ====================
** Time: 4,005.
Interrupt E (1) requested.
Handler for E (1) starting.
** Time: 4,005
Interrupt F (1) requested.
** Time: 4,005
Interrupt A (4) requested.
Handler for E (1) preempted.
Handler for A (4) starting.
** Time: 4,007
Interrupt B (4) requested.
** Time: 4,008
Interrupt C (3) requested.
** Time: 4,009
Interrupt D (4) requested.
** Time: 4,015
Handler for A (4) finished: lat. 0, dur. 10, resp. 10
Handler for E (1) resumed.
Handler for E (1) preempted.
Handler for B (4) starting.
** Time: 4,030
Handler for B (4) finished: lat. 8, dur. 15, resp. 23
Handler for E (1) resumed.
16-21 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-21
16-22 *
* 16-22
Handler for E (1) preempted.
Handler for C (3) starting.
** Time: 4,038
Handler for C (3) finished: lat. 22, dur. 8, resp. 30
Handler for E (1) resumed.
Handler for E (1) preempted.
Handler for D (4) starting.
** Time: 4,088
Handler for D (4) finished: lat. 29, dur. 50, resp. 79
Handler for E (1) resumed.
** Time: 4,089.
Handler for E (1) finished: lat. 0., dur. 84., resp. 84.
Handler for F (1) starting.
** Time: 4,091.
Handler for F (1) finished: lat. 84., dur. 2., resp. 86.
Simulation completed.
16-22 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-22
16-23 *
* 16-23
Perturbations
One-shot assumption too limiting.
Useful problems based on perturbation of one-shot assumption.
These problems solved by adapting one-shot solution procedure.
Adapting Solution
Instead of using latency formulas (from previous slides): : :
: : :find an ordering of events: : :
: : :meeting problem restrictions: : :
: : :while resulting in worst-case behavior.
Two Perturbations from One-Shot
- Timing restrictions on events.
- Multiple occurrences of an event type.
Timing Restrictions
Usually minimum or maximum time between events.
E.g., event A occurs 12 s after B.
16-23 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-23
16-24 *
* 16-24
Multiple Event Occurrences
Event may happen several times.
Bound on number and timing of occurrences will be given.
E.g., event A occurs 3 times > 5 s apart.
Multiple Occurrences Notation
Subscript used to indicate occurrence.
E.g., A1 , first occurrence of event type A; A2 second.
Handling Multiple Occurrences
In class, the handler must be run for each occurrence.
E.g., if A occurs twice (A1 and A2 ),: : :
: : :handler for A must be run twice: : :
: : :even if A2 occurs before handler for A1 runs.
16-24 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-24
16-25 Perturbations Example Problem *
* 16-25
Find the worst-case response time for all events in a system using
strong and weak priority interrupts and one-shot events. The events
and interrupt handlers are described below. The handler must be
run once for each event occurrence, even if an event occurs a second
time before the first the handler was run for the first occurrence.
Event Strong Weak Run Event
___Priority________Priority_______Time________Occurrences_________________________________*
*_____________________________________
A 3 1 10 s Occurs once, any time.
B 2 3 15 s Occurs twice, any times.
C 2 2 8 s Occurs once, 45 to 50 s after event A.
D 2 1 50 s Occurs once, any time.
E 1 2 1 s Occurs three times, with > 100 s separation.
F 1 1 2 s Occurs once.
Solution:
Event A
Event order: A can occur any time.
Latency for A: 0 s.
Response time of A is th (A) = 10 s.
Event B
Since event-type B can occur twice: : :
: : :an event B might have to wait: : :
: : :for a previous occurrence of B to be handled.
Possible event order: D, B1 , B2 , A.
Latency for B2 is tl(B) = th (A) + th (B) + th (D) = 75 s.
Response time of B2 is tl(B) + th (B) = 90 s.
16-25 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli1*
*6. 16-25
16-26 *
* 16-26
Example, continued.
Event Strong Weak Run Event
___Priority________Priority_______Time________Occurrences_________________________________*
*_____________________________________
A 3 1 10 s Occurs once, any time.
B 2 3 15 s Occurs twice, any times.
C 2 2 8 s Occurs once, 45 to 50 s after event A.
D 2 1 50 s Occurs once, any time.
E 1 2 1 s Occurs three times, with > 100 s separation.
F 1 1 2 s Occurs once.
Event C
C only occurs after event A so:
Possible event order: D, C, B1 , B2 .
Latency for C: tl(C) = 2th (B) + th (D) = 80 s.
Response time of C is tl(C) + th (C) = 88 s.
Event D.
C and A cannot both occur within D's latency period.
Possible event order: B1 , D, A, B2 .
Latency for D: tl(D) = th (A) + 2th (B) = 40 s.
Response time of D is tl(D) + th (D) = 90 s.
16-26 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli1*
*6. 16-26
16-27 *
* 16-27
Example, continued.
Event Strong Weak Run Event
___Priority________Priority_______Time________Occurrences_________________________________*
*_____________________________________
A 3 1 10 s Occurs once, any time.
B 2 3 15 s Occurs twice, any times.
C 2 2 8 s Occurs once, 45 to 50 s after event A.
D 2 1 50 s Occurs once, any time.
E 1 2 1 s Occurs three times, with > 100 s separation.
F 1 1 2 s Occurs once.
Event E
Both A and C can occur during E's latency.
Possible event order: F , E, A, B1 , B2 , D, C
X
Latency for E: tl(E) = th (e) = 100 s.
e2fA;B1;B2;C;D;F g
Response time of E is tl(E) + th (E) = 101 s.
Event F
E's second occurrence is after F starts.
Possible event order: E1 , F, A, B1 , B2 , D, C
X
Latency for F : tl(F ) = th (e) = 99 s.
e2fA;B1;B2;C;D;Eg
Response time of F is tl(F ) + th (F ) = 101 s.
16-27 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli1*
*6. 16-27
16-28 Example Problem Solution Details *
* 16-28
Simulator Output
** Time: 4
================= B Worst-Case Latency and Run Time ====================
** Time: 5.
Interrupt D (0) requested.
Handler for D (0) starting.
** Time: 5
Interrupt B (0) requested.
** Time: 5.
Interrupt B (1) requested.
** Time: 6
Interrupt A (0) requested.
Handler for D (0) preempted.
Handler for A (0) starting.
** Time: 16
Handler for A (0) finished: lat. 0, dur. 10, resp. 10
Handler for D (0) resumed.
** Time: 65.
Handler for D (0) finished: lat. 0., dur. 60., resp. 60.
Handler for B (0) starting.
** Time: 80.
Handler for B (0) finished: lat. 60., dur. 15., resp. 75.
Handler for B (1) starting.
** Time: 95.
Handler for B (1) finished: lat. 75., dur. 15., resp. 90.
** Time: 1,004
================= C Worst-Case Latency and Run Time ====================
** Time: 1,005.
Interrupt D (1) requested.
Handler for D (1) starting.
** Time: 1,005
Interrupt C (0) requested.
** Time: 1,005.
Interrupt B (2) requested.
** Time: 1,005.
Interrupt B (3) requested.
** Time: 1,055.
Handler for D (1) finished: lat. 0., dur. 50., resp. 50.
Handler for B (2) starting.
** Time: 1,070.
Handler for B (2) finished: lat. 50., dur. 15., resp. 65.
Handler for B (3) starting.
** Time: 1,085.
Handler for B (3) finished: lat. 65., dur. 15., resp. 80.
Handler for C (0) starting.
** Time: 1,093.
Handler for C (0) finished: lat. 80., dur. 8., resp. 88.
** Time: 2,004
================= D Worst-Case Latency and Run Time ====================
** Time: 2,005.
Interrupt B (4) requested.
Handler for B (4) starting.
** Time: 2,005
16-28 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-28
16-29 *
* 16-29
Interrupt D (2) requested.
** Time: 2,006
Interrupt A (1) requested.
Handler for B (4) preempted.
Handler for A (1) starting.
** Time: 2,007
Interrupt B (5) requested.
** Time: 2,016
Handler for A (1) finished: lat. 0, dur. 10, resp. 10
Handler for B (4) resumed.
** Time: 2,030.
Handler for B (4) finished: lat. 0., dur. 25., resp. 25.
Handler for B (5) starting.
** Time: 2,045.
Handler for B (5) finished: lat. 23., dur. 15., resp. 38.
Handler for D (2) starting.
** Time: 2,095.
Handler for D (2) finished: lat. 40., dur. 50., resp. 90.
** Time: 3,004
================= E Worst-Case Latency and Run Time ====================
** Time: 3,005.
Interrupt F (0) requested.
Handler for F (0) starting.
** Time: 3,005
Interrupt E (0) requested.
** Time: 3,006
Interrupt A (2) requested.
Handler for F (0) preempted.
Handler for A (2) starting.
** Time: 3,007
Interrupt B (6) requested.
** Time: 3,008
Interrupt B (7) requested.
** Time: 3,009
Interrupt D (3) requested.
** Time: 3,016
Handler for A (2) finished: lat. 0, dur. 10, resp. 10
Handler for F (0) resumed.
Handler for F (0) preempted.
Handler for B (6) starting.
** Time: 3,031
Handler for B (6) finished: lat. 9, dur. 15, resp. 24
Handler for F (0) resumed.
Handler for F (0) preempted.
Handler for B (7) starting.
** Time: 3,046
Handler for B (7) finished: lat. 23, dur. 15, resp. 38
Handler for F (0) resumed.
Handler for F (0) preempted.
Handler for D (3) starting.
** Time: 3,051
Interrupt C (1) requested.
** Time: 3,096
16-29 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-29
16-30 *
* 16-30
Handler for D (3) finished: lat. 37, dur. 50, resp. 87
Handler for F (0) resumed.
Handler for F (0) preempted.
Handler for C (1) starting.
** Time: 3,104
Handler for C (1) finished: lat. 45, dur. 8, resp. 53
Handler for F (0) resumed.
** Time: 3,105.
Handler for F (0) finished: lat. 0., dur. 100., resp. 100.
Handler for E (0) starting.
** Time: 3,106.
Handler for E (0) finished: lat. 100., dur. 1., resp. 101.
** Time: 4,004
================= F Worst-Case Latency and Run Time ====================
** Time: 4,005.
Interrupt E (1) requested.
Handler for E (1) starting.
** Time: 4,005
Interrupt F (1) requested.
** Time: 4,005.5
Interrupt A (3) requested.
Handler for E (1) preempted.
Handler for A (3) starting.
** Time: 4,007
Interrupt B (8) requested.
** Time: 4,008
Interrupt B (9) requested.
** Time: 4,009
Interrupt D (4) requested.
** Time: 4,015.5
Handler for A (3) finished: lat. 0., dur. 10., resp. 10.
Handler for E (1) resumed.
Handler for E (1) preempted.
Handler for B (8) starting.
** Time: 4,030.5
Handler for B (8) finished: lat. 8.5, dur. 15., resp. 23.5
Handler for E (1) resumed.
Handler for E (1) preempted.
Handler for B (9) starting.
** Time: 4,045.5
Handler for B (9) finished: lat. 22.5, dur. 15., resp. 37.5
Handler for E (1) resumed.
Handler for E (1) preempted.
Handler for D (4) starting.
** Time: 4,051
Interrupt C (2) requested.
** Time: 4,095.5
Handler for D (4) finished: lat. 36.5, dur. 50., resp. 86.5
Handler for E (1) resumed.
Handler for E (1) preempted.
Handler for C (2) starting.
** Time: 4,103.5
Handler for C (2) finished: lat. 44.5, dur. 8., resp. 52.5
16-30 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-30
16-31 *
* 16-31
Handler for E (1) resumed.
** Time: 4,104.
Handler for E (1) finished: lat. 0., dur. 99., resp. 99.
Handler for F (1) starting.
** Time: 4,105
Interrupt E (2) requested.
** Time: 4,106.
Handler for F (1) finished: lat. 99., dur. 2., resp. 101.
Handler for E (2) starting.
** Time: 4,107.
Handler for E (2) finished: lat. 1., dur. 1., resp. 2.
Simulation completed.
16-31 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-31
16-32 Strong and Weak Priority One-Shot Scheduling Problem *
* 16-32
Responses in a RTS are generated by interrupt handlers. Strong and
weak priority can be used. The events, the run time of the event
handlers, and the timing constraints on the responses are given in
the table below. Assign priorities so that the deadlines are met and
the minimum number of strong priority levels are used.
Event Run Response Time Occurrence
Name________Time_______________Constraint_________________________________
A 50 s < 90 s Once, any time.
B 20 s < 30 s Once, any time.
C 10 s 80 s Once, any time.
Solution:
Event Strong Weak Response
Name_________Priority________Priority_______Latency_________Time___________
A 1 1 30 s 80 s
B 2 1 0 s 20 s
C 1 2 70 s 80 s
16-32 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-32
16-33 Periodic Events *
* 16-33
An event type is said to be periodic if: : :
: : :the time between occurrences is fixed: : :
: : :the time of occurrences (phase) is arbitrary.
The period is the time between occurrences.
tb (X ) will denote the period of event type X .
(The b is for between.)
Example
Let tb(A) = 10 s, where A is an event type.
Then A might occur at t= s = 10; 20; 30; : :.:
Or A might occur at t= s = 12; 22; 32; : :.:
16-33 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-33
16-34 *
* 16-34
Relative Timing
Since time of occurrences arbitrary: : :
: : :in a system with several periodic event types,: : :
: : :the relative timing of the events is arbitrary.
Relative Timing Example
Suppose event-type A is periodic with tb(A) = 10 ms : : :
: : :and B is periodic also with tb(B) = 10 ms .
Then A and B could occur at:: : :
: : :the same time,: : :
: : :or A could follow B by any time < 10 ms .
But, because their periods are the same,: : :
: : :the time from A to B is fixed,: : :
: : :even though this time is not known in advance.
16-34 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-34
16-35 Latency Estimation with Periodic Events *
* 16-35
Exhaustive Method
By trial-and-error, find the worst-case scenario.
Statistical Method
Find average effect of relatively short handlers.
16-35 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-35
16-36 Periodic-Interrupts Example Problem *
* 16-36
A RTS has three event types, A, B, and C. All event types are peri-
odic; their periods, the run time of their handlers, and their priority
levels appear in the table below. Find the latency and response time
for each event type.
Event Strong Period Handler Run Time
Name________Priority________tb=_s________________________th_=_s______
A 3 23 5
B 2 100 20
C 1 36 2
Solution:
Latency for A: 0 s.
Response time of A is tr (A) = th (A) = 5 s.
Latency for B: tl(B) = th (A) = 5 s.
Response time of B is tr (B) = 2th (A) + th (B) = 30 s.
(B occurs just after A; before B finishes A occurs a second time.)
Latency for C: tl(C) = 2th (A) + th (B) = 30 s.
Response time of C is tr (C) = 2th (A) + th (B) + th (C) = 32 s.
16-36 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-36
16-37 Statistical Method of Latency Estimation *
* 16-37
Motivation: exhaustive method may be too time consuming.
Statistical Method Idea
Consider average_not exact_number of times: : :
: : :one handler interrupts another.
Illustration
Consider two periodic events, A and B.
Let interrupt A have higher strong priority than B.
Let th (A) = 100 s, tb(A) = 300 s, th (B) = 450 s, and tb(B) = 10 s.
Exhaustive Method on Illustration
B can be interrupted by A 2 or 3 times.
WC run-time for B then ta (B) = th (B) + n th (A),
where n is number of times B interrupted:
Substituting yields ta (B) = 750 s.
16-37 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-37
16-38 *
* 16-38
WC Run Using Average Number of Interruptions
Ignoring fact that n is an integer: : :
: : :let n = ta (B)=tb(A) .
This average contains unknown value, ta (B).
Solving for ta (B) yields ta (B) = ___th_(B)____t. (A)
1 _______tb(Ah)
Average Method on Illustration
Substituting yields ta (B) = 675 s.
Difference, 750 s 675 s = 75 s, too big to ignore: : :
: : :but as n increases the difference drops.
16-38 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-38
16-39 *
* 16-39
Important Quantity in Average Method: Loading Factor
Consider actual run time equation:
ta (B) = ___th_(B)____t. (A)
1 _______tb(Ah)
Average n = th (A)=tb(B) not explicit.
But 1 th_(A)_tb(A)is.
So 1 th_(A)_tb(A)will be used instead of average n.
1 th_(A)_tb(A)is example of loading factor.
Intuitive Definition of Loading Factor
Fraction of CPU time that A leaves for B.
B's run time computed for slower CPU using loading factor.
First definitions, then details of the statistical method.
16-39 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-39
16-40 Definitions *
* 16-40
Load (noun) [that a handler places on system]
The load of a periodic event's handler is
l = th =tb,: : :
: : :where th is run time of handler: : :
: : :and tb is event's period.
In words: fraction of CPU time needed by handler.
A system will be overloaded if the sum of all loads is greater than one.
Load (verb)
Event X is said to load event Y : : :
: : :if strong priority of X is higher than Y : : :
: : :and lth (X) < th (Y ),: : :
: : :where l is a constant called the loading threshold.
Loading Threshold Values
Higher values give more precise answers.
Unless stated otherwise l = 50.
16-40 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-40
16-41 *
* 16-41
Load Set
Let Y denote an event.
The load set for Y is : : :
: : :the set of events that load Y .
Loading Factor
Let Y denote an event : : :
: : :and X be the load set for Y .
Then the loading factor for Y 's handler is
X th (e)
lf (Y ) = 1 _______.
e2X tb(e)
In words: Y 's loading factor is fraction of CPU time : : :
: : :available to Y 's handler : : :
: : :after accounting for X , the load set.
Loaded Duration
Let Y denote an event with loading factor lf (Y ).
Then the loaded duration of event Y 's handler is
t0h(Y ) = th_(Y_)_l.
f (Y )
Note:___ the actual duration, ta (Y ), can be longer.
16-41 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-41
16-42 *
* 16-42
General Solution Technique
Start at the highest strong-priority level.
For all events in a strong-priority level:
- Find the loading factor, compute the loaded duration.
- Exhaustively compute the actual duration (consider only higher-priority
events which do not load the event being considered).
- Exhaustively compute the latency.
- Exhaustively compute the response time.
Repeat for the next lower strong-priority level or finish if at the lowest
strong priority.
16-42 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-42
16-43 Statistical-Latency-Estimation Example Problem *
* 16-43
A RTS has three event types, all periodic. Their period, priority,
and the run time of their handlers is listed in the table below. Find
the latency and response time for each event.
Event Strong Period Handler Run
Name________Priority_____________tb____Time,_th______________
A 3 10 s 0:5 s
B 2 50 ms 37 s
C 1 1 s 40 s
Solution:
- Event A
Latency, tl(A) = 0 s.
Response time, tr (A) = tl(A) + th (A) = 0:5 s.
- Event B
th_(B)___
= 74 > l = 50, therefore A loads B.
th (A)
th (A)
Loading factor for B is lf (B) = 1 _________ = 0:95.
tb (A)
th (B)
Loaded duration: t0h(B) = _________= 38:95 s.
lf (B)
Latency, tl(B) = th (A) = 0:5 s.
Response time, tr (B) = tl(B) + t0h(B) = 39:45 s.
16-43 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-43
16-44 *
* 16-44
Example, continued.
Event Strong Period Handler Run
Name________Priority_____________tb____Time,_th______________
A 3 10 s 0:5 s
B 2 50 ms 37 s
C 1 1 s 40 s
- Event C
th_(C)___ th (C)
= 80 > l; _________= 1:08 < l,
th (A) th (B)
therefore A loads C but B does not.
th (A)
Loading factor, lf (C) = 1 _________ = 0:95.
tb (A)
Event C's worst-case latency due to A followed by one loaded B:
Latency, tl(C) = th (A) + t0h(B) = 39:45 s.
Event B can occur either during C's latency or run time, but not
both:
th (C)
Response time, tr (C) = th (A) + t0h(B) + _________ = 81:55 s.
lf (C)
16-44 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-44
16-45 Perturbations *
* 16-45
Quasi-Periodic Events
Occur regularly, but not with fixed period.
Examples:
- Period ranging from 100 ms to 80 ms .
- No more than 5 times in 10 ms interval.
- At t = 0 and exactly 27 s after previous occurrence handled.
Load of Handlers for Quasi-Periodic Events
Can sometimes find a worst-case tb.
This would be used in load factors.
The method for determining the WC tb depends upon details of quasi-
periodic event.
16-45 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-45
16-46 Another Statistical Latency Estimation Example Problem *
* 16-46
A RTS must react to six event types. The names of the event types,
their occurrence times, the priorities of their respective interrupts,
and the run time of their handlers is listed in the table below. For
each event type find the latency, duration, and response time. Also
find the total system load.
Event Strong Weak Handler Occurrence
Name _____Pri._________Pri._______Run_Time______________________________________________________*
*________________________________
A 4 2 3 s Periodic, tb(A) = 20 s.
B 4 1 2 s From 7 s to 13 s after event A, if at all.
C 3 1 700 s Periodic, tb(C) = 27 ms .
D 3 2 11 s No more than 3 times in any 1 ms interval.
D At most 2 unresponded events held.
E 2 1 1 ms Periodic, tb(E) = 100 ms .
F 1 1 500 ms Anytime after resp. to prev. occur.
Solution:
Events A and B
From table above, cannot occur at same time.
A possible event sequence: A.
B possible event sequence: B.
And so latency: tl(A) = tl(B) = 0 s.
Response time: tr (A) = ta (A) = 3 s.
Response time: tr (B) = ta (B) = 2 s.
16-46 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-46
16-47 *
* 16-47
Example, continued.
Event Strong Weak Handler Occurrence
Name _____Pri._________Pri._______Run_Time______________________________________________________*
*________________________________
A 4 2 3 s Periodic, tb(A) = 20 s.
B 4 1 2 s From 7 s to 13 s after event A, if at all.
C 3 1 700 s Periodic, tb(C) = 27 ms .
D 3 2 11 s No more than 3 times in any 1 ms interval.
D At most 2 unresponded events held.
E 2 1 1 ms Periodic, tb(E) = 100 ms .
F 1 1 500 ms Anytime after resp. to prev. occur.
Event C Run Time
Loading: A, B.
effective__ tb(B) same as tb(A).
lf (C) = 1 th_(A)__t th_(B)__ = 0:75.
b(A)tb(A)
Actual run time ta (C) = th_(C)__l= 933 1_s.
f (C) 3
Event D Run Time
Use exhaustive method, note variation in B's timing.
Possible event sequence: D, B1 , A, B2 .
ta (D) = th (D) + 2th (B) + th (A) = 18 s.
16-47 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-47
16-48 *
* 16-48
Example, continued.
Event Strong Weak Handler Occurrence
Name _____Pri._________Pri._______Run_Time______________________________________________________*
*________________________________
A 4 2 3 s Periodic, tb(A) = 20 s.
B 4 1 2 s From 7 s to 13 s after event A, if at all.
C 3 1 700 s Periodic, tb(C) = 27 ms .
D 3 2 11 s No more than 3 times in any 1 ms interval.
D At most 2 unresponded events held.
E 2 1 1 ms Periodic, tb(E) = 100 ms .
F 1 1 500 ms Anytime after resp. to prev. occur.
Event C Latency
Event D can occur 3 times in an interval: : :
: : :in which A can occur 3 times and B twice.
Possible event sequence: D0 , A0 , C, B0 , D1 , A1 , D2 , B1 , A2 .
tl(C) = 3th (D) + 3th (A) + 2th (B) = 46 s.
Event D Latency
Event D2 must wait for C: : :
: : :and an earlier instance of D to finish.
Possible event sequence: C, D1 , D2 , B1 , A, B2 .
C indicates C and events that load C's handler.
tl(D) = ta (C) + ta (D) = 951:33 s.
16-48 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-48
16-49 *
* 16-49
Example, continued.
Event Strong Weak Handler Occurrence
Name _____Pri._________Pri._______Run_Time______________________________________________________*
*________________________________
A 4 2 3 s Periodic, tb(A) = 20 s.
B 4 1 2 s From 7 s to 13 s after event A, if at all.
C 3 1 700 s Periodic, tb(C) = 27 ms .
D 3 2 11 s No more than 3 times in any 1 ms interval.
D At most 2 unresponded events held.
E 2 1 1 ms Periodic, tb(E) = 100 ms .
F 1 1 500 ms Anytime after resp. to prev. occur.
Event C Response Time
The event sequences used: : :
: : :for computing C's latency and duration: : :
: : :could happen both___ during the latency and run intervals: : :
: : :therefore response time is sum of two:
Response time tr (C) = tl(C) + ta (C) = 979:33 s.
Event D Response Time
The response time of D includes two runs of D.
The event sequences used in computing ta (C): : :
: : :had D interrupted by two B's and an A.
This cannot happen for two consecutive runs of D.
Possible event sequence: C, D1 , D2 , B1 , A1 , B2 A2 .
Response time tr (D) = ta (C) + 2(th (D) + th (A) + th (B)) = 965:33 s.
16-49 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-49
16-50 *
* 16-50
Example, continued.
Event Strong Weak Handler Occurrence
Name _____Pri._________Pri._______Run_Time______________________________________________________*
*________________________________
A 4 2 3 s Periodic, tb(A) = 20 s.
B 4 1 2 s From 7 s to 13 s after event A, if at all.
C 3 1 700 s Periodic, tb(C) = 27 ms .
D 3 2 11 s No more than 3 times in any 1 ms interval.
D At most 2 unresponded events held.
E 2 1 1 ms Periodic, tb(E) = 100 ms .
F 1 1 500 ms Anytime after resp. to prev. occur.
Event E
Loaded by A, B, and D:
lf (E) = 1 th_(A)__t th_(B)__ th_(D)__ = 0:717.
b(A)tb(B) tb(D)
Worst-case latency includes
: : :time for C: : :
: : :plus time for D's waiting after C finishes: : :
: : :plus 3 A's and 2 B's:
tl(E) = 3th (D) + 3th (A) + 2th (B) + ta (C) = 979:33 s.
Actual duration is similar, except E occurs before C.
ta (E) = th_(E)__l+ ta (C) + 3ta (D) + 3ta (A) + 2ta (B) = 2:374 ms .
f (E)
Response time must not count C twice:
tr (E) = tl(E) + th_(E)__l= 2:374 ms .
f (E)
16-50 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-50
16-51 *
* 16-51
Example, continued.
Event Strong Weak Handler Occurrence
Name _____Pri._________Pri._______Run_Time______________________________________________________*
*________________________________
A 4 2 3 s Periodic, tb(A) = 20 s.
B 4 1 2 s From 7 s to 13 s after event A, if at all.
C 3 1 700 s Periodic, tb(C) = 27 ms .
D 3 2 11 s No more than 3 times in any 1 ms interval.
D At most 2 unresponded events held.
E 2 1 1 ms Periodic, tb(E) = 100 ms .
F 1 1 500 ms Anytime after resp. to prev. occur.
Event F
All other events load F :
X th (e)
lf (F ) = 1 _______= 0:681.
e2fA;B;C;D;Eg tb(e)
Duration
ta (F ) = th_(F_)_l= 734:1 ms .
f (F )
Latency of F is the same as response time of E since there is only one
interrupt at strong levels 1 and 2 and since neither interrupt will recur
until after handler finishes.
tl(F ) = tr (E) = 2:374 ms .
tr (F ) = tl(F ) + ta (F ) = 736:5 ms .
Because of event F , worst-case load is 1.
16-51 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-51
16-52 Example Problem Solution Details *
* 16-52
Simulator Output Format
Output shows worst-case scenarios for some events.
As with simulator output appearing above, latency and response times shown are only worst c*
*ase for
a few events, see title at the head of each run.
Events in a handler's load set are not shown while a handler is running. For example, C is*
* loaded
by A and B, so while C is running occurrences of A and B are not shown.
Just before a handler starts a message is printed for each active event in its load set, in*
*dicating that
those events will be ignored (and the run time of the handler is computed using the loading*
* factor),
for example, "Event A simulated using handler load." If the event is already being ignored*
* no mes-
sage is printed. Similarly, before a handler starts a message is printed for each event wh*
*ich will no
longer be ignored. For example, "Normal simulation of A resuming." Sometimes both message*
*s are
printed (the software is not yet polished), use the second message.
- Loaded Event Handlers -
Event C: ld. factor, 0.75; ld. dur, 933.333 load set A, B
Event E: ld. factor, 0.75; ld. dur, 1333.33 load set A, B
Event F: ld. factor, 0.714074; ld. dur, 700207. load set A, B, C, E
** Starting simulation...
=============== C(0) Worst-Case Latency and Response. ==================
** Time: 1,000.
Interrupt D (0) requested.
Handler for D (0) starting, time remaining 11
** Time: 1,000.
Interrupt A (0) requested.
Handler for D (0) preempted.
Handler for A (0) starting, time remaining 3
** Time: 1,000
Interrupt C (0) requested.
** Time: 1,000.
Interrupt D (1) requested.
** Time: 1,003.
Handler for A (0) finished:
latency 0. + duration 3. = response time 3.
Handler for D (0) resumed, time remaining 11..
** Time: 1,007
Interrupt B (0) requested.
Handler for D (0) preempted.
Handler for B (0) starting, time remaining 2
** Time: 1,009
Handler for B (0) finished:
latency 0 + duration 2 = response time 2
Handler for D (0) resumed, time remaining 7..
** Time: 1,016.
Handler for D (0) finished:
latency 0. + duration 16. = response time 16.
Handler for D (1) starting, time remaining 11
** Time: 1,020.
Interrupt A (1) requested.
16-52 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-52
16-53 *
* 16-53
Handler for D (1) preempted.
Handler for A (1) starting, time remaining 3
** Time: 1,023.
Handler for A (1) finished:
latency 0. + duration 3. = response time 3.
Handler for D (1) resumed, time remaining 7..
** Time: 1,025
Interrupt D (2) requested.
** Time: 1,027
Interrupt B (1) requested.
Handler for D (1) preempted.
Handler for B (1) starting, time remaining 2
** Time: 1,029
Handler for B (1) finished:
latency 0 + duration 2 = response time 2
Handler for D (1) resumed, time remaining 3..
** Time: 1,032.
Handler for D (1) finished:
latency 16. + duration 16. = response time 32.
Handler for D (2) starting, time remaining 11
** Time: 1,040.
Interrupt A (2) requested.
Handler for D (2) preempted.
Handler for A (2) starting, time remaining 3
** Time: 1,043.
Handler for A (2) finished:
latency 0. + duration 3. = response time 3.
Handler for D (2) resumed, time remaining 3..
** Time: 1,046.
Handler for D (2) finished:
latency 7. + duration 14. = response time 21.
Event A simulated using handler load.
Event B simulated using handler load.
Handler for C (0) starting, time remaining 700
** Time: 1,979.33
Handler for C (0) finished:
latency 46. + duration 933.333 = response time 979.333
16-53 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-53
16-54 *
* 16-54
- Loaded Event Handlers -
Event C: ld. factor, 0.75; ld. dur, 933.333 load set A, B
Event E: ld. factor, 0.75; ld. dur, 1333.33 load set A, B
Event F: ld. factor, 0.714074; ld. dur, 700207. load set A, B, C, E
Event A simulated using handler load.
Event B simulated using handler load.
** Starting simulation...
================= D(1) Worst-Case Response. ====================
** Time: 1,000.
Interrupt C (0) requested.
Handler for C (0) starting, time remaining 700
** Time: 1,000
Interrupt D (0) requested.
** Time: 1,000.
Interrupt D (1) requested.
** Time: 1,933.33
Handler for C (0) finished:
latency 0. + duration 933.333 = response time 933.333
Normal simulation of A resuming.
Normal simulation of B resuming.
Handler for D (0) starting, time remaining 11
** Time: 1,934.
Interrupt B (0) requested.
Handler for D (0) preempted.
Handler for B (0) starting, time remaining 2
** Time: 1,936.
Handler for B (0) finished:
latency 0. + duration 2. = response time 2.
Handler for D (0) resumed, time remaining 10.3333.
** Time: 1,941.
Interrupt A (0) requested.
Handler for D (0) preempted.
Handler for A (0) starting, time remaining 3
** Time: 1,944.
Handler for A (0) finished:
latency 0. + duration 3. = response time 3.
Handler for D (0) resumed, time remaining 5.33333.
** Time: 1,949.33
Handler for D (0) finished:
latency 933.333 + duration 16. = response time 949.333
Event A simulated using handler load.
Event B simulated using handler load.
Normal simulation of A resuming.
Normal simulation of B resuming.
Handler for D (1) starting, time remaining 11
** Time: 1,954.
Interrupt B (1) requested.
Handler for D (1) preempted.
Handler for B (1) starting, time remaining 2
** Time: 1,956.
Handler for B (1) finished:
latency 0. + duration 2. = response time 2.
Handler for D (1) resumed, time remaining 6.33333.
16-54 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-54
16-55 *
* 16-55
** Time: 1,961.
Interrupt A (1) requested.
Handler for D (1) preempted.
Handler for A (1) starting, time remaining 3
** Time: 1,964.
Handler for A (1) finished:
latency 0. + duration 3. = response time 3.
Handler for D (1) resumed, time remaining 1.33333.
** Time: 1,965.33
Handler for D (1) finished:
latency 949.333 + duration 16. = response time 965.333
16-55 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-55
16-56 *
* 16-56
- Loaded Event Handlers -
Event C: ld. factor, 0.75; ld. dur, 933.333 load set A, B
Event E: ld. factor, 0.717; ld. dur, 1394.7 load set A, B, D
Event F: ld. factor, 0.681074; ld. dur, 734135. load set A, B, C, D, E
Event A simulated using handler load.
Event B simulated using handler load.
Event D simulated using handler load.
================= E(0) and F(0) Worst-Case Latency and Response.==========
** Time: 1,000.
Interrupt C (0) requested.
Normal simulation of D resuming.
Handler for C (0) starting, time remaining 700
** Time: 1,000
Interrupt F (0) requested.
** Time: 1,000
Interrupt E (0) requested.
** Time: 1,288.33
Interrupt D (0) requested.
** Time: 1,621.67
Interrupt D (1) requested.
** Time: 1,933.33
Handler for C (0) finished:
latency 0. + duration 933.333 = response time 933.333
Event D simulated using handler load.
Normal simulation of A resuming.
Normal simulation of B resuming.
Normal simulation of D resuming.
Handler for D (0) starting, time remaining 11
** Time: 1,934.
Interrupt A (0) requested.
Handler for D (0) preempted.
Handler for A (0) starting, time remaining 3
** Time: 1,937.
Handler for A (0) finished:
latency 0. + duration 3. = response time 3.
Handler for D (0) resumed, time remaining 10.3333.
** Time: 1,941.
Interrupt B (0) requested.
Handler for D (0) preempted.
Handler for B (0) starting, time remaining 2
** Time: 1,943.
Handler for B (0) finished:
latency 0. + duration 2. = response time 2.
Handler for D (0) resumed, time remaining 6.33333.
** Time: 1,949.33
Handler for D (0) finished:
latency 645. + duration 16. = response time 661.
Event A simulated using handler load.
Event B simulated using handler load.
Event D simulated using handler load.
Normal simulation of A resuming.
Normal simulation of B resuming.
Normal simulation of D resuming.
16-56 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-56
16-57 *
* 16-57
Handler for D (1) starting, time remaining 11
** Time: 1,954.
Interrupt A (1) requested.
Handler for D (1) preempted.
Handler for A (1) starting, time remaining 3
** Time: 1,955.
Interrupt D (2) requested.
** Time: 1,957.
Handler for A (1) finished:
latency 0. + duration 3. = response time 3.
Handler for D (1) resumed, time remaining 6.33333.
** Time: 1,961.
Interrupt B (1) requested.
Handler for D (1) preempted.
Handler for B (1) starting, time remaining 2
** Time: 1,963.
Handler for B (1) finished:
latency 0. + duration 2. = response time 2.
Handler for D (1) resumed, time remaining 2.33333.
** Time: 1,965.33
Handler for D (1) finished:
latency 327.667 + duration 16. = response time 343.667
Event A simulated using handler load.
Event B simulated using handler load.
Event D simulated using handler load.
Normal simulation of A resuming.
Normal simulation of B resuming.
Normal simulation of D resuming.
Handler for D (2) starting, time remaining 11
** Time: 1,974.
Interrupt A (2) requested.
Handler for D (2) preempted.
Handler for A (2) starting, time remaining 3
** Time: 1,977.
Handler for A (2) finished:
latency 0. + duration 3. = response time 3.
Handler for D (2) resumed, time remaining 2.33333.
** Time: 1,979.33
Handler for D (2) finished:
latency 10.3333 + duration 14. = response time 24.3333
Event A simulated using handler load.
Event B simulated using handler load.
Event D simulated using handler load.
Handler for E (0) starting, time remaining 1000
** Time: 3,374.03
Handler for E (0) finished:
latency 979.333 + duration 1394.7 = response time 2374.03
Event C simulated using handler load.
Event E simulated using handler load.
Handler for F (0) starting, time remaining 500000
** Time: 737,509.
Handler for F (0) finished:
latency 2374.03 + duration 734135. = response time 736509.
16-57 EE 4770 Lecture Transparency. Formatted 12:36, 7 April 1999 from lsli16*
*. 16-57
| David M. Koppelman - koppel@ee.lsu.edu | Modified 7 Apr 1999 12:36 (17:36 UTC) |