Producer-Consumer Determinism

The Producer-Consumer pattern is a common pattern used in concurrent programming. In this model one task writes values to a fixed length buffer and another task reads values from the fixed length buffer.

There are many variations on the Producer-Consumer pattern, mostly dealing with various numbers of producers and various numbers of consumers.

This article will use a simple Producer-Consumer pattern with a single producer and a single consumer. 

Determinism

The Producer-Consumer pattern has some simple limitations. The Consumer task cannot read data from an empty buffer and the Producer task cannot write data to a full buffer. These limitations might lead the programmer to assume that the Producer and Consumer will spend their time alternately reading and writing the buffer. First the Producer will write a value then the Consumer will read a value. While the general idea is correct, the actual viewed results may be a bit confusing.

Non-Deterministic Example

with Ada.Text_IO; use Ada.Text_IO; procedure Main is    Max_Iter : constant Positive := 40;    Buf_Size : constant          := 6;    subtype Index is Integer range 0 .. Buf_Size - 1;    type Buf_Array is array (Index) of Integer;    protected Buffer is       entry Write (Item : in Integer);       entry Read (Item : out Integer);    private       Buf       : Buf_Array;       Read_Idx  : Index   := 0;       Write_Idx : Index   := 0;       Count     : Natural := 0;    end Buffer;    protected body Buffer is       entry Write (Item : in Integer) when Count < Buf_Size is       begin          Buf (Write_Idx) := Item;          Write_Idx       := (Write_Idx + 1) mod Buf_Size;          Count           := Count + 1;          Put_Line ("Producer wrote" & Item'Image);       end Write;       entry Read (Item : out Integer) when Count > 0 is       begin          Item     := Buf (Read_Idx);          Read_Idx := (Read_Idx + 1) mod Buf_Size;          Count    := Count - 1;          Put_Line ("Consumer read" & Item'Image);       end Read;    end Buffer;    task Producer;    task Consumer;    task body Producer is    begin       for I in 1 .. Max_Iter loop          Buffer.Write (I);       end loop;       Put_Line ("       Producer finished");    end Producer;    task body Consumer is       Num : Integer;    begin       for I in 1 .. Max_Iter loop          Buffer.Read (Num);       end loop;       Put_Line ("       Consumer finished");    end Consumer; begin    null; end Main;

This example provides a shared buffer of 6 data elements. The Producer writes to the buffer when it is not full and the Consumer reads from the buffer when it is not empty. A typical execution of this program results in the following output:

Producer wrote 1 Consumer read 1 Producer wrote 2 Consumer read 2 Producer wrote 3 Consumer read 3 Producer wrote 4 Producer wrote 5 Producer wrote 6 Producer wrote 7 Producer wrote 8 Producer wrote 9 Consumer read 4 Producer wrote 10 Consumer read 5 Consumer read 6 Consumer read 7 Consumer read 8 Consumer read 9 Consumer read 10 Producer wrote 11 Consumer read 11 Producer wrote 12 Producer wrote 13 Producer wrote 14 Producer wrote 15 Producer wrote 16 Producer wrote 17 Consumer read 12 Producer wrote 18 Consumer read 13 Consumer read 14 Consumer read 15 Consumer read 16 Consumer read 17 Consumer read 18 Producer wrote 19 Consumer read 19 Producer wrote 20 Consumer read 20 Producer wrote 21 Consumer read 21 Producer wrote 22 Consumer read 22 Producer wrote 23 Producer wrote 24 Producer wrote 25 Producer wrote 26 Producer wrote 27 Producer wrote 28 Consumer read 23 Producer wrote 29 Consumer read 24 Consumer read 25 Consumer read 26 Consumer read 27 Consumer read 28 Consumer read 29 Producer wrote 30 Consumer read 30 Producer wrote 31 Producer wrote 32 Producer wrote 33 Producer wrote 34 Producer wrote 35 Producer wrote 36 Consumer read 31 Producer wrote 37 Consumer read 32 Consumer read 33 Consumer read 34 Consumer read 35 Consumer read 36 Consumer read 37 Producer wrote 38 Consumer read 38 Producer wrote 39 Producer wrote 40        Producer finished Consumer read 39 Consumer read 40        Consumer finished

As you can see, while the Producer and Consumer sometimes alternate in their execution, there are also periods during which either the Producer or the Consumer dominates, creating a series of actions from one task or the other. In other words, the execution of the two tasks is not deterministic. The non-deterministic nature shown is due to the operating system choosing when to schedule each task.

Deterministic Examples

How can the programmer create deterministic behavior given the whims of the operating system?

One way is to reduce the buffer size to 1 element.

with Ada.Text_IO; use Ada.Text_IO; procedure Main is    Max_Iter : constant Positive := 40;    Buf_Size : constant          := 1;    subtype Index is Integer range 0 .. Buf_Size - 1;    type Buf_Array is array (Index) of Integer;    protected Buffer is       entry Write (Item : in Integer);       entry Read (Item : out Integer);    private       Buf       : Buf_Array;       Read_Idx  : Index   := 0;       Write_Idx : Index   := 0;       Count     : Natural := 0;    end Buffer;    protected body Buffer is       entry Write (Item : in Integer) when Count < Buf_Size is       begin          Buf (Write_Idx) := Item;          Write_Idx       := (Write_Idx + 1) mod Buf_Size;          Count           := Count + 1;          Put_Line ("Producer wrote" & Item'Image);       end Write;       entry Read (Item : out Integer) when Count > 0 is       begin          Item     := Buf (Read_Idx);          Read_Idx := (Read_Idx + 1) mod Buf_Size;          Count    := Count - 1;          Put_Line ("Consumer read" & Item'Image);       end Read;    end Buffer;    task Producer;    task Consumer;    task body Producer is    begin       for I in 1 .. Max_Iter loop          Buffer.Write (I);       end loop;       Put_Line ("       Producer finished");    end Producer;    task body Consumer is       Num : Integer;    begin       for I in 1 .. Max_Iter loop          Buffer.Read (Num);       end loop;       Put_Line ("       Consumer finished");    end Consumer; begin    null; end Main;

