Przykład wykonania, który jest sekwencyjnie spójny, ale nie konsekwentnie spójny.

Question

W kontekście poprawności programów współbieżnych, Spójność sekwencyjna jest silniejszym warunkiem niż spójność spoczynkowa zgodnie ze sztuką programowania wieloprocesorowego autorstwa Maurice'a Herlihy'ego i Nira Shavita (rozdział 3). Autorzy wielu publikacji: Autorzy w 3.4.1 należy również wspomnieć, że istnieją sekwencyjnie spójne egzekucje, które nie są konsekwentnie spójne. Nie rozumiem jak. Czy ktoś mógłby rzucić światło lub wykonać próbną egzekucję?

Answer 1

Rozpatrz numer queue (FIFO), do którego zapisujesz i usuwasz elementy.

Z this dissertation o współbieżności, że odczyt (str.20):

Przykładem sytuacji, które są dozwolone w sekwencyjnej konsystencji modelu, dozwolona w spoczynku modelu konsystencji pokazano na Figurze 2.1 . Dwa procesy współdzielą współbieżną strukturę danych kolejki. Pierwszy proces zapisuje x. W pewnym nie nakładającym się kolejnym przedziale, , drugi proces wpisuje y. Na koniec drugi proces wykonuje deklinację i odbiera y. Ten przykład jest sekwencyjnie spójny, ale nie jest spójny, przy założeniu, że czas między kolejnymi operacjami spadnie poza okres spoczynku.

Figura 2.1:

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

Historia ta jest dozwolone przez kolejne konsystencji może być dozwolone lub zabronione przez spoczynkowego konsystencji i zabrania linearizable konsystencji.

Jeśli przyjmiesz, że pomiędzy tymi dwoma kolejkami, kolejka była spokojna, to T2 powinna zobaczyć zmiany z T1, a kolejka powinna zwrócić x. Jeśli założysz, że pomiędzy tymi dwoma kolejkami nie było żadnych spoczynkowych interwałów, wtedy dwie kolejki mogą być ponownie zamieniane według twoich potrzeb, a deq(): y jest spójne.