8. Deadlock

Un insieme di processi รจ in deadlock quando ogni processo รจ in attesa di un evento che puรฒ essere causato solo da un processo dello stesso insieme, dunque a sua volta in attesa. Vediamo ora le 4 condizioni necessarie per il verificarsi di un deadlock.

Condizioni necessarie per l'avvenimento di un deadlock

  1. Mutua esclusione: almeno una delle risorse deve essere non condivisibile. Per esempio, un processo richiede una risorsa ma questa รจ giร  utilizzata da un altro processo, quindi deve aspettare che si liberi.
  2. Hold and Wait: deve esserci almeno un processo nel gruppo che detiene una risorsa, ma รจ bloccato, in quanto necessita di almeno un'altra risorsa, detenuta da un altro processo.
  3. No pre-emption: le risorse possono essere rilasciate solo dopo il loro utilizzo, la possessione di una risorsa non puรฒ essere rescissa forzatamente.
  4. Attesa circolare: devono esistere N processi in attesa del rilascio delle risorse tali che P0 attenda P1, P1 attenda P2,...,Pnโˆ’1 attenda Pn.

Vediamo ora un modo per visualizzare graficamente l'eventuale avvenimento di deadlock.

Modello Astratto (RAG)

Un Resource Allocation Graph (in breve RAG) รจ un modello astratto per la determinazione e la rappresentazione di eventuali situazioni di deadlock. Nello specifico, il RAG รจ un grafo G(V,E) dove:

Esempio 1

RAG-1.png700

In questo esempio P1 prima richiede le due risorse disponibili in R1, le ottiene e infine smette di usarne una.

Come capiamo se si verificherร  un deadlock?

Se il RAG non contiene cicli, non sono presenti deadlock. Se presenta cicli, possiamo distinguere due casi:

Esempio 2

RAG-2.png700

4 modi per gestire un deadlock

Esaminano ora le principali soluzioni per la prevenzione, rilevazione e correzione dei deadlock.

Deadlock Prevention (prevenzione statica)

L'obiettivo รจ impedire che si verifichi una delle 4 condizioni che devono essere vere contemporaneamente affinchรจ si verifichi un deadlock.

Analizziamo quindi una ad una le 4 condizioni e cerchiamo una soluzione.

Mutua esclusione

รˆ impossbile impedire totalmente la mutua esclusione per alcuni tipi di risorse

Hold and wait

Soluzioni
Problemi

No pre-emption

Soluzioni
Problemi

Attesa circolare

Soluzioni
Problemi

Svantaggi

In generale queste soluzioni sono molto costose e possono degradare notevolmente le prestazioni.

Deadlock Avoidance (prevenzione dinamica)

La prevenzione statica ha lo svantaggio di diminuire l'utilizzo delle risorse quindi il throughput del sistema. Gli algoritmi di prevenzione dinamica tendono a migliorare le prestazioni, ma necessitano delle informazioni sulle richieste che ogni processo potrebbe fare.
Nello specifico, per ogni processo รจ necessario sapere:

Questi algoritmi si basano sul mantenere uno stato safe del sistema. Questo avviene se esiste una sequenza safe, ovvero, se usando le risorse disponibili, il sistema puรฒ allocare risorse ad ogni processo, in qualche ordine, in modo che ciascun di essi possa terminare la sua esecuzione.
Piรน precisamente, una sequenza di processi (P1,...,PN) รจ safe se, per ogni Pi, le sue richieste possono essere soddisfatte utilizzando le risorse disponibili o quelle detenute da tutti i Pj con j<i, cioรจ aspettando che tutti i processi precedenti a Pi terminino e rilasciono le risorse detenute. Se tale sequenza non esiste, il sistema รจ detto in stato unsafe, ovvero potrebbe andare in deadlock, ma non necessariamente.

Dunque riassumendo, l'idea รจ utilizzare algoritmi che lasciano il sistema sempre in uno stato safe. Allโ€™inizio il sistema รจ in uno stato safe. Ogni volta che P richiede R, R viene assegnata a P se si rimane in uno stato safe.

Svantaggi

