Version 1.3 of ais/ai-00148.txt

Unformatted version of ais/ai-00148.txt version 1.3
Other versions for file ais/ai-00148.txt

!standard 09.05.04 (07)          04-03-23 AI95-00148/02
!class confirmation 96-06-06
!status ARG Approved 5-0-4 04-03-05
!status work item 00-02-14
!status received 96-06-06
!priority Low
!difficulty Easy
!subject Requeue of protected entry calls
!summary
The requeue of a protected entry to an entry in another protected object requires the protected action resulting from the requeue to be completed before the original protected action completes.
If the entry that is the subject of the requeue executes immediately, then the "inner" protected objects completes and is left before the servicing of entry queues in the task that executed the requeue statement.
!question
Does the requeue of a protected entry call to an entry in another protected object result in a nesting of protected actions? (Yes.)
!response
RM95-9.5.4(7) says that a requeue statement causes the enclosing entry body to be completed, finalized, and left. This does not mean that all of the protected operations that originated with the call have finished.
Section 9.5.1(7) states
"After performing an operation on a protected object
other than a call on a protected function, but prior to completing the associated protected action, the entry queues (if any) of the protected object are serviced (see 9.5.3)."
and 9.5.3(13-18) says
13 "When a queued call is selected, it is removed from its entry queue. Selecting a queued call from a particular entry queue is called servicing the entry queue. An entry with queued calls can be serviced under the following circumstances:
14 {N/A - on accept statements}
15 If after performing, as part of a protected action on the
associated protected object, an operation on the object other than a call on a protected function, the entry is checked and found to be open.
16 If there is at least one call on a queue corresponding to an open entry, then one such call is selected according to the entry queuing policy in effect (see below), and the corresponding accept_statement or entry_body is executed as above for an entry call that is selected immediately.
17 - N/A - on entry queueing polocies
18 For a protected object, the above servicing of entry queues continues until there are no open entries with queued calls, at which point the protected action completes."
Any execution resources associated with the protected entry and any epilogue actions, such as evaluation of entry guards as a result of this protected entry, are not performed until after the requeue statement completes.
In cases where the requeue operation results in immediate execution of the entry, then the protected operation that was the target of the requeue will be executed completely, as well as the execution of all other protected entry operations in the same protected object that evaluate to TRUE and have queued calls on the entry.
If the Protected Object that is the target of the requeue has a higher priority ceiling, or if the program is executing on a multiprocessor system, then the potential exists that the protected object's execution resource cannot be acquired. The potential exists in such situations that the task executing within the target protected object is attempting (either directly or indirectly) to similarly access the original protected object. It is the responsibility of the writers of such programs to ensure that such situations cannot occur.
!appendix

!section 9.5.4(07)
!subject Requeue of protected entry calls
!reference RM95-9.5.4(7,11)
!from Ted Giering 96-5-29
!reference 96-5581.a Ted Giering 96-5-29>>
!discussion

        RM95-9.5.4(7) says that a requeue statement causes the enclosing
entry body to be completed, finalized, and left.  RM95-9.5.4(11) says
that in the case of an external requeue to a protected object, a new
protected operation is started on the target object.
        There is some controversy here about whether this requires (or
even allows) the external requeue of a protected object to
another protected object to involve the nesting of protected
actions.  RM95-9.5.4(7) might be read to mean that the protection
action executing the original entry body should be completed before
starting the protected action on the target object.  On the other
hand, RM95-9.5.4(11) says that the protected action is started, which
in the absence of any qualification means immediately, without waiting
for anything else (such as servicing the entry queues of the first
object).
        In short, does an external requeue of a protected entry call to
another protected entry involve having both objects locked at the same
time?

                Ted Giering



****************************************************************

!section 9.5.4(07)
!subject Requeue of protected entry calls
!reference RM95-9.5.4(7,11)
!reference 96-5581.a Ted Giering 96-5-29
!reference 96-5588.a Robert A Duff 96-5-31>>
!discussion

Completing, finalizing, and leaving an entry_body does not imply that
the protection action is over.  It just means that the entry_body itself
is done (any local variables within the entry_body have been finalized,
and so forth).  Thus, the protected action associated with a requeue is
nested within the other protected action.

That is, if X1.E1 is being requeued to X2.E2 (external requeue), then
the locking will be something like this:

    lock X1
    lock X2
    unlock X2
    unlock X1

