D.10

D.10

[Matthew Heaney]

Paragraph D.10 (7) states that

"The operations Set_True and Set_False are atomic with respect to each
other and with respect to Suspend_Until_True..."


Q: Is Suspend_Until_True atomic with respect to Suspend_Until_True?

In 12.3.1 of Burns and Wellings, they state that a semaphore can be used
to program mutual exclusion between two tasks, like this:


  Sema : Suspension_Object;

  task T;

  T1, T2 : T;


  task body T is
  begin

     Set_True (Sema);

    ...

     Suspend_Until_True (Sema);

     <critical region>

     Set_True (Sema);

     ...

  end T;

     

The suspension object is true.  Now suppose the two tasks try to call
Suspend_Until_True at the same time.  Is this an atomic operation?

The assumption by Burns and Wellings seems to be that, one of the tasks
will get the suspension object first, find that it's already true, wake
up (or just stay awake), and set the flag back to false as a side-effect
of the Suspend_Until_True call.

The other task, who got in a little later, finds the suspension object
is false, and goes to sleep, until the first task finishes its critical
region, and sets the suspension object back to true.

Is this a legitimate scenario?  The RM states that PE gets raised if one
task calls Suspend_Until_True and another task is already waiting on the
same object.  But what does "already waiting on the suspension object"
mean?

Does it mean that the task has started calling Suspend_Until_True, and
isn't finished yet when the other task calls Suspend_Until_True?

Does the statement "waiting on the suspension object" include the time
when one object calls Suspend_Until_True, and the suspension object is
already true?

Or does it only refer to the time when a task calls Suspend_Until_True,
and goes to sleep because the suspension object is false?

Can calls to Suspend_Until_True interleave?

Re: D.10

[Steve Quinlan]

In the Annotated ARM, there is a discussion item after D.10.6 which seems to
make clear (is that an oxymoron?) that it was not intended to be used this
way:

 " This object is assumed to be private toe the declaring task, i.e. only
that task will call Suspend_Until_True on this object, and the count of
callers is at most 1. Other tasks can, of course, change and query the state
of this object."

Re: D.10

[James S. Rogers]

Matthew Heaney wrote in message ...
>Paragraph D.10 (7) states that
>
>"The operations Set_True and Set_False are atomic with respect to each
>other and with respect to Suspend_Until_True..."
>
>
>Q: Is Suspend_Until_True atomic with respect to Suspend_Until_True?
>
>In 12.3.1 of Burns and Wellings, they state that a semaphore can be used
>to program mutual exclusion between two tasks, like this:
>

Why not implement this as a protected object instead of a task. Protected
operations are guaranteed to be atomic.

Jim Rogers
Colorado Springs, Colorado

Re: D.10

[Robert Dewar]

In article <m3lnfxtan3.fsf@mheaney.ni.net>,
  Matthew Heaney <matthew_heaney@acm.org> wrote:
> The RM is ambiguous.  It doesn't say specifically that
> the suspension object can be shared this way (ie that
> Suspend_Until_True is atomic wrt other calls to
> Suspend_Until_True), but it doesn't say it can't be.

I must say I don't see any ambiguity in the RM here, but
I have trouble with your question because the terminology
is vague ("A is atomic wrt B" does not have a clear meaning
in this context).

> I would like to know the specific intent of the language
> designers, and whether or not the algorithm in B&W is in
> fact legal.

You are using legal again in some peculiar sense (in Ada
it means that something satisfies static semantic and
syntax requirements).

I think you will get a clearer answer to your question if
you produce a small example, and ask a question about it
at the proper level of semantic description. If I write X,
then is Y true, where Y is stated in terms with which we
are familiar, preferably those in the RM!

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

Re: D.10

[Robert Dewar]

In article <7evbm6$oto$1@nnrp1.dejanews.com>,
  Robert Dewar <robert_dewar@my-dejanews.com> wrote:
> I must say I don't see any ambiguity in the RM here, but
> I have trouble with your question because the terminology
> is vague ("A is atomic wrt B" does not have a clear
> meaning in this context).

