std::deque Thread Saftey Situtation

On Aug 29, 9:35 pm, NvrBst <nvr...@gmail.c omwrote:

Ahh thank you. I find examples a lot easier to follow, one question:

some_struct_typ e myStruct;
while(q.size() 0) {
{
WrapMutex(m_Q[TCPIP].qLock);
myStruct = q.front();
q.pop_front();
}
ProcessData(myS truct);

}

This would imply the ".size()" doesn't have to be wrapped in the
CriticalSection s?

Yes, but I got that wrong. In general, it should be in the critical
section.

To be truly safe without locking up the deque for the entire loop, the
loop would have to be reorganized so that the q.size() call was within
the critical section.

The reasion I put the locks/unlocks outside the
whileloop was solely for that reasion.

Ok. That is not exception-safe by itself, although you did mention
using try-catch blocks to counter that. The wrapper class approach
shouldn't need the try-catch blocks to be exception-safe.

...

I was thinking ".front()" should also be thread safe for the same (C#-
Based) reasion, since it's a 32bit applications, and .front() should
be returning a pointer to the first element. Since the thread

I'm not familiar with C#, so I don't know when C# pointers analogize
to either C++ raw pointers, or C++ references. It makes a huge
difference here.

front() and back() return C++ references. begin() and end() return
iterators (which usually have the same behavior as pointers).
Iterators are designed so that a pointer is an iterator for a C-style
array.

calling .front() is the only thread who's removing elements, and since
this thread knows that ".size()" shows one element, then I would of
assumed ".front()" would be thread-safe as well.

It's important that this is the only thread removing elements. As
long as std::deque is implemented correctly, insertions by other
threads to the front or back will only invalidate all iterators;
references will be fine. That is: *q.begin() is not safe, q.front()
would mostly be safe. [Insertions to the middle will invalidate
references.] However, the loop does assume that no other threads are
inserting to the front.

Since .size() was a method call instead of a property, I was thinking
there might be more to it in c++... Which I'm not confused on again:

True. There's more to size() than to empty(), as well.

".size()" ".front()" would both be thread-safe operations for a thread
thats removes elements (being the only thread that removes items)?

q.empty() would come pretty close to being thread-safe (and might well
be for a good implementation on a sufficiently friendly CPU). The
other member functions are likely to be thrown off by temporarily
inconsistent internal state.

As long as all insertions are to the end, it is possible that a good
implementation would have a coincidentally thread-safe q.front().
Insertions to the middle will invalidate this.

The reference from q.front() should be thread-safe regardless, given
that this thread is the only thread removing items. But q.pop_front()
will invalidate the reference, so the assignment is needed.

So in essance I can change it to the following if I wanted to fine
tune the thread-safty locking to it's bare minimium in my example (and
remove my try statment to boot, yay)?

The try-catch statements can be outright gone, yes.

some_struct_typ e myStruct;
while(q.size() 0) {
myStruct = q.front();
{
WrapMutex(m_Q[TCPIP].qLock);
q.pop_front();
}
ProcessData(myS truct); }

A fortunate implementation would let us get away with:

some_struct_typ e myStruct;
while(!q.empty( )) {
myStruct = q.front();
{
WrapMutex(m_Q[TCPIP].qLock);
q.pop_front();
}
ProcessData(myS truct); }

The loop that would be maximally portable would be like:

some_struct_typ e myStruct;
bool in_loop = false; /* redundant */
do{
in_loop = false;
{
WrapMutex my_lock(m_Q[TCPIP].qLock);
if (!q.empty())
{
myStruct = q.front();
q.pop_front();
in_loop = true;
};
}
if (in_loop) ProcessData(myS truct);
}
while(in_loop);

NvrBst <nv****@gmail.c omkirjutas:

>A low level mutex is a very fast beast unless you have heavy
contention. If your data is expensive to copy, that might be a
bottleneck, but wait dealing with that until you have gotten your
basic structure to work.

/Peter

The information is too much to copy. When I said clean, I ment more-

There is no need to copy. You should write a swap() member function for
swapping the contents of an item in the queue with a local data item. The
swap() method can be usually implemented fast and exception-safe;
std::string and all STL containers already have it.

Fetching the item from the queue would then be something like that (using
boost::thread library, this helps to get one's mutex/locks/conditions
semantics right):

std::deque<Item queue;
boost::mutex queue_mutex;
boost::conditio n queue_condition ;

....

Item local;
{
boost::mutex::s coped_lock lock(queue_mute x);
while(queue.emp ty()) {
// wait until an item arrives
// other behaviors can be imagined here as well
queue_condition .wait(lock);
}
queue.front().s wap(local);
queue.pop_front ();
}
// ... process local to your heart's content, with no mutex locked.

Pushing:

Item tobepushed;
....
{
boost::mutex::s coped_lock lock(queue_mute x);
queue.push_back (Item());
queue.back().sw ap(tobepushed);
queue_condition .notify_all();
}
And of course, you should pack the queue in a nice class or template,
possibly with a template policy for different waiting strategies. I
wonder whether boost already doesn't have such a queue, seems to be a
quite generic thing to me...

