Assicurare che il sistema non entri mai in uno stato di deadlock.
Permettere al sistema di entrare in uno stato di deadlock, quindi ripristinare il sistema.
Ignorare il problema e fingere che i deadlock non avvengano mai nel sistema;
Mutua esclusione — in generale non è richiesta per risorse condivisibili (es. file in sola lettura), ma alcune risorse non possono essere condivise quindi in generale non è possibile prevenire i deadlock evitando la condivisione delle risorse (es. File in scrittura).
Possesso e attesa — evitare “possesso e attesa” significa “non possedere” oppure “non attendere”. Quindi:
Impossibilità di prelazione:
Attesa circolare — si impone un ordinamento totale su tutti i tipi di risorsa e si pretende che ciascun processo richieda le risorse in ordine crescente.
Ordinamento delle risorse
1 : stampante
2: scanner
3: plotter
4: unita’ nastro
5: unita’ CD
Due risorse: R e S
↓
Assenza di cicli
Presuppone che il sistema conosca a priori informazioni addizionali sulle richieste future dei processi.
Una sequenza <P1, P2, …, Pn > è sicura se, per ogni Pi, le risorse che Pi può ancora richiedere possono essergli allocate sfruttando le risorse disponibili + le risorse possedute da tutti i Pj, con j < i.
La matrice di allocazione di una risorsa riporta, per ogni processo, il numero di istanze possedute e il massimo numero di istanze che utilizzerà.
Lo stato a) e’ sicuro, infatti.
Se però dallo stato (a) si assegna una ulteriore istanza al processo P1 si ottiene uno stato non sicuro (stato b) che conduce a un deadlock (stato d).
Osservazione: nello stato (b), anche assegnando le 2 risorse libere a P1 o P3 (invece che a P2) si ottiene un deadlock.
IDEA : in base delle risorse disponibili soddisfare prima le richieste di un processo che, può completare la propria esecuzione, permettendo così il rilascio di tutte le risorse in suo possesso.
Ciascun processo deve dichiarare a priori il massimo impiego di risorse.
Quando un processo richiede una risorsa si verifica prima che il nuovo stato sia uno stato sicuro. In caso contrario il processo attende.
Il nome deriva dal fatto che esso può essere applicato in una banca per evitare che il cassiere consegni tutto il denaro disponibile (le risorse), e non possa piuù soddisfare le richieste di tutti i suoi clienti (i processi).
Dati necessari per l’algoritmo nel caso di
( Need [ i ] = Max [ i ] – Allocation [ i ] )
Sia Request [i ], numero di istanze richieste dal processo Pi.
Se Request [i ] ≤ Need [i ] , si vada al passo 2. Altrimenti, si riporti una condizione di errore, poiché il processo ha ecceduto il massimo numero di richieste.
Se Request [i ] ≤ Available , si vada al passo 3. Altrimenti Pi deve attendere, poiché le risorse non sono disponibili.
Il sistema simula l’allocazione al processo Pi delle risorse richieste, modificando lo stato di allocazione delle risorse come segue:
Available = Available – Request [i ]
Allocation [i ] = Allocation [i ] + Request [i ]
Need [i ] = Need [i ] – Request [i ]
Come fare a vedere se uno stato e’ sicuro?
Cerchiamo una sequenza sicura
Siano Finish vettore di lunghezza n e Work un intero. Si inizializzi:
Si cerchi i tale che valgano contemporaneamente:
Se tale i non esiste, si esegua il passo 4.
Se Finish [i ] == true per ogni i, il sistema è in stato sicuro.
Finish[1] = Finish[2] = Finish[3] = false
Work = Available = 3
i=1 Need[1] _ Work e Finish[i ] = false ? no
i=2 Need[2] _ Work e Finish[2 ] = false ? Si
Work = 3+2 = 5 Finish[2] = true
i=1 Need[1 ] _ Work e Finish[1 ] = false ? no
i=2 Need[2 ] _ Work e Finish[2] = false ? no
i=3 Need[3 ] _ Work e Finish[3 ] = false ? Si
Work = 5+2 = 7 Finish[3] = true
i=1 Need[1 ] _ Work e Finish[1 ] = false ? Si
Work = 7+3 = 10 Finish[1] = true
Fine → Stato sicuro
La sequenza <P2, P3, P1 > soddisfa i criteri di sicurezza
(Finish[i] == true per ogni i)
Finish[1] = Finish[2] = Finish[3] = false
Work = Available = 2
i=1 Need[1] _ Work e Finish[1 ] = false ? no
i=2 Need[2] _ Work e Finish[2 ] = false ? Si
Work = 2+2 = 4 Finish[2] = true
i=1 Need[1 ] _ Work e Finish[1 ] = false ? no
i=2 Need[2 ] _ Work e Finish[2] = false ? no
i=3 Need[3 ] _ Work e Finish[3 ] = false ? no
dopo P2 nessuno riesce a terminare
(Finish[1] = Finish[3] = false )
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
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
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.