C++ コアガイドライン:謎の解決

今日、前回の投稿のなぞなぞを解きます。読者のおかげで、ABA 問題の分析は非常に正確です。

思い出させるだけです。 C++ コアガイドラインのルール CP.100 が謎の出発点です。

CP.100:ロックフリープログラミングを使用しないでください。

ルールの課題は、次のコードスニペットにバグがあることを示しています。バグは ABA の問題によるものです。投稿 ABA - A は A と同じではありません。ABA の問題を簡潔に紹介しています。

extern atomic<Link*> head; // the shared head of a linked list

Link* nh = new Link(data, nullptr); // make a link ready for insertion
Link* h = head.load(); // read the shared head of the list 

do {
 if (h->data <= data) break; // if so, insert elsewhere 
 nh->next = h; // next element is the previous head 
} while (!head.compare_exchange_weak(h, nh)); // write nh to head or to h

私のドイツのブログの匿名の読者に特に感謝します。ここに実行可能なコードと問題の詳細な分析があります。

#include <atomic>

class Link {
public:
 Link(int d, Link* p) : data(d), next(p) {}
 int data;
 Link* next;
};

void foo (int data) {
 extern std::atomic<Link*> head;

 Link* nh = new Link(data, nullptr); // (1)
 Link* h = head.load(); // (2)

 do {
 if (h->data <= data) break; // (3)
 nh->next = h; // (4)
 } while (!head.compare_exchange_weak(h, nh)); // (5)
}

まず、このコードは何をすべきでしょうか?ノードの単一リンクリスト (リンク) を作成します。各ノードには、ポインターとデータフィールドがあります。ポインターは次の要素 (node->next) を指し、データフィールドには値 node->data が格納されます。新しい各ノードは、データが昇順で並べられるように、単方向リンクリストに挿入されます。

単一リンクリストの正しい位置に新しいノードを挿入するには、次の手順を実行します。

1 行目 :新しいノードが作成されます。ノードは各スレッドでローカルに作成されるため、これで問題ありません。
2 行目 ：先頭へのポインタを読み込みます。読み取り操作はアトミックです。したがって、分離して考えると、操作も問題ありません。孤立してとはどういう意味ですか? 2 行目は 5 行目で一種のトランザクションを作成します。行 2 はトランザクションの初期状態を保存し、行 5 はその間に何も変更されていない場合にトランザクションを発行します。
3 行目 :前の行に対応して、この行 3 は問題ありません。 head のデータが新しいデータよりも小さい場合、値の比較のみが行われ、関数が終了する可能性があります。
4 行目 :nh はローカルデータです。したがって、nh->next の代入は問題ありません。その間にヘッド h が変更され、その結果、 nh->next がその後ヘッドを参照しない場合があります。これは、次の 5 行目で変更がコミットされた場合にのみ問題になります。
5 行目 :命令 head.compare_exchange_weak(h, nh) は、head と 2 行目の格納された h を比較し、h と nh が同じになるとすぐにアトミックステップで交換します。 head が h と等しくない場合、h が head に設定されます。行 5 はアトミックトランザクションの終わりであり、更新された単一リンクリストを公開します。

これらの数行のコードの問題は何ですか?トランザクション全体は、5 行目のポインター比較に基づいています。ポインター比較がだまされる可能性がある場合、単一リンクリストが壊れる可能性があります。

ヘッドの読み込み (2 行目) と、現在のヘッドが古いヘッドであるかどうかのチェック (5 行目) の間に時間枠があります。これは、別のスレッドが起動してその間にヘッドが変更される可能性があることを意味しますが、最初のスレッドはそれを認識しません。

バグのある一連のイベントを紹介しましょう。