tasking in Ada and Annex D question

tasking in Ada and Annex D question

[nabbasi]

Hello, 

This is gnat 3.11p, on red hat 5.2.

The README.TASKING says:

"The FSU threads provide a completely accurate implementation of
Annex D requirements, and operating with FSU threads, as far as we
know"


"On Linux the default is the fsu runtime and is selected by the means of soft
links."

Running a small program that creates 2 tasks, each going in 
an infinite loop printing (I/O) message, shows that only
one task gets the chance to run, while the other is blocked
waiting for the other one to yield explicitly? This must
be because the default threads used are FSU (user level?) and 
not the native (kernel level) threads. 

Switching to using native Linux threads intead of FSU as explained 
in the above GNAT document, then now I see that each task  will 
run for some small time, and they will flip/flop between each 
others as expected, i.e. each running in turn.

So, my questions are:

1. How could FSU be an Annex D compliant, if one thread will block
the other like this? (even though one will expect that doing
an IO message will cause a task to yield the CPU). Does Annex D
not have some sort of "quantum" based scheduling? since both
tasks are of equal priority, one will expect that one task will 
run out of its quantum, and the next ready task to become
compute, no? (I really need to study AnnexD too :)

Since the native threads seem to give the behavior one would
expect, wouldn't make more sense that this become the
default when gnat is installed on Linux, and not the FSU one.

thanks,
Nasser

 -- with FSU threads (Annex D), this
-- program prints only "i" or "j" messages
-- meaning only one task runs.
-- but with native threads, both "i" and "j"
-- print, i.e. both tasks run in turn.
-- gnat 3.11p on Linux.

