Il deadlock

IL DEADLOCK

Il termine DEADLOCK può essere considerato come sinonimo di stallo, ed è la situazione che si verifica quando i processi sono impossibilitati a proseguire perché nessuno di essi è in grado di acquisire quell'aliquota di risorse residue che occorrerebbe loro per una corretta terminazione. Il problema nasce dal fatto che le risorse possono essere utilizzate da un solo processo al volta, e se incidentalmente una risorsa HW o SW viene allocata a più processi richiedenti si verifica una situazione di deadlock.

Un esempio di natura pratica che può aiutarci a capire la natura del deadlock potrebbe essere il seguente: immaginiamo che due persone vogliano bere, e che siano disponibili solo una bottiglia ed un bicchiere. Se uno dei due prende la bottiglia, e l'altro il bicchiere, nessuno dei due potrà bere (stallo).

Cerchiamo ora di riassumere le condizioni entro le quali può verificarsi il deadlock e le strategie da usare per superare questa situazione.

Affinché in un sistema possa dar luogo ad un deadlock, devono verificarsi ben quattro circostanze contemporaneamente:

1) Condizione di mutua esclusione; se tutte le risorse sono private ai processi, e quindi non si verifica nessuna esigenza di gestire una mutua esclusione, è ovvio che non si può avere un deadlock.

2) Possesso ed attesa; un processo si tiene strette le risorse che gli sono state già assegnate, e ne richiede delle nuove, ponendosi in attesa della loro concessione senza restituire ai rispettivi gestori le risorse di cui è in possesso.

3) Impossibilità di prelazione; non è previsto il prerilascio, cioè non è possibile sottrarre con la forza delle risorse ad un processo.

4) Attesa circolare; un processo che possiede delle risorse ne attende altre da parte di un altro processo che a sua volta è in attesa delle risorse del primo.

Quindi è possibile prevenire il deadlock facendo in modo che almeno una delle quattro condizioni precedenti sia sempre falsa. In tal caso, possiamo essere certi che il sistema è DEADLOCK FREE.

Tuttavia, applicare la strategia di eliminare una delle quattro condizioni summenzionate, ossia tentare di prevenire il deadlock, è il modo più difficile e anche più costoso di affrontare il problema.

Spesso si rinuncia a prevenire il deadlock nel modo descritto, ma piuttosto si cerca di evitarlo mediante un algoritmo che interviene ogni volta che si verifica una richiesta di risorse da parte di un processo e che si accerta se esiste o meno la possibilità che, nelle condizioni attuali, si verifichi un deadlock.

Infine, si potrebbe pensare anche di ignorare del tutto il problema del deadlock, ma questa scelta potrebbe portare a realizzare un sistema che gira a vuoto e quindi inutile.

Considereremo ora in modo più dettagliato le due alternative principali.

1) PREVENIRE IL DEADLOCK. Si deve far sì che almeno una della quattro condizioni di cui alla pagina precedente non si verifichi mai.

Salta subito all'occhio che la condizione di mutua esclusione non può essere mai eliminata del tutto, perché ciò vorrebbe dire considerare un sistema gestito secondo il modello delle risorse private, anziché comuni, e quindi il problema del deadlock non si presenterebbe proprio.

Vediamo se possiamo eliminare la condizione di possesso ed attesa. Facciamo cioè in modo che ogni processo che necessiti di utilizzare determinate risorse le deve chiedere sin dall'inizio, conservandone il possesso fino alla propria terminazione; nessun processo può richiedere delle risorse a tempo di esecuzione; dunque, praticamente, rinunciamo all'allocazione dinamica delle risorse. Un'altra strategia potrebbe essere viceversa quella di permettere l'allocazione dinamica delle risorse, ma di impedire che un processo acquisisca delle risorse se non ha prima riconsegnato tutte le risorse di cui è in possesso, anche nel caso che alcune di queste ultime gli possano ancora servire. Entrambe le tecniche citate potrebbero essere applicate in linea di principio, ma nella pratica esse comporterebbero un uso poco efficiente delle risorse ed un notevole spreco di tempo, e inoltre potrebbe verificarsi il fenomeno dello starvation, poiché un processo potrebbe ritrovarsi in una situazione tale che almeno una delle risorse di cui ha bisogno è sempre allocata a qualcun altro.

Ugualmente difficile è affidarsi alla condizione di prelazione. Non è sempre possibile forzare il rilascio di una risorsa da parte di un processo e concederla ad un altro, poiché bisogna garantire che in un momento successivo la risorsa possa essere restituita al processo iniziale nel medesimo stato in cui essa si trovava, e ad esempio questo è irrealizzabile nel caso delle stampanti.

