Systèmes Réactifs et Programmation Synchrone

LPMI – option IREEL Systèmes réactifs et programmation synchrone - 2006

Marie-Agnès Peraldi-Frati 1

Systèmes Réactifs et Programmation Synchrone

LPSILOption InfoRmatique Embarquée

et résEaux sans fiL

Marie-Agnès Peraldi-Frati

Mise en œuvre des STR 30h• Approche Asynchrone• Ordonnancement TR• RTLinux

Cours IREEL

Mise en œuvre des STR 30h• L’Approche synchrone• Vérification • Simulation

Problématique des STR 15hUML Temps réel 30h

Réseaux sans fil 30hRéseaux filaires 15h

• FIP •OSEK• CAN

• Wan: GSM GPRS

• LAN : 802.11

• PAN Bluetooth

Administration de système linux30h - Installation

- configuration

OS embarqué 15h

- Windows CE ?

- Linux embarqué ?

Programmation JavaCArd 9h



Caractéristiques des Applications embarquées

Systèmes à contrôler+

Comportement attendu

Objectif Réalisation

Caractéristiques des systèmes embarqués

Outilsd’analyse

Modèles

Générateurs

Moyens

Analyse de propriétés

Plate-formed’étude et dedéveloppement

Systèmes à contrôler+

Comportement attendu



Génie logiciel et temps réel

Spécification

fonctionnelle

Modélisation

Conception

Implantation

Test unitaire

Simulation

Validation


• Implantation : Logiciel / matériel

• Spécification : contrat clair entre intervenants d’un projet

–Spécification fonctionnelle

–Contraintes temporelles et logiques

–Propriétés à vérifier

• Modélisation : formalisation des besoins

–Modèle asynchrones : tâches

–Modèles synchrones : automates

• Conception : Langages (C, C++, Assembleur, VHDL …)



Modèles Synchrones


Spécification

fonctionnelle

Modélisation

Conception

Implantation

Test unitaire

Simulation

Validation

Approches formelles

Objectifs : • Modéliser un système

• Valider les propriétés : logiques, temporelles

• Génération de code pour simulation

• Génération de code embarqué



Langages synchrones

• Approche formelle– Outils de simulation (XES)– Outils de preuve (XEVE)

• Adaptés aux systèmes réactifs – « Les systèmes réactifs [Harel 85] réagissent

immédiatement à leur environnement. Activés par

leurs entrées ils réagissent de manière réflexe en

produisant des sorties»– Cette définition caractérise parfaitement les

langages synchrones

Exemple de systèmes réactifs à Contrôle prépondérant

• Contrôle de processus temps-réel• Systèmes embarqués• Supervision de systèmes complexes• Protocoles de communication *• Pilotes de périphériques• Contrôleurs matériels• interface homme-machine



Systèmes réactifs etprogrammation synchrone

• Les approche formelles pour les STR • Le paradigme synchrone• Langages impératifs synchrones

(Esterel)• Formalismes graphiques synchrones

(SyncCharts)• Sémantiques

Caractérisation des approches synchrones

• Réactivité– possibilité de répondre à tout stimuli– !! Ne pas en perdre

• Déterminismemême séquence d ’entrée

⇒ même séquence de sortie

– Permet d’établir les propriétés de safety– Différence avec Statecharts (Harel 85)



Hypothèses synchrones

• Signaux : – support de communication– Signaux purs ou valués– Simultanéité des signaux – Echantillonnage parfait

Les hypothèses utilisées dans les langages synchrones facilitent l’expression des modèles

• Temps logique : – multiforme ( Seconde, mètre, top …)


• Réactions en temps nul – Instants d’exécution

tick Temps physiqueO0

I1

O1 O2

I3

O3O2

I2

– En pratique : temps de réaction plus court que le délai inter-évènements

tick Instants logiques

I1 I3I2

O1O2O0O3O2




• Perception globale :

– diffusion instantanée des signaux entre modules

Réaction instantanée

Exemple : tic-tac

ENTREE

COMPTEUR

TIC

TAC

ENTREE

COMPTEUR(1)TAC

ENTREE

COMPTEUR(2)TIC TIC

ENTREE

COMPTEUR(3)

°°°Signaux

Hors stimuli : pas de réaction



Programmation impérativesynchrone

Introduction : ABRO

• Entrées : A, B, R• Sortie : O• Comportement :

– O doit être émis dès qu’il y a eu occurrences de A et B depuis la dernière occurrence de R

– R est un signal prioritaire qui annule les occurrences de A et de B.



Traces pour ABRO

Instants

R

A

B

O

1

0

0

0

0

2

1

0

0

0

3

0

0

0

0

4

0

1

0

0

5

0

0

0

0

6

0

0

1

1

7

0

1

1

0

