Re: Advantages

Re: Advantages

[Peter Amey]

Andrew Carroll wrote:
[snip]
> 
>>Quite a lot of the really nasty pitfalls associated with parallel
>>programming in other languages are made either impossible or much more
>>easily detected and debugged by Ada.
> 
> 
> Okay Marin and Nick, I want to learn more.  Where can I find the
> statistical and practical proof?  I'm not trying to snub your comments,
> I just want to be able to provide the proof when I talk to my co-workers
> about Ada.  Thanks!
> 
> 

Not Marin or Nick but unsolicited 2c anyway.

You could take a look at the Ravenscar profile.  This is a subset of Ada 
95's built-in tasking constructs that guarantees schedulability analysis 
and freedom from deadlocks.  Using SPARK in conjunction with this allows 
lots of other nice properties to be proved as well.  Ravenscar is 
interesting because it is existential proof that Ada facilitates 
reliable use of concurrency.  I don't know of any equivalent in any 
other language.  Flight critical software to DO-178B level A has been 
written using these Ada tasking constructs.  The profile will be a 
defined part of the Ada language after the current 2005 revision process.

Some references:
Pofile definition:  <http://polaris.dit.upm.es/~ork/documents/RP_spec.pdf>
Crosstalk article:
<http://www.stsc.hill.af.mil/crosstalk/2003/11/0311dobbing.html>
Aonix Raven link:
<http://www.aonix.com/pdf/ravensc.pdf>
RavenSPARK link:
<http://www.praxis-cs.co.uk/sparkada/pdfs/high_integrity_ravenscar.pdf>

Peter

Advantages

[Andrew Carroll]

> ------------------------------
> Message: 6
> From: "Nick Roberts" <nick.roberts@acm.org>
> Subject: Improving Ada's Image
>
> "Marin David Condic" <nobody@noplace.com> wrote in message
> news:40CEDEBB.3050209@noplace.com...
>
> > Like I said: The thing that makes operating systems hard to
> > get right are not usually language issues. They are related to
> > the asynchronicity of events and the complexity of the
> > algorithms involved.
>
> This is one of the biggest advantages of writing system software in
Ada.
> Quite a lot of the really nasty pitfalls associated with parallel
> programming in other languages are made either impossible or much more
> easily detected and debugged by Ada.

Okay Marin and Nick, I want to learn more.  Where can I find the
statistical and practical proof?  I'm not trying to snub your comments,
I just want to be able to provide the proof when I talk to my co-workers
about Ada.  Thanks!

Advantages

[Andrew Carroll]

Ehhhh, someone sent me an email with an attachment regarding my post
titled "Advantages".  I inadvertently deleted it.  Please send it again
thanks.


Andrew Carroll
Carroll-Tech
720-273-6814
andrew@carroll-tech.net

Advantages

[Andrew Carroll]

Jim, Good article.  Thank you.

So an Ada task can get out of being blocked?
"...A task may remove itself from an entry queue whenever it needs
to..." (Java Threads: A Faulty Concurrency Model)

Andrew Carroll
Carroll-Tech
720-273-6814
andrew@carroll-tech.net

Re: Advantages

[Marin David Condic]

I'm not sure what you want for statistical proof. In my experience with 
writing low-level software in an environment where I don't have an OS, I 
can say that the things that tend to cause the most difficult problems 
are where the software meets the hardware. Try to get two different CPUs 
synchronized across some communication link or deal with some I/O device 
where timing or synchronization are important to getting it right. Or 
sometimes its within the CPU instruction set itself - where arguments 
start about hardware vs software bugs. The *hard* stuff to get right is 
not related to bugs in type checking or constraint checking (or other 
language related stuff). Its the uncertainty of when things are 
happening or the fact that dozens of things are happening nearly all at 
once and corner conditions can come up that are difficult to test and 
difficult to program around.

Tasking may help, but that is only built on the assumption that your 
tasking primitives down at the low level have no bugs. Try figuring out 
how to synchronize tasks across multiple processors and implement the 
full set of Ada requirements in that regard and it might give you an 
idea of how difficult that might be to get right.

So I don't think that Ada automagically makes an OS "better" in some 
regard. Its going to have more to do with how sound the "Model" is for 
the lower level stuff - and even then, as you pile more and more layers 
on top ofit, you start discovering the limitations or design flaws in 
the model. I'm not saying someone can't do a better job with Ada - just 
that an OS is *really hard* to make stable and secure and it isn't 
something that can be done in a few weekends of coding and hope it will 
somehow be better.

MDC

Andrew Carroll wrote:
>>------------------------------
>>Message: 6
>>From: "Nick Roberts" <nick.roberts@acm.org>
>>Subject: Improving Ada's Image
>>
>>"Marin David Condic" <nobody@noplace.com> wrote in message
>>news:40CEDEBB.3050209@noplace.com...
>>
>>
>>>Like I said: The thing that makes operating systems hard to
>>>get right are not usually language issues. They are related to
>>>the asynchronicity of events and the complexity of the
>>>algorithms involved.
>>
>>This is one of the biggest advantages of writing system software in
> 
> Ada.
> 
>>Quite a lot of the really nasty pitfalls associated with parallel
>>programming in other languages are made either impossible or much more
>>easily detected and debugged by Ada.
> 
> 
> Okay Marin and Nick, I want to learn more.  Where can I find the
> statistical and practical proof?  I'm not trying to snub your comments,
> I just want to be able to provide the proof when I talk to my co-workers
> about Ada.  Thanks!
> 
> 


-- 
======================================================================
Marin David Condic
I work for: http://www.belcan.com/
My project is: http://www.jsf.mil/NSFrames.htm

Send Replies To: m   o   d   c @ a   m   o   g
                    c   n   i       c   .   r

     "Face it ladies, its not the dress that makes you look fat.
     Its the FAT that makes you look fat."

         --  Al Bundy

======================================================================

Advantages

[Andrew Carroll]