La possibilità che appare più realistica è quella di impedire il verificarsi di attese circolari. Si può ad esempio stabilire un ordinamento totale fra le risorse; tutte le risorse vengono numerate, ed un processo P può ottenere la risorsa R_j, se già possiede una risorsa R_i, solo se R_j segue R_i nell'ordinamento che si è imposto. L'attesa circolare è allora di fatto scongiurata. Si noti che lo stesso effetto si ottiene imponendo che P rilasci R_i se R_i nell'ordinamento che si è disposto segue R_j.

Tutto il discorso fatto fin qui ha un valore esclusivamente teorico. Nei fatti, non esiste nessun SO che prevenga il deadlock mediante il sistema di inibire una delle quattro condizioni che insieme lo determinano. Si può affermare anzi che il problema della PREVENZIONE DEL DEADLOCK è un 'giocattolo', ideato per fini didattici ma che non trova rispondenze sul versante commerciale.

2) EVITARE IL DEADLOCK. Nel momento in cui si presenta l'opportunità di assegnare una risorsa ad un processo, l'assegnazione viene ritardata se ci accorgiamo che questa potrebbe portare ad un deadlock. Quindi dobbiamo applicare ad ogni richiesta di assegnazione un algoritmo incaricato di verificare se l'assegnazione può essere fatta senza incorrere in una situazione di stallo.

Tutti gli algoritmi della serie si basano sulla premessa che qualunque processo deve sempre dichiarare il numero massimo di risorse di cui avrà bisogno durante la propria evoluzione. Si sottolinea che deve essere dichiarato solo il numero, e non il tipo, di risorse. Di questi algoritmi ne presentiamo uno solo, detto ALGORITMO DEL BANCHIERE, basato sulla verifica di stato sicuro del sistema. In un determinato istante, un certo numero di processi sarà presente nel sistema, e ognuno di essi sarà in possesso di un certo numero di risorse. Di ogni processo, come abbiamo detto, si conosce il massimo numero di risorse che esso potrebbe richiedere. Inoltre in quell'istante esisterà un pool di risorse libere. Si dice allora che il SO è in stato sicuro se esiste almeno una possibile sequenza di allocazione delle risorse residue per la quale tutti i processi siano in grado di terminare, cioè se la situazione è tale che il SO può allocare in almeno un modo le risorse ad un processo alla volta (concedendone l'uso fino al massimo fabbisogno), fino alla terminazione di tutti i processi (e impedendo quindi il sopraggiungere di un deadlock).

Supponendo che il SO si trovi in uno stato sicuro, un algoritmo come quello del banchiere deve verificare, ad ogni nuova richiesta di risorse, se, nel caso la richiesta venga accordata, si continua a rimanere o meno in uno stato sicuro. Se la risposta è affermativa, si ha la sicurezza che almeno una sequenza di assegnazione delle risorse ai processi consente di non cadere in un deadlock.

Osserviamo che non è detto che se il sistema si trova in uno stato non sicuro il deadlock si verificherà di certo: esiste semplicemente una possibilità concreta che si verifichi. Prima di passare a spiegare l'algoritmo del banchiere, facciamo dunque un esempio semplice per chiarire la differenza tra stato sicuro e stato non sicuro. Un sistema ha 12 unità nastro, e ci sono tre processi, P1, P2 e P3, che devono utilizzarle.

Sono libere tre unità nastro (poiché 5 + 2 + 2 = 9), e quindi in questo momento il sistema è in uno stato sicuro, perché esiste una possibile sequenza di assegnazione per la quale tutti possano terminare. In particolare la sequenza P2 - P1 - P3 di allocazione per i nastri garantisce la terminazione di tutti i processi. Se P3 richiedesse una ulteriore unità a nastro, questa non dovrebbe essergli concessa, poiché in caso contrario il SO andrebbe in uno stato non sicuro. Infatti se la risorsa gli venisse allocata, si avrebbe la situazione seguente:

P2 ha bisogno di 2 unità, e poiché sono disponibili al momento proprio 2 unità, queste gli vengono assegnate; infine, le 4 risorse vengono rilasciate. Viene chiamato in causa P1, ma esso non può andare in esecuzione perché ha bisogno di 5 unità e ce ne sono solo 4. Lo stesso dicasi per P3, e il sistema va in deadlock.