Now the entry guard conditions on the Protected Object named Buffer force the Producer and Consumer tasks to take turns in a deterministic manner.

Producer wrote 1 Consumer read 1 Producer wrote 2 Consumer read 2 Producer wrote 3 Consumer read 3 Producer wrote 4 Consumer read 4 Producer wrote 5 Consumer read 5 Producer wrote 6 Consumer read 6 Producer wrote 7 Consumer read 7 Producer wrote 8 Consumer read 8 Producer wrote 9 Consumer read 9 Producer wrote 10 Consumer read 10 Producer wrote 11 Consumer read 11 Producer wrote 12 Consumer read 12 Producer wrote 13 Consumer read 13 Producer wrote 14 Consumer read 14 Producer wrote 15 Consumer read 15 Producer wrote 16 Consumer read 16 Producer wrote 17 Consumer read 17 Producer wrote 18 Consumer read 18 Producer wrote 19 Consumer read 19 Producer wrote 20 Consumer read 20 Producer wrote 21 Consumer read 21 Producer wrote 22 Consumer read 22 Producer wrote 23 Consumer read 23 Producer wrote 24 Consumer read 24 Producer wrote 25 Consumer read 25 Producer wrote 26 Consumer read 26 Producer wrote 27 Consumer read 27 Producer wrote 28 Consumer read 28 Producer wrote 29 Consumer read 29 Producer wrote 30 Consumer read 30 Producer wrote 31 Consumer read 31 Producer wrote 32 Consumer read 32 Producer wrote 33 Consumer read 33 Producer wrote 34 Consumer read 34 Producer wrote 35 Consumer read 35 Producer wrote 36 Consumer read 36 Producer wrote 37 Consumer read 37 Producer wrote 38 Consumer read 38 Producer wrote 39 Consumer read 39 Producer wrote 40        Producer finished Consumer read 40        Consumer finished

Using the Ada programming language this seems to be task coordination done the hard way. The easy way to achieve this same behavior is to use the Ada Rendezvous facility to communicate between the Producer and the Consumer.

The Rendezvous facility provides very direct synchronization between tasks. The task calling a task entry must suspend until the called task handles the task entry. The called task must suspend at the point of handling an entry until another task calls the entry.

The same Producer-Consumer problem implemented using a task entry is shown below.

with Ada.Text_IO; use Ada.Text_IO; procedure PC_Rendezvous is    Max_Iter : constant := 40;    task Producer;    task Consumer is       entry Write (Item : in Integer);    end Consumer;    task body Producer is    begin       for I in 1 .. Max_Iter loop          Put_Line ("Producer writing" & I'Image);          Consumer.Write (I);       end loop;       Put_Line("      Producer finished");    end Producer;    task body Consumer is       Num : Integer;    begin       for I in 1 .. Max_Iter loop          accept Write (Item : in Integer) do             Num := Item;          end Write;          Put_Line ("Consumer read" & Num'Image);       end loop;       Put_Line("      Consumer finished");    end Consumer; begin    null; end PC_Rendezvous;

The output of this program is:

Producer writing 1 Consumer read 1 Producer writing 2 Consumer read 2 Producer writing 3 Consumer read 3 Producer writing 4 Consumer read 4 Producer writing 5 Consumer read 5 Producer writing 6 Consumer read 6 Producer writing 7 Consumer read 7 Producer writing 8 Consumer read 8 Producer writing 9 Consumer read 9 Producer writing 10 Consumer read 10 Producer writing 11 Consumer read 11 Producer writing 12 Consumer read 12 Producer writing 13 Consumer read 13 Producer writing 14 Consumer read 14 Producer writing 15 Consumer read 15 Producer writing 16 Consumer read 16 Producer writing 17 Consumer read 17 Producer writing 18 Consumer read 18 Producer writing 19 Consumer read 19 Producer writing 20 Consumer read 20 Producer writing 21 Consumer read 21 Producer writing 22 Consumer read 22 Producer writing 23 Consumer read 23 Producer writing 24 Consumer read 24 Producer writing 25 Consumer read 25 Producer writing 26 Consumer read 26 Producer writing 27 Consumer read 27 Producer writing 28 Consumer read 28 Producer writing 29 Consumer read 29 Producer writing 30 Consumer read 30 Producer writing 31 Consumer read 31 Producer writing 32 Consumer read 32 Producer writing 33 Consumer read 33 Producer writing 34 Consumer read 34 Producer writing 35 Consumer read 35 Producer writing 36 Consumer read 36 Producer writing 37 Consumer read 37 Producer writing 38 Consumer read 38 Producer writing 39 Consumer read 39 Producer writing 40 Consumer read 40       Consumer finished       Producer finished

Task deterministic behavior is achieve by forcing synchronization between the two tasks.