C ConcurrencyinAction中危險指標的實作是否存在缺陷？-有解無憂

我正在閱讀 C Concurrency in Action 的第二版。下面的代碼來自代碼清單 7.6。它pop()使用危險指標來實作堆疊。

std::shared_ptr<T> pop() {
  std::atomic<void*>& hp = get_hazard_pointer_for_current_thread();
  node* old_head = head.load();  // #1
  do {
    node* temp;
    do {
      temp = old_head;
      hp.store(old_head);        // #2
      old_head = head.load();    // #3
    } while (old_head != temp);  // #4
  } while (old_head &&
           !head.compare_exchange_strong(old_head, old_head->next));
  hp.store(nullptr);
  // ...
}

書中解釋了內回圈的作用：

您必須在while回圈中執行此操作，以確保在讀取舊指標和設定危險指標node之間沒有洗掉head#1#2。在此視窗期間，沒有其他執行緒知道您正在訪問此特定節點。head幸運的是，如果要洗掉舊節點，head它本身肯定已經改變，所以您可以檢查這一點并繼續回圈，直到您知道head指標仍然具有您設定危險指標的相同值#4。

根據的實作，如果另一個執行緒通過between和pop洗掉了頭節點，則將修改為新節點。pop#1#2head

讓我困惑的是，head其他執行緒的修改能被當前執行緒及時看到嗎？例如，如果的新值head尚未傳播到當前執行緒，那么#1和#3仍將讀取相同的值（舊值），導致內while回圈退出，進而外while回圈訪問old_head->next，從而導致未定義的行為。

我已經在 stackoverflow 上搜索了一些答案。例如，這個答案說

的默認記憶體排序為所有變數std::memory_order_seq_cst的所有操作提供了一個全域總排序。這并不意味著您不能獲得陳舊的值，但它確實意味著您獲得的值決定并由您的操作所在的總順序中的位置決定。std::memory_order_seq_cst

這條評論說

每個原子變數都有自己的修改順序，所有執行緒都可以同意，但這只會序列化修改，而不是讀取。涉及讀取的一致性要求只是保證如果您在修改順序中看到了一個值，則看不到更早的值。

但是cppreference說

從 atomic variable 加載的每個memory_order_seq_cst操作都遵循以下條件之一：BM

最后一次A修改的操作的結果，在單個總順序M中出現在 B 之前

...

那么我的問題的答案到底應該是什么？

另外，如果在這里使用較弱的排序（如釋放-獲取或放松），會出現上述問題嗎？

這是代碼pop：

std::shared_ptr<T> pop() {
  std::atomic<void*>& hp = get_hazard_pointer_for_current_thread();
  node* old_head = head.load();  // #1
  do {
    node* temp;
    do {
      temp = old_head;
      hp.store(old_head);        // #2
      old_head = head.load();    // #3
    } while (old_head != temp);  // #4
  } while (old_head &&
           !head.compare_exchange_strong(old_head, old_head->next));
  hp.store(nullptr);  // Clear hazard pointer once you're finished
  std::shared_ptr<T> res;
  if (old_head) {
    res.swap(old_head->data);
    if (outstanding_hazard_pointers_for(old_head)) // Check for hazard pointers referencing a node before you delete it.
      reclaim_later(old_head);
    else
      delete old_head;
    delete_nodes_with_no_hazards();
  }
  return res;
}

pop()彈出指向的節點head并在沒有危險指標指向它時釋放它。修改head是通過實作的compare_exchange_strong。

uj5u.com熱心網友回復：

不，我不認為它有缺陷。

為了驗證演算法是否正確，我在這里再注釋幾行代碼。我重寫了第 8 行，以明確它從另一個執行緒的危險指標加載。

std::shared_ptr<T> pop() {
  std::atomic<void*>& hp = get_hazard_pointer_for_current_thread();
  node* old_head = head.load();  // #1
  do {
    node* temp;
    do {
      temp = old_head;
      hp.store(old_head);        // #2
      old_head = head.load();    // #3
    } while (old_head != temp);  // #4
  } while (old_head &&
           !head.compare_exchange_strong(old_head, old_head->next));
                                 // #5 deref of old_head
                                 // #6 the compare_exchange
  hp.store(nullptr);             // #7 
  std::shared_ptr<T> res;
  if (old_head) {
    res.swap(old_head->data);
    if (other_thread_hp.load() == old_head)
                                 // #8
      reclaim_later(old_head);
    else
      delete old_head;           // #9
    delete_nodes_with_no_hazards();
  }
  return res;
}

非正式理由

假設執行緒 A 試圖安全地取消參考old_head，而執行緒 B 想要洗掉它。

完全有可能，例如，compare_exchange_strong執行緒 B 中的第 6 行（簡稱 B6）相對于實時發生在負載 A1 和 A3 之間，但直到稍后才對執行緒 A 可見。

