Hi all,

I have a (possibly) very naive question:

Most of the software that we write consist of an architecture where
multiple tasks/threads wait/block at a MsgQ (or Mailbox) until the next
message arrives.

The messages can only be commands (GOF command). A command can be
associated with a "CommandServer", in which case it executes in the
context (thread) of the CommandServer (the context in which the MsgQ
associated with that server is serviced). MsgQ's are of course Thread
Safe devices, and when implemented (if not provided by the API), they
consist of a normal queue. Access to queue are protected by mutual
exclusion), and notification to unblock the recipient are performed by
Counting Semaphore. Posting over queues are always non-blocking, and
exceptions happen in the event of queues being full at the time of
posting (queues obviously have size associated with them, similar to
stacks). Commands in our implementation always get cloned, and whether
arguments are copied or transferred (and whether they are allocated on
stack or heap) depends on their size.

The nice thing of this architecture, is that this typically provides
one with the ability to do ones OOD and Concurrency (or Threading)
design orthogonally. Whether or not a call (or msg) is asynchronous,
depends on whether a command is associated with a server. We have
extended the command pattern to handle a number of arguments, and used
mechanisms to ensure that references to one stack is not mistakedly
accessed on other stacks (quite simple, really). We have used this
architecture for a couple of years now, and because of its simplicity
have not considered using, say for instance, something like what
boost::threads provide.

One of the caveats of this architecture, is that the references in a
command waiting to be processed may become invalid. This could be
easily solved by using concepts similar to weak pointers instead of
bald pointers (typically making either mechanisms optional). Of course,
something like GC would be ideal, but the command's association with
the recipient should not prolong the lifetime of the recipient, but
should only prevent the command from executing in the event of the
recipient seizing to exist). We have implemented this scheme on a
number of platforms (I suppose our current implementation can be
heavily scrutinized, but I think the concept is sound).

I must emphasize that this architecture lives within the boundaries of
one process/application, and is only used for intertask/thread
communication.

My questions are:

- Have some of you implemented similar schemes/architectures?
- Could a scheme like this be considered as a viable candidate for
intertask/thread communication in C++. Of course, the notion of
task/thread currently does not even exist in C++.

- The idea is then (to summarize), to create a high level callable
entity in C++ that is associated with a context (or not).
- To have the notion of Context, where context represents what is
currently known as "Thread of execution", each Context just consisting
of code to execute callable entities when they arrive.

Obviously, sometimes traditional Mutual Exclusion is still required,
but we have found this to be minimal when not using the message queues,
and failsafe (and abstracted) when using the message queues.

The constructs that we needed to realize this were...

- Mutexes.
- Counting Semaphores.

.... if the platform did not support the notion of message queues (very
similar to the notion of POSIX mq_, with which I'm sure some of you
might be familiar). These constructs are constructs that need to be
realised in C++ anyway, right?

Your comments would be appreciated,

Kind regards,

Werner


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

werasm wrote:

> I have a (possibly) very naive question:

Good question IMO.

> Most of the software that we write consist of an architecture where
> multiple tasks/threads wait/block at a MsgQ (or Mailbox) until the next
> message arrives.
>
> The messages can only be commands (GOF command). A command can be
> associated with a "CommandServer", in which case it executes in the
> context (thread) of the CommandServer (the context in which the MsgQ
> associated with that server is serviced).

Why not have multiple mq's then? In which case you wouldn't need to
stuff the command with a reference to the command server (a worker
thread, I guess?) and mitigate possible contention between command
servers extracting commands from the same queue.

> MsgQ's are of course Thread
> Safe devices, and when implemented (if not provided by the API), they
> consist of a normal queue. Access to queue are protected by mutual
> exclusion), and notification to unblock the recipient are performed by
> Counting Semaphore.

If your queue data structure probably provides something like
std::queue<>::empty() you may not care about losing notifications when
a new command added to the queue while no command server is waiting for
the notification; one would just check if the queue is empty before
blocking to wait for a notification. I wonder why you need a counting
semaphore, rather than a mutex + condition.

> Posting over queues are always non-blocking, and
> exceptions happen in the event of queues being full at the time of
> posting (queues obviously have size associated with them, similar to
> stacks).

Allocating memory may block a thread. Does it mean that you are
allocating from a preallocated pool?

> Commands in our implementation always get cloned, and whether
> arguments are copied or transferred (and whether they are allocated on
> stack or heap) depends on their size.

That is very interesting. How do you know if a pointer or a reference
argument refers to a heap or a stack allocated object? The size of the
object being pointed to can not tell you that, can it?

