Semantics of requeue

Semantics of requeue

[Moti Ben-Ari]

I have a question on the semantics of requeue:

When a requeue is done on an "internal" entry of a protected object,
it is clear that the caller is queued as part of the
"on-going protected action" (LRM 9.5.4(10)).
This prevents nasty race conditions, as shown in many
published examples of concurrent programs written in Ada 95.

However, I am uncertain exactly what is supposed to happen when
a requeue is done on an entry of another protected object or
on an entry of a task.
Specifically, suppose task T1 executing PO.E requeues on entry T2.E.
Is it possible that between the end of the
protected action PO.E, and the (re-)queueing of the caller T1
on the entry T2.E, another task T3 could execute T2.E and
"jump the queue" (assuming default FIFO scheduling)?

LRM 9.5.4(7-8) says:

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,
as for a normal entry call (see 9.5.3).

Thus I am asking: are paragraphs 7-8 part of a single atomic
statement, or can the scheduler preempt a task between 7 and 8.

Thanks

Moti Ben-Ari

Dr. Mordechai (Moti) Ben-Ari
Dept. of Science Teaching, Weizmann Institute of Science
Rehovot 76100 Israel, Tel: 972-8-934-2940. Fax: 972-8-934-4174.
ntbenari@wis.weizmann.ac.il

Re: Semantics of requeue

[Tucker Taft]

Moti Ben-Ari (ntbenari@wis.weizmann.ac.il) wrote:
: I have a question on the semantics of requeue:

: When a requeue is done on an "internal" entry of a protected object,
: it is clear that the caller is queued as part of the
: "on-going protected action" (LRM 9.5.4(10)).
: This prevents nasty race conditions, as shown in many
: published examples of concurrent programs written in Ada 95.

: However, I am uncertain exactly what is supposed to happen when
: a requeue is done on an entry of another protected object or
: on an entry of a task.
: Specifically, suppose task T1 executing PO.E requeues on entry T2.E.
: Is it possible that between the end of the
: protected action PO.E, and the (re-)queueing of the caller T1
: on the entry T2.E, another task T3 could execute T2.E and
: "jump the queue" (assuming default FIFO scheduling)?

No.  If anything, "external" requeue is *more* "atomic" than
"internal" requeue.  LRM 9.5.4(11) indicates that the protected
action for an external requeue on a protected object happens
nested within the protected action which performed the requeue,
immediately after leaving the requeuing entry body, but
*before* ending the protected action associated with the
requeuing entry body.  For an "internal" requeue, only the
(re)queuing happens immediately after leaving the requeuing
entry body, never the execution of the target entry body.

For an internal requeue, it is not appropriate to immediately 
execute the target entry body, since the target 
entry queue might already have things on it in front
of the requeued call, even if the associated barrier is true.  
For an external requeue on a protected object, if the barrier for 
the target entry queue is true, then there would not be any calls 
already on it, so it makes sense to immediately execute the
target entry body.

As far as requeuing from a protected object onto a task entry, 
this is clearly always "external," so there is no problem
doing the requeuing or "selection" immediately after leaving
the requeuing entry body (before the protected action ends), but 
the actual rendezvous is performed by the accepting task, so 
that happens at its own pace, depending on the active priority
of the acceptor.

: LRM 9.5.4(7-8) says:

: 7   ... The entry_body or accept_statement enclosing the
: requeue_statement is then completed, finalized, and left (see 7.6.1).

The important thing to realize that leaving an entry_body
does not end the protected action.  That doesn't happen until
after all entry queue servicing happens.

: 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,
: as for a normal entry call (see 9.5.3).

: Thus I am asking: are paragraphs 7-8 part of a single atomic
: statement, or can the scheduler preempt a task between 7 and 8.

Preemption by a higher priority task is always possible.  However,
the important point is that the protected action (presuming the
requeuer is an entry body) is ongoing, and so the lock associated
with the requeuing protected object is still held.

: Thanks

: Moti Ben-Ari

: Dr. Mordechai (Moti) Ben-Ari
: Dept. of Science Teaching, Weizmann Institute of Science
: Rehovot 76100 Israel, Tel: 972-8-934-2940. Fax: 972-8-934-4174.
: ntbenari@wis.weizmann.ac.il

-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Cambridge, MA  USA