In
informatica
, lo
stallo
o
deadlock
[1]
indica una situazione in cui due o piu
processi
o azioni si bloccano a vicenda, aspettando che uno esegua una certa azione (es. rilasciare il controllo su una
risorsa
come un
file
, una porta
input/output
ecc.) che serve all'altro e viceversa.
Un esempio e rappresentato da due persone che vogliono disegnare: hanno a disposizione solo una riga e una matita e hanno bisogno di entrambe. Potendo prendere un solo oggetto per volta, se uno prende la matita, l'altro prende la riga, e se entrambi aspettano che l'altro gli dia l'oggetto che ha in mano, i due generano uno stallo.
Questa situazione puo esser vista come un
paradosso
e non puo essere risolta, ma si puo prevenire. Applicazioni che sono tipicamente soggette agli stalli sono le
basi di dati
, nel caso in cui ci siano richieste circolari di accesso esclusivo da parte di diverse transazioni sulle stesse risorse, oppure i
sistemi operativi
che gestiscono l'accesso contemporaneo a file e a dispositivi di I/O di diversi processi.
In un
deadlock
si verificano sempre queste condizioni, dette anche di Havender:
- Mutua esclusione: almeno una delle risorse del sistema deve essere 'non condivisibile' (ossia usata da un processo alla volta oppure libera).
- Accumulo incrementale: i processi che possiedono almeno una risorsa devono attendere prima di richiederne altre (gia allocate ad altri processi).
- Impossibilita di prelazione: solo il processo che detiene la risorsa puo rilasciarla.
- Attesa circolare: esiste un gruppo di processi {P
0
,P
1
,...,P
n
} per cui P
0
e in attesa per una risorsa occupata da P
1
, P
1
per una risorsa di P
2
, ecc. P
n
per una risorsa di P
0
.
Una situazione di
deadlock
puo essere riconosciuta analizzando il
grafo delle attese
dei processi del sistema.
I
deadlock
si possono verificare solo se sono presenti contemporaneamente le quattro condizioni di cui sopra (che sono quindi necessarie).
Le condizioni diventano anche sufficienti nel caso di una sola istanza per ciascun tipo di risorsa.
E una soluzione possibile solo se il sistema e capace di mantenere delle informazioni sulle risorse disponibili e sulle risorse che ogni processo puo potenzialmente richiedere.
Si definisce
stato sicuro
di un sistema quando e possibile eseguire i processi in una sequenza tale per cui, allocando ad ognuno di essi tutte le risorse che potenzialmente puo richiedere, gli si permetta di terminare la propria esecuzione e quindi evitare il
deadlock
. Se il sistema si trova in uno stato sicuro il deadlock puo essere evitato, ma uno stato non sicuro non implica necessariamente un deadlock.
Il sistema puo dunque evitare del tutto gli stalli se, ad ogni richiesta di una risorsa da parte di un processo, effettua una verifica dello stato in cui si troverebbe allocando la risorsa. Se lo stato e sicuro la risorsa puo essere tranquillamente allocata. A tal fine si puo utilizzare l'
algoritmo del banchiere
.
Tuttavia, per la maggior parte dei sistemi e impossibile conoscere in anticipo le risorse che richiedera un processo, per cui e spesso impossibile evitare del tutto i deadlock.
In questo caso si cerca di evitare i deadlock annullando una o piu delle condizioni di cui sopra: essendo esse collettivamente sufficienti basta infatti invalidarne una.
Per esempio:
- Annullando la condizione di mutua esclusione e permettendo l'accesso contemporaneo ad una stessa risorsa da parte di diversi processi (es. file aperti in lettura). Puo essere impossibile come nei casi di scrittura su file o accesso ad una risorsa senza
spooling
.
- Si puo richiedere ad un processo di richiedere tutte le risorse di cui dovra disporre all'avvio oppure con la convenzione di rilasciare una risorsa prima di richiederne un'altra. Spesso questa soluzione non e praticabile o poco efficace. Tuttavia e utilizzata nei database che fanno uso di
two-phase locking
.
- Permettere la prelazione, il che quindi permetterebbe a un processo di rilasciare la risorsa detenuta da un altro processo: cio puo lasciare l'applicazione
vittima
in uno stato incoerente, dato che finisce per perdere una risorsa che stava utilizzando.
- L'attesa circolare si puo risolvere permettendo ad ogni processo di richiedere solo una risorsa alla volta oppure imponendo un ordinamento (o una gerarchia) sui processi e prevenire in tal modo la formazione di cicli nel grafo delle attese.
Quando non e possibile evitare o prevenire i deadlock si possono solo definire degli algoritmi per riconoscere e risolvere gli stati di deadlock.
Per quanto riguarda la risoluzione, si puo procedere con la terminazione di tutti i processi in stallo o di un processo per volta fino alla risoluzione del deadlock, oppure con la prelazione sulla risorsa che causa il problema. Particolare cura deve essere riposta nella scelta della
vittima
della prelazione.
In presenza di un
sistema distribuito
(come per esempio un database risiedente su diversi server), riconoscere una situazione di potenziale deadlock si rende ancora piu complessa. In genere la rivelazione del possibile stato insicuro puo essere effettuata solo ricostruendo il
grafo delle attese
globale a partire da quelli locali o con particolari algoritmi (vedi la variante distribuita del
two-phase locking
).
Tuttavia, la possibilita che il grafo delle attese globale non rifletta sempre correttamente l'effettivo stato del sistema distribuito, puo rivelare dei
deadlock
inesistenti (
phantom deadlocks
) che sono gia stati risolti perche uno dei processi ha terminato la sua esecuzione nel frattempo o che non sono mai esistiti realmente.
L'approccio consiste nell'assumere che il
deadlock
non avverra mai. Se l'intervallo di tempo tra i
deadlock
e sufficientemente grande e la perdita di dati tollerabile, si puo applicare l'
algoritmo dello struzzo
[2]
ignorando di fatto l'esistenza dei
deadlock
. Questo puo essere fatto in modo sicuro se viene
provato formalmente
che i
deadlock
non si verificheranno mai. Il framework RTIC utilizza questo metodo.
[3]
Si definisce "stato sicuro" uno stato in cui e possibile allocare tutte le
risorse
richieste da un processo senza che questo finisca in un
deadlock
.
Il fatto che il sistema si trovi in uno stato sicuro non implica che tutte le allocazioni avverranno con successo, ma solo che esiste almeno un modo per allocare tutte le risorse. Se il sistema si trova in uno stato sicuro il deadlock puo essere evitato, ma uno stato non sicuro non implica necessariamente un deadlock.
Il sistema puo dunque evitare del tutto gli stalli se, ad ogni richiesta di una risorsa da parte di un processo, effettua una verifica dello stato in cui si troverebbe allocando la risorsa. Se lo stato e sicuro la risorsa puo essere tranquillamente allocata. A tal fine si puo utilizzare l'
algoritmo del banchiere
.
Tuttavia, per la maggior parte dei sistemi e impossibile conoscere in anticipo le risorse che richiedera un processo, per cui e spesso impossibile evitare del tutto i deadlock visto che non si puo determinare in anticipo se un futuro stato sara sicuro.