Skip Navigation | ANU Home | Search ANU | Search FEIT | Feedback

---

• If you did not get to complete the rendezvous and requeue portions of Lab 5 then go back and do that now. Note that there are some model answers available.
• You may be glad to know that this is the last Ada lab.
• The gnat environment is only available on Linux systems. To work from home you must ssh to machine partch.

Your education in concurrent programming would not be complete without consideration of bounded buffers and dining philosophers - so here they are!

---

Bounded Buffers

---

A bounded buffer is an array with two indices; one index indicates the next free slot in the array, while the other indicates the slot containing the next object to be removed. As the array is of finite size, the indices must wrap around the array. Does this all sound familiar - it should - as this is exactly how the queue example used in Labs 1 and 2 was programmed!!

Buffering in general is extremely widely used in concurrent programming. The idea is that one task deposits data into a buffer, while another task retrieves the data at a later stage. Breaking the nexus between the producer and consumer is advantageous since it breaks the synchronization, allowing the producer to continue doing other work rather than waiting for the consumer to be ready. This is especially important when the two tasks are associated with different timescales, e.g. the CPU and an I/O device. The disadvantage of using a buffer is that it adds overhead, requiring that data be copied to and from the intervening buffer. Also handling scenarios that require the consumer to communicate back to the producer is not quite as easy.

To illustrate the use of a bounded buffer we consider a modification of the code to sum integers from 1..N. In this case we decide to have No_Producer producer tasks and No_Consumer consumer tasks. Each producer is assigned a subset of the 1..N integers that it must pass to the consumer tasks. Rather than direct communication, however, we employ an intermediate buffer and have producers place their numbers into the buffer and consumers retrieve them. If each consumer adds the numbers it retrieves to a running total, then at termination the sum of the private sub-totals should equal to the sum of 1..N, which as we know is given by N*(N+1)/2.

From previous labs we can create tasks and communicate with them. We also have the queue package that we can use as the basis for a bounded buffer. We start by constructing the following code that creates the relevant numbers of producer and consumer tasks and has them put/retrieve data from the queue.

• File bounded_buffer_test.adb

  with Ada.Text_IO; use Ada.Text_IO;
  with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; 
  with Queue_Pack_Generic; 
  procedure Bounded_Buffer_Test is
     -- how many numbers we give to each producer
     Factor : Positive := 100;
  
     -- use the queue package as our bounded buffer
     package Queue_Pack_Positive is
        new Queue_Pack_Generic (Element => Positive);
     use Queue_Pack_Positive;
     The_Queue : Queue_Type;
  
     -- This is the consumer task
     task type Consumer(Id : Integer);
     task body Consumer is
        My_Value, My_Total : Natural := 0;
     begin
        Put("Hello From Consumer "); Put( Id); New_Line;
        loop
           -- retrieve data from the buffer
           Dequeue(Item => My_Value, Queue => The_Queue);
           -- add to local total
           My_Total := My_Total + My_Value;
           delay 0.01;
        end loop;
     exception
        -- exception when queue is empty
        when Queueunderflow => Put("Consumer underflow Value");
           Put (My_Total);New_Line;
     end Consumer;
  
     -- This is the producer task
     task type Producer(Id : Integer; First : Integer; Last : Integer);
     task body Producer is
     begin
        Put("Hello From Producer "); Put( Id); New_Line;
        -- loop over my range of integers
        for I in First..Last loop
           -- put data into buffer
           Enqueue (Item => i, Queue => The_Queue);
           delay 0.01;
        end loop;
     exception
        -- exception when queue is full
        when Queueoverflow  => Put("Producer overflow");
           Put(Id); New_Line;
     end Producer;
  
     -- needed to dynamically allocate an array of consumers or producers
     type Consumer_Ptr is access Consumer;
     type Consumer_Array is array(Natural range <>) of Consumer_Ptr;
     type Consumer_Array_Ptr is access Consumer_Array;
     type Producer_Ptr is access Producer;
     type Producer_Array is array(Natural range <>) of Producer_Ptr;
     type Producer_Array_Ptr is access Producer_Array;
  
     -- now define our data quantities
     My_Consumers : Consumer_Array_Ptr;
     My_Producers : Producer_Array_Ptr;
     No_Producers, No_Consumers: Natural;
     Start_Val, End_Val : Positive;
     Grand_Total : Natural := 0;
  begin
     -- input number of producers and consumers
     Put("Input Number of Producers");New_Line;
     Get(No_Producers);
     Put("Input Number of Consumers");New_Line;
     Get(No_Consumers);
     Put("Number of Producers: ");Put(No_Producers);New_Line;
     Put("Number of Consumers: ");Put(No_Consumers);New_Line;
     My_Producers := new Producer_Array(1..No_Producers);
     My_Consumers := new Consumer_Array(1..No_Consumers);
  
     -- start the producers and assign unique sub range of values
     Start_Val := 1;
     for I in My_Producers'Range loop
        End_Val := Start_Val + Factor;
        My_Producers(I) := new Producer(I, Start_Val, End_Val);
        Start_Val := End_Val + 1;
     end loop;
     delay 0.0;
  
     -- start the consumers
     for I in My_Consumers'Range loop
        My_Consumers(I) := new Consumer(I);
     end loop;
  
     -- Print the value we should get!
     Grand_Total := End_Val * (End_Val + 1)/2;
     Put("Value Should Be "); Put (Grand_Total);New_Line;
  
  end Bounded_Buffer_Test;
  