> ------------------------------
> Message: 5
> From: Marin David Condic <nobody@noplace.com>
> Subject: Re: Advantages
>
> I'm not sure what you want for statistical proof. In my experience
with
> writing low-level software in an environment where I don't have an OS,
I
[snip]

I don't doubt anything that you said.  You are more experienced with it
than I am!  I'm sure, as I know and you said, MANY of the answers I seek
can really only be obtained from experience.  If I asked "what features
of Ada provide the biggest advantages to writing system software?"  what
would you say?  So far two people mentioned the tasking features of Ada.
Great, I trust you!  What features of Ada make it easier to detect
pitfalls in parallel programming?  What features of Ada help with
debugging?

Have any tests been done to show that Ada tasking features are better
that other languages' "tasking" features if the model is the same?  If
so, where are the results?  How much better were the Ada tasking
features?

> Try to get two different CPUs synchronized across some communication
link or deal with some I/O device where timing or synchronization are
important to
> getting it right.
So if I did try, what features of Ada are going to help me?

> Its the uncertainty of when things are happening or the fact that
dozens of things are happening nearly all at once and corner conditions
can come up that are
> difficult to test and difficult to program around.
So your saying that the real time features of Ada help to remove the
"race condition" uncertainty and deal with corner conditions?

> I'm not saying someone can't do a better job with Ada - just that an
OS is *really hard* to make stable and secure and it isn't something
that can be done in a
> few weekends of coding and hope it will somehow be better.
What features of Ada help to make an OS stable and secure?  Bounds
checking?  Typing?  Rendezvous?  Protected Objects?

Andrew

Re: Advantages

[Nick Roberts]

"Andrew Carroll" <andrew@carroll-tech.net> wrote in message
news:mailman.165.1088318818.391.comp.lang.ada@ada-france.org...

> ... What features of Ada make it easier to detect pitfalls
> in parallel programming?  What features of Ada help with
> debugging?

I don't wish to cross with Marin in answering this, but forgive me if I
throw my oar in a bit.

Suppose I have two threads (another name for 'tasks') which both need to
read a variable (which is a struct (record)) from time to time, and one of
them also updates the variable from time to time. When an update is done, it
involves assigning values to several of the variable's members (components),
so the update is not 'atomic'. This means that there needs to be some kind
of synchronisation between the threads, to prevent one thread trying to read
the variable right in the middle of it being updated.

In most programming languages, including C for example, under a typical
execution environment or OS, the usual or only way to do this will be by the
explicit use of semaphores (or a similar facility). When a thread wants to
read or update the variable, it sets the semaphore (which may cause it to
wait (to be 'blocked')). When it has finished, it resets the semaphore
(which may unblock another waiting thread). Let's say the function to set a
semaphore is named 'sem_p', and the function to reset it is 'sem_v'. If the
variable is named 'r' (and has members 'x' and 'y') and the semaphore is
named 's', a C program might contain code like this:

   /* Thread A */
   ...
   sem_p(s); /* set the semaphore, maybe wait */
   x = r.x; y = r.y; /* read the variable */
   sem_v(s); /* reset the semaphore */
   ...

   /* Thread B */
   ...
   sem_p(s); /* set the semaphore, maybe wait */
   r.x = x; r.y = y; /* update the variable */
   sem_v(s); /* reset the semaphore */
   ...

This is all well and dandy, but there are many things that can go wrong. For
example, supposing a programmer accidentally omitted one of the calls to
sem_p or sem_v? Or accidentally used the wrong semaphore in one of the
calls? This kind of mistake is easily done in a big, complex program with
lots of threads and semaphores. The consequences are often hard to debug: it
is typical that a problem is only manifested intermittently; it is typical
that using a debugger (single stepping or breakpoint jumping) destroys the
temporal circumstances of normal execution that are needed to observe the
problem at all; it is typical that, even when the problem is observed, the
cause is subtle and very hard to determine.

In Ada 95, you would typically use a protected object to protect the
variable from unwanted parallel access. (In Ada 83 you would typically have
used a task and a 'rendezvous', but I'll illustrate the protected object
approach here.)

   type R_Type is
      record
         X, Y: Float;
         ...
      end record;

   protected Prot_R is
      function Get return R_Type;
      procedure Set (New_R: in R_Type);
   private
      Inner_R: R_Type;
   end;

   protected body Prot_R is

      function Get return R_Type is
      begin
         return Inner_R;
      end;

      procedure Set (New_R: in R_Type) is
      begin
         Inner_R := New_R;
      end;

   end Prot_R;

   ...
   --- in task A
   declare
      Local_R: R_Type;
   begin
      Local_R := Prot_R.Get; -- read variable
      X := Local_R.X;
      Y := Local_R.Y;


   ...
   --- in task B
   Prot_R.Set((X,Y,...)); -- update variable

Because the use of OS primitives such as semaphores is hidden from the user
by Ada, many of the mistakes that would be easy to make in the C code are
either impossible -- for example, we cannot omit a call to set or reset a
semaphore, since Ada does these for us invisibly -- or caught by the
compiler and reported to us in an obvious way -- for example, if we tried to
use 'Inner_R' in an expression in task A or B, the compiler would complain
that Inner_R is not visible at that point (because it is private to Prot_R).

Obviously this example is simplistic compared to real software, but I hope
it gives a flavour of Ada's advantages in concurrent programming.

You might like to note that the use of an Ada protected object gives further
advantages than I have mentioned so far. It is implemented in such a way
that functions are permitted to be parallel with one another (but not with
any procedure). So, tasks A and B would be permitted to read Prot_R
simultaneously, but no task would be allowed to read it while another was in
the middle of setting it. Protected objects can provide yet more
sophisticated functionality (with 'entries'). And then there are tasks,
rendezvouses, and various other facilities too. All of this functionality
can be achieved in other languages, but generally only at a lower and more
error-prone level.

Really, one could write a big book about concurrent programming in Ada.
Hehe, in fact I'm sure somebody has! I'm sorry, I can't recall the details,
but I'm sure someone else will oblige.

-- 
Nick Roberts

Re: Advantages

