Deadlock

Deadlock

Un insieme di processi si trova in una situazione di stallo o deadlock se ogni processo dell'insieme aspetta un evento (tipicamente il rilascio di una risorsa) che solo un altro processo dell'insieme può provocare: ciascun processo coinvolto nel deadlock risulta impossibilitato a proseguire perchè non in grado di acquisire autonomamente l'aliquota mancante di risorse che gli sarebbero necessarie per una corretta terminazione. Un esempio didattico di deadlock di natura pratica coinvolge due persone sedute ad un tavolo con un'unica bottiglia e un unico bicchiere: se uno prende il bicchiere e l'altro la bottiglia nessuno dei due potrà bere e si entra in stallo. Un deadlock può verificarsi solo se si presentano tutte e quattro contemporaneamente le seguenti condizioni necessarie e sufficienti:

mutua esclusione (almeno una delle risorse deve essere ad uso esclusivo se sono tutte private e non condivisibili chiaramente non ci sarà mai un deadlock)

possesso ed attesa (i processi che richiedono una risorsa devono attendere prima di richiederne delle altre, ma non restituiscono quelle di cui sono già in possesso)

impossibilità di prelazione (solo il processo che detiene la risorsa può rilasciarla e non è previsto il prerilascio, ovvero non è possibile sottrargliela con la forza)

attesa circolare (esiste un gruppo di processi in cui P è in attesa per una risorsa occupata da P , P per un risorsa di P , Pn per una risorsa di P

In assenza di almeno una di queste condizioni si è certi che il sistema è deadlock free. Le strategie possibili da adottare per la gestione dei deadlock sono almeno quattro: prevenire, evitare, rilevare e risolvere. Inutile dire che scegliere deliberatamente di ignorare la possibilità che si presenti un deadlock non rappresenta di per sè una strategia valida: un sistema in deadlock è un sistema bloccato che gira a vuoto, mantenendo i processi attivi in condizione di stallo e le risorse allocate di fatto inutilizzate.

Per prevenire un deadlock occorre - in teoria - fare sì che almeno una delle quattro condizioni citate non si verifichi mai. La condizione di mutua esclusione non può essere eliminata se non rinunciando ad un modello di risorse comuni, ma in tale ipotesi il problema del deadlock non si pone affatto. La condizione di possesso e attesa può essere eliminata rinunciando del tutto all'allocazione dinamica (ad ogni processo che ha bisogno di certe risorse si impone di richiederle tutte insieme in anticipo conservandole fino alla propria terminazione, e non invece a tempo di esecuzione un po' alla volta) oppure consentendo una allocazione dinamica con vincolo di restituzione (un processo può acquisire nuove risorse solo se prima riconsegna tutte quelle in suo possesso, anche se queste ultime possono in teoria ancora servirgli prima della terminazione): ambedue queste strategie sono applicabili in teoria, ma determinano in pratica un utilizzo inefficiente delle risorse così come il fatto che un processo potrebbe andare incontro al fenomeno dello starvation (almeno una delle risorse di cui ha bisogno è sempre in possesso di qualche altro processo). Forzare la prelazione (per eliminare la terza condizione) è spesso difficile o impossibile perchè, per imporre ad un processo il rilascio forzato di una risorsa, occorre comunque garantire ad esso che questa gli sarà restituita nel medesimo stato in cui si trovava al momento in cui gli è stata tolta (irrealizzabile ad esempio nel caso delle stampanti). La condizione di attesa circolare, infine, può essere eliminata applicando un ordinamento totale alle risorse e imponendo che se i < j un processo può ottenere la risorsa Rj solo se già possiede Ri, o equivalentemente imponendo che rilasci Rj se non possiede Ri. In realtà questo discorso resta solo teorico, poichè non esiste alcun SO che prevenga il deadlock affidandosi all'inibizione di una delle quattro condizioni che lo determinano: la prevenzione del deadlock è semplicemente una speculazione didattica senza alcuna applicazione commerciale.

