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.