Multithreading: Understanding semaphore behaviour

Question

I am trying to get familiar with the concept of semaphores. For that reason I have written a simple semaphore class called MySemaphore and a Test-Class MutexThread utilizing said semaphore for mutual exclusion. Please find the code for my classes at the bottom of this post.

In my MutexThread-class I am using two synchronized(mutex) blocks in order to make sure that acquire() and the release() are both executed synchronized with my output to stdout. The result I get is as expected:

BORN -> Thread-0 born!
ACQUIRE -> Thread-0 is entering critical section!
BORN -> Thread-1 born!
BORN -> Thread-2 born!
BORN -> Thread-3 born!
BORN -> Thread-4 born!
BORN -> Thread-5 born!
BORN -> Thread-6 born!
BORN -> Thread-7 born!
BORN -> Thread-8 born!
BORN -> Thread-9 born!
RELEASE -> Thread-0 is leaving critical section!
INFO -> Thread-0 holdsLock: false
ACQUIRE -> Thread-1 is entering critical section!
RELEASE -> Thread-1 is leaving critical section!
INFO -> Thread-1 holdsLock: false
ACQUIRE -> Thread-2 is entering critical section!
RELEASE -> Thread-2 is leaving critical section!
INFO -> Thread-2 holdsLock: false
[...]

However, there are two things that I do not understand:

a) If I comment out the line System.out.println("INFO -> " + getName() + " holdsLock: " + holdsLock(mutex)); at the end of the while-loop the JVM does no longer cycle through the independet threads. The output now looks like this:

BORN -> Thread-0 born!
ACQUIRE -> Thread-0 is entering critical section!
BORN -> Thread-1 born!
BORN -> Thread-2 born!
[...]
BORN -> Thread-9 born!
RELEASE -> Thread-0 is leaving critical section!
ACQUIRE -> Thread-0 is entering critical section!
RELEASE -> Thread-0 is leaving critical section!
ACQUIRE -> Thread-0 is entering critical section!
[...]

Why is this? Why does only Thread-0 lock and unlock the MySemaphore-object? This is also true when I set MAX_PARALLEL_THREADS to an arbitrary N: In that case the JVM will always cycle through the same N threads, but other threads created never get access to the object. How can a single line of code (which just outputs some info to stdout) have such a huge impact?

b) When I use a semaphore-object from the class Semaphore from java.util.concurrent instead of my own MySemaphore-class the code does no longer work. It will lock up somewhere between the two synchronized(mutex)-blocks. The output looks like this:

BORN -> Thread-0 born!
ACQUIRE -> Thread-0 is entering critical section!
BORN -> Thread-1 born!
BORN -> Thread-2 born!
[...]
BORN -> Thread-9 born!
[... That's it. Program locks!]

Why is this? How is the class Semaphore from java.util.concurrent different than my own class? How does this result in the lock-up?

Code for my Semaphore-Class:

public class MySemaphore
{
    private int value;

    public MySemaphore(int value)
    {
        this.value = value;
    }

    public synchronized void acquire()
    {
        while(value <= 0)
        {
            try
            {
                wait();
            }
            catch (InterruptedException ex) {}
        }

        value--;
    }

    public synchronized void release()
    {
        value++;
        notify();
    }
}

Code for my Test-Class:

public class MutexThread extends Thread
{
    private MySemaphore mutex;

    public MutexThread(MySemaphore semaphore)
    {
        this.mutex = semaphore;
        start();
    }

    public void run()
    {
        while (true)
        {
            try
            {
                synchronized (mutex)
                {
                    mutex.acquire();
                    System.out.println("ACQUIRE -> " + getName() + " is entering critical section!");
                }

                sleep(1000);

                synchronized (mutex)
                {
                    mutex.release();
                    System.out.println("RELEASE -> " + getName() + " is leaving critical section!");
                }

                System.out.println("INFO -> " + getName() + " holdsLock: " + holdsLock(mutex));
            }
            catch (InterruptedException ex) {}
        }
    }

    public static void main(String[] args)
    {
        final int THREADS = 10;
        final int MAX_PARALLEL_THREADS = 1;

        MySemaphore mutex = new MySemaphore(MAX_PARALLEL_THREADS);
        Thread[] t = new Thread[THREADS];

        for (int i = 0; i < THREADS; i++)
        {
            t[i] = new MutexThread(mutex);
            System.out.println("BORN -> " + t[i].getName() + " born!");
        }
    }
}

Answer 1

The statement System.out.println(...) is an IO operation. IO operations are basically very slow and usually also include blocking the current thread until the IO operation has finished.

If a thread is blocked due to an IO operation, this is the chance for other waiting threads to get processor time again and run. And this is exactly the behavior you see, when having the IO operation in the code.

When removing that IO operation from the code, the current thread directly continues to acquire the mutex. There is only a very small time window, where this thread could get blocked by the system, so another thread gets running. But ... this time window and thus this little chance exists.

Additionally, you are notifying only one thread in the release method. Chances are better, if you notify all waiting threads, so the system has more choices. Do it this way:

public synchronized void release() {
    value++;
    notifyAll();
}

Run your program now for a while. I did get some changes in the running threads.

Answer 2

You use synchronized (mutex) both inside and outside the MySemaphore class. This always smells bad, and when you use java.util.concurrent.Semaphore instead of MySemaphore it causes a deadlock: the thread trying to release a semaphore is blocked on synchronized (mutex) which is owned by another thread which tries to aquire the semaphore.