next up previous contents index
Next: Summary Up: Protected Objects Previous: The Ada 95 Protected Object   Contents   Index

Subsections


GNAT Implementation

Ada does not specify which task executes the entry barrier and the entry body. Protected entry bodies can be executed by any task, regardless of which task made the corresponding entry call [GB94a, Section 5(3)]). Therefore two obvious candidates are (1) the task that called the entry and (2) the task which opens the barrier of the entry [GMB93, Section 3.4]. They are referred to as the Self-Service Model and the Proxy Model of protected entry execution, respectively.

Self-Service Versus Proxy

In the self-service mode4.1 a task exiting a protected object selects a task waiting on an open entry barrier (if any) based on the entry queuing discipline in effect and wakes it up, making it the active task within the eggshell.

In the proxy model, the task exiting the eggshell executes the entry body itself, wakes the calling task and then repeats the check and entry body execution for waiting callers, finally exiting the eggshell when there are no more entry calls waiting on True barriers.

The principal advantages of the self-service model are that it permits more parallelism and simplifies schedulability analysis. Parallelism is increased because on a multiprocessor the exiting task can proceed with its own execution in parallel with the execution of the next queued call. Schedulability analysis is simplified because a thread is allowed to continue with its own execution immediately after the (presumably bounded) time it takes to complete the body of its own protected operation and pass lock ownership to the next queued caller.

The principal advantage of the proxy model is simplicity. If an entry body cannot be executed immediately, the calling task has only to suspend and wait (some other task will be responsible for executing the entry body). More complex features of protected objects, including timed and asynchronous entry calls, are simplified even more by this model. However, schedulability analysis is compromised by this model since a task attempting to exit an eggshell must first execute all of the waiting entry calls whose barriers are open, and there is no language-imposed restriction on the number of such calls that can be pending.

Using Pthreads to implement the self-service model introduces one problem. The task attempting to exit an eggshell must be able to transfer ownership to a task waiting on an Open entry. However, there is no good way to solve it with Pthreads because, though it is possible to force a thread to be given a mutex by raising its priority over that of the other contenders, this may lead to unnecessary context switches and degrades the implementation of Ada priority over Pthreads. Therefore GNAT implements the proxy model.

Proxy Model: In-line Versus Call-Back Implementation

There are two possible implementations of the proxy model: In-line and Call-back. In the In-line implementation the code generated for all the barriers and entry bodies is put by the compiler in a single entry service procedure (cf. Figure [*]). This procedure has a main loop which evaluates all the barriers and calls a GNARL procedure to select the next entry code to be executed (the value 0 is returned when there is no candidate). This service entries procedure is called at the end of any protected action that might result in a change of state in the object.

Figure 4.2: Proxy Model: In-Line Implementation.
\begin{figure}\centerline{\psfig{figure=figures/04-PO/02-inline.eps,
width=14.0cm}}\end{figure}

In the Call-back implementation all the logic required to implement the semantics of the protected objects is moved down to the GNARL level. The compiler translates entry barrier to a function that returns a Boolean datum and translates the entry body to a procedure (cf. Figure [*]). In addition the compiler generates a table with the access to these subprograms. The reference to this table must be given to the Ada run-time.

Figure 4.3: Proxy Model: Call-Back Implementation.
\begin{figure}\centerline{\psfig{figure=figures/04-PO/03-callback.eps,
width=14.0cm}}\end{figure}

Until version 2.04, the in-line implementation was used in GNAT. Then they decided to implement both models and to compare both implementations. Although the in-line implementation allows the compiler to make better optimizations, their results indicated that the call-back interface allows for much simpler translations and eliminates some of the overhead inherent in the in-line interface's frequent alternation between the GNU Ada Run-Time and the application code. The call-back interface also has a big advantage in the simplicity and understandability of both the generated code and the internal logic of the compiler [GB95]. Therefore, the current versions of the GNAT compiler have the call-back implementation.


Protected Type Specification

The GNAT compiler translates the following protected type specification

   protected type PO ( <Discriminants> )is
      procedure P ( <Params> );
      function  F ( <Params> ) return ...;
   private
      <Private_Data>;
   end PO;

...to the following code:

  1: type poV (Discriminants) is new Limited_Controlled with
  2:    record
  3:       <Private_Data>
  4:       _object : aliased GNARL.Protection_Entries ( <Num_Entries> );
  5:    end record;
  6:
  7: procedure Finalize (_object : poV) is
  8: begin
  9:    --  Raise Program_Error to the queued tasks.
 10:    ...
 11: end Finalize;

