Need pseudo code for producer consumer problem stated below

Question

Need algorithm/pseudo-code for a producer-consumer problem in which we have one producer and two consumers sharing a bounded buffer (capacity N). Any of the two consumers can consume an item from the buffer if buffer is not empty; however, the consumers have to wait if the buffer is empty. Moreover, the producer has to wait if the buffer is full. Implement the buffer is FIFO circular queue. Also can someone answer below questions? Can all the N slots may be full in the buffer simultaneously? If yes how? and if not why not?

Answer 1

The buffer can be full if the producer adds values to the buffer faster than the consumers extract values from the buffer. If the consumers extract the values as fast or faster than the producer adds values the buffer will never fill.

Instead of pseudo-code I will present a general solution using the Ada programming language. This solution works for one or more producers and one or more consumers.

The Ada solution consists of three files. The first file is a package specification which defines the API for a producer-consumer problem.

-----------------------------------------------------------------------
-- Producer-consumer with bounded buffer
-----------------------------------------------------------------------
generic
   Capacity : Positive;
package Bounded_PC is
   task type Producer is
      entry set_id(Id : in Positive);
      entry Stop;
   end Producer;

   task type Consumer is
      entry set_id(Id : in Positive);
      entry Stop;
   end Consumer;

end Bounded_PC;

This solution requires the size of the shared buffer to be specified as a generic parameter when instantiating the package Bounded_PC.

