4

Take a look at the code below. Assume that this is the ENTIRE class. I have not omitted ANY code. This is literally all it does.

If I instantiate this class in my main program loop and call myExample.Add(whatever) from time to time, do I need to worry about any problems caused by not locking around Dequeue() and Enqueue()?

public class Example<T>
{
    private Queue<T> q = new Queue<T>();

    public Example()
    {
        new Thread(() => 
        {
            while (true) 
            {
                if (this.q.Count > 0)
                {
                    var item = this.q.Dequeue();
                }
                Thread.Sleep(1);
            }
        }).Start();
    }

    public void Add(T val)
    {
        this.q.Enqueue(val);
    }
}

What happens if this.q.Enqueue(val) is called at the same time as this.q.Dequeue()?

core
  • 32,451
  • 45
  • 138
  • 193

8 Answers8

8

The short version is you must synchronize access to a queue if you expect it to function. There are obvious thread races in the Count/Dequeue, but more importantly no operation is guaranteed - the internal state could legitimately do anything, and is likely to be corrupted.

You would also want a way of exiting the thread eventually...

To write a blocking queue, see here: Creating a blocking Queue<T> in .NET.

Community
  • 1
  • 1
Marc Gravell
  • 1,026,079
  • 266
  • 2,566
  • 2,900
  • But why? Marc, I know you're way smarter than I am, but if you're gonna get these points, you need to tell me what the obvious race conditions are. :) I agree with you about the internal state, but what about the race conditions? – core May 14 '09 at 08:50
  • OK - the race condition *in this case* probably isn't significant; there aren't going to be multiple readers. However, threading is hard: to determine that there *isn't* a race condition (without the lock) I need to read the code and understand the calling pattern. Why not make it *obvious* that there is no potential for a race by locking over the count/dequeue? This also means that when you extend the class later you haven't got to go bug hunting. – Marc Gravell May 14 '09 at 09:51
2

It depends. :) If you call into Example with multiple threads, you will have a race condition between your check for the count of the queue and the dequeue. For example ...

T1 Call Example
T2 Call Example
T2 check Q.Count > 0 (yes)
T1 check Q.count > 0 (yes)
T2 dequeue
T1 dequeue OOPS!

If you don't call into example with multiple threads, then you will have no problem since you don't care what you take off, only that you take something off. If you cared what you took off, then the race condition between Add and Example would be an issue again.

JP Alioto
  • 44,864
  • 6
  • 88
  • 112
  • I was thinking this at first, but the only place the queue gets dequed is inside the one loop... so anything external to the Example class should only be able to queue things, and wouldn't be able to see the queue. – uzbones May 14 '09 at 03:56
  • Each thread that calls into Example forks a new thread that enters that loop. If I send 10 threads into Example, I will have 10 threads running in that loop. Those threads never return. So, it will build up over time and you will have a race condition. – JP Alioto May 14 '09 at 04:00
  • They aren't static classes, so they would all be seperate objects, and the constructor is what creates the thread, so it would always be 1 thread per object. – uzbones May 14 '09 at 04:04
1

Chris

Add a private static field

readonly static object lockObject = new object();

enclose the dequeue and enqueue with

lock(lockObject)
{
  //do stuff
}

for your lambda put it outside the loop

Gary
  • 1,847
  • 2
  • 14
  • 22
1

Since you're writing to the Queue via the Dequeue method you do need to lock it. Queues are thread safe for multiple readers but not multiple writers Queue thread safety.

sipsorcery
  • 30,273
  • 24
  • 104
  • 155
  • Note that the "reader" in that scenario is foreach, not Dequeue (which is a "write"). As such; in reality, it is simpler to say that queues don't usefully support multiple callers. At all. – Marc Gravell May 14 '09 at 04:03
1

MSDN says that Queue is not thread safe: http://msdn.microsoft.com/en-us/library/7977ey2c.aspx

Jonathan Parker
  • 6,705
  • 3
  • 43
  • 54
0

I assume by 

this.queue.Enqueue(val);

you mean

this.q.Enqueue(val);

?

If so, then yes, you need to perform some sort of locking. Collections aren't inherently thread safe. Considering that you're always removing from one thread, and always adding from another it MIGHT work ok, but why not play it safe?

Dan Fuller
  • 1,133
  • 11
  • 16
  • I don't believe it will ever be safe, since the Queue is liable to resize its internal array at any moment. – Nick Farina May 14 '09 at 03:59
  • I agree, I belive the enqueuing could have issues, because you could attempt to dequeue something before it's fully queued, or write two items into the same position in the internal array. – uzbones May 14 '09 at 04:02
0

I don't see why you think it might be safe.

My worry/assumption is that entering the Enqueue and Dequeue simultaneously (from two different threads) might corrupt the internal state of the Queue instance.

ChrisW
  • 54,973
  • 13
  • 116
  • 224
0

Since you are explicitly creating a separate thread which modifies the Queue, it is not ever safe to call Add(), regardless of what thread you call it from.

You need to lock() the "if" statement block since it's not even safe to call q.Count, then lock again in the Add() method.

Nick Farina
  • 4,470
  • 2
  • 32
  • 30