Deadlock in Java code with Semaphore and acquire(int)

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(){
            publi开发者_开发问答c 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?

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.)

Semaphore does acquire all permits at once, otherwise it would not be a real semaphore. BUT: The Java version also has an internal waiting queue. And the behaviour of that queue is NOT serve best fit of currently free resources but more or less gather permits until the request of the first in the queue can be permitted. But before a thread enters that queue a check is done if the available permits allow the thread to avoid entering the queue at all.

I have modified your code to show that queue behaviour:

import java.util.concurrent.*;
public class SemaphoreTest{
    static Semaphore s = new Semaphore(0);

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

    public static void main(String[]args) throws Exception{
        SemaphoreTest f = new SemaphoreTest();

        f.fun('B',2);
        f.fun('F',6);
        f.fun('A',1);
        f.fun('C',3);
        f.fun('D',4);
        f.fun('E',5);

        while(s.hasQueuedThreads()){
            Thread.sleep(1000);
            System.out.println("release "+1+", available "+(s.availablePermits()+1));
            s.release(1);
        }
    }
}

Basically the following changes have been done:

• Start with 0 permits - let anyone enter the queue first.
• "Define" the order of queuing by giving each thread 500ms time after Thread.start.
• Each thread will call acquire but not release.
• The main thread will feed the semaphore slowly with one permit after the other.

This will give this output deterministically:

acquire 2
acquire 6
acquire 1
acquire 3
acquire 4
acquire 5
release 1, available 1
release 1, available 2
B_2
release 1, available 1
release 1, available 2
release 1, available 3
release 1, available 4
release 1, available 5
release 1, available 6
F_6
release 1, available 1
A_1
release 1, available 1
release 1, available 2
release 1, available 3
C_3
release 1, available 1
release 1, available 2
release 1, available 3
release 1, available 4
D_4
release 1, available 1
release 1, available 2
release 1, available 3
release 1, available 4
release 1, available 5
E_5
release 1, available 1

Which means: Each thread is awoken, if

• it is at the head of the queue.
• enough permits have been accumulated.