The package defines two task types (tasks are Ada's name for threads). The first task type is named Producer. The Producer task type defines two entries. The entry Set_Id establishes the programmer-chosen Id for a particular instance of the task type. The entry Stop is used to stop the execution of an instance of the task type. The task type Consumer has an identical interface, with an entry to set the task Id and an entry to stop the task.

This is the entire API for the producer and consumer tasks in this example.

The implementation of the tasks and their shared buffer is contained in the package body for the Bounded_PC package.

with Ada.Text_IO; use Ada.Text_IO;

package body Bounded_PC is
   subtype Index_T is Positive range 1..Capacity;
   type Buf_Array is array (Index_T) of Integer;

   ------------
   -- Buffer --
   ------------

   protected Buffer is
      Entry Write(Item : in Integer);
      Entry Read(Item : out Integer);
   private
      Buf : Buf_Array;
      Write_Index : Index_T := 1;
      Read_Index  : Index_T := 1;
      Count       : Natural := 0;
   end Buffer;


   protected body Buffer is

      entry Write(Item : in Integer) when Count < Capacity is
      begin
         Buf(Write_Index) := Item;
         Write_Index := (Write_Index mod Capacity) + 1;
         Count := Count + 1;
      end Write;

      entry Read(Item : out Integer) when Count > 0 is
      begin
         Item := Buf(Read_Index);
         Read_Index := (Read_Index mod Capacity) + 1;
         Count := Count - 1;
      end Read;

   end Buffer;

   --------------
   -- Producer --
   --------------

   task body Producer is
      Value : Integer := 0;
      Me : Positive;
   begin
      accept Set_Id(Id : in Positive) do
         Me := Id;
      end Set_Id;

      loop
         select
            accept Stop;
            exit;
         else
            select
               Buffer.Write(Value);
               Put_Line("Producer" & Me'Image & " wrote" & Value'Image);
               Value := Value + 1;
            or
               delay 0.001;
            end select;
         end select;
      end loop;
   end Producer;

   --------------
   -- Consumer --
   --------------

   task body Consumer is
      Value : Integer;
      Me : Positive;
   begin
      accept Set_Id(Id : in Positive) do
         Me := Id;
      end Set_Id;

      loop
         select
            accept Stop;
            exit;
         else
            select
               Buffer.Read(Value);
               Put_Line("Consumer" & Me'Image & " read" & Value'Image);
            or
               delay 0.001;
            end select;
         end select;
      end loop;
   end Consumer;

end Bounded_PC;

Ada allows the programmer to specify the range of values for an array index. The subtype Index_T is a subtype of Integer with a minimum value of 1 and a maximum value of Capacity, which is the generic parameter used to make an instance of this package.

The array type used as the bounded shared buffer in this example is named Buf_Array. Buff_Array is indexed by Index_T and each element is an Integer.

The buffer itself is an Ada protected object. Ada protected objects are implicitly protected from race conditions. The protected object named Buffer has two entries. The Write entry will be called by instances of the Producer task type. The Read entry will be called by instances of the Consumer task type. The Write entry passes an Integer in to the buffer and the Read entry passes an Integer out of the buffer.

The private part of the protected Buffer specification contains the internal data elements of Buffer. Those elements are an instance of Buf_Array named Buf, and instance of Index_T named Write_Index, an instance of Intex_T named Read_Index and an instance of the subtype Natural, which is an Integer with a minimum value of 0. This instance is named Count.

The protected body of Buffer implements the two entries Write and Read. The Write entry has a boundary condition allowing the Write entry to execute only when the buffer is not full, or as the logic states, when Count is less than Capacity. When the Write entry does execute it assigns the value in the parameter Item to the array element at Write_Index. It then increments the Write_Index accounting for modular wrap around logic. Finally it increments Count. If the boundary condition is false, in this case Count is not less than Capacity, the calling task is suspended in a queue automatically managed by the language. The next task in the queue, if any, is then handled and its value is written to the buffer.

The logic for the Read entry is very similar. The boundary condition differs from the Write boundary condition. Instead the Read entry only executes when the buffer is not empty, or as stated in the logic, when Count > 0. When the Read entry executes it copies the value in the Buf array at index Read_Index to the parameter Item, increments Read_Index using modular arithmetic and decrements count. The Read entry has its own entry buffer where instance of Consumer will be queued until a value is written to Buffer.

The Producer task type is implemented by first declaring two local variables. Each instance of the task type will have its own instances of these two variables. The first variable, named Value, is an Integer initialized to 0. The second variable is a subtype of Integer named Positive, which is an integer with a minimum value of 1. The name of this variable is Me. Me will hold the task Id assigned to this instance of the task.

After the "begin" reserved word there is an accept statement which accepts the Set_Id task entry. The value passed to this instance of producer will be assigned to its local Me variable. The task will wait at the accept call until another task calls its entry and passed its ID.

The real work of this task is to write numbers to Buffer until another task calls its Stop entry. All this is done within the loop statement. The "select" statement forms the beginning of a conditional branch in the response. Either the task will accept a call from another task on the Stop entry, in which case it will exit the loop, or it will write a value to the Buffer protected object. Upon successfully writing to Buffer the producer instance outputs a message identifying the task ID and the value written to Buffer. The number contained in the variable Value is incremented. If the Write entry does not execute within 0.001 seconds (1 millisecond) the loop repeats.

The Consumer task type is very similar to the producer. It declares two local variables Value and Me. It waits to accept is Set_Id entry and assigns the number passed to it to its local variable named Me. The consumer then executes a loop similar to the producer loop. The only difference is that it reads value from Buffer and prints that value.

The Bounded_PC package must be used within an actual program. The following procedure named main provides the program structure to test this package.

with Bounded_PC;

procedure Main is
   package Int_Pck is new Bounded_Pc(10);
   use Int_Pck;

   P1 : Producer;
   P2 : Producer;
   C1 : Consumer;
   C2 : Consumer;
begin
   P1.Set_Id(1);
   P2.Set_Id(2);
   C1.Set_Id(1);
   C2.Set_Id(2);
   delay 0.01;
   P1.Stop;
   P2.Stop;
   delay 0.01;
   C1.Stop;
   C2.Stop;
end Main;

The a concrete instance of the generic Bounded_Pc package is declared passing the number 10 as the capacity of the Buffer array.

Two producers named P1 and P1 are created. Two consumers named C1 and C2 are created.

following the "begin" reserved word in the main procedure the Set_Id entries for tasks P1, P2, C1, C2 are called, passing ID values for each task.

The main procedure then delays (sleeps) for 0.01 seconds, or 10 milliseconds. The Stop entries for P1 and P2 are called, the main procedure delays for another 10 milliseconds and then calls the stop procedures for C1 and C2.

The output of this program is:

Producer 2 wrote 0
Producer 2 wrote 1
Producer 2 wrote 2
Producer 2 wrote 3
Producer 2 wrote 4
Producer 2 wrote 5
Producer 2 wrote 6
Producer 2 wrote 7
Producer 2 wrote 8
Producer 2 wrote 9
Producer 2 wrote 10
Consumer 1 read 0
Consumer 1 read 1
Consumer 1 read 2
Consumer 1 read 3
Consumer 1 read 4
Consumer 1 read 5
Consumer 1 read 6
Consumer 1 read 7
Consumer 1 read 8
Consumer 1 read 9
Consumer 1 read 10
Consumer 1 read 11
Producer 2 wrote 11
Consumer 2 read 0
Consumer 1 read 12
Producer 2 wrote 12
Producer 1 wrote 0
Producer 2 wrote 13
Consumer 2 read 13
Producer 2 wrote 14
Producer 1 wrote 1
Producer 1 wrote 2
Producer 1 wrote 3
Producer 2 wrote 15
Producer 1 wrote 4
Producer 1 wrote 5
Producer 2 wrote 16
Producer 2 wrote 17
Producer 2 wrote 18
Producer 1 wrote 6
Producer 2 wrote 19
Consumer 2 read 14
Consumer 1 read 1
Consumer 2 read 15
Consumer 1 read 2
Producer 1 wrote 7
Producer 2 wrote 20
Producer 1 wrote 8
Producer 2 wrote 21
Consumer 2 read 3
Consumer 1 read 4
Consumer 2 read 16
Consumer 1 read 5
Consumer 2 read 17
Consumer 1 read 18
Consumer 2 read 6
Consumer 1 read 19
Consumer 1 read 20
Consumer 1 read 8
Consumer 1 read 21
Consumer 1 read 9
Consumer 2 read 7
Consumer 1 read 22
Producer 1 wrote 9
Producer 1 wrote 10
Producer 2 wrote 22
Producer 1 wrote 11
Consumer 2 read 10
Consumer 1 read 11
Consumer 2 read 23
Consumer 1 read 12
Producer 1 wrote 12
Producer 2 wrote 23
Consumer 2 read 13
Producer 1 wrote 13
Producer 2 wrote 24
Producer 1 wrote 14
Consumer 1 read 24
Producer 1 wrote 15
Producer 1 wrote 16
Producer 1 wrote 17
Producer 1 wrote 18
Producer 1 wrote 19
Producer 1 wrote 20
Producer 1 wrote 21
Consumer 1 read 25
Producer 1 wrote 22
Producer 1 wrote 23
Producer 1 wrote 24
Producer 1 wrote 25
Consumer 1 read 15
Producer 2 wrote 25
Producer 1 wrote 26
Consumer 1 read 16
Consumer 2 read 14
Consumer 1 read 17
Producer 2 wrote 26
Producer 2 wrote 27
Consumer 1 read 19
Consumer 2 read 18
Consumer 1 read 20
Consumer 1 read 22
Consumer 1 read 23
Producer 1 wrote 27
Consumer 2 read 21
Consumer 2 read 25
Consumer 2 read 26
Consumer 2 read 26
Consumer 2 read 27
Consumer 1 read 24
Consumer 2 read 27
Producer 1 wrote 28
Producer 1 wrote 29
Producer 1 wrote 30
Consumer 2 read 28
Consumer 2 read 29
Consumer 2 read 30
Consumer 2 read 31
Consumer 1 read 28
Producer 1 wrote 31
Producer 2 wrote 28
Producer 1 wrote 32
Producer 2 wrote 29
Producer 2 wrote 30
Producer 2 wrote 31
Producer 2 wrote 32
Producer 2 wrote 33
Producer 2 wrote 34
Producer 2 wrote 35
Producer 2 wrote 36
Producer 2 wrote 37
Producer 2 wrote 38
Consumer 2 read 32
Producer 1 wrote 33
Consumer 1 read 29
Consumer 2 read 33
Consumer 1 read 30
Consumer 1 read 32
Consumer 1 read 33
Consumer 1 read 34
Consumer 1 read 35
Consumer 1 read 36
Consumer 1 read 37
Producer 1 wrote 34
Consumer 1 read 38
Producer 1 wrote 35
Consumer 2 read 31
Consumer 1 read 39
Consumer 1 read 35
Consumer 1 read 36
Producer 1 wrote 36
Consumer 2 read 34
Consumer 1 read 37
Producer 1 wrote 37
Producer 1 wrote 38
Producer 2 wrote 39
Consumer 2 read 38
Consumer 1 read 39
Consumer 2 read 40
Producer 1 wrote 39
Producer 2 wrote 40
Consumer 1 read 40
Producer 1 wrote 40
Consumer 2 read 41
Consumer 1 read 41
Producer 1 wrote 41
Producer 2 wrote 41
Producer 1 wrote 42
Consumer 2 read 42
Producer 2 wrote 42
Producer 2 wrote 43
Producer 2 wrote 44
Producer 2 wrote 45
Producer 2 wrote 46
Producer 2 wrote 47
Producer 2 wrote 48
Producer 2 wrote 49
Producer 2 wrote 50
Producer 2 wrote 51
Consumer 1 read 42
Producer 1 wrote 43
Producer 2 wrote 52
Consumer 2 read 43
Consumer 1 read 43
Consumer 2 read 44
Consumer 2 read 46
Consumer 2 read 47
Consumer 1 read 45
Consumer 2 read 48
Consumer 2 read 50
Consumer 2 read 51
Consumer 2 read 52
Consumer 1 read 49
Consumer 1 read 44
Consumer 2 read 53
Producer 2 wrote 53
Producer 2 wrote 54
Producer 1 wrote 44
Consumer 1 read 54
Consumer 2 read 55
Consumer 1 read 45
Producer 2 wrote 55
Producer 1 wrote 45
Producer 2 wrote 56
Consumer 2 read 56
Producer 2 wrote 57
Consumer 1 read 57