8

1

1

1

0

9

0

0

1

0

10

0

1

0

1

Machine de Mealy : ABRO

010/0

R A B/ O

001/01- -/01- -/0

1- -/0011/1

0 - 1/1 01- /1

0 - 0/0

0 0 - /0

0 - - /0

000/0

1- -/0



Partie impérative

Partie

déclarative

Esterel : ABRO

module ABRO:

input A,B,R;

output O;

loop

await R;

loop

[await A || await B];

emit O

each R

end loop

end module

Style de programmation

• Langage simple :– peu de primitives– écrire une fois, utiliser partout

• Contrôle– séquence (;), parallélisme (||)– préemption ( loop … each )



Style de programmation

• Modéliser le temps c’est manipuler des signaux – emit : diffusion instantanée des signaux – await : attente et réception d’un signal.

Temps d’exécution d’au moins un tick

• Signaux diffusés entre les modules • Signaux purs ou valués

=> Présence et/ou valeur d’un signal

Instruction en temps nulBoucle sans fin

Style de programmation• Tout programme doit « prendre un temps

d’exécution fini »

module PAS_CORRECT:

input Start;

output res: integer ;

var v : integer in;

await Start;

loop

v=v+1;

end loop

emit res(v);

end var

end module



Present test la présence

d’un signal

Ne prend pas de temps

Style de programmation• Autre exemple d’instruction en temps nul : present

module PAS_CORRECT_AU_DEBUT_MAIS_APRES_OUI:

input I;

output LA, PAS_LA ;

loop

present I then

emit LA;

else

emit PAS_LA;

end present

end loop

end module

prend du temps pause;



Watchdogs

• Entrées :– set : integer– reset– second

• Sortie :– alarm

Watchdogsmodule Watchdoginput set : integer, reset, second;output alarm;var D : integer inloop

await set; D=?set; abort

await D second; emit alarm;

when reset;end loopend varend module



Signaux valués

• Entrées : Revolution, Second• Sortie: Rpm : integer• Comportement:

à chaque occurrence de Second, émettre le nombre de tours par minute (Rpm). Soit 60 fois le nombre de tours comptabilisé depuis la dernière occurrence de Second. Chaque tour est signalé par Revolution.

Signal valué

Commentaire, %{ … }%% Tachometer

module TACHO:

input Revolution, Second;

output Rpm: integer;

loop

var Rnb := 0 : integer in

abort

every Revolution do

Rnb := Rnb + 1

end every

when Second do

emit Rpm(Rnb*60)

end abort

end var

end loop

end module

Variable avec sa portée

Préemptions



TAXI (C. André)

Exemple : calcul du prix d’une course de taxi

• Charge fixe

• Prix à la minute (TUCharge)

• Prix au kilomètre (DUCharge)

Fonction

constantes

Partage d’information

module TAXI:

input Km, Second, Go, Stop;

output Charge:integer;

constant FixedCharge:integer,

TUcharge:integer, DUcharge:integer;

function PLUS(integer,integer):integer;

await Go;

% a taxi drive ...

end module

Pas de variable partagée. Le partage d ’information sefait par diffusion instantanée de signaux



Fonction de

combine

Emissiondu résultat

Valeurdu signal

signal AddCharge: combine integer with PLUS in

var Amount := FixedCharge:integer in

abort

when Stop do

emit Charge(Amount)

end abort

end var

end signal

every Km do

emit AddCharge(DUCharge)

end every

every 30 Second do

emit AddCharge(TUCharge)

end every||

Signaux locaux

every AddCharge do

Amount := Amount + ?AddCharge

end every||

Abstraits pourEstérel

Module générique

module TopMeter:

type T;

function Mult(integer,T):T;

constant K:T;

input Top, Get;

output Got:T;

% imperative code

end module

fonction

type



% body

loop

var Nb := 0 : integer in

end var

end loop

every Top do

Nb := Nb + 1

end every

abort

when Get do

emit Got( Mult(Nb,K) )

end abort

Instanciation

module GetSpeed:

function intMult(integer,integer):integer;

function floatMult(integer,float):float;

input WheelRev, ShaftRev;

input IgnitionON, IgnitionOFF, Second;

output Rpm:integer, Speed:float;

constant TachoK:integer, SpeedK:float;

% body

end module



instanciations

await IgnitionON;

abort

||

when IgnitionOFF

run TACHO/TopMeter [

type integer/T;

function intMult/Mult;

signal ShaftRev/Top, Second/Get, Rpm/Got;

constant TachoK/K ]

run SPEED/TopMeter [

type float/T;

function floatMult/Mult;

signal WheelRev/Top, Second/Get, Speed/Got;

constant SpeedK/K ]

Renommage:actual/formal

Préemptions

