Deadlock. Sistemi Operativi a.a. 2007-08 7.2 Deadlock Il problema del deadlock Modello del sistema...

DeadlockDeadlock

Sistemi Operativi a.a. 2007-087.2

DeadlockDeadlock

Il problema del deadlock

Modello del sistema

Caratterizzazione dei deadlock

Metodi per la gestione dei deadlock

Prevenire i deadlock

Evitare i deadlock

Rilevare i deadlock

Ripristino da situazioni di deadlock

Oggi c’è un traffico tremendo…


Il problema del deadlock Il problema del deadlock 1 1

In un ambiente multiprogrammato più processi possono entrare in competizione per ottenere un numero finito di risorse

DeadlockDeadlock o stallostallo insieme di processi bloccati: ciascun processo “possiede” una risorsa ed attende di acquisire una risorsa allocata ad un altro processo dell’insieme


Esempio 1 Esempio 1

Nel sistema sono presenti due stampanti

P1 e P2 si sono assicurati una stampante ciascuno ed entrambi richiedono anche l’altra

EsempioEsempio 22

Semafori A e B, inizializzati a 1:

P1 P2

wait (A); wait(B);

wait (B); wait(A);

Il problema del deadlock Il problema del deadlock 2 2


Esempio: attraversamento di un Esempio: attraversamento di un ponteponte

In ogni istante, sul ponte possono transitare autoveicoli solo in una direzione

Ciascuna sezione del ponte può essere immaginata come una risorsa

Se si verifica un deadlock, il recoveryrecovery può essere effettuato se un’auto torna indietro (rilascia la risorsa ed esegue un roll back)

In caso di deadlock, può essere necessario che più auto debbano tornare indietro

È possibile si verifichi starvation (attesa indefinita)


Esempio: leggi ferroviarie in Esempio: leggi ferroviarie in KansasKansas

Testo della legge approvata dalla legislazione del Kansas (inizi XX secolo):

““Quando due treni convergono ad un incrocio, Quando due treni convergono ad un incrocio, ambedue devono arrestarsi, e nessuno dei due ambedue devono arrestarsi, e nessuno dei due può ripartire prima che l’altro si sia mosso”può ripartire prima che l’altro si sia mosso”


Modello di sistemaModello di sistemaTipi di risorse R1, R2,…,Rm

Cicli di CPU, spazio di memoria, file, dispositivi di I/OCicli di CPU, spazio di memoria, file, dispositivi di I/O

Ciascun tipo di risorsa Ri ha Wi istanze

Il protocollo di accesso alle risorse da parte dei processi prevede…

RichiestaRichiesta se la richiesta non può essere soddisfatta immediatamente, causa diverso utilizzo della risorsa, il processo richiedente deve attendere fino all’acquisizione della risorsa

UtilizzoUtilizzo

RilascioRilascio

Richiesta/rilascio realizzati con apposite system call: request/ release request/ release device, open/close open/close file, allocate/free allocate/free memory o con wait/signal wait/signal su opportuni semafori


Caratterizzazione del deadlockCaratterizzazione del deadlockUna situazione di deadlock può verificarsi solo se valgono simultaneamente le seguenti condizioni:

Mutua esclusioneMutua esclusione: esiste almeno una risorsa non condivisibile, cioè un solo processo alla volta può usare quella risorsa

Possesso ed attesaPossesso ed attesa: un processo, che possiede almeno una risorsa, attende di acquisire ulteriori risorse possedute da altri processi

Impossibilità di prelazioneImpossibilità di prelazione: una risorsa può essere rilasciata dal processo che la possiede solo volontariamente, al termine della sua esecuzione

Attesa circolareAttesa circolare: esiste un insieme {P0,P1,…,Pn} di processi in attesa, tali che P0 è in attesa di una risorsa che è posseduta da P1, P1 è in attesa di una risorsa posseduta da P2,…, Pn–1 è in attesa di una risorsa posseduta da Pn, e Pn è in attesa di una risorsa posseduta da P0


