Barber Shop Problem Implemented using Ada

In computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes. The problem is analogous to that of keeping a barber working when there are customers, resting when there are none, and doing so in an orderly manner.

The Sleeping Barber Problem is often attributed to Edsger Dijkstra (1965), one of the pioneers in computer science.

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.

An Ada solution

The design approach taken below began with identifying the active and passive elements in the simulation. The active elements include the barber and the customers. The barbershop is a passive element. It contains chairs in a waiting room, a single barber chair, a count of waiting customers, and a state of Open or Closed.

The Ada language provides tasks as active elements of concurrency and protected objects as passive elements of concurrency. Operations on a passive object are always called by one or more tasks, and execute within the execution schedule of the task making the call.

The actions of the barber are to sleep when there are no customers, serve a customer in one of the chairs, and close the shop when directed.

The actions of the customers are to take an available seat or leave if no seat is available. Customers also leave if the barbershop is closed.

This solution provides a task for the barber, a task for all the customers, and a protected object named Barber_Shop.

The Barber_Shop package specification declares two tasks.

package Barber_Shop is
   task Barber is
      entry Close_Shop;
   end Barber;

   task Customers;
end Barber_Shop;

The Barber task simulates the behaviors of the barber. The barber task closes the barbershop when the entry Close_Shop is called by the main procedure.

The package body for the Barber_Shop package defines a protected object named Shop, which handles whether or not the shop is open along with whether or not customers have arrived.

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 .. 3;
   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) * 6.0);
         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;

The main procedure is very simple. It starts the simulation by withing the Barber_Shop package, delays for 60 seconds, and then calls Barber.Close_Shop;

with Barber_Shop; use Barber_Shop;
procedure Main is
begin
   delay 60.0;
   Barber.Close_Shop;
end Main;