• Variante différée/immédiate… when immediate occ

• Jusqu’à présent: forme abortive forteabort … when … do … end abort

• Avortement faibleweak abort … when … do … end abort

• Suspensionsuspend … when …



Runner (G. Berry)

module Runner:

constant NumberOfLaps: integer;

input Morning, Second, Meter;

input Step, Lap;

output Walk, Jump, Run;

input relation Lap => Meter;

input relation Morning => Second;

% body

end module

every Step do

emit Jump

end every

abort

when 15 Second;

sustain Run

abort

sustain Walk

when 100 Meter;

abort

when Lap

repeat NumberOfLap times

end repeat

every Morning do

end every



Module

module module-ident :

déclarations

corps

end module

Instructions impératives classiques

nothing

call proc-id (var-list)(val-list)

stat1 ; stat2

stat1 || stat2

loop stat end loop

if b-expr then stat1 else stat2 end if

trap trap-id in stat end trap

exit trap-id

var var-dcl in stat end var

var-id := expr



valué

pur

Instructions réactives primitives

Signal local :

signal sig-dcl in stat end signal

Émission de signal:

emit sig-id ou emit sig-id (expr)

Test de signal:

present sig-id then

stat1

else

stat2

end present

halt % ne fait rien pour toujours

abort stat when occ % préemption forte

halt

stat

abort

stat

abort

occavortement

Terminaison

normale

nothing % ne fait rien instantanément

nothing



occ

Représente la présence d’un signaldans sa forme la plus simple.

On peut considérer des occurrences complexesen combinant les présences par les opérateurs :

and or not

On écrit alors l ’expression entre [ ]

On peut également utiliser des gardes complexes :

int-expr occ-complexe

abort

…

when S

abort

…

when [S and T]

abort

…

when 5 S

trap trap-id in stat end trap

exit trap-id

stat

trap T

stat

trap T

Exit Texception

terminaison

normale



trap T in

trap U in

…

present A then exit T end present;

…

present B else exit U end present;

…

end trap ; % trap U

… stat2

end trap ; % trap T

… stat3

Instructions réactives dérivées

await occ ≡ abort halt when occ

occ

pause ≡ await tick

ticktick



do stat upto occ ≡ abort stat; halt when occ

stat

upto

occ

stat

upto

occ

abort

stat

when occ

handle

handler

end abort

≡

trap T in

abort

stat ;

exit T

when occ ;

handler

end trap

Trap avec handler d’exception

trap trap-id in

stat

handle trap-id do

handler

end trap trap T, E in

statE ;

exit E

||

statT ;

exit T

handle E do

statHandleE;

handle T do

stathandleT;

end trap ;

Variante :liste de trap-idet plusieurs handlers



Boucles temporelles

loop

stat

each occ

≡

loop

do stat upto occ

end loop

sustain S ≡

loop

emit S

each tick

every occ do

stat

end every

≡

await occ ;

loop

stat

each occ

repeat int-expr times

stat

end repeat

var v := int-expr : integer in

trap T in

loop

if v>0 then

stat ; v := v - 1

else

exit T

end if

end loop

end trap

end var



await

case occ1 do

stat1

case occ2 do

stat2

end await

Déterministe :prend la première occurrenceet si plusieurs : la premièredans l’ordre d’écriture

trap T1 in

trap T2 in

abort

await occ2 ; exit T2

when occ1 ; exit T1

handle T2 do

stat2

end trap

handle T1 do

stat1

end trap

Instructions nouvelles (v5)

Cette syntaxe est conseillée

Present :

present

case occ1 do

stat1

case occ2 do

stat2

…

else

stat

end present

If :

if :(cond1) then

stat1

elsif : (cond2) then

stat2

…

else

stat

end if



Préemptions : Strong abort

do

stat

watching occ

timeout

handler

end do

abort

stat

when occ do

handler

end abort

Cas de préemptionsmultiples.Déterministe !

abort

stat

when

case occ1 do stat1

case occ2 do stat2

…

case occN do statN

end abort

trap T in

stat ;

exit T

||

await occ ;

exit T

end trap

Weak abort

weak abort

stat

when occ do

handler

end abort

Suspension

suspend

stat

when occ

Existe aussi

en version

avec préemptions

multiples



Instanciation de module

run• Réutilisation d’un module•Possibilité de renommage des

•types, signaux,

•constantes, fonctions,

•procédures, tâches,

•nom du module

category new-id/old-id , … ;

Syntaxe du renommage

TâchesLes tâches permettent de programmer des activitésqui « durent », contrairement aux fonctions et procéduresqui sont instantanées.L ’exécution d ’une tâche est asynchrone par rapport au programme Estérel. Une tâche est lancé par exec et saterminaison est capturée par un signal return.

Déclarations :

