Symbolic Timing Analysis for Systems SymTA

SymTA/S

Symbolic Timing Analysis for Systems SymTA

SymTA /S /S Symbolic

Symbolic Timing Analysis Timing Analysis for for Systems Systems

Razvan Racu Arne Hamann

ARTIST2 PhD Course, June 12, DTU Copenhagen, Denmark

Day schedule Day schedule

0900 – 0945 Introduction to system performance verification 1000 – 1045 Compositional performance analysis

1100 – 1200 Hands-on tutorial 1: Basics SymTA/S

1330 – 1415 Sensitivity analysis

1430 – 1515 Design space exploration and robustness optimization 1530 – 1630 Hand-on tutorial 2: Advanced SymTA/S features

1630 – 1700 Discussion

System

System design design challenges challenges

Functional vs. performance verification Functional vs. performance verification

ƒ Separate function verification from performance verification

ƒ functional verification/test determines functional correctness independent of the target architecture

ƒ performance verification/test determines platform adherence to

ƒ load conditions and response times (deadlines)

ƒ jitter bounds

ƒ buffer sizes

This presentation is about performance verification !!

Introduction Introduction

implementation language architecture layer

application layer

subsystem 2 Simulink

input language 2 subsystem 3 subsystem 1

IP

UML

application development

M

CoP M

M P DSP

M P

core RTOS

I/O Int Bus- CTRL timer timer drivers RTOS-APIs

application

implementation

target platform system function

Embedded system platform properties Embedded system platform properties

ƒ ES platforms are heterogeneous

ƒ components

ƒ networks

ƒ communication

ƒ scheduling (static, dynamic, event-, time-driven, ...)

ƒ ...

ƒ Heterogeneity results from

ƒ hardware and software component specialization (cost, power, dependability)

ƒ HW/SW reuse

CoPro

Heterogeneous

Heterogeneous resource resource sharing sharing

VLIW ^MEM IPIP ^MEM IPIP

RISC ^MEM DSP

com. com. netwnetw..

static execution order scheduling static priority

scheduling FCFS scheduling

earliest deadline TDMA scheduling

proprietary

Exemple

Exemple 1 : MPSOC 1 : MPSOC

ƒ Heterogeneity resulting from

ƒ hardware and software component specialization

ƒ reuse

External Bus Unit External Bus Unit

SRAM (32 KB) I-Cache (1 KB) ROM (4 KB) SRAM (32 KB) I-Cache (1 KB) ROM (4 KB)

FPI Bus

CAN Bus Interface (2)

CAN Bus Interface (2)

System Timer System Timer Data SRAM

(40 KB) Data SRAM

(40 KB)

Peripheral Core Processor Peripheral

Core Processor

Ports Ports RAM

(4 KB) RAM (4 KB)

Code RAM (16 KB) Code RAM (16 KB)

Bus Interface Bus Interface ASC(2)

ASC(2)

SSC(2) SSC(2)

ADC(2) ADC(2)

GPTA(1) GPTA(1)

Tricore

External Bus Unit External Bus Unit

SRAM (32 KB) I-Cache (1 KB) ROM (4 KB) SRAM (32 KB) I-Cache (1 KB) ROM (4 KB)

FPI Bus

CAN Bus Interface (2)

CAN Bus Interface (2)

System Timer System Timer Data SRAM

(40 KB) Data SRAM

(40 KB)

Peripheral Core Processor Peripheral

Core Processor

Ports Ports RAM

(4 KB) RAM (4 KB)

Code RAM (16 KB) Code RAM (16 KB)

Bus Interface Bus Interface ASC(2)

ASC(2)

SSC(2) SSC(2)

ADC(2) ADC(2)

GPTA(1) GPTA(1)

Tricore

TriCore 1775 (automotive) Philips VIPER (consumer)

Bus

core core

RTOS

I/O Int Bus- CTRL timer timer I/O Int Bus- CTRL timer timer drivers RTOS-APIs

