How to: communication between multiple tasks using protected objects - with no polling?

How to: communication between multiple tasks using protected objects - with no polling?

[Esa Riihonen]

I'm new to Ada and I have a problem ;)

After reading through 'Programming in ADA 2012' by John Barnes - I decided to try Ada in implementing the core functionality of a C-program I have been involved recently.

The C-program consists of various Linux processes that communicate with each other mainly through FIFO's. It seems natural to implement the process functionality as Ada tasks.  As the inter task communication I decided to try protected types (instead of task entries).

Here is the problem. My typical C-process 'listens' to several FIFOs connected to separate processes. This is realized using a ppoll-type 'reactor' - so in essence the process is sleeping until there is some activity in any of the monitored file descriptors (I guess this is in essence quite basic arrangement in the 'C-world').

I first thought I can implement this by the 'select' - something like this:

PO1 and PO2 are instantiations of a protected type with entry 'Get'.

...
loop
  ...
  select
    PO1.Get(...);
  or
    PO2.Get(...);
  or 
    ...
  end select;
  ...
end loop;
...

Alas, I quicky found out that 'or' is not allowed here between the protected object entries.

I can do something like this instead:

...
loop
  ...
  select
    PO1.Get(...);
  else
    null;
  end select;

  select
    PO2.Get(...);
  else
    null;
  end select;
  ...
end loop;
...

But this would be now constantly polling in a loop. I would like the task to be suspended if there is nothing to do. I understand(?) that I probably could achieve this by accepting task entries. But I wan't to know whether it can be done using the protected objects for communication. 

Am I missing something? Or have my though processes been totally corrupted by too much (forced) C during the decades - and thus I'm trying to do something silly and dangerous?

Re: How to: communication between multiple tasks using protected objects - with no polling?

[Hubert]

Hey,

I'm new to Ada as well and I was facing the same problem in my 
application. I have to wait for input from TCP sockets as well as input 
from the user.

It is true that the Select statement, when calling a protected type 
entry or procedure can be used only for one such call. It is not 
possible to wait for multiple protected object entries.

So my solution was to have one protected object that serves as a form of 
event buffer.

Any section of my code that needs to communicate with the task, writes 
an event into the PO. The task then waits for an event in the PO. the PO 
provides these events through an entry with a  barrier that is something 
like "WHEN LENGTH( Event_Queue) > 0".

You can then also use a timed select statement like so:

SELECT
   Wait_For_Event( PO );
OR
   Delay 1.0;
END SELECT

which will time out after 1 second and allow your task to do something 
else before entering the select statement again in a loop. For instance 
you could check for a task entry that commands your task to halt and 
exit, if you want to delete the task or shut down the program



---
This email has been checked for viruses by Avast antivirus software.
http://www.avast.com

Re: How to: communication between multiple tasks using protected objects - with no polling?

[Jeffrey Carter]

On 01/20/2015 03:36 PM, Esa Riihonen wrote:
> 
> The C-program consists of various Linux processes that communicate with each
> other mainly through FIFO's. It seems natural to implement the process
> functionality as Ada tasks.  As the inter task communication I decided to try
> protected types (instead of task entries).

You should also revisit your design in light of Ada tasking capabilities. The
choice of multiple tasks that communicate through queues may not be the best choice.

> Am I missing something? Or have my though processes been totally corrupted by
> too much (forced) C during the decades - and thus I'm trying to do something
> silly and dangerous?

You can do

select
   PO1.Get (...);
then abort
   PO2.Get (...);
end select;

This might, however, result in both entries being executed.

Another approach might be

type Q_ID is (Q1, Q2, ...);

