Cigarette smokers problem using Semaphore

Problem Statement:

The cigarette smokers problem was first presented by Suhas Patil in 1971. There are three smokers and one agent. A cigarette is made of three ingredients: tobacco, paper and match. Each smoker has infinite supply of one ingredient, e.g. the first one has infinite supply of tobacco, the second one has infinite supply of paper and the last one has infinite of match. The agent has infinite supply of all ingredients. The agent repeatedly chooses two ingredients at random and puts them on the table, and the smoker who has the complementary ingredient can take the two ingredients and make a cigarette to smoke. For example, if the agent puts tobacco and paper on the table, the smoker who has infinite supply of match can make a cigarette. In this problem, the agent represents the operating system and the smokers represent the processes. The operating system should allocate the required resources to the processes and, at the same time, avoid deadlock.

You can find more details on different versions here:

• https://www.comp.nus.edu.sg/~phanquyt/cs2106/implementation_smokers.html 
• The Little Book of Semaphores

Below code is for the "Interesting Version" as specified on the above two sites.

package com.concurrency;

import java.util.concurrent.Semaphore;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class CigaretteSmoker {

 /**
  * Boolean variables indicate whether or not an ingredient is on the table.
  */
 boolean isTobacco = false;
 boolean isPaper = false;
 boolean isMatch = false;
 
 /**
  * The pushers use tobaccoSem to signal the smoker with tobacco, and the other semaphores likewise.
  */
 public static Semaphore tobaccoSem = new Semaphore(0);
 public static Semaphore paperSem = new Semaphore(0);
 public static Semaphore matchSem = new Semaphore(0);
 
 /**
  * Semaphore for signaling ingredients are available
  */
 public static Semaphore tobacco = new Semaphore(0);
 public static Semaphore paper = new Semaphore(0);
 public static Semaphore match = new Semaphore(0);
 
 /**
  * All the agents will wait on agentSem and each time agentSem is signaled, one
  * of the Agents wakes up and provides ingredients by signaling two semaphores
  */
 public static Semaphore agentSem = new Semaphore(1);
 
 public static Lock mutex = new ReentrantLock();
 
 /**
  * This method will initiate all the 3 Pushers
  * 
  * Description from http://www.greenteapress.com/semaphores/downey05semaphores.pdf
  * 
  * The solution proposed by Parnas uses three helper threads called “pushers” that
  * respond to the signals from the agent, keep track of the available ingredients,
  * and signal the appropriate smoker.
  */
 
 public void initPushers() {
  Thread pusherA = new Thread() {
   public void run() {
    while(true) {
     try {
      tobacco.acquire();
      System.out.println("Pusher A for tobacco is active");
      mutex.lock();
      try {
       if(isPaper) {
        isPaper = false;
        matchSem.release();
       } else if(isMatch) {
        isMatch = false;
        paperSem.release();
       } else {
        isTobacco = true;
       }
      } finally {
       mutex.unlock();
      }
     } catch (InterruptedException e) {
      e.printStackTrace();
     }
    }
   };
  };
  Thread pusherB = new Thread() {
   public void run() {
    while(true) {
     try {
      paper.acquire();
      System.out.println("Pusher B for Paper is active");
      mutex.lock();
      try {
       if(isTobacco) {
        isTobacco = false;
        matchSem.release();
       } else if(isMatch) {
        isMatch = false;
        tobaccoSem.release();
       } else {
        isPaper = true;
       }
      } finally {
       mutex.unlock();
      }
     } catch (InterruptedException e) {
      e.printStackTrace();
     }
    }
   };
  };
  Thread pusherC = new Thread() {
   public void run() {
    while(true) {
     try {
      match.acquire();
      System.out.println("Pusher C for Match is active");
      mutex.lock();
      try {
       if(isPaper) {
        isPaper = false;
        tobaccoSem.release();
       } else if(isTobacco) {
        isTobacco = false;
        paperSem.release();
       } else {
        isMatch = true;
       }
      } finally {
       mutex.unlock();
      }
     } catch (InterruptedException e) {
      e.printStackTrace();
     }
    }
   };
   
  };
  pusherA.start();
  pusherB.start();
  pusherC.start();
 }
 
 /**
  * This method will initialize all the 3 smokers. Smoker will perform following task:
  * 
  * 1> Try to acquire the ingredient semaphore so that smoker can start only when the necessary ingredients are present. This will be signaled by the Pushers. 
  * 2> Make Cigarette
  * 3> Release the agentSem semaphore so that Agent can place the ingredients again on the table.
  * 4> Start smoking
  */
 public void initSmokers() {
  Thread tobaccoSmoker = new Thread() {
   @Override
   public void run() {
    while(true) {
     try {
      tobaccoSem.acquire();
      makeCigarette();
      agentSem.release();
      smoke();
     } catch (InterruptedException e) {
      e.printStackTrace();
     }
    }
   }
   
   public void makeCigarette() {
    System.out.println("tobaccoSmoker is making cigratte");
    try {
     sleep(5000);
    } catch (InterruptedException ex) {
    }
    System.out.println("tobaccoSmoker is cigratte making completed");
   }
   
   public void smoke() {
    System.out.println("tobaccoSmoker is smoking");
    try {
     sleep(5000);
    } catch (InterruptedException ex) {
    }
   }
  };
  
  Thread matchSmoker = new Thread() {
   @Override
   public void run() {
    while(true) {
     try {
      matchSem.acquire();
      makeCigarette();
      agentSem.release();
      smoke();
     } catch (InterruptedException e) {
      e.printStackTrace();
     }
    }
   }
   
   public void makeCigarette() {
    System.out.println("matchSmoker is making cigratte");
    try {
     sleep(5000);
    } catch (InterruptedException ex) {
    }
    System.out.println("matchSmoker is cigratte making completed");
   }
   
   public void smoke() {
    System.out.println("matchSmoker is smoking");
    try {
     sleep(5000);
    } catch (InterruptedException ex) {
    }
   }
  };
  
  Thread paperSmoker = new Thread() {
   @Override
   public void run() {
    while(true) {
     try {
      paperSem.acquire();
      makeCigarette();
      agentSem.release();
      smoke();
     } catch (InterruptedException e) {
      e.printStackTrace();
     }
    }
   }
   
   public void makeCigarette() {
    System.out.println("paperSmoker is making cigratte");
    try {
     sleep(5000);
    } catch (InterruptedException ex) {
    }
    System.out.println("paperSmoker is cigratte making completed");
   }
   
   public void smoke() {
    System.out.println("paperSmoker is smoking");
    try {
     sleep(5000);
    } catch (InterruptedException ex) {
    }
   }
  };
  
  tobaccoSmoker.start();
  matchSmoker.start();
  paperSmoker.start();
 }
 
 
 /**
  * This method will initialize all the 3 agents. Agents will perform following task:
  * 
  * 1> Try to acquire agentSem Semaphore so that they release the ingredients
  * 2> Places the ingredients on the table. This is done by releasing the respective ingredients semaphore thereby signaling the Pushers to takeover.
  */
 public void initAgents() {
  Thread agentA = new Thread() {
   @Override
   public void run() {
    while(true) {
     try {
      agentSem.acquire();
      System.out.println("Agent A is active and will release provide Tobacco & Paper ingredients.");
      tobacco.release();
      paper.release();
     } catch (InterruptedException e) {
      e.printStackTrace();
     }
    }
   }
  };
  Thread agentB = new Thread() {
   @Override
   public void run() {
    while(true) {
     try {
      agentSem.acquire();
      System.out.println("Agent B is active and will release provide Match & Paper ingredients.");
      match.release();
      paper.release();
     } catch (InterruptedException e) {
      e.printStackTrace();
     }
    }
   }
  };
  Thread agentC = new Thread() {
   @Override
   public void run() {
    while(true) {
     try {
      agentSem.acquire();
      System.out.println("Agent C is active and will release provide Tobacco & Match ingredients.");
      tobacco.release();
      match.release();
     } catch (InterruptedException e) {
      e.printStackTrace();
     }
    }
   }
  };
  agentA.start();
  agentB.start();
  agentC.start();
 }

 public static void main(String[] args) {
  CigaretteSmoker cs = new CigaretteSmoker();
  cs.initAgents();
  cs.initPushers();
  cs.initSmokers();
 }
}

