Sommario
- Introduzione al Deadlock
- Caratterizzazione dei Deadlock
- Metodi per la gestione dei Deadlock
Il Deadlock
- Indica la situazione di un blocco permanente di un insieme di processi in competizione per una o più risorse di sistema
- Problema complesso e di rilievo in quanto può provocare gravi malfunzionamenti
- 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
- Malgrado ciò, la maggior parte dei sistemi operativi non offre strumenti per la prevenzione e il trattamento dei deadlock
- Non esiste una soluzione generale ed efficiente al problema
Tipologie di Risorse
- Risorse Riusabili (reusable)
- 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: richiesta – uso – rilascio
- Es. : Processori; canali I/O, dispositivi di memoria, strutture dati
- Situazioni di Deadlock si possono verificare se ogni processo possiede una risorsa e richiede altre
- Risorse Consumabili
- Create e distrutte; disponibili (teoricamente) in numero infinito
- Esempi: interruzioni, segnali, messaggi …
- Un Deadlock può avvenire se, ad esempio, si utilizza una receive bloccante
Grafo di assegnazione delle risorse
- Un grafo (V,E) in cui V è partizionato in due tipi
- P = {P1, P2, …, Pn}, è l’insieme costituito da tutti i processi nel sistema
- R = {R1, R2, …, Rm}, è l’insieme costituito da tutti i tipi di risorse nel sistema
- Arco (orientato) di richiesta P1 Rj
- Arco (orientato) di assegnazione Rj Pi
- Se il grafo non contiene cicli => non si verificano situazioni di stallo.
- Se il grafo contiene un ciclo =>
- se c’è solo un’istanza per tipo di risorsa, allora si verifica una situazione di stallo;
- se vi sono più istanze per tipo di risorsa, allora è possibile che si verifichi una situazione di stallo.
Grafo di assegnazione delle risorse
Caratterizzazione dei Deadlock
- Un Deadlock può avvenire se sono verificate le seguenti condizioni contemporaneamente (Condizioni Necessarie).
- Mutua esclusione: un solo processo alla volta può usare una risorsa.
- Possesso ed attesa: un processo che possiede almeno una risorsa, attende di acquisire ulteriori risorse possedute da altri processi.
- Impossibilità di prelazione: una risorsa può essere rilasciata dal processo che la possiede solo volontariamente.
- 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
- Più precisamente…c’è possibilità di un Deadlock se sussistono le prime tre condizioni, esistenza del Deadlock se sussistono tutte
Metodi per la gestione dei Deadlock: Deadlock Prevention
- Rimuovere dal sistema ogni possibilità che ci sia un Deadlock
- Due modalità
- Indiretta, che mira ad evitare il verificarsi delle prime tre condizioni
- Diretta, che mira ad evitare il verificarsi di attese circolari
-
- 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.
- La prevenzione del Deadlock si fonda sull’implementazione di strategie che vincolano le richieste di risorse
- Svantaggi: utilizzo delle risorse inefficiente…esecuzione dei processi inefficiente
Metodi per la gestione dei Deadlock: Deadlock Avoidance
- Il sistema decide dinamicamente se una richiesta di una risorsa può portare ad un Deadlock (prevenzione dinamica del Deadlock)
- Strategia
- Quando un processo richiede un insieme di risorse, si assume che la richiesta venga accettata
- Lo stato del sistema viene aggiornato; si determina, applicando opportuni algoritmi (es l’alg. del bancherie) se il nuovo stato è uno stato sicuro: in caso affermativo la richiesta viene soddisfatta, viceversa no
- Problematiche: la strategia di Deadlock avoidance
- Richiede che ogni processo dichiari preventivamente il numero max di risorsa che utilizzerà;
- I processi che vengono analizzati dall’alg. devono essere indipendenti
- Deve esserci un numero predeterminato e costante di risorse da allocare
- Nessun processo può terminare mentre è in possesso di una risorsa
Metodi per la gestione dei Deadlock: Deadlock Detection
- Non vincola le richieste alle risorse
- Periodicamente il sistema esegue un algoritmo per il rilevamento dell’attesa circolare
- Nel caso in cui venga trovata una condizione di attesa circolare il sistema applica un algoritmo di ripristino
- Una strategia di detection:
- Impiega un grafo di attesa in cui i nodi sono processi e un arco Pi -> Pj indica che Pi è in attesa che Pj rilasci una risorsa
- Periodicamente viene richiamato un algoritmo che ricerca un ciclo nel grafo.
- Sono possibili diverse strategie di ripristino
Grafo di allocazione delle risorse
Prossima lezione
Dai Processi ai Thread
Le lezioni del Corso
1. Introduzione ai Sistemi Operativi
2. Richiami
3. Architettura e funzionalità dei sistemi operativi
4. Esercitazione – Installazione del Sistema operativo Linux
6. Gestione dei processi nei sistemi operativi Unix/Linux e Window...
8. Esercitazione: Makefile e librerie
9. Esercitazione: System call per la gestione dei processi
11. Introduzione alla Sincronizzazione dei Processi
12. Sincronizzazione nel modello ad ambiente globale
13. Sincronizzazione nel modello ad ambiente locale
14. Esercitazione: Interprocess Communication e Shared Memory
15. Esercitazione: Gestione dei semafori
16. Esercitazione: Problema dei produttori e consumatori
17. Esercitazione: Problema dei lettori e degli scrittori
19. Il Deadlock
I materiali di supporto della lezione
P. Ancilotti, M.Boari, A. Ciampolini, G. Lipari, “Sistemi Operativi”, Mc-Graw-Hill (Cap. 3 par 3.7)
