Deadlock

Nella lezione del 9/11 abbiamo affrontato il tema dello stallo dei processi (e dei thread). Si verifica una situazione di stallo o deadlock quando esiste un gruppo di processi, tale che ciascun processo del gruppo attende un evento che solo altri processi dello stesso gruppo possono causare.

Esistono quattro condizioni necessarie per il verificarsi dello stallo:

• Hold & wait: i processi devono poter richiedere risorse mentre ne detengono delle altre (i.e., per un nodo-processo nel grafo di allocazione devono poter esistere contemporanemente archi in uscita ed in ingresso);
• Mutual exclusion: le risorse devono essere accessibili in mutua esclusione;
• No preemption: se un processo detiene una risorsa, deve essere l'unico a poterla rilasciare;
• Circular wait: deve esistere un cammino circolare nel grafo di allocazione delle risorse.

Abbiamo poi visto i possibili metodi di gestione del deadlock:

• Ignorarlo (algoritmo dello struzzo)
• Riconoscerlo (attraverso l'analisi del grafo delle risorse) e risolverlo (uccidendo, sospendendo o riportando ad uno stato precedente uno dei processi coinvolti nell'attesa circolare)
• Evitarlo (deadlock avoidance): in particolare attraverso l'algoritmo del banchiere
• Prevenirlo (deadlock prevention), rendendo impossibile il verificarsi di una delle quattro condizioni necessarie:
  • Hold & wait: forzando i processi a richiedere le risorse in modo atomico, o a rilasciare tutte le risorse prima di mettersi in attesa;
  • Mutual exclusion: attraverso lo spooling delle risorse;
  • No preemption: usando metodi di checkpoint & rollback o sospensione dei processi;
  • Circular wait: obbligando i processi ad acquisire le risorse in un ordine predefinito.