Sleeping Barber Problem
Implemented in Ada and Java. The Java implementation is taken from Java Sleeping Barber.
Problem Description:
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 { |
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; |
- 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.
Analysis of Ada Version
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