Per evitare un deadlock è possibile eseguire un opportuno algoritmo di controllo che, ad ogni allocazione di risorsa, verifichi se tale assegnazione prelude ad una situazione di stallo: tutti gli algoritmi siffatti funzionano solo se si impone ai processi di dichiarare in anticipo il numero (non il tipo) massimo di risorse di cui ciascuno avrà bisogno durante la propria esecuzione. Tra i possibili algoritmi applicabili, abbiamo analizzato l'Algoritmo del banchiere (la cui denominazione richiama la strategia di prestito che un titolare avveduto di una banca dovrebbe adottare per far sì che la cassa del denaro non rimanga mai vuota) basato sulla verifica di stato sicuro del sistema: un SO si dice in stato sicuro se, assegnata una parte delle risorse ai processi attivi e posto che le risorse libere non siano tutte esaurite, esiste sempre almeno una possibile sequenza di allocazione delle risorse residue (tipicamente ad un processo alla volta) tale che tutti i processi ancora attivi siano in grado di teminare in modo corretto; un classico stato non sicuro si verifica quando, considerati "terminati" tutti i processi che singolarmente hanno bisogno di un numero di risorse non superiori a quelle attualmente disponibili (e quindi annoverando tra quelle disponibili anche tutte le risorse rilasciate da tali processi che si sta supponendo terminati), dei restanti processi attivi nessuno è in grado di accaparrarsi le risorse di cui ha necessità se non ipotizzando di doverle togliere con la forza ad un altro; supponendo che un SO si trovi in stato sicuro, ad ogni nuova richiesta di allocazione di una risorsa, l'algoritmo ha il compito di verificare se, nel caso tale richiesta venisse accordata, il sistema continuerà a rimanere in uno stato sicuro o meno; si noti comunque che, se anche un SO si viene a trovare in uno stato non sicuro, non è detto che un deadlock debba necessariamente verificarsi, esiste solo una possibilità concreta che ciò accada. Segue l'algoritmo del banchiere in codice pascal-like

var max : array[1..N, 1..M] of integer; Max(i,j) numero massimo di istanze di risorsa J di

cui il processo I ha bisogno in totale

need : array[1..N, 1..M] of integer; Need(i,j) numero residuo di istanze di risorsa J di

cui il processo I ha bisogno attualmente (inizialmente ha gli stessi valori di Max(i,j))

allocation : array[1..N, 1..M] of integer; Mappa delle allocazioni attuali (processo/risorsa)

request : array[1..N, 1..M] of integer; Richiesta attuale di allocazioni (processo/risorsa)

available : array[1..M] of integer; Istanze libere per ciascuno degli M tipi di risorse

S : array[1..N] of boolean initial(true); Vettore Stato Sicuro legata al processo i-esimo

work : array[1..M] of integer; Vettore ad uso temporaneo

finish : array[1..N] of integer; "

procedure Banchiere(i : integer);

begin

if (request[i] > need[i]) then <restituisci un errore>

else if (request[i] > available) then wait( P[i] );

else begin

Verifica_Stato_Sicuro( i );

if S[i] then <alloca risorse>

else begin

available:=available + request[i]; Ripristino della struttura dati

allocation[i]:=allocation[i] - request[i];

need[i]:=need[i] + request[i];

S[i]:=true;

wait( P[i] );

end;

end;

end;

procedure Verifica_Stato_Sicuro(i : integer); NB: operazioni algebriche e confronti

var j :integer; qui effettuati tra vettori vanno intesi

flag : boolean; elemento per elemento!

begin

for j:=1 to N do finish[j]:=false; Inizializzazione di "finish" a FALSE

available:=available - request[i]; Simulazione di allocazione effettiva

allocation[i]:=allocation[i] + request[i]; al processo i-esimo delle risorse

need[i]:=need[i] - request[i]; che ha richiesto

work:=available; Salvataggio "available" corrente

repeat

flag:=true; Ad ogni ciclo Flag è TRUE

for j:=1 to N do

if finish[j]=false and need[j]<=work then begin Simulazione di terminazione di ciascun

work:=work + allocation[j]; processo e restituzione ad "available"

finish[j]:=true; delle risorse occupate ogni volta che

flag:=false; un processo "termina" Flag diventa FALSE

end; per ripetere precauzionalmente il ciclo

untile flag=true;

j:=0;

repeat Lo stato S[i] è TRUE solo se tutti i

j:=j + 1; finish[j] sono TRUE, ovvero se tutti i

until finish[j]=false or j=N; processi sono in grado di terminare

S[i]:=finish[j];

end;