[Jim Rogers]

"Andrew Carroll" <andrew@carroll-tech.net> wrote in 
news:mailman.165.1088318818.391.comp.lang.ada@ada-france.org:

> Have any tests been done to show that Ada tasking features are better
> that other languages' "tasking" features if the model is the same?  If
> so, where are the results?  How much better were the Ada tasking
> features?

Ada concurrency features are generally at a higher abstraction level than
for other languages. The higher abstraction level has many benefits.
The higher abstraction level allows a particular target implementation to
be transparent to the Ada programmer, providing a high level of source
code portability. In languages such as C or C++ you must choose the
appropriate low level threading library, such as pthreads or winthreads.
The Ada concurrency model includes some very sophisticated concepts such
as read/write locks, monitors, condition variables, queued calls 
involving condition variables, programmer-defined queuing policies,
and conditional suspension of calls waiting in a queue (under the
control of the calling task).

All these features can be implemented using the threading facilities
of an underlying OS, or they can be implemented without an OS. The 
difference to the programmer is his choice of a compiler. Some Ada
compilers are specifically designed to produce code for a specific
OS while others are designed to produce code for bare hardware, with
no underlying OS.

>> I'm not saying someone can't do a better job with Ada - just that an
> OS is *really hard* to make stable and secure and it isn't something
> that can be done in a
>> few weekends of coding and hope it will somehow be better.
> What features of Ada help to make an OS stable and secure?  Bounds
> checking?  Typing?  Rendezvous?  Protected Objects?

All of those are tools that help the OS designer. They help because
each resolves several areas of uncertainty in implemented and executing
code.

Jim Rogers

Re: Advantages

[Pascal Obry]

"Nick Roberts" <nick.roberts@acm.org> writes:

> Really, one could write a big book about concurrent programming in Ada.
> Hehe, in fact I'm sure somebody has! I'm sorry, I can't recall the details,
> but I'm sure someone else will oblige.

Concurrency in Ada. Alan Burns and Andy Wellings. 
Cambridge University Press
ISBN 0-521-41471-7

The best book on concurrent programming I would say.

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.org
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: Advantages

[Robert I. Eachus]

Nick Roberts wrote:
> "Andrew Carroll" <andrew@carroll-tech.net> wrote in message
> news:mailman.165.1088318818.391.comp.lang.ada@ada-france.org...
> 
>>... What features of Ada make it easier to detect pitfalls
>>in parallel programming?  What features of Ada help with
>>debugging?
> 
> 
> I don't wish to cross with Marin in answering this, but forgive me if I
> throw my oar in a bit.
> 
> Suppose I have two threads (another name for 'tasks') which both need to
> read a variable (which is a struct (record)) from time to time, and one of
> them also updates the variable from time to time. When an update is done, it
> involves assigning values to several of the variable's members (components),
> so the update is not 'atomic'. This means that there needs to be some kind
> of synchronisation between the threads, to prevent one thread trying to read
> the variable right in the middle of it being updated.

Nick's example is a good one, but it misses a part of the flavor of why 
it is such a huge advantage.  If you know you are going to have to 
protect some object, you declare it as a protected object (makes sense 
;-) with a Get function and a Set procedure.  As the design and software 
development process proceeds, you may have to change the management of R 
dozens of times.  But all these changes are local to the protected 
object that implements R.

If as often happens in a system design, you need to hold two or more 
locks at once, you need to prevent the possibility deadlock.  (Or you 
should prevent the possibility of deadlock.)  One way to do this is to 
show that there is an ordering of all of the semaphores such that no 
task holds a higher numbered semaphore when it acquires a lower numbered 
semaphore.

In Ada, if all these semaphores are actually internal to protected 
objects, the only way to hold R while acquiring S is for the protected 
object for R to have a call which internally calls the protected object 
for S.  This is not hard to write in Ada, but the implicit ordering of 
with clauses will make it impossible for you to have a call that gets S 
while holding R, another call that gets T while holding S, and a third 
call that gets R while holding T.  For that matter any matter any 
calling sequence that violates the rule will mean that the compiler will 
reject the program.  So you can design, build and maintain complex 
real-time systems with many threads of control in Ada, and not only will 
there be no deadlocks, you won't have to do lots of analysis to show 
that the software is deadlock free.  (Yes, you can put two protected 
objects in the same scope and violate the implicit ordering.  But now 
the only source of potential deadlocks is in that one unit--that I hope 
violates your software development plan in some way.)

-- 

                                           Robert I. Eachus

"Reason and experience both forbid us to expect that national morality 
can prevail in exclusion of religious principles." -- George Washington

Re: Advantages

[Brian May]

>>>>> "Robert" == Robert I Eachus <rieachus@comcast.net> writes:

    Robert> In Ada, if all these semaphores are actually internal to
    Robert> protected objects, the only way to hold R while acquiring
    Robert> S is for the protected object for R to have a call which
    Robert> internally calls the protected object for S.  This is not
    Robert> hard to write in Ada, but the implicit ordering of with
    Robert> clauses will make it impossible for you to have a call
    Robert> that gets S while holding R, another call that gets T
    Robert> while holding S, and a third call that gets R while
    Robert> holding T.  For that matter any matter any calling
    Robert> sequence that violates the rule will mean that the
    Robert> compiler will reject the program.  So you can design,
    Robert> build and maintain complex real-time systems with many
    Robert> threads of control in Ada, and not only will there be no
    Robert> deadlocks, you won't have to do lots of analysis to show
    Robert> that the software is deadlock free.  (Yes, you can put two
    Robert> protected objects in the same scope and violate the
    Robert> implicit ordering.  But now the only source of potential
    Robert> deadlocks is in that one unit--that I hope violates your
    Robert> software development plan in some way.)

I am assuming here that two protected objects in two different
packages (units?) don't lie in "the same scope". I hope I haven't
misunderstood you.

The implication of what you say is you can't have a deadlock in Ada
across different packages, that will compile, if you use protected
objects in this manner to access variables

Not true!

