Algoritmo del banchiere

ALGORITMO DEL BANCHIERE

Il nome di questo algoritmo di deve al fatto che esso si fonda sulla strategia che il titolare (avveduto) di una banca di prestiti deve adottare se vuole che la cassa del denaro non rimanga mai vuota. Esso richiede una struttura dati piuttosto articolata, che viene descritta qui di seguito:

Il codice dell'algoritmo è il seguente (si noti che ad esempio con need_i si intende la riga i-esima della matrice need):

Procedure barbiere ;

begin

if (request_i > need_i) then < errore >

else if (request_i > available_i) then wait (P_i)

else

begin

verifica_stato_sicuro (S_i) ;

if (S_i) then alloca_risorse else

begin

wait (P_i) ;

ripristina _struttura_dati

end ;

end ;

end.

Il generico processo effettua una richiesta di risorse; se tale richiesta è superiore alla necessità residua si ha un errore, mentre se è inferiore si passa a confrontare la richiesta con l'effettiva disponibilità. Se le risorse disponibili non sono sufficienti a soddisfare la richiesta, il processo dovrà mettersi in attesa. Contrariamente, si vaglia la possibilità di concedere le risorse: allo scopo si esamina la condizione di stato sicuro (relativamente a ciò che succederebbe se le risorse fossero effettivamente assegnate), richiamando la procedura che segue. Se la condizione di stato sicuro risulta contraddetta il processo dovrà ancora mettersi in attesa, altrimenti si concede l'allocazione. Si noti che in caso di attesa occorre risistemare la struttura dati, che è stata modificata dall'esecuzione della procedure verifica_stato _sicuro.

Nel testo seguente compaiono relazioni di 'minoranza fra due vettori'. Affermando che un vettore è minore o uguale a un altro intendiamo dire che la relazione di minoranza è verificata componente per componente (ad es.: (2,0,1) < = (5,0,2)).

procedura verifica_stato_sicuro (S_i = boolean) ;

var j : integer ;

flag : boolean ;

begin

S_i := true ;

/* viene riprodotta la situazione che si verrebbe a creare

in caso di effettiva assegnazione */

available : = available - request_i ;

allocation_i : = allocation_i + request_i ;

need_i : = need_i - request_i ;

/* lo stato di arrivo sarebbe sicuro? Le istruzioni seguenti lo verificano */

work : = available ;

for j : = 1 to n do finish [j] : = false ;

repeat

flag : = true ;

for j : = 1 to n do

if finish[j] = false and need_j < = work then

begin

work : = work + allocation_j ;

finish[j] : = true ;

flag : = false 

end

until flag ;

j : = 0 ;

repeat

j : = j + 1

until not finish[j] or j = n ;

S_i := finish[j] ;

end ;

Affinché le risorse vengano allocate deve risultare 'S_i = true'. L'assegnazione del valore logico ad S_i avviene nell'ultima istruzione di questa procedura, e, perché il valore assegnato sia true, il vettore finish deve essere composto interamente da true (si deve cioè giungere alla conclusione che ogni processo possa finire la propria esecuzione). Si consideri allora il primo ciclo Repeat until. Affinché tutti gli n elementi di finish (che vengono inizializzati a false) siano posti a true, devono essere eseguite per ogni j I 1..n le istruzioni contenute nella sezione begin.. end. Se si prospetta l'eventualità che, in seguito all'assegnazione, il fabbisogno degli n processi non possa essere più appagato (need_i > work), l'ingresso a tali istruzioni viene precluso. È sufficiente che ciò accada anche per un solo degli indici j perché ne consegua la mancata assegnazione. Si noti per inciso che il ciclo repeat until viene percorso una sola volta unicamente nel caso limite in cui la condizione di fabbisogno insoddisfatto si verifichi per tutti e n i processi, altrimenti sempre due volte.

RILEVAMENTO DEL DEADLOCK E SUO SUPERAMENTO. Supponiamo ora che il sistema non utilizzi alcuno strumento per evitare il deadlock. In tal caso, un eventuale deadlock può essere rilevato solo dopo la sua occorrenza e pertanto il SO deve fornire due algoritmi:

- un algoritmo per rilevare la presenza di un deadlock;

- un algoritmo per eliminare la condizione di deadlock.

L'algoritmo per la rivelazione dello stato di deadlock viene proposto di seguito.

Procedure Test_deadlock (var deadlock : boolean) ;

var i : integer ;

flag : boolean ;

begin

work : = available ;

for i : = 1 to n do

finish [i] : = true ;

if allocation_i < > 0 then finish [i] : = false ;

repeat

flag : = true ;

for i : = 1 to n do

if finish [i] = false and request_i < = work then

begin

work : = work + allocation_i ;

finish [i] : = true ;

flag : = false ;

end ;

until flag ;

i : = 0 ;

repeat

i : = i + 1

until not finish [i] or i = n ;

deadlock : = finish [i] ;

end ;

Vengono usati i vettori available, work e finish e la matrice allocation della struttura dati del caso precedente, con identico significato; request è invece una matrice n x m che indica la richiesta attuale dei processi: ' request i,j = k ' significa che il processo i sta richiedendo altre k istanze della risorsa j.

Si noti la notevole somiglianza esistente fra questo algoritmo e quello subito precedente. Cambiano, oltre all'istruzione finale:

- la parte iniziale. In questo caso non c'è evidentemente una situazione da simulare, ma occorre analizzare una situazione già esistente. Quindi, la struttura dati non viene modificata. Inoltre il vettore finish viene posto a false solo per i processi non ancora terminati, ossia laddove allocation_i <> 0.

- la condizione need_j < = work, che qui diventa request_i < = work. Ai fini dell'ipotesi di terminazione di un processo i viene considerata attendibile la richiesta di risorse piuttosto che l'effettivo bisogno. È evidente che se request_i < = work è garantito il fatto che il processo P_i non è attualmente coinvolto in un deadlock. Naturalmente P_i potrebbe stare effettuando per qualche motivo una richiesta inferiore al bisogno reale, e in un successivo momento potrebbe sovrapporre ulteriori richieste, magari fino al punto di causare un deadlock, ma non c'è problema: ciò sarebbe certamente rilevato alla successiva esecuzione dell'algoritmo.

Quando è consigliabile attivare l'algoritmo di rilevamento del deadlock? Osserviamo che il deadlock può verificarsi solo se accade che un processo fa una richiesta che non può essere immediatamente soddisfatta. Si può pensare quindi di attivare l'algoritmo ogni volta che si presenta questa eventualità, ma tale scelta sarebbe palesemente inopportuna poiché aumenterebbe in maniera intollerabile i tempi di calcolo. Alternative più plausibili consistono nell'attivare l'algoritmo periodicamente (ad es. ogni ora), oppure ogni volta che la CPU risulta sottoutilizzata, ad esempio ogni volta che l'aliquota di utilizzo della CPU scende al di sotto del 40%. Infatti, un deadlock ha generalmente l'effetto di rendere inefficienti le prestazioni del sistema e in particolare di causare una caduta nell'uso del processore.

Veniamo ora brevemente alla questione dell'eliminazione dello stato di deadlock. Un deadlock può essere eliminato in due modi:

1) mediante l'abort di uno o più dei processi che si trovano in attesa circolare. Si può pensare di abortire simultaneamente tutti i processi che si trovano in deadlock, oppure di abortirne uno per volta, verificando dopo ogni abort se esistono ancora processi in deadlock. Entrambe le strategie possono risultare molto dispendiose: la seconda per ovvie ragioni; la prima perché i processi abortiti potrebbero avere effettuato già parecchi calcoli, e i loro risultati vengono così irrimediabilmente persi.

2) mediante prerilascio delle risorse. Si tolgono con la forza le risorse ad uno dei processi bloccati, mettendole a disposizione di altri; se ciò non basta si fa la stessa cosa via via con tutti gli altri. I processi che subiscono il prerilascio vanno posizionati in uno stato dal quale poi possano essere riavviati (ROLLBACK).