This chapter is from the book
This chapter is from the book
This chapter is from the book
Lock Contention
In early JVM releases, it was common to delegate Java monitor operations directly to operating system monitors, or mutex primitives. As a result, a Java application experiencing lock contention would exhibit high values of system CPU utilization since operating system mutex primitives involve system calls. In modern JVMs Java monitors are mostly implemented within the JVM in user code rather than immediately delegating them to operating system locking primitives. This means Java applications can exhibit lock contention yet not consume system CPU. Rather, these applications first consume user CPU utilization when attempting to acquire a lock. Only applications that experience severe lock contention may show high system CPU utilization since modern JVMs tend to delegate to operating system locking primitives as a last resort. A Java application running in a modern JVM that experiences lock contention tends to show symptoms of not scaling to a large number of application threads, CPU cores, or a large number of concurrent users. The challenge is finding the source of the lock contention, that is, where are those Java monitors in the source code and what can be done to reduce the lock contention.
Finding and isolating the location of highly contented Java monitors is one of the strengths of the Oracle Solaris Performance Analyzer. Once a profile has been collected with the Performance Analyzer, finding the highly contented locks is easy.
The Performance Analyzer collects Java monitor and lock statistics as part of an application profile. Hence, you can ask the Performance Analyzer to present the Java methods in your application using Java monitors or locks.
By selecting the View > Set Data Presentation menu in Performance Analyzer and choosing the Metrics tab, you can ask the Performance Analyzer to present lock statistics, both inclusive or exclusive. Remember that inclusive lock metrics include not only the lock time spent in a given method but also the lock time spent in methods it calls. In contrast, exclusive metrics report only the amount of lock time spent in a given method.
Figure 6-10 shows the Performance Analyzer's Set Data Presentation form with options selected to present both inclusive and exclusive lock information. Also notice the options selected report both the time value and the percentage spent locking.
)
Figure 6-10 Set user lock data presentation
After clicking OK, the Performance Analyzer displays the profile's lock inclusive and exclusive metrics in descending order. The arrow in the metric column header indicates how the data is presented. In Figure 6-11, the lock data is ordered by the exclusive metric (notice the arrow in the exclusive metric header and note the icon indicating an exclusive metric).
The screenshot taken in Figure 6-11 is from a simple example program (complete source code for the remaining examples used in this chapter can be found in Appendix B, "Profiling Tips and Tricks Example Source Code") that uses a java.util.HashMap as a data structure to hold 2 million fictitious tax payer records and performs updates to those records stored in the HashMap. Since this example is multithreaded and the operations performed against the HashMap include adding a new record, removing a new record, updating an existing record, and retrieving a record, the HashMap requires synchronized access, that is, the HashMap is allocated as a Synchronized Map using the Collections.synchronizedMap() API. The following list provides more details as to what this example program does:
- Creates 2 million fictitious tax payer records and places them in an in-memory data store, a java.util.HashMap using a tax payer id as the HashMap key and the tax payer's record as the value.
- Queries the underlying system for the number of available processors using the Java API Runtime.availableProcessors() to determine the number of simultaneous Java threads to execute concurrently.
- Uses the number returned from Runtime.availableProcessors() and creates that many java.util.concurrent.Callable objects to execute concurrently in an allocated java.util.concurrent.ExecutorService pool of Executors.
- All Executors are launched and tax payer records are retrieved, updated, removed, and added concurrently by the Executor threads in the HashMap. Since there is concurrent access to the HashMap through the actions of adding, removing, and updating records, HashMap access must be synchronized. The HashMap is synchronized using the Collections.synchronizedMap() wrapper API at HashMap creation time.
From the preceding description, it should be of little surprise this example program experiences lock contention when a large number of threads are trying to concurrently access the same synchronized HashMap. For example, when this program is run on a Sun SPARC Enterprise T5120 Server configured with an UltraSPARC T2 processor, which has 64 virtual processors (the same value as that returned by the Java API Runtime.availableProcessors()), the performance throughput reported by the program is about 615,000 operations per second. But only 8% CPU utilization is reported due to heavy lock contention. Oracle Solaris mpstat also reports a large number of voluntary thread context switches. In Chapter 2, the "Memory Utilization" section talks about high values of voluntary thread context switches being a potential indicator of high lock contention. In that section, it is said that the act of parking a thread and awaking a thread after being notified both result in an operating system voluntary context switch. Hence, an application experiencing heavy lock contention also exhibits a high number of voluntary context switches. In short, this application is exhibiting symptoms of lock contention.
Capturing a profile of this example program with the Performance Analyzer and viewing its lock statistics, as Figure 6-11 shows, confirms this program is experiencing heavy lock contention. The application is spending about 59% of the total lock time, about 14,000 seconds, performing a synchronized HashMap.get() operation. You can also see about 38% of the total lock time is spent in an entry labeled <JVM-System>. You can read more about this in the "Understanding JVM-System Locking" sidebar. You can also see the calls to the put() and remove() records in the synchronized HashMap as well.
)
Figure 6-11 Java monitors/locks ordered by exclusive metric
Figure 6-12 shows the Callers-Callees of the SynchronizedMap.get() entry. It is indeed called by the TaxPayerBailoutDBImpl.get() method, and the SynchronizedMap.get() method calls a HashMap.get() method.
)
Figure 6-12 Callers-Callees of synchronized HashMap.get()
Understanding JVM-System Locking
A JVM-System entry in Performance Analyzer indicates time spent within the JVM internals. In the context of looking at lock contention statistics in Performance Analyzer, this is the amount or percentage of time spent in locks within the internals of the JVM. This may sound alarming when looking at the amount of time spent in the JVM-System in Figure 6-11. Hence, this requires a little further explanation and clarification. Recall from Chapter 5 that switching from a Data Presentation Format of User mode to either Expert mode or Machine mode shows the internal operations of the JVM and puts them in the JVM-System entry seen in User mode. Also remember that switching to Expert mode or Machine mode also shows highly contended Java monitors as a form of a _lwp_mutex, __lwp_cond_wait, or __lwp_park type of entry and isolates the locking within Java APIs with those found within the JVM. Figure 6-13 shows the same profile but is switched from User mode to Expert mode in the Performance Analyzer.
)
Figure 6-13 Switching from User mode to Expert mode
Comparing Figure 6-11 to Figure 6-13 suggests the JVM-System entry has resolved into __lwp_condition_wait and __lwp_park operations. The sum of the __lwp_condition_wait and __lwp_park are close to what is reported for JVM-System in Figure 6-11. Your initial reaction may be the JVM is also experiencing lock contention. However, selecting the __lwp_cond_wait entry and selecting the Callers-Callees tab and walking up the call stack, the source of the locking activity associated with __lwp_cond_wait, in other words the locking activity associated with the JVM-System entry, is shown in Figure 6-14.
)
Figure 6-14 Traversing up the call stack of callers of __lwp_cond_wait
All five of the methods shown in Figure 6-14 are internal JVM methods. Notice that over 95% of the attributable lock time is spent in GCTaskManager::get_task(unsigned). This method is part of the garbage collection subsystem of the Java HotSpot VM. This garbage collection method blocks and waits on a queue for work to do on behalf of the garbage collector subsystem. Each of the method names listed in Figure 6-14 represent areas of the Java HotSpot VM that may block and wait for some work to be placed on their respective work queue. For example, the VMThread::loop() method blocks on a queue for work to do on behalf of the Java HotSpot VM. You can think of the VMThread as the "kernel thread" of the Java HotSpot VM. The CompilerBroker::compile_thread_loop() method blocks and waits for work to do on behalf of the JIT compilation subsystem and so on. As a result, the entries reported as the JVM-System entry in User Mode can be ignored as being hot locks in this profile.
Continuing with the example program, the reaction from many Java developers when he or she observes the use of a synchronized HashMap or the use of a java.util.Hashtable, the predecessor to the synchronized HashMap, is to migrate to using a java.util.concurrent.ConcurrentHashMap.1 Following this practice and executing this program using a ConcurrentHashMap instead of a synchronized HashMap showed an increase of CPU utilization of 92%. In other words, the previous implementation that used a synchronized HashMap had a total CPU utilization of 8% while the ConcurrentHashMap implementation had 100% CPU utilization. In addition, the number of voluntary context switches dropped substantially from several thousand to less than 100. The reported number of operations per second performed with the ConcurrentHashMap implementation increased by a little over 2x to 1,315,000, up from 615,000 with the synchronized HashMap. However, seeing only a 2x performance improvement while utilizing 100% CPU utilization compared to just 8% CPU utilization is not quite what was expected.
Capturing a profile and viewing the results with the Performance Analyzer is in order to investigate what happened. Figure 6-15 shows the hot methods as java.util.Random.next(int) and java.util.concurrent.atomic.AtomicLong.compareAndSet(long, long).
)
Figure 6-15 Hot methods in the ConcurrentHashMap implementation of the program
Using the Callers-Callees tab to observe the callers of the java.util.concurrent.atomic.AtomicLong.compareAndSet(long, log) method shows java.util.Random.next(int) as the most frequent callee. Hence, the two hottest methods in the profile are in the same call stack; see Figure 6-16.
)
Figure 6-16 Callers of AtomicLong.compareAndSet
Figure 6-17 shows the result of traversing further up the call stack of the callers of Random.next(int). Traversing upwards shows Random.next(int) is called by Random.nextInt(int), which is called by a TaxCallable.updateTaxPayer(long, TaxPayerRecord) method and six methods from the BailoutMain class with the bulk of the attributable time spent in the TaxCallable.updateTaxPayer(long, TaxPayerRecord) method.
)
Figure 6-17 Callers and callees of Random.nextInt(int)
The implementation of TaxCallable.updateTaxPayer(long, TaxPayerRecord) is shown here:
final private static Random generator = BailoutMain.random;
// these class fields initialized in TaxCallable constructor
final private TaxPayerBailoutDB db;
private String taxPayerId;
private long nullCounter;
private TaxPayerRecord updateTaxPayer(long iterations,
TaxPayerRecord tpr) {
if (iterations % 1001 == 0) {
tpr = db.get(taxPayerId);
} else {
// update a TaxPayer's DB record
tpr = db.get(taxPayerId);
if (tpr != null) {
long tax = generator.nextInt(10) + 15;
tpr.taxPaid(tax);
}
}
if (tpr == null) {
nullCounter++;
}
return tpr;
}
The purpose of TaxCallable.updateTaxPayer(long, TaxPayerRecord) is to update a tax payer's record in a tax payer's database with a tax paid. The amount of tax paid is randomly generated between 15 and 25. This randomly generated tax is implemented with the line of code, long tax = generator.nextInt(10) + 15. generator is a class instance static Random that is assigned the value of BailoutMain.random which is declared in the BailoutMain class as final public static Random random = new Random(Thread.currentThread().getId()). In other words, the BailoutMain.random class instance field is shared across all instances and uses of BailoutMain and TaxCallable. The BailoutMain.random serves several purposes in this application. It generates random fictitious tax payer ids, names, addresses, social security numbers, city names and states which are populated in a tax payer database, a TaxPayerBailoutDB which uses a ConcurrentHashMap in this implementation variant as its storage container. BailoutMain.random is also used, as described earlier, to generate a random tax for a given tax payer.
Since there are multiple instances of TaxCallable executing simultaneously in this application, the static TaxCallable.generator field is shared across all TaxCallable instances. Each of the TaxCallable instances execute in different threads, each sharing the same TaxCallable.generator field and updating the same tax payer database.
This means all threads executing TaxCallable.updateTaxPayer(long, TaxPayerRecord)trying to update the tax payer database must access the same Random object instance concurrently. Since the Java HotSpot JDK distributes the Java SE class library source code in a file called src.zip, it is possible to view the implementation of java.util.Random. A src.zip file is found in the JDK root installation directory. Within the src.zip file, you can find the java.util.Random.java source code. The implementation of the Random.next(int) method follows (remember from the Figure 6-17 that Random.next(int) is the method that calls the hot method java.util.concurrent.atomic.AtomicLong.compareAndSet(int,int)).
private final AtomicLong seed;
private final static long multiplier = 0x5DEECE66DL;
private final static long addend = 0xBL;
private final static long mask = (1L << 48) – 1;
protected int next(int bits) {
long oldseed, nextseed;
AtomicLong seed = this.seed;
do {
oldseed = seed.get();
nextseed = (oldseed * multiplier + addend) & mask;
} while (!seed.compareAndSet(oldseed, nextseed));
return (int)(nextseed >>> (48 - bits));
}
In Random.next(int), there is a do/while loop that performs an AtomicLong.compareAndSet(int,int) on the old seed and the new seed (this statement is highlighted in the preceding code example in bold). AtomicLong is an atomic concurrent data structure. Atomic and concurrent data structures were two of the features added to Java 5. Atomic and concurrent data structures typically rely on some form of a "compare and set" or "compare and swap" type of operation, also commonly referred to as a CAS, pronounced "kazz".
CAS operations are typically supported through one or more specialized CPU instructions. A CAS operation uses three operands: a memory location, an old value, and a new value. Here is a brief description of how a typical CAS operation works. A CPU atomically updates a memory location (an atomic variable) if the value at that location matches an expected old value. If that property fails to hold, no changes are made. To be more explicit, if the value at that memory location prior to the CAS operation matches a supplied expected old value, then the memory location is updated with the new value. Some CAS operations return a boolean value indicating whether the memory location was updated with the new value, which means the old value matched the contents of what was found in the memory location. If the old value does not match the contents of the memory location, the memory location is not updated and false is returned.
It is this latter boolean form the AtomicLong.compareAndSet(int, int) method uses. Looking at the preceding implementation of the Random.next(int) method, the condition in the do/while loop does not exit until the AtomicLong CAS operation atomically and successfully sets the AtomicLong value to the nextseed value. This only occurs if the current value at the AtomicLong's memory location has a value of the oldseed. If a large number of threads happen to be executing on the same Random object instance and calling Random.next(int), there is a high probability the AtomicLong.compareAndSet(int, int) CAS operation will return false since many threads will observe a different oldseed value at the AtomicLong's value memory location. As a result, many CPU cycles may be spent spinning in the do/while loop found in Random.next(int). This is what the Performance Analyzer profile suggests is the case.
A solution to this problem is to have each thread have its own Random object instance so that each thread is no longer trying to update the same AtomicLong's memory location at the same time. For this program, its functionality does not change with each thread having its own thread local Random object instance. This change can be accomplished rather easily by using a java.lang.ThreadLocal. For example, in BailoutMain, instead of using a static Random object, a static ThreadLocal<Random> could be used as follows:
// Old implementation using a static Random
//final public static Random random =
// new Random(Thread.currentThread.getid());
// Replaced with a new ThreadLocal<Random>
final public static ThreadLocal<Random> threadLocalRandom =
new ThreadLocal<Random>() {
@Override
protected Random initialValue() {
return new Random(Thread.currentThread().getId());
}
};
Then any reference to or use of BailoutMain.random should be replaced with threadLocalRandom.get(). A threadLocalRandom.get() retrieves a unique Random object instance for each thread executing code that used to use BailoutMain.random. Making this change allows the AtomicLong's CAS operation in Random.next(int) to succeed quickly since no other thread is sharing the same Random object instance. In short, the do/while in Random.next(int) completes on its first loop iteration execution.
After replacing the java.util.Random in BailoutMain with a ThreadLocal<Random> and re-running the program, there is a remarkable improvement performance. When using the static Random, the program reported about 1,315,000 operations per second being executed. With the static ThreadLocal<Random> the program reports a little over 32,000,000 operations per second being executed. 32,000,000 operations per second is almost 25x more operations per second higher than the version using the static Random object instance. And it is more than 50x faster than the synchronized HashMap implementation, which reported 615,000 operations per second.
A question that may be worthy of asking is whether the program that used the synchronized HashMap, the initial implementation, could realize a performance improvement by applying the ThreadLocal<Random> change. After applying this change, the version of the program that used a synchronized HashMap showed little performance improvement, nor did its CPU utilization improve. Its performance improved slightly from 615,000 operations per second to about 620,000 operations per second. This should not be too much of a surprise. Looking back at the profile, the method having the hot lock in the initial version, the one that used a synchronized HashMap, and shown in Figure 6-11 and Figure 6-12, reveals the hot lock is on the synchronized HashMap.get() method. In other words, the synchronized HashMap.get() lock is masking the Random.next(int) CAS issue uncovered in the first implementation that used ConcurrentHashMap.
One of the lessons to be learned here is that atomic and concurrent data structures may not be the holy grail. Atomic and concurrent data structures rely on a CAS operation, which in general employs a form of synchronization. Situations of high contention around an atomic variable can lead to poor performance or scalability even though a concurrent or lock-free data structure is being used.
Many atomic and concurrent data structures are available in Java SE. They are good choices to use when the need for them exists. But when such a data structure is not available, an alternative is to identify a way to design the application such that the frequency at which multiple threads access the same data and the scope of the data that is accessed is minimized. In other words, try to design the application to minimize the span, size, or amount of data to be synchronized. To illustrate with an example, suppose there was no known implementation of a ConcurrentHashMap available in Java, that is, only the synchronized HashMap data structure was available. The alternative approach just described suggests the idea to divide the tax payer database into multiple HashMaps to lessen the amount or scope of data that needs to be locked. One approach might be to consider a HashMap for tax payers in each state. In such an approach, there would be two levels of Maps. The first level Map would find one of the 50 state Maps. Since the first level Map will always contain a mapping of the 50 states, no elements need to be added to it or removed from it. Hence, the first level Map requires no synchronization. However, the second level state maps require synchronized access per state Map since tax payer records can be added, removed, and updated. In other words, the tax payer database would look something like the following:
public class TaxPayerBailoutDbImpl implements TaxPayerBailoutDB {
private final Map<String, Map<String,TaxPayerRecord>> db;
public TaxPayerBailoutDbImpl(int dbSize, int states) {
db = new HashMap<String,Map<String,TaxPayerRecord>>(states);
for (int i = 0; i < states; i++) {
Map<String,TaxPayerRecord> map =
Collections.synchronizedMap(
new HashMap<String,TaxPayerRecord>(dbSize/states));
db.put(BailoutMain.states[i], map);
}
}
...
In the preceding source code listing you can see the first level Map is allocated as a HashMap in the line db = new HashMap<String, Map<String, TaxPayerRecord>>(dbSize) and the second level Map, one for each of the 50 states is allocated as a synchronized HashMap in the for loop:
for (int i = 0; i < states; i++) {
Map<String,TaxPayerRecord> map =
Collections.synchronizedMap(
new HashMap<String,TaxPayerRecord>(dbSize/states));
db.put(BailoutMain.states[i], map);
}
Modifying this example program with the partitioning approach described here shows about 12,000,000 operations per second being performed and a CPU utilization of about 50%. The number of operations per second is not nearly as good as the 32,000,000 observed with a ConcurrentHashMap. But it is a rather large improvement over the single large synchronized HashMap, which yielded about 620,000 operations per second. Given there is unused CPU utilization, it is likely further partitioning could improve the operations per second in this partitioning approach. In general, with the partitioning approach, you trade-off additional CPU cycles for additional path length, that is, more CPU instructions, to reduce the scope of the data that is being locked where CPU cycles are lost blocking and waiting to acquire a lock.