Re-entrant and Non Re-entrant Code

Re-entrant means that once a method is called on your object, it should be possible for someone else to call that method. For an example of something that’s non-re-entrant the IBM XML Parser (version 1.x) comes to mind. When certain methods are called on the IBM DOM parser, and exceptions are thrown the entire object becomes frozen and no one can call any more methods on that object. This is an example of non-reentrant code.

Thread-safe vs. threaded classes

When you make thread-safe classes, you have to keep in mind that multiple threads could be trampling through the methods of your class. This requires special care in designing and coding these classes, becuase there is no way of knowing what thread will invoke what method (and in what sequence) on an object of this class. You have to take into account all possible scenarios or design in such a way that the number of possible states that your object can reach is minimized. I prefer to use the smart solution and design in such a way that the number of states my object can reach is minimized, that way I don’t have to think about too many possibilities of what might happen when multiple threads are trampling through the same instance of my class.

In order to make thread-safe classes there are a few simple rules to follow:

• Mutator method access to any shared objects must be synchronized.
• Accessor method access to any shared objects need not be synchronized.
  • There is an exception to this rule however. When your shared object’s value fluctuates very frequently (like stock prices), then it is necessary to synchronize the accessor too, in order to report the correct value of the object rather than some intermediate (and inaccurate) value of the object. There are more advanced techniques to get around making your accessors synchronized which I will show you in the advanced thread tutorial. But for now, be sure to synchronize everything!

Difference between Thread Class and Runnable interface

The only difference between implementing Runnable and extending Thread is that by extending Thread, each of your threads has a unique object associated with it, whereas with Runnable, many threads share the same object instance.

What does volatile do?

This is probably best explained by comparing the effects that volatile and synchronized have on a method. volatile is a field modifier, while synchronized modifies code blocks and methods. So we can specify three variations of a simple accessor using those two keywords:

         int i1;              int geti1() {return i1;}
volatile int i2;              int geti2() {return i2;}
        int i3; synchronized int geti3() {return i3;}

geti1() accesses the value currently stored in i1 in the current thread. Threads can have local copies of variables, and the data does not have to be the same as the data held in other threads. In particular, another thread may have updated i1 in it's thread, but the value in the current thread could be different from that updated value. In fact Java has the idea of a "main" memory, and this is the memory that holds the current "correct" value for variables. Threads can have their own copy of data for variables, and the thread copy can be different from the "main" memory. So in fact, it is possible for the "main" memory to have a value of 1 for i1, for thread1 to have a value of 2 for i1 and for thread2 to have a value of 3 for i1 if thread1 and thread2 have both updated i1 but those updated value has not yet been propagated to "main" memory or other threads.

On the other hand, geti2() effectively accesses the value of i2 from "main" memory. A volatile variable is not allowed to have a local copy of a variable that is different from the value currently held in "main" memory. Effectively, a variable declared volatile must have it's data synchronized across all threads, so that whenever you access or update the variable in any thread, all other threads immediately see the same value. Of course, it is likely that volatile variables have a higher access and update overhead than "plain" variables, since the reason threads can have their own copy of data is for better efficiency.

Well if volatile already synchronizes data across threads, what is synchronized for? Well there are two differences. Firstly synchronized obtains and releases locks on monitors which can force only one thread at a time to execute a code block, if both threads use the same monitor (effectively the same object lock). That's the fairly well known aspect to synchronized. But synchronized also synchronizes memory. In fact synchronized synchronizes the whole of thread memory with "main" memory. So executing geti3() does the following:

1. The thread acquires the lock on the monitor for object this (assuming the monitor is unlocked, otherwise the thread waits until the monitor is unlocked).
2. The thread memory flushes all its variables, i.e. it has all of its variables effectively read from "main" memory (JVMs can use dirty sets to optimize this so that only "dirty" variables are flushed, but conceptually this is the same. See section 17.9 of the Java language specification).
3. The code block is executed (in this case setting the return value to the current value of i3, which may have just been reset from "main" memory).
4. (Any changes to variables would normally now be written out to "main" memory, but for geti3() we have no changes.)
5. The thread releases the lock on the monitor for object this.

So where volatile only synchronizes the value of one variable between thread memory and "main" memory, synchronized synchronizes the value of all variables between thread memory and "main" memory, and locks and releases a monitor to boot. Clearly synchronized is likely to have more overhead than volatile.

Difference between Hashtable and ConcurrentHashMap

ConcurrentHashMap is a pretty ignored class. Not many people know about it and not many people care to use it. The class offers a very robust and fast (comparatively, we all know java concurrency isn’t the fastest) method of synchronizing a Map collection.

I have read a few comparisons of HashMap and ConcurrentHashMap on the web. Let me just say that they’re totally wrong. There is no way you can compare the two, one offers synchronized methods to access a map while the other offers no synchronization whatsoever. What most of us fail to notice is that while our applications, web applications especially, work fine during the development & testing phase, they usually go tits up under heavy (or even moderately heavy) load. This is due to the fact that we expect our HashMap’s to behave a certain way but under load they usually misbehave.

Hashtable’s offer concurrent access to their entries, with a small caveat, the entire map is locked to perform any sort of operation. While this overhead is ignorable in a web application under normal load, under heavy load it can lead to delayed response times and overtaxing of your server for no good reason.

This is where ConcurrentHashMap’s step in. They offer all the features of Hashtable with a performance almost as good as a HashMap. ConcurrentHashMap’s accomplish this by a very simple mechanism. Instead of a map wide lock, the collection maintains a list of 16 locks by default, each of which is used to guard (or lock on) a single bucket of the map. This effectively means that 16 threads can modify the collection at a single time (as long as they’re all working on different buckets). Infact there is no operation performed by this collection that locks the entire map. The concurrency level of the collection, the number of threads that can modify it at the same time without blocking, can be increased. However a higher number means more overhead of maintaining this list of locks.

Retrieval operations on a ConcurrentHashMap do not block unless the entry is not found in the bucket or if the value of the entry is null. In such a case the map synchronizes on the bucket and then tries to look for the entry again just in case the entry was put or removed right after the get in synchronized mode.

Removal operations do require a bit of overhead. All removal operations require the chain of elements before and after to be cloned and joined without the removed element. Since the value of the map key is volatile (not really, the value of the inner Entry class is volatile) if a thread already traversing the bucket from which a value is removed reaches the removed element, it automatically sees a null value and knows to ignore such a value.

Traversal in a ConcurrentHashMap does not synchronize on the entire map either. Infact traversal does not synchronize at all except under one condition. The internal LinkedList implementation is aware of the changes to the underlying collection. If it detects any such changes during traversal it synchronizes itself on the bucket it is traversing and then tries to re-read the values. This always insures that while the values recieved are always fresh, there is minimalistic locking if any.

Iteration over a ConcurrentHashMap are a little different from those offered by other collections. The iterators are not fail-fast in the sense that they do not throw a ConcurrentModificationException. They also do not guarantee that once the iterator is created it will list/show all elements that are added after its creation. The iterators do however guarantee that any updates or removal of items will be reflected correctly in their behaviour. They also guarantee that no element will be returned more than once while traversal.

In conclusion, give it a try, replace some Hashtable’s in your application with ConcurrentHashMap and see how they perform under load. The two are interchangeable so it shouldn’t be hard to update your app. Happy changing!