>       RM95-9.5.4(7) says that a requeue statement causes the enclosing
> entry body to be completed, finalized, and left.  RM95-9.5.4(11) says
> that in the case of an external requeue to a protected object, a new
> protected operation is started on the target object.
>       There is some controversy here about whether this requires (or
> even allows) the external requeue of a protected object to
> another protected object to involve the nesting of protected
> actions.  RM95-9.5.4(7) might be read to mean that the protection
> action executing the original entry body should be completed before
> starting the protected action on the target object.

No, I don't see any way that "leaving" an entry_body means the protected
action is over.  The definition of "leaving a master" in 7.6.1(3)
doesn't say anything like that.

>...On the other
> hand, RM95-9.5.4(11) says that the protected action is started, which
> in the absence of any qualification means immediately, without waiting
> for anything else (such as servicing the entry queues of the first
> object).
>       In short, does an external requeue of a protected entry call to
> another protected entry involve having both objects locked at the same
> time?

Yes.

- Bob


****************************************************************

!section 9.5.4(0)
!subject requeue from protected object to task
!reference RM95-9.5.4
!from Moti Ben-Ari 97-04-01
!reference 97-15739.a Moti Ben-Ari  97-4-1>>
!discussion

Subparagraphs 7-8 (my emphasis):

(7) The entry_body or accept_statement enclosing the requeue_statement
is
    then completed, finalized, and LEFT (see 7.6.1).
(8) For the execution of a requeue on an entry of a target task,
    AFTER LEAVING the enclosing callable construct, ...
    the requeued call is either selected immediately or queued, ...

seem to imply that the protected operation is terminated before
the attempt is made to call the entry.
If the lock on the protected object is released,
a race condition could ensue when another task preempts the
requeueing task, enters the protected object and requeues
on the called task entry.

I would like this interpretation to be ruled out,
so that the lock is held until the requeued call is
selected or safely queued.
Otherwise, external requeues become meaningless for synchronization.

--
Prof. Mordechai (Moti) Ben-Ari   Department of Science Teaching
Weizmann Institute of Science    Rehovot 76100 Israel
ntbenari@wis.weizmann.ac.il      benari@acm.org
http://wgst.weizmann.ac.il/benari/home.htm

Many people would sooner die than think. In fact they do.
   -- Bertrand Russel

****************************************************************

!section 9.5.4(0)
!subject requeue from protected object to task
!reference RM95-9.5.4
!reference RM95-9.5.1(7)
!reference 97-15739.a Moti Ben-Ari 97-04-01
!from Tucker Taft 97-04-02
!reference 1997-15740.a Tucker Taft 1997-4-2>>
!discussion

> Subparagraphs 7-8 (my emphasis):
>
> (7) The entry_body or accept_statement enclosing the requeue_statement
> is
>     then completed, finalized, and LEFT (see 7.6.1).
> (8) For the execution of a requeue on an entry of a target task,
>     AFTER LEAVING the enclosing callable construct, ...
>     the requeued call is either selected immediately or queued, ...
>
> seem to imply that the protected operation is terminated before
> the attempt is made to call the entry.

The entry body is left, but the protected action is not completed.
Per RM95 9.5.1(7), completing a protected operation does *not* imply
completing the protected action.  That happens only after servicing
all entry queues.

> If the lock on the protected object is released,
> a race condition could ensue when another task preempts the
> requeueing task, enters the protected object and requeues
> on the called task entry.
>
> I would like this interpretation to be ruled out,
> so that the lock is held until the requeued call is
> selected or safely queued.
> Otherwise, external requeues become meaningless for synchronization.

The interpretation you fear is incorrect.  The protected action
does not complete until after the requeuing operation is complete,
and all entry queues have been serviced.

> Prof. Mordechai (Moti) Ben-Ari   Department of Science Teaching
> Weizmann Institute of Science    Rehovot 76100 Israel
> ntbenari@wis.weizmann.ac.il      benari@acm.org
> http://wgst.weizmann.ac.il/benari/home.htm

-Tucker Taft  stt@inmet.com

****************************************************************

