Java 中的信号量多线程

Question

所以基本上这就是我要解决的问题：

David, Sean, and Frank plant seeds continuously. David digs the holes. Sean then places a seed in each hole. Frank then fills the hole up. There are several synchronization constraints:

Sean cannot plant a seed unless at least one empty hole exists, but Sean does not care how far David gets ahead of Sean.

Frank cannot fill a hole unless at least one hole exists in which Sean has planted a seed, but the hole has not yet been filled. Frank does not care how far Sean gets ahead of Frank.

Frank does care that David does not get more than MAX holes ahead of Frank. Thus, if there are MAX unfilled holes, David has to wait.

There is only one shovel with which both David and Frank need to dig and fill the holes, respectively.

Write the pseudocode for the 3 processes which represent David, Sean and Frank using semaphores as the synchronization mechanism. Make sure to initialize the semaphores.

这是我在 Java 中实现的解决方案，据我所知，与 standard solution:

相比，它不是很优雅而且有点浪费

import java.util.concurrent.Semaphore;

public class Holes {
    private static final int MAX = 3;
    private static final Semaphore mutexForShovel = new Semaphore(1, true);
    private static final Semaphore mutexForHoleCount = new Semaphore(1, true);
    private static int emptyHoleCount = 0, seededHoleCount = 0, finishedHoleCount = 0;

    public static void main(String[] args) {
        new Thread(() -> { // David
            try {
                while (true) {
                    if (emptyHoleCount < MAX) {
                        mutexForShovel.acquire(); // wait for shovel
                        System.out.println("David is digging a hole...");
                        Thread.sleep(200); // try annotating this
                        mutexForShovel.release(); // release shovel
                        mutexForHoleCount.acquire(); // enter critical section
                        emptyHoleCount++;
                        mutexForHoleCount.release(); // exit critical section
                        System.out.println("Empty = " + emptyHoleCount +
                                " Seeded = " + seededHoleCount +
                                " Finished = " + finishedHoleCount);
                    }
                }
            } catch (InterruptedException e) {
                System.out.println(e.toString());
            }
        }).start();

        new Thread(() -> { // Sean
            while (true) {
                try {
                    if (emptyHoleCount > 0) {
                        System.out.println("Sean is seeding a hole...");
                        Thread.sleep(200); // try annotating this
                        mutexForHoleCount.acquire(); // enter critical section
                        emptyHoleCount--;
                        seededHoleCount++;
                        mutexForHoleCount.release(); // exit critical section
                        System.out.println("Empty = " + emptyHoleCount +
                                " Seeded = " + seededHoleCount +
                                " Finished = " + finishedHoleCount);
                    }
                } catch (InterruptedException e) {
                    System.out.println(e.toString());
                }
            }
        }).start();

        new Thread(() -> { // Frank
            while (true) {
                try {
                    if (seededHoleCount > 0) {
                        mutexForShovel.acquire(); // ask for shovel
                        System.out.println("Frank is filling a hole...");
                        Thread.sleep(200); // try annotating this
                        mutexForShovel.release(); // release shovel
                        mutexForHoleCount.acquire(); // enter critical section
                        seededHoleCount--;
                        finishedHoleCount++;
                        mutexForHoleCount.release(); // exit critical section
                        System.out.println("Empty = " + emptyHoleCount +
                                " Seeded = " + seededHoleCount +
                                " Finished = " + finishedHoleCount);
                    }
                } catch (InterruptedException e) {
                    System.out.println(e.toString());
                }
            }
        }).start();
    }
}

我想我命令 acquire() 和 release() 操作的方式避免了任何“等待”，从而避免了死锁。但是，这是我在终端中从运行得到的输出：

David is digging a hole...
Empty = 1 Seeded = 0 Finished = 0
David is digging a hole...
Empty = 2 Seeded = 0 Finished = 0
David is digging a hole...
Empty = 3 Seeded = 0 Finished = 0

虽然我很困惑，但我在调试器中逐行运行它，这就是我得到的：

David is digging a hole...
Sean is seeding a hole...
Frank is filling a hole...
Empty = 1 Seeded = 0 Finished = 0
Empty = 0 Seeded = 1 Finished = 0
David is digging a hole...
Empty = 1 Seeded = 0 Finished = 1
Sean is seeding a hole...
David is digging a hole...
Empty = 0 Seeded = 0 Finished = 1
Empty = 0 Seeded = 1 Finished = 1
Frank is filling a hole...
Empty = 1 Seeded = 1 Finished = 1
Empty = 1 Seeded = 0 Finished = 2
Sean is seeding a hole...
David is digging a hole...
...

