4 replies to this topic

[skatescholar]

Hi, new to the forums new to programming! Im an engineering student doing an operating systems module with about 6 weeks Java experience and a little bit of C/C++ from before that. We have been given this bounded buffer problem as an assignment and I am truly lost. I understand the concept but have no clue how to implement that into a java program. There are a lot of examples of sample code for this problem online however we have been told we were are not allowed to use semaphores. Below is a brief of what we have been asked to do, any help/input would be great, cheers!

We have a buffer of a fixed size. A Producer thread inserts integers into the buffer, a Consumer thread takes them out. There are obvious constraints:

* The Producer cannot insert into a full buffer
* The Consumer cannot take from an empty buffer
* Updates to the buffer must be mutually exclusive

When roomAvailable is false the buffer is full, when true there is at least one free slot available for the Producer. When dataAvailable is false the buffer is empty, when true there is at least one integer in the buffer for the Consumer to remove. The buffer operates in a FIFO manner, i.e. the first item to go in is the first to come out.

[bobdark]

You have to use mutexes. Hope that helps. Come on, seriously now, what are you stuck on? Most people upon seeing something like "I need help" and no visible effort put into the task will just close the window and not even bother to think on your task.

[skatescholar]

Well I have a solution reached but its using semaphores and we've just been informed that we are not allowed to use semaphores so I have no clue what I should be doing as this is all we have been thought so far. I'll attach the code we have already come up with any pointers or tips would be great!

import java.util.concurrent.Semaphore;

// The Buffer
class BoundedBuffer{
    // Variables
    private Semaphore mutex, data, slot;
    private int nextIn, nextOut, size, occupied, ins, outs;
    private int[] Buffer;

    // Constructor
    public BoundedBuffer(int length){

        // set the size of the buffer.
        this.size = length;
        Buffer = new int[size];

        // initialise variables appropriately
        nextIn = nextOut = occupied = ins = outs = 0;

        // buffer is empty initially. number of empty slots = size
        // number of full slots = 0
        slot = new Semaphore(size);
        data = new Semaphore(0);

        // initialise mutex to 1 for use as single lock.
        mutex = new Semaphore(1);
    }

    // status accessor for private variables.
    public void printstatus() {
        System.out.println("Items inserted : " + ins);
        System.out.println("Items removed : " + outs);
        System.out.println("Spaces occupied : " + occupied);
        System.out.println("Delta : " + (ins - outs - occupied));
    }

    // insertItem method for adding to array.
    public void insertItem(int Item) throws InterruptedException{

    // acquire an empty slot for data production
    slot.acquire();

    // acquire the lock for mutual exclusion
    mutex.acquire();

    // insert item into buffer and modify relevant variables
    Buffer[nextIn % size] = Item;
    nextIn++;
    occupied++;
    ins++;

    // release lock for mutual exclusion
    mutex.release();

    // data has been added, release lock on data consumption
    data.release();
    }

    // removeItem method for removing from array
    public int removeItem() throws InterruptedException{

    // variable for temporarily storing removed data
    int Item;

    // acquire data lock, i.e., there is data available for consumption
    data.acquire();

    // acquire mutual exclusion lock
    mutex.acquire();

    // remove item from buffer and update relevant variables
    Item = Buffer[nextOut % size];
    nextOut++;
    occupied--;
    outs++;

    // release mutual exclusion lock
    mutex.release();

    // data has been removed, release lock on data production.
    slot.release();
    return Item;
    }
}

// Producer thread class for adding items to buffer
class Producer extends Thread {

    // Our thread works on these
    public BoundedBuffer workspace;
    public int currentItem;

    // Constructor
    public Producer(BoundedBuffer workspace) {
        this.workspace = workspace;
    }

    // What the Producer does
    public void run()
    {
        // use try block to implement exit message on interrupt.
        try {

            // loop until interrupted
            while(true)
            {
                // get a random integer between 0 and 100
                currentItem = Math.round(Math.round(Math.random() * 100));

                // use the inertItem method to add it to the buffer
                workspace.insertItem(currentItem);

                /*
                code used for debugging Producer threads.
                use to display value every time an item 
                is inserted.
                System.out.println("Producer : Item " + currentItem +
                " inserted in buffer");
                */    
            
                // Simulate a delay before the next Item is Produced
                sleep((int)(Math.random() * 30));
            }

        // when interrupted, exit politely.
        } catch (InterruptedException e) {
        System.out.println("Producer thread exiting now");
        }
    }
}