hth
Paavo

On Aug 30, 12:55 am, Paavo Helde <nob...@ebi.eew rote:

NvrBst <nvr...@gmail.c omkirjutas:

The information is too much to copy. When I said clean, I ment more-

There is no need to copy. You should write a swap() member function for
swapping the contents of an item in the queue with a local data item.

It depends. If the data is Plain Old Data, this becomes questionable
(and this seems plausible considering we're talking about a struct);
why incur three assignments in place of one?

If there's dynamic memory allocation involved in the assignment
operator, then swap should be implemented regardless, and used
liberally.

....

Fetching the item from the queue would then be something like that (using
boost::thread library, this helps to get one's mutex/locks/conditions
semantics right):

True, but given already-developed code the immediate need to port
becomes questionable. Boost.Thread does have the advantage that it
was rewritten for 1.36.0 to more closely track the C++0x proposals.

....

And of course, you should pack the queue in a nice class or template,
possibly with a template policy for different waiting strategies. I
wonder whether boost already doesn't have such a queue, seems to be a
quite generic thing to me...

Waiting policies (and the initial wait for a non-empty queue) is being
handled by signals currently. I'm not clear on whether there's enough
flexibility to rewrite using Boost.Signals. (Both Boost.Thread and
Boost.Signals are not header-only;

It would be surprising if Boost libraries directly replicated STL
functionality. I don't see any directly relevant data structures in
Boost 1.36.0, possibly because std::queue<T(wh ose default container
is std::deque<T>) fits quite nicely. (The time to notice this was at
the design stage; converting the code now may not be worth it.)

za*****@zaimoni .com kirjutas:

On Aug 30, 12:55 am, Paavo Helde <nob...@ebi.eew rote:

>NvrBst <nvr...@gmail.c omkirjutas:

The information is too much to copy. When I said clean, I ment
more-

There is no need to copy. You should write a swap() member function
for swapping the contents of an item in the queue with a local data
item.

It depends. If the data is Plain Old Data, this becomes questionable
(and this seems plausible considering we're talking about a struct);
why incur three assignments in place of one?

One can use copy of course instead of swap when applicable. I just
answered to OP-s claim "The information is too much to copy.".

>(using boost::thread library, this helps to get one's
mutex/locks/conditions semantics right):

True, but given already-developed code the immediate need to port
becomes questionable.

I did not suggest porting, though after seeing mention of critical
sections and lock.Leave() calls in the OP-s posts I actually feel quite
confident that rewriting the system in boost::thread would take less time
and effort than getting the already-developed code correct. I just used
boost::thread in the example because that is what I know best.

Thanks for the boost development info! We are still using 1.34 as we are
in a project stabilization phase and avoiding upgrades during that time.

regards
Paavo

On 30 Aug., 04:35, NvrBst <nvr...@gmail.c omwrote:

Ahh thank you. *I find examples a lot easier to follow, one question:

some_struct_typ e myStruct;
while(q.size() 0) {
* {
* WrapMutex(m_Q[TCPIP].qLock);
* myStruct = q.front();
* q.pop_front();
* }
* ProcessData(myS truct);

}

This would imply the ".size()" doesn't have to be wrapped in the
CriticalSection s? *

Yes - that is an error with the code: it should be wrapped.

[snip]

Most my confusion comes from my C# background (java, and then C# is
what I grew up with), and in C#'s Queue, the size property is stored
as an Int32 which, when reading, is an atomic operation on mostly all
processors. *Meaning it even read it before another thread changes it,
or after; either case is fine (thread safe) if there are only two
threads, and each thread either pop's or push's, thus can't cause an
exception. *This is because in C# the size doesn't get incremented
untill after the insertion is completed, so exceptions can't occure in
my situation.

This is not correct, and your C# code will not work unless there is
more action involved when reading the Int32 size. The reason is that
even though the size gets written after the data, it might not be seen
this way by another thread. Memory writes undergo a lot of steps
involving caches of different kinds, and the cacheline with the size
might be written to memory before the cache-line containing the data.

>
I was thinking ".front()" should also be thread safe for the same (C#-
Based) reasion, since it's a 32bit applications, and .front() should
be returning a pointer to the first element. *Since the thread
calling .front() is the only thread who's removing elements, and since
this thread knows that ".size()" shows one element, then I would of
assumed ".front()" would be thread-safe as well.

You have the same problem here.

[snip]

/Peter

In article <0bbce4f3-4ab7-47fd-8be1-
7d**********@n3 8g2000prl.googl egroups.com>, nv****@gmail.co m says...

I've read a bit online seeing that two writes are not safe, which I
understand, but would 1 thread push()'ing and 1 thread pop()'ing be
thread-safe? Basically my situation is the follows:

Generally speaking, no, it's not safe.

My advice would be to avoid std::deque in such a situation -- in a
multi-threaded situation, it places an undue burden on the client code.
This is a case where it's quite reasonable to incorporate the locking
into the data structure itself to simplify the client code (a lot).

For one example, I've used code like this under Windows for quite a
while:

template<class T, unsigned max = 256>
class queue {
HANDLE space_avail; // signaled =at least one slot empty
HANDLE data_avail; // signaled =at least one slot full
CRITICAL_SECTIO N mutex; // protect buffer, in_pos, out_pos

T buffer[max];
long in_pos, out_pos;
public:
queue() : in_pos(0), out_pos(0) {
space_avail = CreateSemaphore (NULL, max, max, NULL);
data_avail = CreateSemaphore (NULL, 0, max, NULL);
InitializeCriti calSection(&mut ex);
}

void push(T data) {
WaitForSingleOb ject(space_avai l, INFINITE);
EnterCriticalSe ction(&mutex);
buffer[in_pos] = data;
in_pos = (in_pos + 1) % max;
LeaveCriticalSe ction(&mutex);
ReleaseSemaphor e(data_avail, 1, NULL);
}

T pop() {
WaitForSingleOb ject(data_avail ,INFINITE);
EnterCriticalSe ction(&mutex);
T retval = buffer[out_pos];
out_pos = (out_pos + 1) % max;
LeaveCriticalSe ction(&mutex);
ReleaseSemaphor e(space_avail, 1, NULL);
return retval;
}

~queue() {
CloseHandle(spa ce_avail);
CloseHandle(dat a_avail);
DeleteCriticalS ection(&mutex);
}
};

Exception safety depends on assignment of T being nothrow, but (IIRC)
not much else is needed. This uses value semantics, so if you're dealing
with something where copying is expensive, you're expected to use some
sort of smart pointer to avoid copying. Of course, a reference counted
smart pointer will usually have some locking of its own on incrementing
and decrementing the reference count, but that's a separate issue.

Contrary to the statements elsethread, I've seen little use for being
able to parameterize how the waits happen and such. While there might be
situations where it could be useful, I haven't encountered a need in
real life.

Likewise, there's optimization that could be done -- for an obvious
example, the current design switches to kernel mode twice for every push
or pop, which isn't exactly fast. In real use, however, I haven't see
this take enough processor time to bother optimizing it.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Thank you all for your information :) I think I have what I need now.

This is not correct, and your C# code will not work unless there is
more action involved when reading the Int32 size. The reason is that
even though the size gets written after the data, it might not be seen
this way by another thread. Memory writes undergo a lot of steps
involving caches of different kinds, and the cacheline with the size
might be written to memory before the cache-line containing the data.

Only if there were, say, two threads poping. In my case I only have 1
thread poping, and 1 thread pushing. Even if the poping thread reads
0 elements (because say the size cache wasn't updated in time, but
there is really 1 element), that is safe, it'll ignore untill size
says 1 element. If it reads 1+ element then there is definally 1
element to remove (since no other thread is removing items). Same
logic works for reading when there is a max size you can't go over.

Thanks again for all the information, and enjoy the weekend ;)

