Discussion

Comments, remarks, suggestions, corrections etcetera can be posted here.

Please download the SleepingBarber.jar (the source code is in the jar), then run:

java -jar SleepingBarber.jar

The main logic is in the run() method of the Barber class:

public class Barber extends Thread
  {
  ...
  public void run( )
    {
    try
      {
      while ( true )
        {
        synchronized ( shop )
          {
          while ( !shop.isCustomerWaiting( ) )
            shop.wait( );
          if ( isAsleep )
            {
            isAsleep = false;
            setMessage( "awake ...", "wakes up" );
            shop.isCuttingChairBusy( false );
            setMessage( "ready ...", "frees his chair" );
            }
          shop.notifyAll( );
 
          setMessage( "working ...", "seats a customer" );
          while ( !shop.isCuttingChairBusy( ) )
            shop.wait( );
          }
 
        Customer customer = shop.getCurrentCustommer( );
        setMessage( "working ...", "starts " + customer );
        sleep( SleepingBarber.getRandomInt( SleepingBarber.MAX_TIME_HAIRCUT ) );
        setMessage( "working ...", "finishes " + customer );
        setMessage( "working ...", "--------------------" );
 
        synchronized ( shop )
          {
          shop.letCurrentCustomerOut( );
          shop.notifyAll( );
          while ( shop.isCuttingChairBusy( ) )
            shop.wait( );
          shop.currentCustomerDone( );
          if ( !shop.isCustomerWaiting( ) )
            {
            shop.isCuttingChairBusy( true );
            setMessage( "sleeping ...", "takes his chair" );
            isAsleep = true;
            setMessage( "sleeping ...", "--------------------" );
            setMessage( "sleeping ...", "goes to sleep" );
            setMessage( "sleeping ...", "--------------------" );
            }
          }
        }
      }
    catch ( InterruptedException e )
      {}
    }
  ...
  }

and the run() method of the Customer class:

public class Customer extends Thread
  {
  ...
  public void run( )
    {
    try
      {
      while ( true )
        {
        setMessage( "away ...", "--------------------" );
        setMessage( "away ...", "is away" );
        setMessage( "away ...", "--------------------" );
        sleep( SleepingBarber.getRandomInt( SleepingBarber.MAX_TIME_AWAY ) );
 
        synchronized ( shop )
          {
          setMessage( "entering ...", "enters the shop" );
          int number = shop.getNumber( );
          if ( number != Shop.NO_ROOM )
            {
            if ( shop.isBarberAsleep( ) )
              {
              setMessage( "waiting ...", "wakes the barber" );
              shop.notifyAll( );
              }
            if ( number != shop.nextServing( ) )
              setMessage( "waiting ...", "gets a chair" );
            else
              setMessage( "waiting ...", "stands by" );
            while ( shop.isBarberAsleep( ) || shop.isCuttingChairBusy( ) || !shop.isCurrentCustomerDone( )
                || number != shop.nextServing( ) )
              shop.wait( );
 
            setMessage( "serviced ...", "in cutting chair" );
            shop.letCurrentCustomerIn( this );
            shop.notifyAll( );
 
            setMessage( "serviced ...", "service started" );
            while ( !shop.isCuttingDone( ) )
              shop.wait( );
            setMessage( "serviced ...", "service done" );
            shop.isCuttingChairBusy( false );
            shop.notifyAll( );
            setMessage( "done ...", "out cutting chair" );
            }
          }
        }
 
      }
    catch ( InterruptedException e1 )
      {}
    }
  ...
  }

Since we have just covered semaphore in the class, here is a solution to the Sleeping Barber problem using semaphores. Althought it may looks awkward using semaphores in this problem, I found it a good exerciese though. Also, I intentionally implemented the semaphors class, for practice and demonstration purpose.

/**************************************************************************
 classic sleeping barbar problem
 
 @version 1.0 
 @author	Hui Wang  
****************************************************************************/
public class  Main
{
  public static void main(String[] args)
  {
     final int numChairs = 5;
     final int numCustomers = 10;
 
     Shop shop = new Shop(numChairs);
 
     Barber bb = new Barber(shop);  // use constructor to pass info
     bb.start();
 
     for ( int i = 1; i <= numCustomers; i++ )
     {
       Customer ctr = new Customer(i,shop);
       ctr.start();
     }
 
 
  }
}
 
/*************************************************
/ semaphore class
**************************************************/
class MySemaphore 
{
   private int value;  // attribute
 
   public MySemaphore()  // constructor
   {
      this.value = 0;
   }
 
   public MySemaphore(int init) 
   {
      this.value = init;
   }
 
   public synchronized void signalMS()   // V
   {
      this.value++;
      if (this.value <= 1)  // oringinally 0
      {
         this.notify();
      }
   }
 
   public synchronized void waitMS()   // P
   {
      while (this.value == 0)
      {
        try{
           this.wait();
        }
        catch (InterruptedException ie) {}
      }
      this.value--;
   }
 
 } // end of MySemaphore
 