• File queue_pack_generic.ads

  generic
     type Element is private;
  
  package Queue_Pack_Generic is
     QueueSize : constant Positive := 1000;
     type Queue_Type is limited private;
  
     procedure Enqueue (Item: in  Element; Queue: in out Queue_Type);
     procedure Dequeue (Item: out Element; Queue: in out Queue_Type);
  
     Queueoverflow, Queueunderflow : exception;
  
  private
     type Marker is mod QueueSize;
     type List is array (Marker'Range) of Element;
     type Queue_State is (Empty, Filled);
     type Queue_Type is record
        Top, Free : Marker      := Marker'First;
        State     : Queue_State := Empty;
        Elements  : List;
     end record;
  
  end Queue_Pack_Generic;
  

• File queue_pack_generic.adb

  package body Queue_Pack_Generic is
     procedure Enqueue (Item: in Element; Queue: in out Queue_Type) is
     begin
        if Queue.State = Filled and Queue.Top = Queue.Free then
           raise Queueoverflow;
        end if;
        Queue.Elements (Queue.Free) := Item;
        delay 0.0;
        Queue.Free := Marker'Pred (Queue.Free);
        Queue.State := Filled;
     end Enqueue;
     Procedure Dequeue (Item: out Element; Queue: in out Queue_Type) is
     begin
        if Queue.State = Empty then
           raise Queueunderflow;
        end if;
        Item := Queue.Elements (Queue.Top);
        delay 0.0;
        Queue.Top := Marker'Pred(Queue.Top);
        if Queue.Top = Queue.Free then
           Queue.State := Empty;
        end if;
     end Dequeue;
  end Queue_Pack_Generic;
  

ACTIONS

• Compile the above code and run it with 1 producer and 1 consumer. What happens?
• Now increase the delay between the end of the loop that creates the producers and the start of loop that creates the consumers. With a delay of about 1.0 seconds you should find that the code reports the correct results when running with 1 consumer and 1 producer. You should clearly understand why it now works, and appreciate that this is not a real fix.
• Re-run the code but this time have multiple producers and consumers, e.g. 3 and 3. You should observe that the sum of the results reported as `Consumer underflow ' do not equal the expected result. Moreover in some cases the values reported look wrong, e.g. `Consumer underflow 1567840790'. To understand why it is wrong edit the file queue_pack_generic.adb and comment out the delay 0.0 statements that occur within these routines. Re-run the experiment. You should now find the results to be more reliable - although they are still not guaranteed to be correct!
• Now modify the code to make it work properly! You should:

  • Convert queue_pack_generic to be a protected object.
  • Change enqueue and dequeue from procedures to entry points. Place guards on the entries to ensure that a producer only enters enqueue if there is space left in the buffer to hold the data, and a consumer only enters if there is data in the buffer to be retrieved.
  • The previous change will, however, mean that the queue package never throws an exception. As a result our code will never end; the producers will still terminate when they have finished adding data to the buffer, but the consumers will be left sitting at the guarded dequeue entry. To provide an orderly shutdown have each producer register with the protected object when it is created and deregister when it has completed processing all of its numbers. Modify the guard on dequeue to consider both whether the buffer is empty and whether there are still producers active.
  • Now test your program extensively; you should set all delay statements to 0.0 and test your code for various buffer sizes.

---

Dining Philosophers

---

This famous metaphor for resource allocation and deadlocking problems was first stated in 1971 by Edsger Dijkstra ("Hierarchical Ordering of Sequential Processes." Acta Informatica 1, 115-138). It is outlined in in chapter 6 of Ben-Ari.

Five (or any number of) philosophers sit around a table; they spend their lives alternately thinking and eating (bit like students - well at least the eating part!). In the center of the round table is an infinite supply of spaghetti; before each philosopher is a plate; between each pair of plates is a fork. To eat, a philosopher must get two forks, the one on his/her right and the one on his/her left. A basic program implementing this problem is given below (note the use of an entry family within a protected object):

• File philos.adb

  with Ada.Text_IO; use Ada.Text_IO;
  with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random;
  
  procedure Philos is
  
     -- number of philosophers
     Size : constant Positive := 5;
     -- number of forks/philosophers and fork use
     type No_Fork is mod Size;
     type Availability is (AVAILABLE, IN_USE);
     type Fork_Use is array(No_Fork'Range) of Availability;
  
     -- Random number generator
     G : Generator;
  
     -- Whats up with the forks
     protected Type Fork_Controller is
        entry Get_Fork(No_Fork);
        procedure Release_Fork(Left_Or_Right    : in No_Fork);
        function Deadlock return Boolean;
     private
        The_Forks : Fork_Use := (others => AVAILABLE);
     end Fork_Controller;
  
     protected body Fork_Controller is
        function Deadlock return Boolean is
           Locked : Boolean;
        begin
           Locked := True;
           -- if any of the get_fork entries is free the code is no deadlocked
           for I in No_Fork loop
              if Get_fork(I)'Count = 0 then
                 Locked := False;
              end if;
           end loop;
           return Locked;
        end Deadlock;
  
        procedure Release_Fork(Left_Or_Right    : in No_Fork) is
        begin
           The_Forks(Left_Or_Right) := AVAILABLE;
        end Release_Fork;
  
        -- entry family, 1 entry per fork guarded by fork availability
        entry Get_Fork(for From in No_Fork) when The_Forks(From) = AVAILABLE is
        begin
           The_Forks(From) := IN_USE;
        end Get_Fork;
     end Fork_Controller;
  
     My_Fork_Controller : Fork_Controller;
  
     -- a philosopher task
     task type Philosopher is
        entry Start(Left_Fork : No_Fork; Right_Fork : No_Fork);
     end Philosopher;
     task body Philosopher is
        Left, Right : No_Fork;
        Ident : No_Fork renames Left;
     begin
        accept Start(Left_Fork : No_Fork; Right_Fork : No_Fork) do
           Left  := Left_Fork;
           Right := Right_Fork;
        end Start;
        loop
           Put_Line("Philosopher" & Ident'Img & " is thinking");
           delay Standard.Duration(Random(G));
  
           My_Fork_Controller.Get_Fork(Left);
           Put_Line("Philosopher" & Ident'Img & " has left fork");
           delay Standard.Duration(Random(G));
  
           My_Fork_Controller.Get_Fork(Right);
           Put_Line("Philosopher" & Ident'Img & " has both forks and is eating");
           delay Standard.Duration(Random(G));
  
           My_Fork_Controller.Release_Fork(Left);
           My_Fork_Controller.Release_Fork(Right);
  
        end loop;
     end Philosopher;
  
     -- Declare all size philosophers
     type Philosophers_Array is array(No_Fork) of Philosopher;
     My_Philosophers : Philosophers_Array;
  
  begin
  
     Reset(G);
  
     for I in No_Fork loop
        My_Philosophers(I).Start(Left_Fork => I, Right_Fork => No_Fork'Succ(I));
     end loop;
  
     loop                      -- Watch for deadlock to occur
        delay 0.01;
        if My_Fork_Controller.Deadlock then
           exit;
        end if;
     end loop;
     Put_Line("Deadlock detected, program operation aborted.");
  
     for I in No_Fork loop
        abort My_Philosophers(I);
     end loop;
  
  end Philos;
  

ACTIONS
For the parts indicated you can, if you chose, work in pairs. Make sure, however, that you discuss your solutions at the end so that both of you have a good understanding of what the other has done.

• Compile and run the above code. After some period of time - that varies each time you run the code - you will find that the code deadlocks (note deadlock as opposed to livelock). Make sure you understand why the code deadlocks and how the deadlock is detected.
• The deadlock can be broken by ensuring that odd numbered philosophers pick up the fork on their left first, while even numbered philosophers pick up the fork on their right first. Explain why - for arbitrary numbers of philosophers - this will always break the deadlock.

  Student A Implement this solution and then convince your colleagues that you have done it correctly.

• Another possible strategy is to restrict the number of philosophers permitted to sit at the table at any time to be one less than the total number of forks. We can do this by having a semaphore. Explain why this solution works.

  Student B Implement this solution and then convince your colleagues that you have done it correctly.

• Another possible solution is to use a monitor like construct to control access to pairs of forks. In Ben-Ari this is given as

  monitor Fork_Monitor
    Fork: array(0..4) of Integer range 0..2:=(others=.2);
    OK_to_Eat: array(0..4) of Condition;
  
  procedure Take_Fork(I : Integer) is
  begin
    if Fork(I) /= 2 then Wait(OK_to_Eat(I)); end if;
    Fork ((I+1) mod 5) := Fork((i+1) mod 5)-1;
    Fork ((I-1) mod 5) := Fork((i-1) mod 5)-1;
  end Take_Fork;
  
  procedure Release_Fork(I : Integer) is
  begin
    Fork ((I+1) mod 5) := Fork((i+1) mod 5)+1;
    Fork ((I-1) mod 5) := Fork((i-1) mod 5)+1;
    if Fork((I+1) mod 5) = 2 then 
      Signal(OK_to_Eat(I+1) mod 5));
    end if;
    if Fork((I-1) mod 5) = 2 then 
      Signal(OK_to_Eat(I-1) mod 5));
    end if;
  
  end Release_Fork;
  end Fork_Monitor;
  

  "where the monitor maintains an array Fork which counts the number of free forks available to each philosopher. The Take_Fork procedure waits on its own condition variable until two forks are available. Before leaving the monitor with these two forks, it decrements the number of free forks available to its neighbors. After eating, a philosopher calls Release_Fork to update the available fork array and possibly signal a neighbor."

  Student A Implement this solution and then convince your colleagues that you have done it correctly.

• If the deadlock can be detected by the master thread, then it is possible to modify the code such that the master breaks any deadlock. (This is not an ideal solution, since deadlock detection is no easy matter. Deadlocks are best avoided, not detected!)

  Student B Implement this solution and then convince your colleagues that you have done it correctly.