Jump to content

Basic Synchronization

75% developed
From Wikibooks, open books for an open world

Navigate Concurrent Programming topic: v  d  e )


In a multi-threaded environment, when more than one thread can access and modify a resource, the outcome could be unpredictable. For example, let's have a counter variable that is incremented by more than one thread.

Beware! Synchronization is an ambiguous term. It doesn't consist of making all threads executing the same code section at the same time. It is the opposite. It prevents any two threads from executing the same code section at the same time. It synchronizes the end of one processing with the beginning of a second processing.

Example Code section 1.1: Counter implementation
int counter = 0;
...
counter += 1;

The above code is built up by the following sub-operations:

  • Read ; read variable counter
  • Add ; add 1 to the value
  • Save ; save the new value to variable counter

Let's say that two threads need to execute that code, and if the initial value of the counter variable is zero, we expect after the operations the value to be 2.

Thread 1   Thread 2
         
Read 0   Read 0
         
Add 1   Add 1
         
Save 1   Save 1
         

In the above case Thread 1 operation is lost, because Thread 2 overwrites its value. We'd like Thread 2 to wait until Thread 1 finishes the operation. See below:

Thread 1   Thread 2
         
Read 0   blocked
         
Add 1   blocked
         
Save 1   unblocked
         
  Read 1
     
  Add 1
     
  Save 2
     
Critical Section
In the above example the code counter+=1 must be executed by one and only one thread at any given time. That is called critical section. During programming, in a multi-threading environment we have to identify all those pieces of code that belongs to a critical section, and make sure that only one thread can execute those codes at any given time. That is called synchronization.
Synchronizing threads
The thread access to a critical section code must be synchronized among the threads, that is to make sure that only one thread can execute it at any given time.
Object monitor
Each object has an Object monitor. Basically it is a semaphore, indicating if a critical section code is being executed by a thread or not. Before a critical section can be executed, the thread must obtain an Object monitor. Only one thread at a time can own that object's monitor.
A thread becomes the owner of the object's monitor in one of three ways
  • By executing a synchronized instance method of that object. See synchronized keyword.
  • By executing the body of a synchronized statement that synchronizes on the object. See synchronized keyword.
  • For objects of type Class, by executing a synchronized static method of that class.
The Object Monitor takes care of the synchronization, so why do we need the "wait() and notify() methods"?
For synchronization we don't really need them, however for certain situations it is nice to use them. A nice and considerate thread will use them. It can happen that during executing a critical section, the thread is stuck, cannot continue. It can be because it's waiting for an IO and other resources. In any case, the thread may need to wait a relatively long time. It would be selfish for the thread to hold on to the object monitor and blocking other threads to do their work. So the thread goes to a 'wait' state, by calling the wait() method on the object. It has to be the same object the thread obtained its object monitor from.
On the other hand though, a thread should call the wait() method only if there is at least one other thread out there who will call the notify() method when the resource is available, otherwise the thread will wait for ever, unless a time interval is specified as parameter.
Let's have an analogy. You go in a shop to buy some items. You line up at the counter, you obtain the attention of the sales-clerk - you get her "object-monitor". You ask for the item you want. One item needs to be brought in from a warehouse. It'll take more than five minutes, so you release the sales-clerk (give her back her "object-monitor") so she can serve other customers. You go into a wait state. Let's say there are five other customers already waiting. There is another sales-clerk, who brings in the items from the warehouse. As she does that, she gets the attention of the first sales-clerk, getting her object-monitor and notifies one or all waiting customer(s), so the waited customer(s) wake up and line up again to get the attention of the first sales-clerk.
Note the synchronization between the waiting customer and the sales-clerk who brings in the items. This is kind of producer-consumer synchronization.
Also note that there is only one object-monitor, belonging to the first sales-clerk. That object-monitor/the attention of clerk needs to be obtained first before a wait and a notify can happen.


final void wait() method
The current thread must own this object's monitor. The thread releases ownership of this monitor and waits until another thread notifies the threads waiting on this object's monitor to wake up either through a call to the notify method or to the notifyAll method. The thread then waits until it can re-obtain ownership of the monitor and resume execution.
final void wait(long time)
The same as wait, but the thread wakes after the specified duration of time passes, regardless of whether there was a notification or not.
final void notify()
This method should only be called by a thread that is the owner of this object's monitor. Wakes up a single thread that is waiting on this object's monitor. If many threads are waiting on this object's monitor, 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.
final void notifyAll()
Same as notify(), but it wakes up all threads that are waiting on this object's monitor.


What are the differences between the sleep() and wait() methods?
Thread.sleep(millis)
This is a static method of the Thread class. Causes the currently executing thread to sleep (temporarily cease execution) for the specified number of milliseconds. The thread does not lose ownership of any monitors. It means that if the thread has an object-monitor, all other threads that need that monitor are blocked. This method can be called regardless whether the thread has any monitor or not.
wait()
This method is inherited from the Object class. The thread must have obtained the object-monitor of that object first before calling the wait() method. The object monitor is released by the wait() method, so it does not block other waiting threads wanting this object-monitor.


Clipboard

To do:
Add some exercises like the ones in Variables