ThreadSafe的鏈表實現

Question

我知道，LinkedList的是不是線程安全的，並在工作中我一直在要求寫一個裸露的骨頭線程安全的鏈表。

因爲我不會去通過我不能簡單地換一個LinkedList，但需要編寫一個LinkedList的實現各種併發症的

我猜我需要這一點，但我怎麼能真正實現一個枚舉（對於linedlist ）以線程安全的方式？

public class LinkedlistNode 
    { 
     private LinkedlistNode next; 
     private T item; 
     /// <summary> 
     /// Constructor for a new LinklistNode 
     /// </summary> 
     /// <param name="node">The node item to create</param> 
     public LinkedlistNode(T node) 
     { 
      next = null; 
      item = node; 
     } 
     /// <summary> 
     /// Shows the next item in the collection (or shows null for the the last item) 
     /// </summary> 
     public LinkedlistNode Next 
     { 
      get { return next; } 
      set { next = value; } 
     } 
     /// <summary> 
     /// The contents of the list 
     /// </summary> 
     public T Item   
     {    
      get { return item; }    
      set { item = value; }   
     }    
    } 

Answer 1

良好的開端。首先，我會雙重鏈接列表，包括一個與Next類似的Previous屬性。

與製作鏈表線程安全的主要問題是，不像是一個索引集合，有多達必須在同一時間被鎖定進行添加和刪除三個對象。例如，如果另一個線程在列表中枚舉，則會增加死鎖的可能性;添加/刪除線程需要鎖定第四個節點以刪除第五個節點，而枚舉線程已經鎖定第四個項目並需要鎖定第五個節點。單鏈表可能會遇到同樣的問題，因爲該算法需要另一個枚舉頂點來確定「前一個」節點，該節點最終會阻止嘗試訪問第一個已被第一個枚舉器鎖定的第四個項目，第五項。

我想有一個很大的問題要問：你需要究竟如何添加和刪除的項目？如果此實現將用作堆棧或隊列後面的集合，則使其更容易線程安全，因爲枚舉列表將不被允許，並且當前列表中的節點只有端點節點（一個用於堆棧，另一個用於隊列）需要在添加/刪除時被鎖定，除非堆棧或隊列只有一個項目，否則鎖定這些節點將僅阻止嘗試添加或刪除的其他線程。

如果這是一個完整的鏈接列表實現，需要與列表類似的功能來導航到任何項目和添加和從任何地方刪除，那麼我認爲你最好的選擇是隱藏節點在將封鎖的封裝之後本身在執行任何操作之前，就像互鎖使用整型類型一樣。這不是一種「細粒度」的方法;任何想要對列表做任何事情的線程都必須等待。嘗試允許多個線程同時訪問時，出現死鎖的機會太多了。

您的細粒度，線程安全鎖定唯一的希望不死鎖是始終獲取鎖以相同的順序清單將被枚舉，並只允許重複在一個方向。基本上，這要求您隱藏雙鏈表的「Previous」節點，並允許節點獲取其他節點上的「永久」鎖。

Answer 2

有一個廣泛的答案，在這個問題/答案在mulithreaded情況SLLs執行：

Thread-safe deletion of a linked list node, using the fine-grained approach