Lโ€™utilizzo delle risorse รจ minore rispetto al caso in cui non uso tecniche di prevenzione dinamica.

Tra gli algoritmi che si basano sul mantenere uno stato safe abbiamo due principali alternative:

Vediamoli ora nel dettaglio.

Algoritmo Resource Allocation Graph (RAG)

Funziona solo con un'unica istanza per risorsa. Si rappresentano processi e risorse come nodi di un grafo orientato. Gli archi assumono significati diversi a seconda del tipo: Rโ†’P indica che la risorsa R รจ allocata a P, Pโ†’R indica che il processo P richiede la risorsa R, esiste un terzo tipo di freccia Pโˆ’โˆ’>R detta claim edge che indica che P potrebbe richiedere R. Durante l'esecuzione i claim edge si trasformano in allocazioni se la richiesta รจ soddisfatta. Richieste che causano un ciclo nel grafo non vengono accettate, in quanto causano uno stato unsafe. Visto che รจ necessario un algoritmo per la rilevazione dei cicli, questo algoritmo ha complessitร  O(n2), dove n รจ il numero di processi.

Esempio

RAG-3.png700

Algoritmo del banchiere

Come il RAG, ha bisogno di sapere il numero massimo di istanze che ogni processo potrebbe richiedere per ogni risorsa, ma funziona con qualsiasi numero di istanze, anche se รจ meno efficiente del RAG. Si basa sul mantenere delle strutture dati (matrici) con le informazioni sulle risorse richieste e allocate da ogni processo e sulle risorse di sistema disponibili. Ad ogni richiesta, si stabilisce se questa รจ possibile da soddisfare restando in uno stato safe, simulando l'assegnazione delle risorse. รˆ costituito dunque da due algoritmi, l'algoritmo di allocazione e l'algoritmo di verifica dello stato.

Vediamo ora quali strutture dati vengono utilizzate:

int n; //i processi disponibili
int available[m]; // numero di istanze di R_i disponibili
int max[n][m]; // matrice delle richieste di risorse, le righe rappresentano i processi
			   // le colonne le risorse
int alloc[n][m]; // matrice di allocazione corrente
int need[n][m]; // matrice bisogno rimanente, ovvero need[i][j] = max[i][j]-alloc[i][j]

Vediamo ora una possibile implementazione dell'algoritmo di allocazione.