// Consumer thread class for removing items from the buffer
class Consumer extends Thread {

    // Thread works on these
    public BoundedBuffer workspace;
    public int currentItem;

    // Constructor
    public Consumer(BoundedBuffer workspace) {
        this.workspace = workspace;
    }

    // What the consumer thread does
    public void run()
    {
        // use try block to implement exit message on interrupt.
        try {
            // loop indefinitely until interrupted
            while(true)
            {
                // remove an item using the removeItem method
                currentItem = workspace.removeItem();

                /*
                code used for debugging Consumer threads.
                use to display value every time an
                item is removed.
                System.out.println("Consumer : Item " + currentItem + 
                " removed from buffer");
                */

                // Simulate a delay before the next Item is Consumed
                sleep((int)(Math.random() * 30));
            }
        // when interrupted, exit politely
        } catch (InterruptedException e) {
        System.out.println("Consumer thread exiting now");
        }
    }
}

// Watcher Thread for keeping track of events
class Watcher extends Thread {
    // what the thread works on
    public BoundedBuffer workspace;

    // Constructor
    public Watcher(BoundedBuffer workspace) {
        this.workspace = workspace;
    }

    // what the watcher does
    public void run()
    {
        // use try block to implement exit message on interrupt.
        try {
            // loop indefinitely until interrupted
            while(true)
            {
                // update user using printstatus method
                workspace.printstatus();
            
                //wait 2 seconds
                sleep(2000);
            }
        // when interrupted, exit politely
        } catch (InterruptedException e) {
        System.out.println("Watcher thread exiting now");
        }
    }
}

// Main
class Assignment01 {

    public static void main(String[] args) throws InterruptedException {


        /* make a BoundedBuffer object, with the size specified on 
        the command line, or 50 if no size was specified.*/
        int size = 50;
        if(args.length>0) {
            try {
                size = Integer.parseInt(args[0]);
            } catch (NumberFormatException e) {
                System.err.println("Argument must be an integer.");
            }
        }
        BoundedBuffer space = new BoundedBuffer(size);
        
        // create our threads
        Producer pthread = new Producer(space);
        Consumer cthread = new Consumer(space);
        Watcher wthread = new Watcher(space);

        // start our threads
        wthread.start();
        pthread.start();
        cthread.start();

        Thread.sleep(20*1000);
        Consumer cthread1 = new Consumer(space);
        cthread1.start();

        Thread.sleep(20*1000);
        Producer pthread1 = new Producer(space);
        Producer pthread2 = new Producer(space);
        pthread1.start();
        pthread2.start();

        Thread.sleep(20*1000);
        Consumer cthread2 = new Consumer(space);
        cthread2.start();
        // wait 2 minutes
        Thread.sleep(1 * 60 * 1000);

        // interrupt threads.
        pthread.interrupt();
        pthread1.interrupt();
        pthread2.interrupt();
        cthread.interrupt();
        cthread1.interrupt();
        cthread2.interrupt();
        wthread.interrupt();
    }
}

Edited by ZekeDragon, 12 April 2010 - 03:28 AM.
Please use [code] tags (the # button) when posting code.

[bobdark]

what are the constraints of the assignment?

[sourlemon]

Since you can't use semaphore, monitor would be a good alternative (and easier if you ask me). Have you learn the concept yet?

The point is that you put the objects you want to access in a monitor (or a room if you will). Only one person can enter the room at a time. So suppose the producer wants to produce an item in Buffer[nextIn]. Your code would look like this:

synchronized(Buffer[nextIn]){
 //This ensure that it is the only one accessing Buffer[nextIn]. If someone is using it, it'll automatically wait until Buffer[nextIn] is free.
      //your code to add item
}

Suppose you know the buffer is full, so you want the producer to sleep until someone calls it to wake up. You just put (if I remember correctly) the code below. It says, I'm waiting on Buffer Object. When you call wait, you release your lock on the buffer until you are notify.

synchronized(Buffer){
//To get the lock on buffer
     Buffer.wait();
}

To wake up the producer, you call notifyAll(), which wakes up everyone that is waiting for that object.

synchronized(Buffer){
//To get the lock on buffer
     Buffer.notifyAll();
}

Hopefully that helps. Good luck :)