-- cut --
package types is

    type R_Type is
    record
        X, Y: Float;
    end record;

end types;
-- cut --

-- cut --
with Types;

package alpha is

   protected Prot_R is
      function Get return Types.R_Type;
      function Get_Deadlock return Types.R_Type;
      procedure Set (New_R: in Types.R_Type);
   private
      Inner_R: Types.R_Type;
   end;

end alpha;
-- cut --


-- cut --
with Ada.Text_IO;
with beta;

package body alpha is

   protected body Prot_R is

      function Get return Types.R_Type is
      begin
         Ada.Text_IO.Put_Line("Got      Alpha 1");
         Ada.Text_IO.Put_Line("Released Alpha 1");
         return Inner_R;
      end;

      function Get_Deadlock return Types.R_Type is
        Temp : Types.R_Type;
      begin
         Ada.Text_IO.Put_Line("Got      Alpha 2");
         delay 5.0;
         Ada.Text_IO.Put_Line("Trying   Beta");
         Temp := beta.Prot_R.get;
         Ada.Text_IO.Put_Line("Released Alpha 2");
         return Temp;
      end;

      procedure Set (New_R: in Types.R_Type) is
      begin
         Inner_R := New_R;
      end;

   end Prot_R;

end alpha;
-- cut --


-- cut --
with types;

package beta is

   protected Prot_R is
      function Get return Types.R_Type;
      function Get_Deadlock return Types.R_Type;
      procedure Set (New_R: in Types.R_Type);
   private
      Inner_R: Types.R_Type;
   end;

end beta;
-- cut --

-- cut --
with Ada.Text_IO;
with Alpha;

package body beta is

   protected body Prot_R is

      function Get return Types.R_Type is
      begin
         Ada.Text_IO.Put_Line("Got      Beta 1");
         Ada.Text_IO.Put_Line("Released Beta 1");
         return Inner_R;
      end;

      function Get_Deadlock return Types.R_Type is
        Temp : Types.R_Type;
      begin
         Ada.Text_IO.Put_Line("Got      Beta 2");
         delay 5.0;
         Ada.Text_IO.Put_Line("Trying   Alpha");
         Temp := alpha.Prot_R.get;
         Ada.Text_IO.Put_Line("Released Beta 2");
         return Temp;
      end;

      procedure Set (New_R: in Types.R_Type) is
      begin
         Inner_R := New_R;
      end;

   end Prot_R;

end beta;
-- cut --

-- cut --
with Ada.Text_IO;
with Types;
with Alpha;
with Beta;

procedure deadlock is
        Local_R : Types.R_Type;

        task X is
                entry Start;
        end X;

        task body X is
                Task_R : Types.R_Type;
        begin
                accept Start;
                Ada.Text_IO.Put_Line("Task: trying beta");
                Task_R := Beta.Prot_R.Get_Deadlock;
                Ada.Text_IO.Put_Line("Task: stopping");
        end X;
begin
        Ada.Text_IO.Put_Line("Main starting");
        X.Start;
        Ada.Text_IO.Put_Line("main: trying alpha");
        Local_R := Alpha.Prot_R.Get_Deadlock;
        Ada.Text_IO.Put_Line("main: stopping");
end;
-- cut --

On my system produces:

-- cut --
Main starting
main: trying alpha
Got      Alpha 2
Task: trying beta
Got      Beta 2
Trying   Beta
Trying   Alpha
-- cut --

looks like deadlock to me... One task is trying to get beta, but can't
because the other task has it, this task is trying to get alpha but
can't because the first task has it.

Sure, contrived example, but I think it gets the point across. Also,
if you removed the delays it might sometimes work (if I got that
correct), depending on timing.

It is worth mentioning the compiler does warn you, at least for this
case:

-- cut --
>gnatmake deadlock
gnatgcc -c deadlock.adb
gnatgcc -c alpha.adb
alpha.adb:19:10: warning: potentially blocking operation in protected operation
gnatgcc -c beta.adb
beta.adb:19:10: warning: potentially blocking operation in protected operation
gnatbind -x deadlock.ali
gnatlink deadlock.ali
-- cut --

I would imagine that there are other cases where the compiler can't
warn you.
-- 
Brian May <bam@snoopy.apana.org.au>

Advantages

[Andrew Carroll]

> ------------------------------
> Message: 3
> From: "Nick Roberts" <nick.roberts@acm.org>
> Subject: Re: Advantages
>
[snip]
> Because the use of OS primitives such as semaphores is hidden from the
user
> by Ada, many of the mistakes that would be easy to make in the C code
are
> either impossible -- for example, we cannot omit a call to set or
reset a
> semaphore, since Ada does these for us invisibly -- or caught by the
> compiler and reported to us in an obvious way -- for example, if we
tried to
> use 'Inner_R' in an expression in task A or B, the compiler would
complain
> that Inner_R is not visible at that point (because it is private to
Prot_R).
>
[snip]
> --
> Nick Roberts
>

Ohhhhh, that IS a BIG plus!!  Two years ago I took an Operating Systems
course and we discussed semaphores but we only discussed it with respect
to the C programming language.  I understand all that you said.  Great
demonstration Thanks!!


> ------------------------------
> Message: 5
> From: Jim Rogers <jimmaureenrogers@worldnet.att.net>
> Subject: Re: Advantages
>
> Ada concurrency features are generally at a higher abstraction level
than
> for other languages. The higher abstraction level has many benefits.
> The higher abstraction level allows a particular target implementation
to
> be transparent to the Ada programmer, providing a high level of source
> code portability. In languages such as C or C++ you must choose the
> appropriate low level threading library, such as pthreads or
winthreads.
>
> The Ada concurrency model includes some very sophisticated concepts
such
> as read/write locks, monitors, condition variables, queued calls
> involving condition variables, programmer-defined queuing policies,
> and conditional suspension of calls waiting in a queue (under the
> control of the calling task).
>
> All these features can be implemented using the threading facilities
> of an underlying OS, or they can be implemented without an OS. The
> difference to the programmer is his choice of a compiler. Some Ada
> compilers are specifically designed to produce code for a specific
> OS while others are designed to produce code for bare hardware, with
> no underlying OS.
[snip]
>
> Jim Rogers
>
So you're saying that Ada moves as much of the target implementation
peculiarities to the compiler level to achieve the abstraction?
Would it be safe to say then that Ada in general depends heavily on the
compiler to catch implementation mistakes?