Paavo Helde schrieb:
[...]

Item local;
{
boost::mutex::s coped_lock lock(queue_mute x);
while(queue.emp ty()) {
// wait until an item arrives
// other behaviors can be imagined here as well
queue_condition .wait(lock);
}
queue.front().s wap(local);
queue.pop_front ();
}
// ... process local to your heart's content, with no mutex locked.

Doing the wait on the condition variable while holding the lock is a bad
idea, but you'll recognize that error very early when your application
dead locks.

--
Thomas

I myself wrote:

Paavo Helde schrieb:
[...]

>Item local;
{
boost::mutex::s coped_lock lock(queue_mute x);
while(queue.emp ty()) {
// wait until an item arrives
// other behaviors can be imagined here as well
queue_condition .wait(lock);
}
queue.front().s wap(local);
queue.pop_front ();
}
// ... process local to your heart's content, with no mutex locked.

Doing the wait on the condition variable while holding the lock is a bad
idea, but you'll recognize that error very early when your application
dead locks.

Sorry, the code is correct. condition::wait will unlock the mutex while
waiting on the condition variable.

I should have checked the boost.thread documentation earlier.

--
Thomas

"Thomas J. Gritzan" <ph************ *@gmx.dekirjuta s:

I myself wrote:

>Paavo Helde schrieb:
[...]

>>Item local;
{
boost::mutex::s coped_lock lock(queue_mute x);
while(queue.emp ty()) {
// wait until an item arrives
// other behaviors can be imagined here as well
queue_condition .wait(lock);
}
queue.front().s wap(local);
queue.pop_front ();
}
// ... process local to your heart's content, with no mutex locked.

Doing the wait on the condition variable while holding the lock is a
bad idea, but you'll recognize that error very early when your
application dead locks.

Sorry, the code is correct. condition::wait will unlock the mutex
while waiting on the condition variable.

Yes, that's one thing I like about boost::thread library that it makes
some kind of errors impossible (like forgetting to unlock the mutex
before wait, or forgetting to relock it after the wait).

regards
Paavo