Deadlock in Java code with Semaphore and acquire(int)

Question

I have the following Java code:

import java.util.concurrent.*;

class Foo{
    static Semaphore s = new Semaphore(1);

    public void fun(final char c, final int r){
        new Thread(new Runnable(){
            public void run(){
                try{ 
                    s.acquire(r);
                    System.out.println(c+"_"+r);
                    s.release(r+1);
                } catch(Exception e){ e.printStackTrace(); }
            }
        }).start();
    }
}

class ths{
    public static void main(String[]args) throws Exception{
        Foo f = new Foo();
        f.fun('B',2);
        f.fun('F',6);
        f.fun('A',1);
        f.fun('C',3);
        f.fun('D',4);
        f.fun('E',5);
    }
}

Ideally, this should print A_1 through F_6 in order and exit, but for some reason that doesn't happen. It usually prints A_1 and B_2 and then it gets stuck.

I can't find anything obviously wrong with my code. Any suggestions?

Answer 1

The basic problem is that acquire(int permits) does not guarantee that all permits will be grabbed at once. It could acquire fewer permits and then block while waiting for the rest.

Let's consider your code. When, say, three permits become available there's nothing to guarantee that they will be given to thread C. They could, in fact, be given to thread D to partially satisfy its acquire(4) request, resulting in a deadlock.

If you change the code like so, this fixes the problem for me:

public void fun(final char c, final int r){
    new Thread(new Runnable(){
        public void run(){
            try{ 
                while (!s.tryAcquire(r, 1, TimeUnit.MILLISECONDS)) {};
                System.out.println(c+"_"+r);
                s.release(r+1);
            } catch(Exception e){ e.printStackTrace(); }
        }
    }).start();
}

(On second thoughts, the above is also broken since there's no guarantee the correct thread will ever get the permits -- it could keep trying and timing out indefinitely.)