ad ogni richiesta di risorse da parte di un processo i-esimo, viene lanciata la routine di controllo Banchiere, la quale controlla che la richiesta non ecceda la necessità residua stimata (stima fatta a partire dal numero massimo di risorse dichiarate inizialmente come necessarie al singolo processo), se la richiesta non può essere soddisfatta mette il processo in attesa su un semaforo privato, altrimenti prima di allocare le risorse richieste lancia una routine di Verifica dello Stato Sicuro: se questa restituisce uno stato sicuro allora le risorse vengono effettivamente allocate, altrimenti il processo viene ugualmente messo in attesa (e le strutture dati modificate ripristinate

Se il SO non usa alcuno strumento per evitare in tempo reale il deadlock, si può scegliere di rilevare il deadlock quando si è già verificato e - una volta rilevato - si può risolvere lo stallo occorso. L'algoritmo per la rilevazione del deadlock è una variante della routine di Verifica dello Stato Sicuro già presentata

procedure Verifica_Deadlock(var OK : boolean); NB: operazioni algebriche e confronti

var j :integer; qui effettuati tra vettori vanno intesi

flag : boolean; elemento per elemento!

begin

for j:=1 to N do begin Inizializzazione di "finish" a FALSE,

finish[j]:=false; tranne che per quei processi che si

if not allocation[i] finish[j]:=true; "assumono" già terminati

end;

work:=available; Salvataggio "available" corrente

repeat

flag:=true; Ad ogni ciclo Flag è TRUE

for j:=1 to N do

if finish[j]=false and request[j]<=work then begin Simulazione di terminazione di ciascun

work:=work + allocation[j]; processo e restituzione ad "available"

finish[j]:=true; delle risorse occupate ogni volta che

flag:=false; un processo "termina" Flag diventa FALSE

end; per ripetere precauzionalmente il ciclo

untile flag=true;

j:=0;

repeat Lo stato NO_DEADLOCK è TRUE solo se tutti

j:=j + 1; I finish[j] sono TRUE, ovvero se tutti i

until finish[j]=false or j=N; processi sono in grado di terminare

OK:=finish[j];

end;

e in essa non c'è alcuna allocazione da simulare, c'è solo uno stato corrente da verificare. I processi che non hanno allocato risorse si assumono dormienti, terminati o comunque ininfluenti sull'eventuale stato di deadlock in corso, inoltre la simulazione di terminazione dei processi attivi viene eseguita tenendo conto della richiesta attuale e non del numero totale di risorse residue che il processo potrebbe in teoria richiedere allo scopo di terminare: un processo potrebbe certamente fare una richiesta pericolosa solo in un tempo successivo ma, se questa dovesse produrre effettivamente un deadlock, esso verrebbe certamente rilevato alla prossima esecuzione della Verifica_Deadlock. Resta da capire con che frequenza è opportuno lanciare questo algoritmo di rilevamento il primo sintomo che è in corso un deadlock è l'impossibilità di un processo di allocare una risorsa, tuttavia eseguire la verifica ogni volta che ciò succede sarebbe non solo poco efficiente ma aumenterebbe in maniera intollerabile i tempi di calcolo: un'alternativa plausibile è quella di eseguire la verifica ciclicamente (per esempio ogni ora) oppure soltanto quando l'uso della CPU scende sotto una certa soglia (ad esempio il 40%), visto che normalmente un deadlock produce un crollo delle prestazioni del sistema legato ad un crollo d'uso della CPU. Una volta rilevato il deadlock, due sono fondamentalmente le strategie possibili per risolverlo: mediante eliminazione (abort) di uno o più processi in attesa circolare, tutti simultaneamente oppure uno alla volta verificando dopo ogni abort se il deadlock persiste (strategia dispendiosa, soprattutto nella seconda variante, anche perchè i processi potrebbero aver eseguito già molte operazioni che andranno così irrimediabilmente perdute); mediante prerilascio delle risorse ad uno o più dei processi bloccati, a tutti simultaneamente oppure uno alla volta verificando dopo ogni prelazione se il deadlock persiste (i processi che subiscono il prerilascio andrebbero posizionati in uno stato consistente dal quale possano poi continuare l'esecuzione quando la risorsa gli verrà riconcessa, accorgimento spesso difficile e a volte impossibile); mediante la creazione e il puntuale aggiornamento di registri che descrivono lo stato di utilizzo delle risorse condivise, in modo che in caso di stallo sia possibile effettuare un ritorno al più vicino punto di controllo sicuro (rollback to checkpoint), con conseguente disfacimento soltanto di quelle operazioni che hanno preceduto e presumibilmente indotto il deadlock (tecnica sicuramente complessa, spesso difficile e a volte impossibile da realizzare perchè il disfacimento forzato può indurre inconsistenza dei dati