> ------------------------------
> Message: 9
> From: Pascal Obry <pascal@obry.org>
> Subject: Re: Advantages
>
> "Nick Roberts" <nick.roberts@acm.org> writes:
>
> > Really, one could write a big book about concurrent programming in
Ada.
> > Hehe, in fact I'm sure somebody has! I'm sorry, I can't recall the
details,
> > but I'm sure someone else will oblige.
>
> Concurrency in Ada. Alan Burns and Andy Wellings.
> Cambridge University Press
> ISBN 0-521-41471-7
>
> The best book on concurrent programming I would say.
>
> Pascal.
>
Thanks, I'll be looking this one up on Amazon.


> ------------------------------
> Message: 10
> From: "Robert I. Eachus" <rieachus@comcast.net>
> Subject: Re: Advantages
[snip]
> for S.  This is not hard to write in Ada, but the implicit ordering of
> with clauses will make it impossible ... any
> calling sequence that violates the rule will mean that the compiler
will
> reject the program.

VERY NICE!!  I'm guessing that Ada does this type of checking in general
and not just for the concurrency model?

>
>                                            Robert I. Eachus
>

I think you have shown me another side of Ada.  Or at least given me a
glimpse of another side of Ada.  It helps so much to have an example!!!
Do the new "limited with" and "synchronized" keywords discussed for
Ada200Y affect the information you have provided?

Thanks again!!!!

RE: Advantages

[Lionel.DRAGHI]

By the way, there was a presentation on a tool able to detect deadlock by
source code statical analysis, during the last Ada-France meeting.

The tool (still on developpement) is called Qasar, and was presented by JF.
Peyre.
Slides are available on the Ada-France web www.ada-france.org

-- 
Lionel Draghi.

Re: Advantages

[Marin David Condic]

Thats a reasonably good example. I'd note two things - 1) It only gets 
worse when you're interacting with other hardware or multiple processors 
and 2) Ada can't really help you when you're implementing the low level 
primitives that Ada uses to accomplish things like the semaphores you 
describe.

In case #1, you're dealing with a certain amount of asynchronicity and 
concurrency with what the hardware is doing and that is just simply 
beyond the scope of what Ada can address. In case #2, one hopes that if 
you get a good, solid model for handling all the primitive operations 
Ada needs, then the things you build upon it will be solid as well. In 
this way, Ada is a help. But you *still* have to get those low level 
primitives right and any errors in logic at that level will create 
instability in the OS.

That's why I say that getting a secure and reliable OS built is a 
difficult task and that Ada is no guarantee of success in that arena. 
All the primitives needed to do semaphores, rendesvous and multitasking 
in general are *complicated* and hard to get right. Ada doesn't help 
here because it must rely on those mechanisms being right before it can 
exist.

MDC


Nick Roberts wrote:
> "Andrew Carroll" <andrew@carroll-tech.net> wrote in message
> news:mailman.165.1088318818.391.comp.lang.ada@ada-france.org...
> 
> 
>>... What features of Ada make it easier to detect pitfalls
>>in parallel programming?  What features of Ada help with
>>debugging?
> 
> 
> I don't wish to cross with Marin in answering this, but forgive me if I
> throw my oar in a bit.
> 
> Suppose I have two threads (another name for 'tasks') which both need to
> read a variable (which is a struct (record)) from time to time, and one of
> them also updates the variable from time to time. When an update is done, it
> involves assigning values to several of the variable's members (components),
> so the update is not 'atomic'. This means that there needs to be some kind
> of synchronisation between the threads, to prevent one thread trying to read
> the variable right in the middle of it being updated.
> 
> In most programming languages, including C for example, under a typical
> execution environment or OS, the usual or only way to do this will be by the
> explicit use of semaphores (or a similar facility). When a thread wants to
> read or update the variable, it sets the semaphore (which may cause it to
> wait (to be 'blocked')). When it has finished, it resets the semaphore
> (which may unblock another waiting thread). Let's say the function to set a
> semaphore is named 'sem_p', and the function to reset it is 'sem_v'. If the
> variable is named 'r' (and has members 'x' and 'y') and the semaphore is
> named 's', a C program might contain code like this:
> 
>    /* Thread A */
>    ...
>    sem_p(s); /* set the semaphore, maybe wait */
>    x = r.x; y = r.y; /* read the variable */
>    sem_v(s); /* reset the semaphore */
>    ...
> 
>    /* Thread B */
>    ...
>    sem_p(s); /* set the semaphore, maybe wait */
>    r.x = x; r.y = y; /* update the variable */
>    sem_v(s); /* reset the semaphore */
>    ...
> 
> This is all well and dandy, but there are many things that can go wrong. For
> example, supposing a programmer accidentally omitted one of the calls to
> sem_p or sem_v? Or accidentally used the wrong semaphore in one of the
> calls? This kind of mistake is easily done in a big, complex program with
> lots of threads and semaphores. The consequences are often hard to debug: it
> is typical that a problem is only manifested intermittently; it is typical
> that using a debugger (single stepping or breakpoint jumping) destroys the
> temporal circumstances of normal execution that are needed to observe the
> problem at all; it is typical that, even when the problem is observed, the
> cause is subtle and very hard to determine.
> 
> In Ada 95, you would typically use a protected object to protect the
> variable from unwanted parallel access. (In Ada 83 you would typically have
> used a task and a 'rendezvous', but I'll illustrate the protected object
> approach here.)
> 
>    type R_Type is
>       record
>          X, Y: Float;
>          ...
>       end record;
> 
>    protected Prot_R is
>       function Get return R_Type;
>       procedure Set (New_R: in R_Type);
>    private
>       Inner_R: R_Type;
>    end;
> 
>    protected body Prot_R is
> 
>       function Get return R_Type is
>       begin
>          return Inner_R;
>       end;
> 
>       procedure Set (New_R: in R_Type) is
>       begin
>          Inner_R := New_R;
>       end;
> 
>    end Prot_R;
> 
>    ...
>    --- in task A
>    declare
>       Local_R: R_Type;
>    begin
>       Local_R := Prot_R.Get; -- read variable
>       X := Local_R.X;
>       Y := Local_R.Y;
> 
> 
>    ...
>    --- in task B
>    Prot_R.Set((X,Y,...)); -- update variable
> 
> Because the use of OS primitives such as semaphores is hidden from the user
> by Ada, many of the mistakes that would be easy to make in the C code are
> either impossible -- for example, we cannot omit a call to set or reset a
> semaphore, since Ada does these for us invisibly -- or caught by the
> compiler and reported to us in an obvious way -- for example, if we tried to
> use 'Inner_R' in an expression in task A or B, the compiler would complain
> that Inner_R is not visible at that point (because it is private to Prot_R).
> 
> Obviously this example is simplistic compared to real software, but I hope
> it gives a flavour of Ada's advantages in concurrent programming.
> 
> You might like to note that the use of an Ada protected object gives further
> advantages than I have mentioned so far. It is implemented in such a way
> that functions are permitted to be parallel with one another (but not with
> any procedure). So, tasks A and B would be permitted to read Prot_R
> simultaneously, but no task would be allowed to read it while another was in
> the middle of setting it. Protected objects can provide yet more
> sophisticated functionality (with 'entries'). And then there are tasks,
> rendezvouses, and various other facilities too. All of this functionality
> can be achieved in other languages, but generally only at a lower and more
> error-prone level.
> 
> Really, one could write a big book about concurrent programming in Ada.
> Hehe, in fact I'm sure somebody has! I'm sorry, I can't recall the details,
> but I'm sure someone else will oblige.
> 


