January 28, 2009 by Oren Ellenbogen on Uncategorized

ReaderWriterLock, my naive implementation

Ron challenged me to write my own implementation of reader/writers lock. He did a great job of doing his own implementation.

I came up with this:
(note: this is really naive implementation, it’s far from ideal in terms of fairness and possible racing conditions. Just take it as brain-teaser)

public class StateReaderWriterLock : IDisposable
    {
        private readonly AutoResetEvent _changeStateAutoLock = new AutoResetEvent(false);
        private readonly AutoResetEvent _writerDone = new AutoResetEvent(false);
        private readonly object _readersLock = new object();
        private readonly object _writersLock = new object();
        private int _readers;
        private int _state; // 0 is "neutral", 1 is read, 2 is write
        private int _writers; 
  
        public void LockReader()
        {
            while (true)
            {
                // try to bring the state from "neutral" or "read" to "read". If the current state is "write", let's wait.
                while (Interlocked.CompareExchange(ref _state, 1, 0) == 2)
                    _changeStateAutoLock.WaitOne(); 
  
                // an interesting case here where the last reader is now in ReleaseRead and we're trying to read as well, we might be too late (the writer might have changed the _state already)
                // if that happens - we're back to square one, but we still want to avoid recursive locking!
                bool loseInRace = false;
                lock (_readersLock)
                {
                    if (Interlocked.CompareExchange(ref _state, 1, 0) == 2)
                        loseInRace = true;
                    else
                        _readers++;
                }
                if (!loseInRace)
                    return; // success!
            }
        } 
  
        public void ReleaseReader()
        {
            lock (_readersLock)
            {
                _readers--; 
  
                // if I am the last reader, let's reset the state so any given reader/writer can take it
                if (_readers == 0)
                {
                    Thread.VolatileWrite(ref _state, 0);
                    _changeStateAutoLock.Set();
                }
            }
        } 
  
        public void LockWriter()
        {
            while (true)
            {
                // try to bring the state from "neutral" or "write" to "write". If the current state is "read", let's wait.
                while (Interlocked.CompareExchange(ref _state, 2, 0) == 1)
                    _changeStateAutoLock.WaitOne(); 
  
                bool loseInRace = false;
                lock (_writersLock)
                {
                    if (Interlocked.CompareExchange(ref _state, 2, 0) == 1)
                        loseInRace = true;
                    else
                        _writers++;
                } 
  
                if (!loseInRace)
                    break; // great success!
            } 
  
            // allow 1 writer only
            if (Thread.VolatileRead(ref _writers) > 1)
            {
                _writerDone.WaitOne();
            }
        } 
  
        public void ReleaseWriter()
        {
            lock (_writersLock)
            {
                _writers--; 
  
                // if I am the last writer, let's reset the state so any given reader/writer can take it
                if (_writers == 0)
                {
                    Thread.VolatileWrite(ref _state, 0);
                    _changeStateAutoLock.Set();
                }
                else
                {
                    _writerDone.Set();
                }
            }
        } 
  
        public void Dispose()
        {
            _changeStateAutoLock.Close();
            _writerDone.Close();
        }
    }
  

Not sure it’s the greatest job interview question, but it is indeed challenging and fun to play with.

January 28, 2009 by Oren Ellenbogen on Uncategorized

On Interlocked.Increment and volatile

Imagine you’ve got the following code, running in 2 separate threads T1 and T2:

private bool _go = true;

T1                                      T2
while (_go)                        // … some code here …
{                                         _go = false; // something happened, let’s stop
   // … do work
}

Even if T2 will set _go to false, this code might lead to endless loop in T1. Why is that?
Each CPU have a local memory called L1 Cache, that might cache the value of _go. Multiple threads running on multiple CPU’s can (and will) cache data and re-order instructions to optimize code. So if for example, T1 is running on processorA and T2 is running on processorB, we might have an endless loop here. A simple solution here is to add the volatile keyword on the _go field definition to assure order and avoid caching on CPU level:

“The volatile modifier is usually used for a field that is accessed by multiple threads without using the lock statement to serialize access. Using the volatile modifier ensures that one thread retrieves the most up-to-date value written by another thread.” (MSDN)

Now let’s examine another example, again 2 threads T1 and T2:

private int _writers = 0;

T1                                                         T2
while (_writers > 1)                              ….
{                                                           Interlocked.Increment(ref _writers);
    _someAutoEvent.WaitOne();
}

You can see that we’re using an atomic increment via Interlocked.Increment method, so we should be thread-safe here right? not quite.
We’ve got one thread that is reading (T1) and another thread that is writing (T2) to _writers. If T1 is running in processorA and T2 in processorB, the _writers value will be cached on the CPU level for some time which means T1 might see different value than T2. If T2 would have catch the returned value from Interlocked.Increment and it as the only reader of that field, then it was thread-safe. This is not the case here.
The solution here is to use Thread.VolatileRead(ref _writers) to make sure T1 gets the latest value. We could have used lock keyword as well of course to serialize access to _writers field.

Summary:

Although setting a word size variable is atomic (like in our first example), it doesn’t mean it is thread-safe! For “boolean flags” I would recommend using volatile as a clean and simple solution.
For “counters scenarios”, I would have used Interlocked with Thread.ReadVolatile. This should outperform lock usage and still keep your code neat and shiny.
The lock keyword is probably the safest way to avoid dangerous race conditions, so unless you’re sure about your solution, keep it simple and use lock.

Oren Ellenbogen's Blog

Entrepreneurship, Management, Coding and monkey tricks.

Day: January 28, 2009

ReaderWriterLock, my naive implementation

On Interlocked.Increment and volatile