Solution Hacker

Get yourself familiar with concurrency programming

When I interview my candidates, I like to ask questions related to multi-threading. I found out that it is a good topic to differentiate out a hardcore programmer from application-oriented programmer. I am not saying I am looking for someone who could write the concurrency library as efficient as the one created by Doug Lea. In fact, I am looking for candidates who has solid understanding of this topic. However, I found out that most candidates have little knowledge in this area apart from the meaning of “synchronized” keyword in Java syntax. Therefore I decide to write a series of articles to cover some areas of multi-threading that I feel important to understand. Of course, I would start from the basic first.

Introduction of Synchronization

Synchronization is a way to lock an object, so no 2 threads possibly running on the same code at the same time.

public class SynchronizedCounter {
    private double c = 0;

    public synchronized void increment() {
        c++;
    }

    public synchronized void decrement() {
        c--;
    }

    public synchronized int value() {
        return c;
    }

    public void method2() {
        ...
    }
}

If count is an instance of SynchronizedCounter, then making these methods synchronized has two effects:

• Mutual Exclusion – It is not possible for two invocations of synchronized methods on the same object to interleave. When one thread is executing a synchronized method for an object, all other threads that invoke synchronized methods for the same object block (suspend execution) until the first thread is done with the object. Remember this rule doesn’t apply to non-synchronized methods. And the thread holds the lock of the object can reenter its synchronized methods (ie. reentrance).
• Memory-Visibility – When a synchronized method exits, it automatically establishes a happens-before relationship with any subsequent invocation of a synchronized method for the same object. This guarantees that changes to the state of the object are visible to all threads. Most of the interviewers miss this one. In database, it is like the concept of “commit”. If you don’t commit your changes, others could not see your changes.

All in all, synchronized methods enable a simple strategy for preventing thread interference and memory consistency errors. Interference happens when two operations, running in different threads, but acting on the same data, interleave. This means that the two operations consist of multiple steps, and the sequences of steps overlap. This will result in unpredictable data lost (hard to fix). Memory consistency error occurs when complier and processor reorder statements and uses the cached value for better performance

Problem of Synchronization

Synchronization will serialize the method calls from different threads. At any given time, only one thread can execute the synchronized method and the other threads need to wait until the object lock releases. This will dramatically diminish the liveness of your application. To minimize the impact, you should:

1. Reduce lock duration – Synchronized statements are useful for improving concurrency with fine-grained synchronization
2. Reduce lock scope – Mutex variable in the synchronized lock may help you to avoid locking the whole object. In Java 5 concurrency library, there is class called ReentrantLock that provides the same features as synchronized with better performance and flexibility. Here is what is stated in “Java Concurrency in Practice”:

Why create a new locking mechanism (ie. ReentrantLock) that is so similar to intrinsic locking (ie. synchronized)? Intrinsic locking works fine in most situations but has some functional limitations. It is not possible to interrupt a thread waiting to acquire a lock, or to attempt to acquire a lock without being willing to wait for it forever. Intrinsic locks also must be released in the same block of code in which they are acquired; this simplifies coding and interacts nicely with exception handling, but makes non-block structured locking disciplines impossible. None of these are reasons to abandon synchronized, but in some cases a more flexible locking mechanism offers better liveness or performance.

So far so good.? Great! lets me ask you 3 questions:

1. Question 1: In the example above, if thread A is executing a synchronized method “increment”, can another thread execute method2? Yes. Because method2 is not synchronized
2. Question 2: If thread A is in the synchronized method xyz , can it invoke another synchronized abc? Yes. The object lock is reentrant.
3. Question 3: If I want to make the above class thread-safe without using synchronized object lock, are there any other alternatives? Yes.
   • ReentrantLock – http://www.ibm.com/developerworks/java/library/j-jtp10264/
   • Atomic variable – http://www.ibm.com/developerworks/java/library/j-jtp11234/