!section 9.5.4(10)
!subject     Requeue of protected entry calls
!reference AI95-00148
!reference 96-5581.a Ted Giering 96-5-29
!reference 96-5588.a Robert A Duff 96-5-31
!reference RM95-9.5.4(10-11)
!from      Dan Rittersdorf 97-3-31
!keywords  external requeue
!reference 1997-15741.a Dan Rittersdorf 1997-4-3>>
!discussion

   Bob,

Last May, you said:
>!section 9.5.4(07)
>!subject Requeue of protected entry calls
>!reference RM95-9.5.4(7,11)
>!reference 96-5581.a Ted Giering 96-5-29
>!reference 96-5588.a Robert A Duff 96-5-31
>!discussion
>
>Completing, finalizing, and leaving an entry_body does not imply that the
>protection action is over. It just means that the entry_body itself is done
>(any local variables within the entry_body have been finalized, and so
>forth). Thus, the protected action associated with a requeue is nested
>within the other protected action.
>
>That is, if X1.E1 is being requeued to X2.E2 (external requeue), then the
>locking will be something like this:
>
>lock X1
>lock X2
>unlock X2
>unlock X1
>
   [Quoting Ted Giering]
>> RM95-9.5.4(7) says that a requeue statement causes the enclosing
>> entry body to be completed, finalized, and left. RM95-9.5.4(11) says
>> that in the case of an external requeue to a protected object, a new
>> protected operation is started on the target object.
>> There is some controversy here about whether this requires (or
>> even allows) the external requeue of a protected object to
>> another protected object to involve the nesting of protected
>> actions. RM95-9.5.4(7) might be read to mean that the protection
>> action executing the original entry body should be completed before
>> starting the protected action on the target object.
>
>No, I don't see any way that "leaving" an entry_body means the protected
>action is over. The definition of "leaving a master" in 7.6.1(3) doesn't say
>anything like that.
>

   This reasoning is causing a bit of confusion here.  It would seem to
   contradict ACVC tests such as c954021.a, unless we're misunderstanding
   how this nesting of protected actions should occur.

   Consider the first message task c954021.a creates.  It calls
   Distributer.Input, which immediately requeues on task entry
   Credit_Computation.Input.  Distributer.Input is completed, finalized,
   and left, but (as noted above) the protected action continues.
   Credit_Computation.Input is open and is immediately selected.
   Credit_Computation.Input immediately makes an external call on
   Distributer.Credit_Is_Overloaded.  This would attempts to start a
   new protected action on the current protected object, which is a
   bounded error, because The Distributer.Input protected action is ongoing.

   If the enclosing protected action was not completed as part of the
   execution of the requeue, prior to the selection and execution of
   Credit_Computation.Input, then the call to Distributer.Credit_Is_Overloaded
   will deadlock or raise program_error.

   The semantics of requeue on a task entry do not appear to allow for the
   completion of the enclosing protected action prior to selection, so
   either the test is not valid, or we are confused.

   Could you comment on the situation in this test?

   [Quoting Ted Giering]
>>...On the other
>> hand, RM95-9.5.4(11) says that the protected action is started, which
>> in the absence of any qualification means immediately, without waiting
>> for anything else (such as servicing the entry queues of the first
>> object).
>
>> In short, does an external requeue of a protected entry call to
>> another protected entry involve having both objects locked at the same
>> time?
>
>Yes.
>
>   * Bob
>

   Even assuming the test got past the initial message task, it then runs
   into the situation you and Ted were discussing.  In the second message task,
   Distributer.Input encounters Credit_Overloaded, and requeues on
   Hold.Wait_For_Underflow.  This is an external requeue from within an
   entry body, so as you explain above, the protected actions nest.

      Lock Distributer
         Lock Hold
            ...
         Unlock Hold
      Unlock Distributer

   Hold.Wait_For_Underload is not open, so the caller blocks.
   There is some question about what should become of the outer protected
   action on Distributer while the caller blocks on Hold.Wait_for_Underload.
   When is it completed?  It must be completed prior to Wait_for_Underload
   becoming open, obviously, but it is not clear how.  The semantics of
   this nesting of protected actions is not clear from the RM95.

   Could you please elaborate on your answer in light of this ACVC test?

   Thank you.

--
  Dan.Rittersdorf@mail.ccur.com        or              RittersdorfD@ACM.org
