c# - 没有锁的线程安全集合

Question

我正在准备自己的面试，我遇到了以下问题。我试过了，但我找不到任何东西可以创建一个包含没有“锁”的线程安全集合的类。如果知道任何解决方案，请提供帮助。

创建一个从 Object 派生的 C# 类并实现以下方法：

• AddString – 此方法应将给定字符串添加到内部集合
• ToString – 覆盖此方法并返回一个以逗号分隔的字符串，其中包含内部集合中的所有字符串

要求：

• 必须是线程安全的
• 必须支持多个并发阅读器
• 不得使用任何预先存在的线程安全集合
• 奖励：不要使用任何类型的锁

Answer 1

这是一种实现集合的无锁修改的方法，方法是处理本地副本，然后在检查竞争时尝试以原子方式将其与全局集合交换：

public class NonLockingCollection
{
    private List<string> collection;

    public NonLockingCollection()
    {
        // Initialize global collection through a volatile write.
        Interlocked.CompareExchange(ref collection, new List<string>(), null);
    }

    public void AddString(string s)
    {
        while (true)
        {
            // Volatile read of global collection.
            var original = Interlocked.CompareExchange(ref collection, null, null);

            // Add new string to a local copy.
            var copy = original.ToList();
            copy.Add(s);

            // Swap local copy with global collection,
            // unless outraced by another thread.
            var result = Interlocked.CompareExchange(ref collection, copy, original);
            if (result == original)
                break;
        }
    }

    public override string ToString()
    {
        // Volatile read of global collection.
        var original = Interlocked.CompareExchange(ref collection, null, null);

        // Since content of global collection will never be modified,
        // we may read it directly.
        return string.Join(",", original);
    }
}

编辑：由于使用Interlocked.CompareExchange隐式执行易失性读取和写入引起了一些混乱，因此我在等效代码下方发布了Thread.MemoryBarrier调用。

public class NonLockingCollection
{
    private List<string> collection;

    public NonLockingCollection()
    {
        // Initialize global collection through a volatile write.
        collection = new List<string>();
        Thread.MemoryBarrier();
    }

    public void AddString(string s)
    {
        while (true)
        {
            // Fresh volatile read of global collection.
            Thread.MemoryBarrier();
            var original = collection;
            Thread.MemoryBarrier();

            // Add new string to a local copy.
            var copy = original.ToList();
            copy.Add(s);

            // Swap local copy with global collection,
            // unless outraced by another thread.
            var result = Interlocked.CompareExchange(ref collection, copy, original);
            if (result == original)
                break;
        }
    }

    public override string ToString()
    {
        // Fresh volatile read of global collection.
        Thread.MemoryBarrier();
        var original = collection;
        Thread.MemoryBarrier();

        // Since content of global collection will never be modified,
        // we may read it directly.
        return string.Join(",", original);
    }
}

Answer 2

根据问题，您应该能够在对象中添加一个并发集合，该集合将为您处理线程安全要求。他们没有指定使用哪种类型的内部集合。

您应该能够从 concurrentcollection 命名空间实现其中一个集合并实现这一点。

http://msdn.microsoft.com/en-us/library/system.collections.concurrent.aspx

Answer 3

您可以创建一个非阻塞链表。例如像这样的东西。

.net 框架提供了类似的方法CompareExchange(Object, Object, Object)，允许您编写安全代码而无需锁定整个列表。

Answer 4

我的解决方案。基本上使用 Interlocked.Exchange 和 AutoResetEvents 模拟锁定。做了一些简单的测试，它似乎工作。

    public class SharedStringClass
    {
        private static readonly int TRUE = 1;
        private static readonly int FALSE = 0;

        private static int allowEntry;

        private static AutoResetEvent autoResetEvent;

        private IList<string> internalCollection;

        public SharedStringClass()
        {
            internalCollection = new List<string>();
            autoResetEvent = new AutoResetEvent(false);
            allowEntry = TRUE;
        }

        public void AddString(string strToAdd)
        {
            CheckAllowEntry();

            internalCollection.Add(strToAdd);

            // set allowEntry to TRUE atomically
            Interlocked.Exchange(ref allowEntry, TRUE);
            autoResetEvent.Set();
        }

        public string ToString()
        {
            CheckAllowEntry();

            // access the shared resource
            string result = string.Join(",", internalCollection);

            // set allowEntry to TRUE atomically
            Interlocked.Exchange(ref allowEntry, TRUE);
            autoResetEvent.Set();
            return result;
        }

        private void CheckAllowEntry()
        {
            while (true)
            {
                // compare allowEntry with TRUE, if it is, set it to FALSE (these are done atomically!!)
                if (Interlocked.CompareExchange(ref allowEntry, FALSE, TRUE) == FALSE)
                {
                    autoResetEvent.WaitOne();
                }
                else
                {
                    break;
                }
            }
        }
    }

Answer 5

最简单的解决方案是拥有一个 type 字段string[]。每当调用者想要添加一个字符串时，创建一个新数组并附加新项并将其交换为旧项。

此模型不需要同步。它不容忍并发写入者，但它允许并发读取。