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^2m), 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 alla base dell'algoritmo[modifica | modifica wikitesto]

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 del credito presso la banca (fino ad un certo limite individuale) e le risorse allocabili sono viste come i 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).

Funzionamento dell'algoritmo[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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. 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[modifica | modifica wikitesto]

  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[modifica | modifica wikitesto]

Supponiamo che il processo P_j richieda delle nuove risorse. Sia R_j[m] il vettore delle richieste del processo tale che R_je_i=k_i numero di istanze della risorsa i-esima richieste da P_j

  1. verifico che R_j\geq 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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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.

Voci correlate[modifica | modifica wikitesto]