> The nice thing of this architecture, is that this typically provides
> one with the ability to do ones OOD and Concurrency (or Threading)
> design orthogonally. Whether or not a call (or msg) is asynchronous,
> depends on whether a command is associated with a server.

Are not commands always executed asyncronously by some other thread
than the one that created a command?

> We have
> extended the command pattern to handle a number of arguments, and used
> mechanisms to ensure that references to one stack is not mistakedly
> accessed on other stacks (quite simple, really)

I'd like to take a look at the solution. So far, I could not find means
of doing so, other than to walk through a list of all threads stack
ranges.

> We have used this
> architecture for a couple of years now, and because of its simplicity
> have not considered using, say for instance, something like what
> boost::threads provide.
>
> One of the caveats of this architecture, is that the references in a
> command waiting to be processed may become invalid. This could be
> easily solved by using concepts similar to weak pointers instead of
> bald pointers (typically making either mechanisms optional). Of course,
> something like GC would be ideal, but the command's association with
> the recipient should not prolong the lifetime of the recipient, but
> should only prevent the command from executing in the event of the
> recipient seizing to exist). We have implemented this scheme on a
> number of platforms (I suppose our current implementation can be
> heavily scrutinized, but I think the concept is sound).
>
> I must emphasize that this architecture lives within the boundaries of
> one process/application, and is only used for intertask/thread
> communication.
>
> My questions are:
>
> - Have some of you implemented similar schemes/architectures?

Many has in-house implementations of something like that.

> - Could a scheme like this be considered as a viable candidate for
> intertask/thread communication in C++. Of course, the notion of
> task/thread currently does not even exist in C++.
>
> - The idea is then (to summarize), to create a high level callable
> entity in C++ that is associated with a context (or not).
> - To have the notion of Context, where context represents what is
> currently known as "Thread of execution", each Context just consisting
> of code to execute callable entities when they arrive.

There are quite a big number of choices and implementation strategies,
I don't think there would be one thing that provides the level of
abstraction and overhead good enough for everyone.

For example, the fact, that the queue holds a weak, not string
reference to the command, is more of a policy rather than of a
mechanism. Queues can be implemented using containers + synchronization
primitives or using platform mechanism like local datagram sockets.

I believe we have everything in c++ now required to build a custom
infrastructure of this kind quite easily. For example, the one you
described, could be implemented using boost::thread for threading, std
containers, boost::function + boost::bind for commands, boost smart
pointers to implement a specific command lifetime policy.


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

werasm wrote:
> Hi all,

Hi.
[snipped]
>
> - Have some of you implemented similar schemes/architectures?

Yes, though in my model, the client does not necessarily reside on same
server.

> - Could a scheme like this be considered as a viable candidate for
> intertask/thread communication in C++. Of course, the notion of
> task/thread currently does not even exist in C++.

IMO, communicating between two threads in the same process by stuffing
a mutex-protected-plus-semaphore queue is so straigthforward, any
standardization of it is more likely to result in an impediment than a
benefit.  The fundamental question always centers around primitives:

1.  How good are your primitives?
2.  With what facility can you synthesize the system you need from
those primitives?

Let's see, I already have in my arsenal, as probably do others:

1.  Queue<>
2.  Shared<> (mutex wrapper)
3.  Counted<> (semaphore wrapper)
4.  Thread::Object (many don't have this)

I can use (4) to create as many threads as I want.  The data structure
containing struct Command { }'s would be


Shared<Counted<Queue<Command> > > commands;;

commands.acquire();
commands.push(Command());
commands.release();


> - The idea is then (to summarize), to create a high level callable
> entity in C++ that is associated with a context (or not).
> - To have the notion of Context, where context represents what is
> currently known as "Thread of execution", each Context just consisting
> of code to execute callable entities when they arrive.

Are these real threads or not?
>
> Obviously, sometimes traditional Mutual Exclusion is still required,
> but we have found this to be minimal when not using the message queues,
> and failsafe (and abstracted) when using the message queues.

Also, you mentioned tha blocking does not happen on insertion of
commands into your queue.
I'd be wary of this. :)

Best,

-Le Chaud Lapin-


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Hello Werner,

On Tue, 17 Oct 2006 14:35:13 -0400, werasm wrote:

> Most of the software that we write consist of an architecture where
> multiple tasks/threads wait/block at a MsgQ (or Mailbox) until the next
> message arrives.

This sounds like You are redeveloping Hoare's Channels which are part of
Communicating Sequential Processes (CSP). To get an idea what CSP is all
about I recommend to take a peek at Peter Welch's JCSP tutorial
presentation [0]. Which was in fact was an eye opener for me to understand
when I was in a similar situation as You some time ago.

Coming to Your questions:
> - Have some of you implemented similar schemes/architectures?

Yes others and myself have developed CSP implementations over the
past few years for C, C++, Objective-C and Java. And we are still
developing our implementations further, to obtain a complete
programming language implementation of CSP. You may want to take a look at
Neil's C++CSP [1] and at the WOTUG homepage [2] giving You some background
information regarding CSP.

> - Could a scheme like this be considered as a viable candidate for
> intertask/thread communication in C++. Of course, the notion of
> task/thread currently does not even exist in C++.

Probably, but whatever synchronisation primitives You offer make sure that
they work as expected and don't include nasty surprises like the occasional
deadlock or livelock. Furthermore, I would recommend that users can ensure
that their use of the synchronisation primitives is _correct_. This is for
instance possible when using CSP models using dedicated model checkers
such as FDR [3].

Cheers
Bernhard

[0] http://www.cs.ukc.ac.uk/projects/ofa/jcsp/components.pdf
This presentation centres on JCSP a Java implementation of CSP but the
presented CSP principles ideas are the same under any programming
language. There are more presentations by the same author at:
http://www.cs.kent.ac.uk/projects/ofa/jcsp/

[1] http://cppcsp.net/
[2] http://www.wotug.org
[3] http://www.fsel.com/fdr2_download.html


-- 
William of Ockham, Albert Einstein, and Stephen Hawking walk into a bar.
Bartender: Oh, NO! Not another bloody parallel programming joke.

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Maxim Yegorushkin wrote:

> Why not have multiple mq's then? In which case you wouldn't need to
> stuff the command with a reference to the command server (a worker
> thread, I guess?) and mitigate possible contention between command
> servers extracting commands from the same queue.

We do have multiple message queues. Each "worker thread" (as you call
it), consist of a function that extracts the next message from a queue.
Only one CommandServer can post to that queue. I have seperated the
responsibility of servicing the queue (CmdMngr) and processing commands
(CmdSvr). (Very) Basically things look as follow:

class ExecutableCmd
{
  public:
    //...omitting detail...
    virtual void execute() = 0;
};

class ProcessableCmd : private ExecutableCmd
{
  public:
    //...omitting detail...
    virtual ProcessableCmd* processClone() = 0;
};

class Cmd : private ProcessableCmd
{
  public:
    const Cmd& operator()()
    {
      if( svr_ ) { svr_->process(*this); }
      else{ execute(); }
    }

  private:
    CmdSvr* svr_; //Could be weak_ptr...
};

Cmd is basically the baseclass that holds the logic wrt. processing of
itself. It is a little more complicated, but basically boils down to
above.

Priority (below), when critical typically allows a command to be
inserted in front. We don't use it often though.

class CmdSvr
{
  public:
    void process( ProcessableCmd& cmd, int timeout = 0,
      eCmdPriority prior = eCmdPriority_NORMAL ) throw();

  private:
    virtual void processImpl( ... ) = 0;
};

The CmdSvr typically has a few more responsibilities not apparent here,
such as the ability to disable and enable posting etc, which we have
found a handy feature during debugging of multithreading apps.

Then (lower down in the hierarchy) we have a class responsible for
owning context, and executing commands in that context:

class CmdMngr : public CmdSvr
{
  protected:
    void serviceCmdQueue() throw();
};

serviceCmdQueue is a template method that prescribes the process of
executing commands as they are retrieve from the command queue. For our
implementation, all derivatives call this from within their task entry
point... typically:

while( 1 ){ serviceCmdQueue(); }

only slightly more elaborate, handling things such as flushing of the
queues etc., and activation by means of binary semaphore.

It must be noted that only commands can be sent over queues, and that
the entire application really exist of parallel threads (or workers),
each responsible for processing commands received on the queue that it
owns only. Each CmdMngr is responsible for handling exceptions raised
by the code that it executes (It is associated with an interface that
propogates exceptions - exceptions deriving from std::exception don't
propagate above this layer.

> If your queue data structure probably provides something like
> std::queue<>::empty() you may not care about losing notifications when
> a new command added to the queue while no command server is waiting for
> the notification;

A command server has parts executed in the contexts of the actual call,
and a part executed in the context of the thread that it represents.
The part executed in the context of the actual call is always
non-blocking. We have provided interface for the ability to block, but
we have found that this is never necessary (i.e. timeout currently
always zero). If the queue is full, and the time specified (zero...) is
not met, then an exception is raised (if preferred), else the command
state indicates the failure. A command cannot be processed before
current failure state is not cleared. The part executing in the context
of the task/thread associated with the server, blocks at the queue
until a next command arrives to execute. It always blocks, therefore a
command server (Actually, CmdMngr, which is-a server) is always waiting
for the next command (except while processing the current one), and
cannot miss it if it was put on the queue.

>I wonder why you need a counting
> semaphore, rather than a mutex + condition.

I suppose a counting sem was an overkill - you are right.
Maybe/probably even slows things down. The queue does have that
knowledge (to know that it is empty). I could toy with implementing my
Windows Mailbox by only using a binary sema (or an event) as signal.
Currently I use critical sections to perform mutual exclusion.

> Allocating memory may block a thread. Does it mean that you are
> allocating from a preallocated pool?

Yes, it does :-). In this environment, there are unfortunately 2 more
decisions that you have to make:

1. How much are you willing to queue. I only queue cloned pointers,
btw, which makes things quite efficient.
2. How much you are willing to queue, and the sizes of your commands
and their arguments are an indication of how much memory you need to
pre-allocate, sadly.

I must mention that I have started looking at using boost pools over
the range of sizes expected. Example:

pool 64 bytes
pool 128 bytes
pool 256 bytes
pool 512 bytes
etc..
heap.

If a pool was not provided for a size required, we loan from the heap
and it is logged - very rare. The pools have an initial size estimate,
and grow as required. We don't have this scheme currently though, we
have a scheme of queues (thread safe, of course) that are pre-allocated
(by guessing). We have a little bit of pointer hiding in the memory to
the stack to which the memory must return, and when looking for a
specific size, we use a binary seach. If a specific size does not
exist, we lend from the next up until we find a pool that has
something, else we lend from the heap - which is very rare. I have
toyed with this in comparison too the boost::pool. I think it was very
similar wrt efficiency. boost::pool is more scalable if one gets the
sizes wrong, though (in that the heap is less likely to be used).

> That is very interesting. How do you know if a pointer or a reference
> argument refers to a heap or a stack allocated object? The size of the
> object being pointed to can not tell you that, can it?

Yes, good question. The only reason we consider the size, is that for
large objects, we want to prevent additional copying. For small
objects, we send a copy of the argument over. For large objects we send
a pointer over (and only perform one copy) - the joy of templates. For
references (if the callback receives are reference), we store a copy or
a pointer to a copy. We never store the reference, as the mistake of
sending a reference that exist on a calling stack can easily be made.
Simple, if <T&> typedef T ArgT; Then, after that, the size of ArgT
determines the storage type, so to speak. For pointer storage types,
ownership is released after execution, and the cloned command receives
ownership, until it is destroyed after execution. All arguments are
also pre-allocated, if they happen to be pointers due to large size (a
thing to determine is at what size it become worth not storing the
actual type - this is currently a thumbsuck).

> Are not commands always executed asyncronously by some other thread
> than the one that created a command?

If associated with a CommandServer, yes. We do have a scheme similar to
ADA rendezvous, though (if I understand it correctly), where one task
blocks until another task has completed execution of the command. This
is effectively a synchronous command, then. We have found some use for
it, but quite rare. This is implemented wrapping a binary semaphore
with a Mutex. The recipient signals when the call has completed. The
sender waits at the bin sem. The mutex prevents races... This is
dangerous, though, as it often happens (during implementation of Harrel
State Charts), that we use commands to unwind the stack (also handy).
If a command is executed in the context of a server with who it is
associated, and it takes perform a rendezvous, instant deadlock. Other
more interesting scenarios exist :-). One of the uses in which I have
found this helpfull, is during graceful termination of threads from
other contexts/threads. This has been abstracted though.

