Monitors in java

Monitors are an other mechanism of concurrent programming. It’s a higher level mechanism than semaphores and also more powerful. A monitor is an instance of a class that can be used safely by several threads. All the methods of a monitor are executed with mutual exclusion. So at most one thread can execute a method of the monitor at the same time. This mutual exclusion policy makes easier to work with monitor and to develop the method content of the monitor.

Monitors have an other feature, the possibility to make a thread waiting for a condition. During the wait time, the thread temporarily gives up its exclusive access and must reacquire it after the condition has been met. You can also signal one or more threads that a condition has been met.
There is several advantages on using monitors instead of a lower-level mechanisms :

• All the synchronization code is centralized in one location and the users of this code don’t need to know how it’s implemented.
• The code doesn’t depend on the number of processes, it works for as many processes as you want
• You don’t need to release something like a mutex, so you cannot forget to do it

When we must describe a monitor, we simple use the monitor keyword and describe the methods as common methods :

monitor SimpleMonitor {
    public method void testA(){
        //Some code
    }
 
    public method int testB(){
        return 1;
    }
}

To describe a condition variable, we use the cond keyword. A condition variable is a kind of queue of process who are waiting on the same condition. You have several operations available on a condition, the most important is to signal a process waiting to be awaken and to wait on a condition. There are some similarities between signal/wait operations and P and V of semaphores, but this is a little different. The signal operation does nothing if the queue is empty and the wait operation put always the thread in the waiting queue. The process queue is served in a first come, first served mode. When a thread wakes up after waiting on a condition, it must reacquire the lock before continuing in the code.
Before going further, we must have more informations about the signal operations. When writing monitors, you normally have the choice between several philosophies for the signaling operation :

1. Signal & Continue (SC) : The process who signal keep the mutual exclusion and the signaled will be awaken but need to acquire the mutual exclusion before going.
2. Signal & Wait (SW) : The signaler is blocked and must wait for mutual exclusion to continue and the signaled thread is directly awaken and can start continue its operations.
3. Signal & Urgent Wait (SU) : Like SW but the signaler thread has the guarantee than it would go just after the signaled thread
4. Signal & Exit (SX) : The signaler exits from the method directly after the signal and the signaled thread can start directly. This philosophy is not often used.

The available policies depends on the programming language, in Java, there is only one policy available, the SC one.
In Java there is no keyword to directly create a monitor. To implement a monitor, you must create a new class and use Lock and Condition classes. Lock is the interface is ReentrantLock is the main used implementation, this is the one that we’ll learn to use in the current post. To create a ReentrantLock, you have two constructors, a default constructor and a constructor with a boolean argument indicating if the lock is fair or not. A fair lock indicates that the threads will acquire the locks in the order they ask for. Fairness is a little heavier than default locking strategies, so use it only if you need it. To acquire the lock, you just have to use the method lock and unlock to release it.
The explicit locks have the same memory semantics than the synchronized blocks. So the visibility of the changes is guarantee when you use lock()/unlock() blocks.
So to implement, the monitor example we’ve seen before, we just need to create a class and use the lock to make the mutual exclusion :

public class SimpleMonitor {
    private final Lock lock = new ReentrantLock();
 
    public void testA() {
        lock.lock();
 
        try {
            //Some code
        } finally {
            lock.unlock();
        }
    }
 
    public int testB() {
        lock.lock();
 
        try {
            return 1;
        } finally {
            lock.unlock();
        }
    }
}

The person who’ve already read the other parts of this post set will say that it will be easier to use the synchronized keyword on the two methods. But with synchronized, we will not have the condition variables. If you don’t need condition variables but only locking, it will be easier to use the synchronized blocks instead of Locks.

You can create conditions using the newCondition method on the lock. A condition is a variable of type Condition. You can make the current thread wait on the condition using the await method (and its variant with timeout) and you can signal threads using signal and signalAll methods. The signalAll methods wakes up all the threads waiting on the condition variable.
Let’s try with a simple common example : A bounded buffer. It’s a cyclic buffer with a certain capacity with a start and an end.

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
 
public class BoundedBuffer {
    private final String[] buffer;
    private final int capacity;
 
    private int front;
    private int rear;
    private int count;
 
    private final Lock lock = new ReentrantLock();
 
    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();
 
    public BoundedBuffer(int capacity) {
        super();
 
        this.capacity = capacity;
 
        buffer = new String[capacity];
    }
 
