Algoritmo del banchiere

Da Wikipedia, l'enciclopedia libera.

L'Algoritmo del banchiere è utilizzato per evitare 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 è , dove è il numero di processi e 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 il numero di risorse disponibili, il numero di istanze della risorsa i-esima, e il numero di processi attivi:

  1. Array risorse disponibili : con memorizza la quantità di ogni tipo di risorsa disponibile nel sistema.
  2. Matrice risorse assegnate : con vettore che indica quante istanze di ogni risorsa sono state assegnate al processo .
  3. Matrice risorse massime : con vettore che indica quante istanze di ogni risorsa verranno al massimo richieste dal processo per portare a termine la computazione.
  4. Matrice delle risorse residue : con vettore che indica quante istanze di ogni risorsa sono necessarie al processo 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 che assicura la terminazione dell'intero set di processi attualmente in esecuzione. La parte di simulazione dell'assegnazione verrà eseguita quando un processo 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 un array di valori booleani in cui ogni variabile è inizialmente falsa e definiamo L come
  2. trova un indice tale che e se questo non esiste salta al passo 4
  3. poni , e salta al passo 2
  4. se per ogni i allora il sistema è in uno stato sicuro

Simulazione dell'assegnazione[modifica | modifica wikitesto]

Supponiamo che il processo richieda delle nuove risorse. Sia il vettore delle richieste del processo tale che numero di istanze della risorsa i-esima richieste da

  1. verifico che nel caso questo sia falso genero un errore, poiché il processo ha richiesto più risorse di quante ne può richiedere
  2. verifico che nel caso in cui questo sia falso, non accolgo la richiesta del processo per mancanza di risorse
  3. Simulo l'assegnazione ponendo ed eseguo la prima parte dell'algoritmo per verificare che sia un'assegnazione sicura, se non lo è nego la richiesta di

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 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]

Bibliografia[modifica | modifica wikitesto]

Een algorithme ter voorkoming van de dodelijke omarming.