Dining Philosophers Problem
The book I’m going through, Programming Interviews Exposed, presents the Dining Philosophers Problem and their solution to the problem. Firstly, their explanation for their solution is weak because they do not describe the underlying principle they applied to prevent deadlocks. Secondly, their implementation of their solution still results in starvation. Finally, with a few modifications, I’ll go over my improved solution and compare the results of the two.
The Problem
This question comes from the Programming Interviews Exposed book:
Five introspective and introverted philosophers are sitting at a circular table. In front of each philosopher is a plate of food. A fork (or a chopstick) lies between each philosopher, one by the philosopher’s left hand and one by the right hand. A philosopher cannot eat until he or she has both forks in hand. Forks are picked up one at a time. If a fork is unavailable, the philosopher simply waits for the fork to be freed. When a philosopher has two forks, he or she eats a few bites and then returns both forks to the table. If a philosopher cannot obtain both forks for a long time, he or she will starve. Is there an algorithm that will ensure that no philosophers starve?
Applying an Order to Resources
In Programming Interviews Exposed, the authors recommend that all except one philosopher grabs the left fork, then the right. They mention this prevents the dead lock with no explanation or how someone would come up with this solution.
Firstly, you get deadlocks where there is a cycle in your resource allocation graph. In these graphs, you have directed edges from resources to threads when that thread has a lock on that resource. You have an edge from a thread to a resource when that thread is waiting for that resource. A cycle in this graph describes a scenario where no one can make progress because everyone in the cycle is waiting on each other to finish.
Chopstick1 -> Philospher1 -> C2 -> P2 -> C3 -> P3 -> C4 -> P4 -> C5 -> P5
^ /
\________________________________________________________________/
One way to prevent deadlocks, is to ensure that you never have cycles. If you can create an order to describe your resources and if all threads acquire the resources in that order, then you will never have deadlocks.
To solve the dining philosophers problem, you can assign a number to each fork, giving it an order. You always grab the lowest fork first. For instance philosopher 5 needs forks 1 and 5. Since 1 is the lowest, philosopher 5 will try to grab this fork first. This is how you arrive at the solution where all except one philosopher graphs the left first.
Another real world problem you can see this resource ordering technique applied to is bank accounts. Imagine you’re implementing a transfer from a withdrawing account into the depositing account. The naive way would be to first lock the withdrawing account, then lock the depositing account. However, this generates a cycle when the two accounts are trying to transfer to each other at the same time. First both transfers lock the withdrawing account, locking both accounts. Now both transfers try to lock the depositing accounts and waits forever because both accounts are already locked. Instead of locking the withdrawing account, then the depositing account, first lock the account with the lower ID. This will prevent all possible deadlocks.
Barging
The idea behind Programming Interviews Exposed’s solution is correct as explained in the previous section, but their implementation is not. At a high level, their solution involves monitors and looks like this:
synchronized(lowerLock) {
synchronized(higherLock) {
// philosopher eats the food
}
}
Unfortunately, Java monitors do not have a queue for threads waiting for a monitor. As a result, any thread waiting for a monitor even the most recently added one can be the next one allowed into the monitor. This is contrary to a programmer’s intuition as we expect the oldest waiter to be allowed in next. Not allowing the longest waiting thread is called barging. When the lives of philosophers are at stake, you want to prevent barging because it allows starvation.
To illustrate, I implemented the books solution of the problem in Java and recorded how many times each philosopher got to eat, with various eating durations:
When philosopher takes no time to eat: count philosopher_id 1 0 104 1 390 3 When philosopher takes 100 ms to eat: count philosopher_id 8 0 28 1 76 2 371 3 12 4 When philosopher takes 1 second to eat: count philosopher_id 16 0 48 1 74 2 337 3 20 4
From these results, we can see that philosopher 3 gets to eat an unfair amount of time and that when it takes no time to eat, some philosophers never get to eat.
Preventing Barging
The easiest way to prevent barging in Java is to use fair locks. ReentrantLock’s constructor accepts a boolean fairness parameter. By setting this to true, it fulfills the .lock() calls in the order that they come, unlike a monitor. The resulting code would look something like:
ReentrantLock [] locks = new ReentrantLock[5];
for(int i = 0 ; i < locks.length; i++) {
locks[i] = new ReentrantLock(true); // make it fair
}
// ...
// ...
lowerLock.lock();
try {
higherLock.lock();
try {
// philosopher eats the food
} finally {
higherLock.unlock();
}
} finally {
lowerLock.unlock();
}
I re-ran the problem with the fair locks and recorded how many times each philosopher ate:
When philosopher takes no time to eat count philosopher_id 108 0 38 1 48 2 263 3 38 4 When philosopher takes 100ms to eat count philosopher_id 85 0 95 1 99 2 131 3 85 4 When philosopher takes 1 second to eat count philosopher_id 89 0 91 1 100 2 127 3 88 4
From these results, we see that in all scenarios, no philosopher starved. Secondly, we see a more even distribution of eating compared to the previous barging solution. Unfortunately we are unable to eliminate all the unfairness as the resource ordering we used to solve the problem gives higher priority to the second highest philosopher resulting in an inherent unfairness. From this example we can see that if you have a scenario where you need to prevent starvation, make sure to use fair locks instead of monitors.
How To Avoid Busy Waiting
Update 2021-04-08: Viliam spotted an error. Thank you again! I called notify() and wait() on the implicit this rather than the lock! This adds to my argument that the best way to wait for something is to use a Future. There are so many ways to get it wrong.
Programming Interviews Exposed asks us to describe busy waiting and how to avoid it. The book provides a decent solution, but not the best solution. I’ll first introduce the problem and then build upon the solution until we have our best solution.
Busy Waiting
You have busy waiting When one thread, waits for a result from another thread and you use and NOOP/empty loop to wait for that result. We will explore waiting for a result from two sub tasks to demonstrate and solve this problem.
Thread thread1 = new Thread(new Subtask1Runnable());
Thread thread2 = new Thread(new Subtask2Runnable());
thread1.start();
thread2.start();
while( waitinigForThread1() && waitingForThread2() ) {
// empty loop
}
// do something with result from thread1 and thread2
You want to avoid this pattern because it wastes CPU cycles:
- Other threads you have running could of made use of those cycles
- Other processes sharing the same machine could have also used those cycles
- If the machine only has one CPU, thread2 could have made use of those cycles
Poor Solution: Sleep
So the issue is that we’re wasting CPU cycles by repeatedly checking the condition. So what if we made the thread sleep for a bit.
while( waitinigForThread1() && waitingForThread2() ) {
Thread.sleep(1000); // Sleep for 1 second
}
This is an improvement over busy waiting as we’re now wasting less cycles. However
there are still some draw backs to this pattern:
- You’re still wasting cycles. It may seem like you’re wasting one cycle every
second. However, every time the thread wakes up it has to reload the thread’s stack, registers, and it has to recompute if the other thread is done. There’s still significant wastage. - How do you set the sleep duration?
- Set it too long, and there is a long delay between the threads finishing and
the main thread recognizing that it’s done - Set it too short, and you increase the amount of wasted cycles
- Set it too long, and there is a long delay between the threads finishing and
Better But Still Poor Solution: Exponential Backoff
To take away a bit of the tuning, we can add an exponential backoff. To describe the process, imagine that your plane gets delayed for some unknown period of time. What do you do? Well first you might go to the washroom for a few minutes. Then you might get something to eat for half an hour. Then you might play a game on your cellphone for an hour. Finally, you’ll read a book for the next couple of hours. Your waiting tasks become progressively larger as you wait more. That’s the idea behind exponential backoff. You sleep for progressively longer durations as you wait for longer periods of time.
private static final int MAX_BACKOFF=1000*60*60; // 1 hour
private static final int INITIAL_BACKOFF=100; // 100ms
int backOff=INITIAL_BACKOFF;
while( waitinigForThread1() && waitingForThread2() ) {
Thread.sleep(backOff); // Sleep for 1 second
backOff=backOff<<2; //bit shift to the left to multiply by 2
if(backOff < MAX_BACKOFF) {
backOff = MAX_BACKOFF;
}
}
Now this solution isn’t the best possible solution yet for a couple of reasons:
- Ideally we want the the main thread to wake up only once or twice
- Once when the first sub task completes
- A second time when the second sub tasks completes
- We still have to play with the starting back off, and max back off parameters to get decent performance
Decent Solution: Locking or Monitors (Based on Programming Interviews Exposed)
As I hinted in the previous section, is there a way you can just wake up the sleeping thread once each task finishes? This is the solution that Programming Interview Exposed proposes. You can setup up some a lock and have the main thread wait on the lock. Then the two threads ‘notify’ when they have finished. Each ‘notify’ wakes the main thread and the main thread check to see if both threads finished.
This method uses the least possible cycles, but it is error prone. If not coded properly, you can end up with race conditions or deadlocks. Consider our two sub task example:
Object lock = new Object(); // shared object to synchronize on
int doneCount = 0;
Thread thread1 = new Thread(new Runnable() {
public void run() {
// ...
// do sub task 1
// ...
synchronized(lock) {
doneCount++;
lock.notify();
}
}
});
Thread thread2 = new Thread(new Runnable() {
public void run() {
// ...
// do sub task 2
// ...
synchronized(lock) {
doneCount++;
lock.notify();
}
}
});
// this is the main thread again
synchronized(lock) {
thread1.start();
thread2.start();
while(doneCount < 2) {
lock.wait();
}
}
This solution is great as the main thread only wakes up twice. Once when sub task 1 finishes, and a second time when sub task 2 finishes.
However, in this example we can mess up in many ways:
- If I started the threads outside the synchronized block, the two threads
could finish before the main thread calls ‘wait()’. This would leave the main thread sleeping forever and no future notifies are called. - If I put the count outside of the synchronized block, the two threads might
update them at the same time and I’ll get doneCount==1 instead of 2! - If I forget to call notify() on one of the threads, then when the main thread
might never wake up because it didn’t get one of the notifications. - Placing the entire sub task in the synchronized block instead of just the
shared data accesses would of only let one sub task run at a time resulting in
no parallelism. - In a previous version of the above pseudocode I wrote notify() and wait() instead of lock.notify() and lock.wait()! If you use a shared Object lock monitor, you have to remember to call notify() and wait() on that lock instead of this.
As a result, I do not recommend the solution presented in Programming Interviews Exposed.
Good Solution: Futures and Other Concurrency Libraries
Instead of trying to carefully code this pattern every time, you can use libraries that have already correctly implemented these patterns. In our example where we’re waiting for two results from two threads so we can apply Futures.
ExecutorService executor = ...
Future<String> future1 = executor.submit( new Callable<String>() {
public String call() {
/* do work for first result here */
}
});
Future<String> future2 = executor.submit( new Callable<String>;() {
public String call() {
/* do work for second result here */
}
} );
String result1 = future1.get();
String result2 = future2.get();
From the example we can immediately see that it’s the most elegant solution, and less bug prone. But more importantly, we still use the least possible cycles as execution of the main thread only resumes when each of the futures complete.
Here we were looking at an example waiting on two sub tasks to complete. However, there are many different waiting scenarios and the standard libraries of C# and Java provide many concurrency facilities to make developers’ lives easier. Before trying to code up your own monitor or locking, see if you problem has been solved before.
Summary
If you want to avoid busy waiting you can apply the write concurrent library for your problem. If the library doesn’t exist, you can try using monitors and locks, but be warned that there are many opportunities to mess up. Finally, don’t use busy loops or sleep to wait on tasks.
Removing Characters From a String
Programming Interviews Exposed asks us to remove characters from an input string, looking for the characters in a second string. I am unhappy with solution they provide, particularly because of the reasons they use to invalidate what I believe to the better solution. You can check out my solution to the problem on my github repository.
In this problem we are given the following C# signature:
string removeChars( string str, string remove );
‘str’ is the original string we are removing characters from. ‘remove’ is the string that contains that characters that we need to remove from ‘str’. For example if
str=”hello world” and
remove=” wo”
the result should be “hellwrld” with all spaces, w’s, and o’s removed.
Synchronized
My first issue, is they recommend not using the StringBuffer for the wrong reason. The reason you do not want to use StringBuffer, is because it’s synchronized in both Java and C#. Below is the Java source code from grepcode:
public synchronized StringBuffer append(char c) {
super.append(c);
return this;
}
The Microsoft documentation on StringBuffer says,
The methods are synchronized where necessary so that all the operations on any particular instance behave as if they occur in some serial order that is consistent with the order of the method calls made by each of the individual threads involved.”
Since the buffer does not exceed the scope of our method, and we know that only one thread is modifying the buffer, we don’t need the expensive overhead of protecting against concurrent access. We can go with the cheaper solution of using a StringBuilder (in both Java and C#).
Extra Memory
Here the authors recommend building the string in the original character array and using two pointers to the array. One for the next non-deleted character and a second for where the next character is coming from. Ideally this is an excellent solution, if implementing correctly. I have annotated their solution with the issues.
// str has N characters
// remove has M characters
string removeChars( string str, string remove ){
//NOTE: We use N extra memory because .toCharArray() copies the
//array in string because strings are immutable
char[] s = str.toCharArray();
//Note: Again, we use M extra memory because .toCharArray copies
char[] r = remove.toCharArray();
bool[] flags = new bool[128]; // assumes ASCII!
int len = s.Length;
int src, dst;
// Set flags for characters to be removed
for( src = 0; src &amp;lt; len; ++src ){
flags[r[src]] = true;
}
src = 0;
dst = 0;
// Now loop through all the characters,
// copying only if they aren’t flagged
while( src &amp;lt; len ){
if( !flags[ (int)s[src] ] ){
s[dst++] = s[src];
}
++src;
}
// NOTE: Again we use N extra memory because the string constrcutor
// copies the characters of s, into the new string
return new string( s, 0, dst );
}
Because Strings are immutable in Java and C#, toCharArray() in Java and toCharArray() in C# both have to allocate a new character array to prevent the caller from modifying the internal character array. Secondly you cannot force the Java String(char[], int, int) or the C# string(char[],int,int) [String->StringNative->StringObject] methods to use your char[] array. It has to copy it because the caller has a reference to the original character array and potentially modify it.
Overall, we used 2N + M memory, when the best possible solution in Java or C# uses 2N extra memory. We need N for the buffer and N for returning the result as a String. So we might as well have kept a StringBuilder anyways as it tremendously simplifies the code and uses potentially less extra memory because potentially a majority of the characters in the original string might be removed. I think this is an excellent example of what Knuth meant in “premature optimization is the root of all evil” because in this solution we didn’t make it more efficient and we made it more complex.
If you really wanted to use no extra memory, this should have been implemented in C/C++ with the following signature:
void removeChars( char * str, char * rem );
Keeping the same code as above, but modifying str instead, allows us to incur no extra memory by modifying the contents of char*str in place.
Summary
Given the solution provided in the book and the limitations of immutable Strings in Java and C#, we might as well have used a StringBuilder, incurring potentially less excess memory and a simpler solution. StringBuffer should not be used as it’s synchronized and we’re not using Threads. Finally, we were really wanted to achieve the author’s intended solution, we need to use C/C++ and change the method signature.
Joseph Mate's Blog 
leave a comment