Introduzione al deadlock (parte I)

INDICE:

• Introduzione
• Risorse e assegnazione
• Modello di richiesta/assegnazione
• Generare un deadlock e situazioni errate
• Come riconoscere allora un deadlock
• Introduzione alla prevenzione del deadlock(nella parte II)
• Prevenire il deadlock
• - Deadlock Avoidance
• - Un esempio di deadlock avoidance: L'algoritmo del banchiere
• - Deadlock Detection & Recovery
• Situazioni reali

INTRODUZIONE
Questa problematica nasce quando i sistemi operativi hanno incominciato a supportare più processi contemporaneamente e quindi a dover gestire la richiesta e l'assegnazione delle risorse ad essi. Queste risorse possono essere la disponibilità di CPU, la memoria, ma anche segnali, messaggi o interrupt.
Possono nascere dei problemi nel moment in cui si hanno più processi nella stessa macchina che acquisiscono risorse per poter procedere.

Per capire le problematiche che si possono avere in una situazione del genere proviamo ad ipotizzae un processo che ha il compito di aggiornare una base di dati e che quindi ha bisogno di accedere a diversi file che la compongono.
L'aggiornamento richiede quindi che il processo debba poter prendere contemporaneamente questi file in modo da rendere consistente l'aggiornamento su tutte le tabelle.
Ma non è detto che questo sia l'unico processo che in quel momento richiede di accedere ai file in questione.

Se il primo processo inizia a prendere i file in maniera sequenziale dal primo all'ultimo mentre il secondo parte dall'ultimo verso il primo, si rischia di avere metà risorse per ciascun processo. Siccome entrambi i processi hanno bisogno di tutti i file per continuare l'aggiornamente si rischia di avere metà delle risorse a disposizione per ognuno.
Da qui nasce il termine deadlock, dove nessuno dei due processi può evolvere.

RISORSE E ASSEGNAZIONE
Esistono tre tecniche per risolvere il problema del deadlock che partono dalla prevenzione dell'errore fino al recovery.
Si hanno quindi: prevenzione (da la garanzia che il deadlock non si verifichi, ma pone anche un comportamento abbastanza rigido alla concorrenza sul sistema), l'avoidance e il detection/recovery (ammette la possibilità di deadlock, ma tiene degli strumenti per poter riconoscere la condizione e cercare di sistemarla; ad esempio uno dei due processi in questione può essere ucciso).
In generale più s da la possibilità al deadlock di verificarsi, più aumenta la concorrenza al sistema.

Le risorse possono essere classificate in due tipi, Riutilizzabile e Non Riutilizzabili. Le prime sono quelle che procurano più facilmente situazioni di deadlock. Esse non possono in particolare essere utilizzate contemporaneamente da più processi e non vengono distrutte dopo il loro uso; di queste si occupa il sistema operativo.
Le seconde sono meno pericolose dal punto di vista di situazione di deadlock, e scompaiono dopo il loro uso.
Riassumendo brevemente:

RIUTILIZZABILI (CPU, Canali di I/O, Risorse di memoria etc.)

- Non possono essere utilizzate da più processi contemporaneamente
- Non vengono rilasciate dopo il loro uso
- L'assegnazione viene tipicamente fatta dal sistema operativo

NON RIUTILIZZABILI (Segnali, interrupt, Messaggi etc.)

- In generale non c'è limite alle volte in cui essa può essere riprodotta
- Una volta usata viene rilasciata dal sistema operativo e non può essere di nuovo usata
- Può essere fornita da processo a processo

E' necessario stabilire una sorta di protocollo per poter permettere l'accesso a una risorsa da parte di un determinato processo. Nei sistemi operativi generalmente si applica una sequenza in tre punti:

• Richiesta Il processo richiede una particolare risorsa. Se questa richiesta non può essere soddisfatta immediatamente il processo può decidere se attendere o meno che questa torni di nuovo disponibile.
• Assegnazione Il processo può operare sulla risorsa per gli scopi specifici per cui ne ha richiesto l'assegnazione.
• Rilascio Nel caso in cui la risorsa sia riutilizzabile da altri processi, viene di nuovo rilasciata al sistema che provvederà ad una nuova assegnazione in base alle richieste. Il sistema operativo in particolare si occupa di mantenere una tabella di assegnazione delle risorse per i processi attivo; anche per le risorse non riutilizzabili viene mantenuta una tabella delle richieste de processi.

MODELLO DI RICHIESTA E ASSEGNAZIONE
Attraverso la rappresentazione di un deadlock all'interno di un grafo di risorse possiamo capire più in dettaglio come può nascere un problema di questo genere.

