Resource Allocation Graphs: differenze tra le versioni

Versione delle 17:01, 5 feb 2019

Versione attuale delle 11:27, 26 mag 2024

(4 versioni intermedie di 4 utenti non mostrate)

Riga 1:

{{O|informatica|gennaio 2017}}

{{F|informaticasistema operativo|ottobre 2015}}

{{W|informatica|ottobre 2015}}

[[File:Resource-allocation-graph.svg|thumb|Esempio di RAG. V = {(P1, P2, P3), (R1, R2, R3)}

{{F|informatica|ottobre 2015}}

[[File:Resource-allocation-graph.svg|thumb|Esempio di RAG.V = {(P1, P2, P3), (R1, R2, R3)

E = {R1 -> P1, R2 -> P2, R3 -> P2, P3 -> R3} ]]

Riga 9:

Il RAG è un [[grafo]] <math>G(V,E)</math> dove:

* <math>V</math> indica il numero di nodi: [[Cerchio|cerchi]] per indicare i processi e [[Rettangolo|rettangoli]] per indicare le risorse; all'interno dei rettangoli verranno indicate con dei pallini il numero di istanze corrispondenti a tale risorsa.

* <math>E</math> indica il numero di archi: dal processo (cerchio) alla risorsa (rettangolo) significa che il processo richiede tale risorsa; dalla risorsa al processo indica che tale risorsa è detenuta da quel processo. Gli archi possono essere orientati e vengono indicati con una freccia.

Se il RAG non contiene cicli, non sono presenti [[deadlock]]. Se presenta cicli, possiamo distinguere due casi:

# '''La risorsa ha una sola istanza''', pertanto si avrà una situazione di deadlock.

Riga 17:

Per la seconda alternativa, ovvero l'algoritmo con RAG, si aggiunge una nuova tipologia di arco nel RAG: un arco tratteggiato dal processo alla risorsa, che significa che tale processo potrebbe richiedere tale risorsa. L'algoritmo con RAG quindi può distinguere situazioni dette ''safe'', se non sono presenti cicli, e situazioni dette ''unsafe'', se sono presenti cicli nel RAG. Non sempre uno stato ''unsafe'' significa presenza di deadlock, ma il deadlock si può verificare solo in uno stato di ''unsafe''.<br />

Tale algoritmo presenta una complessità <math>O(n^2)</math>, dove <math>n</math> indica il numero di processi.

== Bibliografia ==

* Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, "Sistemi operativi. Concetti ed esempi", Pearson, 2014.

{{Portale|informatica}}

* Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, Sistemi operativi. Concetti ed esempi, Pearson, 2014.

[[Categoria:Sistemi operativi]]