没有锁的Threadsafe集合

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

您可以创建一个非阻塞链表。例如这样的事情。

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