Termination of tasks waiting on a protected queue

Termination of tasks waiting on a protected queue

[Natasha Kerensikova]

Hello,

I have been having a task termination issue, and I'm wondering whether I
got my design wrong or whether I'm missing something, so I ask you to
help me on that.

The basic need is delegating potentially long jobs to a dedicated task
(or pool of tasks) so that the program flow generating the jobs and
continue quickly. I furthermore assume that the jobs are "fire and
forget", that there is no need to report anything about completion (or
lack of thereof) to the code that generated the jobs (or more
realistically, that reporting is performed through channels outside of
the scope of the problem).

So I went with the basic design below:

   package Example is
      type Job_Description is private;

      function Create_Job (...) return Job_Description;
      procedure Enqueue_Job (Job : in Job_Description);

   private

      package Job_Lists is new Ada.Containers.Doubly_Linked_Lists
        (Job_Description);

      protected Queue is
         procedure Append (Job : in Job_Description);
         entry Get_Next (Job : out Job_Description);
      private
         List : Job_Lists.List;
         Has_Job : Boolean := False;
      end Queue;

      task Worker is
      end Worker;
   end Example;

   package body Example is
      procedure Enqueue_Job (Job : in Job_Description) is
      begin
         Queue.Append (Job);
      end Enqueue_Job;

      protected body Queue is
         procedure Append (Job : in Job_Description) is
         begin
            List.Append (Job);
            Has_Job := True;
         end Append;

         entry Get_Next (Job : out Job_Description)
            when Has_Job is
         begin
            Job := List.First_Element;
            List.Delete_First;
            Has_Job := not List.Is_Empty;
         end Get_Next;
      end Queue;

      task body Worker is
         Job : Job_Description;
      begin
         loop
            Queue.Get_Next (Job);
            <actually to the job>
         end loop;
      end Worker;
   end Example;

As you might have guessed, I have recently read a lot of material about
Ravenscar profile, and as far as I can tell this example does match the
profile, even though the original need happens in a much more relaxed
environment.

For example, without Ravenscar restrictions, the Worker task could
easily be turned into a task type, and use an array of them to
implement a pool of workers.

The problem is, how to terminate cleanly the worker tasks in a
non-Ravenscar environment when the main application is completed?

From my understanding of ARM 9.3, I need a terminate alternative in the
worker tasks. But those can only exist in selective accepts, so I have
to turn things around and make the task wait for one of its entries to
be called, rather than wait for an external protected entry.

But then, how can a worker task entry be used to solve my problem? A
protected operation cannot call a task entry, because it's potentially
blocking. The job generator cannot call the entry directly, because it
would block when the task is not ready, so I still need a queue between
the generator and the worker task.

Alternatively, I could use a special value for Job_Description (or a new
out parameter) to make the worker exit its infinite loop, and somehow
make the protect Queue object aware that the master is completed, so
that it can signal the worker task(s) to complete. But how can this be
implemented? Since the tasks block the finalization of the master, I
can't rely on a Finalize procedure to notify the protected object.


Thanks in advance for your help,
Natasha

Re: Termination of tasks waiting on a protected queue

[anon]

try using a Select / terminate statements

      task body Worker is
         Job : Job_Description;
      begin
         loop
           select
              Queue.Get_Next (Job);
              <actually to the job>
           or
              terminate ;
           end select ;
         end loop;
      end Worker;


