Lock-free producer/consumer implementation

Question

I know of BlockingCollection in .net, but this is rather for my understanding of the pattern. Is this implementation correct ?

Consumer

class Consumer
{
    readonly Queue<int> _q;

    public Consumer(Queue<int> q)
    {
        this._q = q;
    }

    public void Consume()
    {
        for (int i = 0; i < 10; i++)
        {
            while (_q.Count == 0)
            {
            }

            Console.WriteLine("consuming " + _q.Dequeue());
        }

    }
}

Producer

class Producer
    {
        readonly Queue<int> _q;
        readonly int _maxSize;

        public Producer(Queue<int> q, int maxSize)
        {
            this._q = q;
            this._maxSize = maxSize;
        }

        public void Produce()
        {
            for (int i = 0; i < 10; i++)
            {
                while (_q.Count == _maxSize)
                {
                }

                Console.WriteLine("producing " + (i + 1));
                _q.Enqueue(i + 1);
            }    
        }
    }

Client

class Program
    {
        static void Main(string[] args)
        {
            Queue<int> q = new Queue<int>();
            var prod = new Producer(q, 10);
            var consumer = new Consumer(q);

            var producerThread = new Thread(new ThreadStart(prod.Produce));
            producerThread.Start();

            var consumerThread = new Thread(new ThreadStart(consumer.Consume));
            consumerThread.Start();
        }
    }

The way I see it, this handles the race condition in Inadequate implementation by introducing while instead of if

The program runs fine on my machine, so is this correct or am i missing something? why the need for synchronization?

Answer 1

The bigest problem is that code while(true){} will eat up all CPU that is available for the thread. Try running your program on a single core machine (it will run fine because you are only producing 10 items but try producing infinite number - they should still be consumed properly). The minimum change should be while(condition) Thread.Yield() or Thread.Sleep(). Yielding will still eat up all CPU but sleeping will put your thread down for longer than might be needed - this is why synchronization is used - to notify the other thread instead of making it sleep and try guessing when the new data will arrive.

More important issue that requires synchronization is that Queue.Enqueue() and Queue.Dequeue() will most probably not be atomic operations - what happens if you enqueue an item while it is dequeing? This is why classes like ConcurrentQueue have been created in .NET Framework.

Next problem is a situation with multiple consumers. Assume two consumers and one item in the queue. If both of them run at the same time, they will both at the same time detect that q.Count == 1. Now the first of them dequeues the only item from the queue. Now the second one tries to dequeue but there is nothing there anymore - it will throw an exception.