Algoritmo del banchiere
- un algoritmo per evitare lo stallo sviluppato da Dijkstra (1965)
- il nome deriva dal metodo utilizzato da un ipotetico banchiere di provincia che gestisce un gruppo di clienti a cui ha concesso del credito; non tutti i clienti avranno bisogno dello stesso credito simultaneamente
Descrizione
- un banchiere desidera condividere un capitale (fisso) con un numero (prefissato) di clienti
- per Dijkstra l'"unità di misura" erano fiorini olandesi
- ogni cliente specifica in anticipo la sua necessità massima di denaro
- che ovviamente non deve superare il capitale del banchiere
- i clienti fanno due tipi di transazioni
- richieste di prestito
- restituzioni
- il denaro prestato ad ogni cliente non può mai eccedere la necessità massima specificata a priori
- ogni cliente può fare richieste multiple, fino al massimo importo specificato
- una volta che le richieste sono state accolte e il denaro è stato ottenuto deve garantire la restituzione in un tempo finito
Metodo di funzionamento
Il banchiere deve essere in ogni istante in grado di soddisfare tutte le richieste dei clienti, o concedendo immediatamente il prestito oppure comunque facendo loro aspettare la disponibilità del denaro in un tempo finito
Dati
- N: num clienti
- IC: capitale iniziale
- c_i: limite di credito del cliente i (c_i <=IC)
- n_i = c_i-p_i credito residuo del cliente i
- COH= IC - $\sum_{i=1}^N p_i$ saldo di cassa
Definzione: Stato SAFE
sia s una permutazione dei valori 1…N
- Esempio: N=4 s=1,2,3,4,2
- indichiamo con s(i) l'iesmia posizione della sequenza
si calcoli il vettore avail come segue
con $j=1…N-1$
Nota: lo stato UNSAFE è condizione necessaria ma non sufficiente per avere deadlock (i.e., un sistema in uno stato UNSAFE può evolvere senza procurare alcun deadlock)
sembra un deadlock ma il realta' il proc 3 ha ricevuto tutti i "soldi" che doveva ricevere e questo significa che puo darli indietro. La sequenza 3,2,1,4,5 esegue tutti i prestiti a compimento
Regola pratica (per il banchiere a singola valuta)
lo stato SAFE può essere verificato usando la sequenza che ordina in modo crescente i valori di ni.
nfatti, se esiste una sequenza di verificare la safety di uno stato, sicuramente anche la sequenza che ordina i valori di ni consente di fare altrettanto
Esempio stato unsafe
Banchiere multivaluta
Dati
Definizione stato SAFE
Problema:
- la regola di ordinare i processi secondo i valori di ni non è applicabile
- l'ordine può essere in generale diverso fra le diverse valute gestite dal banchiere
Soluzione:
- si può creare la sequenza procedendo passo passo aggiungendo un processo a caso fra quelli completamente soddisfacibili
- ovvero, al passo j si sceglie quelli per cui ns(j) ≤ avail[j]
Teorema
Se durante la costruzione della sequenza s si giunge ad un punto in cui nessun processo risulta soddisfacibile, lo stato non è SAFE, i.e. non esiste alcuna sequenza che consenta di soddisfare tutti i processi
Dimostrazione per assurdo:
supponiamo che lo stato sia SAFE, ovvero che esista la sequenza che consente di soddisfare tutti i processi
sia C la sequenza interrotta e C' la sequenza che porta allo stato SAFE
ALgoritmo dello struzzo
nascondere la testa sotto la sabbia, ovvero fare finta che i deadlock non si possano mai verificare
Motivazioni:
- dal punto di vista ingegneristico, il costo di evitare i deadlock può essere troppo elevato
Nota:
- è la soluzione più adottata nei sistemi Unix
- è usata anche nelle JVM