Understanding Producer-Consumer using java synchronization

Question

I have been working on the PC problem to understand Java Synchronization and inter thread communication. Using the code at the bottom, the output was

Producer produced-0
Producer produced-1
Producer produced-2
Consumer consumed-0
Consumer consumed-1
Consumer consumed-2
Producer produced-3
Producer produced-4
Producer produced-5
Consumer consumed-3
Consumer consumed-4

But shouldn't the output be something like as below

Producer produced-0
Consumer consumed-0
Producer produced-1
Consumer consumed-1
Producer produced-2
Consumer consumed-2
Producer produced-3

I expect such an output because my understanding is, the consumer is notified of the value produced as soon as the the produce method releases lock when the method terminates. As a result the consumer block which was waiting, enters the synchronized state acquiring lock to consume the value produced, meanwhile the producer method is blocked. this lock is released at the end of the consume method which is acquired by the producer thread which was blocked due to synchronization and the cycle continues as each method is blocked due to the lock acquired.

Please let me know what did I misunderstood? Thanks

package MultiThreading;

//Java program to implement solution of producer
//consumer problem.
import java.util.LinkedList;

public class PCExample2
{
 public static void main(String[] args)
                     throws InterruptedException
 {
     // Object of a class that has both produce()
     // and consume() methods
     final PC pc = new PC();

     // Create producer thread
     Thread t1 = new Thread(new Runnable()
     {
         @Override
         public void run()
         {
             try
             {
                 while (true) {
                     pc.produce();   
                 }                 
             }
             catch(InterruptedException e)
             {
                 e.printStackTrace();
             }
         }
     });

     // Create consumer thread
     Thread t2 = new Thread(new Runnable()
     {
         @Override
         public void run()
         {
             try
             {
                 while (true) {
                     pc.consume();   
                 }
             }
             catch(InterruptedException e)
             {
                 e.printStackTrace();
             }
         }
     });

     // Start both threads
     t1.start();
     t2.start();

     // t1 finishes before t2
     t1.join();
     t2.join();
 }

 // This class has a list, producer (adds items to list
 // and consumber (removes items).
 public static class PC
 {
     // Create a list shared by producer and consumer
     // Size of list is 2.
     LinkedList<Integer> list = new LinkedList<>();
     int capacity = 12;
     int value = 0;

     // Function called by producer thread
     public void produce() throws InterruptedException
     {         
         synchronized (this)
         {
             // producer thread waits while list
             // is full
             while (list.size()==capacity)
                 wait();

             System.out.println("Producer produced-"
                                           + value);

             // to insert the jobs in the list
             list.add(value++);

             // notifies the consumer thread that
             // now it can start consuming
             notify();

             // makes the working of program easier
             // to  understand
             Thread.sleep(1000);
         }
     }

     // Function called by consumer thread
     public void consume() throws InterruptedException
     {
         synchronized (this)
         {
             // consumer thread waits while list
             // is empty
             while (list.size()==0)
                 wait();

             //to retrive the ifrst job in the list
             int val = list.removeFirst();


             System.out.println("Consumer consumed-"
                                             + val);

             // Wake up producer thread
             notify();

             // and sleep
             Thread.sleep(1000);
         }
     }
 }
}

Answer 1

Pay attention to two mothods: notify && Thread.sleep

Object.notify():

Wakes up a single thread that is waiting on this object's monitor. If any threads are waiting on this object, one of them is chosen to be awakened. The choice is arbitrary and occurs at the discretion of the implementation. A thread waits on an object's monitor by calling one of the wait methods.
The awakened thread will not be able to proceed until the current thread relinquishes the lock on this object. The awakened thread will compete in the usual manner with any other threads that might be actively competing to synchronize on this object; for example, the awakened thread enjoys no reliable privilege or disadvantage in being the next thread to lock this object.

Thread.sleep():

Causes the currently executing thread to sleep (temporarily cease execution) for the specified number of milliseconds plus the specified number of nanoseconds, subject to the precision and accuracy of system timers and schedulers. The thread does not lose ownership of any monitors.

