WAIT() NOTIFY() SHORTCOMING: SINGLE WAIT QUEUE

There is an inherent drawback of wait(), notify() methods in Java.

As we are aware every Object in Java is associated with a Entry Queue and a Wait Queue. When a thread reaches a synchronized block, it will wait on the Entry Queue of the Object if any other Thread already has the lock. Once it acquires the lock, does its processing, calles Object.wait(), it waits on Wait Queue of the Object. When some other Thread calls Object.notify(), one of the threads waiting on the Wait Queue is moved to the Entry queue of the Object, where it fights for the lock on the Object (with all other Threads waiting at the Entry Queue).

The shortcoming is that wait is not a conditional wait. Every object has just one wait queue.

So if a Object.notify() is called, of all threads waiting on wait queue, any one thread at random is moved to the entry queue. There is no direct way to notify a particular Thread. What we do is a workaround. Instead of Object.notify(), we call Object.notifyAll(), so as all threads are moved from Object’s wait queue to entry queue. Object.wait() call is made in a while loop each checking on a particular condition. So we attach each Object.wait() with a particular condition, as below.

1 2 3 4 5 6 7 8 9 10 11 12 13

//Thread1 synchronized(object) {     while(!condition1) {         object.wait();     } } //Thread 2 synchronized(object) {     while(!condition2) {         object.wait();     } }

When some other Thread sets condition2 = true (while condition1 is still false) and calls object.nofityAll(), both the above Threads which are waiting on the wait queue of the object, are moved to entry queue of the object. Since wait() is in spinning while loop, so Thread1 (if it gets the lock) again calls object.wait() while the Thread2 (if it gets the lock) comes out of the loop starts the processing.

The drawback you see, is unnecessary processing (looping once and checking for condition) in Thread1 and also unnecessary moving of Thread1 from wait queue of Object to entry queue to back. Thread1 wanted to awaken only ifcondition1 == true and Object.notify() is called (not just @ Object.notify()). What would have been nice if there was provision for Conditional Monitor Objects with each having its own wait queue. Something like,

1 2 3 4 5 6 7 8 9

//Thread 1 synchronized(object) {     object.wait(condition1); } //Thread 2 synchronized(object) {     object.wait(condition2); }

Here wait is now waiting on a condition. I have seen some good implementations which are provided  for above problem. One being here.

THREAD SLEEP/WAIT

Oxford Dictionary defines wait and sleep as below:
wait: delay action until (someone) arrives or is ready.
sleep: a condition of body and mind which typically recurs for several hours every night, in which the nervous system is relatively inactive and consciousness practically suspended

Wait is to not act till someone arrives. Sleep is to not act for a specified time. It’s amazing how much dictionary meaning of words can tell you about their technical aspects.

Wait and Sleep are confusing terms. A wife falls asleep waiting for the husband to be back from office. Isn’t sleep just a wait to wake up again. Aren’t they interchangeable terms? Which holds lock on the monitors? Which consumes CPU cycles? Lets’s explore.

One important concept to be understood before moving forward is Context Switching: When multiple processes share a single CPU, they fight for the CPU time. It is via context switching that each of them gets some CPU time slice. In very basic terms, one process should be switched out of CPU so that another process can run. Similar context switching can be understood at the JVM level for a single process which has many threads.

To begin with we need to define, the States of a Thread in Java.

1. RUNNABLE: Thread executing in JVM (might not execute in OS, as OS might make it wait for the processor, say)
2. WAITING: Waiting ad infinitum for some other thread to perform some action. If current Thread callsObject.wait(), it is WAITING for some other thread to call Object.notify().
3. BLOCKED: Waiting to get monitor lock
   • Either waiting to enter synchronized block, or
   • In Waiting state of Current Thread, if some other thread calls Object.notify(), the Current Thread moves to BLOCKED state and fights for the monitor lock. If some other Thread gets the lock, current Thread goes back to WAITING state.)
4. TIMED_WAITING: 
   • Waiting for a specified time interval (Thread.sleep(TIMEOUT)) or
   • Waiting for some other Thread to call Object.notify() or for a specified time interval, whichever is shorter (Object.wait(TIMEOUT)).

What happens when Thread.sleep(TIMEOUT) is called? TIME-SYNCHRONIZATION

1. The running Thread is forcefully switched out (context switching) and put in TIMED_WAITING state for the specified interval.
2. As name suggests, it simply sleeps and require no CPU time-slice. Theoretically speaking, if this is the only process running and you put Sleep statements with substantial TIMEOUT, you will notice drop in CPU usage. Short bursts of continuous sleep statements, might increase CPU usage as Context Switching incurs its own cost.
3. Once the Sleep time is over, Thread is scheduled back to be executed. However there is no guarantee that  Context Switching will happen immediately. Depends upon the resources available. If a high priority work is going on, this Thread will not get CPU time instantaneously. If will be scheduled no doubt, but when it will be executed comes with no guarantee.
4. Sleep can be interrupted by Thread.interrupt(). This caused InterruptedException to be thrown. It is normally used to HALT the operations.
5. If sleep is called from a synchronized block (say). No other Thread can enter this block. Thread holds the ownership (lock) of the monitor object.
6. sleep is a static method. If we call diffThread.sleep from the current Thread, it wont halt diffThread. It is the current Thread which will sleep.

What happens when Object.wait() is called from inside the synchronized block? MULTI-THREAD SYNCHRONIZATION

1. The running Thread is switched out (context switching) and goes to the WAITING state .  In WAITING state, itrequires no CPU time-slice.
2. In Java every Object is associated with two queues, wait queue and entry queue. Post Object.wait() Thread waits on the wait queue of the object.
3. The Thread will hold no lock on the monitor object. Any other thread can enter the synchronized block.
4. It will remain in WAITING state until some other Thread which will synchronize on the same object, calls Object.notify()
5. Once Object.notify() is called, of all Threads that are WAITING on the same monitor object, one is awakened at random and is moved to BLOCKED state (Moved from waiting queue of object to entry queue of the object), where it tries to get the lock on monitor object. It has to fight with other Threads BLOCKED on the same Object. Once it gets the lock, it is scheduled to be executed by the CPU, again with no guarantees when.
6. If 10 Threads have called Object.wait() on the same object, Object.notifyAll(), awakens all 10 threads and move them in BLOCKED state where they fight with other BLOCKED Threads for the lock on the object  One of these 10 might get the lock (some other Thread which was BLOCKED to enter the  synchronized block, might just get the lock) and rest 9 go back to the WAITING state (in effect waiting Queue of the Object) till they get the next notify signal.
7. In BLOCKED state Thread incurs CPU cost as it tries to get the lock. JVM might try to get to acquire monitor lock multiple times before context switching it OR JVM might context switch it just after one try. It depends on Algorithm implemented at JVM level.