在行動書採用分體式引用計數的併發鎖免費棧的實現

-1

在安東尼·威廉姆斯在行動書併發，他實現了採用分體式引用計數鎖免費棧。在頭節點的初始加載之後。在這裏他使用下面代碼中列出的方法調用increase_head_count。在行動書採用分體式引用計數的併發鎖免費棧的實現

counted_node_ptr old_head = head.load(); 
increase_head_count(old_head); 

void increase_head_count(counted_node_ptr& old_counter) 
{ 
    counted_node_ptr new_counter; 

    do 
    { 
     new_counter = old_counter; 
     ++new_counter.external_count; 
    } 
    while (!head.compare_exchange_strong(old_counter, new_counter)); 

    old_counter.external_count = new_counter.external_count; 
}

完整的實現可以在這個鏈接中找到https://github.com/subjam/concurrency-in-action/blob/master/ch7/stack_ref.cpp。我的問題是，如果一個senario發生多個線程試圖同時執行pop（）並且所有線程讀取頭節點，然後只有一個線程執行直到結束，其他人開始執行這個功能，然後這個實現是如何工作的。

我在這裏呆了一段時間，如果有人能幫助我理解這一點，我會很高興。

來源

2017-04-26 Kasun

如果在while子句中，old_counter仍然等於new_counter，那麼head設置爲new_counter。在任何一次成功的單線程中都是這種情況。

對於其他線程同時訪問此方法，compare_exchange_strong（）返回false導致循環迭代。但是，它也會複製old_counter的內容。

這意味着在這些其他（不成功）線程的下一個循環中，old_counter已更新爲head的當前內容。

來源

2017-04-26 15:37:55

謝謝你的答案..我對這個問題沒有多少懷疑。有兩個線程來執行increase_head_count函數，一個在開始時暫停。現在有一個線程會一直執行，甚至在暫停線程喚醒時甚至會刪除old_node指針（請參閱鏈接中給出的完整實現），是不是會拋出異常（無效的內存或類似的東西）執行時++ new_counter.external_count;因爲它代表被刪除的節點（由第一個線程）。 – Kasun

第一個線程（通過'increase_head_count（）'方法一路通過）將在刪除它之前控制'head'。它試圖在刪除之前將其從堆棧中刪除。當它從堆棧中成功移除時，第二個線程（在'increase_head_count（）'中喚醒）將不會有任何頭的引用。正如我上面所說的，'old_counter'現在將被更新爲指向新的'head'，所以它不會嘗試訪問任何已被刪除的節點。 –

我使用此代碼的擔憂是，如果最後的第一個（成功）的線程獲得推節點，'head'現在指向原來'counted_node_ptr'，代碼（在方法'pop'）這第二個線程不會試圖刪除這個'head'，因爲'ptr'是'NULL'。不刪除頭部會允許在'count_node_ptr'內循環的所有輔助線程離開'pop'返回一個空值'T'。然而'head'的原始值'ptr'不能保證是'NULL'，因爲沒有構造函數它就不會被初始化。 –

在行動書採用分體式引用計數的併發鎖免費棧的實現

回答

相關問題