// request_vector รจ un vettore contenente le richieste del processo P_i
// ossia la colonna di max[i] dove i รจ il processo P_i
void request (int req_vec []) {
//se almeno un elemento รจ maggiore lancia un errore
	if (req_vec [] > need[i][])
		error(); //il processo vuole usare di piรน del massimo dichiarato
	if (req_vec[] > available[])
		wait(); //se non ci sono abbastanza risorse per soddisfare il processo, aspetto

// simuliamo l'allocazione
available[] = available[] - req_vec[]; //risorse disponibili -= risorse richieste
alloc[i][] = alloc[] + req_vec[]; //risorse allocate += risorse richieste
need[i][] = need[i][] - req_vec[]; //risorse di cui necessito -= risorse richieste

if(!state_safe()) { /* se non รจ safe, ripristino il vecchio stato */
	//rollback
	available[] = available[] + req_vec[];
	alloc[i][] = alloc[] - req_vec[]; 
	need[i][] = need[i][] + req_vec[];
	wait();
}

Vediamo ora una possibile implementazione dell'algoritmo di verifica dello stato.

//ritorno true se lo stato รจ safe, false se non รจ safe
//Complessitร : O(m*n^2)
boolean state_safe() {
	//vettore locale uguale ad available[]
	int work[m] = available[];
	boolean finish[n] = (FALSE, ..., FALSE);
	int i;
	while(finish != (TRUE, ..., TRUE)) {
		/* cerca P_i che NON abbia terminato e che possa completare con le risorse disponibili in work. L'ordine non ha importanza. Se piรน processi possono eseguire, ne posso scegliere uno a caso, gli altri eseguiranno dopo, visto che le risorse possono solo aumentare. */
		/* Nello specifico, per ogni processo si controlla se ci sono abbastanza risorse disponibili per soddisfarlo. Se รจ cosรฌ, si esce dal for e lo si soddisfa. Se non riesco a soddisfare tutti i processi ritornerรฒ false. */
		for(i = 0; (i < n) && (finish[i] || need[i][] > work[]); i++);
		if(i == n)
			return FALSE; /* non ho trovato una sequenza safe */
		else {
			work[] = work[] + alloc[i][];
			finish[i] = TRUE;
		}
	}
	return TRUE;
}

Il problema principale dell'algoritmo del banchiere รจ la sua inefficienza, il semplice controllo dello stato safe/unsafe ha costo O(n2โ‹…m), con n numero di processi e m tipi di risorsa.

Esempio

Vediamo ora un esempio sul funzionamente dell'algoritmo del banchiere.
Abbiamo 5 processi: P0,P1,P2,P3,P4 e 3 risorse:

Inoltre, questa รจ la situazione al tempo t0:

Questa รจ la tabella dell'allocazione delle risorse, ossia nell'istante t0 quante risorse sono riusciti a prendere i 5 processi.

Allocation A B C
P0 0 1 0
P1 2 0 0
P2 3 0 2
P3 2 1 1
P4 0 0 2

Questa รจ la tabella delle risorse totali che ogni processo necessita di usare.

Max A B C
P0 7 5 3
P1 3 2 2
P2 9 0 2
P3 2 2 2
P4 4 3 3

Calcoliamo ora quante istanze delle risorse A, B, C sono ancora disponibili al tempo t0:

Vediamo A:

A
P0 0
P1 2
P2 3
P3 2
P4 0
Istanze totali di A usate: 7
Istanze di A ancora usabili : 10โˆ’7=3

Vediamo B:

B
P0 1
P1 0
P2 0
P3 1
P4 0
Istanze totali di B usate: 2
Istanze di B ancora usabili : 5โˆ’2=3

Vediamo C:

C
P0 0
P1 0
P2 2
P3 1
P4 2
Istanze totali di C usate: 5
Istanze di C ancora usabili : 7โˆ’5=2

Dunque al tempo t0 le istanze disponibili sono le seguenti:

Available A B C
3 3 2

Infine, calcoliamo quante risorse ogni processo necessita ancora, facendo MAX[] - ALLOCATION[], ossia risorse totali di cui necessito - risorse che sono giร  riuscito ad allocare.

Need A B C
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1

Detto questo, diamo per vero che al tempo T0 il sistema sia in stato safe, e <P1 , P3 , P4 , P2 , P0> รจ una sequenza safe. Potremmo tranquillamente calcolarcela con l'algoritmo che vediamo tra poco, ma te lo lascio come esercizio per casa ๐Ÿ˜ณ.

Ipotizziamo ora che P1 richieda (1,0,2) al tempo t1.

Verifichiamo prima di tutto se P1 puรฒ farlo.

richiesta diย P1โ‰คAvailable?โŸบ(1,0,2)โ‰ค(3,3,2)โ‡’OK

Dunque P1 puรฒ richiedere la risorsa. Aggiorniamo quindi le tabelle nelle righe relative a P1.

Allocation A B C
P0 0 1 0
P1 2+1=3 0 0+2=2
P2 3 0 2
P3 2 1 1
P4 0 0 2
Available A B C
3โˆ’1=2 3 2โˆ’2=0
Need A B C
P0 7 4 3
P1 1โˆ’1=0 2 2โˆ’2=0
P2 6 0 0
P3 0 1 1
P4 4 3 1

Non ci resta che eseguire l'algoritmo (la funzione request() sopra) e verificare se si presenterร  un deadlock.
Abbiamo innanzitutto che work[] = {2,3,0}.
Ora parte il for(), che per ogni processo controlla se ci sono abbastanza risorse disponibili per soddisfarlo.
i=0 finish=FALSE, need[0] = (7,4,3) > work โŒ

Dunque P0 non puรฒ allocare le risorse.

i=1 finish=FALSE, need[1] = (0,2,0) <= work โœ…

Quindi P1 puรฒ allocare le risorse.
Quindi si fa partire per primo P1, e quando avrร  finito, le risorse disponibili saranno (2, 3, 0) + (3, 0, 2), ossia le risorse giร  disponibili + quelle che aveva giร  allocato P1. Cioรจ, si assume ottimisticamente che P1 esegua fino al termine e che quindi restituisca le sue risorse.
work = work + (3,0,2) = (5,3,2)
finish[1] = TRUE

A questo punto il for riinizia dall'inizio e ripassa tutti i processi.
i=0 finish=FALSE, need[0]=(7,4,3) > work โŒ
i=1 finish=TRUE
i=2 finish=FALSE, need[2]=(6,0,0) > work โŒ
i=3 finish=FALSE, need[3]=(0,1,1) <= work โœ…

Quindi P3 puรฒ allocare le risorse. Quando avrร  finito, le risorse che saranno disponibili sono (7,4,3). Infatti:
work = work + (2,1,1) = (7,4,3)
finish[3] = TRUE

A questo punto il for riinizia dall'inizio e ripassa tutti i processi.
i=0 finish=FALSE, need[0]=(7,4,3) <= work โœ…

Quindi P0 puรฒ allocare le risorse. Quando avrร  finito, le risorse che saranno disponibili sono (7,5,3). Infatti:
work = work + (0,1,0) = (7,5,3)
finish[0] = TRUE

A questo punto il for riinizia dall'inizio e ripassa tutti i processi.
i=0 finish=TRUE
i=1 finish=TRUE
i=2 finish=FALSE, need[2]=(6,0,0) <= work โœ…

Quindi P2 puรฒ allocare le risorse. Quando avrร  finito, le risorse che saranno disponibili sono (10,5,5). Infatti:
work = work + (3,0,2) = (10,5,5)
finish[2] = TRUE

A questo punto il for riinizia dall'inizio e ripassa tutti i processi.
i=0 finish=TRUE
i=1 finish=TRUE
i=2 finish=TRUE
i=3 finish=TRUE
i=4 finish=FALSE, need[4]=(4,3,1) <= work โœ…

Quindi P4 puรฒ allocare le risorse. Quando avrร  finito, le risorse che saranno disponibili sono (10,5,7). Infatti:
work = work + (0,0,2) = (10,5,7)
finish[4] = TRUE

Tutti i processi sono riusciti a prendere le risorse di cui necessitavano e la sequenza safe trovata รจ <P1 , P3 , P0 , P2 , P4>.

Ipotizziamo ora che P0 richieda (0,2,0) al tempo t2.

Verifichiamo prima di tutto se P0 puรฒ farlo.

richiesta diย P0โ‰คAvailable?โŸบ(0,2,0)โ‰ค(2,3,0)โ‡’OK

Dunque P0 puรฒ richiedere la risorsa. Aggiorniamo quindi le tabelle nelle righe relative a P0.

Allocation A B C
P0 0 1+2=3 0
P1 3 0 2
P2 3 0 2
P3 2 1 1
P4 0 0 2
Available A B C
2 3โˆ’2=1 0
Need A B C
P0 7 4โˆ’2=2 3
P1 0 2 0
P2 6 0 0
P3 0 1 1
P4 4 3 1

Non ci resta che eseguire l'algoritmo (la funzione request() sopra) e verificare se si presenterร  un deadlock.
Abbiamo innanzitutto che work[] = {2,1,0}.
Ora parte il for(), che per ogni processo controlla se ci sono abbastanza risorse disponibili per soddisfarlo.
i=0 finish=FALSE, need[0] = (7,2,3) > work โŒ
i=1 finish=FALSE, need[1] = (0,2,0) > work โŒ
i=2 finish=FALSE, need[2] = (6,0,0) > work โŒ
i=3 finish=FALSE, need[3] = (0,1,1) > work โŒ
i=4 finish=FALSE, need[4] = (4,3,1) > work โŒ

Quindi nessun processo riuscirebbe piรน ad allocare risorse, siamo in uno stato unsafe!

Deadlock Detection and Recovery (algoritmi di rilevamento del deadlock e di ripristino)

Entrambi i metodi di prevenzione visti sopra tendono a ridurre la disponibilitร  delle risorse per la prevenzione di un problema che si presenta raramente. Si puรฒ optare invece per degli algoritmi di rilevamento del deadlock e di ripristino, che sebbene siano svantaggiati dal costo di ripristino, non richiedono conoscenze a priori sulle risorse e le richieste.
Di seguito due algoritmi di rilevamento, ciascuno derivato da uno degli algoritmi di avoidance.

Rilevazione e ripristino con RAG (Algoritmo Wait-for)

Basato sul RAG, funziona solo con un'unica istanza per risorsa. Viene mantenuto in memoria un grafo d'attesa (da qui il nome wait-for), cioรจ una struttura dati creata appositamente per questa funzione, ottenuta eliminando i nodi risorsa dal RAG e collassando i vertici. Nel grafo cosรฌ ottenuto un arco Piโ†’Pj indica che Pi รจ in attesa di una risorsa detenuta da Pj . Questo si ha solo se nel RAG era presenta una risorsa Rx tale che Piโ†’Rx e Rxโ†’Pj. Periodicamente viene invocato un algoritmo O(n2) per stabilire l'esistenza di un ciclo, che indica un deadlock in corso e se viene trovato viene effettuata la fase di ripristino.

AlgoritmoWait-For.png700

Quindi i vantaggi sono che la conoscenza anticipata delle richieste non รจ piรน necessaria e le risorse non vengono sprecate per prevenire un deadlock. Ovviamente lo svantaggio รจ il costo del recovery.

Algoritmo di rilevamento del banchiere

Utilizza una struttura dati molto simile all'omonimo algoritmo di deadlock avoidance, funziona quindi con qualsiasi numero di istanze. Si basa sul verificare in tempo O(n2m) che una serie di richieste non causi un deadlock. Rispetto all'algoritmo originale non richiede di imporre un massimo sulle richieste.

Vediamo ora quali strutture dati vengono utilizzate:

int n; //i processi disponibili
int available[m]; // numero di istanze di R_i disponibili
int alloc[n][m]; // matrice di allocazione corrente
int need[n][m]; // matrice delle richieste che devono ancora essere soddisfatte

Vediamo ora una possibile implementazione dell'algoritmo.

//ritorno true se lo stato รจ safe, false se non รจ safe
//Complessitร : O(m*n^2)
boolean state_safe() {
	int work[m] = available[m];
	bool finish[] = (FALSE,...,FALSE);
	bool found = TRUE; //per vedere se faccio un for intero senza mai trovare un processo che puรฒ eseguire
	while (found) {
		found = FALSE;
		for (i=0; i<n && !found; i++) {
			/* cerca un Pi con richiesta soddisfacibile */
			if (!finish[i] && need[i][] <= work[]){
				/* assume ottimisticamente che Pi esegua fino al termine
				e che quindi restituisca le risorse. Se non รจ cosรฌ,
				il possibile deadlock verrร  evidenziato alla prossima
				esecuzione dell'algoritmo. */
				work[] = work[] + alloc[i][];
				finish[i]=TRUE;
				found=TRUE;
			}
		}
	} /* se finish[i]=FALSE per un qualsiasi i, Pi รจ in deadlock */
}

Sรฌ, รจ letteralmente identico a state_safe() dell'algoritmo del banchiere in prevenzione dinamica, solo che si usa la variabile found al posto di if(i == n) e il for non riparte ogni volta ma va avanti. La vera differenza perรฒ รจ che quell'algoritmo, per ogni richiesta di risorsa da parte di un processo, prova ad effettuare l'allocazione e in caso di deadlock la annulla. Qui le allocazioni non hanno un controllo, ma semplicemente ogni tanto si fa partire la funzione state_safe() e se c'รจ un deadlock si fa un ripristino.

Esempio

Vediamo ora un esempio sul funzionamento di questo algoritmo.
Abbiamo 5 processi: P0,P1,P2,P3,P4 e 3 risorse:

Inoltre, questa รจ la situazione al tempo t0:

Questa รจ la tabella dell'allocazione delle risorse, ossia nell'istante t0 quante risorse sono riusciti a prendere i 5 processi.

Allocation A B C
P0 0 1 0
P1 2 0 0
P2 3 0 3
P3 2 1 1
P4 0 0 2

Questa รจ la tabella delle risorse che ogni processo necessita ancora.

Need A B C
P0 0 0 0
P1 2 0 2
P2 0 0 0
P3 1 0 0
P4 0 0 2

Calcoliamo ora quante istanze delle risorse A, B, C sono ancora disponibili al tempo t0:

Vediamo A:

A
P0 0
P1 2
P2 3
P3 2
P4 0
Istanze totali di A usate: 7
Istanze di A ancora usabili : 7โˆ’7=0

Vediamo B:

B
P0 1
P1 0
P2 0
P3 1
P4 0
Istanze totali di B usate: 2
Istanze di B ancora usabili : 2โˆ’2=0

Vediamo C:

C
P0 0
P1 0
P2 3
P3 1
P4 2
Istanze totali di C usate: 6
Istanze di C ancora usabili : 6โˆ’6=0

Dunque al tempo t0 le istanze disponibili sono le seguenti:

Available A B C
0 0 0

Orco! Non ci sono risorse disponibili, ma questo non vuol dire che sia un deadlock!

Detto questo, non ci resta che eseguire l'algoritmo (la funzione state_safe() sopra) e verificare se siamo in una situazione di deadlock.
Abbiamo innanzitutto che work[] = {0,0,0}.
Ora parte il for(), che per ogni processo controlla se ci sono abbastanza risorse disponibili per soddisfarlo.
i=0 finish=FALSE, need[0] = (0,0,0) <= work โœ…

Quindi P0 puรฒ allocare le risorse.
work = work + (0,1,0) = (0,1,0)
finish[0] = TRUE

A questo punto il for continua.
i=1 finish=FALSE, need[1]=(2,0,2) > work โŒ
i=2 finish=FALSE, need[2] = (0,0,0) <= work โœ…

Quindi P2 puรฒ allocare le risorse.
work = work + (3,0,3) = (3,1,3)
finish[2] = TRUE

A questo punto il for continua.
i=3 finish=FALSE, need[3]=(1,0,0) <= work โœ…

Quindi P3 puรฒ allocare le risorse.
work = work + (2,1,1) = (5,2,4)
finish[3] = TRUE

A questo punto il for continua.
i=4 finish=FALSE, need[4]=(0,0,2) <= work โœ…

Quindi P4 puรฒ allocare le risorse.
work = work + (0,0,2) = (5,2,6)
finish[4] = TRUE

A questo punto il for รจ finito ma siccome almeno un processo รจ riuscito ad allocare le risorse, found รจ stato impostato a true e il for riparte dall'inizio.
i=0 finish=TRUE
i=1 finish=FALSE, need[1]=(2,0,2) <= work โœ…

Quindi P1 puรฒ allocare le risorse.
work = work + (2,0,0) = (7,2,6)
finish[1] = TRUE

A questo punto il for continua.
i=2 finish=TRUE
i=3 finish=TRUE
i=4 finish=TRUE

A questo punto il for รจ finito ma siccome almeno un processo รจ riuscito ad allocare le risorse, found รจ stato impostato a true e il for riparte dall'inizio.
i=0 finish=TRUE
i=1 finish=TRUE
i=2 finish=TRUE
i=3 finish=TRUE
i=4 finish=TRUE

Il for รจ terminato nuovamente, nessuno ha allocato risorse quindi found รจ rimasto a false. Dunque si esce dal while e si verifica se finish[i]=true per ogni i.
La risposta รจ si, tutti i processi sono riusciti a prendere le risorse di cui necessitavano e la sequenza safe trovata รจ <P0 , P2 , P3 , P4 , P1>.

Vediamo ora un esempio in cui lo stato non รจ safe e bisogna ripristinare tutto.
Supponiamo che P2 avesse richiesto unโ€™ulteriore istanza della risorsa C. La nuova tabella delle richieste di risorse รจ la seguente:

Need A B C
P0 0 0 0
P1 2 0 2
P2 0 0 1
P3 1 0 0
P4 0 0 2

Non ci resta quindi che eseguire l'algoritmo (la funzione state_safe() sopra) e verificare se siamo in una situazione di deadlock.
Abbiamo innanzitutto che work[] = {0,0,0}.
Ora parte il for(), che per ogni processo controlla se ci sono abbastanza risorse disponibili per soddisfarlo.
i=0 finish=FALSE, need[0] = (0,0,0) <= work โœ…

Quindi P0 puรฒ allocare le risorse.
work = work + (0,1,0) = (0,1,0)
finish[0] = TRUE

A questo punto il for continua.
i=1 finish=FALSE, need[1]=(2,0,2) > work โŒ
i=2 finish=FALSE, need[2]=(0,0,1) > work โŒ
i=3 finish=FALSE, need[3]=(1,0,0) > work โŒ
i=4 finish=FALSE, need[4]=(0,0,2) > work โŒ

A questo punto il for รจ finito ma siccome almeno un processo รจ riuscito ad allocare le risorse, found รจ stato impostato a true e il for riparte dall'inizio.
i=0 finish=TRUE
i=1 finish=FALSE, need[1]=(2,0,2) > work โŒ
i=2 finish=FALSE, need[2]=(0,0,1) > work โŒ
i=3 finish=FALSE, need[3]=(1,0,0) > work โŒ
i=4 finish=FALSE, need[4]=(0,0,2) > work โŒ

Il for รจ terminato nuovamente, nessuno ha allocato risorse quindi found รจ rimasto a false. Dunque si esce dal while e si verifica se finish[i]=true per ogni i.
La risposta รจ no, P1 , P2 , P3 , P4 non riescono a prendere le risorse di cui necessitano, dunque P1 , P2 , P3 , P4 formano un deadlock.

Dunque, abbiamo detto prima che "ogni tanto" si fa partire l'algoritmo visto sopra. Ma a quanto corrisponde quel "ogni tanto"?
La frequenza di invocazione di un algoritmo di rilevamento dipende dalla frequenza con cui si verificano deadlock nel sistema. Generalmente vengono invocati ogni N cicli, o quando l'utilizzo della CPU scende sotto una certa soglia (sintomo di deadlock). Invocarli ad ogni richiesta di risorse รจ la scelta piรน sicura, ma anche la piรน costosa.

Detto questo, come ripristiamo il sistema ad uno stato safe?
Generalmente si opta per la gestione automatica da parte del sistema, che puรฒ intervenire in due modi: uccidendo tutti processi coinvolti o riprendendosi le risorse contese. Nel primo caso, l'uccisione di tutti i processi, si ha un elevato costo per il sistema e, nel caso i processi stessero interagendo con periferiche, si rischiano incosistenze. Inoltre tutti i processi dovrebbero ripartire, perdendo cosรฌ il lavoro svolto. Spesso quindi si sceglie un'uccisione selettiva, ma in tal caso รจ necessaria una qualche politica per stabilire un ordine di prioritร  per la sequenza di uccisione. Inoltre, dopo ogni uccisione, รจ necessario invocare nuovamente l'algoritmo di rilevamento per stabilire se c'รจ ancora un deadlock. Se si sceglie la prelazione delle risorse, si deve anche in questo caso definire una politica per stabilire a chi vengono tolte le risorse ed in quale ordine. Nella situazione peggiore si deve effettuare un total rollback (cioรจ riparto da zero!). Segue che le operazioni di rollback, ovvero di ripristino ad uno stato passato per un processo, sono particolarmente costose ed esiste la possibilitร  di starvation.

Conclusioni

Abbiamo capito che ognuno dei 4 approcci visti ha vantaggi e svantaggi. Dunque, come sempre si รจ soliti fare in queste situazioni, si puรฒ cercare una soluzione combinata. Si puรฒ quindi suddividere le risorse in classi (tipo risorse interne, memoria, risorse di processo e spazio di swap) e per ognuna di esse scegliere l'algoritmo piรน appropriato.
C'รจ anche una soluzione molto piรน semplice, usata per esempio in UNIX, ossia il complesso algoritmo dello struzzo. Semplicemente si nasconde la testa sotto la sabbia e si fa finta che i deadlock non si possano mai verificare.