线程收集无锁 [英] Threadsafe collection without lock

问题描述

我准备自己接受记者采访时，我整个followign问题就来了。我试过，但我找不到任何可以创建一个包含线程安全的集合类，而不锁。如果知道的任何解决方案，请您帮助

I am preparing myself for an interview and I came across the followign question. I tried but I could not find anything which can create a class containing thread safe collection without "lock". If know any solution then please help.

创建对象派生的C＃类并实现以下方法：

Create a C# class derived from Object and implements the following methods:

• AddString - 这个方法应该给定的字符串添加到内部集合


• 的ToString - 重写此方法并返回一个包含所有的字符串一个单一的，逗号分隔的字符串内部集合

要求：

• 必须是线程安全


• 必须支持多个并发读取器


• 不得使用任何预先存在的线程安全的集合


• 奖励：不使用任何类型的锁

• Must be thread-safe
• Must support multiple concurrent readers
• Must not use any pre-existing thread-safe collections
• Bonus: don’t use any type of lock

推荐答案

下面是一个通过在本地副本工作实现了集合的无锁的修改，然后尝试与全球征集原子掉它，同时检查比赛方式：

Here’s a way of achieving lock-free modification of a collection by working on a local copy and then attempting to atomically swap it with the global collection whilst checking for races:

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 调用而不是

Edit: Since using Interlocked.CompareExchange to implicitly perform volatile reads and writes has given rise to some confusion, I’m posting below the equivalent code with Thread.MemoryBarrier calls instead.

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);
    }
}

这篇关于线程收集无锁的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！