Java 并发 : Exclusive Queue Problem

Question

我正在尝试为“Little book of Semaphores”中的“Exclusive Queue”问题编写一个解决方案。问题表述如下:

想象一下，线程代表舞厅舞者，两种舞者(领导者和追随者)在进入舞池之前排成两个队列等待。当领导者到达时，它会检查是否有追随者在等待。如果是这样，他们都可以继续。否则它会等待。类似地，当跟随者到达时，它会检查领导者并相应地继续或等待。此外，每个领导者只能与一个追随者同时调用舞蹈，反之亦然。

书中提到它是使用信号量的解决方案，但我试图使用 Java 中的对象锁来解决它。这是我的解决方案:

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();
            } 

        }
    }
}

但是跑了一会儿就挂了。你能告诉我僵局在哪里以及我如何解决它吗？另外，我想在 Leader 和 Follower 完成后打印一个新行。我该怎么做？

Answer 1

这是一个典型的死锁:

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

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

防止这种情况最简单的方法是以相同的顺序获取锁(顺便说一句，同时使用Lock 和synchronized 不是一个好习惯)。还有其他检测死锁的技术，但在您的任务上下文中，更改算法应该更有益。

从简单开始 - 使用单锁使逻辑正确，然后在不破坏正确性的情况下做更多聪明的事情来提高并发性。