This is a followup to myself to make my point a bit
clearer. You can talk about operations being atomic, but
not entities. So if your question is

  Is the operation Suspend_Until_True atomic with
  respect to itself?

Then I think the useful answer is that the question is
meaningless, and the technical answer is no!



>
> > I would like to know the specific intent of the
language
> > designers, and whether or not the algorithm in B&W is
in
> > fact legal.
>
> You are using legal again in some peculiar sense (in Ada
> it means that something satisfies static semantic and
> syntax requirements).
>
> I think you will get a clearer answer to your question if
> you produce a small example, and ask a question about it
> at the proper level of semantic description. If I write
X,
> then is Y true, where Y is stated in terms with which we
> are familiar, preferably those in the RM!
>
> -----------== Posted via Deja News, The Discussion
Network ==----------
> http://www.dejanews.com/       Search, Read, Discuss, or
Start Your Own
>

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

Re: D.10

[Robert Dewar]

In article <m3ogkuuriu.fsf@mheaney.ni.net>,
  Matthew Heaney <matthew_heaney@acm.org> wrote:
> Paragraph D.10 (7) states that

My advice is to stay completely away from this feature
in the language. It is gratutious nonsense if you ask
me. It consists of one particular, not very well thought
out second level primitive.

Much better to define your own.

Possibly your implementation might do something specially
efficient with this package, it might also do something
specially efficient with simple cases of protected records.
Certainly GNAT just translates this into the corresponding
protected type in a naive way, and we have never seen a
program that used it except an ACVC test or two :-)

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

Re: D.10

[Matthew Heaney]

Robert Dewar <robert_dewar@my-dejanews.com> writes:

> In article <m3lnfxtan3.fsf@mheaney.ni.net>,
>   Matthew Heaney <matthew_heaney@acm.org> wrote:
> > The RM is ambiguous.  It doesn't say specifically that
> > the suspension object can be shared this way (ie that
> > Suspend_Until_True is atomic wrt other calls to
> > Suspend_Until_True), but it doesn't say it can't be.
> 
> I must say I don't see any ambiguity in the RM here, but
> I have trouble with your question because the terminology
> is vague ("A is atomic wrt B" does not have a clear meaning
> in this context).


I was trying to phrase my question using the same terms as the RM, but
perhaps I goofed.

RM95 D.10 (7) reads "The operations Set_True and Set_False are atomic
with respect to each other and with respect to Suspend_Until_True..."

My question is, why doesn't the RM also say "The operation
Suspend_Until_True is atomic with respect to Suspend_Until_True"?


> > I would like to know the specific intent of the language
> > designers, and whether or not the algorithm in B&W is in
> > fact legal.
> 
> You are using legal again in some peculiar sense (in Ada
> it means that something satisfies static semantic and
> syntax requirements).

Agreed; I used the term "legal" incorrectly.

 
> I think you will get a clearer answer to your question if
> you produce a small example, and ask a question about it
> at the proper level of semantic description. 

I included an example in my original post.

Here is the text from Concurrency In Ada (by Burns and Wellings),
section 12.3.1:

(start of excerpt)
Using a Suspension_Object, it is possible to program mutual exclusion
between two tasks by simply encapsulating their critical sections with
the following:

   Mutex : Suspension_Object;

   ...

   Set_True (Mutex);

   ...

   Suspend_Until_True (Mutex);
     -- critical section
   Set_True (Mutex);

Suspension objects can also be used inside protected objects to
implement condition synchronization. (end of excerpt)


My question is, Is this is a correct program, or isn't it?

Does this program have a defined meaning, or doesn't it?

Is the statement "it is possible to program mutual exclusion between two
tasks by simply encapsulating their critical sections with the
following..." true, or isn't it?



> If I write X, then is Y true, where Y is stated in terms with which we
> are familiar, preferably those in the RM!

The phrase "atomic with respect to" came out of the RM, which I why I
used it.  Incorrectly, I guess.

Re: D.10

[Matthew Heaney]

Robert Dewar <robert_dewar@my-dejanews.com> writes:

