Java Concurrency: Exclusive Queue Problem

I am trying to write a solution for 'Exclusive Queue' problem from 'Little book of Semaphores'. Problem is stated as follows:

Imagine that threads represent ballroom dancers and that two kinds of dancers, leaders and followers, wait in two queues before entering the dance floor. When a leader arrives, it checks to see if there is a follower waiting. If so, they can both proceed. Otherwise it waits. Similarly, when a follower arrives, it checks for a leader and either proceeds or waits, accordingly. Also, there is a constraint that each leader can invoke dance concurrently with only o开发者_JS百科ne follower, and vice versa.

Book mentions it's solution using semaphores, but I am trying to solve it using Object lock in Java. Here is my solution:

ExclusiveQueuePrimitive.java:

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class ExclusiveQueuePrimitive {

    public static void main(String[] args) throws InterruptedException {
        System.out
                .println("-------------------------------Application START-------------------");
        final int NUM_RUN = 1000;
        // for (int j=0; j<NUM_RUN; j++) {
        for (;;) {
            Counters c = new Counters();
            int NUM_THREADS = 5;

            List<Thread> threads = new ArrayList<Thread>();

            for (int i = 0; i < NUM_THREADS; i++) {
                Thread tl = new Thread(new Leader(c, i + 1));
                Thread tf = new Thread(new Follower(c, i + 1));
                threads.add(tf);
                threads.add(tl);
                tf.start();
                tl.start();
            }
            for (int i = 0; i < threads.size(); i++) {
                Thread t = threads.get(i);
                t.join();
            }
        }
        // System.out.println("--------------------------------Application END-------------------");
    }
}

class Counters {

    public int leaders = 0;
    public int followers = 0;
    //public final Lock countMutex = new ReentrantLock();

    public boolean printed = false;
    public Lock printLock = new ReentrantLock();



    public final Lock leaderQueue = new ReentrantLock();
    public final Lock followerQueue = new ReentrantLock();

    public void dance(String str) {
        System.out.println("" + str);
    }

    public void printLine() {
        System.out.println("");
    }
}

class Leader implements Runnable {

    final Counters c;
    final int num;

    public Leader(Counters counters, int num) {
        this.c = counters;
        this.num = num;
    }

    @Override
    public void run() {

        synchronized (c.leaderQueue) {
            try {
                if (c.followers > 0) {

                        c.followers--;
                        synchronized (c.followerQueue) {
                            c.followerQueue.notify();
                        }


                } else {
                    c.leaders++;

                    c.leaderQueue.wait();
                }
                c.dance("Leader " + num + " called dance");
            } catch (InterruptedException e) {

                e.printStackTrace();
            } 

        }
    }
}

class Follower implements Runnable {

    final Counters c;
    final int num;

    public Follower(Counters counters, int num) {
        this.c = counters;
        this.num = num;
    }

    @Override
    public void run() {

        synchronized (c.followerQueue) {
            try {
                if (c.leaders > 0) {
                    synchronized (c.leaderQueue) {
                        c.leaders--;
                        c.leaderQueue.notify();
                    }
                } else {
                    c.followers++;
                    c.followerQueue.wait();
                }
                c.dance("Follower " + num + " called dance");

            } catch (InterruptedException e) {
                e.printStackTrace();
            } 

        }
    }
}

However, after running for a while, it hangs up. Can you tell me where is the deadlock and how I can fix it. Also, i want print a new line after pair of Leader and Follower are done. How can I do that?

That IS a classic deadlock:

class Leader {
    synchronized (c.leaderQueue) { ...
        synchronized (c.followerQueue) { ... }
    }
}

class Follower {
    synchronized (c.followerQueue) { ...
        synchronized (c.leaderQueue) { ... }
    }
}

The simplest thing to prevent that is to grab the locks in the same order (btw using Lock and synchronized together is not a good practice). There are other techniques to detect deadlocks, but in the context of your task it should be more beneficial to change the algorithm.

Start simple - use single lock to make the logic correct, then do more smart things to improve concurrency without breaking correctness.

You have a mutex on c.followerQueue and one on c.leaderQueue. On one side you acquire the leader queue first and then the follower queue, and on the other side you acquire the follower queue first.

This is bad. If one side grabs the follower lock, and the other side grabs the leader lock, then neither can proceed. You must avoid having inconsistent orderings of lock acquisitions.

To print a line after each pair finishes, just print in either the leader or the follower but not both. The code for the leader finishing implies a follower has finished also...