Deadlock
Principi del deadlock (s tallo) R ilevamento dello s tallo Trattamento dello s tallo Es clus ione dello s tallo S tarvation
Un esempio di ingorgo
2 3
1 4
Stallo possibile
Sistemi Operativi 11/12 Deadlock
Stallo
2
Un esempio di ingorgo
I quadranti 1-4 sono risorse contese
Lautomobile a destra richiede 1 e 2 Lautomobile in alto richiede 2 e 3 Lautomobile a sinistra richiede 3 e 4 Lautomobile in basso richiede 4 e 1
Sistemi Operativi 11/12
Deadlock
Deadlock
Esistono potenziali conflitti tra i processi che utilizzano risorse condivise La maggior parte delle risorse prevede un utilizzo esclusivo
Esempi: CD-ROM, plotter
Non necessariamente i deadlock coinvolgono dispositivi di I/O: esempio database in rete
Sistemi Operativi 11/12
Deadlock
Le risorse
I deadlock possono verificarsi quando i processi ottengono accessi esclusivi a dispositivi (o oggetti software), in generale si parler di risorse Le risorse possono essere di diverso tipo: dispositivi di I/O, memoria, una tupla di un database, ma vengono comunemente classificate in due tipi diversi:
1. risorse con prerilascio: possono essere tolte ai processi senza problemi (memoria, CPU) 2. risorse senza prerilascio: se vengono tolte ai processi si ha il fallimento dell'elaborazione (stampanti, lettori di nastro)
Sistemi Operativi 11/12
Deadlock
Le risorse
In generale i deadlock coinvolgono risorse senza prerilascio La sequenza di passi necessari per l'uso di una risorsa :
1. Richiesta della risorsa 2. Utilizzo della risorsa 3. Rilascio della risorsa
Se la risorsa non disponibile, il processo viene fatto attendere, in alcuni sistemi il processo viene automaticamente bloccato e poi risvegliato quando la risorsa torna disponibile, in altri il processo che deve esplicitamente gestire la situazione
Sistemi Operativi 11/12
Deadlock
Definizione di deadlock
Un insieme di processi in deadlock se ogni processo dell'insieme in attesa di un evento che solo un altro processo appartenente allo stesso insieme pu causare
Un processo in deadlock non procede mai e non finisce mai la sua esecuzione, processi in deadlock possono bloccare l'intero sistema
Sistemi Operativi 11/12
Deadlock
Condizioni necessarie
Coffman e altri (1971) hanno dimostrato che le seguenti sono condizioni necessarie affinch esista un deadlock:
1. Mutua esclusione: un solo processo alla volta pu utilizzare la risorsa 2. Prendi e aspetta (Hold and Wait): i processi che detengono risorse possono chiederne altre 3. Assenza di prerilascio (No Preemption): le risorse possono essere rilasciate solo dal processo che le detiene, il rilascio non pu essere forzato 4. Attesa circolare (Circular Wait): deve esistere una lista circolare di processi/risorse
Sistemi Operativi 11/12
Deadlock
Modellazione del deadlock
Holt (1972) ha mostrato che le quattro condizioni possono essere rappresentate da grafi orientati I nodi possono essere di due tipi:
risorse (quadrati) processi (cerchi)
Gli archi possono solo connettere nodi di tipo diverso. Necessariamente anche gli archi assumono significato diverso:
archi uscenti da processi: il processo ha richiesto la risorsa archi uscenti da risorse: la risorsa allocata al processo
P R
R P
Sistemi Operativi 11/12
Deadlock
Modellazione del deadlock
1 2 3 1 4
Sistemi Operativi 11/12
Deadlock
10
Modellazione del deadlock
Problema dei filosofi
F1
P1
F2
P1
P4
P2
P4
P2
F4
P3
F3
P3
Risorse singole
Risorse multiple
Sistemi Operativi 11/12
Deadlock
11
Grafo con risorse multiple
R1
R2
R3
Assegnamento
P1
P2
P3
P4
P5
Richiesta
R4
R5
R6
R7
Sistemi Operativi 11/12
Deadlock
12
Grafo con cicli
R1
esiste almeno un ciclo nel grafo
esempio di figura
P1 R1 P2 R2 P1, P1 R1 P2 R3 P1
P1
P2 R3
R2
esiste deadlock? no, esistono abbastanza risorse per tutti!
Sistemi Operativi 11/12
Deadlock
13
Grafo con ciclo e deadlock
i cicli sono buoni indizi di deadlock esiste deadlock?
s, in R2 non ci sono abbastanza risorse per soddisfare le richieste di P1 e P2
R1
P1
P2 R3
se esiste un ciclo nel grafo allora pu esserci un deadlock
R2
sono possibili cicli senza deadlock un deadlock pu verificarsi solo se esiste un ciclo
Deadlock 14
Sistemi Operativi 11/12
Trattamento del deadlock
In generale sono utilizzate quattro strategie per trattare i deadlock:
1. Non porsi il problema 2. Individuare il deadlock e risolverlo 3. Prevenire il deadlock in modo dinamico 4. Prevenire il deadlock impedendo una delle quattro condizioni necessarie
Sistemi Operativi 11/12
Deadlock
21
Algoritmo dello struzzo
l'approccio pi semplice: far finta di niente Se il deadlock avviene ogni 50 anni allora inutile preoccuparsi Esempio UNIX:
Tabella dei processi Tabella dei file aperti
Sistemi Operativi 11/12
Deadlock
22
Prevenzione dei deadlock
La seconda strategia consiste nel rendere impossibile il deadlock Se si evita una delle quattro condizioni necessarie il deadlock diventa impossibile
Sistemi Operativi 11/12
Deadlock
23
Mutua esclusione
Se non vi sono risorse assegnate in modo esclusivo ad un singolo processo non vi saranno deadlock Un possibile approccio lo Spooling
Occorre un processo daemon (demone) e una directory di spooling Per la stampa di un file, il processo genera l'intero file e lo memorizza nella directory di spooling Il daemon l'unico processo ad avere accesso alla directory di spooling e ha il compito di avviare la stampa Lo spooling viene usato anche nei trasferimenti via rete (posta elettronica, ftp, ... )
Sistemi Operativi 11/12
Deadlock
24
Spooling
Esempio stampante: Effettuando lo spooling sulle uscite per la stampante, pi processi possono produrre le loro uscite contemporaneamente
Dato che esiste un solo processo che utilizza la stampante fisica e non ha bisogno di altre risorse il deadlock impossibile Non tutti i processi possono essere gestiti attraverso lo spooling (es. la tabella dei processi)
Rimane comunque la possibilit di deadlock sulla risorsa disco
Sistemi Operativi 11/12
Deadlock
25
Prendi e aspetta
Occorre evitare che processi che detengono risorse rimangano in attesa di ulteriori risorse. Ci possono essere varie soluzioni: Un processo richiede immediatamente tutte le risorse di cui ha bisogno, se non sono disponibili attende Nascono nuovi problemi: Un processo non sempre sa quello di cui ha bisogno nel corso dell'esecuzione L'uso delle risorse non ottimizzato (rimangono risorse spesso inutilizzate) Vi il rischio che un processo che ha bisogno di molte risorse rimanga in attesa per tempi molto lunghi Un modo leggermente diverso quello di imporre che un processo rilasci temporaneamente le risorse detenute prima di una nuova richiesta La terza condizione nessun prerilascio di fatto inutilizzabile
Sistemi Operativi 11/12
Deadlock
26
Attesa Circolare
L'attesa circolare pu essere eliminata in vari modi: Un processo pu richiedere una sola risorsa per volta Le risorse sono numerate e possono essere richieste solo secondo l'ordine numerico
P4
F1
P1
F2
P2
F3
P3
F4
Il filosofo 4 non pu richiedere la forchetta 4 prima della forchetta 1 Una variante richiede semplicemente che la nuova risorsa debba avere una etichetta maggiore di tutte quelle detenute
Sistemi Operativi 11/12
Deadlock
27
Attesa circolare
2 3
1 4
Lautomobile in basso non pu chiedere 4 prima di 1 Perci lauto a sinistra pu procedere
Sistemi Operativi 11/12
Deadlock
28
Attesa circolare
Il grafo non descrive un ciclo
Sistemi Operativi 11/12
Deadlock
29
Evitare il deadlock
possibile impedire il verificarsi di un deadlock? S se si hanno a disposizione alcune informazioni
Il modello pi semplice e pi utile richiede che ciascun processo dichiari il numero massimo di risorse necessarie Lalgoritmo esamina dinamicamente lo stato di allocazione delle risorse per garantire che non accada mai una attesa circolare Lo stato definito dal numero di risorse disponibili e allocate e dal numero massimo di risorse richieste
Sistemi Operativi 11/12
Deadlock
30
Stato sicuro
Uno stato si dice sicuro se esiste una sequenza di altri stati che porta tutti i processi ad ottenere le risorse necessarie (e quindi terminare) altrimenti viene detto non sicuro
sicuro (non vi deadlock)
non sicuro (possibilit di deadlock) deadlock
Per evitare i deadlock quindi sufficiente evitare gli stati non sicuri
Sistemi Operativi 11/12
Deadlock
31
Stato sicuro/non sicuro
R1
R1 P2
R1 P2
P1
P1
P1
P2
R2
R2
R2
Stato sicuro
Stato non sicuro
Deadlock
Possibile richiesta
Sistemi Operativi 11/12
Deadlock
32
Algoritmo del banchiere
Tratta risorse multiple Ogni processo deve dichiarare il numero massimo di risorse necessarie Se un processo richiede una risorsa, se non disponibile rimane in attesa Dopo che un processo ha ottenuto tutte le risorse necessarie, le deve rilasciare in un tempo finito
Sistemi Operativi 11/12
Deadlock
33
Algoritmo del banchiere
Nome Anna Barbara Carlo Davide Disponibili U 0 0 0 0 10 M 6 5 4 7 L'algoritmo stato proposto da Dijkstra (1965) imita il comportamento di un banchiere nei confronti delle richieste dei clienti Ad ogni cliente concesso un certo numero di unit di credito (per esempio 1000 ) (cio le risorse finanziarie Massime necessarie per portare a conclusione i rispettivi affari) Lo stato del sistema la quantit di credito Usato ad ogni istante Complessivamente le risorse necessarie sarebbero 22 unit, ma il banchiere ne ha a disposizione solamente 10
Sistemi Operativi 11/12
Deadlock
34
Algoritmo del banchiere
Nome Anna Barbara Carlo Davide Disp. U M 1 1 2 4 2 6 5 4 7 N 5 4 2 3 Uno stato si dice sicuro se esiste una sequenza di altri stati che porta tutti i clienti ad ottenere prestiti fino al loro massimo credito (e quindi terminare) uno stato sicuro?
S perch con due unit Carlo pu portare a termine i suoi affari (liberando quindi quattro unit, ...)
Risorse Necessarie N=M-U
Sistemi Operativi 11/12
Deadlock
35
Algoritmo del banchiere
Nome Anna Barbara Carlo Davide Disp. U 1 2 2 4 1 M N 6 5 4 7 5 3 2 3 Non uno stato sicuro perch nessun cliente riesce a portare a termine i suoi affari Se invece di concedere credito a Carlo si concede a Barbara
Sistemi Operativi 11/12
Deadlock
36
Algoritmo
Una richiesta viene evasa solo se porta in uno stato ancora sicuro altrimenti il processo deve attendere L'algoritmo descritto applicabile ad un sistema con una singola risorsa multipla, ma pu essere generalizzato al caso di un sistema complesso con molte classi di risorse L'algoritmo del banchiere soffre del solito problema: presuppone una conoscenza completa del sistema comunque un punto di partenza per risolvere i casi concreti
Sistemi Operativi 11/12
Deadlock
37
Risorse multiple
Dati: allocazione corrente, massima allocazione, risorse disponibili
Occorre calcolare le risorse necessarie
Processi P0 P1 P2 P3 P4 Disponibili
Corrente 1 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1
Massima 2 0 2 1 3 1 2 1 2 2 2 1 3 1 2 0 1 2 1 2 1 1 1 2 2
Necessaria 1 0 1 1 3 0 1 1 1 2 2 1 3 1 1 0 0 1 0 1 1 1 0 2 2
Lunico processo che pu ottenere tutte le risorse che gli servono P3
Sistemi Operativi 11/12 Deadlock 38
Risorse multiple
Processi P0 P1 P2 P3 P4 Disponibili
Corrente 1 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 2 1 2 0 0 1 0 0 1 0 0 0 0
Massima 2 0 2 1 3 1 2 1 2 2 2 1 3 1 2 0 1 2 1 2 1 1 1 2 2
Necessaria 1 0 1 1 3 0 1 1 1 2 2 1 3 1 1 0 0 0 0 0 1 1 0 2 2
Quando un processo termina le rilascia e le risorse disponibili aumentano Disponibili
Sistemi Operativi 11/12
1 1 2 1 2
Deadlock 39
Risorse multiple
Processi P0 P1 P2 P3 P4 Disponibili
Corrente 1 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 2 1 2
Massima 2 0 2 1 3 1 2 1 2 2 2 1 3 1 2 0 1 2 1 2 1 1 1 2 2
Necessaria 1 0 1 1 3 0 1 1 1 2 2 1 3 1 1 1 1 0 2 2
P1 pu terminare
Sistemi Operativi 11/12
Deadlock
40
Risorse multiple
Processi P0 P1 P2 P3 P4 Disponibili
Corrente 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 2 2 2 2 2
Massima 2 0 2 1 3 1 2 1 2 2 2 1 3 1 2 0 1 2 1 2 1 1 1 2 2
Necessaria 1 0 1 1 3 2 1 3 1 1 1 1 0 2 2
P4 pu terminare
Sistemi Operativi 11/12
Deadlock
41
Risorse multiple
Processi P0 P1 P2 P3 P4 Disponibili
Corrente 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 2 2 3 2 2
Massima 2 0 2 1 3 1 2 1 2 2 2 1 3 1 2 0 1 2 1 2 1 1 1 2 2
Necessaria 1 0 1 1 3 2 1 3 1 1
P2 pu terminare
Sistemi Operativi 11/12
Deadlock
42
Risorse multiple
Processi P0 P1 P2 P3 P4 Disponibili
Corrente 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 3 2 3
Massima 2 0 2 1 3 1 2 1 2 2 2 1 3 1 2 0 1 2 1 2 1 1 1 2 2
Necessaria 1 0 1 1 3
P0 pu terminare
Disponibili
3 2 4 2 3
Se esiste una sequenza in cui tutti i processi ottengono tutte le risorse necessarie, allora il sistema in uno stato sicuro
Sistemi Operativi 11/12 Deadlock 43
Risorse multiple
Processi P0 P1 P2 P3 P4 Disponibili
Corrente 1 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1
Massima 2 0 2 1 3 1 2 1 2 2 2 1 3 1 2 0 1 2 1 2 1 1 1 2 2
Necessaria 1 0 1 1 3 0 1 1 1 2 2 1 3 1 1 0 0 1 0 1 1 1 0 2 2
Se si concede una risorsa A a P0
Processi P0 P1 P2 P3 P4 Disponibili
Sistemi Operativi 11/12
Corrente 2 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 0 0 1 0 1
Deadlock
Massima 2 0 2 1 3 1 2 1 2 2 2 1 3 1 2 0 1 2 1 2 1 1 1 2 2
Necessaria 0 0 1 1 3 0 1 1 1 2 2 1 3 1 1 0 0 1 0 1 1 1 0 2 2
44
Risorse multiple
Processi P0 P1 P2 P4 Disponibili Processi P0 P2 P4 Disponibili
Sistemi Operativi 11/12
Corrente 2 0 10 0 1 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 2 12 Corrente 2 0 10 0 0 0 0 0 1 0 0 1 0 0 1 2 2 22
Deadlock
Massima 2 0 2 1 3 1 2 1 2 2 2 1 3 1 2 1 1 1 2 2
Necessaria 0 0 1 1 3 0 1 1 1 2 2 1 3 1 1 1 1 0 2 2
Massima 2 0 2 1 3 2 1 3 1 2 1 1 1 2 2
Necessaria 0 0 1 1 3 2 1 3 1 1 1 1 0 2 2
45
Risorse multiple
Processi P0 P2 Disponibili
Corrente 2 0 10 0 0 0 0 0 1 1 2 3 22
Massima 2 0 2 1 3 2 1 3 1 2
Necessaria 0 0 1 1 3 2 1 3 1 1
Non pi possibile portare a termine nessuno dei due processi
Sistemi Operativi 11/12
Deadlock
46
Rilevamento del deadlock
Permette al sistema di entrare in uno stato di deadlock Richiede un algoritmo di rilevamento Occorre definire uno schema di recovery
Sistemi Operativi 11/12
Deadlock
47
Individuare lo stallo e risolverlo
Un diverso approccio consiste nell'individuare il deadlock e risolverlo Ogni volta che una risorsa viene richiesta o rilasciata si controlla il grafo delle risorse per verificare l'esistenza di un ciclo, se esiste si elimina uno dei processi coinvolti Un metodo pi semplice non controlla nemmeno il grafo: periodicamente se un processo bloccato da troppo tempo (es. un'ora) viene rimosso
Esiste il pericolo di effetti collaterali (non sempre possibile annullare tutti gli effetti di un processo non concluso positivamente
Sistemi Operativi 11/12
Deadlock
48
Rilevamento a singola istanza
tutti i tipi di risorse possono avere una sola istanza allora un ciclo nel grafo delle allocazioni indica un deadlock un generico algoritmo di rilevamento richiede una complessit dellordine di n2 operazioni ove n il numero di processi del grafo di attesa
Sistemi Operativi 11/12
Deadlock
49
Grafo di attesa e di allocazione
Grafo di allocazione
Corrispondente grafo di attesa
Sistemi Operativi 11/12
Deadlock
50
Rilevamento a istanze multiple
esistono pi istanze per ogni tipo di risorsa si usa un algoritmo simile a quello del banchiere per rilevare il deadlock
richiede una complessit dellordine di m * n2 operazioni (m = numero di tipi di risorse, n = numero di processi)
la frequenza con cui si attiva lalgoritmo di rilevamento dipende
dalla probabilit che si verifichi un deadlock dal numero di processi coinvolti
Sistemi Operativi 11/12
Deadlock
51
Strategie di recovery
Dopo il rilevamento di un deadlock che fare?
preemption rollback terminazione di processi
Ignorare il problema
approccio pi semplice migliori prestazioni e sistema meno restrittivo esempio: Unix, Windows
Sistemi Operativi 11/12
Deadlock
52
Terminazione di processi
Uccidere tutti i processi coinvolti Uccidere solo un processo alla volta fino a che il ciclo di deadlock non si aperto Problema: quale ordine scegliere:
Priorit del processo Tempo di esecuzione trascorso e/o necessario Risorse usate/necessarie Numero di processi che devono essere terminati Processi interattivi o batch
Sistemi Operativi 11/12
Deadlock
53
Deadlock e sistemi operativi
A volte si usa un approccio combinato
Le risorse sono partizionate in classi ordinate gerarchicamente Si applica un algoritmo di ordinamento delle risorse basato sulle classi Allinterno di ogni classe, si usa un algoritmo particolare per i deadlock Si garantisce che il deadlock non possa coinvolgere pi di una classe e che linsieme nel suo complesso pu essere ritenuto sicuro
Sistemi Operativi 11/12
Deadlock
54
Esempio di approccio combinato
Classi di risorse
risorse di sistema
tutto ci che usato dal S.O.
memoria utente
memoria assegnata ai processi degli utenti
risorse dei processi
file, dispositivi di I/O, ecc...
spazio di swap
spazio destinato su dispositivo di memorizzazione di massa per i processi
Sistemi Operativi 11/12
Deadlock
55
Soluzione combinata
ordinamento di risorse nelle quattro classi singoli approcci in ogni classe
risorse di sistema
prevenzione: ordinamento allinterno della classe
memoria utente
preemption: swap di un processo su memoria di massa
risorse ai processi
prevenzione: i processi informano prima il S.O: delle risorse che necessitano
spazio di swap
prevenzione: tutte le risorse sono allocate allo stesso tempo (preallocation)
Sistemi Operativi 11/12
Deadlock
56
Starvation
Un fenomeno simile al deadlock la starvation un processo non pu procedere perch altri processi detengono sempre una risorsa di cui ha bisogno
la richiesta del processo non viene mai soddisfatta
in linea di principio, il processo potrebbe ottenere la risorsa, ma non l'ottiene perch:
a priorit bassa la temporizzazione della richiesta della risorsa errata l'algoritmo per l'allocazione delle risorse costruito male
Sistemi Operativi 11/12
Deadlock
57
Esempi di starvation
processi batch con bassa priorit in un sistema time-sharing attraversare una strada trafficata (trasmissione su bus, protocollo di token) cercare di chiamare il servizio informazioni delle Ferrovie avere accesso a un corso molto gettonato a numero chiuso
Sistemi Operativi 11/12
Deadlock
58
Starvation
STOP
Lauto allo stop attende allinfinito, perch le auto della strada principale hanno una alta priorit
Sistemi Operativi 11/12
Deadlock
59
Starvation
Soluzioni: opportunit: ogni processo ha una percentuale adeguata di tutte le risorse tempo: la priorit del processo viene aumentata se il processo aspetta per un tempo troppo lungo
Sistemi Operativi 11/12
Deadlock
60
Starvation
STOP
L'introduzione di un semaforo pu risolvere il problema
Sistemi Operativi 11/12
Deadlock
61
Algoritmo del banchiere
Es ercizi
Esercizio 1
Processo A B C D Totali
U 3 2 1 2 8
M 7 5 6 9 Dire quali richieste sono accettabili da parte del sistema con 12 o 14 risorse a disposizione: (A,2) (B,2) (C,3) (D,4)
Sistemi Operativi 11/12
Deadlock
63
Esercizio 1 dopo (A, 2)
Processo A B C D Totali
U 5 2 1 2 10
M 7 5 6 9
Con 12 risorse a disposizione posso concludere il processo A
Sistemi Operativi 11/12
Deadlock
64
Esercizio 1 dopo (B, 2)
Processo A B C D Totali
U 3 4 1 2 10
M 7 5 6 9
Con 12 risorse a disposizione posso concludere il processo B
Sistemi Operativi 11/12
Deadlock
65
Esercizio 1 dopo (C, 3)
Processo A B C D Totali
U 3 2 4 2 11
M 7 5 6 9 Con 12 risorse a disposizione non posso concludere alcun processo Con 14 il processo B
Sistemi Operativi 11/12
Deadlock
66
Esercizio 1 dopo (D, 4)
Processo A B C D Totali
U 3 2 1 6 12
M 7 5 6 9
Con 12 o 14 risorse a disposizione non posso concludere alcun processo
Sistemi Operativi 11/12
Deadlock
67
Esercizio 2
Un sistema ha quattro processi e cinque risorse allocabili. Lallocazione corrente e il massimo fabbisogno sono i seguenti:
Processi A B C D Disponibili Corrente 1 0 2 1 1 2 0 1 1 0 1 1 0 1 0 1 1 1 1 0 0 0 x 1 1 Massima 1 1 2 1 2 2 2 2 1 0 2 1 5 1 0 1 1 2 2 1
Quale il pi piccolo valore di x perch questo stato sia sicuro?
Sistemi Operativi 11/12 Deadlock 68
Esercizio 2 x=1 (a)
Processi A B C D Disponibili
Corrente 1 0 2 1 1 2 0 1 1 0 1 1 0 1 0 1 1 1 1 0 0 0 x 1 1
Massima 1 1 2 1 2 2 2 2 1 0 2 1 5 1 0 1 1 2 2 1
Necessaria 0 1 0 0 1 0 2 1 0 0 1 0 5 0 0 0 0 1 1 1
Sistemi Operativi 11/12
Deadlock
69
Esercizio 2 x=1 (b)
Processi A B C D Disponibili
Corrente 1 0 2 1 1 2 0 1 1 0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 1
Massima 1 1 2 1 2 2 2 2 1 0 2 1 5 1 0 1 1 2 2 1
Necessaria 0 1 0 0 1 0 2 1 0 0 1 0 5 0 0 0 0 1 1 1
Sistemi Operativi 11/12
Deadlock
70
Esercizio 2 x=1 (c)
Processi A B C Disponibili
Corrente 1 0 2 1 1 2 0 1 1 0 1 1 0 1 0 1 1 2 2 1
Massima 1 1 2 1 2 2 2 2 1 0 2 1 5 1 0
Necessaria 0 1 0 0 1 0 2 1 0 0 1 0 5 0 0
Sistemi Operativi 11/12
Deadlock
71
Esercizio 2 x=1 (d)
Processi B C Disponibili
Corrente 2 0 1 1 0 1 1 0 1 0 2 1 4 3 2
Massima 2 2 2 1 0 2 1 5 1 0
Necessaria 0 2 1 0 0 1 0 5 0 0
Una risorsa di tipo 3 non basta, ne servono almeno 2 (x=2)
Sistemi Operativi 11/12
Deadlock
72
Esercizio 2 x=2
Con x=2 (i passi precedenti sono ovviamente uguali)
Processi B C Disponibili Processi B Disponibili Corrente 2 0 1 1 0 1 1 0 1 0 2 1 5 3 2 Corrente 2 0 1 1 0 3 2 5 4 2 Massima 2 2 2 1 0 Necessaria 0 2 1 0 0 Massima 2 2 2 1 0 2 1 5 1 0 Necessaria 0 2 1 0 0 1 0 5 0 0
Sistemi Operativi 11/12
Deadlock
73
Esercizio 3
Un sistema ha 4 processi e 4 risorse allocabili. Lallocazione corrente e il massimo fabbisogno sono i seguenti:
Processi A B C D Allocate 1111 2010 Massime
Disponibili 1131
Sistemi Operativi 11/12
Deadlock
74
Esercizio 3
Un sistema ha 4 processi e 4 risorse allocabili. Lallocazione corrente e il massimo fabbisogno sono i seguenti:
Processi A B C D Allocate 1111 2010 2022 0211 Massime 2121 2432 5422 0341 Necessarie 1010 0422 3400 0130
Disponibili 1131
Richiesta B 0110
Sistemi Operativi 11/12
Deadlock
75
Esercizio 3
Un sistema ha 4 processi e 4 risorse allocabili. Lallocazione corrente e il massimo fabbisogno sono i seguenti:
Processi A B C D Allocate 1111 2120 2022 0211 Massime 2121 2432 5422 0341 Necessarie 1010 0312 3400 0130
Disponibili 1021
Il processo A pu terminare
Sistemi Operativi 11/12 Deadlock 76
Esercizio 3
Un sistema ha 4 processi e 4 risorse allocabili. Lallocazione corrente e il massimo fabbisogno sono i seguenti:
Processi C D Allocate 2022 0211 Massime 5422 0341 Necessarie 3400 0130
Disponibili 2132
Il processo D pu terminare
Sistemi Operativi 11/12 Deadlock 77
Esercizio 3
Un sistema ha 4 processi e 4 risorse allocabili. Lallocazione corrente e il massimo fabbisogno sono i seguenti:
Processi B C Disponibili 2343 Processi Allocate 2120 2022 Massime 2432 5422 Necessarie 0312 3400
Il processo B pu terminare
Allocate Massime Necessarie
Disponibili 4463
Sistemi Operativi 11/12
Il processo C pu terminare
Deadlock 78
Esercizio 3
Un sistema ha 5 processi e 4 risorse allocabili. Lallocazione corrente e il massimo fabbisogno sono i seguenti:
Processi A B C D E Disponibili 2 2 10 4
Sistemi Operativi 11/12
Allocate 4X32 80Y2 4000 0032 21Z4
Massime 6456 10 7 6 8 6208 0342 9169
Deadlock
79
Esercizio 3
Un sistema ha 5 processi e 4 risorse allocabili. Lallocazione corrente e il massimo fabbisogno sono i seguenti:
Processi A B C D E Allocate 4X32 80Y2 4000 0032 21Z4 Massime 6456 10 7 6 8 6208 0342 9169 Necessarie 2 4-X 2 4 2 7 6-Y 6 2208 0310 7 0 6-Z 5
Disponibili 2 2 10 4
Solo A pu terminare purch 4X2
Sistemi Operativi 11/12
Deadlock
80
Esercizio 3
Un sistema ha 5 processi e 4 risorse allocabili. Lallocazione corrente e il massimo fabbisogno sono i seguenti:
Processi B C D E Allocate 80Y2 4000 0032 21Z4 Massime 10 7 6 8 6208 0342 9169 Necessarie 2 7 6-Y 6 2208 0310 7 0 6-Z 5
Disponibili 6 2+X 13 6
D pu terminare
Sistemi Operativi 11/12
Deadlock
81
Esercizio 3
Un sistema ha 5 processi e 4 risorse allocabili. Lallocazione corrente e il massimo fabbisogno sono i seguenti:
Processi B C E Allocate 80Y2 4000 21Z4 Massime 10 7 6 8 6208 9169 Necessarie 2 7 6-Y 6 2208 7 0 6-Z 5
Disponibili 6 2+X 16 8
C pu terminare
Sistemi Operativi 11/12
Deadlock
82
Esercizio 3
Un sistema ha 5 processi e 4 risorse allocabili. Lallocazione corrente e il massimo fabbisogno sono i seguenti:
Processi B E Disponibili 10 2+X 16 8 Processi B Disponibili 12 3+X 16+Z 12
Sistemi Operativi 11/12
Allocate 80Y2 21Z4
Massime 10 7 6 8 9169
Necessarie 2 7 6-Y 6 7 0 6-Z 5
E pu terminare 6Z0
Allocate 80Y2 Massime 10 7 6 8 Necessarie 2 7 6-Y 6
B pu terminare se X=4 e 6Y0
Deadlock 83