Introduzione
Metodi per risolvere o evitare il deadlock
Deadlock prevention
Deadlock avoidance
Deadlock detection e recovery
Approccio combinato al deadlock
 
 

Il deadlock nasce quando alcuni membri di un gruppo di processi che detengono risorse sono bloccati indefinitamente nell'accesso ad altre risorse possedute da altri processi dello stesso gruppo.

ESEMPIO
Consideriamo un incrocio fra 2 strade, senza nessuna indicazione di precedenza, a cui si presentano contemporaneamente 4 auto. La zona centrale dell'incrocio e' divisibile in 4 settori (risorse) "desiderati" dalle rispettive auto. Abbiamo 3 possibilita' per evitare questa situazione, oppure per risolverla quando si verifica:

1. si mette un semaforo
2. si inserisce almeno un diritto di precedenza (e non piu' di 3)
3. non si fa niente: le 4 auto passano contemporaneamente e si fermano dopo avere occupato il centro strada, perche' nessuna puo' procedere. Si decide di tornare indietro un po' e riprovare, oppure arriva il carro attrezzi.

Non bisogna confondere il deadlock con la starvation. Il deadlock e' irrisolvibile quando si verifica, senza un intervento di controllo esterno. La starvation e' una situazione di stallo, da cui si potrebbe "prima o poi" uscire naturalmente. Un esempio e' una strada che si immette in un'altra, dovendo dare la precedenza. Se continuano a passare aurto, una macchina che si deve immettere non puo' farlo, per un tempo massimo non definibile a priori. Si tratta normalmente di un problema di schedulazione, ma puo' anche derivare da un errato controllo del deadlock. Ad esempio, il secondo metodo (della lista precedente) per evitare il deadlock puo' portare a starvation.

Esempi di possibili situazioni di deadlock:

• Spooling (saturazione area disco)
• Creazione di processi (saturazione della process table)
• Apertura di file (saturazione buffer di memoria o tavole dei file)
• Accesso esclusivo a piu' files in mutua esclusione, o a device di I/O.

Il problema e' molto sentito nei sistemi transazionali, in cui si devono garantire accessi in mutua esclusione ad un insieme di risorse (dati su cui piu' processi lavorano).

Una risorsa puo' essere:

• Preemptible (interrompibile) o no. La CPU e' interrompibile, infatti si schedulano piu' processi. La memoria puo' esserlo, se si salva l'immagine su disco.
• Shared (condivisibile) o no. Il codice e' condivisibile, se rientrante.
• Una o piu' di ogni tipo. Ad esempio si possono avere piu' di una CPU (sistemi multiprocessore) o piu' terminali dello stesso tipo utilizzabili indifferentemente, quali stampanti.

Le risorse non sono solo oggetti fisici (CPU, stampanti ecc.) ma anche virtuali (messaggi di comunicazione, routine di sistema...).

Per definire meglio cos'e' un deadlock, consideriamo il Resourse Allocation Graph (RAG).

Le frecce indicano la necessita' di accedere ad una risorsa detenuta da un particolare processo. In figura 6.2,  il processo A possiede la risorsa 1 e aspetta la risorsa 2, mentre il processo B possiede la risorsa 2 e aspetta la 1. Ovviamente per essere un vero deadlock occorre che le risorse non siano ne' condivisibili ne' interrompibili. Inoltre si puo' parlare di RAG  solo se esiste una sola risorsa per ogni tipo. Nel RAG si possono omettere i nodi risorsa.
Piu' formalmente abbiamo le seguenti quattro

Condizioni di Coffman, Elphick e Shoshani (1971) per l'esistenza di deadlock:

1. Si considerano solo le risorse non condivisibili,
2. e non interrompibili.
3. I processi coinvolti in un deadlock possiedono gia' delle risorse e ne aspettano altre (wait-for condition).
4. I processi coinvolti in un deadlock (o parte di essi) sono in una catena circolare nel loro RAG (circular wait).

Nota 1
I processi individuati con le precedenti condizioni possono non essere tutti e soli quelli effettivamente bloccati nel deadlock.

Anche il processo C e' bloccato, ma se si impedisce il ciclo, si libera anche C.

Nota 2
Se di una risorsa esistono piu' istanze indifferenti, l'esistenza di un ciclo non e' piu' sufficiente per l'esistenza del deadlock. In questo caso, in effetti, occorre considerare una tabella anziche' un grafo.

Nota 3
In alcune transazioni ci possono essere richieste del tipo:

