Argthtjtr

I have a Producer Consumer problem and solved it by using semaphores but cannot formally explain which of the four conditions necessary for deadlock I have prevented. It can't be mutual exclusive access or non preemption which leaves either circular-wait or hold and wait. I clearly try to acquire two resources in both the insert and take methods, which hints to hold and wait being existing. Now there's only circular-wait left which I should have prevented but how? Or is my reasoning wrong and it's not circular-wait?

Edit: As people have repeatedly asked me what the problem is with my code because deadlock cannot happen, I want to say there's nothing wrong with it, I just want to know WHY it cannot happen. There are four conditions which need to be met for deadlock to occur which can be found here https://en.wikipedia.org/wiki/Deadlock#Necessary_conditions . I obviously prevented at least one condition or otherwise my code could result in a deadlock. Now I just want to know WHICH of the conditions I prevented.

My Buffers code looks like this:

private String store;

private int capacity;



private int nextIn;

private int nextOut;



private Semaphore mutex = new Semaphore(1);

private Semaphore numAvail = new Semaphore(0); //available items to consume

private Semaphore numFree; //free slots in buffer



public Buffer(int capacity) {

    this.capacity = capacity;

    this.store = new String[capacity];

    numFree = new Semaphore(capacity);

}



public void insert(String item) {



    try {

        //acquire a free slot in the array

        numFree.acquire();



        //get permit to insert

        mutex.acquire();

    } catch (InterruptedException ex) {

        Thread.currentThread().interrupt();

    }



    //critical region - insert to body

    store[nextIn] = item;



    nextIn++;



    //when at end of array begin at index 0 again

    if (nextIn == capacity) {

        nextIn = 0;

    }



    //signal that there is an item available

    numAvail.release();



    //signal that another thread can consume or produce now

    mutex.release();

}



public String take() {

    String item;



    try {

        //check if item exists to consume

        numAvail.acquire();



        //get permit to take

        mutex.acquire();



    } catch (InterruptedException ex) {

        Thread.currentThread().interrupt();

        ex.printStackTrace();

    }



    //critical region

    item = store[nextOut];



    nextOut++;



    if (nextOut == capacity) {

        nextOut = 0;

    }





    //signal other threads that they can consume or produce

    mutex.release();



    //signal that there is a free slot to insert now

    numFree.release();



    return item;

}

I believe that you prevented circular wait.

Circular wait occurs when each process waits for a resource which is being held by another process.

In your example, the only resource that is being waited for while holding another resource is the mutex. However, a thread that holds the mutex does never wait for anything.

For circular wait to occur, the mutex-holding thread would need to wait for something while having the mutex.