## Thursday, July 17, 2014

### Dining Philosophers Problem [Code] : [Java Concurrency]

The dining philosophers problem, invented by Edsger Dijkstra, is the classic demonstration of deadlock. The basic description specifies five philosophers (but the example shown here will allow any number). These philosophers spend part of their time thinking and part of their time eating. While they are thinking, they don’t need any shared resources, but they eat using a limited number of utensils. In the original problem description, the utensils are forks, and two forks are required to get spaghetti from a bowl in the middle of the table, but it seems to make more sense to say that the utensils are chopsticks. Clearly, each philosopher will require two chopsticks in order to eat.
A difficulty is introduced into the problem: As philosophers, they have very little money, so they can only afford five chopsticks (more generally, the same number of chopsticks as philosophers). These are spaced around the table between them. When a philosopher wants to eat, that philosopher must pick up the chopstick to the left and the one to the right. If the philosopher on either side is using a desired chopstick, our philosopher must wait until the necessary chopsticks become available.

The code below has a possibility of deadlock. If every philosopher picks the chopstick to the right of him the last philosopher won't be able to pick his right chopstick, thus no one is able to pick his left and eat food, waiting on each other in a chain to get the second chopstick.

Code below taken from Thinking In Java 4th Edition p1224 onwards]

```import java.util.concurrent.*;
import java.util.*;

class Chopstick {

private boolean taken = false;

public synchronized
void take() throws InterruptedException {
while (taken) {
wait();
}
taken = true;
}

public synchronized void drop() {
taken = false;
notifyAll();
}
}

class Philosopher implements Runnable {

private Chopstick left;
private Chopstick right;
private final int id;
private final int ponderFactor;
private Random rand = new Random(47);

private void pause() throws InterruptedException {
if (ponderFactor == 0) {
return;
}
TimeUnit.MILLISECONDS.sleep(
rand.nextInt(ponderFactor * 250));
}

public Philosopher(Chopstick left, Chopstick right,
int ident, int ponder) {
this.left = left;
this.right = right;
id = ident;
ponderFactor = ponder;
}

public void run() {
try {
System.out.println(this + " " + "thinking");
pause();
// Philosopher becomes hungry
System.out.println(this + " " + "grabbing right");
right.take();
System.out.println(this + " " + "grabbing left");
left.take();
System.out.println(this + " " + "eating");
pause();
right.drop();
left.drop();
}
} catch (InterruptedException e) {
System.out.println(this + " " + "exiting via interrupt");
}
}

public String toString() {
return "Philosopher " + id;
}
}

public static void main(String[] args) throws Exception {
int ponder = 5;
if (args.length > 0) {
ponder = Integer.parseInt(args[0]);
}
int size = 5;
if (args.length > 1) {
size = Integer.parseInt(args[1]);
}
Chopstick[] sticks = new Chopstick[size];
for (int i = 0; i < size; i++) {
sticks[i] = new Chopstick();
}
for (int i = 0; i < size; i++) {
exec.execute(new Philosopher(
sticks[i], sticks[(i + 1) % size], i, ponder));
}
if (args.length == 3 && args[2].equals("timeout")) {
TimeUnit.SECONDS.sleep(5);
} else {
System.out.println("Press 'Enter' to quit");
}
exec.shutdownNow();
}
}```

Code:

```import java.util.concurrent.*;
import java.util.*;

class Chopstick {

private boolean taken = false;

public synchronized
void take() throws InterruptedException {
while (taken) {
wait();
}
taken = true;
}

public synchronized void drop() {
taken = false;
notifyAll();
}
}

class Philosopher implements Runnable {

private Chopstick left;
private Chopstick right;
private final int id;
private final int ponderFactor;
private Random rand = new Random(47);

private void pause() throws InterruptedException {
if (ponderFactor == 0) {
return;
}
TimeUnit.MILLISECONDS.sleep(
rand.nextInt(ponderFactor * 250));
}

public Philosopher(Chopstick left, Chopstick right,
int ident, int ponder) {
this.left = left;
this.right = right;
id = ident;
ponderFactor = ponder;
}

public void run() {
try {
System.out.println(this + " " + "thinking");
pause();
// Philosopher becomes hungry
System.out.println(this + " " + "grabbing right");
right.take();
System.out.println(this + " " + "grabbing left");
left.take();
System.out.println(this + " " + "eating");
pause();
right.drop();
left.drop();
}
} catch (InterruptedException e) {
System.out.println(this + " " + "exiting via interrupt");
}
}

public String toString() {
return "Philosopher " + id;
}
}

public class FixedDiningPhilosophers {

public static void main(String[] args) throws Exception {
int ponder = 5;
if (args.length > 0) {
ponder = Integer.parseInt(args[0]);
}
int size = 5;
if (args.length > 1) {
size = Integer.parseInt(args[1]);
}
Chopstick[] sticks = new Chopstick[size];
for (int i = 0; i < size; i++) {
sticks[i] = new Chopstick();
}
for (int i = 0; i < size; i++) {
if (i < (size - 1)) {
exec.execute(new Philosopher(
sticks[i], sticks[i + 1], i, ponder));
} else {
exec.execute(new Philosopher(
sticks[0], sticks[i], i, ponder));
}
}
if (args.length == 3 && args[2].equals("timeout")) {
TimeUnit.SECONDS.sleep(5);
} else {
System.out.println("Press 'Enter' to quit");
}
exec.shutdownNow();
}
}```

Exercise: Change DeadlockingDiningPhilosophers.java so that when a philosopher is done with its chopsticks, it drops them into a bin. When a philosopher wants to eat, it takes the next two available chopsticks from the bin. Does this eliminate the possibility of deadlock? Can you reintroduce deadlock by simply reducing the number of available chopsticks?
My solution:

```import java.util.concurrent.*;
import java.util.*;
import static net.mindview.util.Print.*;

class Chopstick {

private boolean taken = false;

public synchronized void take() throws InterruptedException {
while (taken) {
wait();
}
taken = true;
}

public synchronized void drop() {
taken = false;
notifyAll();
}
}

class Bin {

public void put(Chopstick stick) throws InterruptedException {
bin.put(stick);
}

public Chopstick get() throws InterruptedException {
return bin.take();
}
}

class Philosopher implements Runnable {

private Chopstick left;
private Chopstick right;
private final int id;
private final int ponderFactor;
private Random rand = new Random(47);

private void pause() throws InterruptedException {
if (ponderFactor == 0) {
return;
}
TimeUnit.MILLISECONDS.sleep(rand.nextInt(ponderFactor * 250));
}

public Philosopher(Chopstick left, Chopstick right,
LinkedBlockingQueue bin, int ident, int ponder) {
this.left = left;
this.right = right;
this.bin = bin;
id = ident;
ponderFactor = ponder;
}

public void run() {
try {
print(this + " " + "thinking");
pause();
// Philosopher becomes hungry
print(this + " taking first, right chopstick");
right = bin.take();
print(this + " taking second, left chopstick");
left = bin.take();
print(this + " eating");
pause();
print(this + " returning chopsticks");
bin.put(right);
bin.put(left);
}
} catch (InterruptedException e) {
print(this + " " + "exiting via interrupt");
}
}

public String toString() {
return "Philosopher " + id;
}
}

public static void main(String[] args) throws Exception {
int ponder = 0;
if (args.length > 0) {
ponder = Integer.parseInt(args[0]);
}
int size = 5;
if (args.length > 1) {
size = Integer.parseInt(args[1]);
}
// chopstick bin:
Chopstick[] sticks = new Chopstick[size];
for (int i = 0; i < size; i++) {
sticks[i] = new Chopstick();
bin.put(sticks[i]);
}
for (int i = 0; i < size; i++) {
exec.execute(new Philosopher(sticks[i], sticks[(i + 1) % size], bin, i, ponder));
}
if (args.length == 3 && args[2].equals("timeout")) {
TimeUnit.SECONDS.sleep(5);
} else {
System.out.println("Press 'Enter' to quit");
}
exec.shutdownNow();
}
}```

Does this eliminate the possibility of deadlock? No. Consider the case when each philosopher takes a single chopstick from the bin so that now the bin contains 0 chopsticks. Nobody has the second chopstick to eat the spaghetti.