In <slrnlngofv.i0l.lithiumcat@nat.rebma.instinctive.eu>, Natasha Kerensikova <lithiumcat@instinctive.eu> writes:
>Hello,
>
>I have been having a task termination issue, and I'm wondering whether I
>got my design wrong or whether I'm missing something, so I ask you to
>help me on that.
>
>The basic need is delegating potentially long jobs to a dedicated task
>(or pool of tasks) so that the program flow generating the jobs and
>continue quickly. I furthermore assume that the jobs are "fire and
>forget", that there is no need to report anything about completion (or
>lack of thereof) to the code that generated the jobs (or more
>realistically, that reporting is performed through channels outside of
>the scope of the problem).
>
>So I went with the basic design below:
>
>   package Example is
>      type Job_Description is private;
>
>      function Create_Job (...) return Job_Description;
>      procedure Enqueue_Job (Job : in Job_Description);
>
>   private
>
>      package Job_Lists is new Ada.Containers.Doubly_Linked_Lists
>        (Job_Description);
>
>      protected Queue is
>         procedure Append (Job : in Job_Description);
>         entry Get_Next (Job : out Job_Description);
>      private
>         List : Job_Lists.List;
>         Has_Job : Boolean := False;
>      end Queue;
>
>      task Worker is
>      end Worker;
>   end Example;
>
>   package body Example is
>      procedure Enqueue_Job (Job : in Job_Description) is
>      begin
>         Queue.Append (Job);
>      end Enqueue_Job;
>
>      protected body Queue is
>         procedure Append (Job : in Job_Description) is
>         begin
>            List.Append (Job);
>            Has_Job := True;
>         end Append;
>
>         entry Get_Next (Job : out Job_Description)
>            when Has_Job is
>         begin
>            Job := List.First_Element;
>            List.Delete_First;
>            Has_Job := not List.Is_Empty;
>         end Get_Next;
>      end Queue;
>
>      task body Worker is
>         Job : Job_Description;
>      begin
>         loop
>            Queue.Get_Next (Job);
>            <actually to the job>
>         end loop;
>      end Worker;
>   end Example;
>
>As you might have guessed, I have recently read a lot of material about
>Ravenscar profile, and as far as I can tell this example does match the
>profile, even though the original need happens in a much more relaxed
>environment.
>
>For example, without Ravenscar restrictions, the Worker task could
>easily be turned into a task type, and use an array of them to
>implement a pool of workers.
>
>The problem is, how to terminate cleanly the worker tasks in a
>non-Ravenscar environment when the main application is completed?
>
From my understanding of ARM 9.3, I need a terminate alternative in the
>worker tasks. But those can only exist in selective accepts, so I have
>to turn things around and make the task wait for one of its entries to
>be called, rather than wait for an external protected entry.
>
>But then, how can a worker task entry be used to solve my problem? A
>protected operation cannot call a task entry, because it's potentially
>blocking. The job generator cannot call the entry directly, because it
>would block when the task is not ready, so I still need a queue between
>the generator and the worker task.
>
>Alternatively, I could use a special value for Job_Description (or a new
>out parameter) to make the worker exit its infinite loop, and somehow
>make the protect Queue object aware that the master is completed, so
>that it can signal the worker task(s) to complete. But how can this be
>implemented? Since the tasks block the finalization of the master, I
>can't rely on a Finalize procedure to notify the protected object.
>
>
>Thanks in advance for your help,
>Natasha

Re: Termination of tasks waiting on a protected queue

[Jeffrey Carter]

On 05/18/2014 12:32 AM, Natasha Kerensikova wrote:
>
> I have been having a task termination issue, and I'm wondering whether I
> got my design wrong or whether I'm missing something, so I ask you to
> help me on that.
>
> The basic need is delegating potentially long jobs to a dedicated task
> (or pool of tasks) so that the program flow generating the jobs and
> continue quickly. I furthermore assume that the jobs are "fire and
> forget", that there is no need to report anything about completion (or
> lack of thereof) to the code that generated the jobs (or more
> realistically, that reporting is performed through channels outside of
> the scope of the problem).

I have done something similar for pools of worker tasks. I used an instance of 
PragmARC.Queue_Unbounded_Blocking to hold the job requests rather than rolling 
my own for each task pool. The solution to termination was to use a timed entry 
call to the queue, with another protected object with a function to indicate if 
the pool tasks should end. The tasks looked like

Forever : loop
    select
       Job_Queue.Get (Item => Info);

       Process (Info => Info);
    or
       delay Check_Interval;

       exit Forever when Control.Finalizing;
    end select;
end loop Forever;

Obviously not Ravenscar compliant.

Check_Interval was quite long, 2 seconds.

-- 
Jeff Carter
"If I could find a sheriff who so offends the citizens of Rock
Ridge that his very appearance would drive them out of town ...
but where would I find such a man? Why am I asking you?"
Blazing Saddles
37

Re: Termination of tasks waiting on a protected queue

[sbelmont700]