Grafo di allocazione risorse Grafo di allocazione risorse 1 1

Un grafo è costituito da un insieme di vertici (o nodi) V variamente connessi per mezzo di un insieme di archi E

Nel grafo di allocazione risorsegrafo di allocazione risorse…

L’insieme V è partizionato in due sottoinsiemi:

P {P1,P2,…,Pn} è l’insieme costituito da tutti i processi del sistema

R {R1,R2,…,Rm} è l’insieme di tutti i tipi di risorse del sistema

Arco di richiestaArco di richiesta: Pi Rj

Arco di assegnazioneArco di assegnazione: Rj Pi


Processo

Tipo di risorsa con 4 istanze

Pi richiede un’istanza di Rj

Pi possiede un’istanza di Rj

Pi

Rj

Pi

Rj

Grafo di allocazione risorse Grafo di allocazione risorse 2 2

Arco di Arco di assegnazioneassegnazione

Arco di Arco di richiestarichiesta


Esempi di grafo di allocazione Esempi di grafo di allocazione risorse risorse 1 1

Grafo di allocazione risorse Grafo di allocazione risorse con deadlock


Esempi di grafo di allocazione Esempi di grafo di allocazione risorse risorse 2 2

Se il grafo non contiene ciclinon ci sono deadlock

Se il grafo contiene un cicloSe vi è una sola istanza

per ogni tipo di risorsa, allora si ha un deadlock

Se si hanno più istanze per tipo di risorsa, allora il deadlock è possibile (ma non certo)Grafo di allocazione risorse con un

ciclo, ma privo di deadlockIl ciclo c’è, ma il deadlock no…


Metodi per la gestione del deadlock Metodi per la gestione del deadlock 1 1

Assicurare che il sistema non entri maimai in uno stato di deadlock

Prevenire i deadlockPrevenire i deadlock: evitare che si verifichino contemporaneamente mutua esclusione, possesso e attesa, impossibilità di prelazione e attesa circolare basso utilizzo risorse e throughput ridotto

Evitare i deadlockEvitare i deadlock: evitare gli stati del sistema a partire dai quali si può evolvere verso il deadlock


Metodi per la gestione del deadlock Metodi per la gestione del deadlock 2 2

Permettere al sistema di entrare in uno stato di deadlock, quindi ripristinare il sistema

Determinare la presenza di un deadlock

Ripristinare il sistema da un deadlock

Ignorare il problema e fingere che i deadlock non avvengano mai nel sistema; impiegato dalla maggior parte dei SO, inclusi Windows e UNIX


Prevenire i deadlock Prevenire i deadlock 1 1

Limitare le modalità di richiesta/accesso delle/alle risorse

Mutua esclusioneMutua esclusione non è richiesta per risorse condivisibili; deve valere invece per risorse che non possono essere condivise, quindi non può essere prevenuta

Possesso e attesaPossesso e attesa occorre garantire che, quando un processo richiede una risorsa, non ne possieda altre

Richiedere ad un processo di stabilire ed allocare tutte le risorse necessarie prima che inizi l’esecuzione, o consentire la richiesta di risorse solo quando il processo non ne possiede alcuna

Basso impiego delle risorse; possibile l’attesa indefinita per processi con forti richieste di risorse


Impossibilità di prelazioneImpossibilità di prelazioneSe un processo, che possiede alcune risorse, richiede un’altra risorsa, che non gli può essere allocata immediatamente, allora rilascia tutte le risorse possedute

Le risorse rilasciate (prelazionate al processo) vengono aggiunte alla lista delle risorse che il processo sta attendendo

Il processo viene avviato nuovamente solo quando può ottenere sia le risorse precedentemente possedute sia quelle attualmente richieste

Alternativamente, le risorse possono essere assegnate al processo che le richiede, qualora siano attualmente possedute da un altro processo in attesa

