I want to replicate race condition into deadlock using the Producer-Consumer model in Java

Question

On wiki I found the following pseudo-code for a producer-consumer program which has a race condition that can lead into a deadlock:

int itemCount = 0;

procedure producer() 
{
    while (true) 
    {
        item = produceItem();

        if (itemCount == BUFFER_SIZE) 
        {
            sleep();
        }

        putItemIntoBuffer(item);
        itemCount = itemCount + 1;

        if (itemCount == 1) 
        {
            wakeup(consumer);
        }
    }
}

procedure consumer() 
{
    while (true) 
    {

        if (itemCount == 0) 
        {
            sleep();
        }

        item = removeItemFromBuffer();
        itemCount = itemCount - 1;

        if (itemCount == BUFFER_SIZE - 1) 
        {
            wakeup(producer);
        }

        consumeItem(item);
    }
}

With this implementation the following scenario should occur:

1. The consumer has just read the variable itemCount, noticed it's zero and is just about to move inside the if block.

2. Just before calling sleep, the consumer is interrupted and the producer is resumed.

3. The producer creates an item, puts it into the buffer, and increases itemCount.

4. Because the buffer was empty prior to the last addition, the producer tries to wake up the consumer.

5. Unfortunately the consumer wasn't yet sleeping, and the wakeup call is lost. When the consumer resumes, it goes to sleep and will never be awakened again. This is because the consumer is only awakened by the producer when itemCount is equal to 1.

6. The producer will loop until the buffer is full, after which it will also go to sleep.

I want to be able to replicate this in Java, but I so far I am unable to after running my program many times. Here is my code:

private LinkedList<Integer> sharedList = new LinkedList<Integer>();
private int sharedValue = 0;
private int MAX_LIMIT = 10;

public void produce() throws InterruptedException {

    Random random = new Random();

    while (true) {
        synchronized (this) {
            if (sharedValue == MAX_LIMIT) { //'produce' thread waits if list is full
                wait();
            }
            sharedValue = sharedValue + 1;
            sharedList.add(sharedValue); System.out.println("added value: " + sharedValue);

            if (sharedValue == 1) {
                notify(); //notifies  'consume' thread if list is not empty
            }
        }
    }
}

public void consume() throws InterruptedException {

    Random random = new Random();

    while (true) {
        synchronized (this) {
            if (sharedValue == 0) {    //'consume' waits if list is empty
                wait();
            }

            sharedValue = sharedValue - 1;
            sharedList.remove(); System.out.println("removed value: " + sharedValue);

            if (sharedValue == MAX_LIMIT-1) {
                notify(); //notifies 'produce' if list is not full
            }
        }
        Thread.sleep(random.nextInt(1000));
    }

}

Answer 1

The reason is you synchronized whole iteration step. Two blocks of code under synchronized (this) {...} will run sequentially.

You could replicate it with:

    private LinkedList<Integer> sharedList = new LinkedList<Integer>();
    private volatile int sharedValue = 0;
    private int MAX_LIMIT = 10;

    public void produce() throws InterruptedException {

        while (true) {

            if (sharedValue == MAX_LIMIT) { //'produce' thread waits if list is full
                synchronized (this) {
                    wait();
                }
            }
            synchronized (this) {
                sharedValue = sharedValue + 1;
                sharedList.add(sharedValue);
                System.out.println("added value: " + sharedValue);
            }

            if (sharedValue == 1) {
                synchronized (this) {
                    notify(); //notifies  'consume' thread if list is not empty
                }
            }
        }

    }

    public void consume() throws InterruptedException {

        while (true) {

            if (sharedValue == 0) {    //'consume' waits if list is empty
                synchronized (this) {
                    wait();
                }
            }

            synchronized (this) {
                sharedValue = sharedValue - 1;
                sharedList.remove();
                System.out.println("removed value: " + sharedValue);
            }

            if (sharedValue == MAX_LIMIT - 1) {
                synchronized (this) {
                    notify(); //notifies 'produce' if list is not full
                }
            }
        }

    }