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.

No comments:

Post a Comment

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. •...