Differences

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

--- discussion [2007/11/01 18:34] – huiwang
+++ discussion [2007/11/23 13:46] (current) – franck
@@ Line 5: / Line 5: @@
-====== Slawomir's Sleeping Barber ======
+===== Slawomir's Sleeping Barber =====
@@ Line 136: / Line 136: @@
-====== Sleeping Barber using Semaphore======
+===== 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,
@@ Line 373: / Line 374: @@
 }
  </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>