CODEWITHSUNDEEP
javamultithreadingsynchronizationdeadlockmonitor
Celesti Aurus
Celesti Aurus

Reputation: 35

wait() does not catch notify(); causes weird deadlock behavior

I'm modelling a train system with eight stations with threads and monitors. The system is modeled as follows, using a circular linked list:

   S2-S3-S4
  /        \
 S1        S5
 >\        /
   S8-S7-S6

All elements of the linked list are of the class Segment. There are two types of Segments, FreeSegments and Stations.

Trains run concurrently on the system as threads traversing the linked list. The code of the train thread is as follows:

public void runWithMonitors(boolean showMsgs) {
    // This is the entry monitor
    synchronized (entryPoint) {
        try {
            // Wait until the next segment is clear
            // This loop guards against spurious wakeups as recommended
            // by the official Java documentation
            while (entryPoint.isOccupied()) {
                entryPoint.wait();
            }
        } catch (InterruptedException ex) {
            print("Services interrupted.", showMsgs);
        }
    }

    // Run this code indefinitely
    while (true) {
        // This is the current segment monitor
        // Only one train can ever occupy this segment
        // Take note of the current segment
        Segment currSegmentMonitor = currSegment;

        synchronized (currSegmentMonitor) {
            // Take this spot
            currSegment.setIsOccupied(true);
            currSegment.setTrainInside(this);

            // If this segment is a station, load and unload passengers
            if (currSegmentMonitor instanceof Station) {
                // Open doors and allow passengers to get off and on
                alightPassengers(showMsgs);
                loadPassengers(showMsgs);
            }

            // Notify this train's observer that its position has changed
            trainObserver.update(dispatcher, showMsgs);

            // Is it okay to proceed?
            try {
                // Wait until the next segment is clear
                // This loop guards against spurious wakeups as recommended
                // by the official Java documentation
                while (nextSegment.isOccupied()) {
                    currSegmentMonitor.wait();
                }
            } catch (InterruptedException ex) {
                print("Services interrupted.", showMsgs);
            }

            // Leave this spot
            currSegment.setIsOccupied(false);
            currSegment.setTrainInside(null);

            // If ready, then proceed
            proceed();

            // Then tell others we're done occupying that spot
            currSegmentMonitor.notify();
        }
    }
}

proceed() implementation

// Move forward
private void proceed() {
    // We've just moved to the next segment
    currSegment = nextSegment;
    nextSegment = currSegment.getNextSegment();
}

Before a train can enter the system, it must wait for the entry segment to be clear. The entry segment is denoted by the > character before the first station (S1).

Once inside the loop, any train at a segment must wait for the next segment to be clear before it proceeds. This is implemented by wait()ing on the current segment until another train thread notify()s it.

However, upon testing, the wait()s don't honor the notify()s at all, causing a train to wait for no reason, deadlocking the system.

I'm testing the system with two or more threads.

Additional observations

I tried to replace the try block with the wait() with the code:

while (nextSegment.isOccupied());

I assumed that removing the wait() would work, but it still results in deadlocks for some reason.

The interesting part, though, is that when placing a debug print statement inside the busy wait, like so:

while (nextSegment.isOccupied()) {
    System.out.println("Next segment: " +   nextSegment.isOccupied());
}

It works normally.

Upvotes: 1

Views: 63

Answers (1)

Andreas
Andreas

Reputation: 159135

Don't use monitors. The problem with monitors is that if no threads are waiting, the notify() call is ignored.

Use Semaphore instead, where the "permit" represents the permission to enter the segment, i.e. that the segment is "free".

When a train wants to enter a segment, it calls acquire(), and when it leaves a segment, it calls release(). All the segments are initialized with 1 permit, i.e. all segments are initially "empty".

You can even use the availablePermits() to determine if the segment is currently "occupied".

UPDATE

If you don't want to use Semaphore, here's what wrong with your code:

Your code is "locking" the current segment, so access to the segment is controlled, however the following code violates that:

while (nextSegment.isOccupied()) {
    currSegmentMonitor.wait();
}

Here the code accesses the nextSegment without having a lock on that segment, i.e. without synchronizing on the segment.

In addition to that, the code is waiting on the wrong monitor, because it is waiting on the current monitor, even though it should be waiting on the next monitor.

Change code to this, to fix it:

synchronized (nextSegment) {
    while (nextSegment.isOccupied()) {
        nextSegment.wait();
    }
}

Upvotes: 2

Related Questions