CVS difference for ais/ai-00148.txt

Differences between 1.1 and version 1.2
Log of other versions for file ais/ai-00148.txt

--- ais/ai-00148.txt	1998/09/30 00:17:26	1.1
+++ ais/ai-00148.txt	2000/02/14 21:27:55	1.2
@@ -1,21 +1,83 @@
-!standard 09.05.04 (07)                               97-08-19  AI95-00148/00
+!standard 09.05.04 (07)                               00-02-14  AI95-00148/01
 !class confirmation 96-06-06
+!status work item 00-02-14
 !status received 96-06-06
 !priority Low
 !difficulty Easy
 !subject Requeue of protected entry calls
 
-!summary 96-06-06
+!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 operations.
+
+!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 statements 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.
 
-!question 96-06-06
 
+!appendix
 
-!response 96-06-06
-
-
-!appendix 97-08-19
-
 !section 9.5.4(07)
 !subject Requeue of protected entry calls
 !reference RM95-9.5.4(7,11)
@@ -110,8 +172,8 @@
 
 (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, 
+    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, ...
 
@@ -127,7 +189,7 @@
 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
@@ -148,14 +210,14 @@
 !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, 
+>     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.
 
@@ -168,7 +230,7 @@
 > 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.
@@ -202,9 +264,9 @@
 
 Last May, you said:
 >!section 9.5.4(07)
->!subject Requeue of protected entry calls 
+>!subject Requeue of protected entry calls
 >!reference RM95-9.5.4(7,11)
->!reference 96-5581.a Ted Giering 96-5-29 
+>!reference 96-5581.a Ted Giering 96-5-29
 >!reference 96-5588.a Robert A Duff 96-5-31
 >!discussion
 >
@@ -223,15 +285,15 @@
 >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 
+>> 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 
+>> 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
@@ -240,14 +302,14 @@
 >
 
    This reasoning is causing a bit of confusion here.  It would seem to
-   contradict ACVC tests such as c954021.a, unless we're misunderstanding 
+   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 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
@@ -266,13 +328,13 @@
 
    [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 
+>> 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 
+>> 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.
@@ -280,10 +342,10 @@
 >   * Bob
 >
 
-   Even assuming the test got past the initial message task, it then runs 
+   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 
+   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
@@ -292,18 +354,18 @@
          Unlock Hold
       Unlock Distributer
 
-   Hold.Wait_For_Underload is not open, so the caller blocks.  
+   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 
+   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
@@ -329,22 +391,22 @@
 [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 
+:    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 is open and is immediately selected.
 :    Credit_Computation.Input immediately makes an external call on
-:    Distributer.Credit_Is_Overloaded.  
+:    Distributer.Credit_Is_Overloaded.
 
-Credit_Computation.Input is a task entry.  The "recursive" call on 
+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 
+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.
 
@@ -352,7 +414,7 @@
 :    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, 
+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
@@ -373,10 +435,10 @@
 
 : ...
 
-:    Even assuming the test got past the initial message task, it then runs 
+:    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 
+:    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
@@ -385,14 +447,14 @@
 :          Unlock Hold
 :       Unlock Distributer
 
-:    Hold.Wait_For_Underload is not open, so the caller blocks.  
+:    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 
+:    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 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
@@ -427,7 +489,7 @@
 
    Tucker,
 
-> 
+>
 > !subject     Requeue of protected entry calls
 > !reference AI95-00148
 > !reference 96-5581.a Ted Giering 96-5-29
@@ -437,29 +499,29 @@
 > !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 
+> :    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 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 
+> :    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 
+> 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.
@@ -473,12 +535,12 @@
    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 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 
+   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 
+   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)
@@ -492,10 +554,10 @@
 > : ... 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, 
+>
+> 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.
@@ -504,26 +566,26 @@
 
    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 
+> :    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 
+> :    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.  
+>
+> :    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 
+> :    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 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
@@ -531,19 +593,19 @@
 > 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, 
+   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 
+   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 
+   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 
+   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?
 
@@ -553,11 +615,11 @@
 
    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 
+   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
@@ -565,5 +627,52 @@
   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