> In article <7evbm6$oto$1@nnrp1.dejanews.com>,
>   Robert Dewar <robert_dewar@my-dejanews.com> wrote:
> > I must say I don't see any ambiguity in the RM here, but
> > I have trouble with your question because the terminology
> > is vague ("A is atomic wrt B" does not have a clear
> > meaning in this context).
> 
> This is a followup to myself to make my point a bit
> clearer. You can talk about operations being atomic, but
> not entities. So if your question is
> 
>   Is the operation Suspend_Until_True atomic with
>   respect to itself?
> 
> Then I think the useful answer is that the question is
> meaningless, and the technical answer is no!


Let me ask the question another way.

Is an invocation of operation Suspend_Until_True on a suspension object
by one task atomic with respect to an invocation of Suspend_Until_True
on the same suspension object by another task?

Re: D.10

[Matthew Heaney]

Robert Dewar <robert_dewar@my-dejanews.com> writes:

> In article <m3ogkuuriu.fsf@mheaney.ni.net>,
>   Matthew Heaney <matthew_heaney@acm.org> wrote:
> > Paragraph D.10 (7) states that
> 
> Much better to define your own.

Can you give me specific advice about how to do that?  What do you mean
by "define your own"?


> Possibly your implementation might do something specially efficient
> with this package, it might also do something specially efficient with
> simple cases of protected records.

The rationale makes the argument that a suspension object is likely to
be more efficient because it is "unnecessary to maintain a queue -- a
major saving in run-time cost."  (Rat95 D.10 p. D-37 para. 6)


> Certainly GNAT just translates this into the corresponding
> protected type in a naive way, and we have never seen a
> program that used it except an ACVC test or two :-)

I learned about suspension objects from the keynote speaker at last
year's SIGAda conference, a person (I forget his name; works for Aonix
UK) involved in the formulation of the Ravenscar profile.

He said specifically that this was a feature for "close to the metal
programming", a phrase he learnt from none other than Tucker Taft.

You might think that a suspension object is "gratuitous nonsense," and
of course you are entitled to your opinion.  

However, my expectation is that the suspension object is in the language
because it admits a more efficient implementation than using a entry
queue.

For example, the programmer might be writing a program using an entry
queue that he knows will only have a maximum of one caller.  In this
case, a queue is unnecessary.


But let us waive aside any debates about whether a suspension object is
a useful language feature, and concentrate on specifics.  Is the program
in section 12.3.1 of Burns and Wellings correct, or not?

Re: D.10

[Robert A Duff]

Matthew Heaney <matthew_heaney@acm.org> writes:

> Is an invocation of operation Suspend_Until_True on a suspension object
> by one task atomic with respect to an invocation of Suspend_Until_True
> on the same suspension object by another task?

Well, the RM doesn't say it is, so I guess it isn't.  I admit the RM
isn't crystal clear on this point.

The *intent* is that this feature would be used in a situation where a
given suspension object is "owned" by a single task, and only that task
does Suspend_Until_True.  That task publishes a handle on the suspension
object to the rest of the world, and other tasks can call Set_True to
wake it up.  I would also expect that only the owner does Set_False
(presumably before "publishing").  Actually, it is set False by default
initialization, so you don't need to ever call Set_False, unless you
want to reuse the same suspension object.

The example you gave from Burns and Wellings seems weird to me,
whatever the RM says.

The run-time system I'm currently working on (for the ADI SHARC DSP
chip) has an implementation (just a few instructions) that will make the
example work.  But it wouldn't surprise me if other implementations have
a race condition.

- Bob
-- 
Change robert to bob to get my real email address.  Sorry.

Re: D.10

[Robert A Duff]

Robert Dewar <robert_dewar@my-dejanews.com> writes:

> My advice is to stay completely away from this feature
> in the language. It is gratutious nonsense if you ask
> me. It consists of one particular, not very well thought
> out second level primitive.
> 
> Much better to define your own.

That kind of statement would have more credibility if you gave some
reasons.  ;-)

My experience is just the opposite:

Averstar's Ada run-time system is fundamentally based on suspension
objects as the main means of suspending tasks.  We can't "define our
own" in terms of protected objects, because we're *implementing*
protected objects.  Suspension objects are a lower-level primitive.

