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;
}
}
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:
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!)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:
AtomicInteger or similar to track how many farmers currently have permission to cross.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.synchronized/wait loop until their flag is set to true.AtomicInteger, and if it's now zero, they check for any waiting farmers and wake them up.