Il grafo viene realizzato modellando in modo grafico le varie risorse, il tipo (riutilizzabili e non) e infine il loro stato (assegnata, pendente). In questo grafo ci sono de processi che richiedono o hanno assegnate delle risorse.
Se un arco va da una risorsa a un processo vuol dire che quella risorsa è stata assegnata al processo, mentre se un arco è tratteggiato da un processo a una risorsa, vuol dire che quel processo ha fatto richiesta d'assegnazione.
Nel momento in cui la risorsa richiesta viene effettivamente assegnata (e quindi non è più pendente) la freccia inverte il verso e diventa continua.
La scomparsa di un arco indica che il processo ha terminato l'uso della risorsa e questa è quindi libera per essere utilizzata altrove - nel caso ovviamente sia riutilizzabile.

Una risorsa può essere singola (e quindi non istanziabile più volte, ad esempio la CPU) ed è quindi rappresentata da un rettangolo con un solo puntino dentro, oppure può essere istanziabile più volte e quindi ha più puntini al suo interno.

A livello grafico un deadlock non è altro che un ciclo all'interno di questo grafo. Può in particolare singnificare che un processo ha già delle risorse e ne ha richieste altre che appartengono ad un altro processo.

La presenza di un deadlock (ciclo) nel grafo può dirci quindi:

• che tutti i procecessi facenti parte del ciclo sono coinvolti nella situazione di deadlock
• nel caso in cui le risorse coinvolte siano riutilizzabili siamo certi di essere in un deadlock
• nel caso in cui le risorse non sia riutilizzabili e il processo sia l'unico in grado di generarle siamo in un deadlock
• nel caso di risorse riutilizzabili con istanze multiple, o di risorse non riutilizzabili per le quali è possibile che esse siano prodotte da un processo esterno al ciclo, allora la presenza del ciclo non è sufficiente ad ammettere la presenza di deadlock.

GENERARE UN DEADLOCK E SITUAZIONI ERRATE
Esistono tre situazioni che se veriicate possono produrre sul grafo un'attesa circolare, ossia un ciclo di deadlock. La mancanza di almeno una di esse permette di escludere il deadlock.
Queste situazioni sono:

• Mutua esclusione La risorsa non è condivisibile e se occupa il processo deve attenderne il rilascio
• Possesso e attesa Un processo può richiedere e attendere risorse dopo averne acquisite già altre
• Impossibilità di prelazione Una risorsa assegnata a un processo può essere rilasciata solo spontaneamente da esso.

Questo è un grafo con deadlock:

Esistono comunque de cicli che non implicano una situazione di deadlock. Ad esempio:

In questa situazione R2 ha come proprietario P1.
P1 fa richiesta per R1.
P3 possiede un'istanza di R1 e richiede R2.
In più P4 possiede la seconda istanza di R2 e P2 possiede la prima istanza di R1.
In questo caso si è in presenza di un ciclo, ma esso può essere risolto in modo molto semplice perch P2 e P4 non hanno fatto altre richieste: quando almeno uno di essi avrà finito, rilasceranno le proprie istanze di R1 e R2 sbloccando allora P1 e P3.

Un ciclo non è quindi automaticamente segnale di presenza di un deadlock, soprattutto se le risorse coinvolte sono con multiple istanze.

COME RICONOSCERE ALLORA UN DEADLOCK
Concludendo possiamo dire che se il grafo non contiene cicli allora non c'è deadlock.
Se il grafo contiene un ciclo, se esiste una sola istanza per ciascuna risorsa contenuta nel ciclo, allora c'è deadlock.
Altrimenti se esistono risorse con più istanze, c'è possibilità di deadlock ma non ne siamo sicuri.

INTRODUZIONE ALLA PREVENZIONE DEL DEADLOCK
Come abbiamo avuto modo di dire in precedenza, esistono tre diverse tecniche per gestire situazioni di deadlock:

• Prevenzione Si basa sull'eliminare a priori almeno una delle condizioni necessarie affinchè il deadlock possa verificarsi, e cioè mutua esclusioni, possesso e attesa, possibilità di prelazione.
• Avoidance In questo caso si lasciano le condizioni viste ma si cerca di prevenire che si verifichino; l'idea è che il sistema assegni le risorse ai processi in maniera tale che essa rimanga in uno stato sicuro.
• Detection/recovery Il sistema lascia evolvere i processi in modo completamente autonomo. Si hanno dei sistemi per scoprire il deadlock, e attuare quindi politiche per sbloccarlo.

[tags]Deadlock, Deadlock recovery, Deadlock Avoidance[/tags]