task task-id(type-ref-list)(type-val-list);

return sig-id : type;

Appel :exec task-id(param-ref-list)(param-val-list)

return sig-id



Programmes incorrects

Rappelons qu’un programme Estérel doit êtreRéactif et Déterministe

Boucle instantanée

loop

emit S

end loop

loop

emit S ;

pause

end loop

Cycles de causalité

Les sorties peuvent être « ré-injectées » en entrée. Il peut en résulter des programmes non réactifs ounon déterministes.

Programmes non réactifs

signal S in

present S then

nothing

else

emit S

end present

end signal

signal S:combine

integer with + in

...

emit S (?S+1);

...

end signal



Programmes non déterministes

signal S in

present S then

emit S

else

nothing

end present

end signal

2 solutions :S absent ouS présent

signal S:integer in

emit S(?S)

end signal

Infinité de solutions

Système d’acquitement

Req

Top

Alarme

OK

OQP



Application : TOP/REQ

TOP TOP TOP TOP TOP

REQ OK REQ OK REQ OKREQ OQP

ALARME

module TOPREQ:

input TOP, REQ;

output OK, OQP, ALARME;

relation TOP # REQ;

signal DONE, QUERY in

% gestion de TOP

||

% Mémorisation

end signal

end module



% gestion de TOP

every TOP do

emit QUERY;

present DONE else

emit ALARME

end present

end every

% mémorisation

loop

await REQ;

emit OK;

abort

when QUERY do

emit DONE

end abort

end loop

every REQ do

emit OQP

end every

0 1 2

REQ/OK

TOP/

TOP/ALARME

REQ/OQP1

23 1

23

TOP



Application : monostable

N Tops

Zup

Top

MRLup:entier

Zdown

n1 n2 n3 n4

Z

d1

d2

d3

pendant d1 il y a eu moins de n1 occurrences de Toppendant d2 il y a eu moins de n2 occurrences de Toppendant d3 il y a eu n3 occurrences de Top

valeur

Lup

1 30

2

1

2

1

2

2

1

3

1

2

Lup / Zup,Cpt:=?Lup

Lup / Zup,Cpt:=?Lup

Lup / Cpt:=?Lup

Lup / Zup,Cpt:=?Lup

Top.Cpt==1 / Zdown

Top / Cpt--

4



Extensions récentes

• Opérateur prepre(S)pre(?S)

• Finalizefinalize

pwith

qend finalize

pre

every [not pre(S) and S] do

emit risingEdgeS

end every

input Top;

output TopNb := 0 :integer;

every Top do

emit TopNb(pre(?TopNb)+1)

end every



Traduction de pre(S)trap T in

signal S, preS in

p;

exit T

||

loop

present S then

pause;

emit preS

else

pause

end present

end loop

end signal

end trap

Traduction de pre(?S)trap T in

signal S := v : Type, preS := v :

Type in

p;

exit T

||

loop

present S then

var preval := ?S in

pause;

emit preS (preval)

end var

else

pause

end present

end loop

end signal

end trap



pre + suspendmodule SuspPre:

input Top,A;

output rEdge;

suspend

signal S in

every A do emit S end every

||

every [S and not pre(S)] do

emit rEdge

end every

end signal

when immediate [not Top]

end module

Dernières volontésabort

p

||

abort

q

when B do

emit b

end abort

when A do

emit a

end abort

quand occurrence de A

On émet a

Mais pas b

Dernière volonté de q

Dernière volonté de p



finalize

• le corps termine,

• le corps lève une exception englobante,

• une instruction parallèle sort d'un trap qui contient une instruction finalize,

• l'instruction finalize est préemptée par une préemption faible ou forte.

Le finalizer code est exécuté quand :

finalize p with q end finalize

finalizevar X := 0 : integer in

abort

finalize

abort

finalize

halt

with

X := 2;

emit O1(X)

end finalize

when J do

X := X*3;

emit O2(X)

end abort

with

X := X + 5;

emit O3(X)

end finalize

when I do

X := X * 7;

emit O4(X)

end abort

end var

Si occurrence de J

finalize: X := 2, O1(2)

handler: X := 6, O2(6)

Terminaison du corps:finalize: X := 11, O3(11)



finalizevar X := 0 : integer in

abort

finalize

abort

finalize

halt

with

X := 2;

emit O1(X)

end finalize

when J do

X := X*3;

emit O2(X)

end abort

with

X := X + 5;

emit O3(X)

end finalize

when I do

X := X * 7;

emit O4(X)

end abort

end var

Si occurrence de I



handler:X := 49, O4(49)

Le compagnon Graphique d’Esterel

Les SyncCharts



Motivation

• Esterel est un langage textuel• Difficulté à exprimer certains comportements

– Contrôle hiérarchique– Modèle à état