application

cache

mem

private

private

private private

shared

architecture application

architecture application

ce₁ pe₁

API

multilayered SW

Example

Example 2: Automotive Platform 2: Automotive Platform

ƒ Heterogeneous

ƒ 50+ ECUs

ƒ many suppliers

ƒ several RTOSes and protocols

ƒ strongly networked

ƒ Complex

ƒ end-to-end deadlines

ƒ hidden dependencies

ƒ global memories

ACC

ABS

ESP ASR

engine

control powertrain control

gateway

ECU₁

diagnosis

CAN₁ CAN₂

ECU₂ ECU₃

ECU₄ ECU₅ ECU₆

ECU₈ ECU₇

Function 2

Function 1 Function 3

BSW RTE Function 1

CAN

N7 M2

BSW RTE Function 2

N7 M2

BSW RTE Function 3

N7 M2

End End -to - to- - end times do not easily compose end times do not easily compose

end to

nd RFunction

RFunction

RFunction

t t t

t

+

+

≠

end to

t

Design as integration problem Design as integration problem

M2 IP₂

M3

M1

Bus

IP₁ DSP

CPU HW

Integration ^M2

IP₂ M3

DSP

IP₁

subsystem 2

M₁

HW

CPU

subsystem 1

P1

P3 P2

Sens

Sens

subsystem 2 subsystem 1

ƒ System design is to a large extend an integration problem

Coupling

Coupling effects effects – – a a closer closer look look

ƒ Example: 3 periodic tasks on CPU send data over the bus

ƒ Static priority scheduling on CPU: P1 > P2 > P3

P₁ P₂ P₃

IP₂ M2 M3

M1

Bus

IP₁ DSP

CPU HW Sens

Coupling

Coupling effects effects – – creation creation of of bursts bursts

ƒ Complex execution traces with dynamic behavior

ƒ Burst events at the output

ƒ Consequences: transient overload, missed deadlines,

T₁

T₂

T₂

T₂

T₂

P₃ P ₂

Priorität

periodic input

bursty output P₁

t

Scheduling

Scheduling anomalies anomalies

ƒ System corner-cases different of component corner-cases

minimum bus load maximum execution time

minimum execution time

maximum bus load

P₁ P₂ P₃

IP₂ M2 M3

M1

Bus

IP₁ DSP

CPU HW Sens

Key platform design challenges Key platform design challenges

ƒ Increasing system complexity

ƒ from single processor to multi-processor (MpSoC)

ƒ from buses to networks (NoC)

ƒ Complex dependencies and modifications threaten design robustness

ƒ Global end-to-end constraints added for control applications

ƒ Integration under optimization requirements

ƒ cost (memory, power, …)

ƒ robustness

ƒ extendibility – consider upcoming features, SW updates, platform updates in product lines

ƒ Reliable system integration is key requirement

ƒ Performance verification required at every design stage

Requirements

System Design System Test

Requirements Test

Module Design

Function Design Function Test

Module Test Architecture

Exploration

Network Timing Estimation

Timing is everywhere Timing is everywhere

ECU Timing Estimation

ECU Timing Verification

Network Timing Verification

System- Timing Verification

Performance

Performance verification verification flow flow

Target architecture performance

Target architecture performance – – general view general view

process execution model P₁ P₂

P₁

M

IP

M P M P

M

global system execution model

activation

component and communication execution model

Process execution model

single process execution P₁

then ...

else { send(...);

receive (...);

... } for { ...

..}

if ... b₁

b₂

b₃ b₄

P

ƒ Influenced by

ƒ execution path

ƒ data dependent

ƒ execution path timing

ƒ target architecture dependent

ƒ process communication (here: message passing)

ƒ execution path dependent

ƒ communication volume

ƒ data and type dependent

execution time analysis

Process timing and communication Process timing and communication

ƒ State of industrial practice - simulation/performance monitoring

ƒ trigger points at process beginning and end

