Advanced
Synchronization in Java
Resource Allocation
Graphs
The Simple Model
A simple system consists of M agents (threads or processes) simultaneously competing for N resources. In the simplest case N = 1 and M = 2.
Examples of resources include:
data structures, files, memory segments, devices (printers, processors, disks,) servers, communication channels, etc.
Each agent is a separate process or thread. There may be different types of agents.
Examples of agents include:
producers, consumers, readers, writers, shoppers, personal assistants, etc.
Certain operations may be performed on a resource. Each operation may have an exclusion constraints of the form:
Under certain conditions, at most k agents may simultaneously perform this operation on this resource.
For example:
At most one agent may perform any operation of device d.
At most one agent may perform a write operation on this file. During this time no agent may perform a read operation.
At most 1 agent may perform an insert or remove operation on this buffer. If the buffer is full, no agent may perform an insert operation. If the buffer is empty, no agent may perform a remove operation.
To perform operation f on resource r, agent c must:
1. Wait for resource r to become available for operation f
2. Perform f on r
3. Release r
The General Model
In a more general system, there may be pools of different types of resources. Each pool has a fixed number of members, all of the same type.
At any given time, t, some resources have been allocated to some agents, and some agents are blocked waiting for a requested resource to be allocated to it. We can represent this situation using a resource allocation graph:
Note: Arrows from agents to resource types are called request edges. Arrows from resources to agents are called assignment edges.
Deadlock,
Starvation, and Race Conditions
A race condition occurs when two variables attempt to access the same variable at the same time. This was what happened in our first version of the joint bank account simulation.
Deadlock occurs when, for example, agent C1 holds resource r3 and waits for resource r1, agent C2 holds resource r1 and waits for resource r2, and agent C3 holds resource r2 and waits for r3. (More or less the picture above).
Starvation occurs when one agent is indefinitely usurped by higher priority agents.
The Critical
Section Problem
The Critical Section Problem (CSP) is the most basic synchronization problem. N agents compete for resource R. Only one agent at a time can hold the resource. A critical section is any region of code that accesses R. Thus no two agents can be in a critical section at the same time. Any solution to the Critical Section Problem must guarantee:
1. Mutual Exclusion: At any given time at most one thread is in its CS.
2. Progress: If no thread is in its CS, then no thread is waiting to enter its CS.
3. Bounded Waiting: Every thread waiting to enter its CS eventually will.
The critical section problem is easily solved in Java by requiring threads to first hold a resource's lock before accessing the resource:
class SlaveThread extends Thread {
Resource resource;
public void run() {
while(true) {
synchronize(resource) {
resource.access();
}
}
}
}
Alternatively, we can make the resource a monitor:
class Resource {
public synchronized void access() { ...
}
}
Now the thread doesn't need to worry about holding locks:
class SlaveThread extends Thread {
Resource resource;
public void run() {
while(true) {
resource.access();
}
}
}
Primitive
Synchronization Mechanisms
Another solution to the CSP is to have an agent disable CPU interrupts just before entering a critical section, then enable interrupts when it leaves a critical section. This implies the code runs in some sort of supervisor mode rather than ordinary user mode.
Most processors provide indivisible instructions that can perform two operations without being interrupted.
We can mimic these instructions in Java:
class Lock
public class Lock {
private boolean locked;
public Lock(boolean val) { locked =
val; }
public Lock() { this(false); }
public synchronized boolean isLocked()
{ return locked; }
public synchronized void lock() {
locked = true; }
public synchronized void unlock() {
locked = false; }
public synchronized boolean testAndSet()
{
boolean temp = locked;
locked = true;
return temp;
}
public synchronized void swap(Lock
other) {
boolean temp = locked;
locked = other.locked;
other.locked = temp;
}
}
class Resource
class Resource {
public Lock mutex = new Lock();
public void access(SlaveThread who) {
while(mutex.testAndSet()); //
busy-waiting
System.out.println(who.getName() +
" accessing resource");
try {
Thread.sleep(500); // simulate
access time
} catch(InterruptedException ie) {
System.err.println(ie.getMessage());
}
mutex.unlock();
}
}
class SlaveThread
class SlaveThread extends Thread {
Resource resource;
public SlaveThread(Resource r, String
name) {
super(name);
resource = r;
}
public void run() {
for(int i = 0; i < 3; i++) {
System.out.println(
getName() + " attempting
to access resource");
resource.access(this);
System.out.println(
getName() + " entering
remainder section");
}
}
}
class Master
public class Master {
public static void main(String[] args)
{
Resource resource = new Resource();
int slaveCount = 3;
Thread[] slaves = new
Thread[slaveCount];
for(int i = 0; i < slaveCount;
i++) {
slaves[i] = new
SlaveThread(resource, " slave " + i);
}
for(int i = 0; i < slaveCount;
i++) {
slaves[i].start();
}
for(int i = 0; i < slaveCount;
i++) {
try {
slaves[i].join();
} catch(InterruptedException ie)
{
System.err.println(ie.getMessage());
} finally {
System.out.println("slave
"+ i + " has died");
}
}
System.out.println("The master
will now die ... ");
}
}
Program output
slave 0 attempting to
access resource
slave 0 accessing resource
slave 1 attempting to access resource
slave 2 attempting to access resource
slave 0 entering remainder section
slave 0 attempting to access resource
slave 2 accessing resource
slave 2 entering remainder section
slave 2 attempting to access resource
slave 1 accessing resource
slave 1 entering remainder section
slave 1 attempting to access resource
slave 1 accessing resource
slave 1 entering remainder section
slave 1 attempting to access resource
slave 1 accessing resource
slave 1 entering remainder section
slave 0 accessing resource
slave 0 entering remainder section
slave 0 attempting to access resource
slave 0 accessing resource
slave 0 entering remainder section
slave 0 has died
slave 1 has died
slave 2 accessing resource
slave 2 entering remainder section
slave 2 attempting to access resource
slave 2 accessing resource
slave 2 entering remainder section
slave 2 has died
The master will now die ...
Variation 2:
Swapping locks
class Resource {
public Lock mutex = new Lock();
public void access(SlaveThread who) {
who.key.lock();
while(who.key.isLocked())
mutex.swap(who.key);
System.out.println(who.getName() + " accessing resource");
try {
Thread.sleep(500); // simulate access time
} catch(InterruptedException ie) {
System.err.println(ie.getMessage());
}
mutex.unlock();
}
}
class SlaveThread extends Thread {
Resource resource;
Lock key = new Lock(true);
public SlaveThread(Resource r, String
name) {
super(name);
resource = r;
}
public void run() {
for(int i = 0; i < 3; i++) {
System.out.println(
getName() + " attempting
to access resource");
resource.access(this);
System.out.println(
getName() + " entering
remainder section");
}
}
}
Counting Semaphores
Usually mutual exclusion means at most one thread at a time may access some resource. More generally, suppose we want to allow at most N threads at a time to access some resource. The traditional solution is to use a counting semaphore, which generalizes the idea of a lock (sometimes called a binary semaphore).
class Semaphore
public class Semaphore {
// = max # of threads allowed to access
some resource:
private int maxValue;
// = # of threads currently allowed to
access some resource:
private int value;
public Semaphore(int val) { maxValue =
value = val; }
public Semaphore() { this(1); }
public synchronized int getValue() {
return value; }
public synchronized void probe() { // P
while (value <= 0) {
try {
wait();
} catch(InterruptedException ie)
{
System.err.println(ie.getMessage());
}
}
value--; // access granted
}
public synchronized void signal() { //
V
if (maxValue <= value) return;
if (value++ == 0) notifyAll(); //
next?
}
}
class Resource
Here's a resource that allows up to five threads at a time to access it:
class Resource {
private Semaphore mutex = new
Semaphore(5);
private int visitors = 0;
public void access() {
mutex.probe();
System.out.println(
"Room for " +
mutex.getValue() + " more visitor(s)");
try {
Thread.sleep(250); // simulate
access time
} catch(InterruptedException ie) {
System.err.println(ie.getMessage());
}
mutex.signal();
}
}
class SlaveThread
class SlaveThread extends Thread {
private Resource resource;
public SlaveThread(Resource r) {
resource = r; }
public void run() {
for(int i = 0; i < 5; i++) {
resource.access();
}
}
}
class Master
public class Master {
public static void main(String[] args)
{
Resource resource = new Resource();
int slaveCount = 10;
Thread[] slaves = new
Thread[slaveCount];
for(int i = 0; i < slaveCount;
i++) {
slaves[i] = new
SlaveThread(resource);
}
for(int i = 0; i < slaveCount;
i++) {
slaves[i].start();
}
for(int i = 0; i < slaveCount;
i++) {
try {
slaves[i].join();
} catch(InterruptedException ie)
{
System.err.println(ie.getMessage());
} finally {
System.out.println("slave
"+ i + " has died");
}
}
System.out.println("The master
will now die ... ");
}
}
Program output
Room for 4 more visitor(s)
Room for 3 more visitor(s)
Room for 2 more visitor(s)
Room for 1 more visitor(s)
Room for 0 more visitor(s) // repeats 31 more times
Room for 2 more visitor(s)
Room for 2 more visitor(s)
Room for 2 more visitor(s)
Room for 1 more visitor(s)
Room for 0 more visitor(s)
Room for 0 more visitor(s)
Room for 0 more visitor(s)
Room for 0 more visitor(s)
Room for 1 more visitor(s)
Room for 0 more visitor(s)
Room for 2 more visitor(s)
slave 0 has died
Room for 2 more visitor(s)
slave 1 has died
Room for 3 more visitor(s)
Room for 3 more visitor(s)
Room for 3 more visitor(s)
slave 2 has died
slave 3 has died
slave 4 has died
slave 5 has died
slave 6 has died
slave 7 has died
slave 8 has died
slave 9 has died
The master will now die ...
Solution 0.0: The
Bakery Algorithm (old school)
Bakeries solve the problem of which customer to serve next by making each one pick a number upon entering the shop. The clerk repeatedly calls out the next largest number and serves the customer holding that number. When the customer is served, he throws away the number and exits the bakery until the next time he gets the munchies.
Of course the baker has merely pushed the problem of deciding which customer to serve next onto the poor number dispenser. What happens if two customers try to take a number at the same time? We could make customers choose a number to choose a number, but this leads to an infinite regress of number dispensers. Instead, we use a quantum number dispenser that may allow several customers to simultaneously choose the same number. If two people have the same number, the baker breaks the tie by first serving the customer with the smaller Social Security Number.
The Bakery Algorithm solves the CSP without using special instructions.
class BakeryThread
A bakery thread is a reusable base class that sets up the machinery for subclasses to pick a number, wait for threads with lower numbers to pass through their critical sections, and discard their numbers:
class BakeryThread extends Thread {
private static int nextID = 0; // id
generator
private int id; // this thread's id
private int numThreads; // total # of
threads
private static boolean[] choosing; //
busy choosing
private static int[] number; // now
serving ...
public BakeryThread(int n) {
numThreads = n;
id = nextID++;
choosing = new boolean[numThreads];
number = new int[numThreads];
}
// = max entry in nums array
private int max(int[] nums) {
int result = nums[0];
for(int i = 1; i < nums.length;
i++) {
result = (result <
nums[i])?nums[i]:result;
}
return result;
}
// = true if thread j's turn is before
this thread's turn
private boolean waitFor(int j) {
if (number[j] == 0) return false;
if (number[id] < number[j])
return false;
if (number[id] == number[j]) return
(j < id);
return true;
}
// choose a number and wait for my turn
to enter critical section
protected void enterCS() {
choosing[id] = true; // I'm going to
choose a number
number[id] = max(number) + 1; // I'm
choosing a number
choosing[id] = false; // I'm done
choosing a number
for(int j = 0; j < numThreads;
j++) {
while(choosing[j]); // wait for
Tj to finish choosing
while(waitFor(j)); // wait for Tj to finish its CS
}
}
// throw away my number:
protected void exitCS() { number[id] =
0; }
}
class Producer
class Producer extends BakeryThread {
private BankAccount account;
public Producer(BankAccount acct, int
n) {
super(n);
account = acct;
}
public void run() {
for(int i = 0; i < 5; i++) {
enterCS();
account.deposit(10);
exitCS();
}
}
}
class Consumer
class Consumer extends BakeryThread {
private BankAccount account;
public Consumer(BankAccount acct, int
n) {
super(n);
account = acct;
}
public void run() {
for(int i = 0; i < 5; i++) {
enterCS();
account.withdraw(10);
exitCS();
}
}
}
class Bank
public class Bank {
public static void main(String[] args)
{
BankAccount account = new
BankAccount(100);
int slaveCount = 4;
Thread[] slaves = new
Thread[slaveCount];
for(int i = 0; i < slaveCount;
i++) {
if (i % 2 == 0) {
slaves[i] = new
Producer(account, slaveCount);
} else {
slaves[i] = new
Consumer(account, slaveCount);
}
}
for(int i = 0; i < slaveCount;
i++) {
slaves[i].start();
}
for(int i = 0; i < slaveCount;
i++) {
try {
slaves[i].join();
} catch(InterruptedException ie)
{
System.err.println(ie.getMessage());
} finally {
System.out.println("slave
"+ i + " has died");
}
}
System.out.print("Closing
balance = ");
System.out.println("$" +
account.getBalance());
}
}
Program output
after deposit balance = $110.0
after withdrawl balance = $100.0
after deposit balance = $110.0
after withdrawl balance = $100.0
after deposit balance = $110.0
after withdrawl balance = $100.0
after deposit balance = $110.0
after withdrawl balance = $100.0
after deposit balance = $110.0
after withdrawl balance = $100.0
after deposit balance = $110.0
after withdrawl balance = $100.0
after deposit balance = $110.0
after withdrawl balance = $100.0
after deposit balance = $110.0
after withdrawl balance = $100.0
after deposit balance = $110.0
slave 0 has died
after withdrawl balance = $100.0
slave 1 has died
after deposit balance = $110.0
slave 2 has died
after withdrawl balance = $100.0
slave 3 has died
Closing balance = $100.0
The Bounded-Buffer
Problem
In Producer-Consumer problems producer agents create imaginary products called widgets and add them to a shared buffer, while consumer agents remove widgets from the shared buffer. Our bank account example is a producer-consumer problem, the bank account is the shared buffer, and widgets are dollars.
The Bounded-Buffer Problem (BBP) is a variant of the Producer-Consumer problems in which the buffer has a limited capacity. In this case a deadlock can result when the consumer removes a widget from a nearly full buffer at the exact time the producer places a new widget in the buffer, then goes to sleep waiting for the consumer to tell it that there's room in the buffer. Eventually, when the consumer removes the last widget, it goes to sleep waiting for the producer to notify it that there are more widgets to consume.
Returning to our original shared bank account example, let's modify the deposit method so that it imposes a cap of $50
public synchronized void
deposit(double amt) {
while (cap < balance + amt) {
try {
wait(); // wait for funds
} catch (InterruptedException ie)
{
System.err.println(ie.getMessage());
}
}
double temp = balance;
temp = temp + amt;
try {
Thread.sleep(300); // simulate
production time
} catch (InterruptedException ie) {
System.err.println(ie.getMessage());
}
System.out.println("after
deposit balance = $" + temp);
balance = temp;
notify();
}
Assume two producers attempt to deposit $15 five times each for a total of 5 x $15 x 2 = $150. Assume two consumers withdraw $10 five times each for a total of 5 x $10 x 2 = $100. The account initially has a balance of $0. Here's the output produced:
after deposit balance = $15.0
after withdrawl balance = $5.0
after deposit balance = $20.0
after withdrawl balance = $10.0
after deposit balance = $25.0
after withdrawl balance = $15.0
after deposit balance = $30.0
after withdrawl balance = $20.0
after deposit balance = $35.0
after withdrawl balance = $25.0
after deposit balance = $40.0
after withdrawl balance = $30.0
after deposit balance = $45.0
after withdrawl balance = $35.0
after deposit balance = $50.0
after withdrawl balance = $40.0
after withdrawl balance = $30.0
after deposit balance = $45.0
after withdrawl balance = $35.0
after deposit balance = $50.0
slave 0 has died
slave 1 has died
slave 2 has died
slave 3 has died
Closing balance = $50.0
The Readers and
Writers Problem
In some cases a resource can permit different types of agents different access privileges. A writer agent modifies the resource. When this is happening no other agent may access the resource. A reader agent does not modify the resource, so multiple readers may access it simultaneously.
class Document
class Document {
private Object mutex = new
Object();
private int readCount = 0;
private int wordCount = 0;
public void read(Reader who) {
synchronized(mutex) {
readCount++; }
System.out.println(who.getName()
+ " is reading");
System.out.println(
who.getName() + ": readCount
= " + readCount);
try {
Thread.sleep(200); // simulate reading time
} catch(InterruptedException ie) {
System.err.println(ie.getMessage());
}
synchronized(mutex) {
if (--readCount == 0)
mutex.notifyAll();
}
}
public void write(Writer who) {
synchronized(mutex) {
while (readCount > 0) {
try {
mutex.wait();
}
catch(InterruptedException ie) {
System.err.println(ie.getMessage());
}
}
System.out.println(
who.getName() + " is
writing");
System.out.println(
who.getName() + ":
readCount = " + readCount);
System.out.println(
who.getName() + ":
wordCount = " + (wordCount += 5));
try {
Thread.sleep(500); // simulate
access time
} catch(InterruptedException ie) {
System.err.println(ie.getMessage());
}
} // synchronized
}
}
class Reader
class Reader extends Thread {
private Document doc;;
public Reader(Document d, String name)
{
super(name);
doc = d;
}
public void run() {
for(int i = 0; i < 3; i++) {
System.out.println(
getName() + " attempting
to read document");
doc.read(this);
System.out.println(
getName() + " entering
remainder section");
}
}
}
class Writer
class Writer extends Thread {
private Document doc;;
public Writer(Document d, String name)
{
super(name);
doc = d;
}
public void run() {
for(int i = 0; i < 3; i++) {
System.out.println(
getName() + " attempting
to write document");
doc.write(this);
System.out.println(
getName() + " entering
remainder section");
}
}
}
class DocumentManager
public class DocumentManager {
public static void main(String[] args)
{
Document doc = new Document();
int slaveCount = 4;
Thread[] slaves = new
Thread[slaveCount];
for(int i = 0; i < slaveCount;
i++) {
if (i % 2 != 0) {
slaves[i] = new Reader(doc,
" reader " + i);
} else {
slaves[i] = new Writer(doc,
" writer " + i);
}
}
for(int i = 0; i < slaveCount;
i++) {
slaves[i].start();
}
for(int i = 0; i < slaveCount;
i++) {
try {
slaves[i].join();
} catch(InterruptedException ie)
{
System.err.println(ie.getMessage());
} finally {
System.out.println(slaves[i].getName()
+ " has died");
}
}
System.out.println("The master
will now die ... ");
}
}
Program Output
writer 0 attempting to write
document
writer 0 is writing
writer 0: readCount = 0
writer 0: wordCount = 5
reader 1 attempting to read document
writer 2 attempting to write
document
reader 3 attempting to read document
reader 1 is reading
reader 1: readCount = 1
reader 3 is reading
reader 3: readCount = 2
writer 0 entering remainder section
writer 0 attempting to write
document
reader 1 entering remainder section
reader 1 attempting to read document
reader 1 is reading
reader 1: readCount = 2
reader 3 entering remainder section
reader 3 attempting to read document
reader 3 is reading
reader 3: readCount = 2
reader 3 entering remainder section
reader 3 attempting to read document
reader 3 is reading
reader 3: readCount = 2
reader 1 entering remainder section
reader 1 attempting to read document
reader 1 is reading
reader 1: readCount = 2
reader 3 entering remainder section
writer 2 is writing
writer 2: readCount = 0
writer 2: wordCount = 10
reader 1 entering remainder section
writer 2 entering remainder section
writer 2 attempting to write
document
writer 0 is writing
writer 0: readCount = 0
writer 0: wordCount = 15
writer 2 is writing
writer 2: readCount = 0
writer 2: wordCount = 20
writer 0 entering remainder section
writer 0 attempting to write
document
writer 2 entering remainder section
writer 2 attempting to write
document
writer 0 is writing
writer 0: readCount = 0
writer 0: wordCount = 25
writer 2 is writing
writer 2: readCount = 0
writer 0 entering remainder section
writer 0 has died
reader 1 has died
writer 2: wordCount = 30
writer 2 entering remainder section
writer 2 has died
reader 3 has died
The master will now die ...
The Dining
Philosophers Problem
Dining philosophers is typical in the class of problems where M agents perpetually compete for size K subsets of a set of N resources.
You know the story: five philosophers are sitting at a round table in a Chinese restaurant. Each has a bowl of rice in front of him, a chopstick he must share with his left neighbor, and a chopstick he must share with his right neighbor. At random speeds each philosopher repeatedly:
1. thinks
2. waits for his chopsticks to become available
3. picks up the chopsticks on either side
4. eats
5. sets down the chopsticks
The problem is step 2. The philosopher can only grab a chopstick if the neighbor he shares it with isn't eating, and he needs both chopsticks.
In code we can think of a philosopher as a thread:
public class Philosopher extends Thread {
public static final int THINKING = 0,
EATING = 1, HUNGRY = 2;
private Object leftChopstick,
rightChopstick;
private Philosopher leftNeighbor,
rightNeighbor;
private int state = 0;
public void run() {
while(true) {
// think
// wait for chopsticks
// grab chopsticks
// eat
// release chopsticks
}
}
}
Why not simply have each philosopher grab the chopstick on his left when it's ready, then grab the chopstick on his right when it's ready? Two potential problems arise. First, what if each philosopher grabs the chopstick on his left at the same time? In this case each philosopher ends up permanently waiting for his right chopstick-- deadlock. Another possibility is that a pattern develops in which philosopher 3 starves because whenever his left chopstick is available, the right is unavailable and vice versa.
Here's a Java solution based on one from the book. Each philosopher encapsulates a reference to his environment, the restaurant, which maintains information about chopstick availability, and who's thinking, hungry, or eating:
class Philosopher extends Thread {
private Restaurant environment; // the
restaurant
private int id; // = position at table
(0 - 4)
public int numBites = 0; // amount of
food consumed
public Philosopher(int i, Restaurant
rt) {
super("philosopher " + i);
this.rt = rt;
id = i;
}
The run method executes the think-hungry-eat cycle ten times:
public void run() {
for(int i = 0; i < 10; i++) {
try {
System.out.println(getName() +
" is thinking");
Thread.sleep(200); // simulate
thinking time
} catch (InterruptedException ie)
{
System.err.println(ie.getMessage());
}
System.out.println(getName() +
" is hungry");
environment.pickup(id); //
acquire chopsticks
try {
System.out.println(getName() +
" is eating");
Thread.sleep(100); // simulate
eating time
numBites++; // take a bite
} catch (InterruptedException ie)
{
System.err.println(ie.getMessage());
}
environment.putdown(id); //
release chopsticks
}
}
The main() method creates
the restaurant and philosophers, starts the philosophers, waits for them to
finish dinner, then prints out the amount of food each one ate:
public static void main(String[] args) {
Restaurant env = new Restaurant();
Philosopher[] philosophers = new
Philosopher[5];
for(int i = 0; i < 5; i++) { //
create philosophers
philosophers[i] = new
Philosopher(i, env);
}
for(int i = 0; i < 5; i++) { //
start philosophers
philosophers[i].start();
}
// wait for philosophers to finish:
for(int i = 0; i < 5; i++) {
try {
philosophers[i].join();
} catch(InterruptedException ie)
{
System.err.println(ie.getMessage());
} finally {
System.out.println(
philosophers[i].getName() +
" has finished dinner");
}
}
for(int i = 0; i < 5; i++) { //
print statistics
System.out.println(
philosophers[i].getName() +
" had " +
philosophers[i].numBites +
" of food");
}
System.out.println("The
restaurant is now closed ... ");
} // main
} // Philosopher
The restaurant maintains an array of 5 semaphores;
Object[] sticksAvailable = new Object[5];
The philosopher with id = i will wait on the sticksAvailable[i] semaphore for his chopsticks to become available.
In addition, the restaurant keeps track of the state of each philosopher:
class Restaurant {
static final int THINKING = 0, EATING =
1, HUNGRY = 2;
private int[] state = new int[5];
private Object[] sticksAvailable = new
Object[5];
public Restaurant () {
for(int i = 0; i < 5; i++) {
state[i] = THINKING;
sticksAvailable[i] = new
Object();
}
}
When he gets hungry, philosopher #i calls pickup(i) to await and pickup his chopsticks:
void pickup(int i) {
state[i] = HUNGRY;
test(i);
if (state[i] != EATING) {
synchronized (sticksAvailable[i])
{
try {
sticksAvailable[i].wait();
} catch (InterruptedException
ie) {
System.err.println(ie.getMessage());
}
}
}
}
The test function is multi-purpose. When philosopher #i is hungry, he calls test(i). If neither neighbor is eating, then he picks up the chopsticks and eats. If philosopher #i is done eating, he calls test(j) and test(k) where j and k are the numbers of his left and right neighbors. If either is hungry, it notifies them that their chopsticks are ready:
void test(int i) {
if ((state[(i + 4) % 5] != EATING)
&&
(state[i] == HUNGRY) &&
(state[(i + 1) % 5] != EATING)) {
state[i] = EATING;
synchronized
(sticksAvailable[i]) {
sticksAvailable[i].notifyAll();
}
}
}
When he's done eating, philosopher #i calls putdown(i) to release his chopsticks:
void putdown(int i) {
state[i] = THINKING;
test((i + 4) % 5);
test((i + 1) % 5);
}
} // Restaurant
Here's a sample of the output produced:
philosopher 0 is hungry
philosopher 0 will pickup his chopsticks
philosopher 0 is eating
philosopher 2 is hungry
philosopher 3 is thinking
philosopher 2 will pickup his chopsticks
philosopher 2 is eating
philosopher 4 is hungry
philosopher 4 will pickup his chopsticks
philosopher 0 is thinking
philosopher 4 is eating
philosopher 1 is hungry
philosopher 1 will pickup his chopsticks
philosopher 2 is thinking
philosopher 1 is eating
philosopher 4 is thinking
philosopher 3 is hungry
philosopher 3 will pickup his chopsticks
philosopher 3 is eating
philosopher 1 is thinking
philosopher 0 is hungry
philosopher 0 will pickup his chopsticks
philosopher 0 is eating
philosopher 2 is hungry
philosopher 2 will pickup his chopsticks
philosopher 2 is eating
philosopher 3 is thinking
philosopher 4 is hungry
philosopher 4 will pickup his chopsticks
philosopher 4 is eating
philosopher 0 is thinking
philosopher 1 is hungry
philosopher 1 will pickup his chopsticks
philosopher 2 is thinking
philosopher 1 is eating
philosopher 4 is thinking
philosopher 3 is hungry
philosopher 3 will pickup his chopsticks
philosopher 3 is eating
philosopher 1 is thinking
philosopher 0 is hungry
philosopher 0 will pickup his chopsticks
philosopher 0 is eating
philosopher 2 is hungry
philosopher 2 will pickup his chopsticks
philosopher 3 is thinking
philosopher 2 is eating
philosopher 4 is hungry
philosopher 4 will pickup his chopsticks
philosopher 0 has finished dinner
philosopher 4 is eating
philosopher 1 is hungry
philosopher 1 will pickup his chopsticks
philosopher 1 is eating
philosopher 3 is hungry
philosopher 1 has finished dinner
philosopher 2 has finished dinner
philosopher 3 will pickup his chopsticks
philosopher 3 is eating
philosopher 3 has finished dinner
philosopher 4 has finished dinner
philosopher 0 had 10 of food
philosopher 1 had 10 of food
philosopher 2 had 10 of food
philosopher 3 had 10 of food
philosopher 4 had 10 of food
The restaurant is now closed