    public void deposit(String data) throws InterruptedException {
        lock.lock();
 
        try {
            while (count == capacity) {
                notFull.await();
            }
 
            buffer[rear] = data;
            rear = (rear + 1) % capacity;
            count++;
 
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }
 
    public String fetch() throws InterruptedException {
        lock.lock();
 
        try {
            while (count == 0) {
                notEmpty.await();
            }
 
            String result = buffer[front];
            front = (front + 1) % capacity;
            count--;
 
            notFull.signal();
 
            return result;
        } finally {
            lock.unlock();
        }
    }
}

So some explications :

1. The two methods are protected with the lock to ensure mutual exclusion
2. Then we use two conditions variables. One to wait for the buffer to be not empty and an other one to wait for the buffer to be not full.
3. You can see that I have wrapped the await operation on a while loop. This is to avoid signal stealers problem that can occurs when using Signal & Continue

And that BoundedBuffer can be easily used with several threads with no problems.
As you can see, you can use monitors to solve a lot of concurrent programming problems and this mechanism is really powerful and performing.
I hope you find this post useful.

Atomic variables

When a data (typically a variable) can be accessed by several threads, you must synchronize the access to the data to ensure visibility and correctness. We discussed about atomic operations in java earlier.
By example, if you have a simple counter (yes, once again) :

public class Counter {

private int value;
 
    public int getValue(){
        return value;
    }
 
    public int getNextValue(){
        return value++;
    }
 
    public int getPreviousValue(){
        return value--;
    }
}

This class works really well in single-threaded environment, but don’t work at all when several threads access the same Counter instance. If you don’t know why, read this post about synchronization. You can solve the problem using synchronized at method level :

public class SynchronizedCounter {
    private int value;
 
    public synchronized int getValue(){
        return value;
    }
 
    public synchronized int getNextValue(){
        return value++;
    }
 
    public synchronized int getPreviousValue(){
        return value--;
    }
}

This class now works well. But locking is not a lightweight mechanism and have several disadvantages. When several threads try to acquire the same lock, one or more threads will be suspended and they will be resumed later. When the critical section is little, the overhead is really heavy especially when the lock is often acquired and there is a lot of contention. Another disadvantage is that the other threads waiting of the lock cannot do something else during waiting and if the thread who has the lock is delayed (due to a page fault or the end of the time quanta by example), the others threads cannot take their turn.
So how to do to avoid this disadvantages ? We must use non-blocking algorithms. This algorithms don’t use blocking mechanisms and by that fact are more scalable and performing. These algorithms use low-level machine instructions which are atomic to ensure the atomicity of higher-level operations. While locking is a pessimistic approach, we can also use optimistic technique to develop algorithms. This time, we’ll detect collisions between threads in which case, the operation fails and we do something else (often retrying the same operation).
The actual processors provide several instructions that simplify greatly the implementation of these non-blocking algorithms, the most-used operation today is the compare-and-swap operation (CAS). This operation takes three parameters, the memory address, the expected current value and the new value. It atomically update the value at the given memory address if the current value is the expected, otherwise it do nothing. In both cases, the operation return the value at the address after the operation execution. So when several threads try to execute the CAS operation, one thread wins and the others do nothing. So the caller can choose to retry or to do something else. We often use this operation to implement another operation, the compare-and-set. This method makes exactly the same things as CAS but return a boolean indicating if the operation succeeded or not.
Before Java 5.0, this operation was not available directly to developer, but in Java 5.0 several atomic variables (for int, long, boolean and reference values) were added. The int and long versions also supports numeric operations. The JVM compiles these classes with the better operations provided by the hardware machine, CAS or a Java implementation of the operation using a lock. Here are the classes :

• AtomicInteger
• AtomicLong
• AtomicBoolean
• AtomicReference

All these classes supports compare-and-set (via the compareAndSet() method) and other operations (get(), set() and getAndSet()). The setters operations are implemented using compareAndSet. These classes supports multi-threaded access and have a better scalability than synchronizing all the operations.
Here is how we can rewrite our counter using an AtomicInteger :

public class AtomicCounter {
    private final AtomicInteger value = new AtomicInteger(0);
 
    public int getValue(){
        return value.get();
    }
 
    public int getNextValue(){
        return value.incrementAndGet();
    }
 
