Torna alla pagina di Sistemi Operativi
:: Appunti caotici ::
Lezione 1
Caratterizzazione del deadlock
Pag 1
Sommario
...
Pag 2
Uso di risorse condivise
Il fenomeno degli stalli ricorre quando più processi vogliono accedere contemporaneamente a risorse condivise.
Problema del deadlock
Il disegnetto rappresenta la strettoia in una via a doppio senso di marcia.
Pag 3
Condizioni per il verificarsi del deadlock
Si ha deadlock se si verificano simultaneamente le seguenti condizioni:
- mutua esclusione (mutual exclusion), altrimenti la risposta potrebbe dare risposte con informazioni non consistenti
- possesso e attesa (hold & wait)
- no rilascio anticipato (no pre-emption). Con la pre-emption non avrei deadlock, dal momento che non potrei bloccare l'accesso alla risorsa: chi l'ha in uno la cede immediatamente a chi la chiede
- attesa circolare (circular wait), ovvero un processo detiene una risorsa richiesta da un altro processo che richiede a sua volta una risorsa detenuta da un altro processo che...
Se anche una sola di queste quattro condizioni non è verificata contemporaneamente allora non ho deadlock.
Grafo di allocazione delle risorse (1)
Per verificare la sussistenza di un deadlock viene utilizzato il grafo di allocazione delle risorse, coi nodi che rappresentano processi P e risorse R, a gli archi che rappresentano richieste (da P a R) o assegnazione (da R a P) di risorse. Per convenzione i nodi P son rappresentati con cerchi e le risorse con rettangoli, all'interno dei quali possono esserci più pallini che rappresentano le istanze di sé stesse che mettono a disposizione (nessun pallino equivale ad un'unica istanza).
Pag 4
Grafo di allocazione delle risorse (2)
Il grafo a sinistra rappresenta una situazione senza deadlock. In particolare:
- P1 ha richiesto R1, ma P2 l'aveva fatto prima di lui e infatti gli è stato assegnato l'accesso.
- R2 mette a disposizione due istanze, che pur essendo identiche possono essere usate in parallelo. Non ho conflitti dato che il principio di mutua esclusione si applica solo sulla stessa istanza
- P3 spezza la possibilità di formare un'attesa circolare. Non ha infatti richieste pendenti su altre risorse già occupate, quindi una volta terminato l'utilizzo di R3, lo rilascerà sbloccando P2 (e per propagazione anche P1)
Il grafo a destra rappresenta invece una situazione con deadlock. Si può infatti notare che si è formato un ciclo di attese tra P3, P2, R3 ed R2, con P2 e P3 che rimarrebbero indefinitamente bloccati. Gli altri processi potrebbero teoricamente andare avanti tranquillamente, a meno che prima o poi non abbiano bisogno di accedere alle risorse bloccate dal ciclo. Ad esempio nel nostro grafo P1 non potrà mai usare R1, dato che P2 si è bloccato e non lo rilascerà mai. Anche P1 quindi, pur non essendo direttamente coinvolto in un ciclo, è in situazione di stallo.
Grafo di allocazione delle risorse (3)
Se le risorse hanno più istanze, posso avere dei casi in cui si creino dei cicli senza però che cada in situazione di deadlock. Nel grafo della slide, abbiamo P2 e P4 che non sono direttamente coinvolti nel ciclo (tra P1, R1, P3 ed R2), e grazie a loro verranno liberate delle istanze in R1 e R2 che sbloccheranno la situazione.
Pag 5
Metodi di gestione dei deadlock
Il sistema operativo deve applicare dei metodi di gestione dei deadlock, o i miei processi non avanzerebbero più. Essi sono:
- ignorare il deadlock. Si è verificato? Amen. Posso permettermi di adottare tale strategia quando l'eventualità che accadano stalli sia rarissima, magari legata ad un errore hardware o software che avviene con frequenza molto bassa. Questa politica normalmente consente all'utente incazzato che non vede progredire il suo processo di killarlo o riavviare tutto il sistema. In questo modo, essendo raro il fenomeno di stallo, sarà difficile che si ripresentino nello stesso modo e con lo stesso ordine le stesse richieste alle risorse da parte dei processi che hanno condotto al precedente deadlock.
- prevenzione del deadlock (deadlock prevention), ovvero garantire nel momento in cui vengono fatte delle richieste (quindi a priori) che queste non vadano a generare situazioni di deadlock.
- evitare il deadlock (deadlock avoidance), che lascia effettuare le richieste e poi nel caso a posteriori le blocca.
- rilevazione e recupero del deadlock, anche qui in cui si suppone che la possibilità di avere stalli sia molto bassa.
Esistono diversi sistemi perché ognuno di questi comporta un carico diverso di lavoro sul processore, quindi posso decidere quale usare in base ai due fattori "criticità della presenza del deadlock nel sistema" (quanto posso permettermi di ignorarlo) e "uso di risorse di calcolo".
Torna alla pagina di Sistemi Operativi
