4.2. Using Multiple Semaphores
In many distributed systems, synchronization needs to go far beyond what can be handled by a single semaphore. Often, many different kinds of resources come into play, and the system must control access to each kind, whether through semaphores or other techniques. But even when semaphores are in place to coordinate access to all resources, that isn't always enough by itself to prevent synchronization problems.
Consider the following example:
public aThenB() {
//... obtain resource A
//... obtain resource B
//... compute
}
public bThenA() {
//... obtain resource B
//... obtain resource A
//... compute
}
Suppose Process 1 executes the aThenB method, while Process 2 executes bThenA. The following interleaved execution might commonly occur:
Process 1 obtains resource A. Process 2 obtains resource B. Process 1 waits for resource B. Process 2 waits for resource A.
In this scenario each processes is blocked and waiting for the other to release a resource. Neither can proceed—the processes are deadlocked. A deadlock occurs when each process in a collection is waiting for an action or response that only another process in the same collection can generate.
There are no general-purpose techniques for preventing deadlock, other than careful algorithm design. However, these types of problems can often be addressed by using additional semaphores to coordinate access to multiple resources. Let's look at an example of how this can be accomplished.
4.2.1. The Dining Philosophers
Our example comes out of a classical coordination problem from computer science known as the dining philosophers problem. The dining philosophers problem is often used to measure the expressivity of a particular coordination language or tool. Here is the story of the dining philosophers from computer science folklore:
According to the story, five philosophers sit around a table as shown in Figure 4.1. Each has a chopstick to his left. An everlasting bowl of rice is placed in the middle of the table. A philosopher spends most of his time thinking, but whenever he is hungry he picks up the chopstick to his left and the chopstick to his right. When attempting to pick up either chopstick, if he finds it already in use he simply waits until it becomes available again. When he has finished eating he puts down both chopsticks and continues to think.
Figure 4.1. The dining philosophers.
We can easily simulate this scenario by creating one semaphore per chopstick, but there is a serious flaw in the system: suppose all five philosophers enter the room and pick up their left chopsticks at once; this leaves no right chopsticks available, and no one is able to eat. They are deadlocked.
We can solve this problem by allowing only four philosophers to enter the room at a time—ensuring that at least one will have access to both his left and right chopsticks and be able to eat. We can control access to the room using four ticket resources represented by a semaphore: a philosopher can enter the room only after obtaining a ticket first.
Here is a space-based implementation of a dining philosopher:
public class Philosopher {
private JavaSpace space;
private int id;
private int num;
private DistributedSemaphore ticket;
private DistributedSemaphore left;
private DistributedSemaphore right;
public static void main(String[] args) {
JavaSpace space = SpaceAccessor.getSpace();
int id = Integer.parseInt(args[0]);
int num = Integer.parseInt(args[1]);
Philosopher philosopher = new Philosopher(space, id, num);
philosopher.work();
}
public Philosopher(JavaSpace space, int id, int num) {
this.space = space;
this.id = id;
this.num = num;
if (id == 0) {
initSpace();
}
ticket = new DistributedSemaphore(space, "ticket");
left = new DistributedSemaphore(space,
"chopstick" + id);
right = new DistributedSemaphore(space,
"chopstick" + ((id + 1) % num));
}
public void work() {
for (;;) {
try {
think();
ticket.down();
left.down();
right.down();
eat();
right.up();
left.up();
ticket.up();
} catch (Exception e) {
e.printStackTrace();
}
}
}
private void initSpace() {
DistributedSemaphore ticket =
new DistributedSemaphore(space, "ticket");
ticket.create(num - 1);
for (int i = 0; i < num; i++) {
DistributedSemaphore chopstick =
new DistributedSemaphore(space, "chopstick" + i);
chopstick.create(1);
}
}
private void think() {
System.out.println("Philosopher " + id + " thinking.");
try {
Thread.sleep(500);
} catch (Exception e) {
e.printStackTrace();
}
}
private void eat() {
System.out.println("Philosopher " + id + " eating.");
try {
Thread.sleep(500);
} catch (Exception e) {
e.printStackTrace();
}
}
}
Let's look carefully at what this code does. The main method expects two command line arguments: An integer identifier that is used to identify a particular philosopher (philosophers are labelled 0 through num-1) and an integer that represents the total number of philosophers. After gaining access to a space, the main method assigns these command line arguments to id and num, respectively. The method then instantiates a Philosopher object, passing it the space, identifier and total number of philosophers, and calls its work method.
Let's now take a look at the constructor for the Philosopher class. The constructor first assigns each of its parameters to local fields. The philosopher with identifier 0 then has the special task of initializing the space by calling initSpace, which writes num-1 ticket entries into the space and then num chopstick entries (identified as “chopstick0”, “chopstick1,” and so on).
Next, every philosopher creates a DistributedSemaphore object for the ticket, and its left and right chopsticks. The left chopstick is given the philosopher's own identifier, and the right chopstick is given an identifier one greater than the philosopher's (modulo the number of chopsticks).
Now let's look at the work method, which allows the philosopher to do what all dining philosophers do: repeatedly think and eat. First the philosopher thinks for a while, and then he tries to down the ticket semaphore, waiting until one is found. Once he has obtained a ticket to the dining room, he picks up the chopstick to his left (by calling down on that chopstick's semaphore), and then picks up the chopstick to his right (also by calling down on that chopstick's semaphore). Note that the method names here are a little confusing: To pick “up” a chopstick we “down” the chopstick's semaphore. But if you think about the semantics of the semaphore operations that we discussed in Section 4.1, it makes sense.
Once the philosopher has both chopsticks in hand, he eats for a while. When he's done eating, he puts down the right chopstick, then the left chopstick, and then gives back his ticket so another hungry philosopher can have a chance to eat. The eat and think methods just print an appropriate message and sleep for half a second.
To run five dining philosophers you need to execute five commands like the following (note that these should be run simultaneously, not one after the other):
java jsbook.chapter4.dining.Philosopher 0 5 java jsbook.chapter4.dining.Philosopher 1 5 java jsbook.chapter4.dining.Philosopher 2 5 java jsbook.chapter4.dining.Philosopher 3 5 java jsbook.chapter4.dining.Philosopher 4 5
Note that the id parameter's value ranges from 0 through 4, to identify each philosopher. When we start up the five philosophers, their interleaved output looks something like this:
Philosopher 2 thinking. Philosopher 4 thinking. Philosopher 3 thinking. Philosopher 1 thinking. Philosopher 0 thinking. Philosopher 4 eating. Philosopher 3 eating. Philosopher 4 thinking. Philosopher 2 eating. Philosopher 3 thinking. Philosopher 1 eating. Philosopher 2 thinking. Philosopher 0 eating. Philosopher 1 thinking. Philosopher 4 eating. Philosopher 0 thinking. Philosopher 3 eating. Philosopher 4 thinking. . . .
Of course, the dining philosophers problem is abstract, but it illustrates important concepts that carry over any time you're building a distributed application with complex synchronization needs. In the dining philosophers example, we've seen how multiple processes can coordinate access to various limited resources: each of the chopsticks is a distinct resource that two processes must share. In order to avoid a situation where all processes are deadlocked, we introduced an additional ticket semaphore that limits access to the room.