Algoritmo del banchiere

L'algoritmo del banchiere è un algoritmo utilizzato per evitare deadlock nell'allocazione delle risorse. In particolare questo algoritmo può indicare se un sistema - in particolare un sistema operativo - si ritroverebbe 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.).

Concetto base

Un sistema, nell'allocare le risorse che vengono richieste, deve procedere come farebbe una banca: i processi sono visti come dei clienti che possono richiedere credito presso la banca (fino ad un certo limite individuale) e le risorse allocabili sono viste come il denaro.

È 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).

Funzionamento

Si utilizzano quattro array per memorizzare le seguenti informazioni, chiamando $m$ il numero di risorse disponibili, $k_{i}$ il numero di istanze della risorsa i-esima, e $n$ il numero di processi attivi:

1. array risorse disponibili $D[m]$: con $De_{i}=k_{i}$ memorizza la quantità di ogni tipo di risorsa disponibile nel sistema
2. matrice risorse assegnate $A[m\times n]$: con $e_{j}^{'}A=A_{j}$ vettore che indica quante istanze di ogni risorsa sono state assegnate al processo $P_{j}$
3. matrice risorse massime $M[m\times n]$: con $e_{j}^{'}M=M_{j}$ vettore che indica quante istanze di ogni risorsa verranno al massimo richieste dal processo $P_{j}$ per portare a termine la computazione
4. matrice delle risorse residue $N[m\times n]$: con $e_{j}^{'}N=N_{j}$ vettore che indica quante istanze di ogni risorsa sono necessarie al processo $P_{j}$ per portare a termine la sua computazione (calcolata sottraendo alla matrice Massimo la matrice Assegnate).

Procedimento

L'algoritmo procede iterativamente, garantendo le risorse necessarie ai processi che, confrontando il loro array di Necessità con quello delle risorse attualmente disponibili nel sistema, possono terminare la loro esecuzione. Ad esecuzione terminata, il processo libera le risorse che aveva 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. Possiamo dividere l'algoritmo in un due parti principali: la parte di verifica dello stato attuale, e la parte di simulazione dell'assegnazione. La verifica dello stato attuale assicurerà che l'attuale assegnazione di risorse ai processi è un'assegnazione che fa permanere il sistema in uno stato sicuro. Uno stato è definito sicuro se esiste una sequenza di scheduling di processi $<P_{i},P_{j},P_{n},....P_{k}>$ che assicura la terminazione dell'intero set di processi attualmente in esecuzione. La parte di simulazione dell'assegnazione verrà eseguita quando un processo $P_{j}$ richiederà delle risorse. L'algoritmo simulerà questa assegnazione e farà poi partire una verifica dello stato, per assicurarsi che l'assegnazione permette di ritrovarsi in uno stato sicuro.

Verifica dello stato

1. Sia $F[n]$ un array di valori booleani $(false,true)$ in cui ogni variabile è inizialmente falsa e definiamo L come $L[m]=D[m]$
2. trova un indice $j$ tale che $F_{j}=false$ e $L\geq N_{j}$ se questo non esiste salta al passo 4
3. poni $L=L+A_{j}$, $F_{j}=true$ e salta al passo 2
4. se $F_{j}==true$ per ogni i allora il sistema è in uno stato sicuro

Simulazione dell'assegnazione

Supponiamo che il processo $P_{j}$ richieda delle nuove risorse. Sia $R_{j}[m]$ il vettore delle richieste del processo tale che $R_{j}e_{i}=k_{i}$ numero di istanze della risorsa i-esima richieste da $P_{j}$

1. verifico che $R_{j}\leq N_{j}$ nel caso questo sia falso genero un errore, poiché il processo ha richiesto più risorse di quante ne può richiedere
2. verifico che $D\geq R_{j}$ nel caso in cui questo sia falso, non accolgo la richiesta del processo $P_{j}$ per mancanza di risorse
3. Simulo l'assegnazione ponendo$A_{j}=A_{j}+R_{j}\;\;\;\;D=D-R_{j}\;\;\;\;N_{j}=N_{j}-R_{j}$ ed eseguo la prima parte dell'algoritmo per verificare che sia un'assegnazione sicura, se non lo è nego la richiesta di $P_{j}$

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.

Stato sicuro

Il concetto di stato sicuro è stato introdotto da Edsger W. Dijkstra probabilmente nel 1965 (o nel 1966) quando sviluppò il suo sistema operativo multiprogrammabile THE (Technische Hogeschool Eindhoven). Una descrizione formale può essere data dal seguente enunciato (in pseudocodice C++):

if (
    Initial_State == SECURE &&
    All_Commands == SECURE &&
    All_Transactions == SECURE &&
    All_Axioms == true
) System_State = SECURE

Lo stato sicuro quindi è uno stato in cui è possibile allocare tutte le risorse richieste da un processo senza che quest'ultimo comporti un deadlock con un altro processo. Il fatto che il sistema si trovi in uno stato sicuro non implica che tutte le allocazioni di risorse avverranno con successo, ma solo che esiste almeno un modo sicuro per allocare tutte le risorse. Se il sistema si trova in uno stato sicuro il deadlock può essere evitato, ma ovviamente uno stato non sicuro non implica necessariamente un deadlock. Il sistema infatti può dunque evitare del tutto gli stalli se ad ogni richiesta di una risorsa da parte di un processo, effettua una verifica dello stato in cui si troverebbe allocando la risorsa. Se lo stato futuro è sicuro, allora la risorsa può essere tranquillamente allocata. A tal fine si può utilizzare l'algoritmo del banchiere.

Questo concetto è difficilmente attuabile sui sistemi moderni, sia perché non è possibile prevedere in modo deterministico l'allocazione delle risorse, come richiesto dall'algoritmo del banchiere, sia perché sarebbe troppo costoso in termini economici. La maggior parte dei sistemi operativi, a partire dallo Unix, non considera il problema di eventuali deadlock in quanto esso infatti è un evento molto raro, data l'abbondanza delle risorse a disposizione. Inoltre è doveroso aggiungere che oggigiorno la gestione dei deadlock è sicuramente più critica nei database che non nei sistemi operativi.

Bibliografia

• (NL) Een algorithme ter voorkoming van de dodelijke omarming. (PDF), su University of Texas.

Voci correlate

• Deadlock
• Processo (informatica)