Kontera

Sunday, March 10, 2013

The Cigarette Smokers Problem

Multithreading - Multiprocessor operating systems
The Cigarette Smokers Problem
Consider a simulation with three smoker threads and one agent thread. Each
smoker continuously makes a cigarette and smokes it. But to make a cigarette, a
smoker needs three ingredients: tobacco, paper, and matches. One of the smoker
threads has only paper, another has only tobacco, and the third has only matches.
The agent thread has an infinite supply of all three materials. The three smoker
threads are initially blocked. The agent places two randomly chosen (different)
ingredients on the table and unblocks the one smoker who has the remaining
ingredient. The agent then blocks. The unblocked smoker removes the two
ingredients from the table, makes a cigarette, and smokes it for a random amount of
time, unblocking the agent on completion of smoking the cigarette. The agent then
puts out another random two of the three ingredients, and the cycle repeats.
Write a multi-class multithreaded Java program that uses a monitor to
synchronize the agent thread and the three smoker threads. Do not mechanically
translate semaphore code into monitor code! The agent thread executes in an
agent object created from an agent class. Each smoker thread executes in a smoker
object. All smoker objects are created from one smoker class whose constructor is
used to specify the ingredient possessed by the smoker object. A driver class with a
main method constructs the objects and starts the threads. Use a single monitor
object instantiated from a class Control for synchronization. Each of the four
threads invokes a synchronized monitor method for its synchronization. No
semaphores are allowed. No synchronized blocks are allowed, only synchronized
methods. No busy waiting is allowed. No calls to nap inside a synchronized method
are allowed (do not nap while holding the monitor object's lock, that is, while inside
a synchronized method or while inside a method called by a synchronized method).
Source Code:
/*
Cigarette Smoker's Problem Solution using java
Author : Sarju
Date: 10-03-2013
*/
import java.util.ArrayList;
import java.util.Random;
class CigaretteSmokersProblem {

    public static void main(String[] args) {
        table smokingtable = new table();

        agent controlAgent = new agent(smokingtable);

        controlAgent.start();

        for (int i = 0; i < 3; i++)
        {
            // each smoker-thread gets the controlAgent, so the thread can wake up the agent and we don't have to do notifyAll();
            smoker smokerThread = new smoker(smokingtable, i, "Smoker " + Integer.toString(i+1), controlAgent);
            smokerThread.start();
        }
    }
}

class smoker extends Thread {

    private table smokingtable = new table();
    private String ingredient;
    private int ingredientNumber;
    private agent controlAgent;

    public smoker(table pSmokingtable, int pIngredientNumber, String pName, agent pAgent)
    {
        // only save the number of the ingredient, we'll get the ingredient's name while the thread is running
        ingredientNumber = pIngredientNumber;
        this.smokingtable = pSmokingtable;
        setName(pName);
        controlAgent = pAgent;
    }

    @Override
    public void run()
    {
        while(true)
        {
            ingredient = smokingtable.getSmokerIngredient(ingredientNumber);

            if (!smokingtable.hasIngredient(ingredient) && !smokingtable.isEmpty())
            {
                System.out.println(getName() + " has " + ingredient + ".");
                try {
                    doSmoke();
                    System.out.println(getName() + " tells the agent to start the next round.");
                    // the thread tells the agent to continue
                    controlAgent.wake();
                } catch (Exception e) {}
            }
        }
    }

    public synchronized void doSmoke() throws Exception
    {
        System.out.println(getName() + " rolls the cigarette.");
        Thread.sleep(2500);
        System.out.println(getName() + " smokes.");
        Thread.sleep(2500);
        System.out.println(getName() + " has finished.");
    }

  }

class agent extends Thread {

    private table smokingtable;

    public agent(table pSmokingtable)
    {
        smokingtable = pSmokingtable;
    }

    @Override
    public void run()
    {
        while(true)
        {
            try {
                Thread.sleep(5000);
            } catch (Exception e) {}
            smokingtable.setAgentIngredients();
            // this triggers the smoker-threads to look at the table
            System.out.println("\n");
            System.out.println("The agents puts " + smokingtable.getAgentIngredients() + " on the table.");
            // pause the agent while one smoker thread is running
            pause();
        }
    }

    public synchronized void wake()
    {
        try
        {
            notify();
        } catch(Exception e){}
    }


    public synchronized void pause()
    {
        try
        {
            this.wait();
        } catch (Exception e) {}
    }

   
}

/*Class for creating table*/
class table {
    //Variables for storing ingredients(tabacco,paper,matches)
    private ArrayList allIngredients  = new ArrayList();
    private ArrayList agentIngredients = new ArrayList();

