View
5
Download
1
Category
Preview:
DESCRIPTION
Cours Rdp
Citation preview
Module OMGL - UE ModDynModélisation de la dynamique / Réseaux de Petri
J. Christian Attiogbé
Février 2009, maj 2012
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 1 / 34
Plan
Plan de la suite
1 Définitions
2 Les bases
3 Fonctionnement d’un réseau
4 Graphe de marquage : sémantiqueExercice
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 2 / 34
Plan
Introduction
Carl Adam Petri, 1962Une notation mathématique et graphiqueFondée sur une bonne théoriePlusieurs extensions et outils logiciels pour les analyserModélisation de systèmes asynchrones, concurrents, distribués,non-déterministes,Utilisable à différentes étapes de construction de logiciels :analyse, modélisation, simulation, développement (synthèse)Utilisation dans de nombreux domaines : protocoles, systèmescritiques, systèmes d’exploitation, ...
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 3 / 34
Plan
Introduction
Le réseau de Petri comme un outil de l’ingénieur : modélisation etétude du fonctionnement d’un système (avant sa construction).
Exemple : modélisons le comportement de deux robots (dans uneusine).Les deux robots usinent des pièces en se servant d’outils communs.Plusieurs problèmes : accès concurrent, synchronisation, blocage, ...
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 4 / 34
Plan
Introduction : un exemple de concurrence
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 5 / 34
Plan
Caractéristiques des réseaux de Petri
Spécification et étude des systèmes concurrents (communication,synchronisation)Abstraction sur les comportements, et les étatsMode de synchronisation : synchrone, asynchroneMode de composition : via le partage de transitions, (pas dehiérarchie)Modèles sémantiques : opérationnelle, axiomatique (algébrique)
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 6 / 34
Plan
Concepts fondamentaux
Ensemble de Places : PEnsemble de transitions : TArcs entrant/sortant des transitions et des placesJetons (dans des places)Marquage (des places) : Mi
Fonctionnement du réseau : franchissement des transitions etdonc, changement de l’état global (marquage).
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 7 / 34
Plan
Etude empirique du fonctionnement des R. de Petri
Exemples de baseModélisation d’un système producteur/consommateur avec lesRdPModélisation d’une chaîne d’assemblage avec des robots ...
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 8 / 34
Plan
Exemple : Producteur/Consomateur
Modélisation du comportement d’un producteur :
repos
production
buffer
produire reposer
P = {repos, production, buffer}T = {produire, reposer}
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 9 / 34
Plan
Exemples : fonctionnement
Modélisation de la composition producteur et consommateur :
repos
production
buffer
produire reposer
reposC
consommation
preleverrepsoserC
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 10 / 34
Les bases
Définitions formelles
Un réseau de Petri (R) est un quadruplet (P, T, Pre, Post) où :P est un ensemble fini de places (avec | P | = m, le cardinal deP),T un ensemble fini de transitions, disjoint de P, (avec | T | = n, lecardinal de T)Pre : P × T → IN une application d’incidence avant (unematrice) : les places entrant dans une transitionPost : P × T → IN une application d’incidence arrière (unematrice) : les places sortant d’une transition
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 11 / 34
Les bases
Exemple
Soit P = {1, 2, 3, 4, 5} et T = {a, b, c, d, e}.Soient Pre (places avant les transitions) etPost (places après les transitions) :
Pre a b c d e1 1 0 0 0 02 0 1 0 0 03 0 0 1 0 04 0 0 0 1 05 0 0 0 1 1
Post a b c d e1 0 0 0 1 02 1 0 0 0 03 1 0 0 0 14 0 1 0 0 05 0 0 1 0 0
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 12 / 34
Les bases
Graphe du réseau
1
2
5 4
a
c b
de
3
.
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 13 / 34
Les bases
Marquage des réseaux
Un réseau marqué est le couple N = (R, µ) formé de :un réseau R etune application (fonction totale) µ : P → IN.µ(p) est le marquage de la place p,on dit aussi le nombre de marques contenues dans p.
Jeton : indique le marquage de chaque place.
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 14 / 34
Les bases
Marquage des places
repos
production
buffer
produire reposer
µ(repos) = 1µ(production) = 0µ(buffer) = 0
(µ(repos), µ(production), µ(buffer))
(1, 0, 0)
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 15 / 34
Fonctionnement d’un réseau
Fonctionnement et propriétés des réseaux de Petri
Franchissement des transitions (non-déterminisme, synchronisation)Franchissable ? quel est le marquage résultant ?
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 16 / 34
Fonctionnement d’un réseau
Fonctionnement des réseaux de Petri (règlessémantiques)
Une transition est franchissable (ou tirable) (enabled) lorsqu’il y aaumoins un jeton dans chacune de ses places en entrée.Une transition franchissable est franchie (instantanément) ou nonfranchie.Lorsque plusieurs transitions sont franchissables,une d’entre elles (de façon non-déterministe) est franchie.Lorsqu’une transition est franchie,on enlève un jeton de chacune de ses places en entrée eton ajoute un jeton dans chacune de ses places en sortie :modification du marquage.
Chaque arc a un poids de 1 par défaut.
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 17 / 34
Fonctionnement d’un réseau
Fonctionnement du réseau : graphe et propriétés
On étudie le modèle à partir du graphe de marquage (réseau borné).
Marquage et vivacité : Transition vivace (vivante) = il y a toujoursun chemin qui y passe ;Réseau vivace = tout noeud sans arc sortant contient au moinschaque transitionRéseau sans blocage = à partir d’un noeud il y a toujours un arcsortant.Interblocage : aucune action possible à partir d’un noeudatteignable....
On peut avoir des réseaux non bornés.
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 18 / 34
Fonctionnement d’un réseau
Fonctionnement du réseau : graphe et propriétés
Exemples de réseaux :Les philosophes (exo au tableau)Lecteurs/rédacteurs· · ·
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 19 / 34
Fonctionnement d’un réseau
Graphe associé à un réseau
Le graphe (P, T, Γ, V) associé au réseau R = (P, T, Pre, Post) estdéfini par :∀p ∈ P Γp(p) = {t ∈ T | Pre(p, t) > 0} (transitions atteignables)∀t ∈ T Γt(t) = {p ∈ P | Post(p, t) > 0} (places atteignables)∀ p ∈ P, ∀ t ∈ T, V(p, t) = Pre(p, t) et V(t, p) = Post(p, t).(valuation)
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 20 / 34
Fonctionnement d’un réseau
Exemple
Soit P = {1, 2, 3, 4, 5} et T = {a, b, c, d, e}.Soient Pre et Post :
Pre a b c d e1 1 0 0 0 02 0 1 0 0 03 0 0 1 0 04 0 0 0 1 05 0 0 0 1 1
Post a b c d e1 0 0 0 1 02 1 0 0 0 03 1 0 0 0 14 0 1 0 0 05 0 0 1 0 0
soit M0 = (1 0 0 0 0) le marquage initial.On construit le réseau suivant avec M0 :
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 21 / 34
Fonctionnement d’un réseau
Graphe du réseau
1
2
5 4
a
c b
de
3
.
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 22 / 34
Graphe de marquage : sémantique
Graphe de marquage
On construit le graphe sur l’ensemble des marquages accessibles notéA(R, M) (ou espace d’états) du réseau.Un état est un marquage.Si les places du réseau sont p1, p2, . . ., p|P|,un marquage est de la forme (µ(p1), µ(p2), . . . , µ(p|P|)).
Le graphe des marquages est noté G(R, M).Ses sommets sont les éléments de A(R, M).Ses arcs sont etiquetés par ti tel que ti ∈ T.
Soient Mi des sommets, M1 →t M2 ssi :
M1, M2 ∈ A(R, M),t ∈ T,M2 est accessible par t à partir de M1
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 23 / 34
Graphe de marquage : sémantique
Entrée et sortie d’une transition
On appelle entrées d’une transition t : les places Γ−1(t) etOn appelle sorties d’une transition t : les places de Γ(t).
On appelle entrées d’une place p : les transitions Γ−1(p) etsorties d’une place p : les transitions de Γ(p).
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 24 / 34
Graphe de marquage : sémantique Exercice
Exercice
On donne Γp et Γt telles que : (on utilisera Γt pour les transitions et Γppour les places et Γ abusivement pour les deux cas)
Γp(1) = {a}Γp(2) = {b}Γp(3) = {c}Γp(4) = {d}Γp(5) = {d, e}
Γt(a) = {2, 3}Γt(b) = {4}Γt(c) = {5}Γt(d) = {1}Γt(e) = {3}
Construisez le graphe du réseau associé à cette description.
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 25 / 34
Graphe de marquage : sémantique Exercice
Pondération des arcs, arcs inhibiteurs
Arcs pondérésArcs pondérés par défaut avec 1Les arcs peuvent avoir un poids > 1
Exemple d’utilisation :Lecteurs/rédacteur ; on veut autoriser n lectures ;mais exclusion entre un redacteur et les lecteurs ;rédaction en exclusion avec les lecteurs.
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 26 / 34
Graphe de marquage : sémantique Exercice
Pondération des arcs
Par défaut les arcs ont un poids de 1
repos
production
buffer
produire reposer
1 1 1
1 1
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 27 / 34
Graphe de marquage : sémantique Exercice
Pondération des arcs
Exercice : consommation 3 par 3 de ce qui est produit :
repos
production
buffer
produire reposer
1 1 1
1 1
3
1vider
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 28 / 34
Graphe de marquage : sémantique Exercice
Pondération des arcs
Exercice : Modélisation de la composition des comportements desprocessus lecteurs/rédacteurs.N ressources sont disponibles pour la lecture ou la rédaction ;un seul processus rédacteur à la fois,1 à N processus lecteurs peuvent lire simultanément,On veut assurer l’exclusion entre lecture et rédaction.
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 29 / 34
Graphe de marquage : sémantique Exercice
Arcs inhibiteurs
Arcs inhibiteurs : permettent des franchissements spécifiques.Un RdP à arcs inhibiteur est une variante des RdP, où on un peut avoirune transition spécifique franchissable lorsque le marquage de laplace entrante est 0.
Exercice : patients/médecin (au tableau)
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 30 / 34
Graphe de marquage : sémantique Exercice
Arcs inhibiteurs
Modélisation de la détection de fin d’un traitement...
p1 rscrc
1
n
Traitement
Terminaison
prendre1finir
FinTraiter
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 31 / 34
Graphe de marquage : sémantique Exercice
Les limites des réseaux de Petri
Manque de modularitépas de hiérarchisationpas de composition explicite
Explosion du modèle (pour la modélisation de grands systèmes)Prise en compte de la modélisation des données...
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 32 / 34
Graphe de marquage : sémantique Exercice
Les extensions des réseaux de Petri
Il existe de nombreuses extensions pour les réseaux de Petri
Réseaux de Petri avec des données (langage de donnéesélaboré)HLPN (High-Level Petri Nets, réseaux de Petri avec prédicats, etc)...
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 33 / 34
Graphe de marquage : sémantique Exercice
Références
De nombreuses références existent :Génie logiciel, Réseaux de Petri, Racloz et BuchsLes réseaux de Petri, Un outil de modélisation, AnnieChoquet-Geniet, Dunod...
J. Christian Attiogbé (Février 2009, maj 2012) Module OMGL - UE ModDyn 34 / 34
Recommended