References:

• http://en.wikipedia.org/wiki/Cigarette_smokers_problem
• https://www.comp.nus.edu.sg/~phanquyt/cs2106/implementation_smokers.html 
• http://www.greenteapress.com/semaphores/downey05semaphores.pdf

Sleeping barber problem using Semaphores

Problem Statement: 

The barber has one barber chair and a waiting room with a number of chairs in it. When the barber finishes cutting a customer's hair, he dismisses the customer and then goes to the waiting room to see if there are other customers waiting. If there are, he brings one of them back to the chair and cuts his hair. If there are no other customers waiting, he returns to his chair and sleeps in it.

Each customer, when he arrives, looks to see what the barber is doing. If the barber is sleeping, then the customer wakes him up and sits in the chair. If the barber is cutting hair, then the customer goes to the waiting room. If there is a free chair in the waiting room, the customer sits in it and waits his turn. If there is no free chair, then the customer leaves.

package com.concurrency;

import java.util.concurrent.Semaphore;

public class SleepingBarber extends Thread {

 /* PREREQUISITES */

 /*
  * we create the semaphores. First there are no customers and the barber is
  * asleep so we call the constructor with parameter 0 thus creating
  * semaphores with zero initial permits. Semaphore(1) constructs a binary
  * semaphore, as desired.
  */