The protected type specification is translated to a record type declaration (lines 1 to 5). If the protected type has discriminants, the record type has the same discriminants (in order to provide the same semantics). Private data is translated to components of this record (line 3). The additional field _object (line 4) contains all the run-time data required to implement the protected object semantics (the object lock, the entry queues, the object priority, etc. --see the GNARL data type Protection_Entries4.2). It is an aliased component because its access must be passed to the GNU Ada Run-Time. As the reader can see, the record type is Limited_Controlled4.3. These are the reasons:

  1. Limited. Protected objects can not be copied. In this way Ada ensures that the object state can only be modified by its protected operations. This semantics is provided by the Ada limited types.

  2. Controlled. When the object finalizes, the predefined exception exception Program_Error must be raised to all the queued tasks. Therefore, the GNAT compiler automatically generates a procedure which does this work (lines 10 to 14).


Protected Subprograms

For each protected subprogram, the GNAT compiler generates two subprograms: $N$ and $P$. $N$ has the user code. It is only called when the object lock has been acquired. $P$ is responsible to take the lock and to call $N$. This scheme allows a protected subprogram to call another protected subprogram in the same object (in this case the compiler generates a direct call to the corresponding $N$ subprogram). One additional parameter is added by the compiler to the parameters profile of the protected subprograms: the _object. Because protected procedures can modify the object's state, they receive the object as in out mode parameter. Protected functions receive the object as an in mode parameter.

    procedure procN (_object : in out poV; ... );
    procedure procP (_object : in out poV; ... );

The compiler adds some renaming sentences to the declarations of the protected subprograms. These renamings simplify the access to the object discriminant and to the private state.

    procedure procN (_object : in out poV; ... ) is
       <Discriminant_Renamings>
       <Private_Object_Renamings>
    begin
       <Sequence_Of_Statements>
    end procN;