______________________________________________________________________________
  Concurrent Computer Corporation      |               Daniel G. Rittersdorf
  2101 W. Cypress Creek Rd.            |               178 Washington Street
  Ft. Lauderdale FL 33309              |               Sparta, MI 49345-1324
  Ph: +1 (954) 974-1700                |               Ph: +1 (616) 887-5431
______________________________________________________________________________

****************************************************************

!section 9.5.4(10)
!subject     Requeue of protected entry calls
!reference AI95-00148
!reference 96-5581.a Ted Giering 96-5-29
!reference 96-5588.a Robert A Duff 96-5-31
!reference RM95-9.5.4(10-11)
!reference 1997-15741.a Dan Rittersdorf 97-3-31
!from Tucker Taft 97-04-03
!keywords  external requeue
!reference 1997-15742.a Tucker Taft 1997-4-3>>
!discussion

[Bob Duff explains that external requeue causes a nested protected action..]

:    This reasoning is causing a bit of confusion here.  It would seem to
:    contradict ACVC tests such as c954021.a, unless we're misunderstanding
:    how this nesting of protected actions should occur.

:    Consider the first message task c954021.a creates.  It calls
:    Distributer.Input, which immediately requeues on task entry
:    Credit_Computation.Input.  Distributer.Input is completed, finalized,
:    and left, but (as noted above) the protected action continues.
:    Credit_Computation.Input is open and is immediately selected.
:    Credit_Computation.Input immediately makes an external call on
:    Distributer.Credit_Is_Overloaded.

Credit_Computation.Input is a task entry.  The "recursive" call on
Distributor.Credit_is_Overloaded is made by the Credit_Computation task,
not by the task executing the Distributor.Input entry body.  The
"requeuing" on a task entry returns effectively immediately to
the requeuing protected object; no direct recursion is possible when
a task entry is involved, because the accepting task always executes
the rendezvous, never the calling task.

: ... This would attempts to start a
:    new protected action on the current protected object, which is a
:    bounded error, because The Distributer.Input protected action is ongoing.

As explained above, this is not an error, because a different task,
"Credit_Computation," is involved.

:    If the enclosing protected action was not completed as part of the
:    execution of the requeue, prior to the selection and execution of
:    Credit_Computation.Input, then the call to Distributer.Credit_Is_Overloaded
:    will deadlock or raise program_error.

:    The semantics of requeue on a task entry do not appear to allow for the
:    completion of the enclosing protected action prior to selection, so
:    either the test is not valid, or we are confused.

Requeuing on a task entry is effectively "immediate".  No dangerous
"recursion" is possible.

:    Could you comment on the situation in this test?

See above.

: ...

:    Even assuming the test got past the initial message task, it then runs
:    into the situation you and Ted were discussing.  In the second message task,
:    Distributer.Input encounters Credit_Overloaded, and requeues on
:    Hold.Wait_For_Underflow.  This is an external requeue from within an
:    entry body, so as you explain above, the protected actions nest.

:       Lock Distributer
:          Lock Hold
:             ...
:          Unlock Hold
:       Unlock Distributer

:    Hold.Wait_For_Underload is not open, so the caller blocks.
:    There is some question about what should become of the outer protected
:    action on Distributer while the caller blocks on Hold.Wait_for_Underload.
:    When is it completed?  It must be completed prior to Wait_for_Underload
:    becoming open, obviously, but it is not clear how.  The semantics of
:    this nesting of protected actions is not clear from the RM95.

The nested protected action in this case lasts only long enough to requeue
the call on a different protected object's entry.  It is only if
the protected entry is open at the moment of requeue that any recursion
is possible.  If the entry is closed, the requeuing involves nested locking
only long enough to add the call to the target entry queue (and to service
any entry queues whose barriers might be affected by a change in the 'Count
attribute of this entry).

:    Could you please elaborate on your answer in light of this ACVC test?

The ACVC test seems fine, because the only "recursion" is through
task entries, for which there is no problem with nesting of
protected actions.

:    Thank you.

:   Dan.Rittersdorf@mail.ccur.com        or              RittersdorfD@ACM.org
: ______________________________________________________________________________
:   Concurrent Computer Corporation      |               Daniel G. Rittersdorf
:   2101 W. Cypress Creek Rd.            |               178 Washington Street
:   Ft. Lauderdale FL 33309              |               Sparta, MI 49345-1324
:   Ph: +1 (954) 974-1700                |               Ph: +1 (616) 887-5431
: ______________________________________________________________________________