type Q_Item (Q : Q_ID := Q_ID'First) is record
   case Q is
   when Q1 =>
      Item_1 : Q1_Item;
   when Q2 =>
      Item_2 : Q2:Item;
   ...
   end case;
end record;

protected Qs is
   entry Get (Item : out Q_Item);
private -- Qs
   Q_1 : Q1_Q;
   Q_2 : Q2_Q;
   ...
end Qs;

protected body Qs is
   entry Get (Item : out Q_Item) when
      not Q_1.Is_Empty or not Q_2.Is_Empty or ...
   is
      -- Empty declarative part
   begin -- Get
      if not Q_1.Is_Empty then
         Item := (Q => Q1, Item_1 => Q_1.Get);
      elsif not Q_2.Is_Empty then
         item := (Q => Q2, Item_2 => Q_2.Get;
      ...
      end if;
   end Get;
end Qs;

if your system is actually many tasks adding items to queues and one waiting for
something on one of those queues, then it might be best to have the waiting task
have entries, and put forwarder tasks between the queues and the waiting task.

-- 
Jeff Carter
"Ada has made you lazy and careless. You can write programs in C that
are just as safe by the simple application of super-human diligence."
E. Robert Tisdale
72

Re: How to: communication between multiple tasks using protected objects - with no polling?

[Simon Wright]

Jeffrey Carter <spam.jrcarter.not@spam.not.acm.org> writes:

> Another approach might be
>
> type Q_ID is (Q1, Q2, ...);
>
> type Q_Item (Q : Q_ID := Q_ID'First) is record
>    case Q is
>    when Q1 =>
>       Item_1 : Q1_Item;
>    when Q2 =>
>       Item_2 : Q2:Item;
>    ...
>    end case;
> end record;
>
> protected Qs is
>    entry Get (Item : out Q_Item);
> private -- Qs
>    Q_1 : Q1_Q;
>    Q_2 : Q2_Q;
>    ...
> end Qs;
>
> protected body Qs is
>    entry Get (Item : out Q_Item) when
>       not Q_1.Is_Empty or not Q_2.Is_Empty or ...
>    is
>       -- Empty declarative part
>    begin -- Get
>       if not Q_1.Is_Empty then
>          Item := (Q => Q1, Item_1 => Q_1.Get);
>       elsif not Q_2.Is_Empty then
>          item := (Q => Q2, Item_2 => Q_2.Get;
>       ...
>       end if;
>    end Get;
> end Qs;

Yet another approach: make Q_Item an abstract tagged type with an
abstract Handle operation. You'd need the actual queue inside the PO to
be of Q_Item'Class (or perhaps an access to such, in which case you'd
need to do your own deallocation).

Re: How to: communication between multiple tasks using protected objects - with no polling?

[Dmitry A. Kazakov]

On Tue, 20 Jan 2015 14:36:20 -0800 (PST), Esa Riihonen wrote:

> Here is the problem. My typical C-process 'listens' to several FIFOs
> connected to separate processes. This is realized using a ppoll-type
> 'reactor' - so in essence the process is sleeping until there is some
> activity in any of the monitored file descriptors (I guess this is in
> essence quite basic arrangement in the 'C-world').
> 
> I first thought I can implement this by the 'select' - something like this:
> 
> PO1 and PO2 are instantiations of a protected type with entry 'Get'.
> 
> ...
> loop
>   ...
>   select
>     PO1.Get(...);
>   or
>     PO2.Get(...);
>   or 
>     ...
>   end select;
>   ...
> end loop;

The typical design of 1-n is reverse: the publisher queues request to the
consumer rather than lets the consumer to come and pick it.

The publisher may call the consumer's entry or else queue the request into
a queue. If publishers shall not be blocked (e.g. in order to prevent
priority inversion or due to time constraints), also when it is n-m, use
the blackboard instead of a queue.

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

Re: How to: communication between multiple tasks using protected objects - with no polling?

[Esa Riihonen]

keskiviikko 21. tammikuuta 2015 2.19.43 UTC+2 Hubert kirjoitti:

... snip ...

> So my solution was to have one protected object that serves as a form of 
> event buffer.
> 
> Any section of my code that needs to communicate with the task, writes 
> an event into the PO. The task then waits for an event in the PO. the PO 
> provides these events through an entry with a  barrier that is something 
> like "WHEN LENGTH( Event_Queue) > 0".

The thing is that in this special case I have in mind my 'writers' are just reporting their status once in a while and have more important things to do - so I don't want them blocked. If I have just one PO for the 'reader' then the 'writers' might block each other and be unnecessry blocked while the 'reader' is going through the messages of the other 'writers'. Thus I tried to build the system with one separete PO for each writer task. 
 
I guess that in practice the associated blocking delays are not a concern in this case. But as I'm using this as an excercise for Ada I'm also concerned about this 'in principle' ;)

> You can then also use a timed select statement like so:
> 
> SELECT
>    Wait_For_Event( PO );
> OR
>    Delay 1.0;
> END SELECT
> 
> which will time out after 1 second and allow your task to do something 
> else before entering the select statement again in a loop. For instance 
> you could check for a task entry that commands your task to halt and 
> exit, if you want to delete the task or shut down the program

That is a good point - I probably will end up implementing the logic along these lines. 

Thanks.

... snip ...

Re: How to: communication between multiple tasks using protected objects - with no polling?

[Esa Riihonen]

keskiviikko 21. tammikuuta 2015 2.47.29 UTC+2 Jeffrey Carter kirjoitti:

... snip ...

> You should also revisit your design in light of Ada tasking capabilities. The
> choice of multiple tasks that communicate through queues may not be the best choice.

That is totally correct.

... snip ...

> You can do
> 
> select
>    PO1.Get (...);
> then abort
>    PO2.Get (...);
> end select;
> 
> This might, however, result in both entries being executed.

If I understand correctly this will indeed work when selecting between two PO entries. And it wouldn't matter if both got executed (although I just now can't see how this could happen). However, there seems not to be a natural way to expand this for more than those two. This seems to be syntactically correct (compiles):

 select
    PO1.Get (...);
 then abort
    select
       PO2.Get (...);
    then abort
       PO3.Get (...);
    end select
 end select;

But I'm not sure whether it would actually do what I want it to do. That is: suspend there until any of the entry barriers becomes true and then exit the whole outermost select statement?

Even if it works I have a (minor) concern that it is not 'pretty' as it doesn't reflect the mutual equality of the entries - and thus has a feel of 'hack' there ;)

> Another approach might be
> 
> type Q_ID is (Q1, Q2, ...);
> 
> type Q_Item (Q : Q_ID := Q_ID'First) is record
>    case Q is
>    when Q1 =>
>       Item_1 : Q1_Item;
>    when Q2 =>
>       Item_2 : Q2:Item;
>    ...
>    end case;
> end record;
> 
> protected Qs is
>    entry Get (Item : out Q_Item);
> private -- Qs
>    Q_1 : Q1_Q;
>    Q_2 : Q2_Q;
>    ...
> end Qs;
> 
> protected body Qs is
>    entry Get (Item : out Q_Item) when
>       not Q_1.Is_Empty or not Q_2.Is_Empty or ...
>    is
>       -- Empty declarative part
>    begin -- Get
>       if not Q_1.Is_Empty then
>          Item := (Q => Q1, Item_1 => Q_1.Get);
>       elsif not Q_2.Is_Empty then
>          item := (Q => Q2, Item_2 => Q_2.Get;
>       ...
>       end if;
>    end Get;
> end Qs;

Thanks for that! I'm not sure I did understand it thoroughly at first reading though I did say that I did read 'the book' - but surely it didn't all sink in in the first reading ;)

> if your system is actually many tasks adding items to queues and one waiting for
> something on one of those queues, then it might be best to have the waiting task
> have entries, and put forwarder tasks between the queues and the waiting task.

'Forwarder tasks' - definitely might be something I will study at this stage.

Thanks a lot.

> -- 
> Jeff Carter
> "Ada has made you lazy and careless. You can write programs in C that
> are just as safe by the simple application of super-human diligence."
> E. Robert Tisdale
> 72

I really like the Tisdale quote - gonna steal it ;)

Re: How to: communication between multiple tasks using protected objects - with no polling?

[Esa Riihonen]

keskiviikko 21. tammikuuta 2015 10.28.08 UTC+2 Dmitry A. Kazakov kirjoitti:
> On Tue, 20 Jan 2015 14:36:20 -0800 (PST), Esa Riihonen wrote:
> 
> > Here is the problem. My typical C-process 'listens' to several FIFOs
> > connected to separate processes. This is realized using a ppoll-type
> > 'reactor' - so in essence the process is sleeping until there is some
> > activity in any of the monitored file descriptors (I guess this is in
> > essence quite basic arrangement in the 'C-world').
> > 
> > I first thought I can implement this by the 'select' - something like this:
> > 
> > PO1 and PO2 are instantiations of a protected type with entry 'Get'.
> > 
> > ...
> > loop
> >   ...
> >   select
> >     PO1.Get(...);
> >   or
> >     PO2.Get(...);
> >   or 
> >     ...
> >   end select;
> >   ...
> > end loop;
> 
> The typical design of 1-n is reverse: the publisher queues request to the
> consumer rather than lets the consumer to come and pick it.
> 
> The publisher may call the consumer's entry or else queue the request into
> a queue. If publishers shall not be blocked (e.g. in order to prevent
> priority inversion or due to time constraints), also when it is n-m, use
> the blackboard instead of a queue.

Thansk for the answer - and yes, the last one is my situation: the publishers just report their state on certain points and then proceed immediately in their more important stuff and should not be blocked.
I effect there is no queue inside my POs - just the most recent status information from the associated task - I guess this is at least some kind of a 'blackboard'.

So - in my mind I have a small number of students each with a separete blackboard. And instead of my teacher walking around checking whether the answer of any of the sudents is ready - I wan't to let the teacher doze in his/her chair and only be woken up when any of the students have their answer ready. And after the student briefly nudges the teacher he/she must be free to immediately continue with his/her other exams.

I guess I just don't know how this 'blackboard' model should be implemented?

Re: How to: communication between multiple tasks using protected objects - with no polling?

[Jeffrey Carter]

On 01/21/2015 10:16 AM, Esa Riihonen wrote:
> keskiviikko 21. tammikuuta 2015 2.47.29 UTC+2 Jeffrey Carter kirjoitti:
> 
>> select
>>    PO1.Get (...);
>> then abort
>>    PO2.Get (...);
>> end select;
>>
>> This might, however, result in both entries being executed.
> 
> If I understand correctly this will indeed work when selecting between two PO entries. And it wouldn't matter if both got executed (although I just now can't see how this could happen).

