In che modo il timestamping può causare un "deadlock globale"?

Question

Sto leggendo alcuni dei vantaggi/svantaggi dell'uso dei timestamp per il controllo della concorrenza in un database distribuito. Il materiale che sto leggendo menziona che anche se i timestamp superano i tradizionali problemi di stallo che possono influenzare il blocco, c'è ancora il problema dello "stallo globale" a cui è vulnerabile.

Il materiale descrive il deadlock globale come una situazione in cui non esiste alcun ciclo nei grafici di attesa dei grafici locali, ma che esiste un ciclo nel grafico globale.

Mi chiedo come potrebbe accadere? Qualcuno potrebbe descrivere una situazione in cui un sistema di timestamp potrebbe causare questo problema?

Answer 1

Ecco un esempio, probabilmente il più semplice possibile. Abbiamo macchine A e B. La macchina A ha blocchi T1 e T2 con la relazione T1 < T2. Macchina B ha T3 e T4 con T3 > T4.

Ora, i grafici locali sono solo che T2 deve attendere che T1 e T3 debbano attendere T4. Quindi non ci sono cicli locali. Ma ora, supponiamo di avere T4 < T1 così T1 deve aspettare T4. E allo stesso tempo T2 < T3 quindi T3 deve attendere T2. In questo caso, c'è un ciclo globalmente.

Quindi, come si verifica questo ciclo? La chiave qui è che non hai mai le informazioni complete in un sistema distribuito. Quindi potremmo apprendere in seguito che le dipendenze inter-macchina ci sono. E poi abbiamo un problema.

Answer 2

Il timestamp viene utilizzato per determinare la risoluzione dei conflitti tra i processi locali su una macchina. Fornisce un mezzo per risolvere i deadlock a quel livello. Per i processi distribuiti è possibile che due processi su macchine diverse siano in attesa l'uno sull'altro. Che è in effetti un deadlock regolare, ma attraverso le macchine. Questo è chiamato un deadlock 'globale'. Il timestamping di Imho potrebbe essere usato anche lì, ma è apparentemente poco pratico.

Alcune informazioni su questo possono essere trovate su http://www.cse.scu.edu/~jholliday/dd_9_16.htm