0

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

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;
  }
}
4

1 回答 1

3

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

它只使用一个线程 […]

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

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

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

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

  1. 您的介绍表明它正在尝试为单车道桥梁建模；但它并没有真正做到这一点，至少我理解“单车道桥”的概念。具体来说：
    • 您的代码在任何给定时间只允许一个农民使用这座桥；但是，如果有很多农民都想从同一个方向过桥，那么“单车道桥”就可以了。（“单车道桥”应该只防止两个农民从相反的方向穿过。）
      • 当您说您的解决方案“仅使用一个线程”时，这个问题是您的意思吗？
    • 如果农民F和G都朝着同一个方向前进，并且农民F在农民G之前到达，我认为“单车道桥”永远不会让农民G在农民F之前通过。但是，您的代码不提供该保证。（注：此保证仅适用于朝同一个方向的农民。如果农民朝相反的方向前进，如果已经有另一个农民与农民G朝同一方向前进，那么让农民G先走可能是有效的。这是一个设计决策你来做。）
  2. 您的代码acquire在try-block 中调用，然后release在相应的finally-block 中调用。这是不安全的，因为这意味着即使该线程从未成功获得许可，线程也可能释放许可。（因此，例如，如果线程T持有许可并且线程U和V都在等待获取许可，那么Thread.interrupt对线程U的调用将导致线程U抛出一个InterruptedException并释放线程T的许可，从而让线程V立即获得许可证！）
  3. 平均而言，在一个农民使用这座桥的时间里，会出现两个新的农民，每个方向都有一个。由于（如上所述）您一次只允许一个农民使用这座桥，这意味着您将越来越落后，越来越多的农民在等待使用这座桥。
    • 当您说您的解决方案不是“无饥饿”时，这个问题是您的意思吗？

但要回答您的具体问题：

[...] 我不知道如何让它没有饥饿？

如果您编写new Semaphore(1, true)而不是仅仅编写new Semaphore(1)（即，如果您将信号量的“公平参数”设置为true），那么您的信号量将确保农民可以按照到达的顺序使用网桥。这将保证没有农民线程会饿死，因为每个农民都会保证在前一个农民释放许可证后立即获得许可证。

. . . 但即使有了这个公平参数，你仍然会遇到（上面提到的）农民不断出现的问题，而你无法通过它们。这可能会使您看起来像资源匮乏问题，但实际上问题只是您没有足够的资源来尝试使用它。

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

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

  • 一个AtomicInteger或类似的跟踪有多少农民目前有权穿越。
  • 一名List等待向北行驶的农民和一名等待向南行驶的农民。
  • Farmer有一个布尔标志来指示它是否有权使用网桥。
  • 当农民出现时，如果桥已经在使用中，他们会将自己添加到适当的列表中，进入synchronized/wait循环，直到他们的标志设置为true。
  • 当农民使用完桥后，他们会更新AtomicInteger，如果它现在为零，他们会检查是否有任何等待的农民并唤醒他们。
于 2019-12-20T01:04:50.193 回答