-Tucker Taft   stt@inmet.com

****************************************************************

!section 9.5.4(10)
!subject     Requeue of protected entry calls
!reference 1997-15744.a Dan Rittersdorf 1997-4-3>>
!discussion

   Tucker,

>
> !subject     Requeue of protected entry calls
> !reference AI95-00148
> !reference 96-5581.a Ted Giering 96-5-29
> !reference 96-5588.a Robert A Duff 96-5-31
> !reference RM95-9.5.4(10-11)
> !reference 1997-15741.a Dan Rittersdorf 97-3-31
> !from Tucker Taft 97-04-03
> !keywords  external requeue
> !discussion
>
> [Bob Duff explains that external requeue causes a nested protected action..]
>
> :    This reasoning is causing a bit of confusion here.  It would seem to
> :    contradict ACVC tests such as c954021.a, unless we're misunderstanding
> :    how this nesting of protected actions should occur.
>
> :    Consider the first message task c954021.a creates.  It calls
> :    Distributer.Input, which immediately requeues on task entry
> :    Credit_Computation.Input.  Distributer.Input is completed, finalized,
> :    and left, but (as noted above) the protected action continues.
> :    Credit_Computation.Input is open and is immediately selected.
> :    Credit_Computation.Input immediately makes an external call on
> :    Distributer.Credit_Is_Overloaded.
>
> Credit_Computation.Input is a task entry.  The "recursive" call on
> Distributor.Credit_is_Overloaded is made by the Credit_Computation task,
> not by the task executing the Distributor.Input entry body.  The
> "requeuing" on a task entry returns effectively immediately to
> the requeuing protected object; no direct recursion is possible when
> a task entry is involved, because the accepting task always executes
> the rendezvous, never the calling task.
>

   Perhaps I wasn't clear enough when asking, because this answer doesn't
   quite cover the question at hand.

   The Message_Task's protected action on Distributer must be completed
   prior to blocking in order for the Credit_Computation task to begin
   its action on Distributer.  I certainly understand that a different
   task is making the "recursive" call.  The question at hand is what
   happens to the Message_Task in the interim, and why?

   RM95 9.5.4(8) says that the open call is selected immediately.  The
   acceptor (Credit_Computation) becomes unblocked and executes the entry.
   While doing that, the caller (Message_Task) remains blocked.  It's the
   time between "requeueing" and "blocking" and what occurs during that
   time that I'm confused about.

   RM95 9.5.3(19) makes it clear that the calling task blocks.  There doesn't
   appear to be anything in the RM that says the protected action is
   completed prior to the blocking, except perhaps the physical ordering of
   the rules in 9.5.3 (8-19).

   Does the task executing the Distributor.Input entry body (Message_Task)
   continue to service entry queues and then complete the protected action
   before blocking?  This would lead to extreme complexity.
   Or, does RM95 9.5.3(11) parenthetically imply that the task executing
   the Distributor.Input entry body doesn't service entry queues because it
   completed by a requeue?  Then it still isn't clear that the protected
   action is completed while the Message_Task blocks during rendezvous.

> : ... This would attempts to start a
> :    new protected action on the current protected object, which is a
> :    bounded error, because The Distributer.Input protected action is ongoing.
>
> As explained above, this is not an error, because a different task,
> "Credit_Computation," is involved.
>

   If the Message_Task's protected action on Distributer isn't completed
   while Message_Task is blocked during rendezvous, deadlock would occur.
   Obviously, looking at c954021.a, this isn't intended.  The intended
   semantics aren't obvious from my reading of Chapter 9.

   If the Message_Task's protected action is completed prior to blocking, why?

