Threadsafe collection without lock

Question

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.

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

• AddString – This method should add a given string to an internal collection
• ToString – Override this method and return a single, comma-delimited string containing all the strings in the internal collection

Requirements:

• 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

Answer 1

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

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

Answer 2

Based on the question you should be able to add a concurrent collection inside your object that will handle the thread safety requirements for you. They did not specify what type of internal collection to use.

You should be able to implement one of the collections from the concurrentcollection namespace and achieve this.

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