java - 经典问题的无饥饿解决方案单车道桥梁问题

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

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




  它仅使用一个线程[…]


我不确定你是什么意思;实际上，它为每个农民启动了一个单独的线程。


  如果农民同时跳到桥的两边，它[...]可能会陷入僵局。


那是不对的。这里唯一的锁定机制是单个信号量，任何获得许可的线程都可以保证在再次尝试获取其之前将其释放，因此deadlock不可能。



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


您的介绍表明它正在尝试对单车道桥进行建模。但实际上并没有做到这一点，至少在我了解“单车道桥梁”的概念时。特别：


您的代码仅允许一个农民在任何给定时间使用桥梁。但是，如果有许多农民都想朝同一个方向过桥，那么“单车道桥”将允许这样做。 （“单车道桥”只能阻止两个农民以相反的方向穿越。）


当您说您的解决方案“仅使用一个线程”时，这是您的意思吗？

如果农民F和G都朝着同一方向前进，并且农民F在农民G之前到达，我认为“单车道桥”永远不会让农民G在农民F之前穿越。但是，您的代码没有提供保证。 （注意：此保证仅适用于朝同一方向的农民。如果朝相反的方向前进，则如果已经有另一个农民与G的方向相同，则让G的农民先行也许是有效的。你来做。）

您的代码在acquire块中调用try，然后在相应的release块中调用finally。这是不安全的，因为这意味着即使线程从未成功获取许可，线程也可能会释放许可。 （因此，例如，如果线程T持有许可，并且线程U和V都在等待获取许可，则在线程U上对Thread.interrupt的调用将导致线程U抛出InterruptedException并释放线程T的许可，从而让线程V立即获得许可！）
平均而言，在一位农民使用桥的时间中，将出现两名新农民，其中一位在各个方向上行驶。由于（如上所述）您一次只允许一个农民使用桥梁，这意味着您将越来越落后，越来越多的农民在等待使用桥梁。


当您说您的解决方案不是“无饥饿”时，这是您的意思吗？





但要回答您的特定问题：


  […]我不确定如何使它免于饥饿？


如果您写的是new Semaphore(1, true)而不是new Semaphore(1)（即，如果将信号量的“公平性参数”设置为true），则信号量将确保农民可以按照到达的顺序使用桥梁。这将确保不会出现农民线程短缺的情况，因为将确保每个农民在前一个农民发布许可证后就立即获得许可。

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

要解决此问题，您确实需要修复上面的问题＃1，并且只要他们沿着相同的方向行驶，就可以允许多个农民同时过桥。我不认为像java.util.concurrent.Semaphore这样的计数信号量会减少它。如果您需要确保在任何给定时间最多获取n个许可证，则该类很有用，但是在您的情况下，只要所有持有人都朝着同一方向行驶，对可以获取的许可证数量没有限制。

相反，我认为您会需要以下内容：


AtomicInteger或类似名称，用于跟踪当前有多少农民被许可穿越。
一位等待北行的农民的threadsafe List，一位等待向南行的农民。
Farmer有一个布尔标志，用于指示它是否具有使用网桥的权限。
当农民出现时，如果桥梁已经在使用中，他们将自己添加到适当的列表中，输入synchronized / wait循环，直到其标志设置为true。
当农民完成使用桥梁时，他们会更新AtomicInteger，如果现在为零，则检查是否有等待的农民并将其唤醒。