OK. Now you know that notify will just wake up a thread which also monitor this object, but the awakened thread will compete to synchronize on this object. If your producer notify the consumer and release the lock, and then the producer and consumer is standing on the same point to compete. And the Thread.sleep does not do the work you want , it will not release the lock when it sleep as the doc said. So this might happen.

In conclusion, Thread.sleep is not very good with synchronize. and even though you remove this, the first output will happen because of the mechanism of notify.

@Andrew S's answer will work.

Answer 2

From the API: The awakened thread will compete in the usual manner with any other threads that might be actively competing to synchronize on this object; for example, the awakened thread enjoys no reliable privilege or disadvantage in being the next thread to lock this object.

Move sleep() outside the synchronized block to give the other thread an advantage to acquire the lock.

Answer 3

It is not necessarily the case that the first thread to make a call for a currently taken lock (let's call it Thread A) will aquire the lock as soon as the lock's current owner thread will relinquish it, if other threads have also made calls for the lock since Thread A tried to acquire it. There is no ordered "queue". See here and here. So, judging by the output of the program, it seems as if after the producer releases the lock, there might be not enough time for the consumer to acquire the lock before the while loop in the producer thread is repeated and the producer thread makes another call for the lock (as the other answers have pointed out, Thread.sleep() does not cause the sleeping thread to relinquish the lock), and if the consumer is unlucky, the producer will re-acquire the lock, even though the consumer was there first.

However, there seems to be another misunderstanding. The producer thread will never "wait" on the PC until the list contains 12 elements, so the consumer thread is only guaranteed to be granted the lock when the producer has produced at least 12 elements (which, incidentally, is what happens when I run the program – the consumer never gets a chance until the producer thread calls wait() on the PC, but then, it consumes the entire list). This also means that, if it happens to be the consumer's turn and the list contains less than 12 elements, the producer thread will not be notified because it is not waiting to be notified, but only blocked and already, let's say "anticipating" or "expecting" the lock on the PC (see also here on the difference between "waiting" and "blocked"). So even if you put the two Thread.sleep() invocations outside the synchronization blocks, thereby giving the consumer thread (hopefully, you shouldn't rely on this) enough time to acquire the lock, the call notify() from the consumer thread will have no effect because the producer thread will never be in a waiting state.

To really ensure that both threads modify the PC alternately, you would have to make the producer thread wait only if the list size is greater than zero, as opposed to if the list contains 12 (or however many) elements.

Answer 4

Just adding the appropriate condition will do the work.

import java.util.LinkedList;
import java.util.Queue;

class Producer extends Thread {

    public Queue<Integer> producerQueue;
    public int size;
    public int count = 0;

    Producer(Queue<Integer> queue, int size) {
        producerQueue = queue;
        this.size = size;
    }

    public void produce() throws InterruptedException {
        synchronized (producerQueue) {
            while (producerQueue.size() > 0) {
                producerQueue.wait();
            }
            System.out.println("Produced : " + count);
            producerQueue.add(count++);
            producerQueue.notify();
            Thread.sleep(100);
        }
    }

    public void run() {
        try {
            while (true) produce();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}


class Consumer extends Thread {
    public Queue<Integer> consumerQueue;
    public int size;

    Consumer(Queue<Integer> queue, int size) {
        consumerQueue = queue;
        this.size = size;
    }

    public void consume() throws InterruptedException {
        synchronized (consumerQueue) {
            while (consumerQueue.size() == 0) {
                consumerQueue.wait();
                Thread.sleep(100);
            }
            System.out.println("Consumed : " + consumerQueue.poll());
            consumerQueue.notify();
        }
    }

    public void run() {
        try {
            while (true) consume();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

}


public class Test {

    public static void main(String[] args) {
        Queue<Integer> commonQueue = new LinkedList<>();
        int size = 10;
        new Producer(commonQueue, size).start();
        new Consumer(commonQueue, size).start();
    }
}