Algoritmo del banchiere

Da Wikipedia, l'enciclopedia libera.

L'Algoritmo del banchiere è utilizzato per prevenire i Deadlock nell'allocazione delle risorse. In particolare questo algoritmo può indicare se un sistema (in particolare un Sistema operativo) si venga a trovare in uno Stato sicuro o meno nel caso assegnasse una risorsa ad uno dei processi richiedenti.

La Complessità computazionale di questo algoritmo è $O (n 2 m)$ , dove $n$ è il numero di processi e $m$ il numero di tipi di risorse (per ogni tipo possono essere disponibili più risorse - per esempio, due stampanti equivalenti, porte di comunicazione, ecc...)

Indice

1 Concetto alla base dell'algoritmo
2 Funzionamento dell'algoritmo
- 2.1 Procedimento
- 2.2 Risultato
3 Voci correlate

[modifica] Concetto alla base dell'algoritmo

Un sistema, nell'allocare le risorse che vengono richieste, deve procedere come farebbe una Banca. La similitudine vuole che i processi vengano visti come i clienti che possono richiedere del credito presso la banca (fino ad un certo limite individuale) e che le risorse allocabili siano appunto soldi.

È chiaro che il sistema, come la banca, non può permettere a tutti i clienti di raggiungere il loro limite di credito contemporaneamente poiché in tal caso la banca fallirebbe (e il sistema non potrebbe allocare risorse a sufficienza, causando un Deadlock).

[modifica] Funzionamento dell'algoritmo

Si utilizzano 4 strutture dati di tipo Array per memorizzare le seguenti informazioni:

Disponibili $[m]$ : memorizza la quantità di ogni tipo di risorsa disponibile nel sistema.
Assegnate $[m \times n]$ : memorizza quante risorse per ogni tipo sono state allocate ad ognuno dei processi.
Massimo $[m \times n]$ : indica la quantità risorse che un processo allocherà al massimo.
Necessità $[m \times n]$ : necessità residua di risorse per ogni processo (calcolata sottraendo alla matrice Massimo la matrice Assegnate).

[modifica] Procedimento

L'algoritmo procede iterativamente, garantendo le risorse necessarie ai processi che, confrontando il loro array di Necessità con quello della risorse attualmente disponibili nel sistema, possono terminare la loro esecuzione. A esecuzione terminata, il processo libera le risorse che aveva già precedentemente allocato (ossia, l'array di risorse Assegnate al processo viene sommato alle risorse disponibili).

In tal modo l'algoritmo può selezionare un ulteriore processo che, con le risorse attualmente disponibili al sistema, può terminare e rilasciare a sua volta le risorse allocate.

[modifica] Risultato

L'algoritmo può decidere che il sistema si trovi in uno Stato sicuro se, attraverso i suoi tentativi ripetuti di trovare un ordine di esecuzione dei processi, scopre una sequenza per cui a tutti gli $n$ processi vengono allocate le risorse concludendo la loro esecuzione.