• desidero la risorsa 1 oppure la risorsa 2,
• desidero la risorsa 1 e la risorsa 2.

Modello di richieste AND/OR

Se il processo A desidera una risorsa posseduta da D oppure una risorsa posseduta da B, c'e' deadlock solo se A e' un knot. Un vertice V e' un knot se per qualunque nodo W, l'asserzione "W e' raggiungibile da V implica che V e' raggiungibile da W" e' vera.

Nota 3
Si parte sempre da una condizione supposta vera: prima o poi ogni processo rilascia tutte le risorse che possiede. Cioe' non si considerano ad esempio eventuali errori di programmazione per cui un programma va in loop e non termina mai.
 
 

Ci sono 3 approcci fondamentali, 2 per prevenire il deadlock, 1 per rilevarlo (e quindi romperlo) dopo che si e' verificato.

Prevention. Nell'esempio iniziale corrisponde al primo caso (semaforo). Ha gli stessi pregi e difetti del semaforo:

• Si stabiliscono delle condizioni di programmazione per cui non si arriva mai al deadlock, senza che sia necessario conoscere nulla di cio' che succede agli altri processi (si guarda solo il semaforo, indipendentemente dall'eventuale presenza di altre auto).
• Porta ad uno scarso utilizzo delle risorse (si sta fermi al semaforo rosso anche se dalle altre parti non ci sono auto in attesa).
• Avoidance. Si impongono condizioni piu' pesanti per evitare il deadlock. Corrisponde all'incrocio con diritto di precedenza: prima di passare occorre verificare se dalle altre direzioni arrivano auto, cioe' bisogna che il S.O. sia informato di cio' che stanno facendo i vari processi prima di dare il via libera).
• Detection e Recovery. Il deadlock puo' avvenire ma e' scoperto tramite controlli periodici.  Si rompe poi in qualche modo (vedere anche il protocollo di comunicazione Ethernet).

Si puo' anche evitare queste tecniche e ricorrere semplicemente all'uso di un time-out. Ogni processo puo' detenere un insieme di risorse solo per un certo tempo massimo, altrimente viene interrotto e le risorse recuperate (vedi deadlock recovery ). E' un metodo poco dispendioso ma molto "doloroso" se il tempo limite non e' calcolato correttamente.

1. Deadlock prevention (Indice)

Le prime proposte vengono da Havender (69) e si ottengono negando una alla volta le 4 ipotesi per l'esistenza del deadlock. In realta' se ne considerano solo 3, visto che non si puo' negare che ci siano risorse strettamente dedicate e non suddivise.

• Negazione della no-preemption. Se un processo richiede una risorsa R che e' posseduta da un altro processo bloccato in attesa di un altra risorsa, R puo' essere tolta al secondo processo e assegnata al primo. Viene poi ridata al secondo processo quando e' libera. Non sempre puo' essere applicato, o e' conveniente farlo: ad esempio per la memoria volatile si usa il salvataggio su disco dell'immagine e poi il suo ripristino, ma per la stampante occorre rifare la stampa dall'inizio.
  Svantaggi: sono possibili riinizializzazioni cicliche e starvation.
• Negazione della wait-for-condition. Occorre che un processo richieda tutte le risorse che gli servono allo stesso tempo. Se la richiesta puo' essere soddisfatta, le risorse sono assegnate, altrimenti si aspetta che lo siano. Si puo' modificare questo schema dicendo che un processo esegue diverse fasi di elaborazione (transazioni) in ciascuna delle quali chiede delle risorse che poi rilascia alla fine. Quindi e' necessario chiedere tutte insieme solo le risorse necessarie per la singola transazione.
  Svantaggi:scarsa utilizzazione delle risorse, necessita' di conoscere a priori le risorse occorrenti in ogni transazione, elevata possibilita' di starvation, se non corretto con aging.
