Re: Ravenscar-compliant bounded buffer

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Tue, 4 Sep 2007 20:00:13 -0700, Steve wrote:

> While I don't know much about the Ravenscar profile (other than what it is) 
> I am famialar with the use of protected types.
> 
> The sample code is a good illustration of "abstraction inversion".  I know 
> this because I posted similar code on this group several years ago and that 
> is how it was described.
> 
> The code uses a high level abstraction "protected type" to create a low leve 
> abstraction "Binary_Semaphore".  The code uses two semaphores to restrict 
> access to the bounded buffer.  In this simple example it is easy to follow, 
> but in a more complex example pairing Acquire's and Release's can be a 
> chore.

That is because of the Ravenscar limitation of one entry per protected
object. The solution Maciej presented is based on splitting one protected
object of two entries into two, each controlling access to its end of FIFO.
Protected objects don't compose so the result. Worse it will be with FIFO
size > 1. 

Here is a solution based on event + requeue rather than mutexes. Requeue is
implicit of course, because Ravenscar forbids requeue statements.

pragma Profile (Ravenscar);

package Bounded_Buffer is
   subtype Multiple is Positive range 2..Positive'Last;
   type Buffer_Type (Size : Multiple) is limited private;

   procedure Get (Buffer : in out Buffer_Type; Item : out Integer);
   procedure Put (Buffer : in out Buffer_Type; Item : Integer);

private
   type Storage_Data is array (Positive range <>) of Integer;

   protected type Buffer_Type (Size : Multiple) is
      entry Wait;
      procedure Get (Item : out Integer; Success : out Boolean);
      procedure Put (Item : Integer; Success : out Boolean);
   private
      Storage   : Storage_Data (1..Size);
      First_In  : Positive := 1;
      First_Out : Positive := 1;
      Empty     : Boolean  := True;
      Free      : Boolean  := False; -- In /= Out explicitly
   end Buffer_Type;
   
end Bounded_Buffer;

Notes:

1. First_In /= First_Out is a complex barrier, so we need it explicitly as
Free.

2. With buffer size 1 this implementation would do busy waiting, for this
reason the minimal buffer size is 2.

package body Bounded_Buffer is

   protected body Buffer_Type is

      entry Wait when Free is
      begin
         null;
      end Wait;

      procedure Put (Item : in Integer; Success : out Boolean) is
      begin
         if Free or else Empty then
            Storage (First_Out) := Item;
            if First_Out = Size then
               First_Out := 1;
            else
               First_Out := First_Out + 1;
            end if;
            Free    := First_Out /= First_In;
            Empty   := False;
            Success := True;
         else
            Success := False;
         end if;
      end Put;

      procedure Get (Item : out Integer; Success : out Boolean) is
      begin
         if Free or else not Empty then
            Item := Storage (First_In);
            if First_In = Size then
               First_In := 1;
            else
               First_In := First_In + 1;
            end if;
            Free    := First_Out /= First_In;
            Empty   := not Free;
            Success := True;
         else
            Success := False;
         end if;
      end Get;
   end Buffer_Type;

   procedure Put (Buffer : in out Buffer_Type; Item : in Integer) is
      Success : Boolean;
   begin
      loop
         Buffer.Put (Item, Success);
         exit when Success;
         Buffer.Wait;
      end loop;
   end Put;
   
   procedure Get (Buffer : in out Buffer_Type; Item : out Integer) is
      Success : Boolean;
   begin
      loop
         Buffer.Get (Item, Success);
         exit when Success;
         Buffer.Wait;
      end loop;
   end Get;

end Bounded_Buffer;

-----------------------
P.S. As a general note. This object might interesting as an exercise, but
not likely needed. In a real application it would be strange to expect
multiple consumers taking integers out of buffer in some unpredictable
order. Normally, it is so that either there is one producer and one or many
consumers (like in distribution of jobs), or else there is many producers
and one consumer (like writing to log file). This might sufficiently
simplify the design. Yet another variant is multiple consumers receiving
whole waveform of integers put to the buffer (broadcasting). This would be
more difficult.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de