Bariery pamięci a operacje blokowane

Question

Próbuję poprawić rozumienie barier pamięci. Załóżmy, że mamy słaby model pamięci i dostosowujemy Dekker's algorithm. Czy jest możliwe, aby działał poprawnie pod słabym modelem pamięci, dodając bariery pamięci?

Myślę, że odpowiedź jest zaskakująca. Powodem (jeśli mam rację) jest to, że chociaż można wykorzystać barierę pamięci, aby upewnić się, że odczyt nie zostanie przeniesiony obok innej, to nie może zagwarantować, że odczyt nie będzie zawierał nieaktualnych danych (takich jak w pamięci podręcznej). W ten sposób mógł minąć jakiś czas w przeszłości, gdy sekcja krytyczna została odblokowana (na pamięć podręczną procesora), ale w chwili obecnej inne procesory mogą ją zablokować. Jeśli moje zrozumienie jest poprawne, należy użyć powiązanych ze sobą operacji, takich jak te, które są zwykle nazywane testowaniem i zestawieniem lub porównywaniem i zamianą, aby zapewnić zsynchronizowaną zgodność wartości w lokalizacji pamięci między wieloma procesorami.

Czy możemy zatem słusznie oczekiwać, że system słabego modelu pamięci nie zapewni tylko barier pamięci? System musi dostarczać operacje, takie jak testowanie i zestawianie lub porównywanie i zamiana, aby były użyteczne.

Zdaję sobie sprawę, że popularne procesory, w tym procesor x86, zapewniają modele pamięci o wiele mocniejsze niż słabe modele pamięci. Proszę skupić się na dyskusji na temat słabych modeli pamięci.

(Jeśli algorytm dekkera jest złym wyborem, wybierz inny algorytm wzajemnego wykluczania gdzie bariera pamięci może z powodzeniem osiągnąć prawidłową synchronizację, jeśli to możliwe).

Answer 1

Masz rację, że bariera pamięci nie może zapewnić, że odczyt widzi aktualne wartości. To, co robi, wymusza porządkowanie operacji, zarówno w jednym wątku, jak i między wątkami.

Na przykład, jeśli wątek A wykonuje serię magazynów, a następnie wykonuje barierę zwolnienia przed ostatnim magazynem do lokalizacji flagi, a wątek B odczytuje z lokalizacji flagi, a następnie wykonuje przejęcie kontroli przed odczytaniem innych wartości, a następnie pozostałe zmienne będą miały wartości przechowywanych przez gwintu a:

// initially x=y=z=flag=0 

// thread A 
x=1; 
y=2; 
z=3; 
release_barrier(); 
flag=1; 

// thread B 
while(flag==0) ; // loop until flag is 1 
acquire_barrier(); 
assert(x==1); // asserts will not fire 
assert(y==2); 
assert(z==3); 

oczywiście, trzeba upewnić się, że ładunek i przechowywać do flag jest atomowy (co proste ładowanie i zapisywanie instrukcje są na najbardziej popularnych procesorów, pod warunkiem, że zmienne są odpowiednio wyrównane). Bez pętli while w wątku B wątek B może dobrze odczytać nieaktualną wartość (0) dla flag, a zatem nie można zagwarantować żadnej wartości odczytanej dla innych zmiennych.

Ogrodzenia mogą być używane do wymuszania synchronizacji w algorytmie Dekkera.

Oto implementacja przykład w C++ (przy użyciu C++ 0x zmienne atomowe):

std::atomic<bool> flag0(false),flag1(false); 
std::atomic<int> turn(0); 

void p0() 
{ 
    flag0.store(true,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_seq_cst); 

    while (flag1.load(std::memory_order_relaxed)) 
    { 
     if (turn.load(std::memory_order_relaxed) != 0) 
     { 
      flag0.store(false,std::memory_order_relaxed); 
      while (turn.load(std::memory_order_relaxed) != 0) 
      { 
      } 
      flag0.store(true,std::memory_order_relaxed); 
      std::atomic_thread_fence(std::memory_order_seq_cst); 
     } 
    } 
    std::atomic_thread_fence(std::memory_order_acquire); 

    // critical section 


    turn.store(1,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_release); 
    flag0.store(false,std::memory_order_relaxed); 
} 

