deadlock ::: Dizionario Informatico

Deadlock: ingl., blocco critico, stallo. In un ambiente multiprogrammato o distribuito più processi possono entrare in competizione per ottenere un numero finito di risorse. Un processo richiede una risorsa, e se in quel momento essa non è disponibile, viene messo in attesa. Può capitare che un processo in attesa non cambi più il suo stato, perché altri processi, ma anche il processo stesso, trattiene le risorse richieste senza mai rilasciarle.
Situazioni di questo tipo sono dette di deadlock; il termine in italiano potrebbe essere tradotto anche come blocco di inattività.
Affinché possa avvenire un deadlock devono essere simultaneamente soddisfatte quattro condizioni necessarie e sufficienti:

mutua esclusione: deve esistere almeno una risorsa condivisa e il cui possesso è mutuamente esclusivo, ovvero, non più di un'entità alla volta può utilizzarla;
possesso & attesa: ogni entità deve poter possedere una risorsa e mentre ne trattiene il possesso mettersi in attesa di possedere un'altra;
mancanza di preemption: non devono esistere meccanismi per cui le risorse possono essere sottratte di forza ai processi che le posseggono;
presenza di cicli di attesa: nel grafo di 'possesso-attesa' deve essere presente un ciclo.

Nel caso che almeno una di queste non sia soddisfatta, allora non avverrà un deadlock in nessun caso.
Un esempio concreto di deadlock è dato da quello che in gergo automobilistico è detto incrocio di cortesia. Si tratta di un incrocio privo di semafori a cui giungono contemporaneamente quattro macchine, una per direzione, che devono attraversarlo per preseguire diritte lungo la propria direzione; ciascuna deve dare la precedenza a quella che sta alla propria destra.
È facile notare che il deadlock avviene in quanto sono soddisfatte le quattro condizioni, infatti:

vi è una risorsa condivisa in mutua esclusione, ed è la possibilità di attraversare l'incrocio in uno dei tre modi previsti dal codice stradale (proseguire diritti, svoltare a destra o svoltare a sinistra);
ogni macchina può manifestare la propria intenzione di attraversare l'incrocio (in uno dei tre modi) e poi mettersi in attesa che la macchina che sta alla propria destra abbia completato a sua volta la manovra per cui ha la precedenza;
non è presente l'impianto semaforico, così come non vi sono vigili urbani che dirigono il traffico;
il ciclo è facilmente individuabile nel caso in cui ogni macchina manifesti contemporaneamente alla altre la volontà di attraversare in linea retta l'incrocio.

Facendo cadere anche solo una di queste condizioni non avverrebbe mai deadlock, ad esempio:

se fosse possibile solo svoltare a destra il problema non si porrebbe;
qualora almeno una automobile non dia la precedenza a quella alla propria destra oppure non segnali correttamente la propria manovra non vi saranno stalli (anche se questo porterebbe con molta probabilità ad un incidente);
i semafori esistono apposta per evitare ingorghi di questo tipo;
fintanto che le automobili non sappraggiungano contemporaneamente all'incrocio, oppure non intendono preseguire diritte non vi saranno problemi.

Come ultima nota, possiamo osservare che il deadlock si avrebbe anche nel caso in cui le quattro macchine volessero svoltare a sinistra. Cfr. Starvation.
[di Marco Lizza]

N.d.a. Il deadlock comparve già negli anni Sessanta nel sistema concorrente di IBM, il Sistema/360 [MUI-2008,p.36], lanciato nel mercato il 7 aprile 1964.

[rev.: 01-2009]

Termini mancanti / suggerimenti?