Why both might be executed is kind of complicated. There was a thread on here
about this some time ago. Consider the Ada-83 timed entry call:

select
   T.E;
or
   delay 1.0;
end select;

Ada 83 did not have protected types/objects or requeue, so if T.E was accepted
before the delay expired, the delay could be cancelled. If the delay expired
before the entry call was accepted then the entry call was aborted.

Ada 95 introduced protected types/objects and requeue. This changed the
semantics somewhat. Since the entry call (which can now be to a task or PO
entry) can be requeued "with abort", the delay can't be canceled when the entry
call is accepted, since a requeued with abort call can be aborted when the delay
expires. Instead, we have to wait until the entry call completes before we can
cancel the delay. If the delay expires while the entry call is being executed,
that's OK because the execution of an entry call is abort deferred.

Similar considerations apply to the ATC with both branches being entry calls and
result in the possibility of both calls being executed.

> However, there seems not to be a natural way to expand this for more than
> those two. This seems to be syntactically correct (compiles):
> 
>  select
>     PO1.Get (...);
>  then abort
>     select
>        PO2.Get (...);
>     then abort
>        PO3.Get (...);
>     end select
>  end select;

Yes, these can be nested as far as desired.

> But I'm not sure whether it would actually do what I want it to do. That is: suspend there until any of the entry barriers becomes true and then exit the whole outermost select statement?

