Version 1.1.1.1 of ais/ai-00148.txt

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

!standard 09.05.04 (07)          97-08-19 AI95-00148/00
!class confirmation 96-06-06
!status received 96-06-06
!priority Low
!difficulty Easy
!subject Requeue of protected entry calls
!summary 96-06-06
!question 96-06-06
!response 96-06-06
!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
______________________________________________________________________________

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

Questions? Ask the ACAA Technical Agent