Protocollo adatto per risorse il cui stato si può salvare e recuperare facilmente (registri, memoria; non per dispositivi di I/O)



Attesa circolareAttesa circolare si impone un ordinamento totale su tutti i tipi di risorsa, f :RN, e si pretende che ciascun processo richieda le risorse in ordine crescente

In alternativa, ogni processo, prima di richiedere un’istanza di Rj, deve rilasciare tutte le istanze di Ri, tale che f(Ri) f(Rj)

Supponiamo che, avendo imposto l’ordinamento suddetto, si verifichi comunque l’attesa circolare

Siano {P1,P2,…,Pn} i processi coinvolti nell’attesa circolare, dove Pi attende la risorsa Ri posseduta dal processo Pi+1

Poiché il processo Pi+1 possiede la risorsa Ri mentre richiede la risorsa Ri+1, i, vale la condizione

f(R1)f(R2)… f(Rn) f(R1)

assurdo!



Evitare i deadlockEvitare i deadlock

Presuppone che il sistema conosca a priori informazioni addizionali sulle richieste future dei processi

Il modello più semplice e utile richiede che ciascun processo dichiari il numero massimo di risorse di ciascun tipo di cui può usufruire

L’algoritmo di deadlockdeadlockavoidanceavoidance esamina dinamicamente lo stato di allocazione delle risorse per assicurare che non si possa verificare mai una condizione di attesa circolare

Lo stato di allocazione delle risorse è definito dal numero di risorse disponibili ed allocate, e dal massimo numero di richieste dei processi


Stato sicuro Stato sicuro 1 1

Quando un processo richiede una risorsa disponibile, il sistema deve decidere se l’allocazione immediata lasci il sistema in stato stato sicurosicuro

Il sistema si trova in uno stato sicuro se esiste una sequenza sicurasequenza sicura di esecuzione di tutti i processi

La sequenza <P1,P2,…,Pn > è sicura se, per ogni Pi, le risorse che Pi può ancora richiedere possono essergli allocate sfruttando le risorse disponibili, più le risorse possedute da tutti i Pj, con j i


Stato sicuro Stato sicuro 2 2Cioè…

Se le richieste di Pi non possono essere

soddisfatte immediatamente, allora Pi può

attendere finché tutti i Pj abbiano terminato

Quando Pj ha terminato, Pi può ottenere le

risorse richieste, eseguire i suoi compiti, restituire le risorse allocate e terminare

Quando Pi termina, Pi+1 può ottenere le risorse richieste, etc.


Se un processo richiede una risorsa disponibile, può dovere attendere scarso utilizzo delle risorse del sistema


Se un sistema è in stato sicuro

non si evolve verso il deadlock

Se un sistema è in stato non sicurosi può evolvere in deadlock

In stato non sicuro, il SO non può impedire ai processi di richiedere risorse la cui allocazione porta al deadlock

DeadlockDeadlockavoidanceavoidance

garantisce che un sistema non evolva mai verso uno stato non sicuro



EsempioEsempio

12 istanze di una risorsa complessivamente disponibili

Al tempo t0

Stato sicuro: <P1, P0, P2>

Se all’istante t1 il processo P2 richiede un’ulteriore unità, e questa gli viene assegnata, lo stato diventa non sicuro (solo P1 può terminare)

Processo

Richiesta max

Unità possedute

P010 5

P14 2

P29 2

3 unità 3 unità disponibdisponibiliili


Algoritmi per evitare i deadlockAlgoritmi per evitare i deadlock

Risorse ad istanza singola: utilizzo del grafo di allocazione risorse

Risorse ad istanza multipla: algoritmo del algoritmo del banchierebanchiere


Algoritmo con grafo di allocazione Algoritmo con grafo di allocazione risorse risorse 1 1

Un arco di reclamoarco di reclamo Pi Rj (rappresentato da una linea

tratteggiata) indica che il processo Pi può richiedere la