-- 
======================================================================
Marin David Condic
I work for: http://www.belcan.com/
My project is: http://www.jsf.mil/NSFrames.htm

Send Replies To: m   o   d   c @ a   m   o   g
                    c   n   i       c   .   r

     "Face it ladies, its not the dress that makes you look fat.
     Its the FAT that makes you look fat."

         --  Al Bundy

======================================================================

Re: Advantages

[Jacob Sparre Andersen]

Andrew Carroll wrote:

> Would it be safe to say then that Ada in general depends heavily on
> the compiler to catch implementation mistakes?

In a way.  But it might give a somewhat incorrect impression.  Even
Ada programmers look at what they write and test their programs once
they compile.  I would rather say that with Ada, the compiler works as
an extra filter for catching implementation mistakes.

Jacob
-- 
"I'm going as a barrel of toxic waste!"

Re: Advantages

[Randy Brukardt]

"Brian May" <bam@snoopy.apana.org.au> wrote in message
news:sa47jtse93b.fsf@snoopy.apana.org.au...
...
> The implication of what you say is you can't have a deadlock in Ada
> across different packages, that will compile, if you use protected
> objects in this manner to access variables
>
> Not true!

<Long example omitted>

All your example proves is that GNAT doesn't catch the error in this
program. It is a bounded error to use a blocking operation in protected
action (see 9.5.1(8-17)). It's defined to either be detected (and raise
Program_Error) or otherwise "may result in deadlock".

So, if you write code that's defined to deadlock, it isn't particularly
surprising that it deadlocks.

The reason that this is a bounded error is that it can't in general be
detected at compile-time, and there were those that thought the overhead of
detecting at run-time was too high. (Janus/Ada always detects it, so your
program would just raise Program_Error. But Janus/Ada wasn't designed for
hard real-time systems.) I'm pretty sure the intent was that it would be
detected if the cost wasn't too severe - there was no intent to allow such
things because of the havoc that could occur in the run-time.

Since GNAT detected the error at compile-time (thus the warning), there
couldn't be any run-time overhead for detecting the error. It should
therefore have raised Program_Error (allowing a known deadlock condition
seems like a very bad thing). But perhaps there is some customer of ACT's
that likes living dangerously? Or, perhaps the case just never came up,
because people rarely try to do the obviously bad...

                                   Randy.

Re: Advantages

[Hyman Rosen]

Randy Brukardt wrote:
 > It is a bounded error to use a blocking operation in protected
> action (see 9.5.1(8-17)). It's defined to either be detected
 > (and raise Program_Error) or otherwise "may result in deadlock".
> 
> Since GNAT detected the error at compile-time (thus the warning), there
> couldn't be any run-time overhead for detecting the error. It should
> therefore have raised Program_Error (allowing a known deadlock condition
> seems like a very bad thing). But perhaps there is some customer of ACT's
> that likes living dangerously? Or, perhaps the case just never came up,
> because people rarely try to do the obviously bad...

If I'm not mistaken, normal Ada I/O is potentially blocking and is
therefore technically not allowed in protected actions. I believe
ACT's customers found this to be too restrictive, and that's why
GNAT doesn't prevent potentially blocking actions from being called.
I seem to recall threads on this subject back when Dewar was still
here.

Re: Advantages

[Randy Brukardt]

"Hyman Rosen" <hyrosen@mail.com> wrote in message
news:3p5Ec.13759$Av3.4246@nwrdny01.gnilink.net...
> Randy Brukardt wrote:
>  > It is a bounded error to use a blocking operation in protected
> > action (see 9.5.1(8-17)). It's defined to either be detected
>  > (and raise Program_Error) or otherwise "may result in deadlock".
> >
> > Since GNAT detected the error at compile-time (thus the warning), there
> > couldn't be any run-time overhead for detecting the error. It should
> > therefore have raised Program_Error (allowing a known deadlock condition
> > seems like a very bad thing). But perhaps there is some customer of
ACT's
> > that likes living dangerously? Or, perhaps the case just never came up,
> > because people rarely try to do the obviously bad...
>
> If I'm not mistaken, normal Ada I/O is potentially blocking and is
> therefore technically not allowed in protected actions. I believe
> ACT's customers found this to be too restrictive, and that's why
> GNAT doesn't prevent potentially blocking actions from being called.
> I seem to recall threads on this subject back when Dewar was still
> here.