    public int getPreviousValue(){
        return value.decrementAndGet();
    }
}

The incrementAndGet() and decrementAndGet() methods are two of the numeric operations provided by the AtomicLong and AtomicInteger classes. You also have getAndDecrement(), getAndIncrement(), getAndAdd(int i) and addAndGet().
This version is faster than the synchronized one and is also thread safe.
If you only have the compareAndSet(), here is how we can implement increment() method using it :
public void increment(AtomicInteger integer){
    while(true){
         int current = integer.get();
         int next = current + 1;
         if(integer.compareAndSet(current, next)){
              return;
    }
  }
}
This seems to be complicated, but this is the cost of non-blocking algorithms. When we detect collision, we retry until the operation succeeded. This is the common schema for non-blocking algorithms.
Here is a thread-safe Stack implemented using AtomicReference :

public class Stack {
    private final AtomicReference<Element> head = new AtomicReference<Element>(null);
 
    public void push(String value){
        Element newElement = new Element(value);
 
        while(true){
            Element oldHead = head.get();
            newElement.next = oldHead;
 
            //Trying to set the new element as the head
            if(head.compareAndSet(oldHead, newElement)){
                return;
            }
        }
    }
 
    public String pop(){
        while(true){
            Element oldHead = head.get();
 
            //The stack is empty
            if(oldHead == null){
                return null;
            }
 
            Element newHead = oldHead.next;
 
            //Trying to set the new element as the head
            if(head.compareAndSet(oldHead, newHead)){
                return oldHead.value;
            }
        }
    }
 
    private static final class Element {
        private final String value;
        private Element next;
 
        private Element(String value) {
            this.value = value;
        }
    }
}

It’s really more complicated than using synchronized on the two methods but also more performing if there is contention (and often even if there is no contention).
So this ends this post. To conclude, atomic variables classes are a really good way to implement non-blocking algorithms and moreover are also a very good alternative to volatile variables, because they can provide atomicity and visibility.

Synchronizing with synchronized keyword

Synchronization is a way to make some code thread safe. A code that can be accessed by multiple threads must be made thread safe. Thread Safe describe some code that can be called from multiple threads without corrupting the state of the object or simply doing the thing the code must do in right order.

public class Counter {
    private int value = 0;    
 
    public int getNextValue(){
        return value++;
    }
}

It’s really simple and works well with one thread, but absolutely not with multiple threads. An incrementation like this is not a simple action, but three actions :

Read the current value of “value”
Add one to the current value
Write that new value to “value”
Normally, if you have two threads invoking the getNextValue(), you can think that the first will get 1 and the next will get 2, but it is possible that the two threads get the value 1. Imagine this situation :

Thread 1 : read the value, get 0, add 1, so value = 1
Thread 2 : read the value, get 0, add 1, so value = 1
Thread 1 : write 1 to the field value and return 1
Thread 2 : write 1 to the field value and return 1

These situations come from what we call interleaving. Interleaving describe the possible situations of several threads executing some statements. Only for three operations and two threads, there is a lot of possible interleavings.

So we must made the operations atomic to works with multiple threads. In Java, the first way to make that is to use a lock. All Java objects contains an intrinsic locks, we’ll use that lock to make methods or statement atomic. When a thread has a lock, no other thread can acquire it and must wait for the first thread to release the lock. To acquire the lock, you have to use the synchronized keyword to automatically acquire and release a lock for a code. You can add the synchronized keyword to a method to acquire the lock before invoking the method and release it after the method execution. You can refactor the getNextValue() method using the synchronized keyword :

public class Counter {
    private int value = 0;    
 
    public synchronized int getNextValue(){
        return value++;
    }
}

With that, you have the guarantee that only thread can execute the method at the same time. The used lock is the intrinsic lock of the instance. If the method is static, the used lock is the Class object of Example. If you have two methods with the synchronized keyword, only one method of the two will be executed at the same time because the same lock is used for the two methods. You can also write it using a synchronized block :

public class Counter {
    private int value = 0;
 
    public int getNextValue() {
        synchronized (this) {
            return value++;
        }
    }
}

This is exactly the same as using the synchronized keyword on the method signature. Using synchronized blocks, you can choose the lock to block on. By example, if you don’t want to use the intrinsic lock of the current object but an other object, you can use an other object just as a lock :

public class Counter {
    private int value = 0;
 
    private final Object lock = new Object();
 
