Differences

This shows you the differences between two versions of the page.

--- discussion [2007/08/15 22:21] – created franck
+++ discussion [2007/11/23 13:46] (current) – franck
@@ Line 3: / Line 3: @@
 Comments, remarks, suggestions, corrections etcetera can be posted here.
+===== Slawomir's Sleeping Barber =====
+Please download the [[http://www.cse.yorku.ca/~cs253184/SleepingBarber.jar|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:
+<code java>
+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 )
+      {}
+    }
+  ...
+  }
+</code>
+and the run() method of the Customer class:
+<code java>
+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 )
+      {}
+    }
+  ...
+  }
+</code>
+===== Sleeping Barber using Semaphore=====
+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.
+<code java>
+/**************************************************************************
+ 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);
+  }
+}
+ </code>
+===== Cigarette-Smokers problem =====
+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.
+<code java>
+/**************************************************************************
+ 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
+</code>
+===== Franck's presentation scheduler =====
+Below you find the code that I used to schedule the third presentations.
+<code java>
+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));
+      }
+    }
+  }
+}
+</code>