That's correct. And it makes sense to allow I/O, as many implementation
don't in fact do anything blocking. But I would expect that the
implementation would treat things that are *known* to be blocking (like a
delay statement) differently - there can be no legitimate reason for doing
that. In a ceiling locking implementation, blocking would effectively break
the locking (as there is no explicit lock), meaning that the entire
abstraction was completely broken. Given that Ada is usually about safety,
allowing that sort of result just doesn't make sense. (Janus/Ada checks when
blocking task supervisor calls are made, so I/O, for example, isn't
necessarily restricted.)

                         Randy.

Re: Advantages

[Brian May]

>>>>> "Randy" == Randy Brukardt <randy@rrsoftware.com> writes:

    Randy> That's correct. And it makes sense to allow I/O, as many
    Randy> implementation don't in fact do anything blocking. But I
    Randy> would expect that the implementation would treat things
    Randy> that are *known* to be blocking (like a delay statement)
    Randy> differently - there can be no legitimate reason for doing
    Randy> that. In a ceiling locking implementation, blocking would

<hat mode="devils advocate">

You want to send a message to a hardware device. The requirements
specify that one message should be sent to the device, followed by a
fixed delay, then another message. During this entire period of time,
exclusive access is required to the device, because other threads
could otherwise interfere.

Lets also assume that sending the message is a blocking function that
will block until either an acknowledgement or error is returned by the
device.

What is the safest way of implementing this under Ada?

Three blocking statements, that require exclusive access to a
resource.

You could have a protected type emulate a semaphore, but then we are
back to using primitive operations (and related mistakes) that Ada was
meant to avoid.

You could have these 3 statements run from a procedure within a
protected type (along with procedures to do other things), but you not
suppose to make calls that potentially block from a protected type.

Just curious as to the recommended way of dealing with this
situation...

</hat>
-- 
Brian May <bam@snoopy.apana.org.au>

Re: Advantages

[Jeffrey Carter]

Brian May wrote:

> You want to send a message to a hardware device. The requirements
> specify that one message should be sent to the device, followed by a
> fixed delay, then another message. During this entire period of time,
> exclusive access is required to the device, because other threads
> could otherwise interfere.
> 
> Lets also assume that sending the message is a blocking function that
> will block until either an acknowledgement or error is returned by the
> device.
> 
> What is the safest way of implementing this under Ada?
> 
> You could have a protected type emulate a semaphore, but then we are
> back to using primitive operations (and related mistakes) that Ada was
> meant to avoid.

The problem is that protected objects are not general-purposes 
structures to provide mutual exclusion, as they appear on the surface. 
Rather, they are specialized to provide mutual exclusion for data. Hence 
the restrictions against calling potentially blocking operations.

This was probably a mistake, but that changes nothing. If you're 
creating your own language, you can avoid making this mistake.

Probably the safest way is the Ada-83 way: use a task. Tasks can block 
all they want.

If the measured overhead of an additional task and a rendezvous exceeds 
your requirement, Ada has some features that allow a semaphore to be 
used much more safely than in other languages:

A controlled type can be used to automatically seize (during Initialize) 
and release (during Finalize) a semaphore. This avoids the omission of 
such calls, especially the "missed path" problem in which there is an 
exit path (such as due to exceptions) without a release call.

The semaphore can be hidden; those who invoke the sequence of operations 
see them as a single atomic operation. This localizes the places where 
the semaphore is manipulated, and makes finding errors in its use easier.

-- 
Jeff Carter
"I'm a lumberjack and I'm OK."
Monty Python's Flying Circus
54

Re: Advantages

[Dmitry A. Kazakov]

On Fri, 02 Jul 2004 10:49:52 +1000, Brian May wrote:

>>>>>> "Randy" == Randy Brukardt <randy@rrsoftware.com> writes:
> 
>     Randy> That's correct. And it makes sense to allow I/O, as many
>     Randy> implementation don't in fact do anything blocking. But I
>     Randy> would expect that the implementation would treat things
>     Randy> that are *known* to be blocking (like a delay statement)
>     Randy> differently - there can be no legitimate reason for doing
>     Randy> that. In a ceiling locking implementation, blocking would
> 
> <hat mode="devils advocate">
> 
> You want to send a message to a hardware device. The requirements
> specify that one message should be sent to the device, followed by a
> fixed delay, then another message. During this entire period of time,
> exclusive access is required to the device, because other threads
> could otherwise interfere.
> 
> Lets also assume that sending the message is a blocking function that
> will block until either an acknowledgement or error is returned by the
> device.
> 
> What is the safest way of implementing this under Ada?
> 
> Three blocking statements, that require exclusive access to a
> resource.
> 
> You could have a protected type emulate a semaphore, but then we are
> back to using primitive operations (and related mistakes) that Ada was
> meant to avoid.
> 
> You could have these 3 statements run from a procedure within a
> protected type (along with procedures to do other things), but you not
> suppose to make calls that potentially block from a protected type.
> 
> Just curious as to the recommended way of dealing with this
> situation...

There is no recommended way, there are only ways.

Just to add to what Jeffrey Carter said. A protected action can be split
into "floating" pieces using the requeue statement.

For example, you can initiate I/O in one entry point, then requeue to
another which barrier will fire upon completion. You might argue that it is
rather a complicated way, especially if requeue with abort should be
supported and there is a large number of different states, but it works.
(It much resembles a finite state machine.)

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

Re: Advantages

[Marin David Condic]

A complicated situation like this would seem to want some sort of 
lower-level task acting as the manager of the device. It would need to 
be providing a lot more logic than you get inherently from a protected 
type. The protected type is designed just to get exclusive write access 
to some collection of data - not really manage lots of logic about 
ordering the accesses to the data.

