Beginner question regarding threads

[Doug Mika]

Let me first illustrate the simple problem:

If I have a stack data structure accessed by two threads and the following code that runs on both threads:

if(!stack.empty()){
..
stack.pop();
..
}

then I may encounter a problem if thread A executes pop() after thread B passes the if statement. That is, there is a chance that if I have one element on my stack, that both threads may execute pop() on it.

The simple solution that comes to my mind is to wrap this entire block of code:

if(!stack.empty()){
..
stack.pop();
..
}

in a mutex to ensure that only one thread executes it at a time. Is there another neat/quick way to achieve what I'm trying to do?

[Victor Bazarov]

What do the dots designate in your example? Some other processing?
Does it only happen if the stack is not empty? If you make this
processing exclusive (with a mutex or critical section or a semaphore),
in other words if you make it synchronous, will it be a performance
bottleneck? If not, it's probably OK to lock the whole thing.

What book are you reading on threads? What do they say about such
situations?

BTW, have you found 'comp.programming.threads' newsgroup yet?

V
--
I do not respond to top-posted replies, please don't ask

[Ian Collins]

Please wrap your lines!

Use a condition variable with !stack.empty() as the condition.

--
Ian Collins

[Christopher Pisz]

If I have some data structure that I am going to share between thread, I
prefer to make my own class, write the same interface, make the original
data structure a private member, and then have the class I wrote control
the data and the mutex.

Incomplete example:

template <T> class ConcurrentStack
{
public:
void push(const T & value)
{
m_mutex.lock();
m_stack.push(value);
m_mutex.unlock();
}

T pop()
{
m_mutex.lock();
T value(m_stack.pop());
m_mutex.unlock();

return value;
}

private:
std::stack<T> m_stack;
std::mutex m_mutex;
};

basic idea...I'm sure you can make it more efficient and take care of
the nuances from there.

I keep a concurrent library in my common code for such things. I like my
container to own its own mutex rather than someone else and especially
rather than a whole bunch of people trying to lock and unlock it. This
way, no one need worry about the fact that there is a mutex, threads
must simply be aware that they have to wait via the documentation.


--
I have chosen to troll filter/ignore all subthreads containing the
words: "Rick C. Hodgins", "Flibble", and "Islam"
So, I won't be able to see or respond to any such messages
---

[Doug Mika]

I'm reading C++ Concurrency in Action: Practical Multithreading by Anthony Williams. Any other you would suggest?

[Doug Mika]

I guess what I wanted to ask is is there a structure/way in C++ to "bundle" commands into "one" command ensuring that once I start executing the first command that no thread will interrupt until I execute the last command in the bundle?

ie.
/*beginning of bundle*/
if(!stack.empty()){
/*some code*/
stack.pop();
}
/*end of bundle*/

out of the collection of commands I wanted to create "one command" that is guaranteed to be executed without interruptions by ANY other thread?

[Scott Lurndal]

The "proper" way would be for the stack object
to provide thread-safe methods. That means the
stack object needs to handle concurrent access
to the stack internally, using whatever synchronization
mechanism makes sense for the application.

The simplest is to use a mutex (e.g. pthread_mutex std::mutex) within
the ::push, ::pop and ::emtpy methods to protect access
to the underlying data structure used to represent a
stack of objects.

It's not a good idea to do the synchronization outside of
the stack object.

e.g.:

void
Stack::push(T& obj)
{
std:lock_guard<std::mutex> lock(_mutex); // _mutex is private class member std::mutex
<push item on stack>
}

void
Stack::pop(T& obj)
{
std::lock_guard<std::Mutex> lock(_mutex);
<pop item from stack>
}

[Victor Bazarov]

It's a good book, I've no doubt.

I started learning multithreading while doing it in Java, and for that I
bought "Java Thread Programming" by Paul Hyde (I picked it up in a local
bookstore at the time after browsing for a few minutes). There are
better books out there, probably. There is no single true source of
knowledge, as you are certainly already aware.

Right now on my shelf I have also "Patterns for Parallel Programming",
"Parallel Programming with Microsoft Visual C++", "The Art of
Multiprocessor Programming", "Intel Thread Building Blocks" (probably
already obsolete), and "Software Optimization for High Performance
Computing" (from HP Professional Books series). Sadly, I don't get to
open them for what I am doing nowadays...

[Victor Bazarov]

