Eine praktische Mehrwort-Vergleichs- und Austauschoperation

10

Im Papier mit dem gleichen Titel wie die von dieser Frage, beschreiben die Autoren , wie ein bauen , nicht blockierend linearisierbar Mehrwort CAS nur mit einem einzigen Wort CAS Betrieb. Sie führen zunächst die Double-Compare-Single-Swap-Operation - RDCSS - wie folgt ein:

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);
}

Dabei RDCSSDescriptor_tist das eine Struktur mit folgenden Feldern:

  • a1 - Adresse der ersten Bedingung
  • o1 - Wert erwartet an der ersten Adresse
  • a2 - Adresse der zweiten Bedingung
  • o2 - Wert erwartet an der zweiten Adresse
  • n2 - der neue Wert, der an die zweite Adresse geschrieben werden soll

Dieser Deskriptor wird einmal in einem Thread erstellt und initialisiert, der die RDCSS-Operation initiiert. Kein anderer Thread hat einen Verweis darauf, bis das erste CAS1 in der Funktion RDCSSerfolgreich ist, wodurch der Deskriptor erreichbar (oder in der Terminologie des Dokuments aktiv ) wird.

Die Idee hinter dem Algorithmus ist die folgende: Ersetzen Sie den zweiten Speicherort durch einen Deskriptor, der angibt, was Sie tun möchten. Wenn der Deskriptor vorhanden ist, überprüfen Sie den ersten Speicherort, um festzustellen, ob sich sein Wert geändert hat. Ist dies nicht der Fall, ersetzen Sie den Deskriptor am zweiten Speicherort durch den neuen Wert. Andernfalls setzen Sie den zweiten Speicherort auf den alten Wert zurück.

Die Autoren erklären nicht, warum die Zeile mit dem !!Kommentar innerhalb des Papiers notwendig ist. Es scheint mir, dass die CAS1Anweisungen in der CompleteFunktion nach dieser Überprüfung immer fehlschlagen, vorausgesetzt, es erfolgt keine gleichzeitige Änderung. Und wenn es eine gleichzeitige Änderung zwischen der Prüfung und dem CAS-Eingang gab Complete, sollte der Thread, der die Prüfung durchführt, immer noch mit seinem CAS-Eingang fehlschlagen Complete, da die gleichzeitige Änderung nicht denselben Deskriptor verwenden sollte d.

Meine Frage ist: Kann die Prüfung in der Funktion RDCSSS, if (r == d->o2)...weggelassen wird, mit RDCSS noch die Semantik einer Doppel vergleichen, einzelnen Swap - Anweisung beibehalten , die ist linearisierbar und Lock-frei ? (Zeile mit !!Kommentar)

Wenn nicht, können Sie das Szenario beschreiben, in dem diese Zeile tatsächlich erforderlich ist, um die Richtigkeit sicherzustellen?

Vielen Dank.

axel22
quelle
Um zu verstehen, was los ist, müssten wir zunächst die Datenstruktur RDCSSDescriptor_t sehen. Zweitens ist dies hier wahrscheinlich kein Thema, da es sich nicht um theoretische Informatik handelt. Es wäre besser, dies auf stackoverflow.com zu erfragen.
Dave Clarke
Die Verbindung zum Papier ist unterbrochen.
Aaron Sterling
1
Ich entschuldige mich für den Link - es sollte jetzt funktionieren. Ich habe die Frage aktualisiert, um zu beschreiben, was der Deskriptor ist. Der Grund, warum ich dies nicht auf stackoverflow.com gepostet habe, ist, dass die FAQ besagt, dass diese Website für Fragen auf Forschungsebene in der Informatik gedacht ist. Ich dachte, die Fragen der Sperrfreiheit und Linearisierbarkeit eines Algorithmus qualifizieren sich als solche. Ich hoffe ich habe die FAQ falsch verstanden.
Axel22
Das Schlüsselwort, das Sie in den FAQ verpasst haben, war "theoretisch". Da einige Leute die Frage interessant finden, lasse ich sie offen.
Dave Clarke
3
@ Dave: Ich bin kein Experte in diesem Teilbereich, aber für mich klingt dies nach einer sehr typischen TCS-Frage. Sie erhalten zwei Berechnungsmodelle (A: mit einem Einzelwort-CAS, B: mit einem Mehrwort-CAS) und ein Komplexitätsmaß (Anzahl der CASs) und werden gefragt, ob Sie Modell B in Modell A simulieren können. und mit welchem ​​Worst-Case-Overhead. (Hier könnte es etwas irreführend sein, dass die Simulation als Teil des C-Codes anstelle des Pseudocodes angegeben wird; dies könnte einer theoretischen Person nahe legen, dass dies mit realen Programmierherausforderungen zusammenhängt.)
Jukka Suomela

