Sommario
Indica la situazione di un blocco permanente di un insieme di processi in competizione per una o più risorse di sistema.
Non esiste una soluzione generale ed efficiente al problema.
Il deadlock è indice di una conflittualità sulle richieste di risorse tra più processi.
Sul ponte possono transitare autoveicoli solo in una direzione alla volta.
Ciascuna sezione del ponte può essere vista come una risorsa.
Se si verifica un deadlock, può essere risolto se un’auto torna indietro (rilascia la risorsa).
Può essere necessario che più auto debbano tornare indietro in caso di deadlock.
E’ possibile la starvation (attesa indefinita).
Esempio
Per la sincronizzazione si usano 2 semafori mutex1 e mutex2, inizializzati a 1.
Se si verifica la sequenza di azioni:
wait(mutex1)
e acquisisce il lettore 1;wait(mutex2)
e acquisisce il lettore 2;wait(mutex2)
e si blocca;wait(mutex1)
e si blocca;i due processi rimangono bloccati.
La situazione di deadlock dipende dalla velocità relativa di esecuzione dei processi.
Si possono distinguere due categorie di risorse:
Di una risorsa ne possono essere presenti più unità (istanze).
Ciascun istanza può essere utilizzata da un solo processo alla volta.
Ciascun processo impiega l’istanza con la seguente sequenza:
Es. : Processori; canali I/O, dispositivi di memoria, strutture dati, database.
Situazioni di deadlock si possono verficare se ogni processo possiede una risorsa e ne richiede altre.
Si supponga di avere uno spazio di memoria di 200 Kbytes (risorsa riusabile), se i processi P1 e P2 richiedono memoria nell’ordine seguente:
P1
. . .
Request 80 Kbytes;
. . .
Request 60 Kbytes;
P2
. . .
Request 70 Kbytes;
. . .
Request 80 Kbytes;
… si verifica una situazione di Deadlock
Create (prodotte) e distrutte (consumate).
Disponibili (teoricamente) in numero infinito.
Esempi: interruzioni, segnali, messaggi …
Un deadlock può avvenire se, ad esempio, si utilizza una receive bloccante.
P1
. . .
Receive (P2);
. . .
Send(P2, M1);
P2
. . .
Receive (P1);
. . .
Send(P1, M2);
Un grafo è un insieme di vertici (o nodi) V e un insieme di archi E.
V è partizionato in due tipi :
Arco di richiesta (arco orientato) P1 → RjArco di assegnazione (arco orientato) Rj → Pi
Se il grafo non contiene cicli → non si verificano situazioni di stallo.
Se il grafo contiene un ciclo →
Problema complesso e di rilievo in quanto può provocare gravi malfunzionamenti (si pensi a sistemi per il controllo di impianti industriali …).
La complessità risiede nel fatto che il blocco dipende dalla velocità relativa dei processi (race condition): un programma potrebbe funzionare per anni prima di evidenziare un problema.
Il problema cresce in complessità con l’introduzione dei thread, i quali possono condividere e competere per le risorse all’interno di un processo.
Malgrado ciò, la maggior parte dei sistemi operativi non offre strumenti per la prevenzione e trattamento dei deadlock.
Un deadlock può avvenire se sono verificate le seguenti condizioni contemporaneamente (Condizioni Necessarie):
Attesa circolare
Esiste un insieme {P0, P1, …, Pn} di processi in attesa, tali che P0 è in attesa per una risorsa che è posseduta da P1, P1 è in attesa per una risorsa che è posseduta da P2, …, Pn–1 è in attesa per una risorsa che è posseduta da Pn, e Pn è in attesa per una risorsa che è posseduta da P0.
Possibilità di un deadlock se sussistono le prime tre condizioni:
Esistenza del deadlock se sussistono tutte e quattro le condizioni:
Assicurare che il sistema non entri mai in uno stato di deadlock.
Prevenzione dei deadlock (prevention): rimuovere dal sistema ogni possibilità che ci sia un deadlock => basso utilizzo risorse.
Evitare i deadlock (avoidance): sussistono le condizioni perché intervenga un deadlock, ma si evita di entrarci effettivamente.
Rilevazione del deadlock. Permettere al sistema di entrare in uno stato di deadlock, per poi risolvere “il problema” (ripristino il sistema).
Ignorare il problema e fingere che i deadlock non avvengano mai nel sistema; impiegato dalla maggioranza dei sistemi operativi, incluso UNIX.
Un sistema progettato in modo da escludere la possibilità di un deadlock.
Due modalità:
Mutua Esclusione – non è richiesta per risorse che possono essere condivise; deve essere concessa per risorse che non possono essere condivise.
Possesso e attesa – si deve garantire che quando un processo richiede una risorsa, questo non possieda altre risorse.
Due strategie: permettere ad un processo di richiedere ed avere assegnate tutte le sue risorse prima che inizi l’esecuzione, o consentire ad un processo di richiedere risorse solo quando non ne possiede alcuna.
Si ha un basso impiego delle risorse. E’ possibile che si verifichi l’attesa indefinita di qualche processo.
Impossibilità di prelazione
Attesa circolare – si impone un ordinamento totale di tutti i tipi di risorsa e si pretende che ciascun processo richieda le risorse con un ordine di numerazione crescente.
Si può dire che la prevenzione del deadlock si fonda sull’implementazione di strategie che vincolano le richieste di risorse.
Svantaggi:
Il sistema decide dinamicamente se una richiesta di una risorsa può portare ad un deadlock (prevenzione dinamica del deadlock).
Tali tecniche richiedono la conoscenza di tutte le richieste che un processo può fare nell’arco di tutta la sua vita.
Il modello più semplice: ogni processo dichiara il numero massimo di risorse di ciascun tipo di cui può avere bisogno.
L’algoritmo di deadlock avoidance esamina dinamicamente lo stato di allocazione delle risorse per assicurare che non ci possa mai essere una condizione di attesa circolare.
Stato di allocazione delle risorse:
Non iniziare un processo se le sue richieste potrebbero portare ad un deadlock (Process Initiation Denial).
Non accettare richieste di una o più risorse ad un processo se queste potrebbero portare ad una situazione di deadlock (Resource Allocation Denial).
Sia n = numero di processi, e m = numero di tipi di risorse.
Resource= R= (R1,…, Rm)
Risorse totali nel sistema. Ri è il numero di istanze presenti nel sistema della risorsa Ri.
Avalaible=V= (V1,…,Vm)
Numero di istanze per ogni risorsa non allocate ad alcun processo. Vi rappresenta il n.ro di istanze della risorsa Ri non ancora allocata.
Claim= C = matrice n×m
Cij= richiesta del processo Pi per la risorsa Rj.
Allocation=A=matrice n×m
Aij= allocazione corrente al processo Pi della risorsa Rj.
La matrice C (di necessità) indica il numero massimo di richieste per ciascun processo (righe) di una certa risorsa.
Questa matrice deve essere fornita prima dell’esecuzione del processo.
Si può definire una politica di deadlock avoidance che rifiuti di eseguire un processo, data la sua matrice C (o meglio la sua riga).
Un processo Pn+1 viene eseguito solo se:
..cioé un processo viene eseguito se il numero massimo di richieste di tutti i processi più quelle del nuovo possono essere soddisfatte.
Riferito anche come algoritmo del bancherie.
La strategia consiste nell’assicurare che il sistema (processi + risorse) sia sempre in uno stato sicuro.
Quando un processo richiede una risorsa disponibile, il sistema deve decidere se l’allocazione immediata porti il sistema in uno stato sicuro.
Il sistema è in uno stato sicuro se esiste una sequenza 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 essere soddisfatte dalle risorse correntemente disponibili + risorse possedute da tutti i Pj, con j<i.
Se un sistema è in uno stato sicuro => non si evolve verso il deadlock.
Se un sistema è in uno stato non sicuro => possibilità di un deadlock.
Avoidance => assicura che un sistema non entri mai in uno stato non sicuro.
Quando un processo richiede un insieme di risorse,
In caso affermativo la richiesta viene effettivamente soddisfatta, viceversa no (il processo è sospeso).
Due processi: P1 e P2
Due risorse riusabili: R1 e R2
Il processo P1 richiede
Il processo P2 richiede
Si consideri lo stato di un sistema di 4 processi e tre risorse.
E’ questo uno stato sicuro?
Per rispondere a questa domanda bisogna capire se ognuno dei quattro processi sia in grado di terminare la propria esecuzione con le risorse disponibili. In altri termini per un processo Pi bisogna verificare che:
E’ evidente che la condizione non è verificata per P1 (che possiede un’istanza di R1 e ne richiede altre due).
In ogni caso, se si assegnasse a P2 un’istanza di R3, P2 potrebbe completare l’esecuzione (la condizione è vera per P2).
Quando P2 finisce le sue risorse verrebbero liberate.
Lo stato raggiunto è sicuro?
Per analogia al passo precedente, se si assegnassero a P1 le risorse richieste, P1 potrebbe terminare la sua esecuzione liberando le risorse allocate.
Lo stato raggiunto è sicuro?
Per analogia al passo precedente, se si assegnassero a P3 le risorse richieste, P3 potrebbe terminare la sua esecuzione liberando le risorse allocate. P4 ora avrebbe tutte le risorse…
Tutti i processi hanno bisogno di almeno un’unità di R1….quindi la richiesta di R1 non dovrebbe essere accolta
La strategia di deadlock avoidance
Non vincola le richieste alle risorse (non c’è alcun controllo).
Periodicamente (oppure ad ogni richiesta, oppure quando il grado di uso della CPU scende sotto certi livelli) il sistema esegue un algoritmo di per il rilevamento dell’attesa circolare.
Nel caso in cui venga trovata una condizione di attesa circolare il sistema applica un algoritmo di ripristino (recovery).
Una strategia di detection:
Si “killano” tutti i processi in uno stato di deadlock.
Si esegue un checkpoint di uno stato precedente al deadlock e si fanno ripartire i processi.
Si fa abortire un processo alla volta fino a quando il deadlock non esiste più.
Si prelazionano le risorse ai processi bloccati fino a quando il deadlock non esiste più.
Minor tempo di CPU consumato finora.
Minor numero di linee di output prodotte finora.
Maggior tempo stimato per la terminazione.
Minor numero di risorse allocate finora.
Minore priorità.
1. Introduzione ai Sistemi Operativi
5. Scheduling nei sistemi mono-processore
6. Threads, SMP
8. Scheduling Multiprocessore e Real-Time
9. Gestione dei processi nei sistemi operativi Unix/Linux e Window...
10. Introduzione alla Programmazione Concorrente
11. Sincronizzazione nel modello ad ambiente globale
12. Problemi di cooperazione nel modello ad ambiente globale
14. Sincronizzazione nel modello ad ambiente locale
15. Deadlock
16. Programmazione Multithread
18. Memoria Virtuale
20. Il File System
21. Primitive di sincronizzazione nel kernel Linux
22. Esercitazione: System call per la gestione dei processi
23. Esercitazione: Inteprocess Communication e Shared Memory
24. Esercitazione: System Call per la gestione dei semafori in Linu...
25. Esercitazione: Problema dei Produttori e dei Consumatori
26. Posix Threads
Ancillotti Boari, “Sistemi Operativi”, par 3.7
Stallings, “Operating Systems” 6th ed., par. 6.3