next up previous contents index
Next: 17. Time and Clocks Up: IV. Fourth Part: Run-Time Previous: 15. The Rendezvous   Contents   Index


16. Protected Objects

The high burden of threads synchronization required by the Ada rendezvous was inappropriate for the implementation of Systems with fast response-time requirements. For this reason, Ada 95 has a more efficient tasking synchronization mechanism based on shared memory: the Protected Objects. Protected procedures and entries must be executed under read/write locks; however, because protected functions are not permitted to affect the state of the protected object, they can be execute under read-only locks, which permits an implementation to execute several calls to protected functions in parallel.

To issue a call to a protected object, a task simply names the object and the required subprogram or entry. As with task entry calls, the caller can use the select statement to issue a timed or conditional entry call. Clearly, it is possible for more than one task to be queued on a particular protected entry. As with task queues, a protected entry is, by default, ordered in a first-in-first-out fashion; however, if the Real-Time Systems Annex is being supported, other queuing disciplines are allowed. When a call on a protected procedure or protected entry is executed, the barrier is evaluated; if the barrier is closed (evaluates to False), the call is queued. Any exception raised during the evaluation of a barrier results in Program_Error being raised in all tasks currently waiting on the entry queues associated with the protected object containing the barrier [BW98, Chapter 7.8]).

When the execution of a protected procedure or entry is completed, all the barriers are re-evaluated and, potentially, entry bodies are executed. After executing the body of one protected procedure or entry all the PO barriers which have queued tasks are reevaluated. If some entry is now open the entry call is accepted and the corresponding entry body is executed. This process repeats until there is no barrier with queued tasks open. If several barriers are open after the execution of a protected procedure or entry Ada does not specify which entry is then serviced.

Chapter 11 not only discusses the expansion of protected-type, barriers, and protected subprograms, but also presents the two main implementation models for protected objects, self-service and proxy, as well as the proposed implementations (cf. Section 11.1). As it is discussed there, GNAT follows the call-back implementation of the proxy model. One of the main reasons (from the viewpoint of the run-time) is that using Pthreads to implement the self-service model introduces one important 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.

16.1 The Lock

According to Ada semantics, a queued entry call has precedence over other operations on the protected object. This is often explained in terms of the eggshell model. The lock on a protected object is the eggshell. Figure 16.1 is a graphical representation of the protected objects. Threads are represented by shadowed circles; the two levels of the protected objects are represented by means of a big circle (associated with the object lock) and a big rectangle (associated with the object state and operations); small rectangles represent the protected operations: black rectangles represent closed entries and white rectangles represent open entries. Accordingly, this example presents one thread executing a protected operation (it is inside the PO), two threads queued in a closed entry, one thread queued in the entry which is now being executed under mutual-exclusion, and some additional threads which are not queued.

Figure 16.1: Graphical Representation of the Protected Object.

16.2 Run-Time Subprograms

16.2.1 GNARL.Protected_Entry_Call

A simple call to a protected entry is expanded by the front-end into a call to the GNARL subprogram Protected_Entry_Call. The entry-call is handled by the run-time similar to task entry-calls (cf. Section 15.5.4). This facilitates the implementation of the Ada requeue statement. Its whole sequence of actions is as follows:

  1. Defer the abortion.

  2. Write lock the object.

  3. Elaborate a new Entry Call Record.

  4. Call the GNARL procedure PO_Or_Queue to issue the call or to enqueue it in the corresponding entry queue.

  5. Call the GNARL procedure PO_Service_Entries to service the opened entries.

  6. Unlock the object.

  7. Undefer the abortion.

  8. Check if some exception must be re-raised.

In case of conditional and timed entry calls, the actions carried out by the GNAT run-time are basically the sequence presented above. However, if the barrier is closed the entry-call record is not enqueued, and the run-time sets to 0 the index of the selected entry. This value is used by the expanded code to execute the else part of the conditional entry call.

16.2.2 GNARL.PO_Do_Or_Queue

The sequence of actions carried out by PO_Do_Or_Queue is as follows:

  1. Call the barrier function.

  2. If the barrier is closed then enqueue the Entry Call Record, and RETURN.

  3. If the barrier is open then execute the steps 2 to 9 of the GNARL procedure Service_Entries.

16.2.3 GNARL.Service_Entries

The run-time must evaluate the entry-barriers after executing a protected procedure or entry, essentially treating the barrier expression as though they depended only on the state of the protected object. In the self-service model, only when the barriers of all entries with queued calls are False the thread can leave the eggshell. This assures that all entry calls made eligible by a state change are executed before any further operations are initiated. For this purpose, the front-end expands the entry barriers and bodies into functions and procedures, and generates a table initialized with their addresses. The run-time receives this table and uses the pointers to call the functions which evaluate the entry barriers, and to call the corresponding body when the barrier is open.

The basic algorithm of the GNARL Service_Entries procedure is as follows:

1 while <There_Is_Some_Open_Barrier_With_Que...
9 GNARL.Wake_Up_Entry_Caller
10 end loop;

Line 1 is evaluated by the GNARL procedure Select_Protected_Entry_Call 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 again executed and the entry barriers are reevaluated. This process stops when no open barrier is found in an entry with queued tasks.

16.3 Summary

In this chapter we have briefly presented the sequence of actions carried out by the run-time subprograms which give support to protected subprograms.

next up previous contents index
Next: 17. Time and Clocks Up: IV. Fourth Part: Run-Time Previous: 15. The Rendezvous   Contents   Index
(C) Javier Miranda and Edmond Schonberg, 2004