• SyncCharts Puissance d’expression des FSM+ hiérarchie+ préemption + suspension

Les Synccharts

Acronyme, pour Synchronous Charts.Fortement inspirés des Statecharts de D.Harel,plus grande richesse

– préemptions la suspension et l’avortement

– sémantique plus stricte basée sur celle d’Esterel.

• Même notion qu’en Esterel– de séquence,– de concurrence,– la préemption

– la communication

ceci de manière parfaitement déterministe.



Problème non déterministe

A B

DC

f/g/h

a/bc

a/

e/

Si on est en B et que a et e sont présents quel est l’état suivant ?

Eléments graphiques des SyncCharts (Safe State Machine)

Priorité sur les arcs

Parallélisme



Eléments graphiques des syncCharts

• Les SyncCharts adoptent une description état/transition.– ont à la fois les caractéristiques des machines de Moore et de

Mealy.– Les étoiles peuvent être des états simples (cercles) ou des macro-

états (rectangles à bords arrondis).– Un état initial, est matérialisé par un arc venant d'un connecteur

(rond noir) et pointant sur un état.– Un état final est représenté par une enveloppe (cercle ou

rectangle) en trait double.

• La transition d’un état à un autre est déclenchée par unévénement s, et cette transition peut s'accompagner del'émission d’un signal e. L’étiquette est alors notée s/e.

Composition parallèle

• Caractéristique des graphes d'états sont bien connus pour leur caractère explosif en présence d'évolutions simultanées.

• Les SyncCharts ont la possibilité de représenter des graphes d'états en parallèle.

– Les lignes pointillées séparent les différentes composantes parallèles.

– Les graphes en parallèle ne sont pas totalement indépendants car leurs évolutions peuvent se synchroniser




A1 …A1 …A1 …A1 … AnAnAnAn

• N automates mis en parallèle• Sémantique est le produit des

automates– Sorte d’entrée est l’union des sortes

d’entrée– Sorte de sortie est l’union des sortes de

sortie


• Produit d’automates

A1,3ab

a/b

a/bA2,4

A1,4



Communication

• Support de communication : le signal • Les composantes perçoivent

simultanément les mêmes informations. • Une émission faite dans une

composante parallèle peut très bien déclencher dans le même instant une évolution dans une autre composante.

Signaux locaux

• La localité est le macro-état

Signaux locaux

A1,3,5

a/

A2,4,6



Hiérarchie

• État Z jamais atteint

• Préemption forte de b

A

Hiérarchie

AA,X

abc/

ac/b

bc/e

B A,Yb/

c/bc/e

Préemption Faible



Hiérarchie

AA,X

abc/

ac/b

bc/

B A,Yb/

c/bc/e

Préemption Forte

Suspension• La préemption est l’interdiction faite à un agent de s’exécuter

• définitivement (avortement) ou• temporairement (suspension).

• La suspension est forcée tant que le signal de suspension estprésent.

le macro-état macro est suspendu chaque fois que le signal i est présent. Aucune évolution interne dans un macroon obtient un véritable ``figeage'' des évolutions



Watchdog simple

Watchdog avec suspension de comptage



Watchdog avec compteur binaire

Exercice à faire en TD

Comparaison SyncCharts/Statecharts

• Transition inter état

• Équivalent à



Comparaison SyncCharts/Statecharts

• Transition inter état

• Équivalent à

Watchdog avec compteur binaire



Du modèle vers l’implantation

Etape 1 : Simulateur



Mise en oeuvre

• Traitement des données autres que prédéfinies (boolean, integer, float, string) : à fournir

• Déclarations dans foo.htypesconstants

functions …• Définitions dans foo_data.c

Mise en oeuvre

• Constantes• En Estérel :

constant n:integer, Duration:TIME;

var v:integer :=15 in

…

end var

• En C :– /* in foo.h */

#define n 12

– /* in foo_data.c */

int V = 15;

TIME Duration = {5,30};



Mise en oeuvre• Fonctions• En Esterel :

function TIME_ADD(TIME,TIME):TIME;

• En C :TIME TIME_ADD(TIME a, TIME b) {

TIME t = a;if ((t.s += b.s) > 59) {

t.s -=60;t.mn++;

}if ((t.mn += b.mn)>59) t.mn-=60;return t;

}

Mise en oeuvre

• Exemple de type défini par l’utilisateur• En estérel: type TIME;

• En C (dans foo.h) :typedef struct {

int mn;

int s;

} TIME;



Mise en oeuvre

• Fonctions d’accès• Affectation - à fournir

_<type>(<type>*,<type>);

#define _<type>(x,y) (*(x)=y)

• Test égalité – à fournir*_eq_<type>(<type>,<type>);

