Algorisme del banquer

L' Algorisme del banquer, dins l'entorn de sistemes operatius és una forma d'evitar l'interbloqueig, proposada per primera vegada per Edsger Dijkstra. És un apropament teòric per evitar els interbloquejos en la planificació de recursos. Requereix conèixer amb anticipació els recursos que seran utilitzats per tots els processos. Això últim generalment no es pot satisfer en la pràctica.

Aquest algorisme usualment és explicat usant l'analogia amb el funcionament d'un banc. Els clients representen els processos, que tenen un crèdit límit, i els diners representa els recursos. El banquer és el sistema operatiu.

El banc confia que no haurà de permetre a tots els seus clients la utilització de tot el seu crèdit a la vegada. El banc també assumeix que si un client maximitza el seu crèdit serà capaç d'acabar els seus negocis i tornar els diners a l'entitat, permetent servir altres clients.

L'algorisme manté el sistema en un estat segur . Un sistema es troba en un estat segur si hi ha un ordre en que poden concedir les peticions de recursos a tots els processos, prevenint l'interbloqueig. L'algorisme del banquer funciona trobant estats d'aquest tipus.

Els processos demanen recursos, i són complaguts sempre que el sistema es mantingui en un estat segur després de la concessió. En cas contrari, el procés és suspès fins que un altre procés alliberi recursos suficients.

En termes més formals, un sistema es troba en un estat segur si hi ha una seqüència segura. Una seqüència segura és una successió de processos, $<p_{1}$ ,..., $P_{n}>$ , on per un procés $P_{i}$ , la comanda de recursos pot ser satisfet amb els recursos disponibles sumats els recursos que estan sent utilitzats per $P_{j}$ , on j <i. Si no hi ha prou recursos per al procés $P_{i}$ , ha d'esperar fins que algun procés $P_{j}$ acabi la seva execució i alliberi els seus recursos. Tot just llavors podrà $P_{i}$ prendre els recursos necessaris, utilitzar-los i acabar la seva execució. En succeir això, el procés $P$ _i+1 pot prendre els recursos que necessiti, i així successivament. Si una seqüència d'aquest tipus no existeix, el sistema es diu que està en un estat insegur , encara que això no implica que estigui bloquejat.

Així, l'ús d'aquest tipus d'algorisme permet impedir l'interbloquejos, però suposa una sèrie de restriccions:

S'ha de conèixer la màxima demanda de recursos per anticipat.
Els processos han de ser independents, és a dir que puguin ser executats en qualsevol ordre. Per tant la seva execució no ha d'estar forçada per condicions de sincronització.
Hi ha d'haver un nombre fix de recursos a utilitzar i un nombre fix de processos.
Els processos no poden finalitzar mentre retinguin recursos.

Estructures i complexitat

S'utilitzen quatre vectors: recursos, assignació, demanda i disponible. La informació que guarda cada un és la següent:

Recursos: aquest vector manté la quantitat total de recursos que poden ser utilitzats pels processos. D'aquesta manera, Recursos [i] = k vol dir que hi ha una quantitat total k de recursos $R_{i}$ disponibles.
Assignació: en aquesta matriu consten l'actual assignació de recursos a cada un dels processos. Assignació [i] [j] = k vol dir que el procés nombre i té assignat k unitats del recurs j.
Demanda: aquesta matriu guarda les quantitats màximes de recursos de cada tipus que seran utilitzats per cada procés.
Disponible: en qualsevol moment, el vector Disponible guardarà la quantitat disponible de cada recurs. Disponible [i] = k vol dir que hi ha una quantitat de k recursos i disponibles per ser utilitzats.

El termes de complexitat, l'algoritme del banquer és d'ordre O (n ² × m), on n és el nombre de processos i m la quantitat de recursos.

Algorisme de comprovació d'estat segur

És un algorisme que determina si el sistema està en un estat segur.

Algorisme d'assignació de recursos

Aquest algorisme determina si una comanda de recursos es pot satisfer de manera segura. És executat pel sistema cada vegada que arriba una petició de recursos per part d'un procés.

Enllaços externs

http://www.sci.csueastbay.edu/#billard/cs4560/node11.html Arxivat 2010-05-26 a Wayback Machine. (en anglès)