Transazioni - Come evitare i deadlock?

Question

Mi è stato chiesto questa domanda in un .net/C# intervista:

se abbiamo due thread T1 e T2. T1 acquisisce un blocco su obj1 e quindi esegue l'elaborazione e acquisisce un blocco su obj2. T2 acquisisce un blocco su obj2 e quindi esegue un po 'di elaborazione e acquisisce un blocco su obj1. Quindi, possiamo avere un deadlock . Qual è la tecnica comune che usiamo nel multithreading per evitare questa situazione?

ho risposto dicendo che T1 e T2 dovrebbe avere qualche meccanismo per comunicare e che dovremmo fare la codifica in modo tale che T2 comincia a fare il suo lavoro solo dopo che T1 ha segnalato che si è fatto con il suo lavoro. L'intervistatore mi ha chiesto se conoscevo le transazioni e come possiamo usarle per affrontare questa situazione di deadlock. Ho una certa esperienza di multithreading nell'interfaccia utente in winforms. Ma non ho mai usato le transazioni. Qualcuno può dirmi di più su questo o indicarmi un url/book,

Answer 1

Un approccio generale per evitare i deadlock è garantire che i thread/processi acquisiscano blocchi sulle risorse nello stesso ordine. ad esempio, T2 dovrebbe bloccare prima obj1 e poi obj2 (lo stesso di T1).

In questo modo non è possibile avere entrambi i thread in possesso di una risorsa che l'altro thread desidera, ovvero un deadlock.

Se la formulazione nella tua citazione era la domanda esatta, è scritta male. Dovrebbe essere:

T1 acquisisce un blocco su obj1, fa qualcosa e poi prova a bloccare anche obj2 obj1 senza sbloccare. Allo stesso tempo T2 acquisisce un blocco su obj2, fa qualcosa e quindi prova a bloccare anche obj1 senza sbloccare obj2. Si verificherà un deadlock .

Consiglio vivamente di leggere Concurrent Programming on Windows di Joe Duffy. È probabilmente il libro più completo sulla teoria e la pratica del threading per Windows.

Answer 2

Un approccio è che tutti i processi devono acquisire tutti i blocchi all'inizio della transazione. Se alcuni non sono disponibili, il processo rilascia tutti i blocchi e riprova. A seconda dell'implementazione, questo può comunque portare a livelli di sviluppo.

Per visualizzare il problema dall'altra estremità, vedere Dijkstra's banker's algorithm.

Answer 3

Non sono del tutto sicuro in cui le transazioni vengono direttamente in questo oltre alla possibilità di eseguire il rollback. La cosa principale IMO è di acquisire le serrature in un ordine coerente, e presto; oh, e usa un timeout quando acquisisci le serrature - non stare lì fermo per sempre.

Il riferimento alle operazioni mi fa pensare principalmente da basi di dati, in questo caso un'altra considerazione è quello di utilizzare trucchi come UPDLOCK per essere sicuri di ottenere un blocco di scrittura inizialmente per evitare problemi che promuovono un (impugnata) lettura di blocco per una scrittura -lock (passando da un deadlock a un semplice blocco). Naturalmente, molti database hanno anche un migliore deadlock detection rispetto alla maggior parte dei normali codici.

Answer 4

Penso che la cosa a cui si riferiva l'intervistatore sia la possibilità di eseguire il rollback di una transazione. Il rollback della transazione annullerà tutte le modifiche apportate dalla transazione come se la transazione non fosse mai avvenuta. Rilascerà anche tutti i blocchi ottenuti da esso.

Ora ogni thread dell'esempio utilizza la propria transazione (nel database, nel file system Vista o in altre interfacce che supportano le transazioni). Se il deadlock si verifica (può essere rilevato facilmente una volta che si verifica), ne selezionerai uno dai thread che fanno parte del deadlock (vittima) e esegui il rollback della transazione. Ciò sbloccherà i blocchi in modo che il thread rimanente possa continuare. Il thread della vittima potrebbe riprovare la transazione.

Se la probabilità di deadlock è bassa rispetto al costo di riprovare l'intera transazione, questa potrebbe essere una soluzione utilizzabile.