Das in der Push-Funktion einer sperrenfreien Warteschlange in Abschnitt 7.15 „C++-Parallelität in Aktion“ erwähnte Probl ⇐ C++

[Guest]

Ich habe in Listing 7.15 „C++ Concurrency in Action“ gelesen:

Die Verwendung des Referenzzählschemas vermeidet dieses spezielle Rennen, aber es ist nicht das einzige Rennen in push(). Wenn Sie sich die überarbeitete Version von push() in Listing 7.15 ansehen, werden Sie ein Muster sehen, das Sie im Stapel gesehen haben: Laden Sie einen atomaren Zeiger (1) und dereferenzieren Sie diesen Zeiger (2). In der Zwischenzeit könnte ein anderer Thread den Zeiger (3) aktualisieren, was schließlich dazu führt, dass die Zuordnung des Knotens aufgehoben wird (in pop()). Wenn die Zuordnung des Knotens aufgehoben wird, bevor Sie den Zeiger dereferenzieren, liegt ein undefiniertes Verhalten vor. Autsch! Es ist verlockend, eine externe Zählung in tail hinzuzufügen, genau wie Sie es für head getan haben, aber jeder Knoten hat bereits eine externe Zählung im nächsten Zeiger des vorherigen Knotens in der Warteschlange. Das Vorhandensein zweier externer Zählungen für denselben Knoten erfordert eine Änderung des Referenzzählschemas, um ein zu frühes Löschen des Knotens zu vermeiden. Sie können dies beheben, indem Sie auch die Anzahl der externen Zähler innerhalb der Knotenstruktur zählen und diese Zahl verringern, wenn jeder externe Zähler zerstört wird (und den entsprechenden externen Zähler zum internen Zähler addieren). Wenn der interne Zähler Null ist und keine externen Zähler vorhanden sind, wissen Sie, dass der Knoten sicher gelöscht werden kann. Dies ist eine Technik, die mir zum ersten Mal durch Joe Seighs Atomic Ptr Plus Project (http://atomic-ptr-plus.sourceforge.net/) begegnet ist. Das folgende Listing zeigt, wie push() unter diesem Schema aussieht.

Listing 7.15 Ein (kaputter) erster Versuch, push() zu überarbeiten:

Code: Select all

void push(T new_value)
{
std::unique_ptr new_data(new T(new_value));
counted_node_ptr new_next;
new_next.ptr = new node;
new_next.external_count = 1;
for (;;)
{
node* const old_tail = tail.load(); // 1
T* old_data = nullptr;
if (old_tail->data.compare_exchange_strong(
old_data, new_data.get())) // 2
{
old_tail->next = new_next;
tail.store(new_next.ptr); // 3
new_data.release();
break;
}
}
}

Allerdings verstehe ich diesen Teil nicht ganz:

Wenn das Wenn die Zuordnung des Knotens aufgehoben wird, bevor Sie den Zeiger dereferenzieren, liegt ein undefiniertes Verhalten vor.

In pop() prüft die Funktion zunächst, ob Kopf und Ende auf dasselbe zeigen Platzhalterknoten. Wenn dies der Fall ist, wird festgestellt, dass die Warteschlange leer ist, und es wird nichts unternommen. In Listing 7.15 aktualisiert die push()-Funktion das Ende erst im letzten Schritt, was bedeutet, dass pop() nicht auf dem in die Warteschlange gestellten Knoten ausgeführt wird, bis push() den Enqueue-Vorgang abschließt. Woher kommt also diese Race-Bedingung?
Da der Autor im Buch kein Beispiel für die Annahme für diese Situation angegeben hat (das Beispiel basiert auf dem vorherigen sperrfreien Stapel). ), kann ich nicht den vollständigen Kontext liefern. Unten ist der Code für pop() vor der Änderung.

Code: Select all

template 
class lock_free_queue {
private:
struct node {
std::shared_ptr data;
node *next;
node() : next(nullptr) {}
};

std::atomic head;
std::atomic tail;

node *pop_head() {
node *const old_head = head.load();
if (old_head == tail.load()) {
return nullptr;
}
head.store(old_head->next);
return old_head;
}

public:
lock_free_queue() : head(new node), tail(head.load()) {}

// ...

std::shared_ptr pop() {
node *old_head = pop_head();
if (!old_head) {
return std::shared_ptr();
}
std::shared_ptr const res(old_head->data);
delete old_head;
return res;
}

void push(T new_value) {
std::shared_ptr new_data(std::make_shared(new_value));
node *p = new node;
node *const old_tail = tail.load();
old_tail->data.swap(new_data);
old_tail->next = p;
tail.store(p);
}

};