On 7/31/2015 2:37 PM, Doug Mika wrote:
> On Thursday, July 30, 2015 at 4:59:49 PM UTC-5, Doug Mika wrote:

>> [...]

> I guess what I wanted to ask is is there a structure/way in C++ to
"bundle" commands into "one" command ensuring that once I start
executing the first command that no thread will interrupt until I
execute the last command in the bundle?
>
> ie.
> /*beginning of bundle*/
> if(!stack.empty()){
> /*some code*/
> stack.pop();
> }
> /*end of bundle*/
>
> out of the collection of commands I wanted to create "one command"
> that is guaranteed to be executed without interruptions by ANY other
> thread?

See "Critical Section".

[Victor Bazarov]

This is not enough. If the stack reports that it's not empty, then the
code that learned that the stack is not empty starts doing something
hoping that the stack remains non-empty, and another thread pops the
last element from the stack, it can easily interfere with the code that
presumes the stack non-empty until it's time to pop.

This is what critical sections are for, IMHO. It's not the best
solution, of course. A better solution would be to refactor the code so
that it doesn't need to keep others from accessing the stack. That's
why I asked Doug about the contents of his ".." in the original post,
but got no answer.

[Christopher Pisz]

I remember running into that. I think we added a lock and unlock to the
interface on top of what was there for such scenarios and would rely on
the internal locks for most things, but lock it externally for things
that would depend on empty or size for logic involving other stack
operations.

[Scott Lurndal]

That's a different mutex. The stack mutex protects the stack.

A higher level mutex protects the algorithm that uses the stack.

[Doug Mika]

On Thursday, July 30, 2015 at 4:59:49 PM UTC-5, Doug Mika wrote:

.. was to be ANY code you could think of that made sense.

[Luca Risolia]

Il 31/07/2015 20:37, Doug Mika ha scritto:
> I guess what I wanted to ask is is there a structure/way in C++ to
"bundle" commands into "one" command ensuring that once I start
executing the first command that no thread will interrupt until I
execute the last command in the bundle?
>
> ie.
> /*beginning of bundle*/
> if(!stack.empty()){
> /*some code*/
> stack.pop();
> }
> /*end of bundle*/

Use a monitor:

template<class T>
class monitor {
private:
mutable T t;
mutable std::mutex m;
public:
monitor(T t_ = T{}) : t{t_} {}
template<class F>
decltype(auto) operator()(F f) const {
std::lock_guard<std::mutex> _{m};
return f(t);
}
};

// For example:
monitor<std::stack<int>> sync_stack;
sync_stack([](auto& s) {
if (!s.empty()){
/*some code*/
s.pop();
}
});

[Richard Damon]

On 7/31/15 2:37 PM, Doug Mika wrote:
>
>
> I guess what I wanted to ask is is there a structure/way in C++ to
> "bundle" commands into "one" command ensuring that once I start
> executing the first command that no thread will interrupt until I
> execute the last command in the bundle?
>
> ie.
> /*beginning of bundle*/
> if(!stack.empty()){
> /*some code*/
> stack.pop();
> }
> /*end of bundle*/
>
> out of the collection of commands I wanted to create "one command"
> that is guaranteed to be executed without interruptions by ANY other thread?
>

Since the model used in C++ includes support for multi-core processors
(supporting memory barriers in addition to access ordering), the other
thread could access the stack without "interrupting" the current thread.

Thus, the only way to achieve what you are asking for would not only
need to prevent a "context swap", but also suspend ALL other processor
cores.

The real solution is to write the program properly, and properly wrap
the accesses to stack with an appropriate synchronizing operations for
ALL accesses.

[Chris Vine]

On Fri, 31 Jul 2015 15:17:10 -0400
Victor Bazarov <v.ba...@comcast.invalid> wrote:
> On 7/31/2015 2:55 PM, Scott Lurndal wrote:

[snip]

It is enough in the sense that it provides an alternative to the OP's
incorrect use of empty(), which is a design error if concurrent access
to the stack object is to be provided.

Here the pop() method takes a non-const reference argument, presumably
as an out parameter, which means that no separate empty() or front()
methods are either needed or desirable. In this approach, pop() either
extracts the item at the top of the stack (if any) as a value and
assigns it to obj, or throws an exception, and it does so in a way which
is thread safe and (if the assignment to the obj argument is done
correctly) also strongly exception safe.

As a minor quibble, the push method should have taken a const lvalue
reference argument or rvalue reference argument, and not a non-const
lvalue reference argument.

Chris