 public static Semaphore customers = new Semaphore(0);
 public static Semaphore barber = new Semaphore(0);
 public static Semaphore accessSeats = new Semaphore(1);

 /* we denote that the number of chairs in this barbershop is 5. */

 public static final int CHAIRS = 5;

 /*
  * we create the integer numberOfFreeSeats so that the customers can either
  * sit on a free seat or leave the barbershop if there are no seats
  * available
  */

 public static int numberOfFreeSeats = CHAIRS;

 /* THE CUSTOMER THREAD */

 class Customer extends Thread {

  /*
   * we create the integer iD which is a unique ID number for every
   * customer and a boolean notCut which is used in the Customer waiting
   * loop
   */

  int iD;
  boolean notCut = true;

  /* Constructor for the Customer */

  public Customer(int i) {
   iD = i;
  }

  public void run() {
   while (notCut) { // as long as the customer is not cut
    try {
     accessSeats.acquire(); // tries to get access to the chairs
     if (numberOfFreeSeats > 0) { // if there are any free seats
      System.out.println("Customer " + this.iD
        + " just sat down.");
      numberOfFreeSeats--; // sitting down on a chair
      customers.release(); // notify the barber that there is
            // a customer
      accessSeats.release(); // don't need to lock the chairs
            // anymore
      try {
       barber.acquire(); // now it's this customers turn
            // but we have to wait if the
            // barber is busy
       notCut = false; // this customer will now leave
           // after the procedure
       this.get_haircut(); // cutting...
      } catch (InterruptedException ex) {
      }
     } else { // there are no free seats
      System.out.println("There are no free seats. Customer "
        + this.iD + " has left the barbershop.");
      accessSeats.release(); // release the lock on the seats
      notCut = false; // the customer will leave since there
          // are no spots in the queue left.
     }
    } catch (InterruptedException ex) {
    }
   }
  }

  /* this method will simulate getting a hair-cut */

  public void get_haircut() {
   System.out.println("Customer " + this.iD
     + " is getting his hair cut");
   try {
    sleep(5050);
   } catch (InterruptedException ex) {
   }
  }

 }

 /* THE BARBER THREAD */

 class Barber extends Thread {

  public Barber() {
  }