现在这是合理的输出！不是吗？继续，我删除了带注释的 Thread.sleep() 行，我得到了这个：

...
Sean is seeding a hole...
Frank is filling a hole...
Empty = 2 Seeded = 0 Finished = 29748
Empty = 2 Seeded = 1 Finished = 29747
Sean is seeding a hole...
Frank is filling a hole...
Empty = 1 Seeded = 1 Finished = 29748
Empty = 1 Seeded = 0 Finished = 29749
Sean is seeding a hole...
Frank is filling a hole...
Empty = 0 Seeded = 1 Finished = 29749
Empty = 0 Seeded = 0 Finished = 29750

Process finished with exit code 130 (interrupted by signal 2: SIGINT)

这又是不错的输出！

所以我想我现在有两个问题：

Q1：终端中的原始输出是否表明发生了死锁？如果是这样，我的代码的哪一部分是错误的，我该如何更改它？

问题 2：为什么我得到不同的输出运行基本相同的代码但方式不同？

非常感谢！！！

Answer 1

private static volatile int emptyHoleCount    = 0,
                            seededHoleCount   = 0,
                            finishedHoleCount = 0;

现在再试一次。线程不会注意到这些变量的变化，因为它们没有被标记为 volatile.

volatile has semantics for memory visibility. Basically, the value of a volatile field becomes visible to all readers (other threads in particular) after a write operation completes on it. Without volatile, readers could see some non-updated value.

The volatile modifier guarantees that any thread that reads a field will see the most recently written value.

您的 while 循环可能会受到编译器优化的影响，因此不会检查变量更新。将变量标记为 volatile 可以避免这种情况（ 就像说，嘿，不要优化这个，它可能会改变，所以不断检查它的值）。

当您休眠或调试它们时，您正在生成线程状态更改，这可能涉及您的线程在返回 时再次检查变量的值运行状态。没有那个“状态改变”，你的线程读取陈旧的数据。

除此之外，作为建议，您的线程包含一个非常危险的循环：

while(true)

如您在示例中所示，您可以通过 SIGINT 调用来阻止它们。我建议实施某种监视器或设置一些易变的布尔标志以优雅地停止它们。

涉及非易失性变量的死锁示例

public class UntilYouUpdateIt 
{
   public static boolean flag = true;

   public static void main(String[] args) throws InterruptedException 
   {
      Thread t1 = new Thread(()->
      {
        while(flag){}
        System.out.println("end");
      });
      t1.start();

      Thread.sleep(100);

      Thread t2 = new Thread(()->
      {
       flag = false;
       System.out.println("changed");
      });
      t2.start();
   }
}

上面的代码会输出：

changed

但节目永远不会结束。由于编译器优化，线程 t1 永远不会退出其循环，假设 flag 始终为真。将布尔值设置为 volatile 可以避免这种情况，就像您的示例的 int 变量一样。

Answer 2

如果不满足启动条件，您的线程将进入快速搅动状态。也就是说，它们变成“while(true) if (false)”，然后循环。由于无事可做，它们旋转得非常快，可能会对其他想要使用 CPU 的东西产生负面影响。我建议如果没有工作要做（不满足启动条件），让线程在再次检查之前休眠。这样线程（没有工作要做）与其他线程配合得很好。

你应该看看计算机性能图。如果遇到死锁，那么您会期望 CPU 图表都归零 - 没有 CPU 可以向前移动，因为每个图表都在等待另一个图表。我认为您实际上是在打击消费 - CPU 可能固定在 100% 并保持在那里。无限循环线程吸收了应用 CPU 并且脱离循环的线程永远无法获得足够的空气来启动。

Answer 3

是的，在无法工作时使用 volatile 和一些放松时间，而且，播种者 Sean 不应该 emptyHoleCount--; 填充者 Frank 应该。

约束 #3 是挖掘者 Dean 和填充者 Frank 之间的合同，挖掘者 Dean 正在履行 if(emptyHoleCount < MAX) 但播种者 Sean 正在干扰，而不是填充者 Frank。

Java 中的信号量多线程

Multithreading with Semaphores in Java

java

multithreading

deadlock

semaphore

synchronized