My preferred method is to not queue the data type, per say, but a discriminated record that is either a 'data' or 'exit', with the former containing the item and the latter containing nothing.  The producers then post an 'exit' item when it's time to shut down, that the consumers then use to exit the loop:

begin
  loop
     Blocking_Dequeue(x);
     exit when x.type == Shutdown;
     Do_Something (x.data);
  end loop;
end;

The problem is making it exception proof, since finalization can't be used to do it automatically.

It has always seemed strange that Ada doesn't seem to have a way to block on multiple entries, in line with posix select() or waitformultipleobjects.  I'd be happy with even just a function that can wait on an array of suspension objects.

-sb

Re: Termination of tasks waiting on a protected queue

[Jeffrey Carter]

On 05/18/2014 11:42 AM, sbelmont700@gmail.com wrote:
>
> It has always seemed strange that Ada doesn't seem to have a way to block on
> multiple entries, in line with posix select() or waitformultipleobjects.  I'd
> be happy with even just a function that can wait on an array of suspension
> objects.

select
    Entry1;
then abort
    Entry2;
end select;

-- 
Jeff Carter
"If I could find a sheriff who so offends the citizens of Rock
Ridge that his very appearance would drive them out of town ...
but where would I find such a man? Why am I asking you?"
Blazing Saddles
37

Re: Termination of tasks waiting on a protected queue

[Natasha Kerensikova]

Hello,

On 2014-05-18, anon@att.net <anon@att.net> wrote:
> try using a Select / terminate statements

It does not work. In the code below, "select" is immediately followed by
"Queue.Get_Next (Job)", which is an entry call,
so the "select" can be a timed entry call, a conditional entry call, or
an asynchronous transfer of control, but not a selective accept.
However, terminate alternatives can exist only in selective accepts.

>       task body Worker is
>          Job : Job_Description;
>       begin
>          loop
>            select
>               Queue.Get_Next (Job);
>               <actually to the job>
>            or
>               terminate ;
>            end select ;
>          end loop;
>       end Worker;

To put in GNAT's terms:

    68.             terminate ;
                   12
        >>> statement expected
        >>> only allowed alternative in timed entry call is delay

Re: Termination of tasks waiting on a protected queue

[Natasha Kerensikova]

Hello,

On 2014-05-18, Jeffrey Carter <spam.jrcarter.not@spam.not.acm.org> wrote:
> I have done something similar for pools of worker tasks. I used an
> instance of PragmARC.Queue_Unbounded_Blocking to hold the job requests
> rather than rolling my own for each task pool. The solution to
> termination was to use a timed entry call to the queue, with another
> protected object with a function to indicate if the pool tasks should
> end.

That's a solution I considered, along with the idea of outputing a
special value in the blocking protected entry to indicate that tasks
should end (choosing between both solutions depending on how unnatural
adding the shutdown order to the queue is, and how badly I want the
termination order to be immediate).

But I haven't managed to design a robust way of triggering the
indication that tasks should end.

This is a library-level queue and a library level task providing a
service to the whole application. So there is no object whose
finalization can be used as a trigger for the task shutdown order.
The only solution I see is to provide an explicit Shudown procedure that
sends the task shutdown signal, but it is fragile: what if the client
forgets to call it? or if an exception make control flow jump around it?
and what if the client calls it too early, and more jobs are added to
the queue?

> Obviously not Ravenscar compliant.

Well Ravenscar was only involved in my coming up with such a solution.
As soon as I'm thinking about task termination, I'm leaving Ravenscar
realm anyway.



Thanks for your help,
Natasha

Re: Termination of tasks waiting on a protected queue

[sbelmont700]

On Sunday, May 18, 2014 2:48:16 PM UTC-4, Jeffrey Carter wrote:
> 
> select
> 
>     Entry1;
> 
> then abort
> 
>     Entry2;
> 
> end select;
> 

It was my understanding that these would execute sequentially; that is, it would try Entry1 and, finding it closed, block on Entry2.  I was referring to a "wait on all and select the first one to unblock" behavior.

-sb

Re: Termination of tasks waiting on a protected queue

[Jeffrey Carter]