> :    Even assuming the test got past the initial message task, it then runs
> :    into the situation you and Ted were discussing.  In the second message task,
> :    Distributer.Input encounters Credit_Overloaded, and requeues on
> :    Hold.Wait_For_Underflow.  This is an external requeue from within an
> :    entry body, so as you explain above, the protected actions nest.
>
> :       Lock Distributer
> :          Lock Hold
> :             ...
> :          Unlock Hold
> :       Unlock Distributer
>
> :    Hold.Wait_For_Underload is not open, so the caller blocks.
> :    There is some question about what should become of the outer protected
> :    action on Distributer while the caller blocks on Hold.Wait_for_Underload.
> :    When is it completed?  It must be completed prior to Wait_for_Underload
> :    becoming open, obviously, but it is not clear how.  The semantics of
> :    this nesting of protected actions is not clear from the RM95.
>
> The nested protected action in this case lasts only long enough to requeue
> the call on a different protected object's entry.  It is only if
> the protected entry is open at the moment of requeue that any recursion
> is possible.  If the entry is closed, the requeuing involves nested locking
> only long enough to add the call to the target entry queue (and to service
> any entry queues whose barriers might be affected by a change in the 'Count
> attribute of this entry).

   Again, this is a case where the Message task has requeue'd a call,
   and is about to block waiting for it to become open.

   You note that the Hold entry queue's are serviced whose barriers might
   be affected by the change in 'Count.  The protected action on Hold
   would then be completed?  Does this mean that the caller (Message_Task)
   can be executing other entry bodies on behalf of other callers while
   it is also "blocked" on Hold.Wait_for_Underload?  Perhaps the wording of
   9.5.3(11) is what's confusing me, because it isn't clear to me
   thatt he queues of Hold are serviced after queueing the call to
   Wait_for_Underload.

   Is the protected action on Distributer then completed prior to blocking
   on the call to Hold.Wait_for_Underload?  Again, why?   RM95 9.5.3(18)
   preceeds RM95 9.5.3(19) textually?

   What if the nested entry is open?  Then the outer protected action would
   still remain until the nested entry body completes, and the nested action
   is completed.  Correct?

   In the case of requeue on an open task entry, could the "blocked" caller
   actually be executing other entry bodies on behalf of other "blocked"
   callers instead of being blocked?  At the time that the called task
   completes rendezvous, the caller could be executing, then, and not blocked
   waiting for rendezvous to complete?

--
  Dan.Rittersdorf@mail.ccur.com        or              RittersdorfD@ACM.org
______________________________________________________________________________
  Concurrent Computer Corporation      |               Daniel G. Rittersdorf
  2101 W. Cypress Creek Rd.            |               178 Washington Street
  Ft. Lauderdale FL 33309              |               Sparta, MI 49345-1324
  Ph: +1 (954) 974-1700                |               Ph: +1 (616) 887-5431
______________________________________________________________________________

****************************************************************

[Editor's note: the following appears to be notes appended by the AI author.]

!subject     Requeue of protected entry calls
!reference AI95-00148
!from Stephen Michell 98-04-02
!keywords  external requeue
!discussion
Construct the following to !summary, !question and !response

RM95-9.5.4(7) says that a requeue statement causes
the enclosing entry body to be completed, finalized, and left. This
does not mean that all of the protected operations that originated
with the call have finished.  There are two remaining activities
before the protected object is left and any locks released:
    The lock for the other protected object is acquired and the protected
    entry called, and possibly executed; and
    The other entry barriers are evaluated, and open entries executed
    (either by this task or by another task released as the PO is left).
The order in which these occur have significant implications on the behaviour
of concurrent systems. If the lock on the existing PO is released before the
other PO lock is acquired, then the two operations are not atomic, and other
tasks and entry calls may interleave these activities. If the lock for the
second PO is acquired and the requeue operation operation performed before
the epilogue portion of the first PO is executed, then on a single cpu system,
it is not possible to have a non-atomic operation or deadlock. On a multi-
cpu system, however, scenarios are possible where deadlock occur because
tasks in each PO attempt to requeue to the other PO.

****************************************************************
Notes from ARG mtg 1998 04 in Henley-on-Thames ref AI-148

Stephen is concerned that the wording in 9.5.4(7) will permit the
releasing of the lock on the entry body (the source of the requeue)
before initiating the start of the requeue onto the new entry.  Tuck
and Bob contend that wording for protected action execution and
completion (9.5.1(3-7), 9.5.3(11,18)) make that interpretation not
possible.  They described the sequences of steps that the original
protected action must follow in doing a requeue.  With a very nice
diagram, they showed that there isn't any other reasonable way for the
sequence of steps to occur other than doing the requeue (as a nested
protected action) before the original protected action is completed
(and its lock is released).

Stephen Michell will go back to the drawing board to record these points.

****************************************************************

Questions? Ask the ACAA Technical Agent