I find suspension objects to be quite a clean feature to use;
race conditions are more easily eliminated than with (for example)
a Suspend_Self/Resume_Other pair of operations.

I know of one customer that uses suspension objects, for example, to
communicate between interrupt handlers and tasks in a way that is more
efficient than protected objects.  The key to the efficiency is that
there can never be more than one task waiting.  I don't think it's
feasible to make the compiler automatically optimize a normal protected
object in a similar way, because how is it supposed to know about this
special (rather global) property.  (Well, I suppose you could have a
pragma.)

> Possibly your implementation might do something specially
> efficient with this package, it might also do something
> specially efficient with simple cases of protected records.

I don't see how a compiler can be expected to figure out that only one
task will ever suspend on a given protected entry.  The programmer has
to tell the compiler.  Using suspension objects does that.  I can
imagine other mechanisms for telling the compiler, but I can't imagine a
totally automatic optimization along these lines.

> Certainly GNAT just translates this into the corresponding
> protected type in a naive way, and we have never seen a
> program that used it except an ACVC test or two :-)

Perhaps GNAT isn't used so much in the same sort of real-time embedded
systems where this kind of efficiency issue is so important, and perhaps
that's why your customers don't use it.  Or perhaps they don't use it
because you haven't implemented it efficiently -- the language design
can make optimizations feasible, but it can't force implementers to do
them.  If we're talking about implementing Ada on top of a typical
operating-system threads implementation, then efficiency is hopeless
anyway, so of course folks aren't going to be worrying about suspension
objects.

- Bob

P.S. The following section, D.11, Asynchronous Task Control -- now
*that's* gratuitous nonsense.  ;-)
-- 
Change robert to bob to get my real email address.  Sorry.

Re: D.10

[Robert Dewar]

In article <wccogks5yhv.fsf@world.std.com>,
  Robert A Duff <bobduff@world.std.com> wrote:
> That kind of statement would have more credibility if you
> gave some reasons.  ;-)

There is no reason not to optimize special forms of
protected records to get the same efficiency that is
possible from suspension objects, and I think this kind
of general optimization seems preferable to creating a
new concept in the RM, which is not even properly
defined (as you Robert Duff admit :-)

At the very least I would have preferred that the RM define
the semantics of Suspension_Object in terms of a protected
record and then suggest that implementations might want to
provide more efficient solutions for this.

Now that I reread the thread, and finally understand what
Matthew is asking (sorry for being slow on this one), I
think he has a real point, the semantics of
Suspension_Object is indeed extremely murky. Indeed the
phrase "atomic with respect .." is completely gobbledygook
since it is nowhere defined what this means.

It is as though some completely separate author wrote this
chapter and chucked it in and nobody paid any attention to
it. That may be a bit unfair, but I know I paid no
attention to it, and I cannot believe that anyone would
have read it carefully and not raised a huge red flag on
seeing the inappropriate language used in this section.

So I guess the ARG has some real work cut out here to
define this annoying gizmo :-)

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

Re: D.10

[Robert Dewar]

In article <wccogks5yhv.fsf@world.std.com>,
  Robert A Duff <bobduff@world.std.com> wrote:
> because we're *implementing*
> protected objects.  Suspension objects are a lower-level
> primitive.

Implementing well defined Ada primitives in terms of lower
level ill-defined primitives is certainly possible. Indeed
unfortunately, in the GNAT world, and I expect in most
other Ada implementation worlds, it is, unfortunately, a
way of life!

But that is no excuse to make the ill-defined lower level
primitives user visible :-)

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

Re: D.10

[Tucker Taft]