void p1() 
{ 
    flag1.store(true,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_seq_cst); 

    while (flag0.load(std::memory_order_relaxed)) 
    { 
     if (turn.load(std::memory_order_relaxed) != 1) 
     { 
      flag1.store(false,std::memory_order_relaxed); 
      while (turn.load(std::memory_order_relaxed) != 1) 
      { 
      } 
      flag1.store(true,std::memory_order_relaxed); 
      std::atomic_thread_fence(std::memory_order_seq_cst); 
     } 
    } 
    std::atomic_thread_fence(std::memory_order_acquire); 

    // critical section 


    turn.store(0,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_release); 
    flag1.store(false,std::memory_order_relaxed); 
} 

do pełnej analizy patrz moja notka na http://www.justsoftwaresolutions.co.uk/threading/implementing_dekkers_algorithm_with_fences.html

Answer 2

Niektóre bariery (takie jak iSync PowerPC oraz obciążenie .acq na ia64) mają również wpływ na dodatkowe obciążenia. tj: jeśli obciążenie było dostępne przed isynchronizacją z powodu wstępnego pobierania, musi zostać odrzucone. Odpowiednio użyta może to wystarczy, aby algorytm Dekkera działał na słabym modelu pamięci.

Masz również działającą dla Ciebie logikę unieważniania pamięci podręcznej. Jeśli wiesz, że twoje obciążenie jest aktualne z powodu czegoś takiego jak isync i że buforowana wersja danych jest unieważniona, jeśli inny procesor ją dotknie, czy to wystarczy?

Poza tym, algorytm Dekkera jest dla wszystkich celów praktycznych głupi. Będziesz chciał użyć atomowych interfejsów sprzętowych i barier pamięci dla każdej prawdziwej aplikacji, więc skupienie się na tym, jak naprawić Dekkera za pomocą atomów, nie wydaje mi się warte;)

Answer 3

Powiedz, że umieściłeś ładunek i przechowujesz bariera po każdym oświadczeniu, a ponadto zapewniłeś, że kompilator nie uporządkował twoich sklepów. Czy nie byłoby to, na jakiejkolwiek rozsądnej architekturze, zapewnić ścisłą spójność? Dekker pracuje na sekwencyjnie spójnych architekturach. Spójność sekwencyjna jest słabszym warunkiem niż ścisła spójność.

http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html

Nawet na CPU, który ma słabą modelu spójności, można jeszcze oczekiwać spójności cache. Myślę, że tam, gdzie rzeczy się wykolejają, zachowuje się bufory sklepów i spekulowane odczyty, a także, jakie operacje są dostępne, spłukując zapisane zapisy i unieważniając spekulowane odczyty. Jeśli nie ma barierki obciążającej, która może unieważnić spekulowane odczyty lub nie ma zapory, która opróżnia bufor pamięci, a ponadto nie będzie w stanie zaimplementować Dekkera, nie będzie można zaimplementować muteksu!

Oto moje roszczenia. Jeśli masz dostępną barierę zapisu i barierę odczytu, a pamięć podręczna jest spójna pomiędzy procesorami, możesz trywialnie uczynić cały kod sekwencyjnie spójnym, wypłukując zapisy (ogrodzenie magazynu) po każdej instrukcji i spłukując spekulacje (czytać ogrodzenie) przed każdym instrukcja. Tak więc twierdzę, że nie potrzebujesz atomików do tego, o czym mówisz, i że możesz robić to, czego potrzebujesz tylko z Dekker. Pewnie, że nie chcesz.

BTW, Corensic, firma dla której pracuję, pisze fajne narzędzia do debugowania problemów z współbieżnością. Sprawdź http://www.corensic.com.