鎖定免費容器和可見性

Question

我見過一些無鎖的堆棧實現......我的問題是關於可見性，而不是原子性。例如，鎖釋放棧的元素（非指針）必須最多64位？我認爲是這樣，因爲你不能保證能見度。真實的例子：可以在此結構可以安全地插入和無鎖容器中取出

struct person 
{ 
    string name; 
    uint32_t age; 
} 

編輯：有些人對這個問題感到困惑。解釋一下：如果作者將人推到堆棧上，讀者得到它，保證讀者看到（記憶可見度）人的正確內容。

Answer 1

我可能是錯的，但我認爲這個問題是不正確的。原子指令處理典型的單指針長度數據;最多隻有兩個指針長度的數據。

不能被原子地操縱，因爲它太大的典型結構。因此，無鎖棧將只會操作指向元素的指針（AFAIK需要在指針長度邊界上對齊 - 我知道沒有這種情況下沒有平臺）。

Answer 2

是的結構可以使用。因爲無鎖數據結構所需的全部內容都是原子更新代表結構內部的單個值的某種方式。元素或有效載荷的大小不會對其無鎖性質產生任何影響。

據我瞭解，無鎖數據結構，將工作像這樣：

1. 將數據複製
2. 修改數據
3. 以原子檢查原始對象一直未修改和更新
4. 從一開始，否則重複

所以只要第三步可以進行原子一切都很好。

將元素本身原子可更新不會給您帶來任何好處，因爲容器必須將它們作爲一個整體進行管理。

Answer 3

注意：只有在實際測試此方法時，請將此答案標記爲正確。

關於你的問題是否低於結構被安全地插入和無鎖容器中取出：

struct person 
{ 
    string name; 
    uint32_t age; 
} 

任何長度的多字節序列可以安全地插入/自鎖免費容器中取出，如果您使用的是冗餘編碼。讓我們假設我們已經有了一次處理4個字節的原子指令（32位）。在這種情況下，我們可以編碼uint32_t age場像這樣：

struct age_t 
{ 
    uint32_t age_low; 
    uint32_t age_high; 
} 

字段age_low存儲32位uint32_t age的低比特（例如，低16位）。字段age_high存儲剩餘的高位。概念：

struct age_t 
{ 
    uint16_t age_low; 
    uint16_t id_low; 
    uint16_t age_high; 
    uint16_t id_high; 
} 

字段id_low和id_high應包含的ID標識的作家。作爲兩個原子32位讀操作，併成功如果所有的部件id_相當於彼此

讀被執行。如果失敗，則需要重新啓動讀取操作。

寫入被實現爲兩個原子的32位寫入和之後是整個age_t值的讀取。如果寫入成功：前面提到的讀取成功，讀取的ID與寫入的ID相同。

關於string值：原理是一樣的。你只需要弄清楚如何分割它的二進制值，類似於如何分割值age。在讀取/寫入整個person結構方面相同。

Answer 4

我必須承認對這個問題我稍微迷茫......

無鎖數據結構通過操縱指向節點（機器尺寸&對齊的）存在。然後這些節點包含您的無鎖數據結構的真實「內容」。該內容可以具有任意大小，因此您的結構可以放在那裏。對於無鎖數據結構通常節點看起來像：

結構節點{ATOMIC_PTR未來;內容; }

，其中的內容可以是任何你想要它是一個指向內存包含的東西或包含的東西直接內存。 可見性在這裏是一個非問題，因爲在修改無鎖數據結構時，首先分配一個新節點，然後填充所需內容，最後使用原子操作來正確設置各種涉及的指針。由於這是你做的最後一件事，而且這些操作通常都會涉及內存障礙以保證可見性和順序，所以你很好。

Answer 5

線程安全的容器（lockfree或鎖定爲此事）解決列表/容器不是線程你把容器內的物品的安全線程安全。 因此，無鎖棧將確保push和pop是線程安全且無鎖的，但是如果您有兩個不同的線程持有指向同一個結構實例的指針（例如，推入堆棧的線程仍然持有ponter和另一個線程線程彈出堆棧），你必須使用一些其他的線程安全的措施，以保證結構的一致性

Answer 6

據上的其他QNA的，

• Does Interlocked.CompareExchange use a memory barrier?
• question about lock free queues

每個x86互鎖指令（包括CAS）意味着一個完整的內存屏障。因此，至少在x86上，我們不需要關心無鎖容器元素的可見性（假設他們使用CAS）。）

Answer 7

一個可以實現對任意大小的數據元素出隊的一個線程安全的實現，如果內容沒有被存儲在任何特定的順序棧或隊列中，如果一個使用一個線程安全的隊列保存未分配項目的索引以及線程安全出列，以保存保存入隊/堆疊項目的數據槽的索引。將項目寫入出隊列表需要從「未分配的插槽」隊列中拉出一個數字，將所需的數據寫入該插槽，然後將該數字的索引排入「主」出列隊列。獲取物品需要從「主要」出列中抽取其編號，將其複製到別處，然後將該編號排入「未分配的插槽」隊列中。

這種方法的一個警告是它雖然它可能是「無鎖」的，因爲停頓的線程不能任意延遲其他線程的進程，線程在獲取時隙索引的時間一個隊列及其將其存儲在另一個隊列中的時間可能導致陣列插槽在任意時間長度內不可用。相比之下，用於較小數據類型的一些無等待堆棧或隊列實現沒有這種限制。一個線程在讀期間存在消失或寫，系統要麼是表示該讀或寫完成，否則處於有效狀態，表明它從未開始有效狀態。