Java Tech Zone: 2014

Friday 7 March 2014

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:

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) {
   }
   ;
  }
 }
}

Sleeping barber problem using Reentrant Locks

package com.concurrency;

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

public class SleepingBarberUsingReentrantLock extends Thread {

 /* No of Chairs in the 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;
 
 /*
  * We create Customer pool which will be waiting for their hair cut.
  */
 public static CustomerPool customers = new CustomerPool(CHAIRS);
 /*
  * We create a ReentrantLock for barber with a condition to wait if the barber is not available
  */
 public static Lock barber = new ReentrantLock();
 public static Condition barberAvailable = barber.newCondition();
 /*
  * We create a ReentrantLock for chairs so that we can increment the counter safely.
  */
 public static Lock accessSeats = new ReentrantLock();

 /* THE CUSTOMER THREAD */

 class Customer extends Thread {

  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
    accessSeats.lock(); // 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.releaseCustomer(); // notify the barber that there is
           // a customer
     accessSeats.unlock(); // don't need to lock the chairs
     barber.lock();
     try {
      barberAvailable.await();  // now it's this customers turn
              // but we have to wait if the
             // barber is busy
     } catch (InterruptedException e) {
     } finally {
      barber.unlock(); 
     }
     notCut = false; 
     this.get_haircut(); // cutting...
    } else { // there are no free seats
     System.out.println("There are no free seats. Customer " + this.id + " has left the barbershop.");
     accessSeats.unlock(); // release the lock on the seats
     notCut = false; // the customer will leave since there
    }
   }
  }

  /* 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.acquireCustomer(); // tries to acquire a customer - if
           // none is available he goes to
           // sleep
     accessSeats.lock(); // at this time he has been awaken ->
           // want to modify the number of
           // available seats
     numberOfFreeSeats++; // one chair gets free
     barber.lock();
     try {
      barberAvailable.signal(); // the barber is ready to cut
     } finally {
      barber.unlock(); 
     }
     accessSeats.unlock(); // 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[]) {

  SleepingBarberUsingReentrantLock barberShop = new SleepingBarberUsingReentrantLock(); 
  barberShop.start();
 }

 public void run() {
  Barber barber = new Barber();
  barber.start(); 

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

class CustomerPool {

    private final Lock lock = new ReentrantLock();
    private final Condition poolAvailable = lock.newCondition();
    private int num_customers;
    private final int max_num_customers;


    public CustomerPool(int num_customer_pools) {
            this.max_num_customers = num_customer_pools;
            this.num_customers = 0;
    }

    public void acquireCustomer() throws InterruptedException {
        lock.lock();
        try {
            while (num_customers <= 0)
                poolAvailable.await();
            --num_customers;
        } finally {
            lock.unlock();
        }
    }

    public void releaseCustomer() {
        lock.lock();
        try {
            // check to ensure release does not occur before acquire
            if(num_customers >= max_num_customers)      
                return;
            ++num_customers;
            poolAvailable.signal();
        } finally {
            lock.unlock();
        }
    }
    
    public int getNumOfCustomers() {
     return num_customers;
    }
}

Pages

Friday 7 March 2014

Cigarette smokers problem using Semaphore

Sleeping barber problem using Semaphores

Sleeping barber problem using Reentrant Locks