Thread safe implementation for a career test

Question

During a test guys asked me a following question but my answer was wrong (not in my point of view). What is your opinion? Thank you in advance!

We have following thread safe implementation of the String Queue class. It is really thread safe, there is no catch in the class

public class StringQueue
{
    private object _lockObject = new object();

    private List<string> _items = new List<string>();

    public bool IsEmpty()
    {
        lock (_lockObject)
            return _items.Count == 0;
    }

    public void Enqueue(string item)
    {
        lock (_lockObject)
            _items.Add(item);
    }

    public string Dequeue()
    {
        lock (_lockObject)
        {
            string result = _items[0];
            _items.RemoveAt(0);

            return result;
        }
    }
}

Problem of this class is that it throws exception on Dequeue operation, if the queue is empty. Therefore one software developer decided to add following function to the class, which returns null if the Queue is empty:

public string DequeueOrNull()
{
    if (IsEmpty())
        return null;

    return Dequeue();
}

Is this function DequeueOrNull() thread safe?

My answer

Yes this function is safe. The function just calls two other safe functions and then it, for definition, is still safe. The explanation is, for new version of C#, when you check is the queue is empty and then you return null; C# jump the last return and then you don't received any errors. With old version of C# the last return is a problem and then you can fix it in this way:

public string DequeueOrNull()
{
    if (IsEmpty())
        return null;
    else
        return Dequeue();
}

It is NOT thread safe, because of the potential race condition. After checking if it's empty, and dequeueing, another thread could have dequeued the last item. — willaien
"What is your opinion?" - my opinion is to vote-close it as "Primarely opinion-based". Question is better suited for code-review site. — Sinatr
@Sinatr I see your point. On the other hand: thread-safety is not a matter of opinion. — René Vogt
"The function just calls two other safe functions and then it, for definition, is still safe." - By that definition all code is inherently "thread safe" because all code ultimately amounts to a series of atomic thread-safe operations. Your definition of thread safety is mistaken. — David

willaien willaien · Accepted Answer · 2016-01-22T15:42:21

The method:

public string DequeueOrNull()
{
    if (IsEmpty())
        return null;

    return Dequeue();
}

Is definitely not threadsafe (in the sense that you can still get an exception you were trying to avoid). In fact, this is a common trap in threading.

In this case, it's like saying "OK, nobody else touch this. Are you empty right now? OK, now everyone else can touch this." "OK, nobody else touch this. I know it was not empty. Now, give me what you have. OK, everyone else can touch this."

The problem is that, in between checking if it's empty and getting the item from the queue, you have given others access to the object, and thus the information you retrieved may be 'stale'. This is a fairly classic race condition.

Sidenote: I wouldn't use a collection that uses an array as a backing source for a queue, but that's beside the point of your interview.

Bonus points: In general, when you're acting upon an object with multiple threads, you have to be very careful about managing the state of that object.

If there are error-prone states that can be caused by multiple threads accessing the object (like if it uses a List<T> as a backing store), then the easiest way to interact with the object is to serialize all requests to it, but, you still need to be careful not to act upon previous information, if it's information that you're using to determine if it will cause an error or not. If you're getting information to prevent an error, then acting upon it (and assuming that there will be no error), then they need to both happen inside of a single lock statement.

Extra Bonus Points: In C#, locks can be re-entered by the same thread. So, you might be able to solve this by simply wrapping the DequeueOrNull() method in another lock statement, like so:

public string DequeueOrNull()
{
    lock(_lockObject)
    {
        if (IsEmpty())
            return null;

        return Dequeue();
    }
}

I'll leave it to others much smarter than me to determine if this would cause deadlocks or not.

Thread safe implementation for a career test

My answer

2 Answers