爲什麼自動垃圾回收消除了ABA的問題？

我在練習冊併發調查ABA問題，維基百科和我已閱讀下列post 爲什麼自動垃圾回收消除了ABA的問題？

據我瞭解ABA問題的根本原因是，在algoritm我們檢查狀態同樣如前，但算法意味着狀態未觸及。

實施例與堆棧：

添加元素堆棧，我們使用下列algoritm：

create new stack node(save to `newNode` variable) 

while(true) { 
    oldHead = stack.get(); 
    newNode.next = oldHead; // point_1 
    if(stack.compareAndSet(oldhead, newNode)) { // atomically replace head if now head same as was in start of iteration 
     break; 
    }  
}

步驟，其LEED到ABA問題：
初始狀態

a->b->c // a-head, c- tail.

Thread_1嘗試增加值d到堆棧和OS暫停之前compareAndSet操作（_1）的螺紋
Thread_2然後執行彈出（Thread_1仍然懸浮）

B->Ç// B-頭，C-尾。
Thread_3然後執行彈出（Thread_1仍然懸浮）

Ç// C型頭，C-尾。
Thread_4然後執行推a（Thread_1仍然懸浮）

A->Ç//一個頭，C-尾。
雖然在某些情況下可能不合需要，但Thread_1會喚醒並且cas操作成功執行。

Althoug this post被接受我不明白爲什麼自動垃圾收集可以消除問題。

雖然我不是C專家，但我明白在C中你不能爲兩個不同的對象分配一個內存範圍。

你能澄清一下嗎？

來源

2017-03-17 gstackoverflow

您的混淆部分可能來自於您將數據結構本身與內容混合在一起。

在「正確的」實現中，您將有包含數據的堆棧節點，而不是數據本身。所以，你最終得到的是Node（a），Node（b）等 - 所以當某個線程推動c堆棧時，它將通過c，但它將是實際被推送的Node（c）。

這意味着，在這樣的環境中，在步驟4進入堆棧的事情不會只是a，這將是new Node(a)，這將是不同指針從Node(a)該其他線程已經看到在步驟1.這些對象可能在商業方面非常平等（所以在Java中，例如，它們的equals方法將返回true），但是指針式比較會有所不同。在這裏，我們來自動GC有所作爲的一部分。來自步驟1的被阻塞的線程仍然在堆棧/寄存器上保持對節點（a）的舊實例的引用，即使它在堆棧後被移除並且在堆中的任何地方沒有強引用。這可以防止該節點被刪除，並且可以重用內存地址，這會欺騙CAS。

請注意，如果您在線程1仍處於關鍵部分時刪除（內存方式）原始節點（a），那麼您在此提到的不良情況只能發生在非GC語言中。這是非常棘手的 - 你留下的線程指向釋放的內存塊，並且需要真的，確定它在以後的任何時候都不會被解除引用，因爲它最終會導致ABA（你可以閱讀來自釋放塊的垃圾）。

如果您沒有以Node（x）的形式實現間接層，而只是讓客戶端直接推送/彈出/修改內部節點，那麼所有的投注都是關閉的 - 客戶端可以推兩次相同的節點，之後導致無限循環。在你的例子中，它會首先刪除，然後再重新插入同一個節點，但是假設數據結構和客戶端代碼之間存在大量泄漏狀態 - 在多線程環境中非常危險，特別是如果你想試驗無鎖結構。

總而言之，自動GC不能保護ABA的所有情況。它可以保護ABA非常特殊的情況，與malloc的內存重用有關，可以針對死鎖對象引用優化的無鎖代碼。

來源

2017-03-17 10:43:43

爲什麼自動垃圾回收消除了ABA的問題？

回答

相關問題