ƒ data dependent execution Æ upper and lower timing bounds

ƒ simulation challenges

ƒ coverage?

ƒ cache and context switch overhead due to run-time scheduling with process preemptions

ƒ Alternative - formal analysis of individual process timing

ƒ provides conservative bounds

ƒ serious progress in recent years

Formal process execution time analysis Formal process execution time analysis

ƒ Active research area with dedicated events (e.g. Euromicro WS)

ƒ Formal analysis using simple processor models

ƒ Li/Malik (Princeton) (95): Cinderella

ƒ Detailed execution models with abstract interpretation

ƒ Wilhelm/Ferdinand (97 ff.): commercial tool AbsInt

ƒ Combinations with simulation/measurement of program segments

ƒ Wolf/Ernst (99): SymTA/P

ƒ All tools provide (conservative) upper execution time bounds (WCET) or time intervals (WCET/BCET)

Component and communication execution model

P₁ P₂ activation

P₁

M

IP

M P M P

M ƒ Influenced by

ƒ resource sharing strategy

ƒ process activation

single component real-time analysis

Component and communication execution model Component and communication execution model

ƒ Resource sharing strategy

Æ process and communication scheduling

ƒ static execution order

ƒ time driven scheduling

ƒ fixed: TDMA

ƒ dynamic: Round-Robin

ƒ priority driven scheduling

ƒ static priority assignment: RMS, SPP

ƒ dynamic priority assignment: EDF

ƒ Timing depends on environment model

ƒ determines frequency of process activations or communication

CoPro

Scheduling

Scheduling Analysis Analysis Techniques Techniques

VLIW ^MEM IPIP ^MEM IPIP

RISC ^MEM DSP

SYSTEM BUS SYSTEM BUS

Lee/Messerschmidt 1989

Liu/Layland 1973 Buttazzo 1993

Sha 1994 Kopetz 1993

from IP vendor

Example: Rate Monotonic Scheduling (RMS) Example: Rate Monotonic Scheduling (RMS)

ƒ Very simple system model

ƒ periodic tasks with deadlines equal to periods

ƒ fixed priorities according to task periods

ƒ no communication between tasks

ƒ (theoretically) optimal solution for single processors

ƒ several practical limitations but good starting point

ƒ Schedulability tests for RMS guarantee correct timing behavior

ƒ processor utilization (load) approach

