9

I have one std::list<> container and these threads:

  • One writer thread which adds elements indefinitely.

  • One reader/writer thread which reads and removes elements while available.

  • Several reader threads which access the SIZE of the container (by using the size() method)

There is a normal mutex which protects the access to the list from the first two threads. My question is, do the size reader threads need to acquire this mutex too? should I use a read/write mutex?

I'm in a windows environment using Visual C++ 6.

Update: It looks like the answer is not clear yet. To sum up the main doubt: Do I still need to protect the SIZE reader threads even if they only call size() (which returns a simple variable) taking into account that I don't need the exact value (i.e. I can assume a +/- 1 variation)? How a race condition could make my size() call return an invalid value (i.e. one totally unrelated to the good one)?

Answer: In general, the reader threads must be protected to avoid race conditions. Nevertheless, in my opinion, some of the questions stated above in the update haven't been answered yet.

Thanks in advance!

Thank you all for your answers!

David
  • 2,663
  • 3
  • 24
  • 41
  • That's imposable to answer without seeing the code. How do the reader threads traverse the list. Is it possible for the reader to have an iterator to a node that is suddenly deleted? If so trying to move to the next or prev iterator now becomes undefined. – Martin York Oct 09 '08 at 15:31
  • Well, the SIZE reader threads (which are the ones under discussion) don't traverse the list, just invoke the size() method. The other threads (writer and reader/writer) are both mutex protected. – David Oct 09 '08 at 15:35
  • 1
    Must-watch _lecture_ here: http://channel9.msdn.com/posts/C-and-Beyond-2012-Herb-Sutter-You-dont-know-blank-and-blank – sehe Jan 03 '13 at 03:52
  • Given that the writer and reader/writer threads can change the size, the reader threads need to be synchronised with them. This is necessary to prevent a reader thread being preempted by a thread that resizes the container. "Accessing a single variable" is not atomic. – Peter Jun 09 '17 at 11:44

8 Answers8

10

Yes, the read threads will need some sort of mutex control, otherwise the write will change things from under it.

A reader/writer mutex should be enough. But strictly speaking this is an implmentation-specific issue. It's possible that an implementation may have mutable members even in const objects that are read-only in your code.

Michael Burr
  • 333,147
  • 50
  • 533
  • 760
  • But the thing is if the size readers could read an invalid value... I mean, a corrupted value. – David Oct 09 '08 at 14:57
  • I think that reader/writer locks would be safe in real world use, but as far as the to-the-word standard goes I think a full mutex might be required in general. – Michael Burr Oct 09 '08 at 15:31
2

Checkout the concurrent containers provided by Intel's Open Source Threading Building Blocks library. Look under "Container Snippets" on the Code Samples page for some examples. They have concurrent / thread-safe containers for vectors, hash maps and queues.

Pat Notz
  • 208,672
  • 30
  • 90
  • 92
  • Looks great but my current project is not using that library :-( Anyway, for an open source project, that library is worth a close look. – David Oct 09 '08 at 15:21
  • It may be worth a look even for non-Open Source projects. Intel sells commercial licenses for it as well. – Michael Burr Oct 09 '08 at 17:57
1

I don't believe the STL containers are thread-safe, as there isn't a good way to handle threads cross-platform. The call to size() is simple, but it still needs to be protected.

This sounds like a great place to use read-write locks.

Herms
  • 37,540
  • 12
  • 78
  • 101
  • STL is part of the C++ implementation. That means it does not have to be portable anyway. E.g. look at the Microsoft/Dinkumware STL implementation shipping as part of VC++. It can use VC++ extensions. In fact, with TR1 it's _expected_ that the library does use compiler extensions. – MSalters Oct 10 '08 at 15:02
1

You should consider some SLT implementation might calculate the size when called.
To overcome this, you could define a new variable 

volatile unsigned int ContainerSize = 0;

Update the variable only inside already protected update calls, but you can read / test the variable without protection (taking into account you don't need the exact value).

Tal
  • 1,759
  • 1
  • 12
  • 22
0

Yes. I would suggest wrapping your STL library with a class that enforces serial access. Or find a similar class that's already been debugged.

Paul Nathan
  • 39,638
  • 28
  • 112
  • 212
0

I'm going to say no. In this case.

Without a mutex, what you might find is that the size() returns the wrong value occasionally, as items are added or removed. If this is acceptable to you, go for it.

however, if you need the accurate size of the list when the reader needs to know it, you'll have to put a critical section around every size call in addition to the one you have around the add and erase calls.

PS. VC6 size() simply returns the _Size internal member, so not having a mutex won't be a problem with your particular implementation, except that it might return 1 when a second element is being added, or vice-versa.

PPS. someone mentioned a RW lock, this is a good thing, especially if you're tempted to access the list objects later. Change your mutex to a Boost::shared_mutex would be beneficial then. However no mutex whatsoever is needed if all you're calling is size().

gbjbaanb
  • 51,617
  • 12
  • 104
  • 148
  • I don't believe it's safe to assume that variable read/writes are atomic, so you really should be protecting the calls. Read-write locks are designed for situations like this, so the overhead of adding one shouldn't be too bad. – Herms Oct 09 '08 at 15:11
  • But in my case, obtaining the wrong value occasionally is acceptable. Do I still have to protect the call?? In fact, these threads are a critical core part of my application, so avoiding extra locks is preferred. – David Oct 09 '08 at 15:17
  • 1
    I would like to see the code before we answer this question explicitly, but from the description you can't assume that would be safe. – Martin York Oct 09 '08 at 15:27
  • You do in fact still need to synchronize. There is the possibility of a race condition when the reader catches up to the writer... which could cause undefined behavior if the reader gains access to an object that hasn't been completely initialized by the writer. – oz10 Oct 09 '08 at 16:24
  • You need to read his question - in his case the answer is that he does not need to lock those other threads. Calling size() in them will not break anything, worst-case is that they will return off-by-one occasionally. – gbjbaanb Oct 09 '08 at 17:54
  • My only concern with this is that you are depending on an implementation detail that _Size is being returned. It is recommended that size be implemented in constant time (i.e. return a variable), but it isn't required. – Justin Rudd Oct 09 '08 at 23:22
  • That's right - I had forgotten that for list containers it's not required that size() be constant-time (the standard say it should be, but does not require it). Still even for containers that are required to have const time size(), it seems like a bad idea to ignore thread safety even for this. – Michael Burr Oct 09 '08 at 23:46
0

The STL in VC++ version 6 is not thread-safe, see this recent question. So it seems your question is a bit irrelevant. Even if you did everything right, you may still have problems.

Community
  • 1
  • 1
MSalters
  • 173,980
  • 10
  • 155
  • 350
0

Whether or not size() is safe (for the definition of "safe" that you provide) is implementation-dependent. Even if you are covered on your platform, for your version of your compiler at your optimization level for your version of thread library and C runtime, please do not code this way. It will come back to byte you, and it will be hell to debug. You're setting yourself up for failure.