    public table()
    {
        allIngredients .add("tabacco");
        allIngredients .add("paper");
        allIngredients .add("matches");
    }
    /*Function for setting two ingredients randomly*/
    public void setAgentIngredients()
    {
        Random random = new Random();

        agentIngredients.clear();

        ArrayList copyAllElements = (ArrayList) allIngredients .clone();

        int ingredient1 = random.nextInt(copyAllElements.size());
        agentIngredients.add(copyAllElements.get(ingredient1));

        copyAllElements.remove(ingredient1);
        int ingredient2 = random.nextInt(copyAllElements.size());
        agentIngredients.add(copyAllElements.get(ingredient2));
    }
    /*Function for checking weather the table is empty*/
    public boolean isEmpty()
    {
        return (agentIngredients.size() == 0);
    }
    /*Function for getting two ingredients that
    are set previously by the function setAgentIngredients()*/
    public synchronized String getAgentIngredients()
    {
        notifyAll();
        return agentIngredients.toString();
    }
    /*Function for getting the ingredient
    with the corresponding smoker*/
    public synchronized String getSmokerIngredient(int pIngredient)
    {
        try {
            this.wait();
        } catch (Exception e) {}
        return allIngredients .get(pIngredient);
    }
    /*Function for Checking the smoker has the same ingredient
    as in the table if so smoking is is not possible*/
    public boolean hasIngredient(String ingredientName)
    {
        return (agentIngredients.contains(ingredientName));
    }

    public synchronized void pause()
    {
        try {
            this.wait();
        } catch (Exception e) {}
    }
}

Sunday, March 3, 2013

Semaphores - Multiprocessor operating systems using Java

/*PROGRAM 1 – Semaphores - Multiprocessor operating systems
Assume there are three processes: Pa, Pb, and Pc. Only Pa can output
the letter A, Pb B, and Pc C.
Utilizing only semaphores (and no other variables) the processes are
synchronized so that the output satisfies the following conditions:
a) A B must be output before any C's can be output.
b) B's and C's must alternate in the output string, that is, after the
first B is output, another B cannot be output until a C is output.
Similarly, once a C is output, another C cannot be output until a B is output.
c) The total number of B's and C's which have been output at any given point in the output
string cannot exceed the number of A's which have been output up to that point.
Examples
AACB -- invalid, violates a)
ABACAC -- invalid, violates b)
AABCABC -- invalid, violates c)
AABCAAABC -- valid
AAAABCBC -- valid
AB -- valid*/

/*AUTHORS: Sarju S, Nidhin AS
Date: 3rd March 2013*/
class ABC {
    int aCount=0;//Variable used to ensure the third rule
    boolean  isPrintBC= false;//Used to ensure the second rule
    //Function used to print A
    synchronized void printA() {
        System.out.print("A");
        aCount++;
        try{
            Thread.sleep(1000);
            notify();
        }
        catch(Exception e){}
    }
    //Function used to print B
    synchronized void printB() {
        if(isPrintBC)//True
        try {
            wait();
        } catch(InterruptedException e) {
        System.out.println("InterruptedException caught");
        }
        //False
        if(aCount>0){
            System.out.print("B");
            try{
            Thread.sleep(1000);
            }
            catch(Exception e){}
            aCount--;
            isPrintBC=true;
            notify();
           
   
        }
        //Rule 3 voilated
        else{
            isPrintBC=true;
            notify();
            }
        }
    //Function used to print C
    synchronized void printC() {
    if(!isPrintBC)//False
        try {
            wait();
        } catch(InterruptedException e) {
        System.out.println("InterruptedException caught");
        }
        //True
        if(aCount>0){
            System.out.print("C");
            try{
            Thread.sleep(1000);
            }
            catch(Exception e){}
           
            aCount--;
            isPrintBC=false;
            notify();
   
        }
        //Rule 3 voilated
        else{
            isPrintBC=false;
            notify();
            }
    }
}
//Process Pa outputs A
class Pa implements Runnable {
    ABC abc;
    Pa(ABC abc) {
        this.abc = abc;
        new Thread(this, "Pa").start();
    }
    public void run() {
        for(int i=0;i<10 br="" i="">        abc.printA();
        }
    }
}
//Process Pb outputs B
class Pb implements Runnable {
    ABC abc;
    Pb(ABC abc) {
        this.abc = abc;
        new Thread(this, "Pb").start();
    }
    public void run() {
        for(int i=0;i<10 br="" i="">            abc.printB();
        }
    }
}
//Process Pc outputs C
class Pc implements Runnable {
    ABC abc;
    Pc(ABC abc) {
        this.abc = abc;
        new Thread(this, "Pc").start();
    }
    public void run() {
        for(int i=0;i<10 br="" i="">        abc.printC();
        }
    }
}
//Main Class
class Multi_Process_OS {
    public static void main(String args[]) {
    ABC abc = new ABC();
        new Pa(abc);
        new Pb(abc);
        new Pc(abc);
    }
}