> I'd like to take a look at the solution. So far, I could not find means
> of doing so, other than to walk through a list of all threads stack
> ranges.

As I've explained, we used the conservative approach. We use function
templates to derive the applicable command. The arguments are derived
from the member function pointer arguments. If the recipient receives
references, we always copy. Depending on the size, we either copy once
and transfer ownership, or we copy twice - once during the call, and
once during the clone. If the argument of the callback function
receives a bald pointer, we assume the caller knows what he is doing. I
allowed this as sometimes one wants allow associating to (or breaking
associations with) other classes over threads - This reduces mutual
exclusion contention :-) - I suppose not so conservative. I have
created specialisations for std::string and character pointers.
std::strings COW techniques have hurt me bad in the past, and the
specialisation performs explicit copying from one string to another.

Wrt to implementation, I suppose I could mail you - quite big though.
Currently there are still some caveats. Like the receiver of the
command is still a bald pointer. I have been meaning to change that for
a while, but I first have to get boost working on all our platforms...
VxWorks for one (I have not yet found the time). Our current systems
work well despite this, though - but only because we aware of the
caveat.

> Many has in-house implementations of something like that.

I was not necessarily aware, but was wondering along those lines. Hence
my idea of standardising. I'm sure they could provide one with some
good options if they try. They being the ones that realize the standard
- us? I think the idea is good, but I don't think I'm the best
implementor - not to bad, I suppose, but there are better people suited
for the job :-). I thinking people of the likes of erdani etc. I did do
our inhouse implementation though, and it promises more than what is
currently available (IMhO).

