AB.CDE Course Website

Java Synchronization

Java Object Mutex Lock

The Java programming language provides two basic synchronization idioms: synchronized methods and synchronized statements.

Each Java object has an associated binary lock:

  • Lock is acquired by invoking a synchronized method/block
  • Lock is released by exiting a synchronized method/block

With this lock, mutex is guaranteed for this object’s method; at most only one thread can be inside it at any time.

Threads waiting to acquire the object lock are waiting in the entry set, status is still blocked and not runnable until it acquires the lock. Once the thread acquires the lock, it becomes runnable.

The wait set is NOT equal to the entry set – it contains threads that are waiting for a certain condition (NOT WAITING FOR THE LOCK).

These sets (entry and waiting) are per object, meaning each object instance only has ONE lock.

  • Each object can have many synchronized methods.
  • These methods share one lock.

Synchronised Method (Anonymous)

Below is an how you can declare a synchronized method in a class. The mutex lock is itself (this). The fact that we don’t use other objects as a lock is the reason why we call this the anonymous synchronisation object.

public synchronized returnType methodName(args)
{
       // Critical section here
       // ...
}

Synchronised Statement using Named Object

And below is a synchronized block based on a specific named object (not this instance).

Object mutexLock = new Object();
public returnType methodName(args)
{
   synchronized(mutexLock)
   {
       // Critical section here
       // ...
   }

   // Remainder section
}

You can also do a synchronized(this) if you’d like to use a synchronised statement anonymously.

Java Static Locks

It is also possible to declare static methods as synchronized. This is because, along with the locks that are associated with object instances, there is a single class lock associated with each class.

The class lock has its own queue sets. Thus, for a given class, there can be several object locks, one per object instance. However, there is only one (static) class lock.

Java Condition Synchronization

Similarly, Java allows for condition synchronization using wait() and notify() method, as well as its own condition variables.

Example: suppose a few threads are trying to execute the same method as follows,

public synchronized void doWork(int id)
{
   while (turn != id) // turn is a shared variable
   {
       try
       {
           wait();
       }
       catch (InterruptedException e)
       {
       }
   }
   // CRITICAL SECTION
   // ...
   turn = (turn + 1) % N;
   notify();
}

Suppose N threads are running this doWork function concurrently with argument id varying between 0 to N-1, i.e: 0 for thread 0, 1 for thread 1, and so on.

In this example, the condition in question is that ONLY thread whose id == turn can execute the CS.

When calling wait(), the lock for mutual exclusion must be held by the caller (same as the conditional variable in the section above). That’s why the wait to the conditional variable is made inside a synchronized method. If not, disaster might happen, for example the following execution sequence:

  • At t=0,
    • Thread Y check that turn != id_y, and then Y is suspended.
  • At t=n,
    • Thread X resumes and increments the turn. This causes turn == id_y.
    • Suppose X then calls notify(), and then X is suspended
  • At t=n+m,
    • Thread Y resumes execution and enters wait().
  • However at this time, the value of turn is ALREADY == id_y.

We can say that thread Y misses the notify() from X and might wait() forever. We need to make sure that BETWEEN the check of turn and the call of wait(), no OTHER THREAD can change the value of turn.

Since we MUST invoke wait() while holding a lock, it is important for wait() to release the object lock eventually (when the thread is waiting). If you call another method to sleep such as Thread.yield() instead of wait(), then it will not release the lock while waiting. This is dangerous as it will result in indefinite waiting or deadlock.

Upon return from wait(), the Java thread would have re-acquired the mutex lock automatically.

In summary,

  • When a thread calls the wait() method, the following happens:

    • The thread releases the lock for the object.
    • The state of the thread is set to blocked.
    • The thread is placed in the wait set for the object.

  • When it calls notify():

    • Picks an arbitrary thread T from the list of threads in the wait set
    • Moves T from the wait set to the entry set
    • The state of T will be changed from blocked to runnable, so it can be scheduled to reacquire the mutex lock

NotifyAll

However we are not completely free of another potential problem yet: notify() might not wake up the correct thread whose id == turn, and recall that turn is a shared variable.

We can solve the problem using another method notifyAll(): wakes up all threads in the wait set.

Wait in a Loop

It is important to put the waiting of a condition variable in a while loop due to the possibility of:

  1. Spurious wakeup: a thread might get woken up even though no thread signalled the condition (POSIX does this for performance reasons)
  2. Extraneous wakeup: you woke up the correct amount of threads but some hasn’t been scheduled yet, so some other threads do the job first. For example:
    • There are two jobs in a queue, and there’s two threads: thread A and B that got woken up.
    • Thread A gets scheduled, and finishes the first job. It then finds the second job in the queue, and finishes it as well.
    • Thread B finally gets scheduled and, upon finding the queue empty, crashes.

