为什么我的notify方法不能正常工作？

Question

我正在通过暂停做同样事情的线程来改进我的并发程序，以等待其中一个线程完成。但是，它不能正确地唤醒线程。下面是代码。

//to store graphs, if a thread finds the graph it is going to compute is in the entry, it waits, otherwise it compute then notify all other threads waiting on it.
Map<Graph, Object> entry = new ConcurrentHashMap<Graph, Object>();

public Result recursiveMethod(Graph g) {
        if (entry.get(g) != null) {//if the graph is in the entry, waits
            synchronized(entry.get(g)) {
                entry.get(g).wait();
            }
            //wakes up, and directly return the result
            return result;
        }
        synchronized(entry) {
            if (entry.get(g) == null)//if the graph is not in the entry, continue to compute
            entry.put(g,new Object());
        }
        //compute the graph recursively calls this method itself...
        calculate here...
        //wake up threads waiting on it, and remove the graph from entry
        synchronized(entry.get(g)){
            entry.get(g).notifyAll();
        }
        entry.remove(g);
        return result;
}

这个方法被许多线程调用。在线程开始计算之前，它会查找条目，以查看是否有另一个线程正在计算相同的图。如果是这样的话，它会等待。如果不是，它将继续计算。在它计算出结果之后，它会通知正在等待它的所有线程。

我使用映射将图形和对象配对。对象是锁。请注意，this map可以识别两个相同的图形，也就是说，以下代码返回true。

Graph g = new Graph();
entry.put(g, new Object());
Graph copy = new Graph(g);
entry.get(g) == entry.get(copy) //this is true

因此，entry.get(g)应该可以作为锁/监视器。然而，大多数线程还没有被唤醒，只有3-4个线程被唤醒。当正在等待的线程数等于我的计算机可以创建的线程数时，这意味着所有的线程都在等待，这个程序永远不会终止。

为什么entry.get(g).notifyAll()不能工作？

Answer 1

由于在检查地图的时间和在地图上操作的时间之间存在不同步的间隔，因此在逻辑中有许多漏洞，线程可能无法正确处理。您需要在地图检查之外进行同步，或者对ConcurrentMaps使用一些特殊的原子方法。

在编写并发代码时，我喜欢假装有一个恶意的gnome在后台运行，在任何可能的地方改变事情(例如，在同步块之外)。这是第一个让你开始的例子：

    if (entry.get(g) != null) {//if the graph is in the entry, waits
        synchronized(entry.get(g)) {

在同步块之外调用entry.get()两次。因此，你在这两次调用中得到的值可能不同(邪恶的侏儒尽可能频繁地改变地图)。实际上，当您尝试对它进行同步时，它可能是null，这将抛出异常。

此外，在等待循环条件改变时，应该始终在循环中进行wait()调用(这是由于可能出现虚假唤醒，或者在您的情况下，也可能是多次唤醒)。最后，您应该在通知之前更改循环条件。@AdrianShum很好地概述了如何正确使用wait/notify。您的while循环不应该包含所有内容，而应该包含在synchronized块中，只包含wait调用。这不是为了处理InterruptedException (另一个问题)，而是为了处理虚假唤醒和notifyAll调用。当您调用notifyAll时，所有等待的线程都会被唤醒，但只有一个线程可以继续运行，因此其他线程需要返回等待状态(因此出现while循环)。

简而言之，编写并发代码很难，而且您尝试实现的内容也并不简单。我建议在尝试完成这段代码之前，先阅读一本好书(比如Josh Bloch的"Java Concurrency In Practice")。

Answer 2

事实上，@jtahlborn已经提出了问题的关键。我试图通过讲述这里最明显的问题来补充。

试着让自己理解条件的基础知识，以及为什么它可以像正常信号一样解决这些竞争条件(例如在windows中)

你的逻辑现在是这样的(假设obj引用的是同一个对象)：

线程1：

if (!hasResult) {
    synchronized(obj) {
        obj.wait();
    }
}

线程2：

hasResult = false;
// do your work
synchronized(obj) {
   obj.notify();
}
hasResult= true;

你要知道线程1和线程2是并行运行的，因此你可能会遇到类似这样的情况

Thread 1                   Thread 2
                         hasResult = false
if (!hasResult)
                         do your work
                         synchronized(obj)
                         obj.notify()
                         end synchronized(obj)

synchronized(obj)
obj.wait()
end synchronized(obj)

线程1将永远等待。

你应该做的是

线程1：

synchronized(obj) {
    while (hasResult) {
        obj.wait();
    }
}

线程2：

hasResult = false;
synchronized(obj) {
   // do your work
   obj.notify();
   hasResult=true;
}

我相信这是@jtahlborn所说的最大的漏洞之一(还有其他的)。注意，设置条件和检查条件在同步块中都是受保护的。这就是条件变量如何解决前面说明的竞态条件的主要基本思想。首先让你自己理解这个想法，然后用一些更合理的东西重新设计你的代码。