c# - ThreadSafe LinkedList实现

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属性来双重链接列表。

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

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

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

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