risorsa Rj in futuro

Un arco di reclamo viene convertito in un arco di richiestaarco di richiesta quando il processo Pi richiede effettivamente la risorsa Rj

Un arco di richiesta viene convertito in un arco di arco di assegnamentoassegnamento quando la risorsa viene allocata al processo

Quando una risorsa viene rilasciata da un processo, l’arco di assegnamento viene riconvertito in un arco di reclamo

Le risorse devono venir reclamate a prioria priori nel sistema

Prima che il processo Pi inizi l’esecuzione, tutti i suoi archi di reclamo devono essere già inseriti nel grafo di allocazione risorse


Supponiamo che il processo Pi richieda una risorsa Rj

La richiesta può essere accordata solo se la conversione dell’arco di richiesta in arco di assegnamento non provoca il formarsi di un ciclo nel grafo di allocazione delle risorse



Grafo di allocazione risorse

Stato non sicuro in un grafo di allocazione risorse



Algoritmo del banchiereAlgoritmo del banchiere

Permette di gestire istanze multiple di una risorsa (a differenza dell’algoritmo con grafo di allocazione risorse)

Ciascun processo deve dichiarare a priori il massimo impiego di risorse

Quando un processo richiede una risorsa può non venir servito istantaneamente

Quando ad un processo vengono allocate tutte le risorse deve restituirle in un tempo finito


Strutture dati per l’algoritmo del Strutture dati per l’algoritmo del banchierebanchiere

Sia n il numero dei processi presenti nel sistema ed m il numero dei tipi di risorse

AvailableAvailable : Vettore di lunghezza m; se Available[j]k, vi sono k istanze disponibili del tipo di risorsa Rj

MaxMax : matrice nm; se Max[i,j]k, il processo Pi può

richiedere al più k istanze del tipo di risorsa Rj

AllocationAllocation: matrice nm; se Allocation[i,j]k, a Pi

sono attualmente allocate k istanze di Rj

NeedNeed : matrice nm; se Need[i,j]k, Pi può richiedere

k ulteriori istanze di Rj per completare il proprio task

NeedNeed[[i,ji,j]]MaxMax[[i,ji,j]]AllocationAllocation[[i,ji,j]]


Algoritmo di verifica della Algoritmo di verifica della sicurezzasicurezza

1. Siano WorkWork e FinishFinish vettori di lunghezza m ed n, rispettivamente; si inizializzi

a) WorkAvailable

b) Finish[i]false, per i1,2,…,n

2. Si cerchi i tale che valgano contemporaneamente:

a) Finish[i]false

b) Needi Work

Se tale i non esiste, si esegua il passo 4.

3. WorkWorkAllocationi

Finish[i]truesi torni al passo 2.

4. Se Finish[i]true per ogni i, il sistema è in stato sicuro


Algoritmo di richiesta delle risorse per il Algoritmo di richiesta delle risorse per il processo processo PPii

Sia RequestRequestii il vettore delle richieste per il processo Pi

Se Requesti[j]k, il processo Pi richiede k istanze del tipo di risorsa Rj

1. Se Requesti Needi, si vada al passo 2.; altrimenti, si riporti una condizione di errore, poiché il processo ha ecceduto il massimo numero di richieste

2. Se RequestiAvailable, si vada al passo 3.; altrimenti Pi deve attendere, poiché le risorse non sono disponibili

3. Il sistema simula l’allocazione a Pi delle risorse richieste, modificando lo stato di allocazione come segue:

AvailableAvailableRequesti

Allocationi AllocationiRequesti

NeediNeediRequesti

Se lo stato è sicuro le risorse vengono definitivamente allocate a Pi

Se lo stato è non sicuro Pi deve attendere, e viene ripristinato il vecchio stato di allocazione delle risorse


Esempio di applicazione dell’algoritmo del Esempio di applicazione dell’algoritmo del banchierebanchiere