    public int getNextValue() {
        synchronized (lock) {
            return value++;
        }
    }
}

The result is the same but has one difference, the lock is internal to the object so no other code can use the lock. With complex classes, it not rare to use several locks to provide thread safety on the class.

There is an other issue with multiple threads : the visibility of the variables. This seems when a change made by a thread is visible by an other thread. For performance improvements, the Java compiler and virtual machines can made some improvements using registers and cache. By default, you have no guarantee that a change made by a thread is visible to an other thread. To make a change visible to an other thread, you must use synchronized blocks to ensure visibility of the change. You must use synchronized blocks for the read and for the write of the shared values. You must make that for every read/write of a value shared between multiple threads.

You can also use the volatile keyword on the field to ensure the visibility of read/write between multiple threads. The volatile keyword ensure only visibility, not atomicity. The synchronized blocks ensure visibility and atomicity. So you can use the volatile keyword on fields that doesn’t need atomicity (if you make only read and write to the field without depending on the current value of the field by example).

You can also note that this simple example can be solved using AtomicInteger, but that will be covered later in an other part of the posts.

Pay attention that trying to solve thread safety on a problem can add new issues of deadlock. By example, if thread A owns the lock 1 and are waiting for the lock 2 and if lock 2 is acquired by thread B who waits on lock 1, there is a deadlock. Your program is dead. So you have to pay great attention to the locks.

There is several rules that we must keep in mind when using locks :

Every mutable fields shared between multiple threads must be guarded with a lock or made volatile, if you only need visibility
Synchronize only the operations that must synchronized, this improve the performances. But don’t synchronize too few operations. Try to keep the lock only for short operations.
Always know which locks are acquired and when there are acquired and by which thread
An immutable object is always thread safe
Here we are, I hope that this post helps you to understand thread safety and how to achieve it using intrinsic locks. In the next posts, we’ll see another synchronization methods.

Difference between synchronized and volatile

The main differences between synchronized and volatile are:

• a primitive variable may be declared volatile whereas synchronized cannot be applied on the primitive types, but on some object or method or class.
• Lock - Volatile deals with visibility, so if one thread modifies some variable, it will be known to other thread, so unlike a synchronized block we will never hold on to any lock; This is the big difference as synchronized offers mutual exclusion while volatile don't.
• Attempting to synchronize on a null object will throw a NullPointerException, while  this is fine with volatile.
• As synchronized offers mutual exclusion, it offers atomicity as well. But volatile doesn't mean atomic. (click on the link to see why)

Thanks

How to synchronize a static variable of a class ?

There are some ways(3 to my knowledge, but may be more), by which a static variable can be synchronized in java.

1) Use a synchronized static method. This synchronizes on the class object.

public class Counter {
    private static int count = 0;

    public static synchronized void incrementCount() {
        count++;
    }
} 

2) Explicitly synchronize on the class object, using synchronize on ClassName.class

public class Counter {
    private static int count = 0;

    public void incrementCount() {
        synchronize (Test.class) {
            count++;
        }
    }
} 

3) Synchronize on some other static object.

public class Counter {
    private static int count = 0;
    private static final Object countLockHelper = new Object();

    public void incrementCount() {
        synchronize (countLockHelper) {
            count++;
        }
    }
} 

Method 3 is best in many cases because the lock object is not exposed outside of your class. So if you create instance of these class, they will be synchronized on the same static object.

But if you just using some basic type like integer here in case of counter, consider using an AtomicInteger or another suitable class from the java.util.concurrent.atomic package:

public class Counter {

    private final static AtomicInteger count = new AtomicInteger(0); 

    public void incrementCount() {  
        count.incrementAndGet();
    }  
}

Class level lock vs instance level lock

A class level lock is the lock which makes all object of a class to wait until the corresponding lock is not released.
e.g

Class A{
   static synchronized void foo(){}
}

Here the method foo is synchronized and hence all the threads on all the objects of the class will wait until the object currently running the foo method completes its execution.

Similarly an instance level lock makes all the threads started using the instance of the class to wait until the lock is not released.
e.g.

Class A{
    //static is missing
    synchronized void bar(){}
}

Here all the threads started from the object which is currently executing the bar method will wait until the current threads completes its execution. Note that other threads of other objects can execute the bar method while another object's thread is executing the bar method.

Get Synchronized Map

By default map is not synchronized in java. To get this we can do following

Getting Synchronized map from hashmap :

HashMap hashMap = new HashMap();
Map map = Collections.synchronizedMap(hashMap);


From TreeMap :

TreeMap treeMap = new TreeMap();
Map map = Collections.synchronizedMap(treeMap);


Getting Synchronized set

By default set is not synchronized. If multiple threads access a set concurrently, and at least one of the threads modifies the set, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the set. If no such object exists, the set should be "wrapped" using the Collections.synchronizedSet method like below :

Hashset :

HashSet hashSet = new HashSet();
Set set = Collections.synchronizedSet(hashSet);

TreeSet :

TreeSet treeSet = new TreeSet(); 
Set set = Collections.synchronizedSet(treeSet);