Sunday, March 17, 2024

Comparison of three algorithms for summing an array of integers

This article shares a comparison of the time taken to sum an array of integers. This article tests three algorithms for summing the array.

• A sequential summation using a single Ada task.

• A concurrent summation using 16 Ada tasks coordinating using the Ada Rendezvous mechanism.

• A concurrent summation using 16 Ada tasks coordinating using a shared buffer.

This test personal computer has the following characteristics.

• Processor : AMD Ryzen 7 7800X3D 8-Core Processor with baseline speed of  4.20 Ghz

• RAM: 64.0 GB (63.2 GB usable) of DDR5 RAM

• Operating System: Windows 11 Home

The software for this test is written in the Ada programming language using the GNAT Community Edition 2021 compiler.

The program source code is contained in three files.

There is one custom Ada package defined for this test. The package is named array_sums. Ada packages separate the interface definition from the implementation. The interface definition, or package specification, as it is called in Ada, is in a file named array_sums.ads.

generic
   Num_Tasks : Positive;
package array_sums is
   type Data_Array is array (Integer range <>) of Integer;
   type Data_Access is access all Data_Array;
   function Sum_Sequential (Item : in not null Data_Access) return Integer;
   function Sum_Buffered (Item : in not null Data_Access) return Integer;
   function Sum_Rendezvous (Item : in not null Data_Access) return Integer;
end array_sums;


This is a generic package. The generic parameter is named Num_Tasks. Num_Tasks must be an integer value greater than 0. The package specification defines two data types.

• Type Data_Array is an unconstrained array of Integer values indexed by the Integer type.

• Type Data_Access is an access type accessing an instance of Data_Array. Access types are similar to references in C++ or Java.

The three functions to be compared are declared.

• Function Sum_Sequential sums an instance of Data_Access, which cannot be null, and returns the sum.

• Function Sum_Buffered sums an instance of Data_Access, which cannot be null, and returns the sum.

• Function Sum_Rendezvous sums an instance of Data_Access, which cannot be null, and returns the sum.

This article will compare the time taken to execute each of the three functions above.

Implementation Source Code

All three functions to sum the Data_Array references by an instance of Data_Access are implemented in the package body. I will first isolate and explain each function.

Sum_Sequential

This function is the simplest function to write and explain. It operates in a single Ada task which sequentially sums all the elements in the array passed to it.

   function Sum_Sequential (Item : in not null Data_Access) return Integer    is
      total : Integer := 0;
   begin
      for value of Item.all loop
         total := total + value;
      end loop;
      return total;
   end Sum_Sequential;

This function uses a single for loop to iterate through every value in the array, adding that value to the local variable total in each iteration. Upon completing the iterations the value of total is returned.

Sum_Buffered