Reentrant Lock

A lock is re-entrant if it is safe to be acquired again by a caller that’s already holding the lock. You can create a ReentrantLock() object explicitly to allow reentrancy in your critical section.

Java synchronized methods and synchronized blocks with intrinsic lock (recall: every object has an intrinsic lock associated with it) are reentrant.

For example, a thread can safely recurse on blocks guarded by reentrant locks (sync methods, sync statement)

// Method 1
public synchronized void foo(int x) {
   // some condition ...
   foo(x-1); // recurse does not cause error
}

// Method 2
public void foo(int x) {
   synchronized(this) { // note that 'this' is the lock. Otherwise, non-reentrant
	// some condition ...
       foo(x-1); // recurse does not cause error
   }
}

// Method 3
Object obj1 = new Object();
synchronized(obj1){
   System.out.println("Try out object ack 1");
   synchronized(obj1){ // intrinsic lock is reentrant
       System.out.println("Try out obj ack 2"); // will be printed
   }
}

Reentrance Lockout

If you use a non-reentrant lock and recurse OR try to acquire the lock again, you will suffer from reentrance lockout. We demonstrate it with the custom lock below:

public class CustomLock{

 private boolean isLocked = false;

 public synchronized void lock() throws InterruptedException{
   while(isLocked){
     wait();
   }
   isLocked = true;
 }

 public synchronized void unlock(){
   isLocked = false;
   notify();
 }

}

And the usage:

CustomLock lock = new CustomLock()

// Thread 1 code
public void doSomething(int argument){
   lock.lock();
   // recurse
   doSomething(argument-1);
   lock.unlock();
}

A thread that calls lock() for the first time will succeed, but the second call to lock() will be blocked since the variable isLocked == true.

Releasing Locks

One final point to note is that some implementations require you to release the lock N times after acquiring it N times. You need to carefully read the documentation to see if the locks are auto released or if you need to explicitly release a lock N times to allow others to successfully acquire it again.

Fine-Grained Condition Synchronisation

If we want to perform fine grained condition synchronization, we can use Java’s named conditional variables and a reentrant lock. Named conditional variables are created explicitly by first creating a ReentrantLock(). The template is as follows:

Lock lock = new ReentrantLock();
Condition lockCondition = lock.newCondition(); // call this multiple times if you have more than 1 condition

// Step 1: LOCK
lock.lock(); // remember, need to lock before calling await()

// Step 2a: WAIT
// To wait for specific condition:
lockCondition.await();

// OR Step 2b: SIGNAL
// To signal specific thread waiting for this condition:
lockCondition.signal();
// ...
// ...

// Step 3: UNLOCK
lock.unlock();

At first, we associate a conditional variable with a lock: lock.newCondition(). This forces us to always hold a lock when a condition is being signaled or waited for.

We can modify the example above of N threads which can only progress if id == turn to use conditional variables as follows:

// Create arrays of condition
Lock lock = new ReentrantLock();
ArrayList<Condition> condVars = new ArrayList<Condition>();
for(int i = 0; i<N; i++) condVars.add(lock.newCondition()); // create N conditions, one for each Thread

The Thread function is changed to incorporate a wait to each condVars[id]:

// the function
public void doWork(int id)
{
   lock.lock();
   while (turn != id)
   {
       try
       {
             condVars[id].await();
	}
       catch (InterruptedException e){}
   }
   // CS
   // assume there's some work to be done here...
   turn = (turn + 1) % 5;
   condVars[turn].signal();
   lock.unlock();
}

Summary

There are a few solutions to the CS problem. The CS problem can be divided into two types:

  • Mutual exclusion
  • Condition synchronization

There are also a few solutions listed below.

Software mutex algorithms provide mutex via busy-wait.

Hardware synchronisation methods provide mutex via atomic instructions.

Other software spinlocks and mutex algorithms can be derived using these special atomic assembly instructions

Semaphores provide mutex using binary semaphores.

Basic condition variables provide condition synchronization and are used along with a mutex lock.

Java anonymous default synchronization object provides mutex using reentrant binary lock (this), and provides condition synchronisation using wait() and notifyAll() or notify()

Java named synchronization object provides mutex using named reentrant binary lock (ReentrantLock()) and provides condition sync using condition variables and await()/signal()

It is entirely up to you to figure out which one to use for your application.

Search