/*************************************************
/ Shop class
**************************************************/
class Shop
{
  // attributes
  private int numChairs ;
  private int waitingCount ;
 
  private MySemaphore customers;
  private MySemaphore barber;
  private MySemaphore mutex;
  private MySemaphore cutting;
 
  private int who;  // who is in service room
 
  // constructor
  public Shop(int nChairs) 
  {
     this.numChairs = nChairs;
     this.barber = new MySemaphore(0);
     this.customers = new MySemaphore(0);
 
     this.mutex = new MySemaphore(1);
     this.cutting = new MySemaphore(0);
 
     this.who = -1;
   }
 
   public void barberWorking() 
   {
      while (true)
      {
         System.out.println("**************\n--> # of waiting: " + waitingCount);
         if (waitingCount == 0)
            System.out.println("--> sleeping. ");
 
         this.customers.waitMS();  // wait for customers
         System.out.println("--> awken / coutinue work, # of waiting : "  
+ waitingCount);
 
         this.mutex.waitMS();
           this.waitingCount--;
           this.barber.signalMS();  // make self available
         this.mutex.signalMS();
 
         try
         {
             Thread.sleep((int)(Math.random() * 3000));  // wait for the thread to finish
         }
         catch (InterruptedException ie)
	 {
             System.out.println("Sleep failed");
         }
 
         System.out.println("--> working on " + who);
 
         cutting.waitMS();    // working
         System.out.println("--> finishing. ");
 
      }
 
  }
 
   public void customerWorking(int i)
   {
      System.out.print( i + " coming");
      this.mutex.waitMS();
      if ( waitingCount < numChairs )
      {  
         System.out.print(" --- already waitting # : " + waitingCount + " --- ");
         System.out.println( i + " entering");
         waitingCount++;
         customers.signalMS();   // increment customer, take seat
 
         mutex.signalMS();
 
         barber.waitMS();   // waiting / competing for barbar 
         this.who = i;   // I am the one getting the barber!
         System.out.println( i + " being served");
         try
         {
            Thread.sleep(2000));  // getting cut
         }
         catch (InterruptedException ie)
	 {
	    System.out.println("Sleep failed");
         }
 
         System.out.println( i + " being finished");
         cutting.signalMS();  // inform barber process 
 
      }
 
      else
      { 
         System.out.print(" --- alreay waitting # : " + waitingCount + " --- ");
         System.out.println( i + " leaving unhappily (full)");
         mutex.signalMS();  // leave the shop
      } 
   }
 
}  // end of Shop
 
 
/*************************************************
/ Barber class
**************************************************/
class Barber extends Thread
{
   private Shop shop;  // attribute
 
   public Barber(Shop s) // constructor
   {
     this.shop = s;
   }
 
   public void run() 
   {
      try
      {      	     
         Thread.sleep((int)(Math.random() * 3000));// wait for the thread to finish
      }
      catch (InterruptedException ie)
      {
	  System.out.println("Sleep failed");
      }
 
      shop.barberWorking();
   }
 }
 
 
/*************************************************
/ Customer class
**************************************************/
class Customer extends Thread 
{
   private int id;
   private Shop shop;
 
   public Customer(int cid, Shop s) 
   {
     this.id = cid;
     this.shop = s;
   }
 
   public void run() 
  {
      try
      {
         Thread.sleep((int)(Math.random() * 3000));  // wait for a while
      }
      catch (InterruptedException ie)
      {
	  System.out.println("Sleep failed");
      }
 
      shop.customerWorking(this.id);
  }
 
}
 

Cigarette-Smokers problem is another famous thread synchronization problem in computer science.

Consider a system with three smoker processes and one agent process. Each smoker continuously rolls a cigarette and then smokes it. But to roll and smoke a cigarette, the smoker needs three ingredients: tobacco, paper, and matches. One of the smoker processes has paper, another has tobacco, and the third has matches. The agent has an infinite supply of all three materials. The three smoker threads are initially blocked. The agent places two of the (different) ingredients on the table. The smoker who has the remaining ingredient then makes and smokes a cigarette, signaling the agent on completion. The agent then puts out another two of the three ingredients, and the cycle repeats.

Given the discussions and exercises in class, the implementation should look quite straightforward.

/**************************************************************************
 classic Cigarette-Smokers problem 
 
 @version 1.0 
 @author	Hui Wang  
****************************************************************************/
 
import java.util.*;
 
public class Main
{
   public static void main (String args[]) 
   {
      Table table = new Table();
 
      Agent agent = new Agent(table);
      Smoker smkr0 = new Smoker("S-toba", table ,Table.Tobacco);
      Smoker smkr1 = new Smoker("S-paper", table ,Table.Paper);
      Smoker smkr2 = new Smoker("S-match", table ,Table.Matches);
 
      // starting the threads
      agent.start();
      smkr0.start(); 
      smkr1.start(); 
      smkr2.start();
   }
}
 
