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.

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