Algoritme de grafos d'assignació de recursos

El algoritme de grafos d'assignació de recursos és un método de detecció de situacions de bloqueig mutu.

Esta tècnica consistix en representar gràficament els recursos assignats als processos i els recursos que els processosnecessiten per a completar la seua eixecució. S'utilisa un enfocament de recorregut de grafo, a on s'exploren els nodos seguint les conexions entre ells. Si s'aplega de nou al nodo d'inici, significa que hi ha una espera circular i per tant un bloqueig.

El propòsit d'esta tècnica consistix ademés de detectar l'interbloqueo, obtindre informació precisa sobre els recursos i processos involucrats en dit bloqueig.

Grafos d'assignació de recursos

Figura 1: Grafos de solicitut i assignació de recurs

Figura 2: Grafo de solicitut de recurs i assignació a diferent procés.

Figura 3: Grafo de espera circular

Es representa un grafo per mig del qual s'aprecia de forma senzilla i molt visual els bloquejos. Es representen els processos per mig de quadrats i els recursos per mig de círculs. Quan un procés solicita un recurs, es dibuixa una flecha que va des del procés cap al recurs. Per un atre costat, quan un recurs està assignat a un procés, es dibuixa una flecha que va des del recurs cap al procés.

En la Figura 1, veig com P1 solicita el recurs R1 i P2 té assignat el recurs R2. En canvi en la Figura 2 veem com P3 solicita el recurs R3 pero és P4 el que té assignat este recurs.

En la Figura 3 existix el interbloqueo. Una espera circular, com veem en la image: quan el recurs que se solicita està assignat a un atre procés i este procés solicita un recurs que ya està assignat al procés citat anteriorment. En este cas, P5 solicita R4 pero R4 esta assignat a P6 i al mateix temps P6 solicita R5 pero R5 està assignat a P5.

Eixa espera circular o cicle pot involucrar més de dos processos i dos recursos, com veem en la Figura 4.

Figura 4: Grafo complet d'assignació de recursos i processos.

Manera d'actuar

Concedir totes les solicituts

La premissa és atendre totes les solicituts sempre que hi haja suficients recursos disponibles, i si es detecta un interbloqueo, implementar accions correctivas.

• No hi ha infrautilización de recursos, tots els disponibles s'aprofiten plenament.
• No es llimiten escenaris a on no existixca la possibilitat d'interbloqueo.

Es concedixen totes les solicituts perque l'objectiu és aplegar al bloqueig i detectar-ho, en el cas de que vullgam evitar-ho o previndre-ho portaríem a terme atres métodos o algoritmes com per eixemple l'algoritme del banquer.

Moment en el que utilisar l'algoritme

Este algoritme de grafos, es pot realisar en diferents moments durant l'assignació de recursos:

Davant cada solicitut que no pot ser satisfeta de manera immediata

• L'identificació més àgil i eficient.
• Permet l'identificació del procés responsable del interbloqueo.
• Pot implicar un cost desproporcionado.

Periòdicament

En l'inconvenient d'elegir el periodo més encertat.

Quan s'observe una disminució en el rendiment

En el moment en el que es detecte una degradació de les prestacions del sistema.