On 05/18/2014 01:51 PM, sbelmont700@gmail.com wrote:
> On Sunday, May 18, 2014 2:48:16 PM UTC-4, Jeffrey Carter wrote:
>>
>> select
>>
>>    Entry1;
>>
>> then abort
>>
>>    Entry2;
>>
>> end select;
>>
>
> It was my understanding that these would execute sequentially; that is, it
> would try Entry1 and, finding it closed, block on Entry2.  I was referring to
> a "wait on all and select the first one to unblock" behavior.

I don't think so. It will block on Entry1 while executing the code in the "then 
abort" block, which will block on Entry2. If Entry1 completes before the block, 
it will attempt to abort the execution of the block. If the block completes 
before the trigger (Entry1), it will attempt to abort the call to the trigger.

Note that if an entry call has been accepted but not completed and not requeued 
with abort, it's probably abort deferred, so the abort won't take place until 
the entry call completes. So it's possible for both entry calls to complete.

I'm not saying this is a good solution, simply that there is a way to block on 2 
entry calls at once.

-- 
Jeff Carter
"If I could find a sheriff who so offends the citizens of Rock
Ridge that his very appearance would drive them out of town ...
but where would I find such a man? Why am I asking you?"
Blazing Saddles
37

Re: Termination of tasks waiting on a protected queue

[Jeffrey Carter]

On 05/18/2014 12:54 PM, Natasha Kerensikova wrote:
>
> This is a library-level queue and a library level task providing a
> service to the whole application. So there is no object whose
> finalization can be used as a trigger for the task shutdown order.
> The only solution I see is to provide an explicit Shudown procedure that
> sends the task shutdown signal, but it is fragile: what if the client
> forgets to call it? or if an exception make control flow jump around it?
> and what if the client calls it too early, and more jobs are added to
> the queue?

I had no access to the pool tasks once they were created, so calling a task 
entry was not possible. The Control PO was library level, and was called so the 
function returned True when the system was shutting down. There were 
library-level tasks, too, so it wasn't the finalization of a controlled object 
that made that call. The system knew when it was time to stop.

If you don't have that knowledge, then things get interesting. You may have to 
accept the failings you discuss and push the responsibility off to the client.

-- 
Jeff Carter
"If I could find a sheriff who so offends the citizens of Rock
Ridge that his very appearance would drive them out of town ...
but where would I find such a man? Why am I asking you?"
Blazing Saddles
37

Re: Termination of tasks waiting on a protected queue

[Brad Moore]

On 14-05-18 01:32 AM, Natasha Kerensikova wrote:
> The problem is, how to terminate cleanly the worker tasks in a
> non-Ravenscar environment when the main application is completed?
>
>  From my understanding of ARM 9.3, I need a terminate alternative in the
> worker tasks. But those can only exist in selective accepts, so I have
> to turn things around and make the task wait for one of its entries to
> be called, rather than wait for an external protected entry.
>
> But then, how can a worker task entry be used to solve my problem? A
> protected operation cannot call a task entry, because it's potentially
> blocking. The job generator cannot call the entry directly, because it
> would block when the task is not ready, so I still need a queue between
> the generator and the worker task.

A protected entry can however requeue to a task entry.

I was faced with a similar problem in the non-Ravenscar task pools in 
Paraffin.

I did not want the programmer to have to call some protected subprogram 
to trigger the task pool to terminate. I also did not want to have to 
wait for a timeout to expire before the application could exit. I wanted 
it to be immediate.

So in your example, it might look something like;

package body Example is

    function Create_Job return Job_Description is
       Result : Job_Description;
    begin
       return Result;
    end Create_Job;

    procedure Enqueue_Job (Job : in Job_Description) is
    begin
       Queue.Append (Job);
    end Enqueue_Job;

    protected body Queue is
       entry Append (Job : in Job_Description) when True is
       begin
          if not Idle then
             requeue Worker.Work_Queued;
          else
             List.Append (Job);
          end if;
       end Append;

       procedure Get_Next (Job : out Job_Description) is
       begin
          Job := List.First_Element;
          List.Delete_First;
       end Get_Next;

       function Is_Empty return Boolean is
       begin
          return List.Is_Empty;
       end Is_Empty;

       procedure Worker_Idle is
       begin
          Idle := True;
       end Worker_Idle;

       function Worker_Is_Idle return Boolean is
       begin
          return Idle;
       end Worker_Is_Idle;

    end Queue;

    task body Worker is
       Job : Job_Description;
    begin
       loop
          begin

             Queue.Worker_Idle;

             if not Queue.Is_Empty then
                Queue.Get_Next (Job);
             else

                select
                   accept Work_Queued (Next_Job : Job_Description) do
                      Job := Next_Job;
                   end Work_Queued;

                or
                   terminate;
                end select;
             end if;

             --  <actually to the job>

          end;
       end loop;
    end Worker;