Antworten:

9

In einer gleichzeitigen Laufzeitumgebung können einfache Dinge seltsam erscheinen ... hoffe, dies kann helfen.

Wir haben ein eingebautes ATOM-CAS1 mit dieser Semantik:

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

Wir müssen eine ATOMIC RDCSS-Funktion mit CAS1 definieren und die folgende Semantik haben:

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

Intuitiv: Wir müssen den Wert bei addr2 nur dann regelmäßig ändern, wenn * addr1 == oldval1 ... wenn ein anderer Thread ihn ändert, können wir dem anderen Thread helfen, den Vorgang abzuschließen, dann können wir es erneut versuchen.

Die RDCSS- Funktion wird verwendet (siehe Artikel), um CASN zu definieren. Nun definieren wir einen RDCSS-Deskriptor folgendermaßen:

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

Dann implementieren wir RDCSS folgendermaßen:

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);  
}
  • SCHRITT 1: Zuerst versuchen wir, den Wert von * addr2 in unseren (eigenen) Deskriptor d zu ändern. Wenn CAS1 erfolgreich ist, dann res == d-> oldval2 (dh res ist KEIN Deskriptor).
  • STEP2: Überprüfen Sie, ob res ein Deskriptor ist, dh STEP1 ist fehlgeschlagen (ein anderer Thread hat addr2 geändert) ... helfen Sie einem anderen Thread, den Vorgang abzuschließen
  • SCHRITT 3: Wiederholen Sie SCHRITT 1, wenn es uns nicht gelungen ist, unseren Deskriptor zu speichern. D.
  • SCHRITT 4: Wenn wir unseren erwarteten Wert von addr2 abgerufen haben, ist es uns gelungen, unseren Deskriptor (Zeiger) in addr2 zu speichern, und wir können unsere Aufgabe zum Speichern von newval2 in * addr2 iif * addr1 == oldval1 abschließen

ANTWORT AUF IHRE FRAGE

Wenn wir STEP4 weglassen, wird der Teil if (... && * addr1 == oldval1) * addr2 = newval2 der RDCSS-Semantik niemals ausgeführt (... oder besser: Er kann auf unvorhersehbare Weise von anderen helfenden Threads ausgeführt werden der aktuelle).

Wie Sie in Ihrem Kommentar ausgeführt haben, ist die Bedingung if (res == d1-> oldval2) bei STEP4 nicht erforderlich: Selbst wenn wir sie weglassen, schlagen beide CAS1 in Complete () fehl, weil * (d-> addr2)! = D. . Ihr einziger Zweck ist es, einen Funktionsaufruf zu vermeiden.

Beispiel T1 = Thread1, T2 = Thread2:

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)
Marzio De Biasi
quelle
Danke, gute Erklärung. Ich habe den Punkt völlig übersehen, dass CAS1 den alten Wert zurückgibt, nicht den neuen.
Axel22
In dem Szenario sagen die letzten beiden Zeilen jedoch Folgendes: Ohne die Bedingung bei STEP4 kann T1 den Wert speichern, da addr2enthält d2->newval2. Aber es scheint mir, dass das CAS1 im CompleteTestament einfach fehlschlägt, weil es erwartet, dass der alte Wert der Deskriptor ist d1- nichts wird von T1 geschrieben. Recht?
Axel22
@ axel22: Ich habe das CAS1 in Complete () verpasst :-D. Ja, Sie haben Recht ... mein Beispiel ist falsch, die if-Bedingung wird nur verwendet, um einen Funktionsaufruf zu vermeiden, wenn wir das if () wegwerfen, ändert sich nichts. Offensichtlich ist das vollständige (d) bei SCHRITT 4 notwendig. Jetzt ändere ich das Beispiel.
Marzio De Biasi
Das Vermeiden eines CAS, von dem wir erwarten, dass es fehlschlägt, ist meines Wissens eine Cache-Optimierungstechnik, da es auf realer Hardware normalerweise negative Auswirkungen hat, wie das Leeren von Cache-Zeilen und den exklusiven Zugriff auf eine Cache-Zeile. Ich denke, der Autor des Papiers wollte, dass der Algorithmus nicht nur korrekt, sondern auch so praktisch wie möglich ist.
Tim Seguine