• Test inégalité – à fournir*_ne_<type>(<type>,<type>);

Mise en oeuvre

• Exemple pour TIME• int _eq_TIME(TIME a, TIME b)

{

return ( (a.mn == b.mn)

&& (a.s ==b.s));

}

• int _ne_TIME(TIME a, TIME b)

{ return !_eq_TIME(a,b); }



Mise en oeuvre• Conversions <type> ↔ string• <type> → string :

char * _<type>_to_text(<type>)

• string → <type> :void _text_to_<type>(<type>*,char*);

• Test syntaxique :int _check_<type>(char *);

Mise en oeuvre• int _check_TIME (char *s) {

int m,s;

return ((sscanf(s,”%d:%d”,&m,&s)

==2?1,0)); }

• void _text_to_TIME (TIME*pt,char *s) {

if (_check_TIME(s))

sscanf(s,”%d:%d”,&(pt->mn),

&(pt->s));

else {

fprintf(stderr,”%s:illegal TIME\n”,s);

pt->mn = pt->s = 0;

}

}

• char * _TIME_to_text (TIME t) {

static char Buffer[9]=“”;

sprintf(Buffer,”%02d:%02d”,t.mn,t.s);

return Buffer; }



Mise en oeuvre

• Procédure• En Estérel :

procedure Incr_TIME(TIME)(integer);

• En C :void Incr_TIME(TIME *pt, int n) {

int s = pt -> s;int mn = pt -> mn;s += n;pt -> s = (s%60);mn += (s/60);pt -> mn = (mn%60);

}

Chaîne de compilation

foo.strl

foo.ic

foo.lc

foo.sc

foo.ssc

strlic

iclc

lcsc

scssc

foo.oc

sscoc

lcoc sscbliffoo.blif

ocdebug sscdebug

sscdebug_out.debug

ocdebug_out.debug

-Llang

foo.lang



Chaîne de compilation v5-21

strlic

.strl .strl .strl

strlic strlic

.ic .ic .ic

iclc

.lc

lcsc

.sc

scssc

.ssc

sccausal

sscoc

.oc

Sources

Esterel

Code lié

Circuit

Circuit trié

Automateexplicite

Analyse lexicale,

syntaxiqueet sémantique

Editionde liens

Générateur

d’équations

Trieur de circuits

acycliques

Décycliseur

de circuits

Générateur

d’automates explicites

Code

intermédiaire

.blif

Circuit

BLIF

xeveVérification

formelle

sscblif

blifopt

blifssc

Optimiseur

Chaîne de compilation v5_9x

strlic

.strl .strl .strl

strlic strlic

.ic .ic .ic

iclc

.lc

lcsc

.sc

scssc

.ssc

sccausal

Sources

Esterel

Code lié

Circuit

Circuit triéAutomate

explicite

Analyse lexicale,

syntaxiqueet sémantique

Editionde liens

Générateur

d’équations

Trieur de

circuits cycliques

Décycliseurde circuitsGénérateur

d’automates explicites

Code

intermédiaire

.blif

Circuit

BLIF

xeveVérification

formelle

sscblif

blifopt

blifssc

Optimiseur

scoc

.oc

evcl

Vérification

formelle

scsimplify

Simplifieur de

contrôle



xesterel

xesterel : options



Format oc

2

4 5

R1

2

AB/O

34

AB AB

5

3

2.2 Present signal tests

A4 : V0 (signal A)

A5 : V1 (signal B)

A6 : V2 (signal R)

2.3 Output actions

A7 : 0

State 2

if A6 then

goto state 2

end;

if A4 then

if A5 then

A7

goto state 3

end;

goto state 4

end;

if A5 then

goto state 5

end;

goto state 2

Du modèle vers l’implantation

Etape 2 : Machine d’exécution



Machine d’execution

• C’est le problème d’implantation des modèles.

• Maintient d’une cohérence entre le modèle et l’implantation

• Valable pour tout modèle– Modèle de tâche– Modèle synchrone– Modèle par composants

Machine d’exécution pour Esterel

• Quelles hypothèses ?– Diffusion instantanée des signaux– Déterminisme– Signaux multiformes – Hypothèse de « temps nul »– Contraintes sur les signaux – Tâches esterel





Compilateur Esterel



Compilateur Esterel

XecMachine



Machine d’exécution en esterel

• Cela se traduit par : – Gestion des évènements d’entrée– Temps d’exécution de l’automate

compatible avec les contraintes des signaux d’entrées.

– Atomicité des réactions de l’automate– Prise en compte des contraintes sur les

signaux lors de la constitution de l’événement d’entrée

– Gestion des tâches en reportant leur état

Interface C Extrait de la doc esterel studio

• Signaux d’entréeFor each input signal IS, the Esterel Studio code generator