I've seen this kind of need before - commonly if you're handling a slow 
A/D converter where you need to point a mux, wait for it to settle, 
start a conversion wait for it to convert and then collect the sample. 
Usually with that kind of situation, its done with only one thread 
controlling the device and deciding how best to manage it - not with a 
protected type.

MDC


Brian May wrote:
> 
> You want to send a message to a hardware device. The requirements
> specify that one message should be sent to the device, followed by a
> fixed delay, then another message. During this entire period of time,
> exclusive access is required to the device, because other threads
> could otherwise interfere.
> 
> Lets also assume that sending the message is a blocking function that
> will block until either an acknowledgement or error is returned by the
> device.
> 
> What is the safest way of implementing this under Ada?
> 
> Three blocking statements, that require exclusive access to a
> resource.
> 
> You could have a protected type emulate a semaphore, but then we are
> back to using primitive operations (and related mistakes) that Ada was
> meant to avoid.
> 
> You could have these 3 statements run from a procedure within a
> protected type (along with procedures to do other things), but you not
> suppose to make calls that potentially block from a protected type.
> 
> Just curious as to the recommended way of dealing with this
> situation...
> 
> </hat>


-- 
======================================================================
Marin David Condic
I work for: http://www.belcan.com/
My project is: http://www.jsf.mil/NSFrames.htm

Send Replies To: m   o   d   c @ a   m   o   g
                    c   n   i       c   .   r

     "Face it ladies, its not the dress that makes you look fat.
     Its the FAT that makes you look fat."

         --  Al Bundy

======================================================================

Re: Advantages

[Robert I. Eachus]

Brian May wrote:

> The implication of what you say is you can't have a deadlock in Ada
> across different packages, that will compile, if you use protected
> objects in this manner to access variables
> 
> Not true!

As others have already pointed out.  True.  The wording of the standard 
is subtle to allow for things like asynchronous I/O operations, or 
protected operations in the library distributed with the compiler that 
'know' about special properties of the target system.  Or more 
important, OS calls that are potentially blocking, but where the 
protected object is coded so that the call is only made when it cannot 
block.

As Randy says, the wording of the message from GNAT is not as clear as 
it could be:  "You blockhead! This program can deadlock!"

That message, of course, is not appropriate in some of the special cases 
where the user can tell that deadlock/Program_Error will never occur. 
And of course "can" not "will" in the message is correct--the compiler 
can't tell if the operations that will deadlock will be called--at least 
not at compile time.

Of course, if you are designing real-time systems, this is what you 
should care about.  The Ada compiler cannot tell you that your program 
will deadlock.  What it can tell you, by the absense of warnings, is 
that your program will not have any deadlocks directly involving 
protected objects.  There are similar rules elsewhere in the language 
involving tasks.

> I would imagine that there are other cases where the compiler can't
> warn you.

No, the compiler can always warn you.  Of course, if you want, you can 
use protected objects to implement P and V, then wrap potentially 
blocking actions inside the semaphores implemented that way.  But that 
is going out of your way to get back to the situation without Ada 
protected objects.

The intent in Ada really is that protected objects used correctly will 
not create deadlocks.  Used correctly of course, means among other 
things absent bounded errors.  If you want to encapsulate a potentially 
blocking operation in a protected object, that is what entries and entry 
barriers are for.  You either have an entry where the barrier condition 
is that the potentially blocking action inside the entry will not block, 
or you can use a requeue statement if you determine that the action will 
block.  Either way, the user of the abstraction can use a timed or 
conditional entry call, so that the caller will either not block, or not 
block for more than a predetermined time.

-- 

                                           Robert I. Eachus

"The flames kindled on the Fourth of July, 1776, have spread over too 
much of the globe to be extinguished by the feeble engines of despotism; 
on the contrary, they will consume these engines and all who work them." 
-- Thomas Jefferson, 1821

Re: Advantages

[Robert I. Eachus]

Andrew Carroll wrote:

> VERY NICE!!  I'm guessing that Ada does this type of checking in
> general and not just for the concurrency model?

The original intent of the Ada elaboration model was to eliminate access
before elaboration (ABE) errors.  The basic concept is that their must 
be a linear elaboration order for a program that does not involve any 
subprogram being called or object being referenced before its 
declaration has been elaborated.  This means you can't reference a 
variable before it has been initialized, and so on.

In the case of protected objects, what I was saying was that the 
existance of this elaboration order means that you can "take advantage" 
of the fact that it exists to prevent deadlock.

As other posts in this thread show, you can still "brute force" a 
deadlock in Ada.  (The simplest way is to have a task call one of its 
own entries.)  But if you create a program where you accidently call a 
procedure or function that calls an entry of a protected object, the 
compiler can/should warn you.  Calling functions or procedures of 
protected objects that occur earlier in the elaboration chain won't 
cause a deadlock, because of the enforced partial ordering.

Of course, also as the discussion showed, you can "get around" this to 
create a deadlock in several ways.  But you can also make the 
elaboration ordering a part of your design, and require messinger tasks 
when a violation could occur.  Again, with tasks you have to design them 
so that they don't deadlock.  But if you get the design right in the 
implementation of the task, calling that task won't create deadlocks. 
Again due to the elaboration heirarchy.

> I think you have shown me another side of Ada.  Or at least given me
> a glimpse of another side of Ada.  It helps so much to have an
> example!!! Do the new "limited with" and "synchronized" keywords
> discussed for Ada200Y affect the information you have provided?

You are asking me to predict the future. ;-) The intent is that the 
changes in Ada 0Y will not break any of these fundamental concepts.  But 
are there design errors in the current versions of these proposals? 
Probably.  That is why there is so much review involved before the new 
version of Ada becomes official.

-- 

                                           Robert I. Eachus

"The flames kindled on the Fourth of July, 1776, have spread over too
much of the globe to be extinguished by the feeble engines of despotism;
on the contrary, they will consume these engines and all who work them."
-- Thomas Jefferson, 1821