Sono interessato alla ricerca che rileva e recupera da deadlock. In altre parole, il sistema è in grado di recuperare da errori di deadlock. Sono interessato ai processori multicore a memoria condivisa. In questo momento ho visto solo la ricerca di sistemi distribuiti. Qualcuno può guidarmi su questo.
Non sono sicuro di cosa intendi per recuperare , perché dal momento che sei in una situazione di stallo - sei ovviamente in uno stato in cui due thread dipendono l'uno dall'altro per completare le attività correnti . Quindi il recupero sarebbe per uno di loro (o entrambi ...) non completare il compito.
In molti casi, specialmente nei sistemi basati su eventi incorporati, il rilevamento viene eseguito tramite il watchdog hardware che riavvia il sistema. Questo può essere considerato un meccanismo di recupero.
Ovviamente puoi essere meno rigoroso e invece di riavviare il sistema, spegnere uno dei thread offensivi (o tutti) e riavviarli, assicurandoti che la situazione di deadlock possa essere evitata in futuro (eliminando il male input per esempio).
Oppure puoi semplicemente sbloccare la chiamata di blocco e lasciare che i thread vengano eseguiti con (potenzialmente) dati corrotti. Di nuovo, dipende dal tuo sistema e dai motivi del deadlock.
La linea di fondo - watchdog (hardware o software) è la soluzione, ma se stai usando la versione del software - devi assicurarti che non sia mai bloccata da sola (per esempio: eseguire su una CPU dedicata per esempio) .
Ah, e il migliore di tutti è, naturalmente, non entrare completamente in una situazione di stallo. Puoi verificare il tuo codice usando il model checking o le simulazioni, ma ovviamente è più facile dirlo e farlo, anche se hai verificato il modello, potresti ancora avere bug nell'implementazione del codice reale ....
Il modo migliore per recuperare da una condizione di deadlock è non entrarci mai prima.
Tecniche come Tony Hoare La comunicazione di processi sequenziali ti dà la possibilità di ragionare formalmente sul tuo sistema, rilevare il potenziale di deadlock e progettarlo dal tuo sistema. Consiglio vivamente di esaminare alcuni dei lavori fatti su CSP nel corso degli anni per vedere se queste tecniche potrebbero essere incorporate nei vostri sistemi.
Un esempio di "deadlock avoidance" è l'uso dei lock del reader-writer. Lo schema di base è che se hai un lucchetto (il lettore) e cerchi di acquisire l'altro (scrittore) ma non puoi, allora devi abbandonare e riprovare l'intera operazione.
In teoria, questo potrebbe essere usato come un meccanismo di recupero deadlock - in una classica situazione di inversione di blocco, dove due thread hanno un blocco che l'altro vuole, quindi uno o entrambi potrebbero tornare al punto in cui hanno acquisito il primo blocca e riprova (non tutti e due contemporaneamente, altrimenti si bloccheranno di nuovo!). Ma questo è limitato come mezzo di tolleranza agli errori, poiché richiede la cooperazione dai thread. In caso negativo, ogni thread potrebbe aver inserito una struttura dati in uno stato inconsistente in cui non sa come uscire, solo come completare. Quindi l'errore non è recuperabile. In molti casi è più difficile evitarlo, piuttosto che evitare l'inversione del blocco.
Quei sistemi distribuiti per i quali hai visto la ricerca, potrebbero avere il vantaggio che se una serie di nodi entra in uno stato di stallo sfortunato, possono essere tutti uccisi e i loro contributi ignorati. Per fare ciò nel caso cattivo che descrivo sopra, avresti bisogno di una qualche forma di memoria transazionale, che è difficile (e attivamente ricercata). Ma ovviamente puoi sempre scrivere il tuo codice multi-core come se fosse codice distribuito (condividi niente tra i thread), quindi usa le tecniche per il codice distribuito.
Rilevare un'inversione di blocco per i mutex è banale in principio, dal momento che è possibile tracciare un grafico diretto delle dipendenze di ciascun thread su altri thread (A dipende da B se B contiene un blocco su cui è in attesa A) e controllare i cicli. Rilevare deadlock su semafori o variabili di condizione è impossibile a meno che non si riesca a fare abbastanza analisi statiche per determinare quale thread è "supposto" per postare ogni semaforo su cui è in attesa un altro thread, o si suppone che sia vero che un altro thread deve essere vero prima continuando.
Dare un'occhiata a Real-Time Systems and Programming Languages di Burns and Wellings. Discute i modi per prevenire deadlock in tempo reale e fa un buon lavoro con la citazione di documenti.
Non devo prenotare con me al lavoro, ma guardando il ToC che hai:
4.7 Multiprocessor and distributed systems
5.10 Shared memory multiprocessors
11.14 Multiprocessor scheduling
Conosco i sistemi di database (dove tutte le serrature sono tenute in un posto e possono essere analizzate), la pratica comune è quella di fare di un thread la "vittima del deadlock" e ucciderlo, liberando così il blocco. Ciò potrebbe essere complicato in un ambiente di sistema operativo, dal momento che un singolo thread / processo potrebbe avere diversi blocchi su parti diverse del sistema, quindi raccogliere una vittima deadlock potrebbe richiedere una significativa introspezione e analisi. Inoltre, riprovare una transazione fallita a causa di un deadlock è un idioma di database piuttosto standard, ma non così comune nella programmazione delle applicazioni.