CircularBuffer, do i need to add a lock?

Question

I'm new to the whole circular/ring buffer way of thinking. I read some articles about how it should work in theory and came up with this code example. In my scenario I will have multiple threads writing and a single thread reading from the buffer.

Do I need to add a lock to the write method?

Thanks in advance!

public class CircularBuffer<T>
{
    private readonly int _size;

    private int _head;
    private byte _headMirrorSide;

    private int _tail;
    private byte _tailMirrorSide;

    private readonly T[] _buffer;

    public CircularBuffer() : this(300) { }

    public CircularBuffer(int size)
    {
        _size = size;
        _buffer = new T[_size + 1];

        _head = 0;
        _headMirrorSide = 0;

        _tail = 0;
        _tailMirrorSide = 0;
    }

    private bool IsFull()
    {
        return _tail == _head && _tailMirrorSide != _headMirrorSide;
    }

    public bool IsEmpty()
    {
        return _tail == _head && _tailMirrorSide == _headMirrorSide;
    }

    private void MovePointer(ref int pointer, ref byte mirrorSide)
    {
        pointer = pointer + 1;

        if (pointer == _size)
        {
            mirrorSide ^= 1;
            pointer = 0;
        }
    }

    public void Write(T obj)
    {
        _buffer[_head] = obj;

        if (IsFull())
        {
            MovePointer(ref _tail, ref _tailMirrorSide);
        }
        MovePointer(ref _head, ref _headMirrorSide);
    }

    public T Read()
    {
        var obj = _buffer[_tail];
        _buffer[_tail] = default(T);

        MovePointer(ref _tail, ref _tailMirrorSide);

        return obj;
    }
}

Edit: The end result was something like this.

public class CircularBuffer<T> where T : class 
{
    private readonly int _size;

    private int _head;
    private byte _headMirrorSide;

    private int _tail;
    private byte _tailMirrorSide;

    private readonly T[] _buffer;

    private readonly object _lock = new object();

    public CircularBuffer() : this(300) { }

    public CircularBuffer(int size)
    {
        _size = size;
        _buffer = new T[_size + 1];

        _head = 0;
        _headMirrorSide = 0;

        _tail = 0;
        _tailMirrorSide = 0;
    }

    private bool IsFull()
    {
        return _tail == _head && _tailMirrorSide != _headMirrorSide;
    }

    private bool IsEmpty()
    {
        return _tail == _head && _tailMirrorSide == _headMirrorSide;
    }

    private void MovePointer(ref int pointer, ref byte mirrorSide)
    {
        pointer = pointer + 1;

        if (pointer == _size)
        {
            mirrorSide ^= 1;
            pointer = 0;
        }
    }

    public void Write(T obj)
    {
        lock (_lock)
        {
            _buffer[_head] = obj;

            if (IsFull())
            {
                MovePointer(ref _tail, ref _tailMirrorSide);
            }
            MovePointer(ref _head, ref _headMirrorSide);
        }
    }

    public T Read()
    {
        lock (_lock)
        {
            if (IsEmpty())
            {
                return null;
            }

            var obj = _buffer[_tail];
            MovePointer(ref _tail, ref _tailMirrorSide);

            return obj;
        }
    }
}

Making a circular buffer thread-safe and wait-free is an easy exercise for 1 Producer and 1 Consumer. But your code is not even safe in that scenario. Supporting multiple writers is a lot more complicated. — H H, Sep 28 '13 at 13:31
Focus the question on what you really need, and why not ConcurrentQueue. — H H, Sep 28 '13 at 13:32
I need a limited FIFO list with the functionality that the "old" values are overwritten if the limit is reached. Shouldn't a ring buffer satisfy those requirements quite well? — mckn, Sep 28 '13 at 15:37
Could anyone point me in the right direction if I want to write a lock free thread-safe implementation? Could you recommend any blogpost, books etc? — mckn, Sep 29 '13 at 18:22
I can recommend not doing it. See [this answer](http://stackoverflow.com/a/871313/60761) or [this one](http://stackoverflow.com/a/2048803/60761) — H H, Sep 29 '13 at 18:29
Oh, I see..thanks! Do you have any more feedback on how to improve my last code example above? — mckn, Sep 29 '13 at 20:00

score 1 · Answer 1 · answered Sep 28 '13 at 12:24

1

If you have multiple threads accessing the buffer and all of them ONLY read, then you don't have to use a lock. However, if one or more threads are modifying data, then you'll need a lock. So in your case the answer is a clear, definitive YES, especially since your Read() method also changes data: the position of the buffer pointer.

answered Sep 28 '13 at 12:24

JensG

13,148
4
45
55

Actually the answer is "no" to the question "do I have to add a lock to the write function?" Because he clearly also needs something for read ;) – Voo Sep 28 '13 at 12:40

score 1 · Accepted Answer · answered Sep 28 '13 at 12:28

As far as you're touching the data from different threads, you have to synchronize the access. The simplest way is lock() instruction, and it should be placed at both Read() and Write() methods.

Obviously, Write() should has lock() to avoid concurrent submit into the same memory cell (because the buffer is accumulating the data from every writer, not "winner" only).

Read() should have lock() as well because it

modifies same internal members as Write() does
can be affected by compiler optimization as well as run-time instruction re-ordering (because computational effect is the same, but inter-thread interaction may be ruined)

P.S. At advanced level, you may use one-way memory barriers instead of unidirectional locks, but this requires a lot of experience

CircularBuffer, do i need to add a lock?

2 Answers2