Praktyczna operacja porównywania i zamiany wielu słów

W artykule o tym samym tytule co tytuł tego pytania, autorzy opisują, jak zbudować nieblokowalną, liniową, wielowątkową operację CAS , używając tylko jednego słowa CAS. Najpierw wprowadzają operację podwójnego porównania-pojedynczej wymiany - RDCSS, jak następuje:

word_t RDCSS(RDCSSDescriptor_t *d) {
  do {
    r = CAS1(d->a2, d->o2, d);
    if (IsDescriptor(r)) Complete(r);
  } while (IsDescriptor(r));
  if (r == d->o2) Complete(d); // !!
  return r;
}

void Complete(RDCSSDescriptor_t *d) {
  v = *(d->a1);
  if (v == d->o1) CAS1(d->a2, d, d->n2);
  else CAS1(d->a2, d, d->o2);
}

gdzie RDCSSDescriptor_tjest strukturą zawierającą następujące pola:

• a1 - adres pierwszego warunku
• o1 - wartość oczekiwana pod pierwszym adresem
• a2 - adres drugiego warunku
• o2 - wartość oczekiwana pod drugim adresem
• n2 - nowa wartość do zapisania pod drugim adresem

Ten deskryptor jest tworzony i inicjowany jeden raz w wątku, który inicjuje operację RDCSS - żaden inny wątek nie ma do niego odwołania, dopóki pierwszy CAS1 w funkcji nie RDCSSpowiedzie się, co czyni deskryptor osiągalnym (lub aktywnym w terminologii artykułu).

Algorytm jest następujący: zastąp drugą lokalizację pamięci deskryptorem informującym o tym, co chcesz zrobić. Następnie, biorąc pod uwagę, że deskryptor jest obecny, sprawdź pierwszą lokalizację pamięci, aby zobaczyć, czy jej wartość się zmieniła. Jeśli nie, zastąp deskryptor w drugiej lokalizacji pamięci nową wartością. W przeciwnym razie ustaw drugą lokalizację pamięci z powrotem na starą wartość.

Autorzy nie wyjaśniają, dlaczego linia z !!komentarzem jest niezbędna w pracy. Wydaje mi się, że po tej kontroli CAS1instrukcje w Completefunkcji zawsze się nie udają, pod warunkiem, że nie ma równoczesnej modyfikacji. A jeśli była jednoczesna modyfikacja między czekiem a CAS w Complete, to wątek wykonujący sprawdzenie powinien nadal zawieść ze swoim CAS w Complete, ponieważ jednoczesna modyfikacja nie powinna używać tego samego deskryptora d.

Moje pytanie brzmi: czy można pominąć sprawdzanie funkcji RDCSSS, if (r == d->o2)...gdy RDCSS nadal zachowuje semantykę instrukcji podwójnego porównania, pojedynczej zamiany, która jest linearyzowalna i bez blokady ? (linia z !!komentarzem)

Jeśli nie, czy możesz opisać scenariusz, w którym ta linia jest rzeczywiście konieczna do zapewnienia poprawności?

Dziękuję Ci.

W równoczesnym środowisku uruchomieniowym proste rzeczy mogą wydawać się dziwne ... mam nadzieję, że to może pomóc.

Mamy wbudowany ATOMIC CAS1 o tej semantycznej:

int CAS1(int *addr, int oldval, int newval) {
  int currval = *addr;
  if (currval == oldval) *addr = newval;
  return currval;
}

Musimy zdefiniować funkcję ATOMIC RDCSS za pomocą CAS1 i mieć następujący semantyczny:

int RDCSS(int *addr1, int oldval1, int *addr2, int oldval2, int newval2) {
  int res = *addr;
  if (res == oldval2 && *addr1 == oldval1) *addr2 = newval2;
  return res;
}

Intuicyjnie: musimy KONKURENCYJNIE zmieniać wartość w addr2 tylko, jeśli * addr1 == oldval1 ... jeśli inny wątek go zmienia, możemy pomóc drugiemu wątkowi w zakończeniu operacji, a następnie możemy spróbować ponownie.

Do zdefiniowania CASN zostanie użyta funkcja RDCSS (patrz artykuł). Teraz definiujemy deskryptor RDCSS w następujący sposób:

RDCSSDESCRI
int *addr1   
int oldval1
int *addr2   
int oldval2
int newval2

Następnie wdrażamy RDCSS w następujący sposób:

int RDCSS( RDCSSDESCRI *d ) {
  do {
    res = CAS1(d->addr2, d->oldval2, d);  // STEP1
    if (IsDescriptor(res)) Complete(res); // STEP2
  } while (IsDescriptor(res);             // STEP3
  if (res == d->oldval2) Complete(d);     // STEP4
  return res;
}

void Complete( RDCSSDESCRI *d ) {
  int val = *(d->addr1);
  if (val == d->oldval1) CAS1(d->addr2, d, d->newval2);
    else CAS1(d->addr2, d, d->oldval2);  
}

• KROK 1: najpierw próbujemy zmienić wartość * addr2 na nasz (własny) deskryptor d, jeśli CAS1 się powiedzie, to res == d-> oldval2 (tzn. Res nie jest deskryptorem)
• KROK 2: sprawdź, czy res jest deskryptorem, tzn. KROK 1 nie powiódł się (inny wątek zmienił addr2) ... pomóż innemu wątkowi w zakończeniu operacji
• KROK 3: spróbuj ponownie KROK 1, jeśli nie uda nam się zapisać naszego deskryptora d
• KROK 4: jeśli pobraliśmy oczekiwaną wartość z addr2, to udało nam się zapisać nasz deskryptor (wskaźnik) w addr2 i możemy zakończyć nasze zadanie przechowując newval2 do * addr2 iif * addr1 == oldval1

ODPOWIEDŹ NA PYTANIE

Jeśli pominiemy STEP4, to część if (... && * addr1 == oldval1) * addr2 = newval2 semantycznej części RDCSS nigdy nie zostanie wykonana (... lub lepiej: można ją wykonać w sposób przewidywalny przez inne wątki pomagające obecny).

Jak zauważyłeś w swoim komentarzu, warunek, jeśli (res == d1-> oldval2) w STEP4 jest niepotrzebny: nawet jeśli go pominiemy, oba CAS1 w Complete () zawiodą, ponieważ * (d-> addr2)! = D . Jedynym celem jest uniknięcie wywołania funkcji.

Przykład T1 = wątek 1, T2 = wątek 2:

remember that addr1 / addr2 are in a shared data zone !!!

T1 enter RDCSS function
T2 enter RDCSS function
T2 complete STEP1 (and store the pointer to its descriptor d2 in addr2)
T1 at STEP1 the CAS1 fails and res = d2
T2 or T1 completes *(d2->addr2)=d2->newval2 (suppose that *(d2->addr1)==d2->oldval1)
T1 execute STEP1 and now CAS1 can fail because *addr2 == d2->newval2
   and maybe d2->newval2 != d1->oldval2, in every case at the end 
   res == d2->newval2 (fail) or
   res == d1->oldval2 (success)
T1 at STEP2 skips the call to Complete() (because now res is not a descriptor)
T1 at STEP3 exits the loop (because now res is not a descriptor)
T1 at STEP4 T1 is ready to store d1->newval2 to addr2, but only if
   *(d1->addr2)==d (we are working on our descriptor) and *(d1->addr1)==d1->oldval1
   ( Custom() function)