• Negazione del circular waiting. Si puo' imporre un ordinamento delle risorse. Sia R={r1, r2, ..., rn} l'insieme delle risorse. Consideriamo F , funzione biunivoca   F: R-->N (ad esempio: F(reader) = 1, F(disk drive) = 5 , F(tape drive) = 7 , F(printer) = 12).
  Se ogni processo richiede le risorse (in ogni sua transazione) in ordine crescente rispetto al valore di F associato, non si verificano attese circolari.
  Supponiamo per assurdo che in queste condizioni si verifichi un ciclo. Allora esisterebbe una sequenza di processi {p1, p2, ..., pn} tale che ogni pi aspetta la risorsa ri assegnata al processo p((i mod n)+1). Per ipotesi abbiamo che F(ri) < F(r(( mod n)+1)). Di conseguenza F(r0) < F(r1) < F(r2) < ... F(rn) < F(r0) per cui dovrebbe essere F(r0) < F(r0).
  Svantaggi: F deve essere unica per tutto il sistema e per un tempo molto lungo. La richiesta di risorse potrebbe essere fatta molto prima di quanto effettivamente necessario. Nel caso di Data Base (ogni risorsa e' una parte del DB) e' impossibile ordinare le risorse.

2. Deadlock Avoidance (Indice)
Con il deadlock prevention si utilizzano poco le risorse. Conoscendo meglio le caratteristiche delle richieste, si potrebbero utilizzare meglio. Occorre considerare lo stato del sistema, formato da:

• le risorse complessive del sistema ancora disponibili,
• le risorse del sistema gia' allocate, e come,
• le possibili future richieste e rilasci dei vari processi.

Dichiarazione delle future richieste
Ogni processo dichiara preventivamente (anche per singola transazione) quale e' il massimo numero di risorse di cui avra' eventualmente bisogno per ogni tipo. Un algoritmo controlla che lo stato di esecuzione complessivo, man mano che si assegnano successivamente le risorse,  non porti mai a deadlock.
Uno stato e' detto safe se il sistema puo' allocare tutte le risorse che i processi possono ancora chiedere per terminare la loro transazione (in un qualche preciso ordine) evitando il deadlock, ossia se esiste un modo per terminare tutte le transazioni attive. Le possibili sequenze di assegnazione di risorse ai processi che portano alla terminazione sono dette safe sequence.
In uno stato S, una sequnza di processi P = <p1, p2, p3, ...., pn> e' detta safe se: per qualunque pi, le richieste che pi puo' ancora fare possono essere soddisfatte considerando le risorse disponibili e quelle possedute dai processi pj con j<i nello stato S.
In pratica, in uno stato safe S, il processo p1 puo' terminare utilizzando le risorse disponibili, quindi rilascia tutte le sue risorse. Il processo p2 puo' allora terminare usando le risorse disponibili in S piu' quelle gia' possedute (e rilasciate) da p1 e cosi' via. Possono esistere piu' safe sequence.
Lo stato iniziale (nessuna transazione attiva) e' safe. Muovendosi solo su stati safe (cioe' accettando di attribuire risorse solo se lo stato risultante e' ancora safe, sospendendo in attesa il processo richiedente altrimenti) non si va mai in uno stato di deadlock. Uno stato unsafe non evolve necessariamente in uno di deadlock, poiche' le richieste dichiarate di risorse sono massimali (potrebbero non essere effettivamente richieste tutte), ma non si puo' sapere a priori.
Il S.O. deve quindi deve evitare di entrare in uno stato unsafe.

Esempio
Supponiamo di avere 12 disk driver. Al tempo T0 rappresentato sotto, il sistema e' safe perche' esiste la sequenza safe <p1, p0, p2>.

processi      massima            risorse
              richiesta          allocate
  p0 . . . . . 10 . . . . . . . . 5
  p1 . . . . .  4 . . . . . . . . 2
  p2 . . . . .  9 . . . . . . . . 2

Se pero', successivamente,  p2 richiede 1 nuovo disco, e gli viene allocato, il sistema non e' piu' safe perche' p1 puo' terminare ma poi p0 e p2 rimangono bloccati.
L'algoritmo che consente di capire se uno stato e safe oppure no si chiama

Algoritmo del Banchiere
Struttura dati:
n               numero di processi del sistema
m               numero di tipi di risorse
available [m]   istanze disponibili di ogni risorsa
max[n,m]        massima richiesta per ogni processo
allocation[n,m] risorse allocate per processo
need[n,m]       risorse ancora richiedibili
                need[i,j]=max[i,j]-allocation[i.j]
req[n,m]        richieste considerate in un certo istante
                req[i,j]+allocation[i.j]<=max[i.j]
req(i)          array i-esimo (richieste di pi

Quando un processo pi effettua una richiesta req(i), l'algoritmo effettua i controlli:

1. se req(i) <= need(i)  --> passo 2, altrimenti errore.
2. se req(i) <= available  --> passo 3 altrimenti aspetta (liberazione di altre risorse).
3. si controlla se il nuovo stato, nel caso di attribuzione delle risorse richieste, e' safe.

Il nuovo stato sarebbe:
available = available - req
allocation (i)= allocation(i) + req(i)
need(i) = need(i) - req(i)
Se il nuovo stato e' safe, la richiesta e' soddisfatta, altrimenti il processo attende.

Sviluppo del punto 3

1. Siano work[m] e finish [n] due nuovi array definiti:
   work = available
   finish = false per qualunque componente.
2. Sia i tale che finish[i]=false and need(i)<=work.
   Se tale i non esiste --> passo 4.
   (X <= Y se e solo se per qualunque i: X[i] <= Y[i])
3. work = work + allocation(i)
   finish[i] = true
   --> passo 2
4. Se finish = true allora lo stato e' safe.

Si puo' dimostrare che l'ordine con cui sono trovati i valori di i che soddisfano il punto 2 non incide sull'esistenza di almeno una di tale sequenza (se ne esiste almeno una, la si trova).
Nota:
I processi sospesi devranno essere riconsiderati successivamente (pericolo di starvation).

ESEMPIO

n = 5   {p1, p2, p3, p4, p5}  processi
m = 3   {A, B, C} tale che |A| = 10  istanze
                           |B| = 5
                           |C| = 7
al tempo T0 lo stato e'

      allocation  max         available
      A B C       A B C       A B C
                              3 3 2
 p0   0 1 0       7 5 3
 p1   2 0 0       3 2 2
 p2   3 0 2       9 0 2
 p3   2 1 1       2 2 2
 p4   0 0 2       4 3 3

E' in uno stato safe.
safe sequence: <p1, p3, p4, p2, p0>
Sia req(1) = (1, 0, 2) la richiesta di p1 all'istante T1.
Se accettata il nuovo stato sarebbe:

      allocation  need         available
      A B C       A B C       A B C
                              2 3 0
 p0   0 1 0       7 4 3
 p1   3 0 2       0 2 0
 p2   3 0 2       6 0 0
 p3   2 1 1       0 1 1
 p4   0 0 2       4 3 1

E' ancora safe. Le possibili sequenze sono:
<p1, p3, p4, p2, p0> e <p1, p4, p3, p0, p2>
Invece la richiesta req(4) = (3, 3,0) porterebbe ad uno stato unsafe.

3. Deadlock Detection e Recovery ( Indice)
Il sistema puo' lasciare avvenire un deadlock, controllando periodicamante l'allocazione. Se e' avvenuto un deadlock si effettua un recovery.

• Mantenimento dell'allocazione e richieste di risorse,
• Algoritmo per verificare lo stato del sistema

Supponiamo di avere anche piu' istanze per ogni tipo di risorsa. La struttura da usare  e' simile a quella dell'algoritmo del banchiere, senza le caratteristiche relative alle richieste.

n               numero di processi del sistema
m               numero di tipi di risorse
available [m]   istanze disponibili di ogni risorsa
allocation[n,m] risorse allocate per processo
req[n,m]        richieste non ancora soddisfatte

Si controlla se c'e' una sequenza possibile di terminazione, supposto che nessun processo faccia altre richieste. Se non esiste una sequenza, c'e' un deadlock.

Algoritmo deadlock detection

1. work[m]  = available
   finish[i]  = if allocation(i)<>0 then false else true  (per qualunque i)
2. Si trova i tale che
   finish[i] = false and request(i) <= work
   altrimenti va al passo 4
3. work = work + allocation(i)
   finish [i] = true
   vai al passo 2
4. se finish[i] = false per qualche i, allora il sistema e' in deadlock e i processi con finish[i]=false appartengono ad un ciclo.

ESEMPIO

5 processi e 3 tipi di risorse {A, B, C} con |A|=7, |B|=2, |C|=6.

         allocation    request        available
        A  B  C        A  B  C        A  B  C
  p0    0  1  0        0  0  0        0  0  1
  p1    2  0  0        2  0  2
  p2    3  0  2        0  0  0
  p3    2  1  1        1  0  0
  p4    0  0  2        0  0  2

Il sistema non e' in deadlock. Se invece le richieste di p2 fossero <0, 0, 2>, si avrebbe un deadlock per p1, p2, p3 e p4.
In pratica, si fa una supposizione ottimistica, cioe' che dopo aver avuto le risorse desiderate le altre risorse verranno rilasciate. Se cio' non accade, o qualche processo fa altre richieste, potrebbe capitare successivamente un deadlock, che sara' scoperto nell'analisi successiva.

Attivazione algoritmo di deadlock detection

L'algoritmo e' attivabile seguendo vari criteri:

• Dopo ogni richiesta di risorsa
• Dopo ogni X unita' di tempo
• Ogni volta che un processo aspetta piu' di X unita' di tempo per avere una risorsa
• Quando la CPU rimane idle per piu' di una certa percentuale di tempo totale (meno significativo).

Recovery dal deadlock

Due possibilita':

1. uccidere 1 o piu' processi (ci puo' essere anche piu' di un ciclo).
2. interrompere e ritirare 1 o piu' risorse fra quelle impegnate.

Nota: quando una risorsa viene "tolta" ad un processo, puo' rimanere in uno stato intermedio non corretto. Ad esempio se un processo stava scrivendo su un file, ma non ha ancora completato la scrittura, possono rimanere delle incongruenze. Se si stava stampando un file, occorre resettare la printer ecc.

1. Uccisione di processi
I processi uccisi sono interrotti, le risorse che possedeva sono liberate (possibilita' di stati incorretti) e fatti successivamente ripartire (devono quindi rioccupare le risorse liberate prima). Si possono usare 2 metodi:

1. Uccidere tutti i processi in deadlock. Spesa elevata a causa del restart successivo dei processi e della perdita del calcolo parziale gia' eseguito,
2. Uccidere 1 solo processo alla volta finche' il deadlock non si risolve. Anche in questo caso c'e' un costo perche'  dopo l'eliminazione di un processo l'algoritmo di controllo deve essere rieseguito.

Nel secondo caso si puo' cercare di uccidere il processo che comporta la perdita minore e la massima "resa" per la risoluzione del deadlock. Non e' facile perche' vanno considerati diversi fattori:

• la priorita' del processo
• il tempo di esecuzione passato e futuro
• quante e di quale tipo sono le risorse gia' detenute dal processo?
• quante risorse puo' ancora chiedere?
• quanti processi saranno coinvolti nella terminazione (processi figli ecc.)?

2. Interruzione delle risorse
Ci sono 3 passi da compiere:

1. scelta della risorsa "vittima": minimizzazione del costo
2. rollback: cosa si fa del processo che deteneva quella risorsa? E' possibile ucciderlo e farlo ripartire da capo (equivale al punto 2 del caso precedente) oppure passare ad uno stato intermedio
3. evitare la starvation. Se il criterio di selezione della vittima e' quello dell'economia, capita facilmente che un processo sia sempre interrotto. Si puo' chiedere che il numero delle interruzione di un processo sia tenuto presente come costo (aging).

Rollback
Per effettuare il roll back di un processo ad uno stato di calcolo precedente (non all'istante iniziale) e' necessario effettuare un checkpoint, cioe' memorizzarne uno stato intermedio completo.
Il problema e' analogo per quanto riguarda una risorsa: quando una risorsa e' interrotta, ed attribuita ad un altro processo, deve essere riportato ad uno stato corretto (reset della printer, cancellazione di quanto scritto precedente in un file ecc.)
Di questo argomento si parlera' piu' in dettaglio nella sezione relativa alle transazioni distribuite.

Sono possibili anche approcci combinati. Ad esempio le risorse possono essere partizionate in classi ordinate gerarchicamente, e puo' essere utilizzato un metodo diverso akk'interno di ogni classe. Una possibile suddivisione:

• Risorse interne usate dal sistema: prevention con ordinamento delle risorse
• memoria centrale: prevention con preemption
• job resourse (device assegnabili): avoidance (le informazioni sull'utilizzo possono essere ottenute dal compilatore o da comandi aggiuntivi dell'utente).
• swappable store: detection con salvataggio intermedio nel backing store per ogni job. Normalmente si puo' conoscere il massimo spazio richiesto.

• I sistemi tendono a diventare distribuiti e a consentire operazioni parallele asincrone --> maggiore concorrenza di esecuzione --> maggiore richiesta di risorse --> maggiore possibilita' di deadlock.
• Si richiede maggiore dinamicita' nelle richieste di risorse, senza doverle dichiarare a priori.
• Tendenza da parte dei sistemi operativi a vedere i dati come risorse --> deadlock sui dati.
• Le risorse nel tempo possono variare, soprattutto nei sistemi distribuiti (elementi aggiunti o guasti). Cosa succede nei vari algoritmi visti prima?