ƒ response time approach (basis for many

RMS RMS Theory Theory – – The The response response time time approach approach

ƒ Critical instant:

all tasks start at t=0 („synchronous assumption“ to ensure maximum interference in the beginning of task execution)

ƒ when each task meets its first deadline, it will meet all other future deadlines (proof exists!)

ƒ test by „unrolling the schedule“ (symbolic simulation)

deadline = period = 350 deadline is met

critical instant

RMS RMS Theory Theory – – The The response response time time formula formula

fix-point problem

response time

core execution time

T₁

C₂ T₂

T₂

C₂ T₂

C₂ T₂

T 2

priority

C₂

C₂

C₁ C₁

T1

Example

Example: : Static Static priority priority w/ w/ arbitrary arbitrary deadlines deadlines

ƒ Assume:

ƒ tasks with periods T, worst-case execution times C

ƒ static priorities

ƒ deadlines (arbitrary) larger than the period

Analysis

Analysis uses uses “ “ Busy Busy Window Window ” ” approach approach ( ( Lehoczky Lehoczky ) )

T₁ C₂ T₂

T₂

T 2

priority

C₂

C₁ C₁

T1

C₂ T₂

C₂ T₂

w₂(3)

2 * T₂ R₂(3)

find fix point where

equations hold!

Other

Other Extensions Extensions in Literature in Literature

ƒ Jitter and burst activation

ƒ Static and dynamic offsets between task activations

ƒ Different task modes

ƒ Execution scenarios

ƒ Blocking and non-preemptiveness

ƒ Scheduling overhead Æ context switch time

ƒ etc...

Global system execution model

P₁ P₂ activation

P₁

M

IP

M P M P

M

global real-time system analysis

ƒ influenced by

ƒ communication pattern

ƒ shared memory access

ƒ environment model

System

System performance performance analysis analysis

System performance analysis

System performance analysis - - state of the art 1/2 state of the art 1/2

ƒ Current approach: target architecture co-simulation, performance simulation

ƒ Simulation challenges

ƒ identification of system performance corner cases

ƒ different from component performance corner cases

ƒ complex phase and data dependent “transient” run-time effects w.

scheduling anomalies

ƒ target architecture behavior unknown to the application function developer

ƒ test case definition and selection?

ƒ simulation of incomplete application specifications ?

ƒ how to do design space exploration before code implementation is available?

System performance analysis

System performance analysis - - state of the art 2/2 state of the art 2/2

ƒ Load analysis

ƒ Example: “all deadlines are met if the resource load is below 69%”

ƒ Consider only average scenarios (no transient load)

ƒ No performance metrics Æ no constraint validation

ƒ Popular as a system level technique for safety critical systems design

ƒ Strict separation of subsystems

ƒ fixed allocation of memory

ƒ fixed allocation of communication resources

ƒ fixed allocation of computation resources

ƒ Spatial and temporal decoupling of resources

ƒ not-in-use allocated parts are locked

ƒ no coupling effects

ƒ Requires system synchronization …

ƒ … paid by timing overhead

Conservative

Conservative design design

Bus

TDMA 1/2 TDMA 1/2

Time Triggered System (TDMA)

ƒ periodic assignment of fixed time slots for communication and processing

ƒ unused slots remain empty

ƒ requires system synchronization

ƒ no coupling effects

time slot assigned to sender P1

context switching time

t_TDMA

t_P1 t_P2 t_P3 t_P1 t_P2 t_P3 t_P1 t_P2 t_P3

TDMA 2/2 TDMA 2/2

ƒ Predictable, independent system capacity

R_i response time P_i, C_i core execution time P_i

ƒ Used in avionics and automotive (TTP, FlexRay)

ƒ Can be used at system level (Giotto - Berkeley)

⎥ ⎥

⎢ ⎤

⎢

× ⎡

− +

=

Pi i Pi

TDMA i

i

t

t C t

C

R ( )

Conservative design

Conservative design - - Summary Summary

ƒ Limitations

ƒ low resource utilization

ƒ extended response times (problem for adaptive control engineering)

ƒ requires general time base (scalability?)

ƒ little flexibility (fixed time slots)

ƒ not a general solution

ƒ inefficiency (performance, bandwidth, costs, power) increases with system size

ƒ Time-triggered systems are a good example for systematic integration, but…

ƒ … reliable integration does not necessarily require conservative design style

System

System level level performance performance analysis analysis

ƒ Global approach („Holistic“)

ƒ local analysis scope extension to several subsystems

ƒ Compositional approach

ƒ global flow analysis combined with local scheduling analysis

Analysis

Analysis scope scope extension extension – – „ „ Holistic Holistic “ “

ƒ Coherent analysis („holistic“ approach)

ƒ Example: Tindell 94, Palencia/Harbour 98, Pop/Eles (DATE 2000, DAC 2002): TDMA + static priority – automotive applications

ƒ Problem: scalability

P2 P1

T

TTP bus interface

P3 P4

D

TTP bus interface queue

RTOS RTOS

TTP bus (TDMA) static priority

process scheduling static priority

queueing

T: Transmitter process

Analysis

Analysis scope scope extension extension ( ( cont‘d cont‘d ) )

ƒ Benefit: scope extension can take global system knowledge into account

ƒ Example: using dependency information to detect that P2 can

send in the same TDMA round as P1, if R_P2 < t_P3 + t_P4, where R_P2 is the worst-case response time of P2

P1

TDMA bus ^{P1 t}P3 t_P4 P2 t_P1 t_P3 t_P4 t_P2

t_round

t_P1

CPU1

HW1 P2

t_P2

P3 CPU2

Compositional

Compositional performance performance analysis analysis

After the break!

SymTA/S

Compositional performance analysis SymTA

SymTA /S /S Compositional

Compositional performance performance analysis analysis

Razvan Racu Arne Hamann

ARTIST2 PhD Course, June 12, DTU Copenhagen, Denmark

CoPro

Multiple

Multiple Scheduling Scheduling Strategies Strategies

VLIW ^MEM IPIP ^MEM IPIP

RISC ^MEM DSP

SYSTEM BUS SYSTEM BUS

static execution order scheduling static priority

scheduling FCFS scheduling

earliest deadline first scheduling TDMA scheduling

proprietary (abstract info)

CoPro

Corresponding

Corresponding Analysis Techniques Analysis Techniques

VLIW ^MEM IPIP ^MEM IPIP

RISC ^MEM DSP

SYSTEM BUS SYSTEM BUS

Lee/Messerschmidt 1989

Liu/Layland 1973 Buttazzo 1993

Sha 1994 Kopetz 1993

from IP vendor

CoPro

Integration ???

Integration ???

VLIW ^MEM IPIP ^MEM IPIP

RISC ^MEM DSP

SYSTEM BUS SYSTEM BUS

Lee/Messerschmidt 1989

Liu/Layland 1973 Buttazzo 1993

Sha 1994 Kopetz 1993

from IP vendor

? ? ?

? ?

BUS

TDMA

Compositional

Compositional approach approach

ƒ Tasks are coupled by event sequences

ƒ Composition by means of event stream propagation

ƒ apply local scheduling techniques at resource level

ƒ determine the behavior of the output stream

ƒ propagate to the next component

DSP

static order

CPU

fixed priority

P1 C1 P3

P2

C2 C4

C3 P4

P5

system input

system input system outputsystem output

Idea Idea

ƒ Use network calculus + additional information as intermediate mathematical formalism

ƒ Arrival curve functions of network calculus

ƒ η⁺(Δt) maximum number of activating events occuring in time window Δt

ƒ η^-(Δt) minimum number of activating events occuring in time window Δt

ƒ d^– minimum event distance - limits burst density

Event

Event specification specification

ƒ Derive event stream models with parameters

ƒ individual events replaced by stream variables

(vectors) with stream parameters period, jitter, min.

distance, …

ƒ derive arrival curve functions from model parameters

5

0 Δt

1 2 3 4

T J t− Δ

0

T J t+ Δ

–J +J

η(Δt)

⎥⎥⎤

⎢⎢⎡ +Δ

=

+ Δ

T J t) t

