!topic LSN027 on Task Rendezvous in terms of PRs $Revision: 1.1 $ !reference mail from Robert Dewar 91-09-24 !from Tucker Taft $Date: 92/02/11 12:57:19 $ !discussion In September, Robert asked us to investigate whether the semantics of protected records can be described in terms of tasking semantics. We chose to turn the question around, and attempt to indicate the correspondence between tasking semantics and protected record semantics by defining the semantics of rendezvous using protected record operations. Here is a copy (with some minor edits) of our response, formulated as an LSN for future reference. Defining rendezvous semantics in terms of protected records is useful for various purposes. It shows some of the power of protected records (including barrier expressions, entry families, requeue, etc). It shows why rendezvous is a useful "high-level" primitive, since emulating it using only the "lower-level" PR primitives is doable, but still a fair amount of work (hence there is not as much "redundancy" as one might think). Finally, it can help in simplifying the reference manual, by allowing us to use correspondences in semantics to minimize the number of rules. ------------------------------ It is straightforward to explain the semantics of rendezvous in terms of protected records. See below for the details. At the highest level, the semantics of rendezvous in terms of PRs are as follows: A rendezvous is a synchronous bi-directional communication between two tasks. The caller waits twice, once for the message to be accepted, and once (requeued, unabortable) for the reply to be complete. The acceptor waits for a message to arrive, handles it, and then provides a reply/acknowledgment. When the caller or acceptor waits, it is as though it were on a protected record entry queue, whose barrier controls when the task is resumed. The last sentence is the one which establishes the important correspondence between rendezvous and PR entry calls. A more implementation-oriented description of the model is as follows: A task entry call becomes a PR entry call on a "TCB" protected record object, with requeue used to suspend the caller while the rendezvous is performed by the acceptor. An accept also turns into protected operations on the TCB, to open the appropriate entries, wait for a caller, and then indicate end-of-rendezvous (releasing the caller from their requeue). This model of the TCB (or simply the "task object") as a protected record works quite well, with task entry calls and accepts turned into protected operations on the TCB. Tasks are still the only way to get a thread of control. However, a rendezvous is seen as a higher level, tightly-synchronized communication mechanism, implementable using the TCB as the intermediary protected record. One nice thing about this model is that essentially all conventional implementations of tasking *do* use a TCB object to coordinate a rendezvous. Of course, a few have hardware support for rendezvous, but most rely on data-oriented synchronization (aka protected-record-like capabilities) to implement the rendezvous. This also helps explain/rationalize the difference between a "task" and a "task object." The task "object" is the TCB object (essentially), whereas the task corresponds to the abstract thread of control. -Tuck =========================================== Here is the detailed model of rendezvous in terms of protected records: For each task, there is a protected record (let's call it the "TCB" -- task control block -- for now) which represents the task. For each entry of the task, there is a corresponding entry in the TCB. There are also other protected operations: TCB.Set_Entries_Open(Bit_Vector_Of_Open_Entries, Is_Terminable) procedure used by accept/selective-accept TCB.Wait_For_Caller(Call_Info) entry used by accept/selective-accept TCB.Close_Entries(Call_Info) procedure used to close open entries (e.g. on timeout, abort, etc.) Call_Info /= null if caller already accepted. TCB.Is_Callable, TCB.Is_Terminated functions corresponding to attribs TCB.Set_Uncallable, TCB.Set_Terminated procedures used to set attributes TCB.Wait_For_End_Rendezvous (private) entry used for requeue while caller task awaits end of rendezvous TCB.End_Of_Rendezvous procedure used to indicated rendezvous is complete; OUT params or exception indication already stored in Call_Info A call on a task entry becomes a call on the corresponding TCB entry, with parameters passed in a "Call_Info" parameter block, and whose barrier indicates whether the entry is open. An accept statement becomes a call on Set_Entries_Open and then a call on Wait_For_Caller. The barrier for Wait_For_Caller is "TCB.Call_Info /= null" indicating that there is a caller ready. The entry body for a TCB entry corresponding to a task entry does the following: Close all entries; Store reference to Call_Info in TCB; Requeue (without abort allowed) on TCB.Wait_For_End_Rendezvous. The body of the accept statement uses the Call_Info returned by Wait_For_Caller to reference the actual parameters. It updates Call_Info appropriately to hold OUT params or exception indication, and then calls TCB.End_Of_Rendezvous to release the caller. ========================================= Here is the approximate code for a TCB protected record: protected type TCB(Num_Entries : Natural) is entry Task_Entry(1..Num_Entries) (Call_Info : Entry_Call_Info_Ptr); -- entries corresponding to task entries procedure Set_Entries_Open( Bit_Vector_Of_Open_Entries : Bool_Array; Is_Terminable : Boolean); -- procedure used by accept/selective-accept entry Wait_For_Caller(Call_Info : out Entry_Call_Info_Ptr) -- entry used by accept/selective-accept procedure Close_Entries(Call_Info : out Entry_Call_Info_Ptr) -- procedure used to close open entries (e.g. on timeout, abort, etc.) -- Call_Info /= null if caller already accepted. function Is_Callable return Boolean; function Is_Terminated return Boolean; -- functions corresponding to attribs procedure Set_Uncallable; procedure Set_Terminated; -- procedures used to set attributes procedure End_Of_Rendezvous; -- procedure used to indicated rendezvous is complete; -- OUT params or exception indication already stored in Call_Info private entry Wait_For_End_Rendezvous; -- (private) entry used for requeue while caller task -- awaits end of rendezvous record Open_Entries : Bool_Array(1..Num_Entries) := (others => False); Callable : Boolean := True; Terminated : Boolean := False; Current_Call_Info : Entry_Call_Info_Ptr := null; end TCB; protected body TCB is entry Task_Entry(for Entry_Index in 1..Num_Entries) (Call_Info : Entry_Call_Info_Ptr) when Open_Entries(Entry_Index) or not Callable is -- entries corresponding to task entries begin if not Callable then raise Tasking_Error; end if; Open_Entries := (others => False); Current_Call_Info := Call_Info; requeue Wait_For_End_Rendezvous; end Task_Entry; procedure Set_Entries_Open( Bit_Vector_Of_Open_Entries : Bool_Array; Is_Terminable : Boolean) is -- procedure used by accept/selective-accept begin Open_Entries := Bit_Vector_Of_Open_Entries; -- Is_Terminable not handled yet... ;-) end Set_Entries_Open; entry Wait_For_Caller(Call_Info : out Entry_Call_Info_Ptr) when Current_Call_Info /= null is -- entry used by accept/selective-accept begin Call_Info := Current_Call_Info; end Wait_For_Caller; procedure Close_Entries(Call_Info : out Entry_Call_Info_Ptr) is -- procedure used to close open entries (e.g. on timeout, abort, etc.) -- Call_Info /= null if caller already accepted. begin Open_Entries := (others => False); Call_Info := Current_Call_Info; end Close_Entries; function Is_Callable return Boolean is -- function corresponding 'CALLABLE begin return Callable; end Is_Callable; function Is_Terminated return Boolean is -- function corresponding to 'TERMINATED begin return Terminated; end Is_Terminated; procedure Set_Uncallable is -- procedure to set 'CALLABLE to false begin Callable := False; end Set_Uncallable; procedure Set_Terminated is -- procedure to set 'TERMINATED to true (and 'CALLABLE to false) begin Terminated := True; Callable := False; end Set_Terminated; procedure End_Of_Rendezvous is -- procedure used to indicated rendezvous is complete; -- OUT params or exception indication already stored in Call_Info begin Current_Call_Info := null; -- This releases waiting caller end End_Of_Rendezvous; entry Wait_For_End_Rendezvous when Current_Call_Info = null; -- (private) entry used for requeue while caller task -- awaits end of rendezvous end TCB; =================================== It is worth adding that there are several other data structures associated with Ada tasking which are easy to represent using protected records. In particular, one can represent a task master using a PR, which includes a list of dependent TCBs, and a count of the number of non-terminable dependents. One can also represent a task activation barrier, with a count of number of tasks still in the middle of activation, and a boolean to keep track of whether any task died due to an unhandled exception prior to completing activation. Here, for example, is a possible representation for an activation barrier: protected type Activation_Barrier is procedure Initialize_Barrier(Count : Natural); -- Initializes count of tasks to be activated entry Wait_For_Activations; -- Suspends until all to-be-activated tasks complete activation. -- Raises TASKING_ERROR if any one of them failed -- during activation due to an unhandled exception procedure Activation_Complete(Unhandled_Exception : Boolean); -- Decrement count of to-be-activated tasks -- Unhandled_Exception is true if task died during -- its activation due to an unhandled exception. -- It is false if task is aborted or completes activation -- normally. private record To_Be_Activated_Count : Natural := 0; Some_Unhandled_Exception : Boolean := False; end Activation_List; protected body Activation_Barrier is procedure Initialize_Barrier(Count : Natural) is -- Initializes count of tasks to be activated begin To_Be_Activated_Count := Count; Some_Unhandled_Exception := False; end Initialize_Barrier; entry Wait_For_Activations when To_Be_Activated_Count = 0 is -- Suspends until all to-be-activated tasks complete activation. -- Raises TASKING_ERROR if any one of them failed -- during activation due to an unhandled exception begin if Some_Unhandled_Exception then raise TASKING_ERROR; end if; end Wait_For_Activations; procedure Activation_Complete(Unhandled_Exception : Boolean) is -- Decrement count of to-be-activated tasks -- Unhandled_Exception is true if task died during -- its activation due to an unhandled exception. -- It is false if task is aborted or completes activation -- normally. begin To_Be_Activated_Count := To_Be_Activated_Count - 1; if Unhandled_Exception then -- Some task failed, so ensure TASKING_ERROR is raised later Some_Unhandled_Exception := True; end if; end Activation_Complete; end Activation_Barrier; ======================================== One significant advantage of actually implementing the upper layers of a tasking run-time system using protected records is that the implementation would be "naturally" multi-threaded. Protected records "encourages" small-granularity locking, which is the key to a multi-threaded kernel.