Yes, but it might execute any number of the entry calls.

> Even if it works I have a (minor) concern that it is not 'pretty' as it doesn't reflect the mutual equality of the entries - and thus has a feel of 'hack' there ;)

It's not pretty and it's not a good idea. ATC is said to be a very complex and
heavyweight construct. I would only use it as a last resort.

>> type Q_ID is (Q1, Q2, ...);
>>
>> type Q_Item (Q : Q_ID := Q_ID'First) is record
>>    case Q is
>>    when Q1 =>
>>       Item_1 : Q1_Item;
>>    when Q2 =>
>>       Item_2 : Q2:Item;
>>    ...
>>    end case;
>> end record;
>>
>> protected Qs is
>>    entry Get (Item : out Q_Item);
>> private -- Qs
>>    Q_1 : Q1_Q;
>>    Q_2 : Q2_Q;
>>    ...
>> end Qs;
>>
>> protected body Qs is
>>    entry Get (Item : out Q_Item) when
>>       not Q_1.Is_Empty or not Q_2.Is_Empty or ...
>>    is
>>       -- Empty declarative part
>>    begin -- Get
>>       if not Q_1.Is_Empty then
>>          Item := (Q => Q1, Item_1 => Q_1.Get);
>>       elsif not Q_2.Is_Empty then
>>          item := (Q => Q2, Item_2 => Q_2.Get;
>>       ...
>>       end if;
>>    end Get;
>> end Qs;

I guess I was asleep when I wrote that. For one thing I left out a way to get
things on the Qs. A better approach would be

protected Queue is
   procedure Put (Item : in Q_Item);
   entry Get (Item : out Q_Item);
private -- Queue
   Q : Q_Item_Q;
end Queue;

protected body Queue is
   procedure Put (Item : in Q_Item) is
      -- Empty declarative part
   begin -- Put
      Q.Put (Item => Item);
   end Put;

   entry Get (Item : out Q_Item) when not Q.Is_Empty is
      -- Empty declarative part
   begin -- Get
      Q.Get (Item => Item);
   end Get;
end Queue;

If you're willing to restrict yourself to a single compiler vendor, Ada 12 has
synchronized queues as part of the standard library, and you could use one of
those instead of writing your own. For earlier versions of Ada, which are
supported by multiple compiler vendors, you could use PragmARC.Queue_Unbounded
(or Queue_Bounded) from the PragmAda Reusable Components rather than writing
your own. I guess it depends on whether writing your own PO is important for
your learning experience.

-- 
Jeff Carter
"Run away! Run away!"
Monty Python and the Holy Grail
58

Re: How to: communication between multiple tasks using protected objects - with no polling?

[Jacob Sparre Andersen]

Esa Riihonen wrote:

> So - in my mind I have a small number of students each with a separete
> blackboard. And instead of my teacher walking around checking whether
> the answer of any of the sudents is ready - I wan't to let the teacher
> doze in his/her chair and only be woken up when any of the students
> have their answer ready. And after the student briefly nudges the
> teacher he/she must be free to immediately continue with his/her other
> exams.
>
> I guess I just don't know how this 'blackboard' model should be
> implemented?

To me it sounds like a single protected object for storing the state of
all the workers (students) makes most sense.  The workers can push in
their most recent state through a (common) protected procedure.  The
master (teacher) blocks on a protected entry until at least one worker
has updated its state.

Greetings,

Jacob
-- 
"Facts do not cease to exist because they are ignored." -- Aldous Huxley

Re: How to: communication between multiple tasks using protected objects - with no polling?

[Dmitry A. Kazakov]

On Wed, 21 Jan 2015 09:34:51 -0800 (PST), Esa Riihonen wrote:

> keskiviikko 21. tammikuuta 2015 10.28.08 UTC+2 Dmitry A. Kazakov kirjoitti:
>> On Tue, 20 Jan 2015 14:36:20 -0800 (PST), Esa Riihonen wrote:
>> 
>>> Here is the problem. My typical C-process 'listens' to several FIFOs
>>> connected to separate processes. This is realized using a ppoll-type
>>> 'reactor' - so in essence the process is sleeping until there is some
>>> activity in any of the monitored file descriptors (I guess this is in
>>> essence quite basic arrangement in the 'C-world').
>>> 
>>> I first thought I can implement this by the 'select' - something like this:
>>> 
>>> PO1 and PO2 are instantiations of a protected type with entry 'Get'.
>>> 
>>> ...
>>> loop
>>>   ...
>>>   select
>>>     PO1.Get(...);
>>>   or
>>>     PO2.Get(...);
>>>   or 
>>>     ...
>>>   end select;
>>>   ...
>>> end loop;
>> 
>> The typical design of 1-n is reverse: the publisher queues request to the
>> consumer rather than lets the consumer to come and pick it.
>> 
>> The publisher may call the consumer's entry or else queue the request into
>> a queue. If publishers shall not be blocked (e.g. in order to prevent
>> priority inversion or due to time constraints), also when it is n-m, use
>> the blackboard instead of a queue.
> 
> Thansk for the answer - and yes, the last one is my situation: the
> publishers just report their state on certain points and then proceed
> immediately in their more important stuff and should not be blocked.
> I effect there is no queue inside my POs - just the most recent status
> information from the associated task - I guess this is at least some kind
> of a 'blackboard'.
> 
> So - in my mind I have a small number of students each with a separete
> blackboard. And instead of my teacher walking around checking whether the
> answer of any of the sudents is ready - I wan't to let the teacher doze in
> his/her chair and only be woken up when any of the students have their
> answer ready. And after the student briefly nudges the teacher he/she must
> be free to immediately continue with his/her other exams.
> 
> I guess I just don't know how this 'blackboard' model should be implemented?

You can use one blackboard for all. The item would contain the student
identity, reference etc.

For an implementation of lock-free blackboard see:

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

Since you have many publishers you must lock the blackboard when writing
it. Readers are still non-blocking. OK, you have just one.

Now you want have a non-busy wait for an event when somebody writes
something into the blackboard. That is a pulse event, see example here:

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

The reader reads the blackboard until there is no new items (the reader's
cursor is behind the cursor to the last item on the blackboard). Then the
reader waits for an event pulsation.

Note that this is a race condition. So you cannot directly use the pulse
event described above (and also for reasons described below). You should
modify it in a way that it would test if the reader's cursor indeed points
after the blackboard end and only then enter waiting. Since this is a
protected action, the event will not be signaled during the test and the
race condition is eliminated.

Naturally you would use a single PO for the pulse event and the write-mutex
in order to minimize the number of protected actions. Protected actions are
expensive. The action releasing the write-mutex will as well pulse the
event [and also release the publisher's object, if reference counting used
for dynamically allocated publishers.]

I know it may look complicated, but it only looks so.

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

Re: How to: communication between multiple tasks using protected objects - with no polling?

[Dmitry A. Kazakov]

On Wed, 21 Jan 2015 19:56:17 +0100, Jacob Sparre Andersen wrote:

> Esa Riihonen wrote:
> 
>> So - in my mind I have a small number of students each with a separete
>> blackboard. And instead of my teacher walking around checking whether
>> the answer of any of the sudents is ready - I wan't to let the teacher
>> doze in his/her chair and only be woken up when any of the students
>> have their answer ready. And after the student briefly nudges the
>> teacher he/she must be free to immediately continue with his/her other
>> exams.
>>
>> I guess I just don't know how this 'blackboard' model should be
>> implemented?
> 
> To me it sounds like a single protected object for storing the state of
> all the workers (students) makes most sense.  The workers can push in
> their most recent state through a (common) protected procedure.  The
> master (teacher) blocks on a protected entry until at least one worker
> has updated its state.

Right, though this works only with a single subscriber (the teacher).
Usually there are more than one and you could not keep the reader's state
in the object anymore, at least when the number of subscribers is not
statically known. You could pass the reader's state to the entry as a
parameter and use tricks to circumvent the rule that parameters may not
appear in the barriers, but that would be more complicated than moving the
storage out of the PO.

In general I try to avoid maintaining complex containers from protected
actions. Yes, this might be probably non-blocking, but still, I find it a
bad idea to allocate/copy/initialize much there. E.g. storing should use a
mutex instead.

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

Re: How to: communication between multiple tasks using protected objects - with no polling?

[Hubert]

the point of a protected object here is that the code each task spends 
in it should be small, just enough to add an entry to a list or so.
When you send a message to a task, it can be that the task is involved 
in a lengthy operatin and thus your task has  to wait until the received 
task can accept it.

You could also make a more complex setup, perhaps something like

Tx1 -> Pox1 -> Tx2 -> Po-final ->Tfinal
Ty2 -> Poy2 -> Ty2 ^

and then Have one output PO per worker task and each has it's own task 
to forward the data to the final PO from which the final task fetches it 
or so.
The Ada tasking system is easy enough to use to set up stuff like this 
pretty quickly and when tasks sleep waiting for an entry they dont eat time.

Just you have to be careful about the maximimum NOF tasks your system 
can support which is, I believe, depended on the underlying OS. But in 
my experience a few dozen are not problem, pehraps even a few 100, 
depending on how much stack each underlying thread reserves. But I 
wasn't able to get any hard data on that.





---
This email has been checked for viruses by Avast antivirus software.
http://www.avast.com

Re: How to: communication between multiple tasks using protected objects - with no polling?

[Esa Riihonen]

torstai 22. tammikuuta 2015 1.22.45 UTC+2 Hubert kirjoitti:
> the point of a protected object here is that the code each task spends 
> in it should be small, just enough to add an entry to a list or so.
> When you send a message to a task, it can be that the task is involved 
> in a lengthy operatin and thus your task has  to wait until the received 
> task can accept it.
> 
> You could also make a more complex setup, perhaps something like
> 
> Tx1 -> Pox1 -> Tx2 -> Po-final ->Tfinal
> Ty2 -> Poy2 -> Ty2 ^
> 
> and then Have one output PO per worker task and each has it's own task 
> to forward the data to the final PO from which the final task fetches it 
> or so.
> The Ada tasking system is easy enough to use to set up stuff like this 
> pretty quickly and when tasks sleep waiting for an entry they dont eat time.

That surely looks promising - AFAICT this was the model that someone other was also proposing "forwarder tasks".

> Just you have to be careful about the maximimum NOF tasks your system 
> can support which is, I believe, depended on the underlying OS. But in 
> my experience a few dozen are not problem, pehraps even a few 100, 
> depending on how much stack each underlying thread reserves. But I 
> wasn't able to get any hard data on that.

My C-program consists of something like 10 processes currently. So, even if I end up to a full scale Ada implementation with added forwarder tasks, we are still speaking of about a couple of dozen tasks max.

Thanks alot again for the insight.

Re: How to: communication between multiple tasks using protected objects - with no polling?

[Esa Riihonen]

keskiviikko 21. tammikuuta 2015 20.39.07 UTC+2 Jeffrey Carter kirjoitti:
> On 01/21/2015 10:16 AM, Esa Riihonen wrote:
> > keskiviikko 21. tammikuuta 2015 2.47.29 UTC+2 Jeffrey Carter kirjoitti:
> > 
> >> select
> >>    PO1.Get (...);
> >> then abort
> >>    PO2.Get (...);
> >> end select;
> >>
> >> This might, however, result in both entries being executed.
> > 
> > If I understand correctly this will indeed work when selecting between two PO entries. And it wouldn't matter if both got executed (although I just now can't see how this could happen).
> 
> Why both might be executed is kind of complicated. There was a thread on here
> about this some time ago. Consider the Ada-83 timed entry call:
> 
> select
>    T.E;
> or
>    delay 1.0;
> end select;
> 
> Ada 83 did not have protected types/objects or requeue, so if T.E was accepted
> before the delay expired, the delay could be cancelled. If the delay expired
> before the entry call was accepted then the entry call was aborted.
> 
> Ada 95 introduced protected types/objects and requeue. This changed the
> semantics somewhat. Since the entry call (which can now be to a task or PO
> entry) can be requeued "with abort", the delay can't be canceled when the entry
> call is accepted, since a requeued with abort call can be aborted when the delay
> expires. Instead, we have to wait until the entry call completes before we can
> cancel the delay. If the delay expires while the entry call is being executed,
> that's OK because the execution of an entry call is abort deferred.
> 
> Similar considerations apply to the ATC with both branches being entry calls and
> result in the possibility of both calls being executed.
> 

OK, I think I understand it now. It seems that even Ada is not totally free of its intricasies that can provide some surprises for an uninitiated ;)

