Re: STL Queue and multithreading
naveen wrote:
1. Multiple threads writting to the Q and multiple threads reading
from it. Mutex will be needed since multiple threads might be
accessing same address from the Q.
Correct.
2. Multiple threads writting to the Q and **single** thread reading
from it. Mutex will be needed since multiple threads might be
accessing same address from the Q.
Correct.
3. Single thread writting to the Q and single thread( different than
the first one) reading from it. Is the mutex needed in this case
also ? or we can live without mutex.
You can't live without a mutex. The reason is that adding or removing an
element requires several atomic changes to the internal state. When these
changes are visible and in which order is beyond your control, due to
compiler or CPU reordering and/or caching things, so some kind of
synchronisation is a must.
I would like to minimize the mutex usage
Okay, so you have already implemented this and found mutex use to be a
bottleneck, right? Now, what you can do is this:
// shared
mutex m;
event e;
queue q;
// consumer:
while(true) {
queue tmp_q;
scoped_lock l(m);
e.wait(l);
tmp_q.swap(q);
l.release();
for(; !tmp_q.empty(); tmp_q.pop_front())
handle(tmp_q.front());
}
// producer:
scoped_lock l(m);
q.push_back(X);
e.signal();
l.release();
Two things to notice there:
1. Instead of competing for the shared resource, the threads cooperate. Keep
this in mind, this is a popular thing to do wrongly when switching from a
single to multiple threads.
2. I don't lock the mutex in order to poll the content of the queue.
Instead, I wait for an event which is signalled after adding an element to
the queue. In the meantime, the consumer thread is sitting and waiting,
without any CPU use.
3. I always swap the whole queue into a local temporary, i.e. I don't just
pop one element but multiple elements if available. This again reduces the
lock/unlock overhead and the possible lock contention time. Also, of course
I don't handle the content with a lock on the queue.
BTW: There is a race condition in above code when handling and queueing
elements overlaps, but I leave that to you to figure out. ;^)
If mutex is needed in all the cases, can you suggest me some other
data structure where message can be written and read without locks or
with minimum locking
There are lock-free queue implementations that use atomic operations.
Searching the web for lock-free algorithms should turn up a few things, but
note that these are only relatively cheap, not free in terms of
performance. Unless you really have a performance problem, I'd use the easy
solution above - maybe just because I'm more familiar with it though.
Uli
--
Sator Laser GmbH
Gesch??ftsf??hrer: Thorsten F??cking, Amtsgericht Hamburg HR B62 932
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]