> There are quite a big number of choices and implementation strategies,
> I don't think there would be one thing that provides the level of
> abstraction and overhead good enough for everyone.

Hmmm, Java was brave enough to try something. I have not yet looked
what C++/CLI has come up with. I venture something like GC would be
beneficial. I especially like the notion of two phased destruction,
where true ownership exists (and hence deletion), but all references to
the original become aware of its non-existance, which they can test
before calling. This is more-or-less what weak pointer gives you (wish
it was standard). It would be ideal for this use, typically.

> For example, the fact, that the queue holds a weak, not string
> reference to the command, is more of a policy rather than of a
> mechanism. Queues can be implemented using containers + synchronization
> primitives or using platform mechanism like local datagram sockets.

Yes, true - but providing a consistent interface (dictating an
interface), will allow various implementations to do the same thing.
Typically, one only need a container of pointers for this exercise,
ever (behind a consistent notion of something like a CmdSvr).

> I believe we have everything in c++ now required to build a custom
> infrastructure of this kind quite easily. For example, the one you
> described, could be implemented using boost::thread for threading, std
> containers, boost::function + boost::bind for commands, boost smart
> pointers to implement a specific command lifetime policy.

Yes, as we have. But standard would be so-o-o-o much nicer. How about
it. Incorporating a nice simple mechanism that abstracts OOD from
Concurrent D. Our inhouse scheme was easily portable between 3 very
different platforms. Java (what a bore of a language:-) - maybe just
kidding) provides more wrt. architecture. The unwillingness to get
things wrong the first time prevents C++ from providing a solution at
all. boosts constructs are at too a low level, but I agree, could be
used. My tasks look very different to theirs though, but probably
because I did not learn from POSIX.

Thanks for your response, It was insightfull.

Kind regards,

Werner


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Bernhard Sputh wrote:
> Hello Werner,
>
> On Tue, 17 Oct 2006 14:35:13 -0400, werasm wrote:

> This sounds like You are redeveloping Hoare's Channels which are part of
> Communicating Sequential Processes (CSP). To get an idea what CSP is all
> about I recommend to take a peek at Peter Welch's JCSP tutorial
> presentation [0]. Which was in fact was an eye opener for me to understand
> when I was in a similar situation as You some time ago.

After reading some of the papers, to a certain extent - yes. I have
been introduces to CSP long ago (probably 8 years now) without
realizing where it came from. We have always used this architecture for
communicating between threads (The difference for me between threads
and processes, of course being that processes don't share memory (one
process 's memory is not accessible, naturally - from another). We have
previoulsy made use of (elaborate) switch statements to handle this
form of communication.

In C++, commands (GOF Command Pattern) can be implemented that the
recipient can always handle the messages (taken from the queue) in the
same way. Using non-member templates, arguments can be deduced
seemlessly, and after an initial implementation, commands are able to
encapsulate all types of functions without changing the command itself
(like a vector can contain all kinds of items). Therefore it evolved,
over time and due to me recognizing (in our establishment) the role
that commands had to play here (I was partially my idea, admittedly),
handling by switch statements fell away completely.

> Yes others and myself have developed CSP implementations over the
> past few years for C, C++, Objective-C and Java. And we are still
> developing our implementations further, to obtain a complete
> programming language implementation of CSP. You may want to take a look at
> Neil's C++CSP [1] and at the WOTUG homepage [2] giving You some background
> information regarding CSP.

I will look at these, thank you.

Regards,

Werner


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On Oct 18, 3:35 am, "werasm" <w_er...@telkomsa.net> wrote:

[snip]

>
> One of the caveats of this architecture, is that the references in a
> command waiting to be processed may become invalid. This could be
> easily solved by using concepts similar to weak pointers instead of
> bald pointers (typically making either mechanisms optional). Of course,
> something like GC would be ideal, but the command's association with
> the recipient should not prolong the lifetime of the recipient, but
> should only prevent the command from executing in the event of the
> recipient seizing to exist). We have implemented this scheme on a
> number of platforms (I suppose our current implementation can be
> heavily scrutinized, but I think the concept is sound).
>
> I must emphasize that this architecture lives within the boundaries of
> one process/application, and is only used for intertask/thread
> communication.
>


