经典问题Single Lane Bridge Problem的无饥饿解决方案

Question

我正在尝试为经典的单车道桥问题提供解决方案，其中单车道桥连接两个村庄。它只使用一根线，因此如果农民同时跳到桥的两侧，就会陷入僵局。到目前为止，这是我的解决方案，但我不确定如何让它免于饥饿？

public class SingleLaneBridge {

  public static void main(String[] args)
  {
    final Bridge bridge = new Bridge();

    Thread thNorthbound = new Thread( new Runnable() {

      @Override
      public void run() {

        while(true) {
          Farmer farmer = new Farmer(bridge);
          Thread th = new Thread(farmer);
          farmer.setName("North Farmer : "+ th.getId());
          th.start();
          try {
            TimeUnit.SECONDS.sleep((long)(Math.random()*10));
          } catch(InterruptedException iex) {
            iex.printStackTrace();
          }
        }

      }
    });

    Thread thSouthbound = new Thread( new Runnable() {

      @Override
      public void run() {

        while(true) {
          Farmer farmer = new Farmer(bridge);
          Thread th = new Thread(farmer);
          farmer.setName("South Farmer : "+th.getId());
          th.start();
          try {
            TimeUnit.SECONDS.sleep((long)(Math.random()*10));
          }
          catch(InterruptedException iex)
          {
            iex.printStackTrace();
          }
        }
      }
    });

    thNorthbound.start();
    thSouthbound.start();
  }

}

class Bridge {
  private final Semaphore semaphore;

  public Bridge() {
    semaphore = new Semaphore(1);
  }
  public void crossBridge(Farmer farmer) {
    try {
      System.out.printf("Farmer trying to cross the bridge.\n",farmer.getName());
      semaphore.acquire();
      System.out.printf("Farmer crossing the bridge.\n",farmer.getName());
      long duration = (long)(Math.random() * 10);
      TimeUnit.SECONDS.sleep(duration);
    }
    catch(InterruptedException iex) {
      iex.printStackTrace();
    }
    finally {
      System.out.printf("Farmer as crossed the bridge.\n",farmer.getName());
      semaphore.release();
    }
  }
}

class Farmer implements Runnable
{
  private String name;
  private Bridge bridge;

  public Farmer(Bridge bridge)
  {
    this.bridge = bridge;
  }

  public void run() {
    bridge.crossBridge(this);
  }

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }
}

Answer 1

首先，免责声明：您问题的某些部分并没有真正意义，但我认为这可能更多是由于误用术语而不是误解本身。不幸的是，如果您想清楚地传达您的问题并理解您阅读的内容，那么术语实际上非常重要。我在下面已经尽力了，但我很可能误解了你真正的问题。

It only uses one thread […]

我不太清楚你的意思；它实际上为每个农民启动了一个单独的线程。

It […] can become deadlocked if farmers jump on either side of the bridge at the same time.

这是不正确的；这里唯一的锁定机制是单个信号量，任何获得许可的线程都保证在再次尝试获取许可之前释放它，因此不可能 deadlock.

我发现您的代码存在三个主要问题：

您的介绍表明它正在尝试模拟单车道桥梁；但它并没有真正做到这一点，至少我理解 "single-lane bridge" 的概念。具体来说：
- 您的代码在任何给定时间只允许一名农民使用这座桥；但是如果有很多农民都想朝同一个方向过桥，那么 "single-lane bridge" 就可以了。（A "single-lane bridge" 应该只能防止两个农民在相反方向穿过。）
  - 这个问题是您所说的解决方案 "only uses one thread" 的意思吗？
- 如果农民F和G都在同一个方向，而农民F在 farmer G 之前到达，我认为 "single-lane bridge" 永远不会让 farmer G 在 farmer F[=90 之前交叉=].但是，您的代码不提供该保证。（N.B。此保证仅适用于相同方向的农民。如果农民相反方向，则可能如果已经有另一个 farmer 与 farmer G 朝着相同的方向前进，那么让 farmer G 先走是有效的。这是你要做出的设计决定。）

您的代码在 try 块中调用 acquire，然后在相应的 finally 块中调用 release。这是不安全的，因为这意味着一个线程可能会释放一个许可，即使该线程从未成功获得许可。（因此，例如，如果线程 T 持有许可并且线程 U 和 V 都在等待获得许可，然后在线程 U 上调用 Thread.interrupt 将导致线程 U 抛出一个 InterruptedException 并且释放线程T的许可，从而让线程V立即获得许可！）

平均而言，在一名农民使用这座桥的时间内，会出现两名新农民，每个方向各一名。因为（如上所述）你一次只允许一个农民使用这座桥，这意味着你会越来越落后，因为越来越多的农民在等待使用这座桥。

这个问题是你说你的解决方案不是"starvation-free"的意思吗？

但要回答您的具体问题：

[…] I am not sure how to make it starvation-free?

如果您写 new Semaphore(1, true) 而不仅仅是 new Semaphore(1)（即，如果您将信号量的 "fairness parameter" 设置为 true），那么您的信号量将确保农民能够按照他们到达的顺序使用桥梁。这将保证没有 farmer-thread 饿死，因为每个 farmer 都将保证在前一个 farmer 发布后立即获得许可。

。 . .但即使有了这个公平参数，你仍然会遇到问题（如上所述），即农民出现的速度总是比你能通过的速度快。这可能会让您看起来像是遇到了 resource starvation 问题，但实际上问题只是您没有足够的资源来尝试使用它。

要解决此问题，您确实需要解决上面的问题 #1，并允许多个农民同时过桥，只要他们朝同一方向行进即可。我不认为像 java.util.concurrent.Semaphore 这样的计数信号量会削减它；如果您需要确保在任何给定时间最多获得 n 个许可，那么 class 很有用，但在您的情况下，对可获得的许可数量没有限制获得，只要所有持有人都朝着同一方向行驶。

相反，我认为您会想要如下内容：

AtomicInteger 或类似的追踪目前有多少农民获准穿越。

一个线程安全 List 农民等待北行，一个农民等待南行。

Farmer有一个布尔标志，表示是否有权限使用网桥

当农民出现时，如果桥已经在使用，他们会将自己添加到适当的列表中，进入 synchronized/wait 循环，直到他们的标志设置为 true.

农民使用完桥后，他们更新 AtomicInteger，如果现在为零，他们检查是否有任何等待的农民并唤醒他们。

经典问题Single Lane Bridge Problem的无饥饿解决方案

Starvation-free solution of classic problem Single Lane Bridge Problem

java

deadlock

semaphore

java-threads

starvation