/***********************************************************************
*   class Table
************************************************************************/
class Table
{
   // attributes
  public static final int Tobacco = 0;
  public static final int Paper = 1;
  public static final int Matches = 2;
 
  private static final int Everything = Tobacco + Paper + Matches;   // 3 
  private static final int Nothing = -1;
  public static final int END_TOKEN  = -100;
 
  private int onTable;   // what's on table ?
 
  // constructor
  public Table () 
  { 
     this.onTable = Nothing; 
  }
 
  public synchronized void put(int put) 
  {
     switch (put) 
     {
        case 1: System.out.println("puting : Tobacco + Paper"); break;
        case 2: System.out.println("puting : Tobacco + Matches"); break;
        case 3: System.out.println("puting : Matches + Paper"); break;
        default: System.out.print("puting :  END TOKEN"); break;
     }
 
     this.onTable = put;   //  put on the table
 
     if ( put != END_TOKEN )
     {  
        notifyAll();
        try { 
          wait(); } 
        catch (InterruptedException e) {...}
     }
     else
     {
        notifyAll();
        System.out.println(" ----> agent done");
     }
  }
 
   public synchronized int getAndSmoke( String id, int myHave) 
   {
 
     while ( ( this.onTable + myHave) != Everything && this.onTable != END_TOKEN )
     {
      try{
         wait();
      }
      catch (InterruptedException e) {...}
     }
 
     if (this.onTable != END_TOKEN)  // normal working
     {
        this.onTable = Nothing;   // take the stuff, emptying the table
 
       // smoking
       System.out.println( id + " is smoking........");
       try
       {
         Thread.sleep(4000);  // smoking for a while, blocking all other threads
       }
       catch (InterruptedException ie){...}
 
       System.out.println( id + " finish smoking.\n");
 
       notifyAll();
       return 0;
     }
     else //  read a END_TOKEN -100
     {
       System.out.println( "reading a END_TOKEN ----> " + id + " done");
       return -100;
     }
 
  } // end of method
 
} // end of Agent class
 
 
/***********************************************************************
*   class Smoker
************************************************************************/
class Smoker extends Thread 
{
   private String id;
   private Table table;
   private int myHave;
 
 
   public Smoker(String sid, Table tab, int mh) 
   {
      this.id = sid;
      this.table = tab;
      this.myHave = mh;
   }
 
   public void run() 
   {  
      int returnValuel;
 
      while (true) 
      {
         int returnValue = this.table.getAndSmoke(this.id, this.myHave);  // may or may not succeed
         if ( returnValue == -100)  // read a end token, done
            break;
      } 
 
   }
 
} // end of table
 
/***********************************************************************
*   class Agent
************************************************************************/
 
class Agent extends Thread 
{
   private Table table;
 
   public Agent(Table tab) 
   {
      this.table = tab;
   }
 
   public void run() 
   {
      Random rand = new Random();
      int putStuff1, putStuff2;
      int i = 0;
 
       while (i < 10)  // put 10 times then finish
       {
          do
          { 
             putStuff1 = Math.abs(rand.nextInt()) % 3 ;  // 0-2
             putStuff2 = Math.abs(rand.nextInt()) % 3 ;  // 0-2
          }
          while ( putStuff1 ==  putStuff2 );  // until different value
 
          System.out.println(putStuff1 + " + " +  putStuff2);
          this.table.put( putStuff1 + putStuff2);
          i++;
       }
 
       // finally , put END_TOKEN
       this.table.put(Table.END_TOKEN);
 
     }
 
 }  // end of agent

Below you find the code that I used to schedule the third presentations.

import java.util.*;
import java.io.*;
 
/**
 * Prints out the schedule of the third presentations.
 *
 * @author Franck van Breugel
 */
public class Presentation
{
 /**
  * Prints out the schedule of the third presentations.
  *
  * @param args none.
  * @throws Exception if file cannot be found.
  */
  public static void main(String[] args) throws Exception
  {
    final int NUMBER_OF_STUDENTS = 16;
    final String FILE_NAME = "COSC6490AA";
    final int MAX = 1000;
    final int LECTURES = 4;
    final int NUMBER_PER_LECTURE = 4;
 
    List<String> names = new ArrayList(NUMBER_OF_STUDENTS);
    Scanner input = new Scanner(new File(FILE_NAME));
    while (input.hasNext())
    {
      String[] record = input.nextLine().split(",");;
      names.add(record[1].trim() + " " + record[0].trim());
    }
 
    Random random = new Random();
    int number = random.nextInt(MAX);
    for (int i = 0; i < number; i++)
    {
      Collections.shuffle(names);
    }
 
    for (int i = 0; i < LECTURES; i++)
    {
      System.out.println("^ Slot ^ Student ^");
      for (int j = 0; j < NUMBER_PER_LECTURE  ; j++)
      {
        System.out.printf("| %d    | %s | %n", j + 1, names.remove(0));
      }
    }
  }
}