4.3. Fairly Sharing a Resource
Our dining philosophers implementation was successful in that it synchronizes the actions of multiple processes competing for limited resources and prevents them from entering into a deadlocked state. However, there is one potential problem it doesn't make any attempt to solve—starvation. Starvation occurs when a process can't access an available resource, because other processes are beating it to the mark—either they are faster, or on a better network connection, or have some other competitive advantage. The dining philosophers code makes no guarantee that every philosopher will eventually get a turn to eat, or that philosophers will eat with the same frequency. Your fellow philosophers might repeatedly beat you to any tickets that become available, preventing you from entering the dining room and eating.
We can address starvation by enforcing fair access to shared resources in a number of ways. One simple technique is to force processes to take turns. Let's see how.
4.3.1. Using a Queue to Take Turns
Consider what happens when you want to be waited on, say at a deli. You take a numbered ticket from a dispenser, in effect placing yourself at the end of the current line of waiting customers. To keep things simple, we'll assume that just one customer can be served at a time. There is typically a message board indicating the “service number” of the customer currently being served. You wait patiently until your number is displayed, and then it's your turn for service. When you're done, the service number gets incremented by one.
Under this first-come, first-served scheme, everyone who requests service will eventually get a turn (as long as each service request has an upper time limit). In other words, customers are treated fairly and won't be made to wait for service indefinitely.
Of course, we are just describing a queue, but our reason for introducing the deli theme is that an implementation of a space-based distributed queue is similar to the working of a ticket dispenser. Let's see how this works.
To implement a queue we need a ticket dispenser and a service number. Both can be represented with our shared variable class. Here is how we can create a queue:
SharedVar dispenser = new SharedVar("Ticket Dispenser", 0);
SharedVar serviceNum = new SharedVar("Service Number", 0);
try {
space.write(dispenser, null, Lease.FOREVER);
space.write(serviceNum, null, Lease.FOREVER);
System.out.println("Dispenser ready to dispense ticket " +
dispenser.value);
System.out.println("Ready to service " +
serviceNum.value);
} catch (Exception e) {
e.printStackTrace();
}
Here we simply instantiate two shared variables with the appropriate names and write them into the space. You'll find an installer application that does this in the complete source code.
Once our queue is created, to enter the queue a customer needs to take a number and wait its turn. Here's the code for takeANumber:
private int takeANumber() {
int myNum = 0;
try {
SharedVar template = new SharedVar("Ticket Dispenser");
SharedVar dispenser = (SharedVar)
space.take(template, null, Long.MAX_VALUE);
myNum = dispenser.value.intValue();
dispenser.increment();
space.write(dispenser, null, Lease.FOREVER);
} catch (Exception e) {
e.printStackTrace();
}
return myNum;
}
The takeANumber method first sets up a template to retrieve the “Ticket Dispenser” shared variable. It then takes the shared variable from the space (waiting if necessary), stashes its value in myNum, and calls the dispenser's increment method. We then write the dispenser back into the space and return myNum. This mirrors what happens when you take a number from a mechanical ticket dispenser: you take (and keep) a number from the dispenser and at the same time advance the dispenser's ticket value.
Once a customer has retrieved a number from the dispenser, it has to wait for its turn. Here is the code for waitForTurn:
public SharedVar waitForTurn(int myNum) {
try {
System.out.println("Customer " + myNum +
" waits for turn");
SharedVar template =
new SharedVar("Service Number", myNum);
SharedVar serviceNum = (SharedVar)
space.take(template, null, Long.MAX_VALUE);
return serviceNum;
} catch (Exception e) {
e.printStackTrace();
return null;
}
}
To wait for a turn, we first create a SharedVar template, using its constructor to set the name field to “Service Number” and the value field to myNum. We then perform a take with the template, which will cause the process to wait until the service number reaches the number myNum. In effect, the customer is waiting until all the customers with lower numbers are serviced.
When through with its turn, a customer calls incrementServiceNumber to increment the service number and return the entry to the space so the next customer in line can have its turn. Here's the code that does this:
public void incrementServiceNumber(SharedVar serviceNum) {
serviceNum.increment();
try {
space.write(serviceNum, null, Lease.FOREVER);
System.out.println("Ready to service " +
serviceNum.value);
} catch (Exception e) {
e.printStackTrace();
}
}
That is all there is to implementing a distributed queue. Let's put all this together into a simple test application:
public class Customer {
private JavaSpace space;
public Customer(JavaSpace space) {
this.space = space;
}
public static void main(String[] args) {
JavaSpace space = SpaceAccessor.getSpace();
Customer customer = new Customer(space);
// get a numbered ticket from the dispenser
int myNum = customer.takeANumber();
// wait your turn
SharedVar serviceNum = customer.waitForTurn(myNum);
// take your turn
System.out.println("Customer " + myNum + " takes its turn");
try {
Thread.sleep(1000);
} catch (Exception e) {
e.printStackTrace();
return;
}
// increment the service number
customer.incrementServiceNumber(serviceNum);
}
// ... other method definitions go here
}
Let's step through this code. The main method of the application obtains a handle to a space and then instantiates a Customer object, which takes a number from the ticket dispenser (takeANumber), waits in line for its turn (waitForTurn), and then takes its turn (in this case, all the customer does is sleep for a while to simulate the time it takes to be serviced). In this example, only one customer is served at a time. So, when the customer is done with its turn, it increments the service number (incrementServiceNumber) so that the next customer in line can proceed. You can imagine a different scenario where there are multiple workers servicing multiple customers at once; in that case, the workers would increment the service number every time they finish with a customer.
Now it is time to make a test run of our turn-taking application. Here is sample output of running five customer applications:
Dispenser ready to dispense ticket 0 Ready to service 0 Customer 0 waits for turn Customer 0 takes its turn Customer 1 waits for turn Customer 2 waits for turn Customer 3 waits for turn Customer 4 waits for turn Ready to service 1 Customer 1 takes its turn Ready to service 2 Customer 2 takes its turn Ready to service 3 Customer 3 takes its turn Ready to service 4 Customer 4 takes its turn Ready to service 5
Here all five customers show up, take a ticket and wait for their turn. More customers can come along later and pick up where these left off. The next customer to show up takes number five from the ticket dispenser and can take its turn without waiting, since the service number is already up to five.
4.3.2. Round-Robin Synchronization
In the previous example, there is a potentially unlimited line of customers waiting for service. As soon as a customer has had a turn at the resource or service, it's done; to take another turn, the customer has to start all over again by taking a new ticket from the dispenser.
Round-robin synchronization provides another method of sharing a resource in which a set of processes accesses a resource repeatedly. With round-robin, we arrange processes in a ring and grant the resource to the processes one after another, going around the ring. Once each process has had a turn, the ring is traversed again, giving each process another turn. This circular resource sharing can either continue indefinitely or for a specified number of rounds.
Here is how we can use the round-robin technique to coordinate n participants: Each participant is given a unique numeric identifier between 0 and n-1, and the service number is started at 0. Each process waits for the service number to reach its own identifier, and then takes its turn. When finished with its turn, it increments the service number. In this manner, participant i can't take its turn until the participant i-1 has finished. Once every member of the circle has taken a turn, the “last” process in the ring updates the service number to point to the “first” process by resetting the service number to 0, and another round begins.
Using our code from the last example as a starting point, we first need to rework the SharedVar a bit for use with the round-robin technique. Here we define a RoundRobinSharedVar that extends SharedVar:
public class RoundRobinSharedVar extends SharedVar {
public Integer numParticipants;
public RoundRobinSharedVar() {
}
public RoundRobinSharedVar(String name,
int value)
{
this.name = name;
this.value = new Integer(value);
}
public RoundRobinSharedVar(String name,
int value, int numParticipants)
{
this.name = name;
this.value = new Integer(value);
this.numParticipants = new Integer(numParticipants);
}
public Integer increment() {
int curValue = value.intValue();
int numParts = numParticipants.intValue();
value = new Integer(
curValue == (numParts - 1) ? 0 : (curValue + 1));
return value;
}
}
We've added a new field called numParticipants, which holds the number of participating processes, and also a new constructor that takes an extra integer argument and assigns its value to the numParticipants field. As usual, we supply the required no-arg constructor.
We also override the increment method, which must update the value field to represent the next participant in the circle. It's no longer correct for increment to simply add 1 to the current value, since participants are now arranged in a ring, not a line. If value holds the value of the last process in the ring (the one numbered one less than the number of participants), the method sets value to 0, otherwise it just adds 1 to the current value as before.
Instead of a Customer class, we define a RoundRobinParticipant class, with a few small differences. Here is its main method, which contains the only changes:
public static void main(String[] args) {
JavaSpace space = SpaceAccessor.getSpace();
RoundRobinParticipant participant =
new RoundRobinParticipant(space);
int myNum = Integer.parseInt(args[0]);
int rounds = Integer.parseInt(args[1]);
int numParticipants = Integer.parseInt(args[2]);
if (myNum == 0) {
participant.initSpace(numParticipants);
}
for (int i = 0; i < rounds; i++) {
// wait your turn in this round
RoundRobinSharedVar serviceNum =
participant.waitForTurn(myNum);
// take your turn
System.out.println("Round " + i + ": Process " +
myNum + " takes its turn");
try {
Thread.sleep(1000);
} catch (Exception e) {
e.printStackTrace();
}
// increment the service number
participant.incrementServiceNumber(serviceNum);
}
}
There are a few changes from the previous Customer code. The application now takes three command-line arguments: an identifying number (myNum), a number of rounds (rounds) and the total number of participants (numParticipants). Because we are assigning an identifying number to each process, the participant no longer uses a ticket dispenser to obtain a number. The process now loops rounds times; each time through the loop, the participant waits for its turn, takes its turn, and increments the service number, just as Customer did. If the process is the last participant in the ring (its number is numParticipants - 1), then our new implementation of increment resets the service number to 0, the number of the first participant.
If we start up five processes that will run for two rounds, here is what the output will look like:
Round 0: Process 0 takes its turn Round 0: Process 1 takes its turn Round 0: Process 2 takes its turn Round 0: Process 3 takes its turn Round 0: Process 4 takes its turn Round 1: Process 0 takes its turn Round 1: Process 1 takes its turn Round 1: Process 2 takes its turn Round 1: Process 3 takes its turn Round 1: Process 4 takes its turn