I think the pattern/architecture you described is similar with
"Active Object", which is created by Douglas C. Schmidt
(the author of ACE).

Here is the paper for the details:

"Active Object An Object Behavioral Pattern for Concurrent
Programming"

at

  http://citeseer.ist.psu.edu/lavender96active.html


> My questions are:
>
> - Have some of you implemented similar schemes/architectures?

Yes, we need this pattern helps because it

   "decouples method execution from method invocation in order
    to simplify synchronized access to an object that resides in its
    own thread of control. "

> - Could a scheme like this be considered as a viable candidate for
> intertask/thread communication in C++.

For the same reason, yes.

> Of course, the notion of
> task/thread currently does not even exist in C++.
>


Even C++ does not have any thread model, we did learn a lot
from practice,  ACE and Boost.Thread are good examples.


> - The idea is then (to summarize), to create a high level callable
> entity in C++ that is associated with a context (or not).

Yes, in Active Object (Or Active Method), the contexts for both
the caller and callee could be different, which is useful for
decoupling.

> - To have the notion of Context, where context represents what is
> currently known as "Thread of execution", each Context just consisting
> of code to execute callable entities when they arrive.
>


Exactly. That is the main point for this pattern/scheme.

> Obviously, sometimes traditional Mutual Exclusion is still required,
> but we have found this to be minimal when not using the message queues,
> and failsafe (and abstracted) when using the message queues.
>
> The constructs that we needed to realize this were...
>
> - Mutexes.
> - Counting Semaphores.
>

Well, of course these low level constructs are necessary. But the
other synchronization primitives can also be used to implement
the concept of "event".

Before starting your own implementation for these stuffs,
you can check ACE for implementation details. And if it is too
heavy for your jobs, then I suggest you check another nice
component library -- POCO at:

   http://www.appinf.com/poco/info/index.html

The POCO library has the following classes, which implement
the Active Object pattern for different considerations:

   - ActiveMethod
   - ActiveResult
   - Activity

All of the classes are base on its own thread interface and
in turn use its own synchronization primitives.

This library is released under Boost library and can be
used for Windows, *nix, cygwin and MacOS.

I must say this library is not as mature as ACE or other
solid component library, but I like its small size interfaces
(part of them cloned from Java/C#) and nice examples.

> ... if the platform did not support the notion of message queues (very
> similar to the notion of POSIX mq_, with which I'm sure some of you
> might be familiar). These constructs are constructs that need to be
> realised in C++ anyway, right?
>

IMHO, Message Queue, together with MailBox for other
platform,  are very useful, but they are not necessarily to
implement the above pattern.

Please check Poco's ActiveMethod for how to pass the
argument and return the result.

HTH


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

werasm wrote:
> Maxim Yegorushkin wrote:

[]

> >I wonder why you need a counting
> > semaphore, rather than a mutex + condition.
>
> I suppose a counting sem was an overkill - you are right.
> Maybe/probably even slows things down.

I would not expect any noticeable performance hit in either case.

> The queue does have that
> knowledge (to know that it is empty).

AFAIK, a queue can be implemented using any of the two fundamental data
structures: array or list. You can tell whether it is empty easily. Is
it not the case for you?

> > Allocating memory may block a thread. Does it mean that you are
> > allocating from a preallocated pool?
>
> Yes, it does :-). In this environment, there are unfortunately 2 more
> decisions that you have to make:
>
> 1. How much are you willing to queue. I only queue cloned pointers,
> btw, which makes things quite efficient.
> 2. How much you are willing to queue, and the sizes of your commands
> and their arguments are an indication of how much memory you need to
> pre-allocate, sadly.
>
> I must mention that I have started looking at using boost pools over
> the range of sizes expected. Example:

[]

> If a pool was not provided for a size required, we loan from the heap
> and it is logged - very rare. The pools have an initial size estimate,
> and grow as required. We don't have this scheme currently though, we
> have a scheme of queues (thread safe, of course) that are pre-allocated
> (by guessing). We have a little bit of pointer hiding in the memory to
> the stack to which the memory must return, and when looking for a
> specific size, we use a binary seach. If a specific size does not
> exist, we lend from the next up until we find a pool that has
> something, else we lend from the heap - which is very rare. I have
> toyed with this in comparison too the boost::pool. I think it was very
> similar wrt efficiency. boost::pool is more scalable if one gets the
> sizes wrong, though (in that the heap is less likely to be used).

Be aware, that by sharing blocks allocated by boost::pool you can
inflict false sharing, that is, if you modify an object which happens
to reside in the the same cache line with the object used by another
thread, you are effectively playing ping-pong between processors on
smp. There are allocators designed for multithreaded applications which
try to mitigate the problem. http://www.hoard.org/ provides docs which
discuss the issue in detail.

