Multithreading with Semaphores in Java

user_13363688 0
Viewed 205

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:

  1. Sean cannot plant a seed unless at least one empty hole exists, but Sean does not care how far David gets ahead of Sean.

  2. 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.

  3. 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.

  4. 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!!!

synchronized deadlock multithreading semaphore java
3 Answers
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.

volatile has 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.

user_21489530

Your threads go into rapid-churn if the start conditions are not met. That is, they become "while(true) if (false)" and then just cycle around. With no work to do, they spin really fast and likely negatively impact other things wanting to use the CPU instead. I'd recommend that if there is no work to do (start condition not met), have the thread sleep before checking again. That way the thread (with no work to do) plays well with other threads.

You should watch computer performance graph. If you are hitting deadlock, then you'd expect the CPU graphs to all go to zero - no CPU can move forward because each is waiting for the other. I think you are actually hitting consumption - CPU probably pegs at 100% and stays there. The infinite-loop thread sucks up app the CPU and the thread that would break free from the loop never gets enough air to start.

user_47889280

yes use volatile and some relax time when not able to work, but also, seeder Sean should not emptyHoleCount--; filler Frank should.

The constraint #3 is a contract between digger Dean and filler Frank that the digger Dean is honoring with if(emptyHoleCount < MAX) but that seeder Sean is interfering with, instead of filler Frank.

user_20235770
Related