Asynchronous channels in Ada

Asynchronous channels in Ada

[Hadrien Grasland]

Hi everyone,

Some months ago, I had some fun learning Go (golang). I found in particular its concurrency model, based on coroutines and pipe-like communication channels, to be quite sound and representative of the way I write task-parallel programs.

Now, to an Ada programmer, coroutines and synchronous channels are not particularly special. Coroutines map well to Ada tasks (although most Ada tasking implementations are not as CPU- and memory-efficient); and rendezvous and protected objects may be considered a more powerful and general alternative to Go-like synchronous channels.

On the other hand, asynchronous "buffered" channels are really a neat abstraction for producer-consumer problems, and I regularly end up facing a problem where I wish I had some in Ada. I'm pretty convinced that one could quite easily build a library-based Ada abstraction which offers similar functionality, but better. Before trying it myself, though, I'd like to check out here if you know of an open-source Ada project which has already implemented something similar.

The ideal intertask communication primitive which I am looking for is...

* One-to-one (one-to-many raises plenty of implementation problems, is not used nearly as often, and may be emulated using one-to-one)
* One-way (there are well-separated sender and recipient roles in the communication)
* FIFO (objects are received in the same order as they are sent)
* Type-safe (all data packets must be of the same type, which should be selectable using a generic formal parameter for optimal abstraction generality)
* Portable across architectures and Ada compilers
* Mostly asynchronous (sender does not block unless buffer is full, recipient does not block unless buffer is empty)
* Interruptible (sender and recipient can terminate the communication)
* Exception-friendly (sender can notify recipient that an exception has occured)
* Blocking-safe (the only circumstance where a task can end up blocking forever on a channel is if there is a task on the other end that is permanently blocked too)
* Reference-counted (that's really the only sane memory management policy for objects which are shared between two unrelated pieces of tasking code)
* Devoid of dynamic memory allocation after initialization time (unless the data packets being transmitted contain controlled dynamically allocated data, of course)

Anyone is aware of something like this that would already exist in the wild ?

Cheers,
Hadrien

Re: Asynchronous channels in Ada

[Simon Wright]

What about Ada.Containers.Bounded_Synchronized_Queues? (ARM A.18.29)

(the ARM doesn't say what happens if the queue is full ... but I'm sure
it does the right thing)

(the AARM says "Since this type has a bounded capacity, Enqueue might
block if the queue is full", so I think we're OK!)

Re: Asynchronous channels in Ada

[Jeffrey R. Carter]

On 02/19/2016 02:02 PM, Hadrien Grasland wrote:
> 
> On the other hand, asynchronous "buffered" channels are really a neat
> abstraction for producer-consumer problems, and I regularly end up facing a
> problem where I wish I had some in Ada. I'm pretty convinced that one could
> quite easily build a library-based Ada abstraction which offers similar
> functionality, but better. Before trying it myself, though, I'd like to check
> out here if you know of an open-source Ada project which has already
> implemented something similar.
> 
> Anyone is aware of something like this that would already exist in the wild?

For Ada 12, there are synchronous queues (ARM A.18.27-29).

http://www.ada-auth.org/standards/rm12_w_tc1/html/RM-A-18-27.html

If you use a language supported by more than one compiler vendor, the PragmARCs
(both for ISO/IEC 8652:1995 and ISO/IEC 8652:2007) have protected queues, both
bounded and unbounded:

https:/pragmada.x10hosting.com/

https://github.com/jrcarter/PragmARC

-- 
Jeff Carter
"You empty-headed animal-food-trough wiper."
Monty Python & the Holy Grail
04

Re: Asynchronous channels in Ada

[Robert A Duff]

Simon Wright <simon@pushface.org> writes:

> What about Ada.Containers.Bounded_Synchronized_Queues? (ARM A.18.29)
>
> (the ARM doesn't say what happens if the queue is full ... 

It does, but it's in A.18.27(10).

>...but I'm sure
> it does the right thing)

- Bob

Re: Asynchronous channels in Ada

[Brad Moore]

On Friday, February 19, 2016 at 2:51:35 PM UTC-7, Jeffrey R. Carter wrote:
> On 02/19/2016 02:02 PM, Hadrien Grasland wrote:
> > 
> > On the other hand, asynchronous "buffered" channels are really a neat
> > abstraction for producer-consumer problems, and I regularly end up facing a
> > problem where I wish I had some in Ada. I'm pretty convinced that one could
> > quite easily build a library-based Ada abstraction which offers similar
> > functionality, but better. Before trying it myself, though, I'd like to check
> > out here if you know of an open-source Ada project which has already
> > implemented something similar.
> > 
> > Anyone is aware of something like this that would already exist in the wild?
> 
> For Ada 12, there are synchronous queues (ARM A.18.27-29).
> 
> http://www.ada-auth.org/standards/rm12_w_tc1/html/RM-A-18-27.html
> 
> If you use a language supported by more than one compiler vendor, the PragmARCs
> (both for ISO/IEC 8652:1995 and ISO/IEC 8652:2007) have protected queues, both
> bounded and unbounded:
> 
> https:/pragmada.x10hosting.com/
> 
> https://github.com/jrcarter/PragmARC


Probably the synchronous queues of Ada 2012 is what you want, but if you
are looking for something different, another alternative that provides portability across Ada 2005 or later, you might be interested in dequesterity

https://sourceforge.net/projects/dequesterity/

It has various flavours of synchronous (and non-synchronous queues), including remote queues for distributed computing. The synchronous passive buffers are likely the closest fit from the other dequesterity buffer types, based on your description.

Brad 

Re: Asynchronous channels in Ada

[Dmitry A. Kazakov]

On 2016-02-19 22:02, Hadrien Grasland wrote:

> Some months ago, I had some fun learning Go (golang). I found in
> particular its concurrency model, based on coroutines and pipe-like
> communication channels, to be quite sound and representative of the way
> I write task-parallel programs.

My condolences... (:-))

Co-routine if you meant that, is a kind of synchronous call. As such it 
does not require a buffered communication channel with its counterparts.

> Now, to an Ada programmer, coroutines and synchronous channels are not
> particularly special. Coroutines map well to Ada tasks (although most
> Ada tasking implementations are not as CPU- and memory-efficient);

Tasks are greatly less efficient than co-routines, considered a single 
core, in order to make a comparable case of course.

Co-routines on their part are very low-level and unsafe.

If Ada had user-tasks implemented as co-routines that would be nice for 
some interesting cases, like implementation of heavy-duty servers and 
communication protocols.

> On the other hand, asynchronous "buffered" channels are really a neat
> abstraction for producer-consumer problems,

Well, I would say, it is a *source* of producer-consumer problems, 
especially regarding QoS, topology issues (e.g. n-to-m connections), 
resource management etc, the list is almost infinite...

> and I regularly end up
> facing a problem where I wish I had some in Ada. I'm pretty convinced
> that one could quite easily build a library-based Ada abstraction which
> offers similar functionality, but better. Before trying it myself,
> though, I'd like to check out here if you know of an open-source Ada
> project which has already implemented something similar.
>
> The ideal intertask communication primitive which I am looking for is...
>
> * One-to-one (one-to-many raises plenty of implementation problems, is
> not used nearly as often, and may be emulated using one-to-one)

Quite often, actually. A non-blocking implementation of 1-n:

http://www.dmitry-kazakov.de/ada/components.htm#Generic_Blackboard

> * One-way (there are well-separated sender and recipient roles in the communication)
> * FIFO (objects are received in the same order as they are sent)
> * Type-safe (all data packets must be of the same type, which should
> be selectable using a generic formal parameter for optimal abstraction
> generality)
> * Portable across architectures and Ada compilers
> * Mostly asynchronous (sender does not block unless buffer is full,
> recipient does not block unless buffer is empty)
> * Interruptible (sender and recipient can terminate the communication)
> * Exception-friendly (sender can notify recipient that an exception has occured)

What exception? If publisher needs to notify the subscriber of anything 
it does so by posting corresponding data, that is.

> * Blocking-safe (the only circumstance where a task can end up
> blocking forever on a channel is if there is a task on the other end
> that is permanently blocked too)
> * Reference-counted (that's really the only sane memory management
> policy for objects which are shared between two unrelated pieces of
> tasking code)

Hmm, for 1-1 communications there is little sense to have the buffer 
reference counted. Publisher and subscriber can be easily put in the 
buffer's scope that is.

There are more interesting cases when publisher or subscriber can walk 
away at any time, but they are more related to 1-n cases.

Or maybe you mean reference-counted data being sent. That does not make 
sense either, because data are marshaled.

The only case when data can be reference-counted is when they cannot be 
or are too expensive to marshal. In that case you post a reference 
instead of data. But that is not the buffer's business.

> * Devoid of dynamic memory allocation after initialization time
> (unless the data packets being transmitted contain controlled
> dynamically allocated data, of course)
>
> Anyone is aware of something like this that would already exist in the wild ?

Yes, there are plenty.

I have a lock-free implementation of non-blocking FIFO:

http://www.dmitry-kazakov.de/ada/components.htm#Generic_FIFO

and a blocking one extension of.

http://www.dmitry-kazakov.de/ada/components.htm#Generic_FIFO.Signaled_FIFO

You can put any of it into a reference-counted object:

http://www.dmitry-kazakov.de/ada/components.htm#Objects_etc


-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Asynchronous channels in Ada

[Hadrien Grasland]

Hi all,

Thank you for your numerous and insightful replies ! As of now, I'm pretty convinced that I can easily find many excellent synchronized FIFO queues implementations in the wild, which satisfy most of my requirements quite well.

However, I am a bit unsatisfied when it comes to the exception handling part of my requirements. Now, I am aware that this was the most exotic part (and go's channels, which I take inspiration from, don't take care of that at all). I also noticed that Dmitry sounded quite confused by that requirement. So let me elaborate on it further.

Let's put ourself in a typical usage scenario where you have a producer task and a consumer task, the former producing a stream of identically typed data that is read by the other. This producer/consumer pair may be part of a fairly large and complex data processing pipeline, such as a compiler frontend.

Now, something goes wrong on the producer side, for any reason, which prevents this task from correctly producing its next data packet. Yet the consumer is expecting said packet. One can then imagine a number of options for the producer :

    Continue as if nothing happened and send the next packet, possibly logging the error somewhere.
    Abort the whole program.
    Ask the user what to do.
    Emit a regular data packet with a special value (e.g. NaN for a float).
    Transmit a specially crafted data packet representing an error (i.e. an exception).

Option 1 is usually too little, and option 2 is usually too much. Option 3 is a cop-out with terrible usability. Most data types are not designed to express error conditions, making option 4 pretty limited in practice. This only leaves option 5 of designing either data transmission channels or their contents with error handling in mind.

Now, you can't do that very well with a simple FIFO, because that container is only designed as a transmission channel for one type of data. So perhaps some are thinking of using two FIFOs, one for regular data and one for exceptions. But then, the consumer will need to check for exceptions all the time, in addition to regular data, a design which is both error-prone (for the developer) and inefficient (twice the synchronization overhead).

Another option is to use one FIFO, but have it carry not just regular data but a wrapper type which can take either data or exceptions. That design is also quite impractical for the consumer, and it is also somewhat inefficient since all data packets need to carry an extra discriminant which must be written by the producer and analyzed by the consumer, even if errors are rare.

My conclusion is that the optimal solution would be something slightly more advanced than a FIFO, which basically encapsulates together a regular FIFO and a simpler exception transmission mechanism (maybe just a boolean flag and a one-element buffer). For all intents and purpose, the resulting ADT looks and feel mostly like a FIFO to everyone involved. But the producer can also send exceptions through it, in which case the consumer will throw when trying to read the corresponding data item.

I wonder if I could find a way to build such a communication channel and reuse existing FIFO implementations without incurring twice the synchronization overhead. Most likely I should look into unsynchronized FIFO implementations then.

Just food for thought, I guess,
Hadrien

Re: Asynchronous channels in Ada

[Jeffrey R. Carter]

On 02/21/2016 03:57 PM, Hadrien Grasland wrote:
> 
> Let's put ourself in a typical usage scenario where you have a producer task
> and a consumer task, the former producing a stream of identically typed data
> that is read by the other. This producer/consumer pair may be part of a
> fairly large and complex data processing pipeline, such as a compiler
> frontend.
> 
> Now, something goes wrong on the producer side, for any reason, which
> prevents this task from correctly producing its next data packet. Yet the
> consumer is expecting said packet. One can then imagine a number of options
> for the producer :

Typically, such designs are used so the consumer doesn't need to know or care
about what happens with the producer, and so there's no need for anything
special about the queue or the data passed via it. Certainly this is the
assumption that most general-purpose solutions will take. If you have specific
needs that such solutions don't address, you will probably need to create a
specific solution.

That said, it would be very easy to add a Boolean value to the PragmARC blocking
protected queues that would cause an exception in a consumer when it next
attempts to get a value from the queue.

-- 
Jeff Carter
"Little blondes with long hair and short skirts and
boots and big chests and bright, witty, and perceptive."
Play It Again, Sam
128

Re: Asynchronous channels in Ada

[Dmitry A. Kazakov]

On 21/02/2016 23:57, Hadrien Grasland wrote:

> Now, something goes wrong on the producer side, for any reason, which
> prevents this task from correctly producing its next data packet.

That cannot happen. You should reconsider your design if you really 
think it could. When the communication channel is up the producer must 
function.

I do not consider the case of a bug in the producer code. But anything 
else is just a valid state. That includes all handled exceptions on the 
producer side.

And any valid producer state must have a corresponding valid state on 
the subscriber's side. This is just basics of any communication protocol 
design.

> Transmit a specially crafted data packet representing an error (i.e. an exception).

This is not an "error" it is a valid state.

There is no problem to marshal an exception to the subscriber side. You 
make the data object like this:

type Data (Abnormal : Boolean := False) is record
    case Abnormal is
       when True =>
          Reason : Ada.Exceptions.Exception_ID;
       when False =>
          ... -- Normal data
    end case;
end record;

Remove default value for Abnormal if your FIFO can handle indefinite 
objects. However, assuming that abnormal data objects are not frequently 
to transmit, making them indefinite might be not necessary.

Regarding bugs, the safest way to handle a bug is to kill the 
application as early as possible. It makes debugging easier.

> I wonder if I could find a way to build such a communication channel
> and reuse existing FIFO implementations without incurring twice the
> synchronization overhead. Most likely I should look into unsynchronized
> FIFO implementations then.

I think any implementation would go.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Asynchronous channels in Ada

[Georg Bauhaus]

On 21.02.16 23:57, Hadrien Grasland wrote:
>      Transmit a specially crafted data packet representing an error (i.e. an exception).

Just for clarification, this sounds like a representation of
a value that expresses "error", so in the strict Ada sense it would not
be an exception, and so cannot trigger anything that isn't expressly
looking for an error value and then raises (like in Dmitry's solution that
uses an exception identifier as a "normal" value; in extension, I'd consider
an abstract common type from which two concrete types are derived,
one for good state and one for bad state, if you want to separate
concerns accordingly and avoid repeated conditionals inspecting discriminant
values).

But I'm assuming you want some mechanism that is triggered automatically
so that coding the normal case does not need to perform case distinctions?
At this point, I'd also look into locating the errors, in the sender,
in the enqueuing call, during processing, during delivery, again during
processing, in the dequeuing call, and in validating steps. Maybe, then,
there is need for more than a Boolean indicator, like an enumeration that's
known to all parties, or more wrapper types one for each of the locations, etc.

One thing that comes to mind is a notification system like interrupts:
A wants B to know that there was an exception, so A signals (by intent) B
so as to interrupt it, or A has some other special task N deliver
a notification, which again interrupts B. Or N is a high priority
caller or some such, but there is that would be case distinction again (by
task entry).

Another option that might work is alternating inspection of a data
queue a second queue that sends state information as necessary.

-- 
"HOTDOGS ARE NOT BOOKMARKS"
Springfield Elementary teaching staff

Re: Asynchronous channels in Ada

[Hadrien Grasland]

So, to summarize, what you would suggest is to mimick the layered architecture of network protocols, and separate the task of getting messages across from one task to another (which can be handled by any synchronized queue implementation), from that of transmitting either valid data or errors inside of messages.

You would then handle the latter task by using either...

1. Discriminated records that can contain either messages or errors depending on the discriminant's value
2. A tagged message interface that is associated to two concrete implementations, one which carries data and normally returns it upon "opening", and one which carries errors and throws exceptions in this situation.

That sounds like a very good idea, I'll experiment with it some more. Thanks !

Re: Asynchronous channels in Ada

[rieachus]

There is a "trick" which is very useful in certain contexts.  Your program has producer and consumer tasks, but you need occasionally to restart the channel and put everything in a consistent state:
declare
  -- queue state and exception information here.
begin
  loop
    exit when...
    begin
      task Producer...;
      task Consumer...;
    exception when ==> ...
    end;
  end loop;
end;

Your consumer task needs to use a terminate_alternative, but it should probably be doing that anyway.  This is just a skeleton scaffolding, but it should get the idea across.  If producer needs to signal an exception, it just does.  When the consumer starts up again, it looks to see what went wrong.

Of course, if your design requires that the producer and consumer tasks be on different hardware, or some such, then you do need a more complex solution. (I spent a lot of time working on systems where a "deadman" timer going off meant you had to get everything restarted inside so many milliseconds. ;-)  You do not want one too many threats to cause the aircraft's controls to lock up.