This page provides an answers for chapter 1 (Introduction) of the book "The Art of Multiprocessor Programming".
The dining philosophers problem was invented by E. W. Dijkstra, a concurrency pioneer, to clarify the notions of deadlock and starvation freedom. Imagine five philosophers who spend their lives just thinking and feasting. They sit around a circular table with five chairs. The table has a big plate of rice. However, there are only five chopsticks (in the original formulation forks) available, as shown in Fig. 1.5. Each philosopher thinks. When he gets hungry, he sits down and picks up the two chopsticks that are closest to him. If a philosopher can pick up both chopsticks, he can eat for a while. After a philosopher finishes eating, he puts down the chopsticks and again starts to think.
1. Write a program to simulate the behavior of the philosophers, where each philosopher is a thread and the chopsticks are shared objects. Notice that you must prevent a situation where two philosophers hold the same chopstick at the same time.
2. Amend your program so that it never reaches a state where philosophers are deadlocked, that is, it is never the case that each philosopher holds one chopstick and is stuck waiting for another to get the second chopstick.
3. Amend your program so that no philosopher ever starves.
4. Write a program to provide a starvation-free solution for any number of philosophers n.
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
class Main extends Thread {
static int num_philosophers = 5;
static List chopsticks = new ArrayList<>();
static int eat_time_millis = 500;
int philosopher_id;
public Main(int philosopher_id) {
this.philosopher_id = philosopher_id;
}
public static void main(String[] args) {
if(num_philosophers < 5) {
System.out.println("num_philosophers must be at least 5!");
return;
}
List philosophers = new ArrayList<>();
for(int i = 0; i < num_philosophers; i++)
philosophers.add(new Main(i));
for(int i = 0; i < num_philosophers; i++)
chopsticks.add(new ReentrantLock(false));
for(Thread philosopher: philosophers)
philosopher.start();
for(Thread philosopher: philosophers) {
try {
philosopher.join();
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}
public void run() {
for(;;) {
System.out.println("Philosopher " + philosopher_id + " is thinking.");
try {
Thread.sleep(200);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
return;
}
Lock leftChopstick = chopsticks.get(philosopher_id);
Lock rightChopstick = chopsticks.get((philosopher_id + 1) % num_philosophers);
leftChopstick.lock();
try {
rightChopstick.lock();
try {
System.out.println("Philosopher " + philosopher_id + " is eating.");
} finally {
rightChopstick.unlock();
}
} finally {
System.out.println("Philosopher " + philosopher_id + " finished eating.");
leftChopstick.unlock();
}
}
}
}
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
class Main extends Thread {
static int num_philosophers = 5;
static List chopsticks = new ArrayList<>();
static int eat_time_millis = 500;
int philosopher_id;
public Main(int philosopher_id) {
this.philosopher_id = philosopher_id;
}
public static void main(String[] args) {
if(num_philosophers < 5) {
System.out.println("num_philosophers must be at least 5!");
return;
}
List philosophers = new ArrayList<>();
for(int i = 0; i < num_philosophers; i++)
philosophers.add(new Main(i));
for(int i = 0; i < num_philosophers; i++)
chopsticks.add(new ReentrantLock(false));
for(Thread philosopher: philosophers)
philosopher.start();
for(Thread philosopher: philosophers) {
try {
philosopher.join();
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}
public void run() {
for(;;) {
System.out.println("Philosopher " + philosopher_id + " is thinking.");
try {
Thread.sleep(200);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
return;
}
// each philospher gets lowest index lock first
int first_chopstick_index = Math.min(philosopher_id, (philosopher_id + 1) % num_philosophers);
int second_chopstick_index = Math.max(philosopher_id, (philosopher_id + 1) % num_philosophers);
Lock firstChopstick = chopsticks.get(first_chopstick_index);
Lock secondChopstick = chopsticks.get(second_chopstick_index);
firstChopstick.lock();
try {
secondChopstick.lock();
try {
System.out.println("Philosopher " + philosopher_id + " is eating.");
} finally {
secondChopstick.unlock();
}
} finally {
System.out.println("Philosopher " + philosopher_id + " finished eating.");
firstChopstick.unlock();
}
}
}
}
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
class Main extends Thread {
static int num_philosophers = 5;
static List chopsticks = new ArrayList<>();
static int eat_time_millis = 500;
int philosopher_id;
public Main(int philosopher_id) {
this.philosopher_id = philosopher_id;
}
public static void main(String[] args) {
if(num_philosophers < 5) {
System.out.println("num_philosophers must be at least 5!");
return;
}
List philosophers = new ArrayList<>();
for(int i = 0; i < num_philosophers; i++)
philosophers.add(new Main(i));
for(int i = 0; i < num_philosophers; i++)
chopsticks.add(new ReentrantLock(false));
for(Thread philosopher: philosophers)
philosopher.start();
for(Thread philosopher: philosophers) {
try {
philosopher.join();
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}
public void run() {
for(;;) {
System.out.println("Philosopher " + philosopher_id + " is thinking.");
try {
Thread.sleep(200);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
return;
}
// each philospher gets lowest index lock first
int first_chopstick_index = Math.min(philosopher_id, (philosopher_id + 1) % num_philosophers);
int second_chopstick_index = Math.max(philosopher_id, (philosopher_id + 1) % num_philosophers);
Lock firstChopstick = chopsticks.get(first_chopstick_index);
Lock secondChopstick = chopsticks.get(second_chopstick_index);
firstChopstick.lock();
try {
secondChopstick.lock();
try {
System.out.println("Philosopher " + philosopher_id + " is eating.");
} finally {
secondChopstick.unlock();
}
} finally {
System.out.println("Philosopher " + philosopher_id + " finished eating.");
firstChopstick.unlock();
}
}
}
}
The previous code already works for n philosophers.
For each of the following, state whether it is a safety or liveness property.
Identify the bad or good thing of interest.
1. Patrons are served in the order they arrive.
2. What goes up must come down.
3. If two or more processes are waiting to enter their critical sections, at least one succeeds.
4. If an interrupt occurs, then a message is printed within one second.
5. If an interrupt occurs, then a message is printed.
6. The cost of living never decreases.
7. Two things are certain: death and taxes.
8. You can always tell a Harvard man.
In the producer-consumer fable, we assumed that Bob can see whether the can on Alice's windowsill is up or down. Design a producer-consumer protocol using cans and strings that works even if Bob cannot see the state of Alice's can (this is how real-world interrupt bits work).
Solution 1:
Bob can't see can
Can with string from Alice to Bob
Can with string from Bob to Alice
Initial state:
Alice can is up.
Bob's can is down.
Alice does the following:
1. She waits until her can is down.
2. She releases the pets.
3. When the pets return, Alice checks whether they finished the food. If so, she resets the can.
4. Knocks down Bob's can.
Bob does the following:
1. He waits until his can is down.
2. He puts food in the yard.
3. Resets his can.
4. He pulls the string and knocks Alice's can down.
Solution 2:
Bob can't see can's on Alice's window.
Initial state:
Bob can is down.
Alice does the following:
1. Waits until pets want food.
2. Waits until Bob's can is up.
3. Knocks over Bob's can.
4. Wait until can is back up.
5. She releases the pets.
6. Wait until the pets return.
Bob does the following:
1. He waits until his can is down.
2. He puts food in the yard.
3. Resets his can.
You are one of P recently arrested prisoners. The warden sets
up a “switch room” with a light switch (on/off). Prisoners enter
the room one at a time and may toggle or leave the switch unchanged.
Each prisoner visits arbitrarily often. Any prisoner may declare when all have visited.
Devise a winning strategy when you know the initial switch is off.
Devise a winning strategy when you do not know whether the initial state is on or off.
If default state is off:
Designate the x'th prisoner as the counter.
Each prisoner on first visit:
- If switch is on, doesn't change it.
- If switch is off, flips switch on.
Each prisoner after first visit:
- Leaves switch unchanged.
When x prisoner enters:
- If switch is on, add 1 internally.
- If internal count is P - 1, announce all visited.
If default state unknown:
Modify solution so everyone counts twice.
Each prisoner waits until they count 2P prisoners.
The warden orders prisoners in a line, placing red or blue hats on each.
Each prisoner sees hats in front but not their own or behind. Starting
from the back, each guesses own hat color aloud. At least P-1 prisoners should be freed.
Devise a strategy.
First person (back) says "red" if even number of reds, "blue" if odd.
The i'th person ignores the first person's color but counts the number
of reds behind and in front (call this x).
Two cases:
- First person said "red": Even number of red hats.
-- If x is odd, say "red", else say "blue".
- First person said "blue": Odd number of red hats.
-- If x is odd, say "blue", else say "red".
Use Amdahl's Law to resolve:
(a) Suppose a method M is non-parallelizable and accounts for
40% execution time. What's the overall speedup limit?
(b) If M accounts for 30%, what speedup must M have to double overall speed?
(c) If M can be sped up three-fold, what fraction must M be to double overall speed?
Amdahl's Law = 1 / ((1 - p) + p / n) = s
(a) 40% serial, 60% parallel:
1 / ((1 - 0.6) + 0.6 / ∞) = 2.5x
(b) 1 / ((1 - 0.7) + 0.3 / n) = 2
Literally not possible, lol.
(c) x = % code sped up 3-fold
1 / ((1 - x) + x / 3) = 2
x = 75%
Running your application on two processors yields speedup S2. Use Amdahl's Law to derive a formula for speedup Sn on n processors in terms of n and S2.
1 / ((1 - p) + p / 2) = S2
S2 * ((1 - p) + p / 2) = 1
S2 * (1 - p) + (S2 * p) / 2 = 1
S2 - S2 p + (S2 p) / 2 = 1
Multiply both sides by 2:
2 S2 - 2 S2 p + S2 p = 2
Group p terms:
2 S2 - S2 p = 2
Rearrange:
- S2 p = 2 - 2 S2
Multiply both sides by -1:
S2 p = 2 S2 - 2
Divide both sides by S2:
p = 2 - (2 / S2)
Replug into Amdahl's Law:
Sn = 1 / ((1 - p) + p / n) = 1 / ((1 -
(2 - 2 / S2)) + (2 - 2 / S2) / n)
You have a choice between buying one uniprocessor that executes five zillion instructions per second, or a ten-processor multiprocessor where each processor executes one zillion instructions per second. Using Amdahl's Law, explain how you would decide which to buy for a particular application.
Our application has 0 parallelizable code so we want the uniprocessor. Multiple processor provides 0 speedup according to Amdahl's law because 0% of the code is parallelizable.