中斷安全組掃描

Question

我需要一個數據結構實現這些有點不尋常（據我所知）要求：

1. 支持的操作是插入（套，件），刪除（套，條）和FORALL（套，操作）
2. 插入和刪除是罕見的操作。該集合通常只包含一個項目。
3. 在C中實現必須是可行的;特別是，你沒有垃圾收集。
4. ForAll必須安全，可以從異步信號處理程序執行，其調用可能會中斷Insert或Delete。

當然，最後的要求是殺手。我有一個玩具實現，它會在全局鏈表上引發一個全局鎖，但是如果信號處理程序中斷了一個關鍵部分，那麼就會發生死鎖。我知道在信號處理程序中執行任意代碼的所有問題;爲了解決這個問題，我們着重討論如何使ForAll崩潰和死鎖安全，因爲它可能會中斷Insert或刪除）。

Answer 1

如果這些集合通常很小，這樣在插入和刪除方法中列表的線性搜索速度足夠快，那麼您可以使用使用比較和交換的無鎖鏈接列表實現。搜索給出了一些解釋和例子。

http://www.google.com/search?q=lock+free+linked+list

所有更新的列表作爲原子操作（比較並交換），因此中斷不會引起問題進行。

Answer 2

我確信Jim的方法很好，但是對於小集和偶爾更新，您可能會更樂意實現最簡單的軟件事務內存形式。

1. 讀取指向當前版本結構的指針。
2. 製作該版本的副本並進行更新。
3. 比較和交換的更新。如果CAS失敗，請返回步驟1.

異步掃描是微不足道的 - 讀取和去除。如果沒有垃圾回收，你需要使用Jim鏈接的文件中的SafeRead和Release之類的東西。