stl deque thread safety

[AndyMcHugh]

Is it safe to add objects to the end of a deque from one thread whilst another thread is reading and deleting objects from the beginning of the same deque instance?

It appears to be working but I'm not sure if this is just luck. I'm using MSVC .NET and also the gnu compiler provided with VxWorks.

[Andreas Masur]

Well...it kind of depends on the STL implementation you are using, however, the following are more or less general rules:

From the STLport:


Simultaneous read access to the same container from within separate threads is safe
Simultaneous access to distinct containers (not shared between threads) is safe
User must provide synchronization for all accesses if any thread may modify shared container

[AndyMcHugh]

[QUOTE=Andreas Masur]Well...it kind of depends on the STL implementation you are using, however, the following are more or less general rules:

Thanks for replying. The general rules kind of say no, but I'd have thought in reality, the answer is more fuzzy.

I was thinking along the lines that if one thread was just pushing things onto the end of the deque, and as these additions occur in constant time, there can't be anything changing at the front of the deque; so another thread should be able to at least just read or perhaps even change the first deque entry without any conflict.

If this was true it would be very useful. If the thread looking at the begining of the deque could also pop things off the front whilst the other thread was pushing them on the back that would be ideal.

I know I could put some critical section stuff round this but I'm trying to avoid it if at all possible as it could impact the timings.

I realise that this may not be supported by every STL, but knowing which ones were OK with it would be useful. Any more insight would be greatly appreciated. If this is really a no-no without critical sections then that would be nice to know too.

Hope to hear back.

Thanks

Andy

[Andreas Masur]

Well...one of the things you have to realize is that inserting or removing elements from a deque causes all iterators, references and pointers to be invalidated. The only exception to this is if elements are inserted at the front or back...in this case references and pointers are not invalidated, hoewever, iterators are. This might be a potential problem in the first place.

To ultimately decide whether a container is thread-safe is by looking at the underlying implementation. Usually you won't find much synchronization within the implementation itself though except for the rules I posted before.

In other words...you should provide synchronization objects such as a critical section. While doing a 'push_back' call...there are several places where for example the size of the container is checked...if an element would get deleted while another one is updated, the 'size()' will return different values and thus losing the data integrity of the container...

[AndyMcHugh]

[QUOTE=the data integrity of the container...[/QUOTE]

Thanks Andreas. I'm only intersted in the front and back of the deque but the size thingy is enough to break it. I'll shove in a critical section. Thanks for the help.

Andy

[Andreas Masur]

You are welcome...

[Andreas Masur]

Ohh...and to add one more thing...I was again referring to the STLport (since this is waht I have used from the beginning), thus, other implementations might implementing the 'push_back()' differently - not relying on the size several times...

Nevertheless, I would still suggest that you add synchronization for every container that is shared across multiple threads...

[TheCPUWizard]

Agreeing with Andreas on this one, better safe than sorry. Even if the CURRENT implementation *would* work, there is no guarentee that a future update might not. Then that could lead to a real subtle bug.

That being said, the one place I have found MANY containser the might seem safe to break is when they transition into/outof the empty state. I have had to fix a number of client programs that suffered this problem with both STL and MFC containers.

[marten_range]

In addition to the good advice here, if you are running under windows you might want to consider these functions:

InitializeSListHead
InterlockedPopEntrySList
InterlockedPushEntrySList

Hope this helps.

[AndyMcHugh]

Thanks. I'm actually tied to a gnu compiler on VxWorks for the target; I'm just using MSVC.NET for development. Still, all interesting stuff.

Andy