> > That is very interesting. How do you know if a pointer or a reference
> > argument refers to a heap or a stack allocated object? The size of the
> > object being pointed to can not tell you that, can it?
>
> Yes, good question. The only reason we consider the size, is that for
> large objects, we want to prevent additional copying. For small
> objects, we send a copy of the argument over. For large objects we send
> a pointer over (and only perform one copy) - the joy of templates.

sizeof(std::list<int>) == 8 for a 32-bit system using GNU C++ standard
library. Yet, passing the list by value can be costly if it contains a
large number of elements. In other words, the size of the objects tells
you nothing about how expensive copy operation may be. Am I missing
something?

> For
> references (if the callback receives are reference), we store a copy or
> a pointer to a copy. We never store the reference, as the mistake of
> sending a reference that exist on a calling stack can easily be made.
> Simple, if <T&> typedef T ArgT; Then, after that, the size of ArgT
> determines the storage type, so to speak. For pointer storage types,
> ownership is released after execution, and the cloned command receives
> ownership, until it is destroyed after execution. All arguments are
> also pre-allocated, if they happen to be pointers due to large size (a
> thing to determine is at what size it become worth not storing the
> actual type - this is currently a thumbsuck).

I don't understand why you need to do that. Why not just take
everything by value, just like boost::bind does? In this case the user
has total control and transparency: if he wants to pass an argument by
reference he just pass a (smart) pointer.

[]

> > Many has in-house implementations of something like that.
>
> I was not necessarily aware, but was wondering along those lines. Hence
> my idea of standardising. I'm sure they could provide one with some
> good options if they try. They being the ones that realize the standard
> - us? I think the idea is good, but I don't think I'm the best
> implementor - not to bad, I suppose, but there are better people suited
> for the job :-). I thinking people of the likes of erdani etc. I did do
> our inhouse implementation though, and it promises more than what is
> currently available (IMhO).
>
> > There are quite a big number of choices and implementation strategies,
> > I don't think there would be one thing that provides the level of
> > abstraction and overhead good enough for everyone.
>
> Hmmm, Java was brave enough to try something. I have not yet looked
> what C++/CLI has come up with. I venture something like GC would be
> beneficial. I especially like the notion of two phased destruction,
> where true ownership exists (and hence deletion), but all references to
> the original become aware of its non-existance, which they can test
> before calling. This is more-or-less what weak pointer gives you (wish
> it was standard). It would be ideal for this use, typically.
>
> > For example, the fact, that the queue holds a weak, not string
> > reference to the command, is more of a policy rather than of a
> > mechanism. Queues can be implemented using containers + synchronization
> > primitives or using platform mechanism like local datagram sockets.
>
> Yes, true - but providing a consistent interface (dictating an
> interface), will allow various implementations to do the same thing.
> Typically, one only need a container of pointers for this exercise,
> ever (behind a consistent notion of something like a CmdSvr).

Three different implementation of queues / worker threads have been
used in my projects. They serve different purposes and their interfaces
reflect the fact. I could not provide the same interface for all. This
may be just my fault :)

> > I believe we have everything in c++ now required to build a custom
> > infrastructure of this kind quite easily. For example, the one you
> > described, could be implemented using boost::thread for threading, std
> > containers, boost::function + boost::bind for commands, boost smart
> > pointers to implement a specific command lifetime policy.
>
> Yes, as we have. But standard would be so-o-o-o much nicer. How about
> it. Incorporating a nice simple mechanism that abstracts OOD from
> Concurrent D. Our inhouse scheme was easily portable between 3 very
> different platforms. Java (what a bore of a language:-) - maybe just
> kidding) provides more wrt. architecture. The unwillingness to get
> things wrong the first time prevents C++ from providing a solution at
> all.

I agree that it would be beneficial for new starters. Java requites a
different mind set, their decisions may not be in line with c++
philosophy.

> boosts constructs are at too a low level, but I agree, could be
> used. My tasks look very different to theirs though, but probably
> because I did not learn from POSIX.

The beauty of boost components, IMO, that they are simple fundamental
mechanisms from which you can compose any application level policy you
like.


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Maxim Yegorushkin wrote:
> werasm wrote:
> > The queue does have that
> > knowledge (to know that it is empty).
>
> AFAIK, a queue can be implemented using any of the two fundamental data
> structures: array or list. You can tell whether it is empty easily. Is
> it not the case for you?

