Boost logo

Boost :

From: William Kempf (sirwillard_at_[hidden])
Date: 2000-08-09 17:31:25

--- In boost_at_[hidden], "Greg Colvin" <gcolvin_at_u...> wrote:
> What is the simplest, safest language construct we know of for
> concurrent access to data? I would say the monitor, as developed
> described by Per Hansen and Tony Hoare in the 1970s, and
implemented in
> many programming languages since then. The classic 1974 paper by
> remains one of the best introductions
> and Hansen's 1993 review is also very useful

A monitor won't always work. Monitors are usually used for internal
synchronization, which can be too fine grained for some things. All
in all, though, you're correct. The monitor is the current "best
practice". Remember, though, a monitor is nothing more than a mutex
and a condition variable working together. These are still the
principle primitives. Since they can also be used with out a monitor
concept for certain tasks I don't think it's appropriate to define
only a monitor and not the primitives the monitor is built up on.

> How to provide monitors in C++? If we were extending the language
> could follow Concurrent Pascal by adding "shared" and "await" as
> keywords. Here is how one could write Hansen's standard buffer
> with such an extension:
> shared class buffer {
> int p,c,full;
> vector buf;
> public:
> buffer(int n) : p(0),c(0),full(0),buf(n) {}
> void send (int m) {
> await (full == buf.size());
> buf[p] = m;
> p = (p+1)%buf.size();
> ++full;
> }
> int receive() {
> await (full == 0);
> int i = buf[c];
> c = (c+1)%buf.size();
> --full;
> return i;
> }
> };
> In this example two or more threads can communicate through the
> buffer with send and receive calls. When a sending thread detects
> empty buffer it blocks, releases the monitor, and awaits a non-empty
> buffer. When a receiving thread detects a full buffer it blocks,
> releases the monitor, and awaits an empty buffer.
> Since we are not extending C++, but merely writing a library, we
> an interface to do the job of the "shared" and "await" keywords.
> is the simplest monitor interface I can imagine so far:
> class shared {
> protected:
> struct entry {
> entry(monitor*);
> ~entry();
> };
> void wait();
> };
> Deriving a class from the "shared" base class does half the work of
> "shared" keyword, by associating shared data with a monitor class.
> control the scope of the monitor we need the separate entry class.
> intended discipline for the use of this class is to declare an
entry at
> the top of every accessible member function of the derived class.
> wait function can do the job of the "await" keyword by way of the
> while (!condition)
> wait();

Check out J/Threads (do a web search) for an implementation very
similar to this in C++. It models the monitor concept off of the
Java language. It's a great concept, I just don't think it's
the "only right choice". For instance, many classes will need to
protect shared resources but they'll never have a need to wait for a
condition. By tying the mutex and condition variable permanently
into a monitor construct with out the individual constructs you're no
longer as efficient as you could be in such a case. Further,
multiple conditions may be used to produce more efficient waits,
while a monitor class is confined to a single condition to wait on.
> To illustrate, here is Hansen's standard buffer example written to
> proposed interface:
> class buffer : shared {
> int p,c,full;
> vector<int> buf;
> public:
> buffer(int n) : p(0),c(0),full(0),buf(n){}
> void send (int m) {
> entry top(this);
> while (full == buf.size())
> wait();
> buf[p] = m;
> p = (p+1)%buf.size();
> ++full;
> }
> int receive() {
> entry top(this);
> while (full == 0)
> wait();
> int i = buf[c];
> c = (c+1)%buf.size();
> --full;
> return i;
> }
> };

Personally, I don't like the derivation from shared. I'd prefer
containment. Especially since shared would have no virtual functions
(other than the d-tor) in your example.

> I propose that our monitors should be recursive. That is, it is OK
> a thread to enter the same monitor more than once. For some
> thread packages this is already true, and if not it is trivial to
> a counter. In my experience recursive monitors are much easier to

That's why I prefer a recursive mutex. However, if the condition
variable were defined appropriately it could use a mutex of either
type. So the monitor could be of either type.
> I do not propose explicit queues for waiting on condition variables.
> Instead the monitor itself provides a single implicit queue. In my
> experience the use of explicit queues is a performance optimization
> best, and a source of error and confusion at worst.

The performance optimization is valid in some cases. I'm not against
a monitor concept, only against it's existance with out the existance
of the mutex and condition variable that it wraps.
> I do not propose specific notification of waiters. Rather, leaving
> scope of a monitor automatically notifies all waiters. I am aware
> this can cause a "thundering herd" performance problem, but I am
> aware that failure to notify the appropriate waiter is a common
cause of
> deadlock.

You have to be careful of starvation or race conditions with this
> I expect this proposal to be criticized for missing some "essential"
> feature. If so, such a feature can be added. Before doing so let
> be sure that it is truly essential, and that it can be implemented
> on every platform we can imagine porting to.

I don't see much for criticism here. I just think the monitor is one
of those higher level concepts that should be addressed only after
the building blocks it's based on are defined. Especially since I
don't think you can do with out the building blocks for some designs.

William Kempf

Boost list run by bdawes at, gregod at, cpdaniel at, john at