end Example;

Brad

> Thanks in advance for your help,
> Natasha
>

Re: Termination of tasks waiting on a protected queue

[Natasha Kerensikova]

Hello,

On 2014-05-18, Brad Moore <brad.moore@shaw.ca> wrote:
> I was faced with a similar problem in the non-Ravenscar task pools in 
> Paraffin.
>
> I did not want the programmer to have to call some protected subprogram 
> to trigger the task pool to terminate. I also did not want to have to 
> wait for a timeout to expire before the application could exit. I wanted 
> it to be immediate.

That looks indeed very similar to what I had in mind.

> So in your example, it might look something like;

Your example is exactly what I was looking for when posting here.
Thanks a lot!

However I'm considering merging the functionalities of Worker_Idle,
Is_Empty and Get_Next into a single protected procedure. Something like

      procedure Get_Next
        (Job : out Job_Description;
         Idle : out Boolean) is
      begin
         if List.Is_Empty then
            Idle := True;
            Queue.Idle := True;
         else
            Job := List.First_Element;
            List.Delete_First;
         end if;
     end Get_Next;

But then the solution is a bit more difficult to scale to multiple
worker tasks. Maybe with an array of Boolean for Idle. Fortunately I
don't have to deal with that for now.


Thanks again for the solution,
Natasha

Re: Termination of tasks waiting on a protected queue

[Randy Brukardt]

<sbelmont700@gmail.com> wrote in message 
news:3ab5fcf0-d2a8-4c82-ab51-02b829aebcaa@googlegroups.com...
> It has always seemed strange that Ada doesn't seem to have a way to block 
> on
> multiple entries, in line with posix select() or waitformultipleobjects. 
> I'd be happy
> with even just a function that can wait on an array of suspension objects.

There was such a proposal for Ada 9x. After much discussion, a report was 
commissioned from the three user-implementor teams. All three reported that 
the operation would be much more expensive to implement than it appears on 
the surface. In particular, the people with hard real-time deadlines could 
not use any imaginable implementation of the feature -- which would have 
made it useless to the #1 constituency. The idea was dropped and never has 
been raised since.

I've totally forgotten why that was, but if you (or someone else) could dig 
up the reports, you could find out why it doesn't work in Ada. (I certainly 
have a printed copy in a dusty box somewhere, but I'm not motivated to go 
spelunking for it.)

[I wrote one of those three reports, but I have no idea where the original, 
digital version of our report is. It's definitely not on my current 
computer. If I could have found it, I could have told you the title of our 
report, which might have helped you dig it up.]

                                                Randy.

Re: Termination of tasks waiting on a protected queue

[Dmitry A. Kazakov]

On Mon, 19 May 2014 16:49:29 -0500, Randy Brukardt wrote:

> <sbelmont700@gmail.com> wrote in message 
> news:3ab5fcf0-d2a8-4c82-ab51-02b829aebcaa@googlegroups.com...
>> It has always seemed strange that Ada doesn't seem to have a way to block 
>> on multiple entries, in line with posix select() or waitformultipleobjects. 
>> I'd be happy with even just a function that can wait on an array of suspension objects.
> 
> There was such a proposal for Ada 9x. After much discussion, a report was 
> commissioned from the three user-implementor teams. All three reported that 
> the operation would be much more expensive to implement than it appears on 
> the surface. In particular, the people with hard real-time deadlines could 
> not use any imaginable implementation of the feature -- which would have 
> made it useless to the #1 constituency. The idea was dropped and never has 
> been raised since.