This function is the largest function of the three because a thread-safe shared buffer is defined to collect the total of all the concurrent tasks iterating through distinct slices of the array passed to the Sum_Buffered function.

   function Sum_Buffered (Item : in not null Data_Access) return Integer is
      protected final_Total is
         procedure Add (Value : in Integer);
         function Report return Integer;
      private
         Total : Integer := 0;
      end final_Total;

      protected body final_Total is
         procedure Add (Value : in Integer) is
         begin
            Total := Total + Value;
         end Add;

         function Report return Integer is
         begin
            return Total;
         end Report;

      end final_Total;

      task type Adder is
         entry Set (Min : Integer; Max : Integer);
      end Adder;

      task body Adder is
         Total : Integer := 0;
         First : Integer;
         Last  : Integer;
      begin
         accept Set (Min : Integer; Max : Integer) do
            First := Min;
            Last  := Max;
         end Set;

         for I in First .. Last loop
            Total := Total + Item (I);
         end loop;

         final_Total.Add (Total);

      end Adder;

   begin

      declare
         type Adders is array (1 .. Num_Tasks) of Adder;

         The_Adders   : Adders;
         Num_Elements : Integer := (Item.all'Length) / Num_Tasks;
         Slice_Start  : Integer := Item.all'First;
         Slice_Max    : Integer := Item.all'First;
      begin

         for I in The_Adders'Range loop
            if I = The_Adders'Last then
               Slice_Max := Item'Last;
            else
               Slice_Max := Slice_Max + Num_Elements;
            end if;
            The_Adders (I).Set (Min => Slice_Start, Max => Slice_Max);
            if I < The_Adders'Last then
               Slice_Start := Slice_Max + 1;
            else
               Slice_Start := Slice_Start + Num_Elements;
            end if;
         end loop;
      end;

      return final_Total.Report;
   end Sum_Buffered;


Shared buffer

The shared buffer is defined as an Ada protected object named final_Total. The protected object implicitly handles locking to prevent race conditions. It contains two methods. A procedure named add which takes an IN parameter of type Integer and adds that integer to the data field in final_Total named Total. A protected procedure implicitly implements a read-write lock on the data. The second method is a function named Report which returns the value of Total. Ada protected functions are not allowed to modify the value of the protected object. Protected functions are read-only methods. Ada protected functions implicitly implement a shared read lock on the data, allowing multiple functions to access the data simultaneously.

Adder task type

Ada tasks are analgous to threads and are often implemented using operating system threads. A task type defines the behavior of a particular kind of task which can be duplicated by creating multiple instances of the task type, just as if the task type were a data type.

Ada task types, like packages, have separate specifications and implementations. The specification for the Adder task type is:

      task type Adder is
         entry Set (Min : Integer; Max : Integer);
      end Adder;

This task type specification declares the Adder type to have one entry named Set. The Set entry has two parameters named Min and Max. Each parameter passes an integer into the instance of the task type. Languages such as C++ and Java would accomplish this through the use of a constructor for a thread class.

The task type implementation is defined in the task body.

      task body Adder is
         Total : Integer := 0;
         First : Integer;
         Last  : Integer;
      begin
         accept Set (Min : Integer; Max : Integer) do
            First := Min;
            Last  := Max;
         end Set;

         for I in First .. Last loop
            Total := Total + Item (I);
         end loop;

         final_Total.Add (Total);

      end Adder;

The task encounters an accept statement before it does anything else. The accept statement implements an Ada Rendezvous with a calling task. This Rendezvous completes the entry specified in the task specification. The task will suspend until another task passes the Min and Max values to the instance of the task type. Within the accept statement the entry parameter values are copied into the local variables First and Last.

The task instance then iterates through the set of array values starting with the index value contained in the First variable through the index value contained in the Last variable, totalling all the values. Upon completion of the for loop the value of Total is added to the final_Total protected object.

Sum_Buffered execution

The Sum_Buffered function begins its execution at the begin reserved word following the end of the declaration of the Adder task type. 

An inner block is declared within the Sum_Buffered function in which all the instances of the Adder task type are declared and executed. The Sum_Buffered function outer block will wait for all the tasks defined in the inner block to complete. This behavior is similar to calling a join method in C++ or Java for each of the declared task instances.

   begin
      declare
         type Adders is array (1 .. Num_Tasks) of Adder;

         The_Adders   : Adders;
         Num_Elements : Integer := (Item.all'Length) / Num_Tasks;
         Slice_Start  : Integer := Item.all'First;
         Slice_Max    : Integer := Item.all'First;
      begin

         for I in The_Adders'Range loop
            if I = The_Adders'Last then
               Slice_Max := Item'Last;
            else
               Slice_Max := Slice_Max + Num_Elements;
            end if;
            The_Adders (I).Set (Min => Slice_Start, Max => Slice_Max);
            if I < The_Adders'Last then
               Slice_Start := Slice_Max + 1;
            else
               Slice_Start := Slice_Start + Num_Elements;
            end if;
         end loop;
      end;

      return final_Total.Report;
   end Sum_Buffered;

The inner block declares an array type and four variables which only exist within the inner block.

• Type Adders is an array of Adder indexed by the values 1 through Num_Tasks. Rememer that Num_Tasks was the generic parameter passed to the package specification.

• The_Adders is an instance of Adders. All the tasks in the Adders array implicitly start at this point, and are immediatly suspended waiting for their Set entry to be called.

• Num_Elements is an Integer containing the number of array elements processed by each of the Num_Elements task objects, except the last task in the array which may contain more tasks because the number of data elements may not evenly divide into Num_Tasks and the extra elements are processed by the last task in the array.

• Slice_Start is an data_array index value specifying the first index value to be processed by a particular task.

• Slice_Max is a data_array index value specifying the maximum index value to be processed by a particular task.

The for loop iterates through all the index values in the The_Adders array, assigning Slice_Start and Slice_Max to each instance by calling that instance’s Set entry.

The inner block completes when all Num_Tasks of the array have completed. At that point all the data elements declared in the inner block are recovered and the Sum_Buffered function returns the value produced by calling final_Total.Report.

Sum_Rendezvous

Sum_Rendezvous has many similarities with Sum_Buffered. Sum_Rendezvous does not use a shared buffer to collect the subtotals from all the tasks. Instead it uses a second entry to report the subtotals.

Sum_Rendezvous also does not use an inner block because the second entry will cause the Sum_Rendezvous function to suspend until the task it calls accepts the Report entry.

   function Sum_Rendezvous (Item : in not null Data_Access) return Integer is

      task type Adder is
         entry Set (Min : Integer; Max : Integer);
         entry Report (Total : out Integer);
      end Adder;

      task body Adder is
         Subtotal : Integer := 0;
         First    : Integer;
         Last     : Integer;
      begin
         accept Set (Min : Integer; Max : Integer) do
            First := Min;
            Last  := Max;
         end Set;

         for I in First .. Last loop
            Subtotal := Subtotal + Item (I);
         end loop;

         accept Report (Total : out Integer) do
            Total := Subtotal;
         end Report;

      end Adder;

      type Adders is array (1 .. Num_Tasks) of Adder;

      The_Adders   : Adders;
      Num_Elements : Integer := (Item.all'Length) / Num_Tasks;
      Slice_Start  : Integer := Item.all'First;
      Slice_Max    : Integer := Item.all'First;
      Subtotal     : Integer;
      Grand_Total  : Integer := 0;
   begin

      for I in The_Adders'Range loop
         if I = The_Adders'Last then
            Slice_Max := Item'Last;
         else
            Slice_Max := Slice_Max + Num_Elements;
         end if;
         The_Adders (I).Set (Min => Slice_Start, Max => Slice_Max);
         if I < The_Adders'Last then
            Slice_Start := Slice_Max + 1;
         else
            Slice_Start := Slice_Start + Num_Elements;
         end if;
      end loop;

      for T of The_Adders loop
         T.Report (Subtotal);
         Grand_Total := Grand_Total + Subtotal;
      end loop;

      return Grand_Total;

   end Sum_Rendezvous;

Adder task specification

The Adder task specification for Sum_Rendezvous adds a second entry to the Adder task specification declared in the Sum_Buffered function.

      task type Adder is
         entry Set (Min : Integer; Max : Integer);
         entry Report (Total : out Integer);
      end Adder;

The Set entry passes two values into an instance of the Adder task type. The Report entry passes a single value out of the instance of the Adder task type.

Adder task body

         task body Adder is
         Subtotal : Integer := 0;
         First    : Integer;
         Last     : Integer;
      begin
         accept Set (Min : Integer; Max : Integer) do
            First := Min;
            Last  := Max;
         end Set;

         for I in First .. Last loop
            Subtotal := Subtotal + Item (I);
         end loop;

         accept Report (Total : out Integer) do
            Total := Subtotal;
         end Report;

      end Adder;

The Adder instance suspends on the accept call for the Set entry, just as we say in the Sum_Buffered function. It then iterates through the array slice of the Data_Array just as the function in the Sum_Buffered function. The difference is seen after the for loop completes. Instead of calling a protected procedure to add the subtotal to a total, the function simply accepts the Report entry and passes the subtotal out to the calling task.

Array_sums_main

The entry point for this comparison program is a procedure named array_sums_main. The purpose of this procedure is to execute each of the three array summing functions in the adder_sums package and display the results and timing for each function.

with Array_Sums;
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Calendar; use Ada.Calendar;

procedure array_Sums_main is
   Start : Time;
   Finis : Time;
   Final_Total : Integer;
   exec_time : Duration;
   package sums is new Array_Sums(16);
   use Sums;
   The_Array : Data_Access := new Data_Array (1 .. Integer'Last);
begin
   The_Array.all := (Others => 1);
   Put_Line
     ("The size of the data array is" & Integer'Image (The_Array'Length));
   New_Line;
   Put_Line ("Sequential algorithm");
   Start := clock;
   Final_Total := Sum_Sequential(The_Array);
   Finis := clock;
    Put_Line ("Array total:" & Final_Total'Image);
   New_Line;
   exec_time := Finis - Start;
   Put_Line ("Elapsed calculation time:" & exec_time'Image & " seconds");
   Put_Line
     ("Time per addition operation:" &
        Float'Image (Float (exec_time) / Float (The_Array'Length)) & "
seconds");
   New_Line;
   Put_Line("Concurrent algorithm coordinating using Rendezvous");
   Start := clock;
   Final_Total := Sum_Rendezvous(The_Array);
   Finis := clock;
    Put_Line ("Array total:" & Final_Total'Image);
   New_Line;
   exec_time := Finis - Start;
   Put_Line ("Elapsed calculation time:" & exec_time'Image & " seconds");
   Put_Line
     ("Time per addition operation:" &
        Float'Image (Float (exec_time) / Float (The_Array'Length)) & " seconds");
   New_Line;
   Put_Line("Concurrent algorithm coordinating using shared buffer");
   Start := clock;
   Final_Total := Sum_Buffered(The_Array);
   Finis := clock;
   Put_Line ("Array total:" & Final_Total'Image);
   New_Line;

   exec_time := Finis - Start;
   Put_Line ("Elapsed calculation time:" & exec_time'Image & " seconds");
   Put_Line
     ("Time per addition operation:" &
        Float'Image (Float (exec_time) / Float (The_Array'Length)) & " seconds");  
end array_sums_main;


The array_sums generic package is instantiated passing the value 16 as the generic parameter. This causes the concurrent functions each to use 16 tasks to complete their calculations.

Comparison output

The output of this procedure is:

The size of the data array is 2147483647

Sequential algorithm
Array total: 2147483647

Elapsed calculation time: 6.531004600 seconds
Time per addition operation: 3.04124E-09 seconds

Concurrent algorithm coordinating using Rendezvous
Array total: 2147483647

Elapsed calculation time: 0.410473000 seconds
Time per addition operation: 1.91141E-10 seconds

Concurrent algorithm coordinating using shared buffer
Array total: 2147483647

Elapsed calculation time: 0.360019200 seconds
Time per addition operation: 1.67647E-10 seconds

It is clear that all three functions totaled the same set of values. The timings of the concurrent algorithms are clearly faster than the timing for the sequential algorithm, with the best timing coming from the Sum_Buffered function.


at No comments:

Thursday, January 11, 2024

Comparing Sleeping Barber Implementations in Java and Ada

 

Sleeping Barber Problem 

Implemented in Ada and Java.  The Java implementation is taken from Java Sleeping Barber.

Problem Description:

Simulate a barber shop with one barber, one barber chair and a waiting room with N chairs for waiting customers. When the barber finishes cutting the hair of one customer he dismisses the customer and goes to the waiting room to see if another customer is waiting. If the customer is waiting the barber cuts the customer's hair. If no customers are waiting the barber goes to sleep on the barber chair. The next customer to arrive must awaken the barber.
If all waiting room chairs are full when a new customer arrives that arriving customer will leave the barbershop. If the barbershop is closed all arriving customers will leave the barbershop. The barber will cut the hair of all customers already in a chair when the barbershop closes.

In these examples there are 4 chairs in the Barber Shop waiting room.

Further Requirements:

  • Thee problem is solved using threads in Java and tasks in Ada
  • The solution must demonstrate how to close the barber shop and shut down the simulation.

The organization of the Ada program differs significantly from the organization of the Java program.

Java Program:

Barber.java

public class Barber {

    public void cutHair() {
        System.out.println("Barber: Cutting Hair --- " +
Thread.currentThread().getName());
    }
}


public class Customer {

    public void enter() {
        System.out.println("Customer: Enters the shop --- " +
Thread.currentThread().getName());
    }

    public void getHairCut() {
        System.out.println("Customer: Getting Haircut --- " + Thread.currentThread().getName());
    }

    public void leave() {
        System.out.println("Customer: Leaves the shop --- " + Thread.currentThread().getName());
    }
}

  Barbershop.java

public class Barbershop {

   private final int limit;

   public int customers;

   private final Barber barber;

   private final Semaphore customerReady;

   private final Semaphore barberReady;

   private final Semaphore customerDone;

   private final Semaphore barberDone;

   private final ReentrantLock mutex;

   public Barbershop(int limit) {

       this.limit = limit;

       customers = 0;

       customerReady = new Semaphore(0);

       barberReady = new Semaphore(0);

       customerDone = new Semaphore(0);

       barberDone = new Semaphore(0);

       mutex = new ReentrantLock();

       barber = new Barber();

   }

   public Void startService() {

       // wait for a customer to arrive

       try {

           customerReady.acquire();

       } catch (InterruptedException e) {

           System.out.println("Barber wait task is interrupted: " + e.getMessage());

       }

       // signal that barber is ready

       barberReady.release();

       // give a haircut

       barber.cutHair();

       // wait for a customer to approve done

       try {

           customerDone.acquire();

       } catch (InterruptedException e) {

           System.out.println("Barber wait task is interrupted: " + e.getMessage());

       }

       // signal the customer that barber is done

       barberDone.release();

       System.out.println("Haircut is done");

       return null;

   }

   public Void receiveNewCustomer() {

       Customer customer = new Customer();

       customer.enter();

       mutex.lock();

       if (customers == limit) {

           mutex.unlock();

           customer.leave();

           return null;

       }

       customers += 1;

       mutex.unlock();

       customerReady.release();

       // wait for the barber to be available

       try {

           barberReady.acquire();

       } catch (InterruptedException e) {

           System.out.println("Customer wait task is interrupted: " + e.getMessage());

       }

       // get the haircut

       customer.getHairCut();

       // signal that customer is done

       customerDone.release();

       // wait for barber to approve done

       try {

           barberDone.acquire();

       } catch (InterruptedException e) {

           System.out.println("Customer wait task is interrupted: " + e.getMessage());

       }

       mutex.lock();

       customers -= 1;

       mutex.unlock();

       return null;

   }

}

 Simulator.java

public class Simulator {

   private static final int NUM_ITERATION = 8;

   public static void main(String[] args) {

       ExecutorService executor = Executors.newWorkStealingPool();

       Barbershop barbershop = new Barbershop(4);

       Callable<Void> barbershopTask = barbershop::startService;

       Callable<Void> receiveCustomerTask = barbershop::receiveNewCustomer;

       List <Future<Void>> barberFutures = new ArrayList<>();

       List <Future<Void>> customerFutures = new ArrayList<>();

       for (int i=0; i<NUM_ITERATION; i++) {

           Future <Void> barberFuture = executor.submit(barbershopTask);

           barberFutures.add(barberFuture);

           Future <Void> customerFuture = executor.submit(receiveCustomerTask);

           customerFutures.add(customerFuture);

       }

       barberFutures.forEach(future -> {

           try {

               future.get();

           } catch (InterruptedException | ExecutionException e) {

               e.printStackTrace();

           }

       });

       customerFutures.forEach(future -> {

           try {

               future.get();

           } catch (InterruptedException | ExecutionException e) {

               e.printStackTrace();

           }

       });

   }

}

 Analysis of the Java version

Size
167 lines of source code.
Barber
Only cuts hair. Does not sleep. Does not close store.
Customer
Enters barber shop. Waits for the barber to be available. Gets haircut. 
Barbershop
Creates semaphores and a mutex. Creates an instance of Barber. Implements startService and receiveNewCustomer.
Simulator
Creates an instance of Barbershop with 4 chairs. Creates a Callable named barberShopTask which executes startService. Creates a Callable named receiveCustomerTask which executes receiveNewCustomer. Creates lists named barberFutures and customerFutures. Iterates 8 times, each time creating a barberFuture from the execution of barbershopTask and then adds the future to barberFutures, then creats a customerFuture from the execution of receiveCustomerTask and add the future to customerFutures. After the creation of the futures each future in the barberFutures is executed. After executing all the barberFutures each future in customerFutures is executed.

The barbershop is implicitly closed when all 8 sets of futures have completed. There is no explicit command to close the barbersop after being open a specified length of time.

The Java version has a confusing set of responsibilities and there is no indication that the barber is sleeping while the barbershop waiting room is empty.

The logic of the interaction of barber behavior and customer behavior is controlled by the Barbershop class and not be either the barber or the customer. Neither the barber nor the customer know whether or not the waiting room is empty or full.

Ada version

barbershop.ads

package Barber_Shop is

  task Barber is

     entry Close_Shop;

  end Barber;

  task Customers;

end Barber_Shop;

barbershop.adb

with Ada.Text_IO;               use Ada.Text_IO;

with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random;

package body Barber_Shop is

  Seed : Generator;

  type Num_Seats is range 0 .. 5;

  protected Shop is

     function Is_Open return Boolean;

     function Shop_Empty return Boolean;

     entry Take_Seat;

     entry Serve_Customer;

     procedure Close_Shop;

  private

     Shop_Open      : Boolean   := True;

     Occupied_Seats : Num_Seats := 0;

  end Shop;

  protected body Shop is

     function Is_Open return Boolean is

     begin

        return Shop_Open;

     end Is_Open;

     function Shop_Empty return Boolean is

     begin

        return Occupied_Seats = 0;

     end Shop_Empty;

     entry Take_Seat when Shop_Open and then 

                             Occupied_Seats < Num_Seats'Last is

     begin

        Occupied_Seats := Occupied_Seats + 1;

     end Take_Seat;

     entry Serve_Customer when Occupied_Seats > 0 is

     begin

        Occupied_Seats := Occupied_Seats - 1;

     end Serve_Customer;

     procedure Close_Shop is

     begin

        Shop_Open := False;

     end Close_Shop;

  end Shop;

  ------------

  -- Barber --

  ------------

  task body Barber is

     procedure Cut_Hair is

     begin

        Put_Line ("Luigi is serving a customer.");

        delay Duration (Random (Seed) * 3.0);

     end Cut_Hair;

  begin

     loop

        select

           accept Close_Shop;

           Put_Line ("Luigi is closing the shop");

           Shop.Close_Shop;

        else

           if Shop.Is_Open then

              if Shop.Shop_Empty then

                 Put_Line ("Luigi is sleeping.");

              end if;

              Shop.Serve_Customer;

              Cut_Hair;

           else

              while not Shop.Shop_Empty loop

                 Shop.Serve_Customer;

                 Cut_Hair;

              end loop;

              exit;

           end if;

        end select;

     end loop;

  end Barber;

  ---------------

  -- Customers --

  ---------------

  task body Customers is

  begin

     loop

        delay Duration (Random (Seed) * 2.5);

        select

           Shop.Take_Seat;

           Put_Line ("A customer took a seat");

        else

           if Shop.Is_Open then

              Put_Line (

               "A customer left because all the seats were taken.");

           else

              Put_Line (

                 "A customer left because the shop is closed.");

              exit;

           end if;

        end select;

     end loop;

  end Customers;

begin

  Reset (Seed);

end Barber_Shop;

 main.adb

with Barber_Shop; use Barber_Shop;

procedure Main is

begin

  delay 60.0;

  Barber.Close_Shop;

end Main;

Analysis of Ada Version  

Size
119 lines of source code.
Barber_Shop package
Declares and defines a protected object named Shop. Declares and defines a task named Barber. Declares and defines a task called Customers. Declares the integer type Num_Seats with valid values in the range of 0 through 5.
Shop protected object
Declares and defines the protected operations named: function Is_Open return Boolean; function Shop_Empty return Boolean; entry Take_Seat; entry Serve_Customer; procedure Close_Shop;. Declares private data members: Shop_Open      : Boolean   := True;,  Occupied_Seats : Num_Seats := 0;. Function Is_Open returns True when the shop is open and False when the shop is closed. entry Take_Seat executes only when the shop is open and the value of Occupied_Seats is less than the maximum value of the type Num_Seats. entry Serve_Customer only executes when Occupied_Seats is greater than 0. procedure Close_Shop sets Shop_Open to False.
Barber task
Iterates until the shop is closed and all customers in the waiting room have had their haircuts. Each iteration Barber checks to see if its Close_Shop entry has been called. If the entry has not yet been called the Barber attempts to cut a customer's hair. If Close_Shop has been called Barber calls the Close_Shop procedure in the Shop protected object. In each iteration while the shop is open the barber calls Shop.Shop_Empty to determine if the shop is currently empty. If it is the Barber outputs "Luigi is sleeping". Whether or not the Shop is empty Barber calls Shop.Serve_Customer. Barber will be suspended while there are no customers in the waiting room and will awaken and server the customer(s) when there are one or more customers in the waiting room. Cutting a customer's hair takes a random time from 0 through 3 seconds. If the shop is closed the Barber cuts the hair of every customer in the waiting room and then terminates.
Customers task
Loops until the shop is closed. Each iteration of the loop begins with a random delay of 0 through 2.5 seconds. Each iteration a customer attempts to take a seat. If the customer cannot take a seat either the waiting room is full or the shop is closed. The customers task outputs a message saying the waiting room is full if the shop is open or a message saying the shop is closed when the shop is closed. After outputting a message stating the shop is closed the Customers task terminates.
Main procedure
The Main procedure context clause declares a dependency on the Barber_Shop package, which causes the Barber task and the Customers task to begin executing. The Main procedure delays for 60 seconds then calls the Close_Shop entry of the Barber task.

The simulation ends after Main calls the Barber Close_Shop entry is called and then all the waiting customers have received their haircuts. The Customer task starts up to 2.5 seconds after the Barber task, allowing the Barber to sleep at the beginning of the simulation.

The Shop protected object is a passive unit of concurrency, only executing when called by either Barber or Customers. The Shop protected object only deals with the states of the Shop. Those states are the number of Occupied_Seats and whether or not the Shop is open.

The Barber task only deals with customers when they are available and with closing the shop.

The Customers task only deals with taking a seat or leaving if no seat can be taken.

The Main procedure causes the Barber and Customers tasks to start, waits 60 seconds and then signals the Barber to close the shop.

at No comments:

Saturday, January 6, 2024

Comparing Array handling in C and Ada

 

Problem Description: Find the Median of two merged sorted arrays.

This article demonstrates some of the differences in array handling using the C language and the Ada language.

C version:

int* merge(int arr1[], size_t len1, int arr2[], size_t len2) {

    int * const ret = malloc((len1 + len2) * sizeof(int));
    int *wr = ret;
 

    // merge the two arrays while they both have values
    for(;len1 && len2; ++wr) {
        if(*arr1 < *arr2) { 
        
            *wr = *arr1++;
            --len1;
        } else {
            *wr = *arr2++;
            --len2;
        }
    }
    // here either len1 or len2 or both are zero
    // fill with any residue from arr1
    while(len1--) *wr++ = *arr1++; 

    // fill with any residue from arr2
    while(len2--) *wr++ = *arr2++;

   
    return ret;
}
 

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
    int *arr = merge(nums1, nums1Size, nums2, nums2Size), len = nums1Size+ nums2Size;
    double mid;
    if(len % 2 == 1)
    {
        mid = *(arr + len/2);
    }
    else
    {
        mid = (*(arr+len/2)+*(arr+len/2+1))/2.0;
    }
    free(arr);
    return mid;
}

 

The C language provides no way to declare an array type. Furthermore only a pointer to the first element of an array is passed to a function parameter when the programmer specifies the array name to be passed. The second parameter associated with each array passed in this example is the number of elements in the array.

The C language does not provide a general concatenation operator for arrays that works with parameters passed to a function because the general case for an array does not carry any information about the number of elements in the array instance. That information is only available within the scope in which the array instance is declared.

The merge function shown above is a solution to these problems. The programmer is required to write their own array concatenation function.

This C language solution produces a merged, but not necessarily sorted, array.

 

Ada version:

The Ada language allows subprograms to be defined within other subprograms. The solution below defines the Find_Median function within the Main procedure.

The Find_Median function is shown below.

   type Flt_Array is array (Positive range <>) of Float;


   function Find_Median (A : Flt_Array; B : Flt_Array) return Float is
      procedure Sort is new Ada.Containers.Generic_Array_Sort
        (Index_Type => Positive, Element_Type => Float,
         Array_Type => Flt_Array);

      Mid  : Positive;
      Temp : Flt_Array := A & B;

   begin
      Sort (Temp);
      Mid := (Temp'First + Temp'Last) / 2;
      return Temp (Mid);
   end Find_Median;

 

Arrays are first class types. The Ada example declares an unconstrained array type indexed by the subtype Positive. The subtype positive is a subtype of the Integer type. Integer is a signed 32-bit integer with a maximum valid value of 2^31 – 1. Subtype Positive is a constrained subtype of Integer with a minimum value of 1 and a maximum value of 2^31 – 1. Each element of the array is a Float. Unconstrained array types allow instances of the array type to have different numbers of elements. Each instance is constrained in its size.

An Ada array instance passed to a function does not “decay” to a pointer to the first object. All information about the array including its element type, the range of index values, and the number of elements in the array instance are passed with the array.

The Find_Median function takes two parameters of type Flt_Array and returns a Float.

The variable Mid is an instance of the subtype Positive, which is the same type as the array index type.

The Temp variable is an instance of Flt_Array initialized by the concatenation of the array passed to parameter A and the array passed to parameter B. The “&” operator in Ada concatenates two arrays of the same type. The “&” operator plus the sort procedure replace the merge function in the C example.

Ada.Containers.Generic_Array_Sort is a pre-defined generic sort procedure for unconstrained arrays. The parameters passed to the generic sort procedure create a concrete procedure specialized for sorting the Flt_Array type.

The index of the mid-point in the array is calculated as

   Mid := (Temp'First + Temp'Last) / 2;

 

The minimum index value of an unconstrained array instance may be any valid value within the specified array index subtype. In this case the minimum value may be any number from 1 through 2^31 – 1. Temp’First evaluates to the minimum index value of the array Temp. Temp’Last evaluates to the maximum index value of the array Temp. The middle index value in the array is calculated by summing the minimum and maximum index values and dividing that sum by 2.

The Temp array in the Find_Median function is declared on the function stack. It therefore is reclaimed with the rest of the stack data when the function completes.

The function returns the value of the array indexed by the variable Mid.

A full program declaring and using the Find_Median function is:

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Containers.Generic_Array_Sort;
 
procedure Main is
   type Flt_Array is array (Positive range <>) of Float;
 
   function Find_Median (A : Flt_Array; B : Flt_Array) return Float is
 
      procedure Sort is new Ada.Containers.Generic_Array_Sort
        (Index_Type => Positive, Element_Type => Float,
         Array_Type => Flt_Array);
 
      Mid  : Positive;
      Temp : Flt_Array := A & B;
   begin
      Sort (Temp);
      Mid := (Temp'First + Temp'Last) / 2;
      return Temp (Mid);
   end Find_Median;

   A1 : Flt_Array := (1.0, 3.0, 5.0, 7.0, 9.0, 11.0, 13.0, 15.0);
   A2 : Flt_Array := (2.0, 4.0, 6.0, 8.0,   10.0, 12.0, 14.0);
begin
   Put_Line ("The median of A1 and A2 is " &
             Float'Image (Find_Median (A1, A2)));
end Main;

 

The output of this program is:

The median of A1 and A2 is  8.00000E+00

at No comments:

Sunday, October 15, 2023

Parallel Comparison of C++ and Ada Producer-Consumer Implementations

 

Producer Consumer Comparison 

The C++ source code for this example is taken from the blog post here by Andrew Wei. A detailed description of the C++ software is given in the blog post.

This solution is shown in parallel with a corresponding Ada solution.

Both C++ and Ada separate interface specifications from implementation. C++ uses the header file, in this case the file named Buffer.hpp, to provide the interface specification for the buffer used in this example. C++ is not very strict about what goes into a header file and what goes into a .cpp file. The Ada version creates an Ada package. The Ada package specification defines the task types named producer_Int and consumer_Int. The buffer shared by all instances of producer_int and consumer_int is defined within the Ada package body file.

Interface Specification Files

Ada C++
package pc_tasks is
   task type produce_Int (Id : Natural);
   task type consume_Int (Id : Natural);
end pc_tasks;
 
//
//  Buffer.hpp
//  ProducerConsumer
//
//  Created by Andrew Wei on 5/31/21.
//

#ifndef Buffer_hpp
#define Buffer_hpp

#include <mutex>
#include <condition_variable>
#include <stdio.h>
 
#define BUFFER_CAPACITY 10

class Buffer {
    // Buffer fields
    int buffer [BUFFER_CAPACITY];
    int buffer_size;
    int left; // index where variables are put inside of buffer (produced)
    int right; // index where variables are removed from buffer (consumed)
    
    // Fields for concurrency
    std::mutex mtx;
    std::condition_variable not_empty;
    std::condition_variable not_full;
    
public:
    // Place integer inside of buffer
    void produce(int thread_id, int num);
    
    // Remove integer from buffer
    int consume(int thread_id);
    
    Buffer();
};

#endif /* Buffer_hpp */

This comparison shows the interface for Ada task types while the C++ interface (.hpp) file shows the interface for the Buffer class. The C++ interface definition defines the interfaces, both public and private, to the Buffer class.

Shared Buffer Implementations

The Ada package body contains both the definition and implementation of the shared buffer object and the implementation of the task types.

Ada C++
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Numerics.Discrete_Random;

package body pc_tasks is
   type Index_T is mod 10; -- Modular type for 10 values
   type Circular_Array is array (Index_T) of Integer;

   protected buffer is
      entry produce (Item : in Integer);
      entry consume (Item : out Integer);
   private
      Buf      : Circular_Array;
      P_Index  : Index_T := Index_T'First;
      C_Index  : Index_T := Index_T'First;
      Buf_Size : Natural := 0;
   end buffer;

   protected body buffer is
      entry produce (Item : in Integer) when Buf_Size < Index_T'Modulus is
      begin
         Buf (P_Index) := Item;
         P_Index       := P_Index + 1;
         Buf_Size      := Buf_Size + 1;
      end produce;

      entry consume (Item : out Integer) when Buf_Size > 0 is
      begin
         Item     := Buf (C_Index);
         C_Index  := C_Index + 1;
         Buf_Size := Buf_Size - 1;
      end consume;
   end buffer;

   task body produce_Int is
      subtype decimal is Integer range 1 .. 10;
      package rand_int is new Ada.Numerics.Discrete_Random (decimal);
      use rand_int;
      value : decimal;
      seed  : Generator;
   begin
      Reset (seed);
      for I in 1 .. 4 loop
         value := Random (seed);
         buffer.produce (value);
         Put_Line ("Task" & Id'Image & " produced" & value'Image);
         delay 0.1;
      end loop;
   end produce_Int;

   task body consume_Int is
      Num : Integer;
   begin
      for I in 1 .. 6 loop
         buffer.consume (Num);
         Put_Line ("Task" & Id'Image & " consumed" & Num'Image);
         delay 0.1;
      end loop;
   end consume_Int;

end pc_tasks;
 
//
//  Buffer.cpp
//  ProducerConsumer
//
//  Created by Andrew Wei on 5/31/21.
//

#include <iostream>
#include "Buffer.hpp"

Buffer::Buffer() {
    buffer_size = 0;
    left = 0;
    right = 0;
}

void Buffer::produce(int thread_id, int num) {
    // Acquire a unique lock on the mutex
    std::unique_lock<std::mutex> unique_lock(mtx);
    
    std::cout << "thread " << thread_id << " produced " << num << "\n";
    
    // Wait if the buffer is full
    not_full.wait(unique_lock, [this]() {
        return buffer_size != BUFFER_CAPACITY;
    });
    
    // Add input to buffer
    buffer[right] = num;
    
    // Update appropriate fields
    right = (right + 1) % BUFFER_CAPACITY;
    buffer_size++;
    
    // Unlock unique lock
    unique_lock.unlock();
    
    // Notify a single thread that buffer isn't empty
    not_empty.notify_one();
}

int Buffer::consume(int thread_id) {
    // Acquire a unique lock on the mutex
    std::unique_lock<std::mutex> unique_lock(mtx);
    
    // Wait if buffer is empty
    not_empty.wait(unique_lock, [this]() {
        return buffer_size != 0;
    });
    
    // Getvalue from position to remove in buffer
    int result = buffer[left];
    
    std::cout << "thread " << thread_id << " consumed " << result << "\n";
    
    // Update appropriate fields
    left = (left + 1) % BUFFER_CAPACITY;
    buffer_size--;
    
    // Unlock unique lock
    unique_lock.unlock();
    
    // Notify a single thread that the buffer isn't full
    not_full.notify_one();
    
    // Return result
    return result;
}

The Ada part of the package implementing the shared buffer is isolated below, along with a repeat of the C++ Buffer class implementation.

Ada C++
   type Index_T is mod 10; -- Modular type for 10 values
   type Circular_Array is array (Index_T) of Integer;

   protected buffer is
      entry produce (Item : in Integer);
      entry consume (Item : out Integer);
   private
      Buf      : Circular_Array;
      P_Index  : Index_T := Index_T'First;
      C_Index  : Index_T := Index_T'First;
      Buf_Size : Natural := 0;
   end buffer;

   protected body buffer is
      entry produce (Item : in Integer) when Buf_Size < Index_T'Modulus is
      begin
         Buf (P_Index) := Item;
         P_Index       := P_Index + 1;
         Buf_Size      := Buf_Size + 1;
      end produce;

      entry consume (Item : out Integer) when Buf_Size > 0 is
      begin
         Item     := Buf (C_Index);
         C_Index  := C_Index + 1;
         Buf_Size := Buf_Size - 1;
      end consume;
   end buffer;
 
//
//  Buffer.cpp
//  ProducerConsumer
//
//  Created by Andrew Wei on 5/31/21.
//

#include <iostream>
#include "Buffer.hpp"

Buffer::Buffer() {
    buffer_size = 0;
    left = 0;
    right = 0;
}

void Buffer::produce(int thread_id, int num) {
    // Acquire a unique lock on the mutex
    std::unique_lock<std::mutex> unique_lock(mtx);
    
    std::cout << "thread " << thread_id << " produced " << num << "\n";
    
    // Wait if the buffer is full
    not_full.wait(unique_lock, [this]() {
        return buffer_size != BUFFER_CAPACITY;
    });
    
    // Add input to buffer
    buffer[right] = num;
    
    // Update appropriate fields
    right = (right + 1) % BUFFER_CAPACITY;
    buffer_size++;
    
    // Unlock unique lock
    unique_lock.unlock();
    
    // Notify a single thread that buffer isn't empty
    not_empty.notify_one();
}

int Buffer::consume(int thread_id) {
    // Acquire a unique lock on the mutex
    std::unique_lock<std::mutex> unique_lock(mtx);
    
    // Wait if buffer is empty
    not_empty.wait(unique_lock, [this]() {
        return buffer_size != 0;
    });
    
    // Getvalue from position to remove in buffer
    int result = buffer[left];
    
    std::cout << "thread " << thread_id << " consumed " << result << "\n";
    
    // Update appropriate fields
    left = (left + 1) % BUFFER_CAPACITY;
    buffer_size--;
    
    // Unlock unique lock
    unique_lock.unlock();
    
    // Notify a single thread that the buffer isn't full
    not_full.notify_one();
    
    // Return result
    return result;
}

 The Ada buffer definition begins by defining the array type to be used in the shared buffer. Ada allows arrays to be indexed by any discrete type. In this example an Ada modular type is declared and named Index_T. Type Index_T is declared to be "mod 10", which specifies that all its values are in the range of 0 through 9 and all the arithmetic operators return a value within this range. The only arithmetic operator used in this example is "+". Addition on a modular type is modular. Thus, in this example, 9 + 1 yields 0, which is exactly as needed for a circular buffer.

Type Circular_Array is an array indexed by Index_T. Every element of Circular_Array is an Integer.

Ada protected objects are protected against race conditions. They are specifically used for data shared by Ada tasks. Ada tasks are commonly implemented as operating system threads, but may also be used on a bare-bones system using only a compiler-generated Ada runtime.

The protected object is named buffer. It is separated into a specification and an implementation, but both parts in this example are contained in the package body. The protected specification declares the name of the protected object. There are three kinds of methods that may be used inside a protected object: procedures, entries and functions. Procedures have exclusive unconditional read-write access to the data in the protected object. Entries have conditional read-write access to the data in a shared object. Functions have shared read-only access to the data in the protected object. This example only uses two entries. The private portion of the protected object contains the definition of the data members in the protected object. Buf is an instance of Circular_Array. P_Index is an instance of the Index_T type and is used by the producer to add new data to the protected object. C_Index is an instance of Index_T type and is used by the consumer to index data read from the protected object. Buf_Size is an instance of the Natural subtype of Integer. Natural is a pre-defined subtype of Integer with a minimum value of 0. Buf_Size is initialized with the value 0.

The protected body implements the two entries. Each entry has an associated condition which must evaluate to True for the entry to execute. All tasks calling an entry while its controlling condition evaluates to False are implicitly placed in an entry queue for the called entry using a queuing policy of First-In-First-Out (FIFO). The next entry call in the queue is serviced as soon as the condition evaluates to TRUE. Tasks suspended in the entry queue are given access to the protected entry before any new tasks, thus maintaining the temporal condition of the calls.

The produce entry can only write to the protected object when Buf_Size is less than Index_T'Modulus, which in this case evaluates to 10. The consumer entry can only read from the protected object when Buf_Size is greater than 0.

Each entry implicitly handles all locking and unlocking of the protected object. The protected object is locked just before the "begin" reserved word in each entry and is unlocked just before the "end" reserved word in each entry. The modular nature of the index manipulations as well as the implicit lock manipulations explain the relatively simple Ada code compared with the more verbose corresponding C++ code.

Thread Implementations

The Ada task implementations are also contained in the package body while the C++ thread implementations are contained in the main.cpp file. Those corresponding source code sections are compared below.

Ada C++
   task body produce_Int is
      subtype decimal is Integer range 1 .. 10;
      package rand_int is new Ada.Numerics.Discrete_Random (decimal);
      use rand_int;
      value : decimal;
      seed  : Generator;
   begin
      Reset (seed);
      for I in 1 .. 4 loop
         value := Random (seed);
         buffer.produce (value);
         Put_Line ("Task" & Id'Image & " produced" & value'Image);
         delay 0.1;
      end loop;
   end produce_Int;

   task body consume_Int is
      Num : Integer;
   begin
      for I in 1 .. 6 loop
         buffer.consume (Num);
         Put_Line ("Task" & Id'Image & " consumed" & Num'Image);
         delay 0.1;
      end loop;
   end consume_Int;
 
// Takes in reference to a buffer and adds a random integer
void produceInt(Buffer &buffer) {
    for (int i = 0; i < 4; i++) {
        // Generate random number between 1 and 10
        int new_int = rand() % 10 + 1;
        buffer.produce(i, new_int);
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
}

// Takes in reference to a buffer and returns the latest int added
// in the buffer
void consumeInt(Buffer &buffer) {
    for (int i = 0; i < 6; i++) {
        buffer.consume(i);
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
}

The Ada tasks have visibility to the buffer protected object because the task bodies and the protected object are both defined within the same package body scope.

The produce_Int task defines an Integer subtype named decimal with valid values in the range of 1 through 10. That type is passed to the generic package Ada.Numerics.Discrete_Random so that random numbers in the range of 1 through 10 will be generated for this program. The random number seed is reset based upon the system clock using the Reset(seed) command. The for loop iterates through the values 1 through 4. Each iteration generates a new random value, writes the value to buffer.produce, outputs the value to standard output and then delays 0.1 seconds (100 milliseconds).

The consumer_int task defines a local integer variable named Num. The for loop iterates through the numbers 1 through 6. Each iteration calls buffer.consume, assigning the entry out parameter to Num, outputs the consumed value and delays 0.1 seconds.

Program Entry Points

While the program entry point for a C++ program is named "main", the program entry point for an Ada program may have any name chosen by the programmer. Note that the Ada entry point is a procedure, meaning it does not return any value and that procedure has no parameters.

Ada C++
with pc_tasks;    use pc_tasks;
with Ada.Text_IO; use Ada.Text_IO;

procedure Main is
begin
   Put_Line("Executing code in main...");
   declare
      Produce_Task0 : produce_Int (0);
      Consume_Task0 : consume_Int (1);
      Produce_Task1 : produce_Int (2);
      Consume_Task1 : consume_Int (3);
      Produce_Task2 : produce_Int (4);
   begin
      null;
   end;
   Put_Line ("Done!");
end Main;
 
int main(int argc, const char * argv[]) {
    std::cout << "Executing code in main...\n";
    
    // Initialize random seed
    srand (time(NULL));
    
    // Create Buffer
    Buffer buffer;
    
    // Create a thread to produce
    std::thread produceThread0(produceInt, std::ref(buffer));
    
    std::thread consumeThread0(consumeInt, std::ref(buffer));
    
    std::thread produceThread1(produceInt, std::ref(buffer));
    
    std::thread consumeThread1(consumeInt, std::ref(buffer));
    
    std::thread produceThread2(produceInt, std::ref(buffer));
    
    produceThread0.join();
    produceThread1.join();
    produceThread2.join();
    consumeThread0.join();
    consumeThread1.join();
    
    std::cout << "Done!\n";
    return 0;
}

Ada does not provide a "join()" method. Instead, the code block in which a task or set of task is declared cannot complete until all the tasks within that code block complete. The idiom shown above declared the 5 task type instances within an inner code block, which does not complete until all five of the tasks have terminated. Upon completion of that inner block the message "Done!" is output to standard output.

Complete code listings for both languages

Ada C++
package pc_tasks is
   task type produce_Int (Id : Natural);
   task type consume_Int (Id : Natural);
end pc_tasks;
 
//
//  Buffer.hpp
//  ProducerConsumer
//
//  Created by Andrew Wei on 5/31/21.
//

#ifndef Buffer_hpp
#define Buffer_hpp

#include <mutex>
#include <condition_variable>
#include <stdio.h>
 
#define BUFFER_CAPACITY 10

class Buffer {
    // Buffer fields
    int buffer [BUFFER_CAPACITY];
    int buffer_size;
    int left; // index where variables are put inside of buffer (produced)
    int right; // index where variables are removed from buffer (consumed)
    
    // Fields for concurrency
    std::mutex mtx;
    std::condition_variable not_empty;
    std::condition_variable not_full;
    
public:
    // Place integer inside of buffer
    void produce(int thread_id, int num);
    
    // Remove integer from buffer
    int consume(int thread_id);
    
    Buffer();
};

#endif /* Buffer_hpp */
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Numerics.Discrete_Random;

package body pc_tasks is
   type Index_T is mod 10; -- Modular type for 10 values
   type Circular_Array is array (Index_T) of Integer;

   protected buffer is
      entry produce (Item : in Integer);
      entry consume (Item : out Integer);
   private
      Buf      : Circular_Array;
      P_Index  : Index_T := Index_T'First;
      C_Index  : Index_T := Index_T'First;
      Buf_Size : Natural := 0;
   end buffer;

   protected body buffer is
      entry produce (Item : in Integer) when Buf_Size < Index_T'Modulus is
      begin
         Buf (P_Index) := Item;
         P_Index       := P_Index + 1;
         Buf_Size      := Buf_Size + 1;
      end produce;

      entry consume (Item : out Integer) when Buf_Size > 0 is
      begin
         Item     := Buf (C_Index);
         C_Index  := C_Index + 1;
         Buf_Size := Buf_Size - 1;
      end consume;
   end buffer;

   task body produce_Int is
      subtype decimal is Integer range 1 .. 10;
      package rand_int is new Ada.Numerics.Discrete_Random (decimal);
      use rand_int;
      value : decimal;
      seed  : Generator;
   begin
      Reset (seed);
      for I in 1 .. 4 loop
         value := Random (seed);
         buffer.produce (value);
         Put_Line ("Task" & Id'Image & " produced" & value'Image);
         delay 0.1;
      end loop;
   end produce_Int;

   task body consume_Int is
      Num : Integer;
   begin
      for I in 1 .. 6 loop
         buffer.consume (Num);
         Put_Line ("Task" & Id'Image & " consumed" & Num'Image);
         delay 0.1;
      end loop;
   end consume_Int;

end pc_tasks;
 
//
//  Buffer.cpp
//  ProducerConsumer
//
//  Created by Andrew Wei on 5/31/21.
//

#include <iostream>
#include "Buffer.hpp"

Buffer::Buffer() {
    buffer_size = 0;
    left = 0;
    right = 0;
}

void Buffer::produce(int thread_id, int num) {
    // Acquire a unique lock on the mutex
    std::unique_lock<std::mutex> unique_lock(mtx);
    
    std::cout << "thread " << thread_id << " produced " << num << "\n";
    
    // Wait if the buffer is full
    not_full.wait(unique_lock, [this]() {
        return buffer_size != BUFFER_CAPACITY;
    });
    
    // Add input to buffer
    buffer[right] = num;
    
    // Update appropriate fields
    right = (right + 1) % BUFFER_CAPACITY;
    buffer_size++;
    
    // Unlock unique lock
    unique_lock.unlock();
    
    // Notify a single thread that buffer isn't empty
    not_empty.notify_one();
}

int Buffer::consume(int thread_id) {
    // Acquire a unique lock on the mutex
    std::unique_lock<std::mutex> unique_lock(mtx);
    
    // Wait if buffer is empty
    not_empty.wait(unique_lock, [this]() {
        return buffer_size != 0;
    });
    
    // Getvalue from position to remove in buffer
    int result = buffer[left];
    
    std::cout << "thread " << thread_id << " consumed " << result << "\n";
    
    // Update appropriate fields
    left = (left + 1) % BUFFER_CAPACITY;
    buffer_size--;
    
    // Unlock unique lock
    unique_lock.unlock();
    
    // Notify a single thread that the buffer isn't full
    not_full.notify_one();
    
    // Return result
    return result;
}
with pc_tasks;    use pc_tasks;
with Ada.Text_IO; use Ada.Text_IO;

procedure Main is
begin
   Put_Line("Executing code in main...");
   declare
      Produce_Task0 : produce_Int (0);
      Consume_Task0 : consume_Int (1);
      Produce_Task1 : produce_Int (2);
      Consume_Task1 : consume_Int (3);
      Produce_Task2 : produce_Int (4);
   begin
      null;
   end;
   Put_Line ("Done!");
end Main;
 
//
//  main.cpp
//  ProducerConsumer
//
//  Created by Andrew Wei on 5/30/21.
//

#include <thread>
#include <iostream>
#include "Buffer.hpp"
#include <stdlib.h>

// Takes in reference to a buffer and adds a random integer
void produceInt(Buffer &buffer) {
    for (int i = 0; i < 4; i++) {
        // Generate random number between 1 and 10
        int new_int = rand() % 10 + 1;
        buffer.produce(i, new_int);
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
}

// Takes in reference to a buffer and returns the latest int added
// in the buffer
void consumeInt(Buffer &buffer) {
    for (int i = 0; i < 6; i++) {
        buffer.consume(i);
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
}

int main(int argc, const char * argv[]) {
    std::cout << "Executing code in main...\n";
    
    // Initialize random seed
    srand (time(NULL));
    
    // Create Buffer
    Buffer buffer;
    
    // Create a thread to produce
    std::thread produceThread0(produceInt, std::ref(buffer));
    
    std::thread consumeThread0(consumeInt, std::ref(buffer));
    
    std::thread produceThread1(produceInt, std::ref(buffer));
    
    std::thread consumeThread1(consumeInt, std::ref(buffer));
    
    std::thread produceThread2(produceInt, std::ref(buffer));
    
    produceThread0.join();
    produceThread1.join();
    produceThread2.join();
    consumeThread0.join();
    consumeThread1.join();
    
    std::cout << "Done!\n";
    return 0;
}

 Summary

The same producer-consumer problem can be solved using both Ada and C++. The C++ approach to the producer-consumer pattern requires far more attention to low level details than does the Ada approach to the producer-consumer pattern. The greatest difference in the two approaches is the requirement for the C++ programmer to explicitly manipulate mutex locking/unlocking and suspended thread wait and notification commanding.

at 1 comment:
Subscribe to: Posts (Atom)

Comparison of three algorithms for summing an array of integers

This article shares a comparison of the time taken to sum an array of integers. This article tests three algorithms for summing the array. •...

  • Threads of Confusion
    Many programming languages support concurrent behavior through the creation of threads and the explicit manipulation of semaphores, locks or...
  • Comparing Ada and High Integrity C++
    I have often suspected that use of a safety critical or high integrity coding standard for C++ would yield a level of safety and software r...
  • Ada vs C++ Bit-fields
    Uses of Bit-fields Bit-fields are typically used to implement communication protocols and to create device drivers for actuators or sensor...