Cos’è un deadlock?
In un ambiente multiprogrammato più processi possono entrare in competizione per ottenere un numero finito di risorse.
Deadlock = STALLO — insieme di processi bloccati: ciascun processo “possiede” una risorsa ed attende di acquisire una risorsa allocata ad un altro processo dell’insieme.
Altri esempi
Esempio 1: risorsa hardware
- Nei primi sistemi batch alcuni sistemi di spooling richiedevano il completamento dell’output prima di cominciare la stampa.
- Se l’output era maggiore della dimensione del disco il sistema si bloccava.
Esempio 2: risorsa software
- Semafori A e B, inizializzati a 1:
P0 P1
wait(A); wait(B);
wait(B); wait(A);
Modello di sistema
- Insieme di processi P1, P2, . . ., Pn
- Insieme di risorse R1, R2, . . ., Rm
- Fisiche: cpu, memoria, stampanti, dispositivi di I/O
- Logiche: file, semafori, sezioni critiche
- Ciascun tipo di risorsa Ri può avere Wi istanze.
- Ad es.: in un sistema biprocessore la “risorsa CPU” ha Wi =2 istanze
Modello di sistema
Una tabella nel kernel conserva lo stato di ogni risorsa (se e a chi è assegnata).
Se un processo richiede una risorsa già assegnata, il processo richiedente è inserito in una apposita coda di processi in attesa.
Sequenza di uso della risorsa
Il protocollo di accesso alle risorse da parte dei processi prevede:
- Richiesta — se la richiesta non può essere soddisfatta immediatamente, il processo richiedente deve attendere fino all’acquisizione della risorsa.
- Utilizzo – il processo opera sulla risorsa.
- Rilascio – il processo rilascia la risorsa.
Richiesta/rilascio realizzati con apposite system call: request/release device, open/close file, allocate/free memory.
Caratterizzazione dei deadlock
Teorema: Una situazione di deadlock può verificarsi se e solo se valgono simultaneamente le seguenti condizioni:
- Mutua esclusione: ogni risorsa è assegnata ad un solo processo oppure è disponibile.
- 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, al termine del suo compito.
- Attesa circolare: esiste un insieme { P1, …, Pn } di processi in attesa, tali che P1 è in attesa di una risorsa che è posseduta da P2, P2 è in attesa di una risorsa posseduta da P3, …, Pn–1 è in attesa di una risorsa posseduta da Pn, e Pn è in attesa di una risorsa posseduta da P1.
Come si può rappresentare un deadlock
Un deadlock si puo’ rappresentare mediante un grafo di allocazione risorse:
Un grafo è costituito da un insieme di vertici (o nodi) V variamente connessi per mezzo di un’insieme di archi E.
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.
L’insieme E consiste di
- Arco di richiesta: Pi → Rj
- Arco di assegnazione: Rj → Pi
Grafo di allocazione risorse
- Processo
- Tipo di risorsa con 4 istanze
- Pi richiede un’istanza di Rj
- Pi possiede un’istanza di Rj
Esempio 1
- 2 processi
- 2 risorse
- R1 → W1 = 1 istanza
- R2 → W2 = 1 istanze
- P1 possiede un’istanza di R1 e attende un’istanza di R2
- P2 possiede un’istanza di R2 attende un’istanza di R1
Il sistema è in deadlock?
Esempio 2
- 2 processi
- 2 risorse
- R1 → W1 = 1 istanza
- R2 → W2 = 2 istanze
- P1 possiede un’istanza di R1 e un’istanza di R2
- P2 possiede un’istanza di R2 attende un’istanza di R1
Il sistema è in deadlock?
Esempio 3
- 3 processi
- 4 risorse
- R1 → W1 = 1 istanza
- R2 → W2 = 2 istanze
- R3 → W3 = 1 istanza
- R4 → W4 = 3 istanze
- P1 possiede un’istanza di R2 e attende un’istanza di R1
- P2 possiede un’istanza di R1 e di R2 e attende un’istanza di R3
- P3 possiede un’istanza di R3
Il sistema è in deadlock?
Esempio 4
- 3 processi
- 4 risorse
- R1 → W1 = 1 istanza
- R2 → W2 = 2 istanze
- R3 → W3 = 1 istanza
- R4 → W4 = 3 istanze
P1 possiede un’istanza di R2 e attende un’istanza di R1
P2 possiede un’istanza di R1 e di R2 e attende un’istanza di R3
P3 attende un’istanza di R3 e attende un’istanza di R2
Il sistema e’ in deadlock?
Esempio 5
- 4 processi
- 2 risorse
- R1 → W1 = 2 istanza
- R2 → W2 = 2 istanze
P1 possiede un’istanza di R2 e attende un’istanza di R1
P2 possiede un’istanza di R1
P3 possiede un’istanza di R1 e attende un’istanza di R2
P4 possiede un’istanza di R2
Il sistema e’ in deadlock?
Riassumendo
Ogni risorsa ha solo un’istanza.
La presenza di un ciclo è condizione necessaria e sufficiente per un deadlock (c’è ciclo se e solo se deadlock):
- se c’e il ciclo nel grafo c’è anche il deadlock (esempio 1);
- se non c’e’ il ciclo non c’è deadlock (esempio2).
Riassumendo
Qualche risorsa ha piu’ istanze.
La presenza di un ciclo è condizione necessaria ma non sufficiente per un deadlock (deadlock implica ciclo):
- se non c’e’ ciclo nel grafo non c’e’ deadlock (esempio 3);
- se c’e’ il ciclo nel grafo:
- può esserci deadlock (esempio 4);
- può non esserci deadlock (esempio 5).
Le lezioni del Corso
2. Lo stallo dei processi – parte prima
3. Lo stallo dei processi – parte seconda
4. Lo stallo dei processi – parte terza
6. Il S.O. Linux – parte prima
7. Il S.O. Linux – parte seconda
8. Il S.O. Windows – parte prima
9. Il S.O. Windows – parte seconda
10. Il S.O. Windows – parte terza
11. I S.O. multimediali – parte prima
12. I S.O. multimediali – parte seconda
13. I S.O. multimediali – parte terza
14. I Sistemi Operativi distribuiti - parte prima
15. I Sistemi Operativi distribuiti - parte seconda
16. I Sistemi Operativi distribuiti - parte terza
17. I Sistemi Operativi distribuiti - parte quarta
18. I Sistemi Operativi distribuiti - parte quinta
19. I Sistemi Operativi distribuiti - parte sesta
I materiali di supporto della lezione
Silberschatz , Galvin, Gagne – Sistemi Operativi 8a ed.
Capitolo 6
Tanenbaum – Moderni sistemi operativi 3a ed.
Capitolo 7
Deitel, Deitel, Choffnes - Sistemi operativi 3a ed.
Capitolo 5
Il Podcast della lezione
Le altre lezioni del corso con podcast
2. Lo stallo dei processi – parte prima
3. Lo stallo dei processi – parte seconda
4. Lo stallo dei processi – parte terza
6. Il S.O. Linux – parte prima
7. Il S.O. Linux – parte seconda
8. Il S.O. Windows – parte prima
9. Il S.O. Windows – parte seconda
10. Il S.O. Windows – parte terza
11. I S.O. multimediali – parte prima
12. I S.O. multimediali – parte seconda
13. I S.O. multimediali – parte terza
14. I Sistemi Operativi distribuiti - parte prima
17. I Sistemi Operativi distribuiti - parte quarta
18. I Sistemi Operativi distribuiti - parte quinta
19. I Sistemi Operativi distribuiti - parte sesta
I podcast del corso sono disponibili anche su iTunesU e tramite Feed RSS.