Matthew Heaney wrote:
> ...
> The rationale makes the argument that a suspension object is likely to
> be more efficient because it is "unnecessary to maintain a queue -- a
> major saving in run-time cost."  (Rat95 D.10 p. D-37 para. 6)
> 
> > Certainly GNAT just translates this into the corresponding
> > protected type in a naive way, and we have never seen a
> > program that used it except an ACVC test or two :-)
> 
> I learned about suspension objects from the keynote speaker at last
> year's SIGAda conference, a person (I forget his name; works for Aonix
> UK) involved in the formulation of the Ravenscar profile.
> 
> He said specifically that this was a feature for "close to the metal
> programming", a phrase he learnt from none other than Tucker Taft.
> 
> You might think that a suspension object is "gratuitous nonsense," and
> of course you are entitled to your opinion.
> 
> However, my expectation is that the suspension object is in the language
> because it admits a more efficient implementation than using a entry
> queue.
> 
> For example, the programmer might be writing a program using an entry
> queue that he knows will only have a maximum of one caller.  In this
> case, a queue is unnecessary.
> 
> But let us waive aside any debates about whether a suspension object is
> a useful language feature, and concentrate on specifics.  Is the program
> in section 12.3.1 of Burns and Wellings correct, or not?

I will admit that when designing the feature, we did not consider
the paradigm which Burns and Welling now suggest.  However, that
always happens when you design a feature.  Users find new and
interesting uses for it that the designers never anticipated.
This certainly doesn't automatically imply that the usage is
bad, just unanticipated.  

As far as whether the RM guarantees that the result of such a use is 
well-defined, it seems it makes no guarantees about atomicity between 
one task calling suspend_until_true and another doing the same.  
(Although Robert Dewar objects to the use of the term "atomic with
respect to one another," I believe the intent is fairly clear --
no bad race conditions exist, and two tasks may safely call the
operations concurrently.)

Now that this apparently useful paradigm has been identified by
B & W, it might be worth requiring that it be well-defined.  I suspect
that most existing implementations will already support it, though 
some investigation would obviously be worthwhile.  Do you have any
reason to believe it isn't currently supported by all implementations?

One other comment:  There was quite a bit of controversy when
the synchronous and asynchronous task control features were first
proposed.  Ultimately, we decided to put them in the Real-Time
Annex, but we intended that their semantics be explainable in
terms of other (albeit higher-level) features.  In fact, the
async task control was explained in terms of priority change.
We considered explaining sync task control in terms of protected
objects, but eventually decided to define them on their own, though
the intent was that they be as well defined as protected objects.

Burns and Wellings have illustrated that we forgot to consider the 
race between one Suspend-Until-True and another, when you "know"
that the suspension object is initially True.  Clearly if it might
be initially False, then the race is not of great interest, because
Program_Error is going to be raised in one of them. The ARG should
take a position on what happens when there is such a race.  I
don't see any reason not to require well-defined semantics in
this case as well.  I don't see a significant implementation burden.

-Tuck

-- 
-Tucker Taft   stt@averstar.com   http://www.averstar.com/~stt/
Technical Director, Distributed IT Solutions  (www.averstar.com/tools)
AverStar (formerly Intermetrics, Inc.)   Burlington, MA  USA

Re: D.10

[Matthew Heaney]

"James S. Rogers" <jimmaureenrogers@worldnet.att.net> writes:

> Matthew Heaney wrote in message ...
> >Paragraph D.10 (7) states that
> >
> >"The operations Set_True and Set_False are atomic with respect to each
> >other and with respect to Suspend_Until_True..."
> >
> >
> >Q: Is Suspend_Until_True atomic with respect to Suspend_Until_True?
> >
> >In 12.3.1 of Burns and Wellings, they state that a semaphore can be used
> >to program mutual exclusion between two tasks, like this:
> >
> 
> Why not implement this as a protected object instead of a task. Protected
> operations are guaranteed to be atomic.


I am exploring primitive (but potentially more efficient) ways to
synchronize tasks.

The RM is ambiguous.  It doesn't say specifically that the suspension
object can be shared this way (ie that Suspend_Until_True is atomic wrt
other calls to Suspend_Until_True), but it doesn't say it can't be.

I would like to know the specific intent of the language designers, and
whether or not the algorithm in B&W is in fact legal.

Re: D.10

[Robert Dewar]

In article <3713BDBF.53855B6C@averstar.com>,
  Tucker Taft <stt@averstar.com> wrote:
> I believe the intent is fairly clear --

Maybe the motto for language designers should be

"The path to hell is paved with fairly clear intentions"

:-)

(for non-English speakers, the above phrase with
"fairly clear" replaced by "good" is an old and
familiar aphorism :-)

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