Gem #35: Bounded buffer package in GNAT hierarchy (Part 1)

by Pat Rogers —AdaCore

Let's get started…

The bounded buffer is a classic concurrent programming component exhibiting asynchronous task interactions. The concept is that of a buffer of a fixed size that is accessed by multiple tasks, some inserting items and some removing them, concurrently and asynchronously. Hence the buffer implementation must be protected against race conditions in which the tasks access the implementation in an interleaved manner and thereby corrupt the representation. In addition to this “mutually exclusive access”, the buffer also requires “condition synchronization”, in which callers are kept waiting until the requested buffer has the necessary state. For example, a task cannot remove an item from a buffer when the buffer is empty. Likewise, an item cannot be put into a buffer when the buffer is full.

Prior to Ada 95, programmers wanting to write portable code had to use the rendezvous to achieve mutual exclusion, with guards to implement the condition synchronization, because no other synchronization mechanism was provided by the language. Although the extended rendezvous has a number of advantages and was a step forward in language design, it has significant overhead when compared to lower-level mechanisms such as semaphores, and is a synchronous mechanism as well. (Ada 80 had a built-in “Semaphore” task type, intended to be implemented efficiently and used as the name suggests, but mixing the higher-level rendezvous with the much lower-level semaphore abstraction was considered poor language design.) In addition, the rendezvous is only available between tasks, meaning that the buffer would have to be implemented as a task too, like the accessing threads. As a result, inserting and removing items would involve expensive task switching, which is the primary source of the comparative inefficiency.

The protected type construct added in Ada 95 addresses this issue directly. Protected types provide efficient mutually exclusive access to encapsulated data, with direct expression of condition synchronization when required. Protected types do not define threads of control, so their use does not involve task switching, and although they do more than simple semaphores, their overhead is comparable.

The GNAT hierarchy of packages includes the generic package GNAT.Bounded_Buffers, providing just the sort of abstraction we have in mind, parameterized for general use. The implementation of the bounded buffer will be that of an array, and we will do assignments of the values held within any given buffer, so the generic formal type representing the values is declared as private, but not limited private or indefinite:

generic
   type Element is private;
package GNAT.Bounded_Buffers is

Given this generic formal profile, users can instantiate the generic as required. For example, given an appropriate generic actual parameter type named “Job”, we could instantiate it as follows:

   package Jobs is new GNAT.Bounded_Buffers (Element => Job);

The package declaration contains a pragma Pure so that the generic can be used during library unit elaboration without a potential access-before-elaboration problem. That effect is achieved because Pure units are preelaborated, in addition to other semantics.

Next the package declares the array type used internally in the representation of the bounded buffer type:

   type Content is array (Positive range <>) of Element;

The array type must be declared outside the protected type, rather than inside in the private part as a hidden implementation artifact. This is an unfortunate holdover from the fact that protected types were originally named “protected records”, with record type semantics: record types cannot declare such things as other types! This limitation was known during the Ada 2005 revision but other revision aspects were more important, so this undesirable restriction remains.

The next declaration in the package is a constant value of type System.Priority:

   Default_Ceiling : constant System.Priority := System.Default_Priority;

In a real-time application using the Real-Time Systems Annex, protected types are given a “ceiling” priority. The constant declared here is a default for that purpose so that applications not using that Annex can ignore this aspect.

Finally the package declares the protected type itself, with two discriminants:

   protected type Bounded_Buffer
      (Capacity : Positive;
       Ceiling  : System.Priority)
   is
      pragma Priority (Ceiling);

The first discriminant is the capacity of the instance object, that is, the maximum number of values it can contain. This value will be used in the declaration of a hidden array object of type Content. With this approach, different objects of the one buffer type can have different capacities. The second discriminant represents the ceiling priority value, used in the pragma Priority. This is where the Default_Ceiling constant would be used in non-real-time applications. Note that we cannot use the Default_Ceiling constant as a default discriminant value because the language does not allow some discriminants to have defaults unless all have defaults.

Continuing with our “Jobs” example instantiation, declaration of a bounded buffer specifies these discriminant values:

   Buffer : Jobs.Bounded_Buffer (Capacity => 20,
                                 Ceiling => Jobs.Default_Ceiling);

In this example we have arbitrarily set the capacity of Buffer to 20. Note that the Bounded_Buffer type is provided directly as a protected type, rather than as a limited private type completed with a protected type. With this approach, clients have full flexibility to do all that protected types allow, such as timed and conditional calls.

Next the protected type declares the visible operations. The two primary operations are Insert and Remove, defined as entries for the sake of the barriers that specify the required condition synchronization. (Only protected entries can have barriers, unlike protected procedures and functions.) The barriers express the “not full” and “not empty” conditions and keep their callers waiting until those conditions hold.

      entry Insert (Item : Element);
      entry Remove (Item : out Element);

Then three functions are declared. The names “Empty” and “Full” describe the purpose of the first two functions. The third, “Extent”, returns the number of elements currently held in the buffer. It is worth noting that the state of a buffer to which these functions may be applied can change immediately after the call returns.

      function Empty return Boolean;
      function Full return Boolean;
      function Extent return Natural;

In part two of this Gem we will explore the private part of the protected type, the package body, and the body of the protected type.

Related Source Code

Ada Gems example files are distributed by AdaCore and may be used or modified for any purpose without restrictions.

About the Author