Ada 95 QUALITY AND STYLE Guide Chapter 6 (Part 1 of 2)

Ada 95 Quality and Style Guide Chapter 6

CHAPTER 6
Concurrency

CHAPTER 6 Concurrency
6.1 CONCURRENCY OPTIONS
6.2 COMMUNICATION
6.3 TERMINATION
6.4 SUMMARY

Concurrency exists as either apparent concurrency or real concurrency. In a single processor environment, apparent concurrency is the result of interleaved execution of concurrent activities. In a multiprocessor environment, real concurrency is the result of overlapped execution of concurrent activities.

Concurrent programming is more difficult and error prone than sequential programming. The concurrent programming features of Ada are designed to make it easier to write and maintain concurrent programs that behave consistently and predictably and avoid such problems as deadlock and starvation. The language features themselves cannot guarantee that programs have these desirable properties. They must be used with discipline and care, a process supported by the guidelines in this chapter.

The correct usage of Ada concurrency features results in reliable, reusable, and portable software. Protected objects (added in Ada 95) encapsulate and provide synchronized access to their private data (Rationale 1995, §II.9). Protected objects help you manage shared data without incurring a performance penalty. Tasks model concurrent activities and use the rendezvous to synchronize between cooperating concurrent tasks. Much of the synchronization required between tasks involves data synchronization, which can be accomplished most efficiently, in general, using protected objects. Misuse of language features results in software that is unverifiable and difficult to reuse or port. For example, using task priorities or delays to manage synchronization is not portable. It is also important that a reusable component not make assumptions about the order or speed of task execution (i.e., about the compiler's tasking implementation).

Although concurrent features such as tasks and protected objects are supported by the core Ada language, care should be taken when using these features with implementations that do not specifically support Annex D
(Real-Time Systems). If Annex D is not specifically supported, features required for real-time applications might not be implemented.

Guidelines in this chapter are frequently worded "consider . . ." because hard and fast rules cannot apply in all situations. The specific choice you make in a given situation involves design tradeoffs. The rationale for these guidelines is intended to give you insight into some of these tradeoffs.

6.1 CONCURRENCY OPTIONS

Many problems map naturally to a concurrent programming solution. By understanding and correctly using the Ada language concurrency features, you can produce solutions that are largely independent of target implementation. Tasks provide a means, within the Ada language, of expressing concurrent, asynchronous threads of control and relieving programmers from the problem of explicitly controlling multiple concurrent activities. Protected objects serve as a building block to support other synchronization paradigms.

Tasks cooperate to perform the required activities of the software. Synchronization and mutual exclusion are required between individual tasks. The Ada rendezvous and protected objects provide powerful mechanisms for both synchronization and mutual exclusion.

6.1.1 Protected Objects

guideline

Consider using protected objects to provide mutually exclusive access to data.
Consider using protected objects to control or synchronize access to data shared by multiple tasks.
Consider using protected objects to implement synchronization, such as a passive resource monitor.
Consider encapsulating protected objects in the private part or body of a package.
Consider using a protected procedure to implement an interrupt handler.
Do not attach a protected procedure handler to a hardware interrupt if that interrupt has a maximum priority greater than the ceiling priority assigned to the handler.
Avoid the use of global variables in entry barriers.
Avoid the use of barrier expressions with side effects.

example


generic

   type Item is private;

   Maximum_Buffer_Size : in Positive;

package Bounded_Buffer_Package is



   subtype Buffer_Index is Positive range 1..Maximum_Buffer_Size;

   subtype Buffer_Count is Natural  range 0..Maximum_Buffer_Size;

   type    Buffer_Array is array (Buffer_Index) of Item;



   protected type Bounded_Buffer is

      entry Get (X : out Item);

      entry Put (X : in Item);

   private

      Get_Index : Buffer_Index := 1;

      Put_Index : Buffer_Index := 1;

      Count     : Buffer_Count := 0;

      Data      : Buffer_Array;

   end Bounded_Buffer;



end Bounded_Buffer_Package;



------------------------------------------------------------------

package body Bounded_Buffer_Package is



   protected body Bounded_Buffer is



      entry Get (X : out Item) when Count > 0 is

      begin

         X := Data(Get_Index);

         Get_Index := (Get_Index mod Maximum_Buffer_Size) + 1;

         Count := Count - 1;

      end Get;



      entry Put (X : in Item) when Count < Maximum_Buffer_Size is

      begin

         Data(Put_Index) := X;

         Put_Index  := (Put_Index mod Maximum_Buffer_Size) + 1;

         Count := Count + 1;

      end Put;



   end Bounded_Buffer;



end Bounded_Buffer_Package;

rationale

Protected objects are intended to provide a "lightweight" mechanism for mutual exclusion and data synchronization. You should use a task only when you need to introduce explicitly a new, concurrent thread of control (see Guideline 6.1.2).

Protected objects offer a low overhead, efficient means to coordinate access to shared data. A protected type declaration is similar to a program unit and consists of both a specification and a body. The data to be protected must be declared in the specification, as well as the operations that can be used to manipulate this data. If some operations are only allowed conditionally, entries must be provided. Ada 95 rules require that entry barriers be evaluated at the end of procedure calls and entry calls on protected objects. Entry barriers should avoid referring to global variables so that the underlying assumptions of the state of the protected object are not violated. Protected procedures and entries should be used to change the state of a protected object.

Most clients of an abstraction do not need to know how it is implemented, whether it is a regular abstraction or a shared abstraction. A protected type is inherently a limited type, and you can use protected types to implement a limited private type exported by a package. As pointed out in Guideline 5.3.3, abstractions are best implemented using private types (possibly derived from controlled types) or limited private types, providing appropriate operations that overcome the restrictiveness imposed by the use of private types.

The Rationale (1995, §9.1) describes the interrupt handling features that make the protected procedure the recommended building block:

A protected procedure is very well suited to act as an interrupt handler for a number of reasons; they both typically have a short bounded execution time, do not arbitrarily block, have a limited context and finally they both have to integrate with the priority model. The nonblocking critical region matches the needs of an interrupt handler, as well as the needs of non-interrupt-level code to synchronize with an interrupt handler. The entry barrier construct allows an interrupt handler to signal a normal task by changing the state of a component of the protected object and thereby making a barrier true.

When using protected procedures for interrupt handling, you must ensure that the ceiling priority of the handler is at least as high as the maximum possible priority of the interrupt to be handled. With priority-ceiling locking, the delivery of an interrupt with a higher priority than the ceiling priority of the handler will result in erroneous execution (Ada Reference Manual 1995, §C.3.1).

A global variable could be changed by another task or even by a call of a protected function. These changes will not be acted upon promptly. Therefore, you should not use a global variable in an entry barrier.

Side effects in barrier expressions can cause undesirable dependencies. Therefore, you should avoid the use of barrier expressions that can cause side effects.

See also Guideline .

exceptions

If the client of the abstraction containing the protected object must use a select statement with an entry call, you must expose the protected object on the package interface.

6.1.2 Tasks

guideline

Use tasks to model selected asynchronous threads of control within the problem domain.
Consider using tasks to define concurrent algorithms.
Consider using rendezvous when your application requires synchronous unbuffered communication.

example

The naturally concurrent objects within the problem domain can be modeled as Ada tasks.


-- The following example of a stock exchange simulation shows how naturally

-- concurrent objects within the problem domain can be modeled as Ada tasks.



-------------------------------------------------------------------------



-- Protected objects are used for the Display and for the Transaction_Queue

-- because they only need a mutual exclusion mechanism.



protected Display is

   entry Shift_Tape_Left;

   entry Put_Character_On_Tape (C : in Character);

end Display;



protected Transaction_Queue is

   entry Put (T : in     Transaction);

   entry Get (T :    out Transaction);

   function Is_Empty return Boolean;

end Transaction_Queue;



-------------------------------------------------------------------------



-- A task is needed for the Ticker_Tape because it has independent cyclic

-- activity.  The Specialist and the Investor are best modeled with tasks

-- since they perform different actions simultaneously, and should be

-- asynchronous threads of control.



task Ticker_Tape;



task Specialist is

   entry Buy  (Order : in Order_Type);

   entry Sell (Order : in Order_Type);

end Specialist;



task Investor;

-------------------------------------------------------------------------

task body Ticker_Tape is

   ...

begin

   loop

      Display.Shift_Tape_Left;



      if not More_To_Send (Current_Tape_String) and then

         not Transaction_Queue.Is_Empty

      then

         Transaction_Queue.Get (Current_Tape_Transaction);

         ... -- convert Transaction to string

      end if;



      if More_To_Send (Current_Tape_String) then

         Display.Put_Character_On_Tape (Next_Char);

      end if;



      delay until Time_To_Shift_Tape;

      Time_To_Shift_Tape := Time_To_Shift_Tape + Shift_Interval;

   end loop;

end Ticker_Tape;



task body Specialist is 

   ...



   loop

      select

         accept Buy  (Order : in Order_Type) do

            ...

         end Buy;

         ...

      or

         accept Sell (Order : in Order_Type) do

            ...

         end Sell;

         ...

      else

         -- match orders

         ...

         Transaction_Queue.Put (New_Transaction);

         ...

      end select;

   end loop;



end Specialist;





task body Investor is

   ...

begin



   loop

      -- some algorithm that determines whether the investor

      -- buys or sells, quantity, price, etc



      ...



      if ... then

         Specialist.Buy (Order);

      end if;



      if ... then

         Specialist.Sell (Order);

      end if;

   end loop;



end Investor;

Multiple tasks that implement the decomposition of a large, matrix multiplication algorithm are an example of an opportunity for real concurrency in a multiprocessor target environment. In a single processor target environment, this approach may not be justified due to the overhead incurred from context switching and the sharing of system resources.

A task that updates a radar display every 30 milliseconds is an example of a cyclic activity supported by a task.

A task that detects an over-temperature condition in a nuclear reactor and performs an emergency shutdown of the systems is an example of a task to support a high-priority activity.

rationale

These guidelines reflect the intended uses of tasks. They all revolve around the fact that a task has its own thread of control separate from the main subprogram (or environment task) of a partition. The conceptual model for a task is a separate program with its own virtual processor. This provides the opportunity to model entities from the problem domain in terms more closely resembling those entities and the opportunity to handle physical devices as a separate concern from the main algorithm of the application. Tasks also allow naturally concurrent activities that can be mapped to multiple processors within a partition when available.

You should use tasks for separate threads of control. When you synchronize tasks, you should use the rendezvous mechanism only when you are trying to synchronize actual processes (e.g., specify a time-sensitive ordering relationship or tightly coupled interprocess communication). For most synchronization needs, however, you should use protected objects (see Guideline 6.1.1), which are more flexible and can minimize unnecessary bottlenecks. Additionally, passive tasks are probably better modeled through protected objects than active tasks.

Resources shared between multiple tasks, such as devices, require control and synchronization because their operations are not atomic. Drawing a circle on a display might require that many low-level operations be performed without interruption by another task. A display manager would ensure that no other task accesses the display until all these operations are complete.

6.1.3 Discriminants

guideline

Consider using discriminants to minimize the need for an explicit initialization operation
(Rationale 1995, §9.1).
Consider using discriminants to control composite components of the protected objects, including setting the size of an entry family (Rationale 1995, §9.1).
Consider using a discriminant to set the priority of a protected object (Rationale 1995, §9.1).
Consider using a discriminant to identify an interrupt to a protected object (Rationale 1995, §9.1).
Consider declaring a task type with a discriminant to indicate (Rationale 1995, §9.6):
- Priority, storage size, and size of entry families of individual tasks of a type
- Data associated with a task (through an access discriminant)

example

The following code fragment shows how a task type with discriminant can be used to associate data with a task (Rationale 1995, §9.6):


type Task_Data is

   record

      ...  -- data for task to work on

   end record;

task type Worker (D : access Task_Data) is

   ...

end;

-- When you declare a task object of type Worker, you explicitly associate this task with

-- its data through the discriminant D

Data_for_Worker_X : aliased Task_Data := ...;

X : Worker (Data_for_Worker_X'Access);

The following example shows how to use discriminants to associate data with tasks, thus allowing the tasks to be parameterized when they are declared and eliminating the need for an initial rendezvous with the task:


task type Producer (Channel : Channel_Number; ID : ID_Number);



task body Producer is

begin



   loop



      ... -- generate an item



      Buffer.Put (New_Item);



   end loop;

end Producer;



...



Keyboard : Producer (Channel => Keyboard_Channel, ID => 1);

Mouse    : Producer (Channel => Mouse_Channel,    ID => 2);

The next example shows how an initial rendezvous can be used to associate data with tasks. This is more complicated and more error prone than the previous example. This method is no longer needed in Ada 95 due to the availability of discriminants with task types and protected types:


task type Producer is

   entry Initialize (Channel : in Channel_Number; ID : in ID_Number);

end Producer;



task body Producer is

   IO_Channel  : Channel_Number;

   Producer_ID : ID_Number;

begin



   accept Initialize (Channel : in Channel_Number; ID : in ID_Number) do

      IO_Channel  := Channel;

      Producer_ID := ID;

   end;



   loop



      ... -- generate an item



      Buffer.Put (New_Item);



   end loop;

end Producer;



...



Keyboard : Producer;

Mouse    : Producer;



...



begin

   ...

   Keyboard.Initialize (Channel => Keyboard_Channel, ID => 1);

   Mouse.Initialize    (Channel => Mouse_Channel,    ID => 2);

   ...

rationale

Using discriminants to parameterize protected objects provides a low-overhead way of specializing the protected object. You avoid having to declare and call special subprograms solely for the purpose of passing this information to the protected object.

Task discriminants provide a way for you to identify or parameterize a task without the overhead of an initial rendezvous. For example, you can use this discriminant to initialize a task or tell it who it is (from among an array of tasks) (Rationale 1995, §II.9). More importantly, you can associate the discriminant with specific data. When you use an access discriminant, you can bind the data securely to the task because the access discriminant is constant and cannot be detached from the task (Rationale 1995, §9.6). This reduces and might eliminate bottlenecks in the parallel activation of tasks (Rationale 1995, §9.6).

notes

Using an access discriminant to initialize a task has a potential danger in that the data being referenced could change after the rendezvous. This possibility and its effects should be considered and, if necessary, appropriate actions taken (e.g., copy the referenced data and not rely on the data pointed to by the discriminant after initialization).

6.1.4 Anonymous Task Types and Protected Types

guideline

Consider using single task declarations to declare unique instances of concurrent tasks.
Consider using single protected declarations to declare unique instances of protected objects.

example

The following example illustrates the syntactic differences between the kinds of tasks and protected objects discussed here. Buffer is static, but its type is anonymous. No type name is declared to enable you to declare further objects of the same type.


task      Buffer;

Because it is declared explicitly, the task type Buffer_Manager is not anonymous. Channel is static and has a name, and its type is not anonymous.


task type Buffer_Manager;

Channel : Buffer_Manager;

rationale

The use of anonymous tasks and protected objects of anonymous type avoids a proliferation of task and protected types that are only used once, and the practice communicates to maintainers that there are no other tasks or protected objects of that type. If the need arises later to have additional tasks or protected objects of the same type, then the work required to convert an anonymous task to a task type or an anonymous protected object to a protected type is minimal.

The consistent and logical use of task and protected types, when necessary, contributes to understandability. Identical tasks can be declared using a common task type. Identical protected objects can be declared using a common protected type. Dynamically allocated task or protected structures are necessary when you must create and destroy tasks or protected objects dynamically or when you must reference them by different names.

notes

Though changing the task or protected object from an anonymous type to a declared type is trivial, structural changes to the software architecture might not be trivial. Introduction of multiple tasks or protected objects of the declared type might require the scope of the type to change and might change the behavior of the network of synchronizing tasks and protected objects.

6.1.5 Dynamic Tasks

guideline

Minimize dynamic creation of tasks because of the potentially high startup overhead; reuse tasks by having them wait for new work on some appropriate entry queue.

example

The approach used in the following example is not recommended. The example shows why caution is required with dynamically allocated task and protected objects. It illustrates how a dynamic task can be disassociated from its name:


task type Radar_Track;

type      Radar_Track_Pointer is access Radar_Track;

Current_Track : Radar_Track_Pointer;

---------------------------------------------------------------------

task body Radar_Track is

begin

   loop

      -- update tracking information

      ...

      -- exit when out of range

      delay 1.0;

   end loop;

...

end Radar_Track;

---------------------------------------------------------------------

...

loop

   ...

   -- Radar_Track tasks created in previous passes through the loop

   -- cannot be accessed from Current_Track after it is updated.

   -- Unless some code deals with non-null values of Current_Track,

   -- (such as an array of existing tasks)

   -- this assignment leaves the existing Radar_Track task running with

   -- no way to signal it to abort or to instruct the system to

   -- reclaim its resources.



   Current_Track := new Radar_Track;

   ...

end loop;

rationale

Starting up a task has significant overhead in many implementations. If an application has a need for dynamically created tasks, the tasks should be implemented with a top-level loop so that after such a task completes its given job, it can cycle back and wait for a new job.

You can use dynamically allocated tasks and protected objects when you need to allow the number of tasks and protected objects to vary during execution. When you must ensure that tasks are activated in a particular order, you should use dynamically allocated tasks because the Ada language does not define an activation order for statically allocated task objects. In using dynamically allocated tasks and protected objects, you face the same issues as with any use of the heap.

6.1.6 Priorities

guideline

Do not rely on pragma Priority unless your compiler supports the Real-Time Annex (Ada Reference Manual 1995, Annex D) and priority scheduling.
Minimize risk of priority inversion by use of protected objects and ceiling priority.
Do not rely upon task priorities to achieve a particular sequence of task execution.

example

For example, let the tasks have the following priorities:


task T1 is

   pragma Priority (High);

end T1;



task T2 is

   pragma Priority (Medium);

end T2;



task Server is

   entry Operation (...);

end Server;



----------------------------

task body T1 is

begin

   ...

   Server.Operation (...);

   ...

end T1;

task body T2 is

begin

   ...

   Server.Operation (...);

   ...

end T2;



task body Server is

begin

   ...

   accept Operation (...);

   ...

end Server;

At some point in its execution, T1 is blocked. Otherwise, T2 and Server might never execute. If T1 is blocked, it is possible for T2 to reach its call to Server's entry (Operation) before T1. Suppose this has happened and that T1 now makes its entry call before Server has a chance to accept T2's call.

This is the timeline of events so far:


T1 blocks

T2 calls Server.Operation

T1 unblocks

T1 calls Server.Operation

-- Does Server accept the call from T1 or from T2?

You might expect that, due to its higher priority, T1's call would be accepted by Server before that of T2. However, entry calls are queued in first-in-first-out (FIFO) order and not queued in order of priority (unless pragma Queueing_Policy is used). Therefore, the synchronization between T1 and Server is not affected by T1's priority. As a result, the call from T2 is accepted first. This is a form of priority inversion. (Annex D can change the default policy of FIFO queues.)

A solution might be to provide an entry for a High priority user and an entry for a Medium priority user.


---------------------------------------------------------------------

task Server is

   entry Operation_High_Priority;

   entry Operation_Medium_Priority;

   ...

end Server;

---------------------------------------------------------------------

task body Server is

begin

   loop

      select

         accept Operation_High_Priority do

            Operation;

         end Operation_High_Priority;

      else  -- accept any priority

         select

            accept Operation_High_Priority do

               Operation;

            end Operation_High_Priority;

         or

            accept Operation_Medium_Priority do

               Operation;

            end Operation_Medium_Priority;

         or

            terminate;

         end select;

      end select;

   end loop;

...

end Server;

---------------------------------------------------------------------

However, in this approach, T1 still waits for one execution of Operation when T2 has already gained control of the task Server. In addition, the approach increases the communication complexity (see Guideline 6.2.6).

rationale

The pragma Priority allows relative priorities to be placed on tasks to accomplish scheduling. Precision becomes a critical issue with hard-deadline scheduling. However, there are certain problems associated with using priorities that warrant caution.

Priority inversion occurs when lower priority tasks are given service while higher priority tasks remain blocked. In the first example, this occurred because entry queues are serviced in FIFO order, not by priority. There is another situation referred to as a race condition. A program like the one in the first example might often behave as expected as long as T1 calls Server.Operation only when T2 is not already using Server.Operation or waiting. You cannot rely on T1 always winning the race because that behavior would be due more to fate than to the programmed priorities. Race conditions change when either adding code to an unrelated task or porting this code to a new target.

You should not rely upon task priorities to achieve an exact sequence of execution or rely upon them to achieve mutual exclusion. Although the underlying dispatching model is common to all Ada 95 implementations, there might be differences in dispatching, queuing, and locking policies for tasks and protected objects. All of these factors might lead to different sequences of execution. If you need to ensure a sequence of execution, you should make use of Ada's synchronization mechanisms, i.e., protected objects or rendezvous.

notes

Work is being done to minimize these problems, including the introduction of a scheduling algorithm known as the priority ceiling protocol (Goodenough and Sha 1988). The priority ceiling protocol reduces the blocking time that causes priority inversion to only one critical region (defined by the entries in a task). The protocol also eliminates deadlock (unless a task recursively tries to access a critical region) by giving a ceiling priority to each task accessing a resource that is as high as the priority of any task that ever accesses that resource. This protocol is based on priority inheritance and, thus, deviates from the standard Ada tasking paradigm, which supports priority ceiling emulation instead of the priority ceiling blocking that occurs with priority inheritance.

Priorities are used to control when tasks run relative to one another. When both tasks are not blocked waiting at an entry, the highest priority task is given precedence. However, the most critical tasks in an application do not always have the highest priority. For example, support tasks or tasks with small periods might have higher priorities because they need to run frequently.

All production-quality validated Ada 95 compilers will probably support pragma Priority. However, you should use caution unless Annex D is specifically supported.

There is currently no universal consensus on how to apply the basic principles of rate monotonic scheduling (RMS) to the Ada 95 concurrency model. One basic principle of RMS is to arrange all periodic tasks so that tasks with shorter periods have higher priorities than tasks with longer periods. However, with Ada 95, it might be faster to raise the priorities of tasks whose jobs suddenly become critical than to wait for an executive task to reschedule them. In this case, priority inversion can be minimized using a protected object with pragma Locking_Policy(Ceiling_Locking) as the server instead of a task.

6.1.7 Delay Statements

guideline

Do not depend on a particular delay being achievable (Nissen and Wallis 1984).
Use a delay until not a delay statement to delay until a specific time has been reached.
Avoid using a busy waiting loop instead of a delay.

example

The phase of a periodic task is the fraction of a complete cycle elapsed as measured from a specified reference point. In the following example, an inaccurate delay causes the phase of the periodic task to drift over time (i.e., the task starts later and later in the cycle):


Periodic:

   loop

      delay Interval;

      ...

   end loop Periodic;

To avoid an inaccurate delay drift, you should use the delay until statement. The following example (Rationale 1995, §9.3) shows how to satisfy a periodic requirement with an average period:


task body Poll_Device is

   use type Ada.Real_Time.Time;

   use type Ada.Real_Time.Time_Span;



   Poll_Time :          Ada.Real_Time.Time := ...; -- time to start polling

   Period    : constant Ada.Real_Time.Time_Span := Ada.Real_Time.Milliseconds (10);

begin

   loop

      delay until Poll_Time;

      ... -- Poll the device

      Poll_Time := Poll_Time + Period;

   end loop;

end Poll_Device;

rationale

There are two forms of delay statement. The delay will cause a delay for at least a specified time interval. The delay until causes a delay until an absolute wake-up time. You should choose the form appropriate to your application.

The Ada language definition only guarantees that the delay time is a minimum. The meaning of a delay or delay until statement is that the task is not scheduled for execution before the interval has expired. In other words, a task becomes eligible to resume execution as soon as the amount of time has passed. However, there is no guarantee of when (or if) it is scheduled after that time because the required resources for that task might not be available at the expiration of the delay.

A busy wait can interfere with processing by other tasks. It can consume the very processor resource necessary for completion of the activity for which it is waiting. Even a loop with a delay can have the impact of busy waiting if the planned wait is significantly longer then the delay interval. If a task has nothing to do, it should be blocked at an accept or select statement, an entry call, or an appropriate delay.

The expiration time for a relative delay is rounded up to the nearest clock tick. If you use the real-time clock features provided by Annex D, however, clock ticks are guaranteed to be no greater than one millisecond (Ada Reference Manual 1995, §D.8).

notes

You need to ensure the arithmetic precision of the calculation Poll_Time := Poll_Time + Period; to avoid drift.

6.1.8 Extensibility and Concurrent Structures

guideline

Carefully consider the placement of components of protected types within a tagged type inheritance hierarchy.
Consider using generics to provide extensibility of data types requiring the restrictions provided by protected objects.

rationale

Once a component of a protected type is added to an inheritance hierarchy of an abstract data type, further extensibility of that data type is impaired. When you constrain the concurrent behavior of a type (i.e., introduce a protected type component), you lose the ability to modify that behavior in subsequent derivations. Therefore, when the need arises for a version of an abstract data type to impose the restrictions provided by protected objects, the opportunity for reuse is maximized by adding the protected objects at the leaves of the inheritance hierarchy.

The reusability of common protected operations (e.g., mutually exclusive read/write operations) can be maximized by using generic implementations of abstract data types. These generic implementations then provide templates that can be instantiated with data types specific to individual applications.

notes

You can address synchronization within an inheritance hierarchy in one of three ways:

You can declare the root as a limited tagged type with a component that belongs to a protected type and give the tagged type primitive operations that work by invoking the protected operations of that component.
Given a tagged type implementing an abstract data type (perhaps resulting from several extensions), you can declare a protected type with a component belonging to the tagged type. The body of each protected operation would then invoke the corresponding operation of the abstract data type. The protected operations provide mutual exclusion.
You can use a hybrid approach where you declare a protected type with a component of some tagged type. You then use this protected type to implement a new root tagged type (not a descendant of the original tagged type).

6.2 COMMUNICATION

The need for tasks to communicate gives rise to most of the problems that make concurrent programming so difficult. Used properly, Ada's intertask communication features can improve the reliability of concurrent programs; used thoughtlessly, they can introduce subtle errors that can be difficult to detect and correct.

6.2.1 Efficient Task Communication

guideline

Minimize the work performed during a rendezvous.
Minimize the work performed in the selective accept loop of a task.
Consider using protected objects for data synchronization and communication.

example

In the following example, the statements in the accept body are performed as part of the execution of both the caller task and the task Server, which contains Operationand Operation2. The statements after the accept body are executed before Server can accept additional calls to Operation or Operation2.


   ...

   loop

      select

         accept Operation do

            -- These statements are executed during rendezvous.

            -- Both caller and server are blocked during this time.

            ...

         end Operation;

         ...

         -- These statements are not executed during rendezvous.

         -- The execution of these statements increases the time required

         --   to get back to the accept and might be a candidate for another task.



      or

         accept Operation_2 do

            -- These statements are executed during rendezvous.

            -- Both caller and server are blocked during this time.

            ...

         end Operation_2;

      end select;

      -- These statements are also not executed during rendezvous,

      -- The execution of these statements increases the time required

      --   to get back to the accept and might be a candidate for another task.



   end loop;

rationale

To minimize the time required to rendezvous, only work that needs to be performed during a rendezvous, such as saving or generating parameters, should be allowed in the accept bodies.

When work is removed from the accept body and placed later in the selective accept loop, the additional work might still suspend the caller task. If the caller task calls entry Operation again before the server task completes its additional work, the caller is delayed until the server completes the additional work. If the potential delay is unacceptable and the additional work does not need to be completed before the next service of the caller task, the additional work can form the basis of a new task that will not block the caller task.

Operations on protected objects incur less execution overhead than tasks and are more efficient for data synchronization and communication than the rendezvous. You must design protected operations to be bounded, short, and not potentially blocking.

notes

In some cases, additional functions can be added to a task. For example, a task controlling a communication device might be responsible for a periodic function to ensure that the device is operating correctly. This type of addition should be done with care, realizing that the response time of the task might be impacted (see the above rationale).

Minimizing the work performed during a rendezvous or selective accept loop of a task can increase the rate of execution only when it results in additional overlaps in processing between the caller and callee or when other tasks can be scheduled due to the shorter period of execution. Therefore, the largest increases in execution rates will be seen in multiprocessor environments. In single-processor environments, the increased execution rate will not be as significant and there might even be a small net loss. The guideline is still applicable, however, if the application could ever be ported to a multiprocessor environment.

6.2.2 Defensive Task Communication

guideline

Provide a handler for exception Program_Error whenever you cannot avoid a selective accept statement whose alternatives can all be closed (Honeywell 1986).
Make systematic use of handlers for Tasking_Error.
Be prepared to handle exceptions during a rendezvous.
Consider using a when others exception handler.

example

This block allows recovery from exceptions raised while attempting to communicate a command to another task:


Accelerate:

   begin

      Throttle.Increase(Step);

   exception

      when Tasking_Error     =>     ...

      when Constraint_Error  =>     ...

      when Throttle_Too_Wide =>     ...

      ...

   end Accelerate;

In this select statement, if all the guards happen to be closed, the program can continue by executing the elsepart. There is no need for a handler for Program_Error. Other exceptions can still be raised while evaluating the guards or attempting to communicate. You will also need to include an exception handler in the task Throttle so that it can continue to execute after an exception is raised during the rendezvous:


...

Guarded:

   begin

      select

         when Condition_1 =>

            accept Entry_1;

      or

         when Condition_2 =>

            accept Entry_2;

      else  -- all alternatives closed

         ...

      end select;

   exception

      when Constraint_Error =>

         ...

   end Guarded;

In this select statement, if all the guards happen to be closed, exception Program_Error will be raised. Other exceptions can still be raised while evaluating the guards or attempting to communicate:


Guarded:

   begin

      select

         when Condition_1 =>

            accept Entry_1;

      or

         when Condition_2 =>

            delay Fraction_Of_A_Second;

      end select;

   exception

      when Program_Error     =>  ...

      when Constraint_Error  =>  ...

   end Guarded;

...

rationale

The exception Program_Error is raised if a selective accept statement (select statement containing accepts) is reached, all of whose alternatives are closed (i.e., the guards evaluate to False and there are no alternatives without guards), unless there is an else part. When all alternatives are closed, the task can never again progress, so there is by definition an error in its programming. You must be prepared to handle this error should it occur.

Because an else part cannot have a guard, it can never be closed off as an alternative action; thus, its presence prevents Program_Error. However, an else part, a delay alternative, and a terminate alternative are all mutually exclusive, so you will not always be able to provide an else part. In these cases, you must be prepared to handle Program_Error.

The exception Tasking_Error can be raised in the calling task whenever it attempts to communicate. There are many situations permitting this. Few of them are preventable by the calling task.

If an exception is raised during a rendezvous and not handled in the accept statement, it is propagated to both tasks and must be handled in two places (see Guideline 5.8).

The handling of the others exception can be used to avoid propagating unexpected exceptions to callers (when this is the desired effect) and to localize the logic for dealing with unexpected exceptions in the rendezvous. After handling, an unknown exception should normally be raised again because the final decision of how to deal with it might need to be made at the outermost scope of the task body.

notes

There are other ways to prevent Program_Error at a selective accept. These involve leaving at least one alternative unguarded or proving that at least one guard will evaluate True under all circumstances. The point here is that you or your successors will make mistakes in trying to do this, so you should prepare to handle the inevitable exception.

Chapter 6 Continued

CHAPTER 6 Concurrency

CHAPTER 6 Concurrency 6.1 CONCURRENCY OPTIONS 6.2 COMMUNICATION 6.3 TERMINATION 6.4 SUMMARY

6.1 CONCURRENCY OPTIONS

6.2 COMMUNICATION

CHAPTER 6
Concurrency

CHAPTER 6 Concurrency
6.1 CONCURRENCY OPTIONS
6.2 COMMUNICATION
6.3 TERMINATION
6.4 SUMMARY