Un deadlock è una situazione in cui due programmi per computer che condividono la stessa risorsa impediscono a vicenda di accedere alla risorsa, determinando che entrambi i programmi cessano di funzionare.
I primi sistemi operativi per computer eseguivano un solo programma alla volta. Tutte le risorse del sistema erano disponibili per questo programma. Successivamente, i sistemi operativi eseguivano più programmi contemporaneamente, alternandoli. I programmi dovevano specificare in anticipo le risorse di cui avevano bisogno in modo da evitare conflitti con altri programmi in esecuzione contemporaneamente. Alla fine, alcuni sistemi operativi offrivano un'allocazione dinamica delle risorse. I programmi potrebbero richiedere ulteriori allocazioni di risorse dopo che avevano iniziato a funzionare. Ciò ha portato al problema della situazione di stallo. Ecco l'esempio più semplice:
Il programma 1 richiede la risorsa A e la riceve. Il programma 2 richiede la risorsa B e la riceve. Il programma 1 richiede la risorsa B e viene messo in coda, in attesa del rilascio di B. Il programma 2 richiede la risorsa A e viene messo in coda, in attesa del rilascio di A.
Ora nessuno dei due programmi può procedere fino a quando l'altro programma non rilascia una risorsa. Il sistema operativo non può sapere quale azione intraprendere. A questo punto l'unica alternativa è abortire (fermare) uno dei programmi.
Imparare a gestire i deadlock ha avuto un impatto importante sullo sviluppo dei sistemi operativi e sulla struttura dei database. I dati sono stati strutturati e l'ordine delle richieste è stato limitato per evitare la creazione di deadlock.