5 processi, da P0 a P4

3 tipi di risorse:

A (10 istanze), B (5 istanze) e C (7 istanze)

Istantanea al tempo T0:

AllocationAllocation MaxMax AvailableAvailableA B C A B C A B C

P0 0 1 0 7 5 3 3 3 2

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


Esempio (Cont.)Esempio (Cont.)

La matrice Need è definita come NeedMaxAllocation

NeedNeedA B C

P0 7 4 3

P1 1 2 2

P2 6 0 0

P3 0 1 1

P4 4 3 1

Il sistema è in stato sicuro, dato che la sequenza <P1,P3,P4,P2,P0> soddisfa i criteri di sicurezza


P1 richiede (1,0,2)

Verificare che RequestAvailable (cioè, (1,0,2) (3,3,2))

AllocationAllocation NeedNeed AvailableAvailableA B C A B C A B C

P0 0 1 0 7 4 3 2 3 0P1 3 0 2 0 2 0 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1P4 0 0 2 4 3 1

L’esecuzione dell’algoritmo di sicurezza mostra che la sequenza <P1,P3,P4,P0,P2> soddisfa i requisiti di sicurezza

La richiesta di P1 viene soddisfatta immediatamente

Può essere soddisfatta la richiesta di P4 per (3,3,0) ?

Può essere soddisfatta la richiesta di P0 per (0,2,0) ?

Esempio (Cont.)Esempio (Cont.)


Rilevamento del deadlockRilevamento del deadlock

Si permette al sistema di entrare in uno stato di deadlock

Per ripristinarne le funzionalità, sono necessari…

…un algoritmo di rilevamento del deadlock

e, successivamente, un algoritmo di ripristino dal deadlock

Costi aggiuntivi per la memorizzazione delle informazioni necessarie al ripristino


Istanza singola di ciascun tipo di Istanza singola di ciascun tipo di risorsarisorsa

Impiega un grafo di attesagrafo di attesa

I nodi rappresentano i processi

L’arco PiPj esiste se Pi è in attesa che Pj rilasci una risorsa che gli occorre

Periodicamente viene richiamato un algoritmo che verifica la presenza di cicli nel grafo

Un algoritmo per rilevare cicli in un grafo richiede un numero di operazioni dell’ordine di n2, dove n è il numero di vertici del grafo


Grafo di allocazione risorse e grafo di Grafo di allocazione risorse e grafo di attesaattesa

Grafo di allocazione risorseGrafo di attesa corrispondente

Un arco PiPj esiste nel grafo di attesa se e solo se il corrispondente grafo di allocazione risorse contiene i due archi PiRq , RqPj per

una qualche risorsa Rq


AvailableAvailable : vettore di lunghezza m, indica il numero di risorse disponibili di ciascun tipo

AllocationAllocation : matrice nm, definisce il numero di risorse di ciascun tipo attualmente allocate a ciascun processo

RequestRequest : matrice nm, indica la richiesta corrente di ciascun processo; se Request[i,j]k, il processo Pi richiede k istanze supplementari della risorsa Rj

L’algoritmo di rilevamento indaga su ogni possibile sequenza di assegnazione per i processi da completare

Più istanze per ciascun tipo di Più istanze per ciascun tipo di risorsarisorsa


Algoritmo di rilevamento Algoritmo di rilevamento 1 11. Siano WorkWork e FinishFinish due vettori di lunghezza m e n,

rispettivamente; inizialmente sia:

a) WorkAvailable

b) Per i1,2,…,n, se Allocationi0, Finish[i]false; altrimenti, Finish[i]true

2. Si trovi un indice i tale che valgano entrambe le condizioni:

a) Finish[i]false

b) Requesti Work

Se tale i non esiste, si vada al passo 4.

3. WorkWorkAllocationi

Finish[i]truesi vada al passo 2.

