So basically this is the problem that I'm trying to solve:
David, Sean, and Frank plant seeds continuously. David digs the holes. Sean then places a seed in each hole. Frank then fills the hole up. There are several synchronization constraints:
Sean cannot plant a seed unless at least one empty hole exists, but Sean does not care how far David gets ahead of Sean.
Frank cannot fill a hole unless at least one hole exists in which Sean has planted a seed, but the hole has not yet been filled. Frank does not care how far Sean gets ahead of Frank.
Frank does care that David does not get more than MAX holes ahead of Frank. Thus, if there are MAX unfilled holes, David has to wait.
There is only one shovel with which both David and Frank need to dig and fill the holes, respectively.
Write the pseudocode for the 3 processes which represent David, Sean and Frank using semaphores as the synchronization mechanism. Make sure to initialize the semaphores.
And this is my solution implemented in Java, which, I know, is not very elegant and kinda wasteful compared to the standard solution:
import java.util.concurrent.Semaphore;
public class Holes {
private static final int MAX = 3;
private static final Semaphore mutexForShovel = new Semaphore(1, true);
private static final Semaphore mutexForHoleCount = new Semaphore(1, true);
private static int emptyHoleCount = 0, seededHoleCount = 0, finishedHoleCount = 0;
public static void main(String[] args) {
new Thread(() -> { // David
try {
while (true) {
if (emptyHoleCount < MAX) {
mutexForShovel.acquire(); // wait for shovel
System.out.println("David is digging a hole...");
Thread.sleep(200); // try annotating this
mutexForShovel.release(); // release shovel
mutexForHoleCount.acquire(); // enter critical section
emptyHoleCount++;
mutexForHoleCount.release(); // exit critical section
System.out.println("Empty = " + emptyHoleCount +
" Seeded = " + seededHoleCount +
" Finished = " + finishedHoleCount);
}
}
} catch (InterruptedException e) {
System.out.println(e.toString());
}
}).start();
new Thread(() -> { // Sean
while (true) {
try {
if (emptyHoleCount > 0) {
System.out.println("Sean is seeding a hole...");
Thread.sleep(200); // try annotating this
mutexForHoleCount.acquire(); // enter critical section
emptyHoleCount--;
seededHoleCount++;
mutexForHoleCount.release(); // exit critical section
System.out.println("Empty = " + emptyHoleCount +
" Seeded = " + seededHoleCount +
" Finished = " + finishedHoleCount);
}
} catch (InterruptedException e) {
System.out.println(e.toString());
}
}
}).start();
new Thread(() -> { // Frank
while (true) {
try {
if (seededHoleCount > 0) {
mutexForShovel.acquire(); // ask for shovel
System.out.println("Frank is filling a hole...");
Thread.sleep(200); // try annotating this
mutexForShovel.release(); // release shovel
mutexForHoleCount.acquire(); // enter critical section
seededHoleCount--;
finishedHoleCount++;
mutexForHoleCount.release(); // exit critical section
System.out.println("Empty = " + emptyHoleCount +
" Seeded = " + seededHoleCount +
" Finished = " + finishedHoleCount);
}
} catch (InterruptedException e) {
System.out.println(e.toString());
}
}
}).start();
}
}
I thought I ordered the acquire() and release() operations in a way that avoids any "hold-and-wait" and thus avoids deadlock. However, this is the output I got from running it in the terminal:
David is digging a hole...
Empty = 1 Seeded = 0 Finished = 0
David is digging a hole...
Empty = 2 Seeded = 0 Finished = 0
David is digging a hole...
Empty = 3 Seeded = 0 Finished = 0
Confused as I was, I ran it line-by-line in the debugger, and this is what I got:
David is digging a hole...
Sean is seeding a hole...
Frank is filling a hole...
Empty = 1 Seeded = 0 Finished = 0
Empty = 0 Seeded = 1 Finished = 0
David is digging a hole...
Empty = 1 Seeded = 0 Finished = 1
Sean is seeding a hole...
David is digging a hole...
Empty = 0 Seeded = 0 Finished = 1
Empty = 0 Seeded = 1 Finished = 1
Frank is filling a hole...
Empty = 1 Seeded = 1 Finished = 1
Empty = 1 Seeded = 0 Finished = 2
Sean is seeding a hole...
David is digging a hole...
...
Now that's reasonable output! Isn't it? Moving on, I removed the annotated Thread.sleep() lines, and I got this:
...
Sean is seeding a hole...
Frank is filling a hole...
Empty = 2 Seeded = 0 Finished = 29748
Empty = 2 Seeded = 1 Finished = 29747
Sean is seeding a hole...
Frank is filling a hole...
Empty = 1 Seeded = 1 Finished = 29748
Empty = 1 Seeded = 0 Finished = 29749
Sean is seeding a hole...
Frank is filling a hole...
Empty = 0 Seeded = 1 Finished = 29749
Empty = 0 Seeded = 0 Finished = 29750
Process finished with exit code 130 (interrupted by signal 2: SIGINT)
Which, again, is decent output!
So I guess I have two questions now:
Q1: Does the original output in the terminal suggest that a deadlock occurred? If so, what part of my code is wrong and how can I change it?
Q2: Why is it that I'm getting different outputs running basically the same code in different ways?
Thanks a lot!!!
private static volatile int emptyHoleCount = 0,
seededHoleCount = 0,
finishedHoleCount = 0;
Try again now. The threads don't notice the changes on those variables, since they are not marked as volatile.
volatilehas semantics for memory visibility. Basically, the value of a volatile field becomes visible to all readers (other threads in particular) after a write operation completes on it. Without volatile, readers could see some non-updated value.The volatile modifier guarantees that any thread that reads a field will see the most recently written value.
Your while loops may be affected by compiler optimization, as a result not checking the variable updates. Marking the variables as volatile avoids this (just like saying, hey, do not optimize this, it may change, so constantly check its value).
When you sleep them, or debug them, you are generating a thread state change that may involve your threads checking the variable's values again, when returning into running state. Without that "state change", your threads read stale data.
Besides this, as a suggestion, your threads contain a very dangerous loop:
while(true)
As you show in the example, you stop them by a SIGINT call. I'd suggest implementing some kind of monitor or setting some volatile boolean flag in order to stop them gracefully.
Deadlock example involving non volatile variables
public class UntilYouUpdateIt
{
public static boolean flag = true;
public static void main(String[] args) throws InterruptedException
{
Thread t1 = new Thread(()->
{
while(flag){}
System.out.println("end");
});
t1.start();
Thread.sleep(100);
Thread t2 = new Thread(()->
{
flag = false;
System.out.println("changed");
});
t2.start();
}
}
The code above would output:
changed
But the program would never end. Thread t1 won't ever exit its loop as a result of compiler optimization, assuming flag will always be true. Setting the boolean as volatile avoids this, just like with your example's int variables.