Tehnologii și arhitectură a STI
Tema A07.01 Noțiuni de bază privind proiectarea comutatoarelor
Rețeaua Petri Petri Networks este unul dintre instrumentele cele mai expresive pentru procesele de modelare, inclusiv cele paralele, sincrone și asincrone. Acestea reflectă secvența logică a evenimentelor, vă permit să urmăriți fluxurile de date, să elaborați interacțiunea proceselor. Rețeaua Petri este dată de un grafic ale cărui noduri sunt împărțite în două subseturi. Figura *** arată un exemplu de astfel de reprezentare a rețelei.
Unul dintre aceste subseturi de noduri reprezintă poziția (indicată prin cercuri și simboluri sunt marcate Pi), celelalte noduri tranzițiile (indicate prin liniuțe și mărci de simboluri ti). Vârfurile sunt conectate prin arce direcționate, care nu sunt marcate.
Intrările și ieșirile ca atare într-o rețea Petri nu pot fi indicate. Pozițiile sale sunt marcate (marcate în interiorul punctului umbrite) și acest lucru este considerat drept marcajul inițial. Aceasta se numește și plasarea după poziția de jetoane. Numărul de chips-uri dintr-o poziție poate varia de la 0 la infinit. Infinitul este denumit de obicei .
Rețeaua Petri este executată prin tranziții care sunt controlate de jetoane.
În orice moment, numai una dintre tranziții poate fi pornită dacă este activată (activă). În principiu, mai multe tranziții pot fi active. Dar se poate începe.
O tranziție se numește rezolvată dacă fiecare dintre pozițiile sale de intrare conține numărul de jetoane care nu sunt mai mici decât numărul de arce care conduc de la această poziție la tranziție.
Pentru a înțelege principiul funcționării netă a Petri, ia în considerare un exemplu mai semnificativ, prezentat în Fig.
Aici sunt marcate pozițiile P1 și P3. care este desemnat ca marcaj (1010). Asta este, dacă există un cip în poziție, este marcat ca (1), altfel ca (0). Marcarea toate nodurile reprezentate ca un vector (1 2 ..., n ..) În cazul în care termenul I poziție i-lea, și n - numărul de posturi în rețea. Tranzițiile acestei rețele sunt prezentate sub forma următoarelor deorva.
Deoarece nodurile copacului sunt acele marcări, care se realizează în timpul executării rețelei Petri.
Marcajul inițial este partea superioară a copacului. Numai tranziția t3 este activă. Triggerul t3 este pornit de faptul că la început cipul este luat din el și apoi plasat în poziția p4. Acest lucru este indicat de noul marcaj (1001).
Apoi, tranziția devine activă t2. Dar în acest caz, lansarea acestei tranziții este însoțită de eliminarea unui cip din poziția p4. dar este plasat două - unul în poziția p2. iar celălalt în poziția p3.
După aceasta, două tranziții t1 și t3 devin active. În această situație, unul dintre ele poate fi început.
Dacă mergem de-a lungul ramurii t3. apoi repetați pașii deja întreprinși. Aceasta înseamnă că netul Petri intră în ciclu. În același timp, în poziția p2 se vor acumula chips-uri. Mai mult, o astfel de acumulare nu este limitată de nimic, care este marcat ca .
Dacă mergem de-a lungul ramurii t1. atunci suntem într-un gol. De fapt, poziția p3 este resetată. Și, prin urmare, tranziția devine t1 interzisă
Acest lucru face ca proprietățile de modelare ale rețelei Petri să fie mai bogate.
net corectă Petri se numește un automat, în cazul în care toate tranzițiile sale nu sunt mai mult de o intrare și un arc de ieșire peste, iar în marcarea inițială sa nu este mai mult de o etichetă.
Sarcină pentru munca independentă. Construiți și explorați rețeaua Petri.
2.3.2 Modelarea sistemelor bazate pe plasele Petri.
Reprezentarea sistemului de către rețeaua Petri se bazează pe două concepte fundamentale: evenimente și condiții. Apariția evenimentelor este controlată de starea sistemului, care poate fi descrisă printr-o varietate de condiții. O condiție poate lua fie valoarea "adevărată", fie valoarea "falsă".
Apariția unui eveniment în sistem este posibilă dacă sunt îndeplinite anumite condiții - condiții prealabile ale evenimentului. Apariția unui eveniment poate duce la îndeplinirea altor condiții - postcondițiile unui eveniment. De exemplu, luați în considerare următoarea problemă de simulare.
Un exemplu. Simularea procesării secvențiale a cererilor de către serverul de baze de date. Serverul este în stare de așteptare până când utilizatorul primește o solicitare, pe care o procesează și trimite rezultatul unei astfel de procesări către utilizator.
Pentru descrierea de mai sus, este posibil să se elaboreze o specificare corespunzătoare a evenimentelor și condițiilor. și un tabel al pre- și postcondițiilor lor.
Condițiile pentru sistemul în cauză sunt:
b. cererea a sosit și așteaptă;
în. serverul procesează cererea;
d. cererea este procesată.
Evenimentele pentru acest sistem sunt:
1. Solicitarea a sosit.
2. Serverul începe să proceseze cererea.
3. Serverul termină procesarea cererii.
4. Rezultatul procesării este trimis.
În această rețea Petri, condițiile sunt modelate prin poziții, evenimente prin tranziții. În acest caz, intrările de tranziție sunt precondițiile evenimentului corespunzător; ieșiri - postcondiții. Apariția unui eveniment este simulată prin rularea tranziției corespunzătoare. Îndeplinirea condiției este reprezentată de un cip în poziția corespunzătoare acestei condiții. Începerea tranziției elimină chipsurile care reprezintă executarea precondițiilor și formează chips-uri noi care reprezintă executarea postcondițiilor.
Un exemplu. Simultanitate și conflict. Luați în considerare rețeaua Petri.
Două tranziții ale acestei rețele sunt în conflict, adică lansarea unuia elimină cipul din poziția comună de intrare și astfel interzice lansarea celuilalt. Astfel, sunt modelate evenimentele exclusiv reciproc.
Un exemplu. Implementarea algoritmului de calcul Y! Și produsul tuturor numerelor parțiale pe intervalul [1, Y] pentru un număr întreg arbitrar Y.
Programul este în limbajul abstract.
2.4. Modelarea interacțiunii proceselor prin rețele Petri.
Există diferite tipuri de interacțiune (sincronizare) a proceselor, inclusiv: interacțiunea prin memoria partajată (partajată); prin transmiterea diferitelor tipuri de mesaje.
Simularea lor este realizată de bine-cunoscutele construcții graf-analitice bazate pe plasele Petri.
Apoi, vom arăta modul în care rețelele Petri pot simula diferite mecanisme de sincronizare a proceselor bazate pe rezolvarea problemelor care au devenit clasice în acest domeniu al aplicației lor.
Problema excluziunii reciproce. Fie ca două procese să partajeze o variabilă comună, o înregistrare, un fișier sau alt element de date.
Pentru a actualiza elementul de date partajat, procesul trebuie să citească mai întâi valoarea veche, apoi să calculeze noua valoare și, în final, să o scrie în aceeași locație. Dacă două procese P1 și P2 în același timp încearcă să efectueze o astfel de secvență de acțiuni, poate să apară denaturarea datelor.
Pentru a exclude astfel de probleme, se folosește o metodă de excludere reciprocă bazată pe conceptul unei secțiuni critice. O secțiune critică este o parte a codului de proces pe care accesează obiectul de date partajat. Înainte de a executa secțiunea critică, procesul așteaptă până când un alt proces finalizează executarea unei secțiuni critice (dacă are loc o astfel de execuție). Apoi intră în secțiunea critică și blochează accesul pentru orice alt proces în secțiunea critică. După finalizarea procesului, secțiunea critică este eliberată pentru alte procese în obiectul de date partajat.
Următoarea rețea Petri simulează un mecanism de excludere reciprocă pentru cele două procese P1 și P2.
Problema producătorului / consumatorului. În această sarcină există și un obiect comun - un buffer, prin care interacțiunea este realizată prin transferul asincron al mesajelor. Procesul producătorului creează mesaje care sunt plasate în tampon. Consumatorul așteaptă până când mesajul este plasat în tampon, îl extrage de acolo și o folosește. O astfel de interacțiune poate fi simulată de următoarea rețea Petri.
Poziția B reprezintă memoria tampon, fiecare cip corespunde mesajului generat, dar care nu a fost încă utilizat.
Sarcina de a savura înțelepciunea. Sarcina meselor a fost propusă de Dijkstroi și este legată de cinci înțelepți care au gândit și au mâncat alternativ.
Înțelepții stau la o masă rotundă, pe care sunt multe feluri de mâncare din bucătăria chineză. Între vecini este un bețișor unic. Pentru a mânca mâncare din China, aveți nevoie de două bastoane. Prin urmare, fiecare înțelept trebuie să ia mai întâi o baghetă la stânga și o baghetă la dreapta și apoi să meargă. Există o situație în care fiecare înțelept își ia o baghetă spre stânga și așteaptă apoi ca bagheta să fie eliberată din partea dreaptă. Asadar, ei vor astepta pana cand vor muri de foame. Astfel, această stare pentru sistemul "înțelepților din cină" este un sfârșit mort.
problema impas în acest sistem poate fi rezolvată prin următoarea modificare a normelor sale de conduită: Să sage în tranziția de la o stare la o stare de meditație nu implică manca la un moment dat, și în același timp, cele două bețe (stânga și dreapta), în cazul în care acestea sunt gratuite. Această situație este modelată de următoarea rețea Petri.
În această rețea Petri poziționează ni. i reprezintă condiția "bagheta i este liberă". În marcarea inițială, fiecare dintre aceste poziții are un cip. Fiecare înțelept i∈ corespunde cu două poziții: poziția di - reprezentând condiția "i-th sage gândește"; și poziția ei - reprezentând condiția "i-th sage mănâncă". În marcarea inițială, fiecare poziție qi conține un cip, iar fiecare poziție ei este goală.
Fiecare salvie corespunde, de asemenea, celor două tranziții: tranziția nachi - reprezentând evenimentul "începutul consumului de alimente de către cel de-al treilea înțelept"; și tranziția zavi - reprezentând evenimentul "finalizarea aportului de alimente de către înțeleptul i-lea".
Pentru a continua descărcarea, trebuie să colectați imaginea: