Deadlock — puzzle sull’ordine dei lock
Riordina come i thread prendono i lock così che nessuno attenda per sempre. Un enigma sulla regola dell’ordine globale dei lock.
Riordina ogni thread così che nessuno attenda un altro per sempre.
- 🔒 A
- 🔒 B
- 🔒 B
- 🔒 A
Come si gioca
- Ogni riga è un thread e i gettoni sono i lock che prende, da sinistra a destra.
- Trascina un gettone (o usa le frecce) per cambiare l’ordine in cui un thread acquisisce i lock.
- Se due thread prendono la stessa coppia in ordine opposto possono bloccarsi per sempre. La soluzione è un unico ordine globale rispettato da tutti — premi Esegui per verificare.
Come funziona
Ogni riga è un thread e ogni gettone un lock che acquisisce, da sinistra a destra. Se due thread prendono la stessa coppia in ordine opposto, esiste un intreccio in cui ciascuno ne tiene uno e attende l’altro — e nessuno avanza più. Premi Esegui: il grafo di attesa viene controllato per un ciclo e, se c’è, i lock colpevoli si illuminano di rosso. La soluzione è la regola delle basi di codice reali: scegliere un ordine globale dei lock e rispettarlo ovunque.
Un enigma didattico. Modella i cicli hold-and-wait, la condizione di deadlock eliminabile per progettazione; i sistemi reali usano anche timeout, strutture lock-free e devono considerare il livelock.
Domande frequenti
Cosa causa davvero un deadlock qui?
Un ciclo nel grafo di attesa. Se il thread 1 tiene A e vuole B mentre il thread 2 tiene B e vuole A, entrambi attendono per sempre. Il gioco disegna esattamente quel ciclo.
Perché ordinare i lock risolve?
Se tutti i thread acquisiscono i lock nello stesso ordine globale, un ciclo è impossibile: un thread può attendere solo un lock successivo a quelli che tiene, quindi il grafo resta aciclico. È la classica regola di gerarchia dei lock.
I deadlock reali si trovano così?
Il controllo del ciclo è la stessa idea dei rilevatori di inversione d’ordine come ThreadSanitizer. Gli strumenti reali osservano l’ordine a runtime; qui vedi tutto il grafo in una volta.