Esempio di esecuzione che è sequenzialmente coerente ma non quiescostante coerente

Question

Nel contesto della correttezza dei programmi concorrenti, la coerenza sequenziale è più forte della coerenza quiescente secondo L'arte della programmazione multiprocessore di Maurice Herlihy e Nir Shavit (capitolo 3) Autori menzionare anche in 3.4.1 che ci sono esecuzioni coerentemente sequenziali che non sono costantemente coerenti. Non capisco come. Qualcuno potrebbe lanciare una luce o fornire un'esecuzione del campione?

Answer 1

Considerare uno queue (FIFO) a cui si accodano e si rimuovono gli elementi.

Da this dissertation sulla concomitanza, ho letto (p.20):

Un esempio di uno scenario che viene ammesso nel modello sequenziale consistenza e annullato nel modello consistenza quiescente è mostrato in Figura 2.1 . Due processi condividono una struttura di dati della coda concorrente. Il processo esegue l'accodamento x. Ad un intervallo successivo non sovrapposto, , un secondo processo accoda y. Infine, il secondo processo esegue un dequeue e riceve y. Questo esempio è coerente in modo sequenziale ma è non uniforme, supponendo che il tempo tra le operazioni di accodamento non rientri nell'intervallo di quiescenza.

Figura 2.1:

T1: --- enq(x) --------------------------- 
T2: ------------- enq(y) ---- deq():y ---- 

Questa storia è consentita dalla consistenza sequenziale, può essere sia permesso o proibito dalla consistenza quiescente, ed è proibito dalla consistenza linearizzabile.

Se si assume che tra i due accodati la coda fosse inattiva, allora T2 dovrebbe vedere le modifiche da T1 e la dequeue deve restituire x. Se si presuppone che non vi sia stato alcun intervallo di quiescenza tra i due accodamenti, allora due accodamenti possono essere ripetuti come si desidera e deq(): y è coerente.