  public void run() {
   while (true) { // runs in an infinite loop
    try {
     customers.acquire(); // tries to acquire a customer - if
           // none is available he goes to
           // sleep
     accessSeats.acquire(); // at this time he has been awaken ->
           // want to modify the number of
           // available seats
     numberOfFreeSeats++; // one chair gets free
     barber.release(); // the barber is ready to cut
     accessSeats.release(); // we don't need the lock on the
           // chairs anymore
     this.cutHair(); // cutting...
    } catch (InterruptedException ex) {
    }
   }
  }

  /* this method will simulate cutting hair */

  public void cutHair() {
   System.out.println("The barber is cutting hair");
   try {
    sleep(5000);
   } catch (InterruptedException ex) {
   }
  }
 }

 /* main method */

 public static void main(String args[]) {

  SleepingBarber barberShop = new SleepingBarber(); // Creates a new
               // barbershop
  barberShop.start(); // Let the simulation begin
 }

 public void run() {
  Barber giovanni = new Barber(); // Giovanni is the best barber ever
  giovanni.start(); // Ready for another day of work

  /* This method will create new customers for a while */

  for (int i = 1; i < 16; i++) {
   Customer aCustomer = new Customer(i);
   aCustomer.start();
   try {
    sleep(2000);
   } catch (InterruptedException ex) {
   }
   ;
  }
 }
}

Reentrant Lock in Java

- ReentrantLock in Java is added on java.util.concurrent package in Java 1.5 along with other concurrent utilities.
- ReentrantLock implements Lock, providing the same mutual exclusion and memory visibility guarantees as synchronized.
- Acquiring a ReentrantLock has the same memory semantics as entering a synchronized block, and releasing a ReentrantLock has the same memory semantics as exiting a synchronized block.
- And like synchronized,ReentrantLock offers reentrant locking semantics i.e. it allows a thread to recursively acquire the same lock that it is holding.

Extended capabilities include:

• Non block structured Locking:  With intrinsic locks, acquire release pairs are block structured. A lock is always released in the same basic block in which it  was  acquired,  regardless  of  how  control  exits  the  block. However in reentrant lock you can acquire the lock in one method and release it in some other method.
• The ability to lock interruptibly: The lockInterruptibly method allows you to try to acquire a lock while  remaining responsive to interruption. lockInterruptibly() may block if the lock is already held by another thread and will wait until the lock is acquired. This is the same as with regular lock(). But if another thread interrupts the waiting thread lockInterruptibly() will throw InterruptedException.
• The ability to have more than one condition variable per monitor. Monitors that use the synchronized keyword can only have one. This means reentrant locks support more than one wait()/notify() queue.
• Fairness: The constructor for this class accepts an optional fairness parameter. When set true, under contention, locks favor granting access to the longest-waiting thread. Otherwise this lock does not guarantee any particular access order. Programs using fair locks accessed by many threads may display lower overall throughput (i.e., are slower; often much slower) than those using the default setting, but have smaller variances in times to obtain locks and guarantee lack of starvation. Synchronized blocks are unfair.
• Polled and Timed Lock Acquisition: ReentrantLock provides convenient tryLock() method, which acquires lock only if its available or not held by any other thread. An overloaded method of tryLock takes the time it should wait and try acquiring the lock before exiting.

 Examples:

1. Guarding Object State Using ReentrantLock. 
   
   

   void lockTest() {
    Lock lock = new ReentrantLock();
    lock.lock();
    try {
     // update object state
     // catch exceptions and restore invariants if necessary
    } finally {
     lock.unlock();
    }
   }
   

   
   This code is somewhat more complicated than using intrinsic locks. The lock must be released in a finally block. Otherwise, the lock would never be released if the guarded code were to throw an exception.
   
   