For the OP problem, which is quite common, it would be enough to allow
single terminate alternative in select. Then code could be written as:

   task body Worker is
      Job : Job_Description;
   begin
      loop
         select
            Queue.Get_Next (Job);
            -- Do the job
         or delay 1.0;
         end select;
         select   -- This is not Ada!
            terminate;
         else
            exit;
         end select;
      end loop;
   end Worker;   

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

Re: Termination of tasks waiting on a protected queue

[Dmitry A. Kazakov]

On Tue, 20 May 2014 09:54:38 +0200, Dmitry A. Kazakov wrote:

>    task body Worker is
>       Job : Job_Description;
>    begin
>       loop
>          select
>             Queue.Get_Next (Job);
>             -- Do the job
>          or delay 1.0;
>          end select;
>          select   -- This is not Ada!
>             terminate;
>          else
>             exit;
               ^^^^ null;  -- Of course

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

Re: Termination of tasks waiting on a protected queue

[Alejandro R. Mosteo]

On Monday, May 19, 2014 1:05:59 AM UTC+2, Brad Moore wrote:
> On 14-05-18 01:32 AM, Natasha Kerensikova wrote:
> 
> > The problem is, how to terminate cleanly the worker tasks in a
> 
> > non-Ravenscar environment when the main application is completed?
> 
> >
> 
> >  From my understanding of ARM 9.3, I need a terminate alternative in the
> 
> > worker tasks. But those can only exist in selective accepts, so I have
> 
> > to turn things around and make the task wait for one of its entries to
> 
> > be called, rather than wait for an external protected entry.
> 
> >
> 
> > But then, how can a worker task entry be used to solve my problem? A
> 
> > protected operation cannot call a task entry, because it's potentially
> 
> > blocking. The job generator cannot call the entry directly, because it
> 
> > would block when the task is not ready, so I still need a queue between
> 
> > the generator and the worker task.
> 
> 
> 
> A protected entry can however requeue to a task entry.
> 
> 
> 
> I was faced with a similar problem in the non-Ravenscar task pools in 
> 
> Paraffin.
> 
> 
> 
> I did not want the programmer to have to call some protected subprogram 
> 
> to trigger the task pool to terminate. 

Could an atomic boolean be used to avoid a protected object? Given that after it being set it wouldn't be unset, and there's no race condition, I wonder.

Re: Termination of tasks waiting on a protected queue

[Brad Moore]

On 14-05-27 05:08 AM, Alejandro R. Mosteo wrote:
> On Monday, May 19, 2014 1:05:59 AM UTC+2, Brad Moore wrote:
>> On 14-05-18 01:32 AM, Natasha Kerensikova wrote:
>>
>>> The problem is, how to terminate cleanly the worker tasks in a
>>
>>> non-Ravenscar environment when the main application is completed?
>>
>>>
>>
>>>   From my understanding of ARM 9.3, I need a terminate alternative in the
>>
>>> worker tasks. But those can only exist in selective accepts, so I have
>>
>>> to turn things around and make the task wait for one of its entries to
>>
>>> be called, rather than wait for an external protected entry.
>>
>>>
>>
>>> But then, how can a worker task entry be used to solve my problem? A
>>
>>> protected operation cannot call a task entry, because it's potentially
>>
>>> blocking. The job generator cannot call the entry directly, because it
>>
>>> would block when the task is not ready, so I still need a queue between
>>
>>> the generator and the worker task.
>>
>>
>>
>> A protected entry can however requeue to a task entry.
>>
>>
>> I did not want the programmer to have to call some protected subprogram
>>
>> to trigger the task pool to terminate.
>
> Could an atomic boolean be used to avoid a protected object? Given that after it being set it wouldn't be unset, and there's no race condition, I wonder.
>

The problem is not the protected subprogram. It is having to force the
programmer to explicitly specify somewhere in the code a trigger to 
initiate the destruction of the task pool, whether via a protected 
object or setting an atomic boolean, or some other means.

Setting the trigger before the main task exits for instance, is error 
prone because there may be other tasks executing that might still want 
to use the task pool.

Using the mechanism I suggested means the task pool does not get 
destroyed until all tasks have completed, since the main task wont exit 
until all other tasks have either completed or are waiting on a select 
statement with a Terminate alternative.