> > However, there seems not to be a natural way to expand this for more than
> > those two. This seems to be syntactically correct (compiles):
> > 
> >  select
> >     PO1.Get (...);
> >  then abort
> >     select
> >        PO2.Get (...);
> >     then abort
> >        PO3.Get (...);
> >     end select
> >  end select;
> 
> Yes, these can be nested as far as desired.
> 
> > But I'm not sure whether it would actually do what I want it to do. That is: suspend there until any of the entry barriers becomes true and then exit the whole outermost select statement?
> 
> Yes, but it might execute any number of the entry calls.
> 
> > Even if it works I have a (minor) concern that it is not 'pretty' as it doesn't reflect the mutual equality of the entries - and thus has a feel of 'hack' there ;)
> 
> It's not pretty and it's not a good idea. ATC is said to be a very complex and
> heavyweight construct. I would only use it as a last resort.
> 
> >> type Q_ID is (Q1, Q2, ...);
> >>
> >> type Q_Item (Q : Q_ID := Q_ID'First) is record
> >>    case Q is
> >>    when Q1 =>
> >>       Item_1 : Q1_Item;
> >>    when Q2 =>
> >>       Item_2 : Q2:Item;
> >>    ...
> >>    end case;
> >> end record;
> >>
> >> protected Qs is
> >>    entry Get (Item : out Q_Item);
> >> private -- Qs
> >>    Q_1 : Q1_Q;
> >>    Q_2 : Q2_Q;
> >>    ...
> >> end Qs;
> >>
> >> protected body Qs is
> >>    entry Get (Item : out Q_Item) when
> >>       not Q_1.Is_Empty or not Q_2.Is_Empty or ...
> >>    is
> >>       -- Empty declarative part
> >>    begin -- Get
> >>       if not Q_1.Is_Empty then
> >>          Item := (Q => Q1, Item_1 => Q_1.Get);
> >>       elsif not Q_2.Is_Empty then
> >>          item := (Q => Q2, Item_2 => Q_2.Get;
> >>       ...
> >>       end if;
> >>    end Get;
> >> end Qs;
> 
> I guess I was asleep when I wrote that. For one thing I left out a way to get
> things on the Qs. A better approach would be
> 
> protected Queue is
>    procedure Put (Item : in Q_Item);
>    entry Get (Item : out Q_Item);
> private -- Queue
>    Q : Q_Item_Q;
> end Queue;
> 
> protected body Queue is
>    procedure Put (Item : in Q_Item) is
>       -- Empty declarative part
>    begin -- Put
>       Q.Put (Item => Item);
>    end Put;
> 
>    entry Get (Item : out Q_Item) when not Q.Is_Empty is
>       -- Empty declarative part
>    begin -- Get
>       Q.Get (Item => Item);
>    end Get;
> end Queue;

At least that is more on my level of understanding - thanks.

> If you're willing to restrict yourself to a single compiler vendor, Ada 12 has
> synchronized queues as part of the standard library, and you could use one of
> those instead of writing your own. For earlier versions of Ada, which are
> supported by multiple compiler vendors, you could use PragmARC.Queue_Unbounded
> (or Queue_Bounded) from the PragmAda Reusable Components rather than writing
> your own. I guess it depends on whether writing your own PO is important for
> your learning experience.

Actually I think I at least would have to consider the synch queues in another part of my rehearsal program.

Many thanks for all the help provided.

> -- 
> Jeff Carter
> "Run away! Run away!"
> Monty Python and the Holy Grail
> 58

Re: How to: communication between multiple tasks using protected objects - with no polling?

[Esa Riihonen]

keskiviikko 21. tammikuuta 2015 22.02.38 UTC+2 Dmitry A. Kazakov kirjoitti:
> On Wed, 21 Jan 2015 09:34:51 -0800 (PST), Esa Riihonen wrote:
> 
> > keskiviikko 21. tammikuuta 2015 10.28.08 UTC+2 Dmitry A. Kazakov kirjoitti:
> >> On Tue, 20 Jan 2015 14:36:20 -0800 (PST), Esa Riihonen wrote:
> >> 
> >>> Here is the problem. My typical C-process 'listens' to several FIFOs
> >>> connected to separate processes. This is realized using a ppoll-type
> >>> 'reactor' - so in essence the process is sleeping until there is some
> >>> activity in any of the monitored file descriptors (I guess this is in
> >>> essence quite basic arrangement in the 'C-world').
> >>> 
> >>> I first thought I can implement this by the 'select' - something like this:
> >>> 
> >>> PO1 and PO2 are instantiations of a protected type with entry 'Get'.
> >>> 
> >>> ...
> >>> loop
> >>>   ...
> >>>   select
> >>>     PO1.Get(...);
> >>>   or
> >>>     PO2.Get(...);
> >>>   or 
> >>>     ...
> >>>   end select;
> >>>   ...
> >>> end loop;
> >> 
> >> The typical design of 1-n is reverse: the publisher queues request to the
> >> consumer rather than lets the consumer to come and pick it.
> >> 
> >> The publisher may call the consumer's entry or else queue the request into
> >> a queue. If publishers shall not be blocked (e.g. in order to prevent
> >> priority inversion or due to time constraints), also when it is n-m, use
> >> the blackboard instead of a queue.
> > 
> > Thansk for the answer - and yes, the last one is my situation: the
> > publishers just report their state on certain points and then proceed
> > immediately in their more important stuff and should not be blocked.
> > I effect there is no queue inside my POs - just the most recent status
> > information from the associated task - I guess this is at least some kind
> > of a 'blackboard'.
> > 
> > So - in my mind I have a small number of students each with a separete
> > blackboard. And instead of my teacher walking around checking whether the
> > answer of any of the sudents is ready - I wan't to let the teacher doze in
> > his/her chair and only be woken up when any of the students have their
> > answer ready. And after the student briefly nudges the teacher he/she must
> > be free to immediately continue with his/her other exams.
> > 
> > I guess I just don't know how this 'blackboard' model should be implemented?
> 
> You can use one blackboard for all. The item would contain the student
> identity, reference etc.
> 
> For an implementation of lock-free blackboard see:
> 
> http://www.dmitry-kazakov.de/ada/components.htm#10.2
> 
> Since you have many publishers you must lock the blackboard when writing
> it. Readers are still non-blocking. OK, you have just one.
> 
> Now you want have a non-busy wait for an event when somebody writes
> something into the blackboard. That is a pulse event, see example here:
> 
> http://www.dmitry-kazakov.de/ada/components.htm#11.2.2
> 
> The reader reads the blackboard until there is no new items (the reader's
> cursor is behind the cursor to the last item on the blackboard). Then the
> reader waits for an event pulsation.
> 
> Note that this is a race condition. So you cannot directly use the pulse
> event described above (and also for reasons described below). You should
> modify it in a way that it would test if the reader's cursor indeed points
> after the blackboard end and only then enter waiting. Since this is a
> protected action, the event will not be signaled during the test and the
> race condition is eliminated.
> 
> Naturally you would use a single PO for the pulse event and the write-mutex
> in order to minimize the number of protected actions. Protected actions are
> expensive. The action releasing the write-mutex will as well pulse the
> event [and also release the publisher's object, if reference counting used
> for dynamically allocated publishers.]

Thanks for the explanation. And the refenced web page looks really good resource for my aim to learn to 'think in Ada'. Added to bookmarks.

> I know it may look complicated, but it only looks so.

I hope that will eventually prove to be so even in my case ;)
 
> -- 
> Regards,
> Dmitry A. Kazakov
> http://www.dmitry-kazakov.de

Re: How to: communication between multiple tasks using protected objects - with no polling?

[G.B.]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote:
> On Wed, 21 Jan 2015 19:56:17 +0100, Jacob Sparre Andersen wrote:

>> To me it sounds like a single protected object for storing the state of
>> all the workers (students) makes most sense.  The workers can push in
>> their most recent state through a (common) protected procedure.  The
>> master (teacher) blocks on a protected entry until at least one worker
>> has updated its state.
> 
> Right, though this works only with a single subscriber (the teacher).
> Usually there are more than one .

The PO and the teacher task(s) could share a suspension
object (one for each teacher). When the PO has collected
enough items, it calls Set_True on some suspension
object to wake the teacher task up.

Re: How to: communication between multiple tasks using protected objects - with no polling?

[Dmitry A. Kazakov]

On Thu, 22 Jan 2015 21:52:17 +0000 (UTC), G.B. wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote:
>> On Wed, 21 Jan 2015 19:56:17 +0100, Jacob Sparre Andersen wrote:
> 
>>> To me it sounds like a single protected object for storing the state of
>>> all the workers (students) makes most sense.  The workers can push in
>>> their most recent state through a (common) protected procedure.  The
>>> master (teacher) blocks on a protected entry until at least one worker
>>> has updated its state.
>> 
>> Right, though this works only with a single subscriber (the teacher).
>> Usually there are more than one .
> 
> The PO and the teacher task(s) could share a suspension
> object (one for each teacher). When the PO has collected
> enough items, it calls Set_True on some suspension
> object to wake the teacher task up.

You missed the point. The scenario I was talking about is a queue, e.g. a
FIFO, which can be implemented using a PO. But a queue is fundamentally a
n-1 scenario, because getting an element from the queue is a destructive
operation, it changes the queue state. In fact, the queue's state is the
state of the subscriber. With multiple subscribers there is no way to tell
which one's state is the queue state. You need the get operation idempotent
and have the subscribers keeping the states of their own.

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