ThreadSafe链表实现

Question

我知道链表不是线程安全的，在工作中我被要求编写一个简单的线程安全链表。

由于我不会经历的各种复杂情况，我不能简单地包装 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 属性来双重链接该列表。

使链表成为线程安全的主要问题是，与索引集合不同，最多必须同时锁定三个对象才能执行添加和删除操作。例如，如果另一个线程正在枚举列表，则这会增加死锁的可能性；添加/删除线程需要锁定第四个节点才能删除第五个节点，而枚举线程已经锁定了第四个节点，需要锁定第五个节点。单链表也会有同样的问题，因为该算法需要另一个枚举顶部确定“前一个”节点，这最终会阻止尝试到达第四个项目，该项目已经被第一个枚举器锁定等待到达第五项。

我想有一个大问题要问：您究竟需要如何添加和删除项目？如果此实现将用作堆栈或队列后面的集合，则使其成为线程安全变得更加容易，因为不允许枚举列表，并且当前在列表中的节点中，只有端点节点（一个用于堆栈，两个用于队列）在添加/删除时需要锁定，除非堆栈或队列只有一项，否则锁定这些节点只会阻止其他线程尝试添加或删除。

如果这是一个完整的链表实现，在导航到任何项目以及从任何位置添加和删除方面需要与列表类似的功能，那么我认为最好的选择是将节点隐藏在包装器后面，该包装器将在执行任何操作之前锁定自身操作，就像 Interlocked 对整数类型所做的那样。无论如何，这都不是一种“细粒度”的方法。任何想要对列表执行任何操作的线程都必须等待轮到它。当尝试允许多个线程同时访问时，出现死锁的机会太多。

对于没有死锁的细粒度、线程安全锁定的唯一希望是始终以枚举列表的相同顺序获取锁，并且只允许在一个方向上进行迭代。基本上，这需要您隐藏双向链表的“前一个”节点，并允许节点获取其他节点上的“持久”锁。