η (

⎥⎦⎥

⎢⎣⎢ −Δ

=

− Δ

T J t) t

η (

T: period J: jitter

5

0 Δt

1 2 3 4

T J t− Δ

0

T J t+ Δ

–J +J

η(Δt)

⎥⎥⎤

⎢⎢⎡ +Δ

=

+ Δ

T J t) t

η (

⎥⎦⎥

⎢⎣⎢ −Δ

=

− Δ

T J t) t

η (

T: period J: jitter

lower bound upper bound

SymTA

SymTA/S /S standard standard event event models models

ƒ Required by RTA

ƒ Periodic/sporadic

ƒ Periodic/sporadic with jitter

ƒ Periodic/sporadic with burst

increasing jitter due to execution/scheduling

Conditionaloutput

P P+J

S

P+B

S+J S+B

Input

Input – – output output event event model model relation relation

ƒ Any scheduling increases jitter

ƒ Jitter grows along functional path

ƒ Increasing jitter leads to

ƒ burst and transient overloads

ƒ higher memory requirements

ƒ power peaks

T₁ T₁

T₂ T₂ T₂

T₂ T₂ T₂

T₂ T₂

T₂ T₂

PE

scheduling PE

P2

P1

environment model

local analysis

derive output event model map to input event model

convergence?

schedulability?

YES

NO NO

YES

infeasible configuration

feasible configuration

System

System analysis analysis loop loop

Reducing

Reducing transient transient load load in design in design

ƒ Re-synchronization

ƒ Minimum event separation using „traffic shaping“

ƒ Requires memory and possibly increases latency

shaper

Traffic shaping

Traffic shaping - - example example

0 +J η(Δt)

3 4 5 6 5

T J t+ Δ

1 2

Δt T

J t− Δ ) (Δt η+

) (Δt η−

−

Δ d

t

0 +J η(Δt)

3 4 5 6 5

T J t+ Δ

1 2

Δt T

J t− Δ ) (Δt η+

) (Δt η−

−

Δ d

t

η(Δt)

3 4 5 6 5

T J t+ Δ

1

2 −

Δ d

t

Δt T

J t− Δ ) (Δt η+

) (Δt η−

d^- shaping

Optimization potential of Traffic Shaping Optimization potential of Traffic Shaping

16 25 28

d=10 6

d=10 6

d=12 8

d=12 8

RTA event models are not sufficient RTA event models are not sufficient

ƒ Event model transitions needed to couple different subsystems and scheduling domains

ƒ More complex activation models needed

ƒ OR activation

ƒ typical in event driven systems

ƒ AND activation and loops

ƒ typical for signal processing _AND

OR

Analysis

Analysis extensions extensions

environment model

local analysis

derive output event model map to input event model

convergence?

schedulability?

YES

NO NO

YES

System

System analysis analysis loop loop

environment model

context-aware analysis

derive output event model map to input event model

convergence?

schedulability?

YES

NO NO

YES

context

context infoinfo

Taking global dependencies into account Taking global dependencies into account

ƒ „intra-context“ dependencies

ƒ different events in a single event stream often activate different task behaviors with different execution times or communication loads

ƒ „inter-context“ dependencies

ƒ activating events in different event streams are often time-correlated which rules out the simultaneous

activation of all tasks

ƒ can be combined leading overall to less conservative analysis results

T⁵

T³

T⁸

R⁴ R³

T⁷

R⁵

T⁴

T⁹

S^ource

T6

T²

R²

R¹ T¹

CET = [2,2]

Priority=Mid

CET = [2,2]

Priority=High

CET = [2,2]

Priority=Low CET = [2,2]

Priority=High CET = [2,2]

Priority=Low

CET = [0,2]

Priority=High

CET = [10,10]

Priority=High

CET = [2,2]

Priority=Low CET = [2,8]

Priority=High

Motivating

Motivating Example Example

•Compositional performance analysis approach (Richter)

P = 50 J = 0

P₅ = 50 J₅ = 8

P₃= 50 J₃ = 8

P₈= 50 J₈= 6

•Static priority preemptive scheduling on all resources

T⁵

T³

T⁸

R⁴

CET = [2,2]

Priority=Mid

CET = [2,2]

Priority=High

CET = [2,2]

Priority=Low

R³ T⁷

CET = [2,2]

Priority=High

R⁵

T⁴

T⁹

S^ource

T6

T²

R²

CET = [2,2]

Priority=Low

CET = [0,2]

Priority=High

CET = [10,10]

Priority=High

CET = [2,2]

Priority=Low

R¹ T¹

CET = [2,8]

Priority=High

Lehoczky (1990) Lehoczky

Lehoczky (1990) (1990)

•Ignore correlation between tasks!

P = 50 J = 0

P₅ = 50 J₅ = 8

P₃= 50 J₃ = 8

P₈= 50 J₈= 6

T⁵

T³

T⁸

R⁴

CET = [2,2]

Priority=Mid

CET = [2,2]

Priority=High

CET = [2,2]

Priority=Low

R³ T⁷

CET = [2,2]

Priority=High

R⁵

T⁴

T⁹

S^ource

T6

T²

R²

CET = [2,2]

Priority=Low

CET = [0,2]

Priority=High

CET = [10,10]

Priority=High

CET = [2,2]

Priority=Low

R¹ T¹

CET = [2,8]

Priority=High

Lehoczky (1990) Lehoczky

Lehoczky (1990) (1990)

•Ignore correlation between tasks!

P = 50 J = 0

P₅ = 50 J₅ = 8

P₃= 50 J₃ = 8

P₈= 50 J₈= 6

Lehoczky (1990) Lehoczky

Lehoczky (1990) (1990)

T⁵

T³

T⁸

R⁴

CET = [2,2]

Priority=Mid

CET = [2,2]

Priority=High

CET = [2,2]

Priority=Low

P₅= 50 J₅ = 8

P₃= 50 J₃= 8

P₈ = 50 J₈= 6

2

2

T₈ 2

Priority

T₅

t

t critical instant

T₃

8 t

8

T⁵

T³

T⁸

R⁴

CET = [2,2]

Priority=Mid

CET = [2,2]

Priority=High

CET = [2,2]

Priority=Low

R³ T⁷

CET = [2,2]

Priority=High

R⁵

T⁴

T⁹

T6

T²

R²

CET = [2,2]

Priority=Low

CET = [0,2]

Priority=High

CET = [10,10]

Priority=High

CET = [2,2]

Priority=Low

R¹ T¹

CET = [2,8]

Priority=High

Tindell (1994) Tindell

Tindell (1994) (1994)

•Periodic arrival of events at system inputs as timing-reference

P = 50 J = 0 S^ource

Global Offset =

T⁵

T³

T⁸

R⁴

CET = [2,2]

Priority=Mid

CET = [2,2]

Priority=High

CET = [2,2]

Priority=Low

R³ T⁷

CET = [2,2]

Priority=High

R⁵

T⁴

T⁹

S^ource P = 50 J = 0

T6

T²

R²

CET = [2,2]

Priority=Low

CET = [0,2]

Priority=High

CET = [10,10]

Priority=High

CET = [2,2]

Priority=Low

R¹ T¹

CET = [2,8]

Priority=High

Tindell (1994) Tindell

Tindell (1994) (1994)

Φi earliest activation time of T_i relative to the periodical arrival of an external

Φ7

Φ1

Φ2

Φ3

Φ8 Φ⁹ Φ6 Φ⁵

Φ4

14 Φ⁵=

2 Φ³ =

4 Φ⁸ =

14 Φ⁵ =

2 Φ³=

4 Φ⁸ =

Tindell (1994) Tindell

Tindell (1994) (1994)

T₈

Priority

T₅

t

t

T₃

t T⁵

T³

T⁸

R⁴

CET = [2,2]

Priority=Mid

CET = [2,2]

Priority=High

CET = [2,2]

Priority=Low

P₅= 50 J₅ = 8

P₃= 50 J₃= 8

P₈ = 50 J₈= 6

Φ5

Φ8

external event arrival

Φ3

critical instant

14 Φ⁵ =

2 Φ³=

4 Φ⁸ =

Tindell (1994) Tindell

Tindell (1994) (1994)

T₈

Priority

T₅

t

t

T₃

t T⁵

T³

T⁸

R⁴

CET = [2,2]

Priority=Mid

CET = [2,2]

Priority=High

CET = [2,2]

Priority=Low

P₅= 50 J₅ = 8

P₃= 50 J₃= 8

P₈ = 50 J₈= 6

Φ5

external event arrival

Φ3

critical instant

2

2

2

Further

Further Techniques Techniques

ƒ Relative offsets and relative jitter

ƒ Extends idea of global offsets

ƒ Describes the earliest activation time of a task relative to a timing-reference ref

ƒ Reference is not necessarily a periodic external event

ƒ Enables tighter response time calculation

ƒ Precedence relations

ƒ Explicitly considers precedence relations between tasks (i.e. task i cannot start until task j has finished execution)

ƒ Orthogonal to offset based techniques