-
Automates temporiss
Amal El Fallah [email protected]
-
Plan
Introduction
Dfinition dun automate temporis
Composition dautomates temporiss
Automates hybrides
Conclusion
-
Le problme rsoudre
S : le systme pour lequel on exige un fonctionnement
correct
En : exigencesde fonctionnementE2 : exigences
de fonctionnementE1 : exigencesde fonctionnement
Environnement physique
comportement discretcomportement continu
Exigences temps rel :=> temps quantitatif de
l'utilisateur=> temps continu
monde rel
monde abstrait formel
formules avec temps continu=modlediscret
du systme
modlecontinu de
l'environnement
-
Besoins
La validation dun systme informatique (ex. un protocole)
respectant des exigences temps rel requiert :
La formalisation de ces exigences
La modlisation de l'environnement du systme en prenant en compte
le temps
Besoin dun mme formalisme pour les exigences et les modles de
systmes ou d'environnements.
-
Lampe trois tats lorsque la lampe est teinte (off), un appui
simple sur "press"
l'allume (light) lorsque la lampe est teinte, un double appui
sur "press" la rend
fortement lumineuse (bright) lorsque la lampe est allume (light)
un appui sur "press" l'teint (off) lorsque la lampe est fortement
lumineuse (bright) un appui sur
"press" l'teint (off)? double appui = deux impulsions en moins
de 10ms
off light brightpress? press?
press?
press?
Il faut un formalisme pour reprsenter les dures des actions
-
Premire solution : temps discretExemple : 1 pas = 1 ms
Mais :modlisation dpendante du pas d'chantillonnagemodlisation
peu prcise : peut rejeter 2 impulsions successives de
"press"spares par 9,1 ms et accepter 2 impulsions successives de
"press" spares par 9,9 ms
Autre solution : la prise en compte d'un temps continu !
off light
bright
press?
tick?
press?
press?press? pres? press? press? press?
press?
t
i
c
k
?
t
i
c
k
?
t
i
c
k
?
t
i
c
k
?
t
i
c
k
?
t
i
c
k
?
t
i
c
k
?
t
i
c
k
?
t
i
c
k
?
press?
-
2me solution
off light brightpress? press?
press?
press?
x:=0x10
Avec xR+ ; x est appele horloge ;- on peut la rinitialiser
(x:=0)- on peut la comparer des constantes (x10)
Introduire une variable relle modlisant l'coulement du temps et
exprime en ms
-
Distributeur automatique de billets
0 1 2
3
45
in-card?n:=0
valide? n:=n+1
code-not-OK n>3
keep-card!
code-OK
give-card?
give-money?
code-not-OK n3
-
Exigences temporelles du DABComment prendre en compte des
exigences temps rel telles que :
lors de chaque essai, le client doit valider son code en moins
de 6 secondes, sinon la carte est conserve
lorsque la transaction russit, le client doit rcuprer sa carte
en moins de 3 secondes, sinon celle-ci est conserve
0 1 2
3
45
in-card?n:=0
valide? n:=n+1
code-not-OK n>3keep-card!
code-OK
give-card?
give-money?
code-not-OK n3
-
Suite du DAB
0 1 2
3
45
in-card?n:=0
valide?n:=n+1
keep-card!code-OK
give-card?
code-not-OK n3
give-money?
code-not-OK n>3
-
Suite du DAB lors de chaque essai, le client doit valider son
code en moins
de 6 secondes, sinon la carte est conserve
0 h1
-
Suite du DAB lorsque la transaction russit, le client doit
rcuprer sa carte en moins
de 3 secondes, sinon celle-ci est conserve
0 h1
-
Suite du DAB le client doit rcuprer ses billets en moins de 5
secondes,
sinon la transaction est annule
0 h1
-
Suite du DAB les billets ne peuvent tre rcuprs par le client
qu'au plus tt 2
secondes aprs avoir rcupr sa carte
0 h1
-
Automate temporis Gnralisation : un automate temporis, c'est
:
des nuds et des transitions entre ces nuds tiquetes par des
actions
l l'a
-
Automate temporis Gnralisation : un automate temporis, c'est
des nuds et des transitions entre ces nuds tiquetes par des
actions des gardes temporelles sur les transitions
l l'ag
Garde : x - y ~ k ou x ~ k avec x et y deux horlogesavec k une
constante entireet ~ {==, , }
-
Automate temporis Gnralisation : un automate temporis, c'est
des nuds et des transitions entre ces nuds tiquetes par des
actions des gardes temporelles sur les transitions des remises zro
d'horloges
l l'ag
Garde : x - y ~ k ou x ~ kavec x et y deux horlogesavec k une
constante entireet ~ {==, , }
RAZ
Remise zro de toutes les horloges de RAZ
-
Automate temporis Gnralisation : un automate temporis, c'est
des nuds et des transitions entre ces nuds tiquetes par des
actions des gardes temporelles sur les transitions des remises zro
d'horloges des invariants dans chaque nud pour forcer le
mouvement
l l'ag
Garde : x - y ~ kavec x et y deux horlogesavec k une constante
entireet ~ {==, , }
RAZ
Remise zro de toutes les horloges de RAZ
Inv(l) Inv(l')
Invariant : formule qui doit tre vraie tant que le nud est
occup
-
Comportement dun automate temporis
Un automate temporis volue soit en laissant passer le temps sans
changer de nud
h
-
Comportement dun A.T. un automate temporis volue
soit en laissant passer le temps sans changer de nud soit en
tirant une transition sans laisser passer le temps
=> le tir d'une transition est instantan=> une transition
ne peut tre tire que si sa garde est vraie=> une transition dont
la garde est vraie peut ne pas tre tire=> on ne peut rester dans
un nud dont l'invariant devient faux
h
-
Syntaxe dun A.T.
un ensemble fini dtats Q un ensemble fini d'horloges X = {x, y,
z ..} un alphabet fini = {a,b, c..} un ensemble de transitions dont
chacune est forme :
dune garde g : une condition c (conjonction) sur les horloges x
dans {>,
-
Smantique dun A.T.
-
Smantique dun A.T.
-
Excution dau A.T. Un excution est un chemin dans le systme de
transitions
temporis o salternent les pas de temps et les transitions
discrtes (q0; (0;0)), (q0; (1,2;1,2)) ,, (q1; (0;1,2)) , (q1;
(0,37;1,57))
,, (q1; (0;1,57))
Une excution gnre un mot temporis: une suite dactions couples
(b;1,2) (a; 1,57)
-
Exemple
x1
x2
x1
a
x:=0x=2
t
1
2
a a a
x
temps (R)
-
temps (R)
2
3
a a
x
obligation de franchissement de la transition
x
-
Exemple
true 2
-
ExempleRemarque : il existe un automate discret quivalent :
true 2
-
ExempleRemarque : il existe un automate discret quivalent :
quivalent
x
-
Exemple : un systme de webmail
-
Une excution
-
Besoin de modularit Composition d A.T.
Vrifier qu'un systme fonctionne correctement ncessite la
modlisation : du systme de son environnement de l'utilisateur
exprimant des exigences de bon fonctionnement (scnarii
attendus ou situations indsirables) Description du systme
(complet) sous la forme d'un
ensemble d'automates temporiss interagissant interaction par
synchronisation des automates sur des actions communes mme temps
(et donc mme taux de progression des horloges) pour tous
les automates Notion de produit synchronis d'automates temporiss
!
-
Composition dautomates
-
Exemple Automates originaux, synchronisation sur c
-
Composition
-
Automates hybrides
Les automates temporiss sont limits : Toutes les horloges ont la
mme vitesse. N'autorise que des comparaisons simples et les remises
zro Modlise le temps, mais n'est pas adaptable la modlisation
dautres
modles continus Les automates hybrides (HA) :
I Les horloges sont remplaces par des variable. Dans chaque tat,
chaque variable varie linairement: x= -1/2 Les comparaisons peuvent
faire intervenir des combinaisons linaires
de variables :x + 2y 3/2 Les mises jour peuvent aussi tre plus
complexes : x := y + 1/3
-
Exemple dun automate hybride Un chauffe-eau est soit allum e
soit teint.
La temprature de l'eau est modlise par la variable t . Elle
croit de 15C par minute lorsque le chauffe-eau est allum (t
= 15), et dcroit de 2C par minute lorsque le chauffe-eau est
teint (t = -2)
Initialement, l'eau est 20C, et elle doit tre maintenue entre 80
et 100C
.
.
-
Comparaison entre les AT et les AH
Les automates hybrides sont plus expressifs On peut les
manipuler en TME avec HyTech.
Par contre il est plus difficile de vrifier des choses sur les
automates hybrides.
La vrification est possible sur les automates temporiss. En
particulier le problme d'accessibilit est dcidable sur les A.T
-
Conclusion
Les automates temporiss permettent dassocier des dures aux
actions
Les rseaux de Petri temporiss permettent dassocier un intervalle
durant lequel une action sera excut
Les intervalles dAllen permettent dassocier des intervalles o
laction peut se produire.
Ces trois formalismes sont trs utiliss en planification
mono-agent et aussi multi-agents car ils permettent la
synchronisation et/ou la concurrence.
-
Exemples supplmentaires
-
Modlisation de la communicationBesoin : modliser une
communication synchrone par envoi/rception de
messagesIde :
tiquette de transition m! = envoi de m tiquette de transition m?
= rception de m synchronisation de m! et m? par une contrainte de
synchronisation
Consquence : ncessit d'une action vide (qui ne fait rien) = pour
permettre la synchronisation de m! et m? uniquement (pas de
synchronisation avec les actions des autres AT du produit
synchronis)
extension de l'alphabet des actions ' = {} extension de la
dfinition des AT par ajout de la transition vide :
qQ, (q, true, , , q) synchronisation de m! et m? uniquement par
une contrainte du type
I=(, , m!, , , , m?, , , )
-
Emission / Rception synchronises
Fproduit a
tous les 20
a a'M
Mdium de latencecomprise entre 5 et 10
Gproduit b entre
0 et 5 aprs chaque rception de a
a!
f
