Hi Guys, Sorry for the slightly noobish question but I'm not that experienced with threading. In my engine I have a thread pool and am able to send it tasks derived from a 'Runnable' base class. I would like to have my main thread retrieve the results from these tasks, and so my idea was to have the tasks write their results into a global(ish) queue. The main thread would then retrieve results from this queue at it's convenience. This means I need a queue which I can read and write safely from multiple threads, and my plan is initially to write a class which wraps the std::queue and a mutex. My wrapper will expose the push_back(), pop(), front(),etc methods, but will make sure the mutex is obtained before calling through to the std::queue implementations. So firstly I would like to know if this is a sensible and conventional approach, or whether there is a better way of doing things (given that I'm trying to keep it relatively simple). Secondly, I would like to know for which std::queue functions I actually need to lock the mutex before calling through. For example, can I safely call size() without locking the mutex? What about front()? Obviously push() and pop() are out. More generally, where can I find this information for all the containers? Is it specified in the C++ standard? Thanks for any input.

If you never write to the queue, then all of the const functions are thread-safe.

If you do ever write to the queue at all, from any thread, then NONE of the functions are thread safe (and you'll have to acquire a lock before calling ANY member).

An alternative is to use a specially designed "lock free" queue, which is thread-safe by design (i.e. not std::queue).
OR
Carefully schedule your program into read and write sections. For example, I use std::vectors in my multi-threaded game a lot - During one "phase" of a frame, a single thread writes to a vector and no other thread reads it, then during a second "phase" (which cannot overlap with the first phase), every thread reads from the vector concurrently.

Thanks all, that's great information. For my first implementation I will simply make sure that I lock before any operation is performed on the std::queue, but longer term is seems like lock-free data structures and algorithms are the way forward. Now I know what I'm looking for I'm sure I can find some good information and implementations. Thanks again!

Quote:Original post by AntheusFor intra-thread queueing, there are better ways. For example, two queues.

queue local;while (foo) {  ..  local.push(message);}// when done with current updateother_thread.add(local);

Such approach can almost eliminate the cost of data sharing, since all operations are single-threaded, and only flips need to be synchronized, perhaps once per update/frame/tick/....

Ok, thanks, I think this is applicable to my scenario. I expect the data to take several frames to compute so it is no problem to wait until the end of a frame before syncronizing. Well, I'll give it a shot and see.

Quote:Original post by Antheus

Quote:Original post by PolyVox
Thanks all, that's great information. For my first implementation I will simply make sure that I lock before any operation is performed on the std::queue

You need to lock around each of *your* operations. Consider:

void push_message(...) {  lock(queue) {    if (queue.size() > 100) return;  }  lock(queue) {    queue.push_back(...);  }}

Atomicity is not enough, container operations might even be atomic. What you need to ensure are transactional semantics - each of the composite operations performed on container need to be a transaction.

Quote:but longer term is seems like lock-free data structures and algorithms are the way forward.

IMHO, not really.

First, they are an incredibly difficult concept to implement correctly, many data structures still don't exist in lock-free manner. Implementations that rely on spin locks might also do more harm, and finally, they solve the wrong problem.

For intra-thread queueing, there are better ways. For example, two queues.

queue local;while (foo) {  ..  local.push(message);}// when done with current updateother_thread.add(local);

Such approach can almost eliminate the cost of data sharing, since all operations are single-threaded, and only flips need to be synchronized, perhaps once per update/frame/tick/....

The other is to define data exchange in such a way that each thread can read shared state without locking and without affecting other state.

QFE!

Couldn't have said it better myself. I fully agree with all of that, and have myself used "batching" of messages to/from the global queue, which works great.