with Ada.Text_Io; use Ada.Text_Io;
procedure Test_Task is
      I : Integer :=0;
      j : Integer :=0;


      task type T1;
      task type T2;

      task body T1 is
      begin
            loop
                I := I+1;
                Put_Line("i=" & Integer'Image(I));
            end loop;
      end T1;

      task body T2 is
      begin
            loop
                j := j+1;
                Put_Line("j=" & Integer'Image(j));
            end loop;
      end T2;

      Task1: T1;
      Task2 : T2;
begin
      null;
end Test_Task;

Re: tasking in Ada and Annex D question

[Dr. Hubert B. Keller]

> Does Annex D
> not have some sort of "quantum" based scheduling? since both
> tasks are of equal priority, one will expect that one task will
> run out of its quantum, and the next ready task to become
> compute, no? (I really need to study AnnexD too :)

This mean Round Robin as a fair scheduling algorithm.

The showed behavior seems correct if having 2 tasks with same priority
and no delay. Using a delay of 0 results in preempting the task actually running
and
requeueing it at the tail of the queue and processing the next one.
Wether round robin is available or not depends on the implementation.
(See pragma dispatching_policy)

H.K.

Re: tasking in Ada and Annex D question

[robert_dewar]

In article <793jl9$hf@drn.newsguy.com>,
  nabbasi@earthlink.net wrote:

> 1. How could FSU be an Annex D compliant, if one thread
> will block the other like this? (even though one will
> expect that doing an IO message will cause a task to
> yield the CPU).

Annex D requires run till blocked semantics, and forbids
any kind of time slicing.

You say that you "expect" that doing an IO message will
cause a task to yield the CPU.

You can expect anything you like, but you read no such
requirement in the RM, because there is no such
requirement!

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: tasking in Ada and Annex D question

[Markus Kuhn]

In nabbasi@earthlink.net writes:
|> Since the native threads seem to give the behavior one would
|> expect, wouldn't make more sense that this become the
|> default when gnat is installed on Linux, and not the FSU one.

The Ada for Linux team people have recently discussed this and
decided to standardize on the native threads and to try and fix
the kernel to achieve Annex D compliance with the native linuxthreads.
Supporting both thread libraries would lead to a real maintenance
hazzle, because all precompiled shared libraries provided on top
of the GNAT RTS would have to be provided twice, once for linuxthreads
and once for FSU. The FSU threads are primarily there to achieve
formal Annex D compliance, which you can't currently do with
linuxthreads, and they are otherwise of very little practical
interest. They provide no concurrency when system calls block,
and they provide no parallelism on multiprocessor machines,
while the native linuxthreads do offer all this.

Markus

-- 
Markus G. Kuhn, Computer Laboratory, University of Cambridge, UK
Email: mkuhn at acm.org,  WWW: <http://www.cl.cam.ac.uk/~mgk25/>

Re: tasking in Ada and Annex D question

[robert_dewar]

In article <796jj7$5s2$1@pegasus.csx.cam.ac.uk>,
  mgk25@cl.cam.ac.uk (Markus Kuhn) wrote:
> They provide no concurrency when system calls block,
> and they provide no parallelism on multiprocessor
> machines, while the native linuxthreads do offer all
> this.

The FSU threads need supporting for at least a while for
two reasons:

1. They are indeed the threads used for validation.

2. They may well be far more efficient, that is true on
many targets, did you experiment with this aspect. A lot
of people do not need concurrency with system calls (indeed
a properly written portable Ada program cannot rely on
such concurrency, since it is not guaranteed by the Ada
standard), and if FSU threads are more efficient, they
may be preferable for many real applications.

In an effort to use shared libraries, be careful not to
take away important functionality.

If experiments show that the efficiency gain is small (I
would suggest running the PIWG tests), then this is of
course not a factor.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: tasking in Ada and Annex D question

[Roger Racine]

In article <7963h1$a6h$1@nnrp1.dejanews.com> robert_dewar@my-dejanews.com writes:

>In article <793jl9$hf@drn.newsguy.com>,
>  nabbasi@earthlink.net wrote:

>> 1. How could FSU be an Annex D compliant, if one thread
>> will block the other like this? (even though one will
>> expect that doing an IO message will cause a task to
>> yield the CPU).

>Annex D requires run till blocked semantics, and forbids
>any kind of time slicing.

>You say that you "expect" that doing an IO message will
>cause a task to yield the CPU.

>You can expect anything you like, but you read no such
>requirement in the RM, because there is no such
>requirement!

In the Ada 95 Rationale, the last paragraph of section D.2.1 states:

" Another anticipated application requirement is for time slicing.  
Implementation-defined time-slicing schemes may conform to this specification 
by modifying the active or base priority of a task, in a fashion similar to 
that outlined for EDF scheduling."

I re-read the Annex and can find nothing to support your contention that it 
requires run till blocked semantics, with your definition of "blocked".  It 
seems that "task dispatching points" are completely implementation defined 
(D.2.2.18).

I am in agreement with those who want tasks to block on I/O calls.  An I/O 
call must be considered a dispatching point, IMHO.

Roger Racine

Re: tasking in Ada and Annex D question

[robert_dewar]

In article <rracine.8.0008248D@draper.com>,
  rracine@draper.com (Roger Racine) wrote:
> In article <7963h1$a6h$1@nnrp1.dejanews.com>
robert_dewar@my-dejanews.com writes:
> I re-read the Annex and can find nothing to support your
> contention that it requires run till blocked semantics,
> with your definition of "blocked".  It seems that "task
> dispatching points" are completely implementation defined
> (D.2.2.18).

Well I am of course talking about
FIFO_Within_Priorities. If you don't specify
the dispatching policy, then of course it is
undefined.

But FWP is the only defined policy in the RM,
and it most definitely requires run till blocked
(and whether IO is blocking or not is of course
implementation defined).

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: tasking in Ada and Annex D question

[Markus Kuhn]

In robert_dewar@my-dejanews.com writes:
|> The FSU threads need supporting for at least a while for
|> two reasons:
|> 
|> [...]
|> 2. They may well be far more efficient, that is true on
|> many targets, did you experiment with this aspect. A lot
|> of people do not need concurrency with system calls (indeed
|> a properly written portable Ada program cannot rely on
|> such concurrency, since it is not guaranteed by the Ada
|> standard), and if FSU threads are more efficient, they
|> may be preferable for many real applications.

What I have a bit of a problem to understand is, for what
else apart from preemptive scheduling, concurrency when system
calls block, and utilization of multiprocessor systems do I
need tasks for (i.e., all the things FSU doesn't do)? I realize
that tasks were the only real synchronization mechanism in Ada83,
but we now have protected objects to do this more efficiently
without context switches. So I believe that in Ada95, the
concurrency of tasks is much more important than the performance
of task switches, because tasks are not used that much any more
for time-consuming synchronization (reader/writer buffer tasks,
semaphore tasks, etc.).

Neat would however be a mechanism that combines native linuxthreads
and FSU into a common mechanism. Groups of Ada tasks could be
assigned to a single linux thread. FSU is used to manage the
tasks *within* one linuxthread, and the Linux kernel switches
between these groups of tasks using linuxthreads. Then you can
fine-tune the performance versus concurrency tradeoffs with a
few pragmas. I don't think it is urgent, but it would be rather
neat. Does this sound like a plan for the future to think about?

Markus

-- 
Markus G. Kuhn, Computer Laboratory, University of Cambridge, UK
Email: mkuhn at acm.org,  WWW: <http://www.cl.cam.ac.uk/~mgk25/>

Re: tasking in Ada and Annex D question

[Niklas Holsti]

Markus Kuhn wrote:
> 
> In robert_dewar@my-dejanews.com writes:
> |> The FSU threads need supporting for at least a while for
> |> two reasons:
> |>
> |> [...]
> |> 2. They may well be far more efficient, that is true on
> |> many targets, did you experiment with this aspect. A lot
> |> of people do not need concurrency with system calls (indeed
> |> a properly written portable Ada program cannot rely on
> |> such concurrency, since it is not guaranteed by the Ada
> |> standard), and if FSU threads are more efficient, they
> |> may be preferable for many real applications.
> 
> What I have a bit of a problem to understand is, for what
> else apart from preemptive scheduling, concurrency when system
> calls block, and utilization of multiprocessor systems do I
> need tasks for (i.e., all the things FSU doesn't do)?

You need tasks to modularise your program's NON-synchronised
(i.e. logically concurrent) functions, while programming each
such function in an easy-to-understand sequential manner.

I do agree that for most Linux applications I can imagine, barring
really embedded stuff, the properties of native Linux threads
seem more suitable, especially for the system calls.

> I realize
> that tasks were the only real synchronization mechanism in Ada83,

For me the chief attribute of tasks is that they are logically
concurrent, not that they occasionally synchronise.

> but we now have protected objects to do this more efficiently
> without context switches. So I believe that in Ada95, the
> concurrency of tasks is much more important than the performance
> of task switches,

IMHO this was also the case in Ada 83 and all other multi-tasking
systems, too.

I don't have an opinion on which threads package to adopt for
GNAT on Linux, but wanted to butt in with the above.

- Niklas

Re: tasking in Ada and Annex D question

[Ehud Lamm]

On Tue, 2 Feb 1999, Niklas Holsti wrote:

> Markus Kuhn wrote:
> > 
> > 
> > What I have a bit of a problem to understand is, for what
> > else apart from preemptive scheduling, concurrency when system
> > calls block, and utilization of multiprocessor systems do I
> > need tasks for (i.e., all the things FSU doesn't do)?
> 
> You need tasks to modularise your program's NON-synchronised
> (i.e. logically concurrent) functions, while programming each
> such function in an easy-to-understand sequential manner.
> 

I ask my students to write a simulation of some grazing animals, predators
and grass, all having different behaviours, and interactions when the meet
(grass is eaten when it meets a hungry cow. Same things happens to the cow
if the lion is hungry :-) etc.)

I urged them to think of coding this sequentially. They usually see the
point. It is harder to coceptualized this using tasks.

Tasks are part of the tools to abstract the control structure.

Ehud Lamm     mslamm@pluto.mscc.huji.ac.il

Re: tasking in Ada and Annex D question

[Tom Moran]

>I am in agreement with those who want tasks to block on I/O calls.  An I/O 
>call must be considered a dispatching point, IMHO.
Even a read from an already-in-memory buffer, or a write to a
delayed-write cache?  Or a rewind request issued to a tape drive?  Do
you want Sequential_IO.Read to implicitly include a dispatching point
before doing any physical read, or before returning to the calling
program, or what?  And why make others use such a routine when you can
write your own IO wrapper that includes a dispatching point?

Re: tasking in Ada and Annex D question

[robert_dewar]

In article <797m6h$73g$2@pegasus.csx.cam.ac.uk>,
  mgk25@cl.cam.ac.uk (Markus Kuhn) wrote:
> What I have a bit of a problem to understand is, for what
> else apart from preemptive scheduling, concurrency when
> system calls block, and utilization of multiprocessor
> systems do I need tasks for (i.e., all the things FSU
> doesn't do)?

My goodness! A surprising question. Multi-threading is
a very fundamental programming paradigm for all sorts of
situations. Endless examples are at hand, but here's just
one, a radar tracking program where each trace is a
separate task. Such applications may not even do any
system calls! There are lots of large scale applications
using Ada tasks which don't care two hoots about system
calls. Note as an example that many of the Ada 83 compilers
in which tasking was used heavily did their own scheduling
within a single process in Unix (or DOS!)

The mapping of tasks into OS threads is a relatively new
development. It is useful for certain kinds of system
programming, but there is a very high efficiency penalty
to be paid for this approach, a penalty which many (most?)
applications do not need to pay.

P.S. of course FSU threads provides preemptive scheduling,
this is required by the RM semantics!

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: tasking in Ada and Annex D question

[Nick Roberts]

To quote chapter and verse, RM95 D.2.2 [7] states

... The language defines only one dispatching policy,
FIFO_Within_Priorities; when this policy is in effect, modifications to the
ready queues occur only as follows ...

with the emphasis on "only", the list that follows this clause does not
include any timed pre-emption.

It does, however, include the 'delay' statement, so (as another poster
mentioned, I think), if you pop in a 'delay 0.0;' statement just after (say)
the I/O operation, you'll get a nice alternation of task activation.

-------------------------------------------
Nick Roberts
-------------------------------------------

robert_dewar@my-dejanews.com wrote in message
<797hoc$j3v$1@nnrp1.dejanews.com>...
[...]
|Well I am of course talking about
|FIFO_Within_Priorities. If you don't specify
|the dispatching policy, then of course it is
|undefined.
|
|But FWP is the only defined policy in the RM,
|and it most definitely requires run till blocked
|(and whether IO is blocking or not is of course
|implementation defined).

Re: tasking in Ada and Annex D question

[Frank Mueller]

OK as the author of FSU Pthreads and one of the programmers of
the Gnat Runtime Library GNARL, let me add my $0.02 but commenting
on a few statements made in this thread:

>> 1. How could FSU be an Annex D compliant, if one thread
>> will block the other like this? (even though one will
>> expect that doing an IO message will cause a task to
>> yield the CPU).

FSU Pthreads includes rewrites for certain system calls to avoid
blocking the entire process, e.g. read(), write(), accept()
Thus, there is a minimum of thread-only blocking semantics for
the most important I/O calls.

>... The language defines only one dispatching policy,
>FIFO_Within_Priorities; when this policy is in effect, modifications to the
>ready queues occur only as follows ...

POSIX Threads support for validating an Ada95 compiler includes the LRM as
well as the Annexes. The latter include the real-time annex, and here you
need protocols such as priority inheritance and priority ceiling. The real-time
annex also supports an interrupt model tied to UNIX signals. FSU Pthreads supports
both.

FSU Pthreads also uses strict priority scheduling on either a FIFO hand-off
within equal priorities or, alternately, round-robin within equal priority. And
it is preemptive.

FSU Pthreads has (almost) full support for signals following the POSIX standard (it partly
monopolizes IO and ALRM signals).
Linuxthreads does not follow the POSIX standard for signal delivery (a design problem,
not easy to fix) und monopolizes the USR/USR1 signals.

>Neat would however be a mechanism that combines native linuxthreads
>and FSU into a common mechanism. Groups of Ada tasks could be
>assigned to a single linux thread. FSU is used to manage the
>tasks *within* one linuxthread, and the Linux kernel switches
>between these groups of tasks using linuxthreads. Then you can
>fine-tune the performance versus concurrency tradeoffs with a
>few pragmas. I don't think it is urgent, but it would be rather
>neat. Does this sound like a plan for the future to think about?

I agree 100%, I had this in mind for a while. I recently found a
student who will work on this. The idea is to combine FSU Pthreads
(user-level lib) and Linuxthreads (kernel threads) into something
like to two-layer Solaris model (Solaris threads as lib, LWPs in
the kernel). Maybe we can also fix the signal semantics of Linuxthreads
in the course. The goal was to cope without modifications of the 
Linux kernel. Let's see if it can be done since there are some
problems with this.

In any case, I think everybody would like to see the speed of FSU Pthreads
be combined with the support for thread-only blocking calls (to the kernel
and libraries) and, most of all, support for multiprocessors.
-- 
Frank Mueller   E-Mail: mueller@informatik.hu-berlin.de   WWW: http://www.informatik.hu-berlin.de/~mueller

Re: tasking in Ada and Annex D question

[Frank Mueller]

OK, one more comment:

>So I believe that in Ada95, the
>concurrency of tasks is much more important than the performance
>of task switches, because tasks are not used that much any more
>for time-consuming synchronization (reader/writer buffer tasks,
>semaphore tasks, etc.).

Well, think again. If you have as many processors as tasks *and* you
use protected functions/procedures only *and* your system supports
multiprocessing (kernel threads), you may be right.

In most realistic case, and any time you use protected entries, you
wrong, IMHO. Your tasks will context switch upon synchronization.
And the context switching time will have an impact on the performance.

For more details, read our SigAda'98 paper:

"The Rendezvous is Dead -- Long Live the Protected Object" by D. Macos and F.
     Mueller in ACM SIGAda'98, Nov 1998, pages 287-293,38 

available as postscript on

http://www.informatik.hu-berlin.de/~mueller/publications.html

The punch line: The rendezvous may not be completely dead but protected objects
are preferable where they can be used (and the paper says exactly where).
-- 
Frank Mueller   E-Mail: mueller@informatik.hu-berlin.de   WWW: http://www.informatik.hu-berlin.de/~mueller

Re: tasking in Ada and Annex D question

[Roger Racine]

In article <798u7r$b2k$2@plug.news.pipex.net> "Nick Roberts" <Nick.Roberts@dial.pipex.com> writes:

>To quote chapter and verse, RM95 D.2.2 [7] states

>... The language defines only one dispatching policy,
>FIFO_Within_Priorities; when this policy is in effect, modifications to the
>ready queues occur only as follows ...

>with the emphasis on "only", the list that follows this clause does not
>include any timed pre-emption.

>It does, however, include the 'delay' statement, so (as another poster
>mentioned, I think), if you pop in a 'delay 0.0;' statement just after (say)
>the I/O operation, you'll get a nice alternation of task activation.

>-------------------------------------------
>Nick Roberts
>-------------------------------------------

>robert_dewar@my-dejanews.com wrote in message
><797hoc$j3v$1@nnrp1.dejanews.com>...
>[...]
>|Well I am of course talking about
>|FIFO_Within_Priorities. If you don't specify
>|the dispatching policy, then of course it is
>|undefined.
>|
>|But FWP is the only defined policy in the RM,
>|and it most definitely requires run till blocked
>|(and whether IO is blocking or not is of course
>|implementation defined).

If you were to have put in the list, it includes the following:

"*  When the active priority of a ready task that is not running changes . . ."

The Ada 95 Rationale (section D.2.2) is very clear on the distinction between 
"dispatching policy" and "scheduling policy".  The former "is used here to 
denote the action of choosing a task to execute on a processor at a particular 
instant, given that one already knows the set of tasks that are eligible for 
execution on that processor at that instant, and their priorities."

"task scheduling"  "includes determination of the other factors, i.e. which 
tasks are eligible to execute . . . and what is the active priority of each 
task."

Then at the end of the section, there is the statement "Another anticipated 
application requirement is for time slicing.  Implementation-defined 
time-slicing schemes may conform to this specification by modifying the active 
or base priority of a task . . .".

Even if you do not agree with the Rationale then the question becomes, how 
many people use "pragma Task_Dispatching_Policy" anyway?  Of course the answer 
is "the ACVC tests" use it.  My guess is that no users do.

Roger Racine