Yes, as I've said here above "It <does> have the knowledge", and I
agree. My notion of queue I think, correlates with yours ;-). The fact
that I used a counting sem was probably just me recognizing at the time
that I might as well use a counting sem instead of a binary sem, and
take until I block, instead of looping until its empty.

> Be aware, that by sharing blocks allocated by boost::pool you can
> inflict false sharing, that is, if you modify an object which happens
> to reside in the the same cache line with the object used by another
> thread, you are effectively playing ping-pong between processors on
> smp. There are allocators designed for multithreaded applications which
> try to mitigate the problem. http://www.hoard.org/ provides docs which
> discuss the issue in detail.

I will keep this in mind. Our own scheme consist of a stack (actually
mailboxes/channels) of pointers to pre-allocated memory. Each stack
represents a certain size. Obviously getting the memory is tread-safe
(implied by the containers). The structure is constant, and we use a
binary search, on allocation to find the correct size. The returing of
memory is fast due to a hidden pointer to the Mailbox (or stack) from
where the memory was taken. I suppose the possibility of false sharing
would then exist for our scheme too?

> sizeof(std::list<int>) == 8 for a 32-bit system using GNU C++ standard
> library.

I see your point...

> Yet, passing the list by value can be costly if it contains a
> large number of elements. In other words, the size of the objects tells
> you nothing about how expensive copy operation may be. Am I missing
> something?

No, you aren't missing something, and very good point (I'm shortsited).
We do require that the arguments are assignable. True, the size of the
object does not relate to how expensive copying/assignment may be,
except for types that do not allocate any dynamic memory. Currently, we
have a scheme by which the caller can decide. Our arguments are not
often POD types, and the decisions are mostly based on size. This lead
us to discussing the possibility of making it rely on size by default,
but keeping the option open for the client (or caller) to decide. To be
honest the size thing was on my wishlist :-). We currently have the
possibility (or policy) of using either actual arguments, or pointers
to arguments, and the caller selects which one, based mostly one size.

Therefore, currently basically boils down to following:

1) Based on argument of callback, decide on type to store.
2) Based on storage policy, decide on how memory is
allocated/deallocated, and on how the type will be stored and
retrieved, and assigned.
3) Storage policy may be determined explicitly or automatically by
evaluating the size of the argument (admittedly, this does not
necessarily correlate with how expensive its copy may be - an
oversight).
4) Of course, new storage policies may evolve.

> For
> references (if the callback receives are reference), we store a copy or
> a pointer to a copy.
[snip]

> I don't understand why you need to do that. Why not just take
> everything by value, just like boost::bind does? In this case the user
> has total control and transparency: if he wants to pass an argument by
> reference he just pass a (smart) pointer.

The callback (by means of argument deduction) determines the type
eventually transported as part of the <Command> which will be used as
argument to the delayed call. References can't be used, and are changed
to "by value" automatically. There are a couple of reasons that they
can't be used.

1) The invocation of the command may happen later than the
construction, therefore a value to bind to the reference does not
necessarily exist. This can be easily solved by storing a pointer, and
is probably not an issue.

2) More importantly, because of the argument deduction from the
callback, naive programmers have in the past mistakedly passed a
reference to an object on one stack over the queue :-). Therefore, we
change all references to by value, but allow the actual callback to
receive any argument. We don't impose any restriction on the callback
itself, as this would make is incompatible with legacy.

> Three different implementation of queues / worker threads have been
> used in my projects. They serve different purposes and their interfaces
> reflect the fact. I could not provide the same interface for all. This
> may be just my fault :)

I suppose (honestly) that I may be more naive than you. I know, even
now - that my implementation could have been better (Especially now
that boost is around). Nevertheless, I have found that our
queues/worker threads do handle all the cases we need. I would not
publish it (yet), but you're welcome to look at parts of it. You can
contact me. I would appreciate good critique.

[snip]

> The beauty of boost components, IMO, that they are simple fundamental
> mechanisms from which you can compose any application level policy you
> like

Yes, boost (and things like Andrei Alexandrescu's MCD) has done allot
for the language (IMhO). Unfortunately my implementation realized
before boost was well known (Dark in Africa :-).

Let me know if you would want a peep. I would mail it (or a subset) to
whichever address you prefer.

Kind Regards,

Werner

email (replace _PUNT_ with . and _BY_ with @):

- MyName_PUNT_Erasmus_AT_za_PUNT_saabgroup_PUNT_com


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

werasm wrote:
> Currently, we
> have a scheme by which the caller can decide. Our arguments are not
> often POD types, and the decisions are mostly based on size.

Beg your pardon. This should read "Our arguments are most often POD
types", which causes the decisions to be bases on size, and which
causes the clients (or callers) to often select the policy based on
size.

W


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]