4. Se Finish[i]false, per qualche i, 1in, il sistema è in uno stato di deadlock; inoltre, se Finish[i]false, Pi è in deadlock


Algoritmo di rilevamento Algoritmo di rilevamento 2 2

NoteNote

L’algoritmo richiede un numero di operazioni dell’ordine di O(mn2) per determinare se il sistema è in uno stato di deadlock

Si ipotizza (ottimisticamente) che Pi non intenda richiedere altre risorse per completare il proprio compito, ma piuttosto che restituisca in tempo finito quelle che già possiede

Se ciò non accade, può verificarsi uno stallo, che verrà rilevato alla prossima verifica sul sistema


Esempio di applicazione dell’algoritmo di Esempio di applicazione dell’algoritmo di rilevamentorilevamento

5 processi, da P0 a P4

3 tipi di risorse: A (7 istanze), B (2 istanze) e C (6 istanze)

Istantanea al tempo T0:

AllocationAllocationRequestRequest AvailableAvailableA B C A B C A B C

P0 0 1 0 0 0 0 0 0 0

P1 2 0 0 2 0 2

P2 3 0 3 0 0 0

P3 2 1 1 1 0 0

P4 0 0 2 0 0 2

La sequenza <P0,P2,P3,P1,P4> conduce a

Finish[i]true per ogni i


Esempio Esempio (Cont.)(Cont.)P2 richiede un’istanza supplementare della risorsa C

RequestRequestA B C

P0 0 0 0

P1 2 0 1

P2 0 0 1

P3 1 0 0

P4 0 0 2

Qual è lo stato del sistema?

Può reclamare le risorse possedute dal processo P0, ma il numero di risorse disponibili non è sufficiente a soddisfare gli altri processi

deadlock: coinvolge i processi P1, P2, P3 e P4


Impiego dell’algoritmo di Impiego dell’algoritmo di rilevamentorilevamento

Quando e quanto spesso richiamare l’algoritmo di rilevamento dipende da:

Frequenza (presunta) con la quale si verificano i deadlockNumero di processi che vengono eventualmente influenzati dal deadlock (e sui quali occorre effettuare un roll back)

Almeno un processo per ciascun ciclo

Se l’algoritmo viene richiamato con frequenza casuale, possono essere presenti molti cicli nel grafo delle risorse non si può stabilire quale dei processi coinvolti nel ciclo abbia “causato” il deadlockAlternativamente, l’algoritmo può essere richiamato ogni volta che una richiesta non può essere soddisfatta immediatamente o quando l’utilizzo della CPU scende al di sotto del 40%


Ripristino dal deadlock: terminazione di Ripristino dal deadlock: terminazione di processiprocessi

Terminazione in abort di tutti i processi in deadlock

Terminazione in abort di un processo alla volta fino all’eliminazione del ciclo di deadlock

In quale ordine si decide di terminare i processi?

I fattori significativi sono:

La priorità del processo

Il tempo di computazione trascorso e il tempo ancora necessario al completamento del processo

Quantità e tipo di risorse impiegate

Risorse ulteriori necessarie al processo per terminare il proprio compito

Numero di processi che devono essere terminati

Tipo di processo: interattivo o batch


Ripristino dal deadlock: prelazione di Ripristino dal deadlock: prelazione di risorserisorse

Selezione di una vittimaSelezione di una vittima È necessario stabilire l’ordine di prelazione per minimizzare i costi

Roll backRoll back Un processo a cui sia stata prelazionata una risorsa deve ritornare ad uno stato sicuro, da cui ripartire

StarvationStarvation Alcuni processi possono essere sempre selezionati come vittime della prelazione: includere il numero di roll back nel fattore di costo

Deadlock. Sistemi Operativi a.a. 2007-08 7.2 Deadlock Il problema del deadlock Modello del sistema...

Documents

Transcript of Deadlock. Sistemi Operativi a.a. 2007-08 7.2 Deadlock Il problema del deadlock Modello del sistema...