Starvation-free solution of classic problem Single Lane Bridge Problem

Question

I am attempting to provide a solution to the classic Single Lane Bridge Problem, where a single lane bridge connects two villages. It only uses one thread and so can become deadlocked if farmers jump on either side of the bridge at the same time. This is my solution so far, but I am not sure how to make it starvation-free?

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

First, a disclaimer: parts of your question don't really make sense, but I think that might be due more to misuse of terminology than to misunderstandings per se. Unfortunately, the terminology is actually quite important if you want to communicate your question clearly and make sense of what you read. I've done my best below, but it's quite possible that I'm misunderstanding your real question.

---

It only uses one thread […]

I'm not sure what you mean; it actually launches a separate thread for every single farmer.

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

That's not correct; the only locking mechanism here is a single semaphore, and any thread that acquires a permit is guaranteed to release it before trying again to acquire it, so there's no possibility of deadlock.

---

I see three major issues with your code:

1. Your introduction suggests that it's trying to model a single-lane bridge; but it doesn't really do that, at least as I understand the concept of a "single-lane bridge". Specifically:
   • Your code allows only one farmer to use the bridge at any given time; but if there are many farmers who all want to cross the bridge in the same direction, then a "single-lane bridge" would allow that. (A "single-lane bridge" should only prevent two farmers from crossing in opposite directions.)
     • Is this issue what you meant when you said that your solution "only uses one thread"?
   • If farmers F and G are both heading the same direction, and farmer F arrives before farmer G, I think a "single-lane bridge" would never have farmer G cross before farmer F. Your code, however, doesn't provide that guarantee. (N.B. This guarantee only applies to farmers heading the same direction. If the farmers are heading in opposite directions, it might be valid to get farmer G go first if there's already another farmer heading the same direction as farmer G. That's a design decision for you to make.)
2. Your code calls acquire in a try-block, and then calls release in the corresponding finally-block. That's not safe, because it means that a thread may release a permit even if that thread never successfully acquired a permit. (So, for example, if thread T holds the permit and threads U and V are both waiting to acquire the permit, then a call to Thread.interrupt on thread U will cause thread U to throw an InterruptedException and release thread T's permit, thereby letting thread V immediately acquire the permit!)
3. On average, in the amount of time that one farmer is using the bridge, two new farmers will show up, one traveling in each direction. Since (as mentioned above) you only allow one farmer to use the bridge at a time, this means that you'll keep falling further and further behind, with more and more farmers waiting to use the bridge.
   • Is this issue what you meant when you said that your solution is not "starvation-free"?

---

But to answer your specific question:

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

If you write new Semaphore(1, true) instead of just new Semaphore(1) (i.e., if you set the semaphore's "fairness parameter" to true), then your semaphore will ensure that farmers can use the bridge in the order that they arrive. This will guarantee that no farmer-thread will starve, because each farmer will be guaranteed to acquire the permit as soon as the previous farmer has released it.

. . . but even with that fairness parameter in place, you'll still have the problem (mentioned above) that farmers keep showing up faster than you can get through them. This might make it look like you have a resource starvation problem, but really the problem is just that you don't have enough of the resource for how you're trying to use it.

To fix this, you really need to fix issue #1 above, and allow multiple farmers to cross the bridge at the same time as long as they're traveling in the same direction. I don't think a counting semaphore like java.util.concurrent.Semaphore is going to cut it; that class is useful if you need to ensure that at most n permits are acquired at any given time, but in your case there's no restriction on the number of permits that can be acquired, as long as all holders are traveling in the same direction.

Instead, I think you'll want something like the following:

• An AtomicInteger or similar to track how many farmers currently have permission to cross.
• One threadsafe List of farmers waiting to travel northbound, and one of farmers waiting to travel southbound.
• Farmer has a boolean flag to indicate whether it has permission to use the bridge.
• When farmers show up, if the bridge is already in use, they add themselves to the appropriate list, enter a synchronized/wait loop until their flag is set to true.
• When farmers finish using the bridge, they update the AtomicInteger, and if it's now zero, they check for any waiting farmers and wake them up.