General Structure

In order to keep safety and have threads waiting without locking each other out we can have the following structure in general:

//PRE for act: P (z.B. a > b)
public void m(){
    synchronized(lock) {
        while(!P) {
            try { lock.wait(); }
            catch {InterruptedException i} {}
        }
        // P holds here!
        doStuff();
        lock.notifyAll(); //only if P was changed by doStuff()
    }
}

public void setA(int a) {
    synchronized(lock) {
        //update a
        lock.notifyAll();
    }
}

Queue Example

In order to implement a non-blocking queue with different 'normal' locks, we run into a classic problem of nested synchronization on different locks:

public synchronized void enqueue(Object c) { //1
    while ((tail + 1) % SIZE == head) {
        synchronized (notFull) { //2
            try { notFull.wait(); } 
            catch (Exception e) {}
        }
    }

    synchronized (notEmpty) { notEmpty.notify(); } //3
    buf[tail] = c;
    tail = (tail + 1) % SIZE;
}

The code uses nested synchronized blocks on notFull and notEmpty. This can lead to deadlocks if two threads acquire these locks in different orders. For example:

Thread A acquires the lock on notFull and waits for notEmpty.
Thread B acquires the lock on notEmpty and waits for notFull.
Both threads are now stuck, leading to a deadlock.

Much better to use Locks and Conditions:

public class Queue2 {
    private final static int SIZE = 10;
    private final Object[] buf = new Object[SIZE];
    private int tail = 0, head = 0;

    private final Lock lock = new ReentrantLock();
    private final Condition notEmpty = lock.newCondition();
    private final Condition notFull = lock.newCondition();

    public Object dequeue() {
        lock.lock();
        try {
            while (tail == head) { // while empty
                try { notEmpty.await(); } catch (Exception e) {}
            }
            Object e = buf[head]; head = (head + 1) % SIZE;
            notFull.signal();
            return e;
        } finally { lock.unlock(); }
    }
    public void enqueue(Object c) {
        lock.lock();
        try {
            while ((tail + 1) % SIZE == head) {
                try { notFull.await(); } catch (Exception e) {}
            }
            buf[tail] = c; tail = (tail + 1) % SIZE;
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }
}

The Condition-based implementation in the Queue2 example is superior because:

No Nested Locks: It uses a single ReentrantLock with separate Condition objects (notEmpty and notFull), avoiding deadlocks.
Fine-Grained Control: Condition objects allow precise signaling (await() and signal()), improving concurrency.
Clearer Semantics: The use of Condition objects makes the code easier to understand and maintain.
Handles Spurious Wakeups: The while loop ensures the condition is re-checked after waking up.
By using ReentrantLock and Condition, the implementation avoids the pitfalls of the synchronized approach and provides a more robust and scalable solution.

Table of Contents

General Structure

Queue Example