Threads - Unlocking lock using flags and try/finally

Question

I'm trying to synchronize 3 threads. Each one of them handles a caterpillar that is moving along it's own path. Unfortunately their paths are crossed like this:

To achieve this goal I'm using locks. There are two sections where blocks are shared: horizontal and vertical (I named it above and below). The problem is that a thread at one point wants to be in two shared sections at the same time.

My question is:

Can I unlock a lock inside try/finally clause using a flag?

I mean, when a thread unlocks a lock inside a try/finally clause, a flag is set and in finally clause it checks if the flag is set, then doesn't unlock a second time. I think it is a safe solution but maybe I'm wrong.

Is there any other way to synchronize the threads?

This is my code: (It almost works)

public void moveForward() throws InterruptedException {
    redIsUpofAbove();
    int choose= 0;
    if (Route.critcalSectionAbove.contains(head))
        choose= 1;
    if (Route.critcalSectionBelow.contains(head))
        choose= 2;

    switch (choose) {
    case 1: {
        boolean flag = true;
        System.err.println(name + " Lock above");
        synchronization.aboveLock.lock(); 
        try {

            takeNextGrid();
            Thread.sleep(sleepValue);
            while (isInAboveCriticalSection()) {
                takeNextGrid();
                Thread.sleep(sleepValue);
                if (isInBelowCriticalSection()) {// Caterpillar is on two
                                                    // shared sections
                    System.out.println(name + " Lock below");
                    if (!synchronization.belowLock.tryLock()) {

                        synchronization.aboveLock.unlock();
                        System.out.println(name + " Unlock above");
                        synchronization.belowLock.lock();
                        flag = false;
                    }
                    try {
                        while (isInBelowCriticalSection()) {
                            takeNextGrid();
                            if (!isInAboveCriticalSection() && flag) {
                                synchronization.aboveLock.unlock();
                                flag = false;
                                System.out.println(name + " Unlock above");
                            }
                            Thread.sleep(sleepValue);
                        }
                    } catch (Exception e) {
                    } finally {
                        synchronization.belowLock.unlock();
                        System.err.println(name + "Unlock belovelock");
                    }
                }
            }
        } catch (Exception e) {
        } finally {
            if (flag) {
                synchronization.aboveLock.unlock();
                System.out.println(name + " unlock above");
            }
        }

        break;
    }
    case 2: {
        boolean flag = true;
        System.err.println(name + " Lock below");
        synchronization.belowLock.lock();
        try {

            takeNextGrid();
            Thread.sleep(sleepValue);
            while (isInBelowCriticalSection()) {
                takeNextGrid();
                Thread.sleep(sleepValue);
                if (isInAboveCriticalSection()) {
                    if (!synchronization.aboveLock.tryLock() && flag) {
                        synchronization.belowLock.unlock();
                        System.out.println(name + " Unlock below");
                        synchronization.aboveLock.lock();
                        flag = false;
                    }
                    try {
                        System.out.println(name + " Lock above");
                        while (isInAboveCriticalSection()) {
                            takeNextGrid();
                            if (!isInBelowCriticalSection() && flag == true) {
                                synchronization.belowLock.unlock();
                                flag = false;
                                System.out.println(name + " Lock below");
                            }
                            Thread.sleep(sleepValue);
                        }
                    } catch (Exception e) {

                    } finally {
                        synchronization.aboveLock.unlock();
                        System.err.println(name + "Lock abovelock");
                    }

                }
            }
        } catch (Exception e) {

        } finally {
            if (flag) {
                synchronization.belowLock.unlock();
                System.out.println("Opuszczam belowLock");
            }
        }

        break;
    }
    default: {
        takeNextGrid();
        break;
    }
    }

}

And the last question:

Is there a way to set a priority to wake up, on threads which are waiting on a locked lock?

Answer 1

Can I unlock a lock inside try/finally clause using a flag?

Assuming you don't get an InterruptException between the lock() call and when you set the flag, then this should work correctly; however, I don't think it makes any sense in the given context.

If you get an exception, what happens to the caterpillar? Does it disappear? If it's still sitting in the same place on the path even after the exception is thrown, then it's still occupying that section of the path; therefore, it doesn't make sense to release the lock.

---

Is there any other way to synchronize the threads?

There are definitely other synchronization mechanisms that you could try (atomics, monitor locks, etc), but this doesn't seem like a performance-critical application, so I would just use whatever makes the most sense to you. If locks make sense, then use locks.

Now, if you're asking if there's a different way to synchronize (i.e., a different strategy to use for mutual exclusion on your paths), then I do have a suggestion for that:

Your current solution has an obvious deadlock problem. Since the below and above sections are acquired separately, the blue caterpillar (G2, "Blue") can acquire the lower section and move in, and at the same time, the red caterpillar (G1, "Red") can acquire the upper section and move in. Now there is no way for either caterpillar to complete its path—they are deadlocked (G1 won't be able to advance into the lower section, and G2 won't be able to advance into the upper section).

By splitting the path into more critical sections (as shown in my image), and acquiring multiple sections when moving into the critical sections, then you can avoid this deadlock situation.

As long as you ensure there are at most 2 caterpillars in the "critical T" (i.e., the union of all 4 critical regions), then you can always avoid deadlock. You can do this by creating a counting semaphore with 2 permits. You acquire() before grabbing the lock for the first critical region in the path, and release() sometime after leaving that region. For example, for Red, the sequence would be:

1. acquire() on the sempahore
2. lock() Above, and advance through it
3. lock() Below-Left
4. release() on the semaphore
5. Continue advancing into Center and then Below-Left
6. Once Red's tail leaves Center, unlock() Above
7. Once Red's tail leaves Below-Left, unlock() Below-Left
8. Continue advancing through the non-critical region...

Notice that we don't need to explicitly lock Center since it's implicitly protected by the semaphore and the other locks.

There are obviously other methods that you could use to ensure that there are only 2 caterpillars in the "critical T", but a semaphore seemed like the simplest way to do this.

This solution avoids deadlock as follows:

• If Red is in Above, and Blue is in Below-Right, then Blue blocks until it can acquire Above before advancing into Center, allowing Red to exit the critical region first.
• If Blue is in Below-Right, and Green is in Below-Left, then Green blocks until it can acquire Below-Right before advancing into Center, allowing Blue to exit the critical region first.
• If Green is in Below-Left, and Red is in Above, then Red blocks until it can acquire Below-Left before advancing into Center, allowing Green to exit the critical region first.

All other possible configurations will also avoid deadlock—those are just the three most interesting cases.

---

Is there a way to set a priority to wake up, on threads which are waiting on a locked lock?

I'm not aware of any tools in the Java library that would actually give you priority guarantees like this. You'd either have to find a 3rd-party library that does this, or implement your own.

A simple way to do this would just be to not use separate threads for your caterpillars. You could do all of your caterpillar logic with a single thread—there's no reason that you need one thread for each caterpillar. If you had all of the logic in a single thread, then the order in which you processed the caterpillars would give you an implicit priority ordering.

Answer 2

Algorithm by DaoWen work well. This is the code for Red Caterpillar, other Caterpillars works on the same principle with small changes. I splitted the path into three critical sections: Above, Left-Below, Right-Below. Center-Region helps define when caterpillar left critical section and then unlock blocade. Semaphores guaranteed that maximally two of threads can ask for enter to critical sections. Flags are useful to unlock blocade before end of the method and provide that blocades are unloced only once.

    public final ReentrantLock aboveLock = new ReentrantLock(true);
public final ReentrantLock LeftBelowLock = new ReentrantLock(true);
public final ReentrantLock RightBelowLock = new ReentrantLock(true);
public final Semaphore semaphore = new Semaphore(2); //counting semaphore

private void movingRed() throws InterruptedException {
    while (true) {
        if (Route.critcalSectionAbove.contains(head)) {
            synchronization.semaphore.acquireUninterruptibly();
            synchronization.aboveLock.lock();
            isAboveLock = true;
            synchronization.LeftBelowLock.lock();
            isBelowLeftLock = true;
            synchronization.semaphore.release();
            try {
                while (!ifTailLeftCenter()) { // advance Critical-region
                                                // until tail crosses center
                    takeNextGrid();
                    Thread.sleep(sleepValue);
                }
                // caterpillar's tail left Center section
                isAboveLock = false;
                synchronization.aboveLock.unlock(); // unclocking above
                while (isInBelowCriticalSectionLeft()) { // advance until
                                                            // tail belong
                                                            // to Left-Below
                    takeNextGrid();
                    Thread.sleep(sleepValue);
                }
                // caterpillar's tail left LeftBelow section
                isBelowLeftLock = false;
                synchronization.LeftBelowLock.unlock();
            } catch (Exception e) {
            } finally {
                if (isAboveLock)
                    synchronization.aboveLock.unlock(); // in case exception
                                                        // was throw before
                                                        // unlock any lock
                if (isBelowLeftLock)
                    synchronization.LeftBelowLock.unlock();
            }
        }
        // caterpillar moving through non-critical region
        takeNextGrid();
        Thread.sleep(sleepValue);
    }
}

Thanks for your help.