deadlock using Semaphore

Question

I have a simple question about managing Threads. I have 3 process that share the same Semaphore with one permit. in normal situation, the first process takes this permit and release two permit tho the second process. The second process release 3 permits to the third process. I given an example to illustrate my problem.

First one:

public class Process0 extends Thread{

Semaphore s;

public Process0(Semaphore s){
    this.s = s;
}

public void run(){
    try {
        sleep(20000);
        s.acquire();

        System.out.println("hello");
    } catch (InterruptedException ex) {
        Logger.getLogger(Process.class.getName()).log(Level.SEVERE, null, ex);
    }

    s.release(2);
    }
}

Second Process:

public class Process1 extends Thread{

Semaphore s;

public Process1(Semaphore s){
    this.s = s;
}

public void run(){
    try {
        this.sleep(10000);
        s.acquire(2);
        System.out.println("Hello 2");
    } catch (InterruptedException ex) {
        Logger.getLogger(Process1.class.getName()).log(Level.SEVERE, null, ex);
    }

    s.release(3);
}

}

And last one:

    public class Process2 extends Thread{

    Semaphore s;

    public Process2(Semaphore s){
        this.s = s;
    }

   public void run(){
        try {

            System.out.println("Acquire  process 3 ");
            s.acquire(3);

            System.out.println("Hello 3");
        } catch (InterruptedException ex) {
            Logger.getLogger(Process2.class.getName()).log(Level.SEVERE, null, ex);
        }

        }

    }

The problem is. When i run this three process and be sure that process 3 is the first that excute the acquire. I will have a deadlock. Process 2 never print "Hello 3" and process 1 never print "Hello 2".Why ?

Semaphore s = new Semaphore(1);

Process0 p = new Process0(s);
Process1 p1 = new Process1(s);
Process2 p2 = new Process2(s);
p.start();
p1.start();
p2.start();

Answer 1

Your Semaphore is constructed as new Semaphore(1), which only has one permit available to be acquired. The call s.acquire(3) will never return since the semaphore will never have three permits available. The attempt to acquire a single permit by Process also blocks since acquisitions are ordered and Process2 arrived "first":

The release method javadoc states that an acquisition can happen when

Some other thread invokes the release() method for this semaphore and the current thread is next to be assigned a permit.

This minimal, single-thread example will show you:

Semaphore s = new Semaphore(1);
s.acquire(2);
System.out.println("Didn't deadlock!");

The solution to this is to use Semaphore.acquire() which requests one permit, or Semaphore.acquire(1) which also requests only one permit.

You also need to make sure that you acquire and release the same amount of permits, unless you have a very good reason to misuse Semaphore. From Javadoc:

There is no requirement that a thread that releases a permit must have acquired that permit by calling acquire [or that a thread releases all of its permits]. Correct usage of a semaphore is established by programming convention in the application.

Additionally, it seems that you might be using the wrong synchronizer for this task. You could use a CyclicBarrier or other class usable for synchronization.

Answer 2

It took me some time to find out what you wanted to accomplish. Here's what I've come up with. Hope it helps.

The problem is that threads in your implementation are trying to acquire lock in some order. So thread waiting for 3 permits waits first, then comes the thread waiting for 2 permits, and obviously stands in line waiting for his 2 permits, then comes the first thread wanting just 1 permit. There is one permit available so it's good to go. Then it returns 2 permits. Unfortunately next in line is thread waiting for 3 permits, not that waiting for 2. Bummer. Blocked. That's what you observe.

If you made other threads to change places in line for acquire, everything would be fine. Here comes

s.tryAcquire(int permits)

and suddenly everything works fine.

I'll make example based on your code, with 1s sleep in busy wait loop to see what's going on.

import java.util.concurrent.Semaphore;

class Process0 extends Thread {

    Semaphore s;

    public Process0(Semaphore s){
        this.s = s;
    }

    public void run(){
        try {
            sleep(20000);
            s.acquire();

            System.out.println("hello");
        } catch (InterruptedException ex) {
            System.out.println(Process.class.getName());
        }

        s.release(2);
        System.out.println("released 2");
        }
    }

 class Process1 extends Thread{

    Semaphore s;

    public Process1(Semaphore s){
        this.s = s;
    }

    public void run(){
        try {
            this.sleep(10000);
            while(!s.tryAcquire(2)) {
                System.out.println("Busy waiting for 2 permits");
                sleep(1000);
            }
            System.out.println("Hello 2");
        } catch (InterruptedException ex) {
            System.out.println(Process.class.getName());
        }

        s.release(3);
        System.out.println("Released 3");
    }
}


 class Process2 extends Thread{

        Semaphore s;

        public Process2(Semaphore s){
            this.s = s;
        }

       public void run() {
            System.out.println("Acquire  process 3 ");
            while(!s.tryAcquire(3)) {
                System.out.println("Busy waiting for 3 permits");
                try {
                    sleep(1000);
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }

            System.out.println("Hello 3");

            }

        }



public class DaemonTest {
    public static void main(String[] args) {
        Semaphore s = new Semaphore(1);

        Process0 p = new Process0(s);
        Process1 p1 = new Process1(s);
        Process2 p2 = new Process2(s);
        p.start();
        p1.start();
        p2.start();
    }
}