2. Polled and Timed Lock acquisition
   
   

   package com.concurrency;
   
   import java.util.concurrent.TimeUnit;
   import java.util.concurrent.locks.Lock;
   import java.util.concurrent.locks.ReentrantLock;
   
   public class ReentrantLockingDemo {
    final Lock lock = new ReentrantLock();
   
    public static void main(final String... args) {
     new ReentrantLockingDemo().go();
    }
   
    private void go() {
     new Thread(newRunable(), "Thread1").start();
     new Thread(newRunable(), "Thread2").start();
    }
   
    private Runnable newRunable() {
     return new Runnable() {
   
      @Override
      public void run() {
       do {
        try {
   
         if (lock.tryLock(500, TimeUnit.MILLISECONDS)) {
          try {
   
           System.out.println("locked thread " + Thread.currentThread().getName());
           Thread.sleep(1000);
          } finally {
           lock.unlock();
           System.out.println("unlocked locked thread " + Thread.currentThread().getName());
          }
          break;
         } else {
          System.out.println("unable to lock thread " + Thread.currentThread().getName() + " will re try again");
         }
        } catch (InterruptedException e) {
         e.printStackTrace();
        }
       } while (true);
      }
     };
    }
   }
   

   
   Output:
   locked thread Thread1
   unable to lock thread Thread2 will re try again
   unlocked locked thread Thread1
   locked thread Thread2
   unlocked locked thread Thread2
   
   
3. Interruptible Lock Acquisition.
   
   

   package com.concurrency;
   
   import java.util.concurrent.TimeUnit;
   import java.util.concurrent.locks.Lock;
   import java.util.concurrent.locks.ReentrantLock;
   
   public class ReentrantLockInterruptiblyDemo {
    private Lock lock = new ReentrantLock();
    public ReentrantLockInterruptiblyDemo() {
     lock.lock();
    }
    
     public void f() {
      try {
       // This will never be available to a second task
       lock.lockInterruptibly(); // Special call
       System.out.println("lock acquired in f()");
      } catch(InterruptedException e) {
       System.out.println("Interrupted from lock acquisition in f()");
      }
     }
     public static void main(String[] args) throws Exception {
     Thread t = new Thread(new Blocked2());
     t.start();
     TimeUnit.SECONDS.sleep(1);
     System.out.println("Issuing t.interrupt()");
     t.interrupt();
    }
   }
   
   class Blocked2 implements Runnable {
    ReentrantLockInterruptiblyDemo blocked = new ReentrantLockInterruptiblyDemo();
    public void run() {
     System.out.println("Waiting for f() in BlockedMutex");
     blocked.f();
     System.out.println("Broken out of blocked call");
    }
   }
    
   

   
   Output:
   Waiting for f() in BlockedMutex
   Issuing t.interrupt()
   Interrupted from lock acquisition in f()
   Broken out of blocked call
   
   
4. Using conditions in ReentrantLock.
   
   This Example is taken from http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/Condition.html
   
   We have a bounded buffer which supports put and take methods. If a take is attempted on an empty buffer, then the thread will block until an item becomes available; if a put is attempted on a full buffer, then the thread will block until a space becomes available. We would like to keep waiting put threads and take threads in separate wait-sets so that we can use the optimization of only notifying a single thread at a time when items or spaces become available in the buffer. This can be achieved using two Condition instances.
   
   

   public class BoundedBuffer {
    final Lock lock = new ReentrantLock();
    final Condition notFull = lock.newCondition();
    final Condition notEmpty = lock.newCondition();
   
    final Object[] items = new Object[100];
    int putptr, takeptr, count;
   
    public void put(Object x) throws InterruptedException {
     lock.lock();
     try {
      while (count == items.length)
       notFull.await();
      items[putptr] = x;
      if (++putptr == items.length)
       putptr = 0;
      ++count;
      notEmpty.signal();
     } finally {
      lock.unlock();
     }
    }
   
    public Object take() throws InterruptedException {
     lock.lock();
     try {
      while (count == 0)
       notEmpty.await();
      Object x = items[takeptr];
      if (++takeptr == items.length)
       takeptr = 0;
      --count;
      notFull.signal();
      return x;
     } finally {
      lock.unlock();
     }
    }
   }