Graficul așteptărilor

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

În informatică , graficul așteptărilor (numit și graficul Holt ) este un grafic orientat direct. Introdus din 1972, este folosit pentru a reprezenta stările de alocare între resurse și procese. [1]

Descriere

Graficul așteptărilor este alcătuit dintr-o pereche (V, E), unde V este setul de noduri și E setul de margini.

Setul V este partiționat în două părți, P: {P1, P2…, Pn}, care reprezintă toate procesele aparținând sistemului și R: {R1, R2, ... Rn}, care reprezintă resursele.

Noduri aparținând graficului de așteptare

Arcurile din grafic pot fi de două tipuri:

  • Un arc direct care merge de la un nod de tip resursă la un nod de tip proces, denumit arc de cerere , reprezintă cererea și ulterior atribuirea resursei. Rj → Pi
  • Un arc de la un proces la o resursă, numit arc de atribuire , indică faptul că resursa este temporar deja alocată unui alt proces. Acest tip de stare poate fi evitat dacă procesele individuale sunt executate secvențial, adică permițând executarea cererii în ordinea sosirii. Pi → Rj

În cadrul graficului, resursele și procesele sunt reprezentate de două tipuri de noduri:

  • Resursele sunt reprezentate printr-o formă dreptunghiulară.
  • Procesele sunt reprezentate printr-o formă circulară.

Fiecare resursă din grafic poate avea mai multe unități utilizabile, numite instanță. Se face astfel o partiție a resursei în sine, indicând multiplicitatea cu puncte din reprezentarea grafică a nodului resursei. Fiecare instanță poate fi asociată cu un singur proces la un moment dat. [2]

Tipuri de resurse

În cadrul graficului, pot fi găsite două tipuri diferite de resurse:

Resurse reutilizabile , care se caracterizează prin următoarele caracteristici:

  • O anumită unitate a unei resurse poate fi alocată, cel mult, unui proces la un moment dat.
  • Unitățile nu pot fi prevenite; odată ce un proces a dobândit o unitate, unitatea nu va fi disponibilă până când nu va fi eliberată de procesul în sine.

Exemple de resurse reutilizabile pot fi dispozitivele fizice, cum ar fi discurile de memorie și casetele.

Al doilea tip este cel al resurselor consumabile :

  • Nu există un număr definit de instanțe disponibile în cadrul acestora.
  • Ori de câte ori este dobândită o unitate a unei resurse, aceasta încetează să mai existe și va fi disponibilă din nou numai după eliberare prin proces.

Principala diferență între resursele reutilizabile și consumabile este că unitățile unei resurse reutilizabile nu sunt niciodată create sau distruse, dar starea lor este modificată, ceea ce poate fi identificat ca „necesar”, „dobândit” sau „eliberat”. În schimb, unitățile fiecărei resurse consumabile sunt create și distruse de fiecare dată când sunt solicitate și eliberate. [3]

Reprezentare grafică

Graficul de așteptare vă permite, de asemenea, să analizați cazurile de blocare , adică atunci când unul sau mai multe procese se află într-o situație de blocare în așteptarea executării unei anumite acțiuni, cum ar fi eliberarea unei resurse. Un caz de impas este reprezentat de prezența unui ciclu care va permite trimiterea unui mesaj, astfel încât să avertizeze procesul în cauză. [3] Deci, să ne imaginăm că trebuie să reprezentăm următoarea situație:

 P: {P1, P2} // set de procese 
R: {R1, R2} // set de resurse
R1 multiplicitate 1
R2 multiplicitate 2

E: {P1 → R1, P1 → R2, P2 → R2, P2 → R1} // reprezentând împreună marginile graficului

P1 solicită R1 // solicită arc
P1 solicită R2 // solicită arc
P2 solicită R2 // solicită arc
P2 necesită R1 // interval de atribuire
Graficul așteptărilor

Procesele afectate vor avea următoarea stare:

  • Procesul P1 dobândește singura instanță a resursei R1 și o instanță a resursei R2
  • Procesul P2 dobândește o instanță a resursei R2; solicită, de asemenea, resursa R1, care nu i se atribuie și este pusă în așteptare.

În acest caz, a doua cerere făcută de procesul P2 nu poate fi satisfăcută, deoarece resursa nu are unități disponibile, astfel încât arcul va fi definit începând de la proces către resursă. [1]

Prin urmare, un arc care intră în nodul resursei va fi reprezentat în interiorul graficului, indicat grafic cu roșu, pentru a evidenția prezența unui arc de atribuire și așteptarea prin procesul P2 a resursei R1.

Stare impas

În cadrul unui sistem blocat, procesele nu își încheie niciodată execuția și, în consecință, resursele sunt blocate. [4] Cazul de blocare este evident în prezența unui ciclu în grafic.

Există mai multe condiții necesare pentru a determina prezența unei stări de blocare:

  • Fiecare proces aparținând buclei este în impas.
  • În cadrul ciclului sunt resurse ale unui anumit set, fiecare constând dintr-o singură instanță.

În schimb, există condiții necesare, dar nu suficiente, cum ar fi resurse cu mai mult de o singură instanță.

Prin urmare, reprezentăm un caz de impas:

 P: {P1, P2, P3}
R: {R1, R2, R3}
R1 multiplicitate 1 
R2 multiplicitate 1 
R3 multiplicitate 2 

E: {P1 → R3, P2 → R1, P3 → R2, P2 → R3, P1 → R1, P2 → R2, P3 → R3}
P1 necesită R3
P2 necesită R1
P3 necesită R2
P2 necesită R3
P1 necesită R1 // interval de atribuire
P2 necesită R2 // interval de atribuire
P3 necesită R3 // interval de atribuire

În acest caz, procesele P1, P2, P3 sunt blocate. Procesul P2 așteaptă resursa R2, deținută de procesul P3. Procesul P3, pe de altă parte, așteaptă ca procesul P1 sau P2 să elibereze resursa solicitată de acesta; în plus, procesul P1 așteaptă ca P2 să elibereze resursa R1. [2]

Caz de impas

Grafic reductibil

Un grafic poate fi definit reductibil în cazul în care există un nod de tip proces care are numai arce de intrare, adică arce de atribuire. Conceptul care stă la baza acestui mecanism este că procesul afectat, care nu are nevoie de alte resurse, cu siguranță își va finaliza procesarea, eliberând resursele pe care le folosește. [1]

Notă

  1. ^ a b c Paolo Camagni, Riccardo Nikolassy, Tehnologii și proiectarea sistemelor informaționale și a telecomunicațiilor , 2016, p. 18.
  2. ^ a b Abraham Silberschatz, Peter Baer Galvin, Sisteme de operare , 1998, p. 199.
  3. ^ a b Richard C. Holt, Unele proprietăți de blocare ale sistemului de calculatoare , în ACM Computing Surveys , vol. 4, nr. 3, septembrie 1972, DOI : 10.1145 / 356603.356607 .
  4. ^ Andrew S. Tanenbaum, Modern Operating Systems , 2002, p. 149.

Bibliografie

  • Andrew S. Tanenbaum, Sisteme de operare moderne , Universitatea Jackson, ISBN 8825618980 .
  • Abraham Silberschatz, Peter Baer Galvin,Sisteme de operare , Addison Wesley, 2002, ISBN 8871920643 .
  • Paolo Camagni, Riccardo Nikolassy, Tehnologii și proiectarea sistemelor informaționale și a telecomunicațiilor , Hoepli, ISBN 9788820378424 .


Elemente conexe

Alte proiecte

Adus de la „ https://it.wikipedia.org/w/index.php?title=Grafo_delle_attese&oldid=122431680 ”