generates an input C function called MODEL_I_IS, which takes an argument of the appropriate type if the signal IS conveys a value.

For example, from the Esterel Studio declarations: input WATCH_MODE_COMMAND; input WATCH_TIME (WATCH_TIME_TYPE); return R;

void DISPLAY_I_WATCH_MODE_COMMAND ( ) { ... } void DISPLAY_I_WATCH_TIME (__V) WATCH_TIME_TYPE __V; { ... }void DISPLAY_I_R ( ) { ... }

• Quand un automate doit réagir à un événement d’entrée composé de un ou plusieurs signaux, les fonctions C doivent être appelées toutes avant le programme principal DISPLAY();




• Signaux de sortieFor each output signal OS, the user must write a void output C

function MODEL_O_OS that takes an argument of the appropriate type if the signal OS conveys a value. This function is automatically called by the reaction function if the signal is emitted.

Output OS1, OS2 : integer;

MODEL_O_OS1 ( ) { /*à définir*/ }

MODEL_O_OS2 (int i) { /*à définir*/ }

• Signaux d ‘entrée/sortieFor an input/output signal IOS, an input C function

MODEL_I_IOS is automatically generated as for an input signal, and you must write an output C function MODEL_O_IOS as for an output signal.


• CapteursA program reaction can access the current values of

sensors. Let SE be a sensor of type T. If the program needs the current value of SE to perform its reaction, it calls an argumentless user-supplied sensor C function MODEL_S_SE.

This function must return a value of type T, which is the sensor current value. To ensure sensor value consistency, the program calls each sensor C function at most once in a reaction. Here is an example: int MODEL_S_TEMPERATURE ( ) { ... }




• Reaction et resetFor the main module MODEL, the Esterel Studio code

generator generates a void function MODEL and a void reset function MODEL_reset that resets the program byperforming the following actions: – resetting the program to its initial state– resetting the valued interface signals for which an initial

value was provided in Esterel source code

The reset function should be called before any reaction is performed if there are initialized interface signals in MODEL.

Machine d’exécution



Machine d’exécution

• Une réaction se déroule en 3 phases : – Activation de l’Input Module : échantillonnage des

signaux d’entrée et construction de l’événement I1– Activation du processus synchrone et génération

de l’événement O1– Activation de l’output module et émission des

événement vers l’environnement– Une réaction de ces trois phases peut être

déclenchée par le signal BoI et se termine par l’émission d’un signal EoI

La vérification formelle



Pourquoi vérifier formellement ?

• Une phase de tests n'est pas suffisante – En effet, tous les « softwares » sont testés. – Une phase de correction fait d'ailleurs souvent

suite à ces premiers tests. – lorsque le programme passe avec succès tous

les tests, il est dit « correct ». – Malgré cela de nombreux incidents ou

accidents ont prouvé que cette notion de correction n'est pas suffisante

Tests non exaustifs

Exemple de logiciels testés

• le problème du Therac-25 (un appareil d'irradiation thérapeutique) : 2 morts, 4 irradiés ;

• le bug du pentium, en 1994. Coût : 500 millions de dollars ;

• l'explosion du premier vol d'Ariane 5, le 4 juin 1996. Coût : 500 millions de dollars de pertes ;



La vérification formelle

• il faut d’abord spécifier deux objets assez vagues : le processus que l'on veux vérifier, et les propriétés qu'il doit satisfaire.

• formalisation du programme : cela se fait généralement à l'aide d'automates (finis), c'est à dire de systèmes de transitions entre des états étiquetés par certaines propriétés.

La vérification

• Techniques de vérification basées sur des formalismes mathématiques afin de décrire précisément :– la chose que l'on contrôle (ce sera, disons,

un processus, un protocole, un programme),

– et ce que signifie cette vague notion d'« exactitude ».



Validation vs.Vérification

• Le processus de validation met en œuvre des techniques de simulation et de tests.

• La vérification (souvent qualifiée de formelle, pour bien marquer la différence avec le test) est l'action de contrôler (formellement, donc) l'exactitude d’un programme. Elle permet de révéler des propriétés d’un système. Elle fait appel au model-checking.

Techniques de vérification

• Les assertions : une propriété qui doit être toujours vérifiée dans le programme

• Les observateurs : une mise en parallèle avec le contrôleur des propriétés attendus ou non attendues.



Assertion

module Simple: input I : integer; output O1, O2;sustain {

O1 if :(?I > 0); % Test1 O2 if :(?I < 0); % Test2

assert EXCLUSION = not (O1 and O2)

end module

Résultat de la vérification

esterelv7 -simul –expand –Ldatapath –B Simple Simple.strl > esverify –v –assert –equations expanded Simple.eid

--- esverify: Reading model from file "Simple.eid".

--- esverify: Checking if assert signal "Simple/EXCLUSION" is always 1

--- esverify: Start model-checking properties

--- esverify: Verification complete for assertion Simple/EXCLUSION: True

--- esverify: ------------------------------

--- esverify: Model-Checking results summary

--- esverify: ------------------------------

--- esverify: Status of assertion "Simple/EXCLUSION": True.



Observateur

• Un observateur est généralement exprimé dans le même formalisme que le système à observer.

• Un observateur permet d’exprimer soit – Une propriété positive : l’observateur doit alors

correspondre à une trace possible dans le contrôleur – Une propriété négative : « bad news will never occur »

cad il n’existe pas de trace qui correspondant à cet observateur.

Vérification de propriété

• Principe : mettre en parallèle un observateur de la propriété.

• En pratique : il est plus simple d’exprimer la contraposée de la propriété P et de vérifier que ¬P n’est jamais satisfaite. Sinon il donne un scénario de contre-exemple.



Propriété 1• O n’est jamais émis sans être précédé de ou

simultané à une occurrence de B depuis la dernière occurrence de R ou depuis l’instant initial si R ne s’est pas encore réalisé.

• module obs1:

input O,R,B;

output OsansB;

loop

abort

await O; emit OsansB

when B

each R

end module

XEVE



SyncChart of the MotorDriver Capsule

enableOut

# not enableIn

1

enableIn

# ack

cmdOutM

logicalStateM

enableIn

# cmdInM

cmdInZ / cmdOutZ

2

# cmdInP

3

cmdOutP

not enableIn/ cmdOutZ

enableIn

# ack

cmdInZ / cmdOutZlogicalStateP

not enableIn/ cmdOutZ

MotorDriver

logicalStateZ# logicalStateM or logicalStateP

Diagramme de structure

:Drivers

La:

MotorDriver

rh:MotorDriver

sd:MotorDriver

b:MotorDriver

fh :MotorDriver

hr:MotorDriver




:Encoder

:Drivers

La:

MotorDriver

rh:MotorDriver

sd:MotorDriver

b:MotorDriver

fh :MotorDriver

hr:MotorDriver


:Encoder

:Drivers

La:

MotorDriver

rh:MotorDriver

sd:MotorDriver

b:MotorDriver

fh :MotorDriver

hr:MotorDriver

1 2 3

4 5 6




:Enable :Enable

:EncoderacceptCommand(byte)

:AcceptCmd

:Ack

:Ack

enGr1 :Enable

enGr2 :Enable

laCmd :Cmd

rhCmd :Cmd

sdCmd:Cmd

bCmd :Cmd

fhCmd :Cmd

hrCmd :Cmd

:Drivers

La:

MotorDriver

rh:MotorDriver

sd:MotorDriver

b:MotorDriver

fh :MotorDriver

hr:MotorDriver

:Enable :Enable

:Cmd

:Cmd

:Cmd

:Cmd

:Cmd

:Cmd

1 2 3

4 5 6

1

2

3

4

5

6

hrLogicalState::MotorState

fhLogicalState::MotorState

bLogicalState:

:MotorState

laLogicalState::MotorState

:MotorState

:MotorState

rhLogicalState:

sdLogicalState:

Observateur d’un scénario

Cal

Tick

250..250ms

Xon

Xoff

Observed = {Cal, Tick, LAon, LAoff, …} Timebase = {ms}

The seat is calibrated in that all adjustment

axes are moved to their stops.

A stop is identified when no more ticks

are supplied by the Hall sensor although

the motor is supplied with voltage

Once the stop is reached, the motors remain

activated for 250 ms so that the control unit

can identify the end position”



Mbp

M1bp

M1done

0..2Sec

(a) (b)

Mbp

M1bp

M1done

0..2Sec

LAFbp RHUbp

Observateur d’un scénario

Observed = {Mbp,M1bp,M1done,LAFbp ….}. Timebase = {Sec}

Propriété de safety

(a)

Mbp

M1done

LAFbp

Mbp

M1bp

M1done

(b)

Observed = {Mbp,M1bp,M1done}

“Whenever M1done is emitted,

M1bp has occurred since the last

occurrence of Mbp”

“Longitudinal Adjustment

Forward”,

occurs between the activation of the

memory function and the selection

of memory 1.

Observed = {Mbp,M1bp,M1done,LAFbp}.




:Enable

acceptCommand(byte)

:AcceptCmd

:Ack

enGr1 :Enable

M1Cmd :Cmd

M2Cmd :Cmd

:Drivers

La:

MotorDriver

rh:MotorDriver

1 2

1

2

M1LogicalState::MotorState

:MotorState

M2LogicalState:

M1Encoder

M2

Documents

Systèmes Réactifs et Programmation Synchrone