Multithreaded program not running as expected

Question

I was trying to learn about semaphores, reading The Little Book of Semaphores by Allen B. Downey.

In that there is a puzzle:

Generalize the rendezvous solution. Every thread should run the following code:

1 rendezvous
2 critical point

The synchronization requirement is that no thread executes critical point until after all threads have executed rendezvous. You can assume that there are n threads and that this value is stored in a variable, n, that is accessible from all threads. When the first n − 1 threads arrive they should block until the nth thread arrives, at which point all the threads may proceed

My solution seems to work only sometimes, and in other cases it gets stuck after printing all rendezvous and a few but not all critical point

I am not able to figure out what is the issue here

Here is my code solution -

import java.util.concurrent.*;
import java.util.List;
import java.util.ArrayList;

class Main {
    
    private static final int n = 10;
    private static int counter = 0;
    private static final Semaphore mutex = new Semaphore(1);
    private static final Semaphore barrier = new Semaphore(0);

    private static class Runner implements Runnable {
        
        @Override
        public void run() {
            try {
                System.out.println("Rendezvous");
                mutex.acquire();
                counter = counter + 1;
                mutex.release();
                while (counter < n);
                barrier.release();
                barrier.acquire();
                System.out.println("Critical Section");
                barrier.release();
            } catch (InterruptedException ex) {
                System.out.println("Got exception while executing code for runner : " + ex.getMessage());
            }
        }
    }
    
    public static void main(String[] args) {
        List<Thread> threads = new ArrayList<>();
        for (int i = 0;i < n;i++) {
            Thread t = new Thread(new Runner());
            t.start();
            threads.add(t);
        }
        
        for (Thread t : threads) {
            try {
                t.join();
            } catch (InterruptedException ex) {
                System.out.println("Got exception while executing code for runner : " + ex.getMessage());
            }
        }
        
        
        System.out.println("Completed");
    }
}

Answer 1

The problem with the code is:

 while (counter < n);

It looks like it is trying to wait until counter gets incremented up to n. The issue is that nothing in the current thread does anything to increment the counter during the loop. For optimization purposes, the current thread is allowed to make assumptions that no other thread is operating on the variable. For example, the compiler may cache the value in a hardware register without going back to the shared memory location each time it checks the comparison. There are a ton of other things that can go wrong with this as well, but that is beyond the scope of this answer.

But the take away should be this: If a shared Integer is not being protected by a mutex as is the case here, AtomicInteger can be used to force synchronization of the value to all threads and defeat the aforementioned optimization as follows:

counter.incrementAndGet();
while( counter.get() < n );

It does not even need a mutex.

However, polling on the value of counter like this is not a good idea because the CPU will just just spin most of the time adding heat to the universe. There is a better way to do this.

Here is a very generous hint on how to solve the puzzle: Imagine there are N threads waiting to acquire() a semaphore that has no permits. If you release() N permits on the semaphore, all threads will continue.