All the sentences of the protected subprograms are properly modified by the compiler to make use of these renamings when the discriminant or the object private data fields are used. Let's see the $P$ subprogram in detail.

  1: procedure procP (_object : in out poV; ... ) is
  2:
  3:   procedure Clean is
  4:   begin
  5:      GNARL.Service_Entries (_object._object'access);
  6:      GNARL.Unlock (_object._object'access);
  7:      GNARL.Abort_Undefer;
  8:   end Clean;
  9:
 10: begin
 11:    GNARL.Abort_Defer;
 12:    GNARL.Lock_Write (_object._object'access);
 13:    procN (_object; ... );
 14:    Clean;
 15: exception
 16:    when others =>
 17:       declare
 18:          E : Exception_Occurrence;
 19:       begin
 20:          GNARL.Save_Occurrence (E, GNARL.Get_Current_Exception);
 21:          Clean;
 22:          GNARL.Reraise (E);
 23:       end;
 24: end procP;

The first actions performed by the $P$ subprogram are to defer the abortion4.4 (line 11) and to lock the object4.5 (line 12). After calling the $N$ subprogram (line 13) we have two possible scenarios:

  1. No exception was raised. In this case the local subprogram Clean is called (line 14) to make the following actions: serve the opened entries with queued tasks (line 5), unlock the protected object (line 6) and undefer the abortion (line 7).

  2. Some exception was raised. In this case, before propagating the exception to the calling task, the protected object must first service the entries with queued tasks (according to the Proxy model). However, the execution of these entries may also raise new exceptions (and the current exception would be lost). Therefore, it is necessary to save the exception occurrence originally raised (line 20) and re-raise it after local subprogram Clean returns.

The GNARL subprogram Service_Entries4.6 will be described in section [*].

Entry Barrier

Each entry barrier expression is translated by the compiler to a function that returns a Boolean type; each entry body is put inside a procedure. A table4.7 is also created by the compiler to store the access these subprograms. This table is used by GNARL to evaluate the entry barriers and to call the selected entry body.


   function EntryBarrier
      (Object       : Address;
       Entry_Index  : Protected_Entry_Index)
      return Boolean
   is
      <Discriminant_Renamings>
      <Private_Object_Renamings>
   begin
     return <Barrier_Expression>;
   end EntryBarrier;

Because all the entry barriers must have the same profile (to create the access table used to implement the call-back) the object parameter is passed by means of an Address parameter.

Entry Body

The entry body is translated by the compiler to a procedure.

  1: procedure EntryName
  2:    (Object      : Address;
  3:     Parameters  : Address;
  4:     Entry_Index : Protected_Entry_Index)
  5: is
  6:    <Discriminant_Renamings>
  7:    <Private_Object_Renamings>
  8:
  9:    type poVP is access poV;
 10:    function To_PoVP is new Unchecked_Conversion (Address, PoVP);
 11:    _object : PoVP := To_PoVP (Object);
 12: begin
 13:    <Statement_Sequence>
 14:    GNARL.Complete_Entry_Body (_object._object);
 15: exception
 16:    when others =>
 17:       GNARL.Exceptional_Complete_Entry_Body
 18:          (_object._object, GNARL.Get_GNAT_Exception);
 19: end EntryName;

The object is again passed by means of an Address parameter (to create the access table used to implement the call-back). Similar to the $N$ subprograms (section [*]), the compiler adds some renamings to facilitate the access to the object discriminant and to the private fields (lines 6 and 7). The compiler also generates the unchecked conversion of the object parameter to the typed object (lines 9 to 11). If no exception is raised by this code, the GNARL subprogram Complete_Entry_Body4.8 is called to notify to the Ada run-time that this entry body has been successfully serviced. Otherwise (some exception was raised) the GNARL subprogram Exceptional_Complete_Entry_Body4.9 is called. This subprogram stores the exception occurrence in the entry call. The exception will be raised by the calling tasks after being woken up.

Entry Family

For each entry family the compiler adds one field to the type declaration which is used to store the bounds of the entry family declaration (the contents of the array are not used).

   type poV (Discriminants) is new Limited_Controlled with
   record
      <Private_Data>
      _object : aliased GNARL.Protection_Entries ( <Num_Entries> );
      Entry_Family_Name : array ( <Bounds> ) of Void;
   end record;


Service Entries

The basic algorithm of the GNARL Service_Entries4.10 procedure is as follows:

  1 while <There_Is_Some_Open_Barrier_With_Queued_Entry_Calls> loop
  2    Update object reference to the Entry_Call_Record
  3    begin
  4      Call the Entry_Body
  5    exception
  6      when others => Broadcast Program_Error
  7    end
  8    Remove the Reference to the Entry_Call_Record
  9    GNARL.Wake_Up_Entry_Caller
 10 end loop;

Line 1 is evaluated by the GNARL procedure Select_Protected_Entry_Call4.11 which traverses all the entry queues and reevaluates the barrier of those entries with queued entry calls. As soon as some barrier is open (it evaluates to true), GNARL selects it to be serviced. In line 2, the Call_In_Progress field of the _object (see the Protection_Entries type definition) is set to the selected entry call record to remember that this is the entry call being attended. Lines 3 to 7 open a new scope to issue the call to the entry body and to handle the exceptions in the user code. In this case the predefined exception Program_Error is broadcasted to all tasks currently queued in any entry of the protected object. In line 8 the reference to the entry call is removed (this entry call has been attended) and the task entry caller is woken up (line 9). After this work the loop is executed again and the entry barriers are reevaluated. This process stops when no open barrier is found in an entry with queued tasks.

Simple Mode Entry Call

A simple call to a protected entry is translated by the compiler to a call to the GNARL subprogram Protected_Entry_Call. The entry calls to protected procedures are handled in a similar way to task entry calls (this facilitates the implementation of the Ada requeue statement). Therefore, one Entry_Call_Record of the Entry Calls Stack is used to issue the entry call.

Conditional Mode Entry Call

In this case the actions carried out by the GNAT run-time are basically the same as in the previous case; however, if the barrier is closed the Entry Call Record is not enqueued and the else part of the conditional entry call is executed.



Footnotes

... mode4.1
The contents of this section are a summary of [GMB93].
...Protection_Entries4.2
System.Tasking.Protected_Objects.Entries
... Limited\_Controlled4.3
Ada.Finalization
... abortion4.4
System.Tasking.Initialization.Defer_Abort
... object4.5
System.Tasking.Protected_Objects.Entries.Lock_Entries
...Service_Entries4.6
System.Tasking.Protected_Objects.Entries
...table4.7
The data type of this table is System.Tasking.Protected_Objects.Protected_Entry_Body_Array
...Complete_Entry_Body4.8
System.Tasking.Protected_Objects.Operations.Complete_Entry_Body
...Exceptional_Complete_Entry_Body4.9
System.Tasking.Protected_Objects.Operations.Exceptional_Complete_Entry_Body
...Service_Entries4.10
System.Tasking.Protected_Objects.Entries.Service_Entries
...Select_Protected_Entry_Call4.11
System.Tasking.Queueing.Select_Protected_Entry_Call
...Protected_Entry_Call4.12
System.Tasking.Protected_Objects.Operations.Protected_Entry_Call
... Record4.13
System.Tasking.Entry_Call_Record
... PO_Service_Entries4.14
System.Tasking.Protected_Objects.PO_Service_Entries
...PO_Do_Or_Queue4.15
System.Tasking.Protected_Objects.PO_Do_Or_Queue

next up previous contents index
Next: Summary Up: Protected Objects Previous: The Ada 95 Protected Object   Contents   Index
(c) Javier Miranda. Canary Islands (Spain), 2002. Version 1.0