4. Question 4: How about declare the variable volatile?
   • Managing Volatility by Brian Goetz
   • Compare Atomic variable, ReentrantLock and Volatile variable.
   • Use int, byte instead of long or double because updating int or byte is an atomic action. Atomic actions cannot be interleaved, so they can be used without fear of thread interference. However, this does not eliminate all need to synchronize atomic actions, because memory consistency errors are still possible (for example, thread A updated an variable atomically but it hasn’t flushed and sync up the main memory, so it is not visible to other threads). Unless the fields in question are declared [code]]czoxMDpcInZvbGF0aWxlLCBcIjt7WyYqJl19[[/code] the JMM does not require the underlying platform to provide cache coherency or sequential consistency across processors, so it is possible, on some platforms, to read stale data in the absence of synchronization. Look at here for better explanation. However, volatile can only guarantee atomicity and memory consistency for single variable. If you want to guarantee that for compound operations, you need to use synchronized block.(or the new java.util.concurrent classes). It is worth pointing out that increment (i.e. ++) and similar operations are not atomic in Java. So incrementing a volatile variable [code]]czoxMzpcInZvbGF0aWxlVmFyKytcIjt7WyYqJl19[[/code] is NOT thread-safe. If you need thread-safe semantics i.e. no possibility of multiple threads corrupting the variable value by having the updates unexpectedly interfere with each other, then you need to use a synchronized block to increment a variable, e.g. [code]]czoyNzpcInN5bmNocm9uaXplZChMT0NLKXtteVZhcisrfVwiO3tbJiomXX0=[[/code], regardless of the overheads this causes – Java Performance Tuning

More On Thread Safety

All the techniques I discussed so far is to show you how to make your code thread safe. They are applicable only if you have to share resources across multiple threads and those threads may modify the resources. That is to say, if you don’t share any resources or other threads only read but no write, your code are thread safe already. Here are some tips related to not sharing and read-only sharing:

1. You can use local variables to carry out logic in the methods if possible (not share)
2. You can use TheadLocal to hold the resources if you want to access it across multiple methods for the same thread (not share)
3. You can use immutable object (private variable without setXXX methods) for read-only sharing. For example, String and PrimitiveWrappers like Integer. However, make sure the declare final for the reference that holds your immutable object.
4. Most of the time, you use collection classes like HashMap, ArrayList to hold our objects. Those classes are not thread safe. To make it thread safe, you may use Collections.synchronized wrappers or simply use the synchronized version of them like Hashtable and Vector. However, these approaches have 2 problems
   • They are not performed. Why lock every reads only to protect occasional write?
   • They are just conditionally thread-safe. All individual operations are thread-safe, but sequences of operations where the control flow depends on the results of previous operations may be subject to data races like doing containsKey(), size() and iterator() methods before actually read and write can give you NullPointerException and ConcurrentModificationException if you don’t do external synchronization.
   • Here are the unconditionally thread-safe version like ConcurrentHashMap, ConcurrentLinkedQueue and CopyOnWriteArrayList to achieve thread-safe with good performance number.
   • When you write an unconditionally thread-safe class, consider using private lock object in place of synchronized methods. This protect you against synchronization interference by clients and subclasses and gives you the flexibility to adopt a more sophisticated approach to concurrent control in later release – Joshua Bloch in Effective Java 2nd version p.281.
5. Deal with lazy initialization
6. Handle denial of service attack that holds the object lock forever

Java Memory Model

JMM is what causes concurrent programming way more complicated than it should be. Honestly, I am not good to write this part because I cannot understand it in full. All I can do is to provide you a video from Jeremy Manson in Google. Hear what the expert said:

 If you still have questions, make sure go to his blog

http://jeremymanson.blogspot.com/

Reference

Below are some of the articles I use:

1. What does volatile do?
2. Sun lesson on concurrency
3. Fixing Java Memory Model – Brian Goetz – Part 1, Part 2
4. Rox Java NIO Tutorial
5. Blocking Queue
6. Synchronization and Java Memory Model – Doug Lea