但是，我們具有順序一致性。每個執行緒都必須按照該順序觀察操作 B6 和 B8。因此，如果 B6 直到 A3 之后才對 A 可見，那么 B8 直到更晚才對 A 可見，到那時，存盤 A2 將生效。換句話說，加載 B8 必須觀察 A3 之前的所有存盤，尤其包括 A2。所以要么 B8 將回傳來自 A 的非空危險指標，在這種情況下洗掉不會完成；否則它會回傳nullptr，這只有在存盤 A7 變得可見時才會發生，并且到那時取消參考 A5 已經完成。

因此，如果在執行 B6 和它變得全域可見之間可能存在延遲，那么實作必須安排執行緒 B 中的所有后續操作，尤其是 B8，都停止，直到 B6 變得可見之后。在當今的硬體上，這種延遲的典型原因是 B6 的存盤進入了存盤緩沖區。因此，為了確保順序一致性，編譯器必須在 B6 和 B8 之間插入一條屏障指令，該指令將等待存盤緩沖區耗盡并提交到一致的 L1 快取，然后再繼續。

編輯：關于延遲非原子操作的評論中的問題：事情有點復雜，因為 B6 是讀取-修改-寫入，但出于記憶體排序目的，您可以將其視為由負載 (B6L) 和商店（B6S），兩者都是seq_cst. 為了對非seq_cst操作（包括所有非原子操作）進行排序，seq_cst存盤只是釋放存盤，seq_cst加載只是獲取加載。因此，事實上，遵循 B6S 的非原子操作不必“停止”，除非另有限制，否則可能會在 B6S 之前變得可見。（然而，它們在 B6L 之前不能變得可見，因為它是獲取的。）

但出于同樣的原因，B8 是獲取。這確實需要稍后的操作，包括 B9 等非原子操作，在 B8 變得可見之前停止。（這里 B9 位于條件分支的一側，這取決于 B8 加載的值，但沒有獲取障礙，它仍然可以開始進行推測性加載。）因此，最終結果是 B9 必須僅在 B6S 之后才可見，因為 B9 必須等待 B8，而 B8 必須等待 B6S。

正確性的正式證明

請記住，C 記憶體模型沒有“及時”或“陳舊”的概念；一切都是根據抽象順序定義的。這里所有的原子操作都是seq_cst默認的，所以它們都有一個總的順序，連貫性規則確保它們以所有通常的方式相互觀察。

我們將為分別由執行緒 A 或 B 執行的操作 #1 撰寫 A1、B1 等。此外，讓hpA, hpB是屬于相應執行緒的危險指標。讓我們在這里進入代碼H0的值，這兩個執行緒最初都加載為它們的, 和,以下節點的地址。headold_headH1H2

我們要確保 A5 發生在 B9 之前。如果A5要解參考指標H0，一定是加載A1，A3都回傳了H0，也就是說A2存盤H0到了hpA。（或者如果 A1 沒有，那么 A3 的倒數第二次和最后一次迭代都必須加載H0；無論哪種方式，結論都是 A2 存盤了H0。）

同樣，如果 B6 要洗掉H0，則必須是H0從B6 加載head和存盤H1的。因此，如果這兩個條件都成立，那么 A3 在總順序中在 B6 之前（或簡稱 A3 < B6）；否則 A3 將被加載H1。通過傳遞性，以及 seq_cst 總順序與排序（程式順序）一致的事實，我們有 A2 < A3 < B6 < B8。

現在因為它是一個總訂單，要么 A7 < B8 要么 A7 > B8。

如果 A7 < B8，則 B8 觀察nullptr由 A7 存盤。由于 A7 是一個發布存盤（seq_cst由通過排序 A5 發生在 A7 之前，B8 發生在 B9 之前，因此 A5 發生在 B9 之前。因此 B9 將洗掉H0，但 A5 已經完成了對它的取消參考，并且沒有資料競爭或 use-after-free。
如果 A7 > B8，那么我們有 A3 < B8 < A7。所以 B8 必須觀察存盤 A3（存盤H0到hpA），而不能觀察存盤 A7 存盤nullptr。所以在這種情況下，B8 加載 value H0，它等于執行緒 B 的值，并且執行緒 B 延遲了old_head的洗掉H0。因此，A5 處的取消參考是安全的，因為H0根本沒有被洗掉。

獲取-發布排序對于該演算法來說不夠好。非正式地，acquire-release 禁止 LoadLoad、StoreStore 和 LoadStore 重新排序，但仍允許 StoreLoad 重新排序。因此，A2 可能在 A3 之后變得可見，這將是災難性的。編輯：對于您在下面的評論，是的，B6S 也可能在 B8 和 B9 之后變得可見（B7 稍后仍然可見）。

寬松的訂購會更糟；例如，A7 可能在 A5 完成之前變得可見。

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/513746.html

標籤：C 多线程并发原子标准原子

上一篇：在Java中將單執行緒計算轉換為多執行緒

下一篇：在bash腳本中并行運行命令