Advanced Java "Stump the Chump" Interview Questions Part 3

A while back I wrote an entry listing some Java-based “stump the chump” questions. These are questions and I have encountered or used in an interview to separate the competent developers from the extremely competent ones. The idea is that the questions represent fairly obscure areas of development where the details can cost days or months of productivity but aren’t really deal breakers in terms of employability.

Recently I encountered a few more such questions, this time in the realm of concurrency and multi-threaded development so I thought I’d document them for future reference.

Question 1: Why will the following code not always terminate?
public class foo {
private boolean shouldStopFlag = false;

public void methodCalledByThreadA() {
while (!shouldStopFlag) {
//Do some work here.
}
}

public void methodCalledByThreadB() {
shouldStopFlag = true;
}
}
The answer to this problem is a fairly subtle one that deals with data visibility. As written, the JRE is allowed to put the shouldStopFlag in any place in memory including registers and cache that isn’t necessarily visible to all threads. I first read about this issue several years ago in the excellent book, Java Concurrency in Practice by Brian Goetz, Joshua Block, et. all. I even gave a speech at the Rocky Mountain Oracle Users’ Group (ROUG) Training Days where I warned others about the issue. However, I still actually had to make the mistake and lose a couple hours wondering why before I truly appreciated the fact that this isn’t really an isolated, “one in a million” kind of problem. (I was running a dual core machine and saw the problem about one time in a hundred calls. Fortunately, I was using test-driven development and was able to reproduce the symptoms every couple of runs.)

There are several solutions that can address this problem. The first is to use a synchronized block to guard the flag. (That may be overkill in this particular code sample but I believe that, in general, synchronized blocks have an unfair stigma due to performance problems that were addressed a long time ago.)

The second option is to use the volatile keyword. This instructs the JRE not to put the variable into areas that aren’t visible across threads. (The meaning of this keyword has changed slightly starting in Java 1.5 so be careful of older documents covering the topic.)

The third option is to make the variable into a java.util.concurrent.atomic.AtomicBoolean. This class makes the variable into a lock-free, thread-safe version of the boolean variable. AtomicBooean variables also have other standard, atomic methods such as compareAndSet and getAndSet. Finally, according to this source, the atomic package also takes advantage of underlying hardware to implement the atomic behavior.

In general, I’ve noticed that certain concurrency issues and tools such as race conditions, semaphores, and deadlocks are well understood by developers but visibility issues unique to Java are not as widely known or understood. (How many people know what the Java Memory Model is and why it changed as of Java 1.5?)

Question 2: Why are happens-before relationships important in the Java Memory Model?

First a note: Notice that I didn’t ask, “What is a happens-before relationship as it pertains to the Java Memory Model?” The reason for this is that the best descriptions that I’ve read of happens-before relationships take several hundred carefully-chosen words and are full of subtleties that I think even the experts would have trouble getting right without a cheat-sheet. The clearest explanation that I have seen on-line so far is here.

In any case, the reason that has-before relationships matter in multi-threaded applications is that under certain circumstances, the compiler and the JRE are allowed to execute commands out of order from what was actually written. The reordering is invisible most of the time. (In single threaded applications, it is invisible all of the time.) However, in multi-threaded applications, the reordering may be visible if the affected sections of code aren’t properly synchronized.

I feel lucky not to have personally run afoul of this issue (that I know of). Some of the just-in-time compiler’s optimizing capabilities are really cool but I’d hate to have to try to identify this issue in a live system.

Separating Advanced Java Programmers from Competent Ones: “Stump the Chump” Interview Questions Part 2

Q: What is Jar sealing and when would you need it?

A: This question relates to how class loaders are implemented. (It’s my preferred stump the chump question and I’ve actually run into this situation before.) The background necessary for this question is as follows:

Class loaders are hierarchical. Most J2SE applications have at least three class loaders and J2EE apps generally have more. (The class loaders in a J2EE app form a tree which allows one Java VM to protect deployments from namespace collisions, etc.) Each class loader, except for the root loader, has a parent and the class loaders are usually supposed to ask the parent to supply a class before trying to do it themselves. Thus, when a class loader tries to load java.lang.String, it should try to get it from the parent rather than create its own. Only if the parent cannot create the class should the loader try. The root-level class loader loads all classes necessary for things like the security manager to perform its job. The second class-loader usually creates all Java classes that run inside the security manager, and the rest of the class loaders in the hierarchy are used for the code that isn’t part of the VM.

Classes are loaded by a class loader exactly once. In other words, classes are read from a jar file no more than once by a class loader instance. The problem comes when developers want the ability to reload a class, for example when an application is hot-deployed to a server. (I believe JUnit also likes to reload any user-created classes between tests.) In that case, the class loader instance is destroyed and a new one is created in its place. However, for this technique to work, the class loader must have the opposite behavior from the one described above, they must first attempt to create the class, and only ask the parent if they cannot do it themselves.

So far, so good. The problem comes when a class is loaded by two separate class loaders in a hierarchy. At this point version differences can cause all kinds of unpredictable behavior and often, the problem doesn’t even manifest itself near the actual offending code. Symptoms generally include things like null pointer exceptions in lines of code that make no sense. In many ways, it reminds me of incrementing a pointer too far in C++ except that it generally doesn’t core the VM.

In general, there are two ways that I’ve seen the problems manifest themselves:

1. An application server’s class loader loads one version of a jar file (like log4j) and the developer deploys a different version with an application. If a method signature changes from one version to the next, then the developer can get errors about not having the correct number of parameters in the method call even though he/she’s done nothing wrong. The VM may also generate errors about calling methods that don’t exist (even when they do) or worse, the method call works fine until the class called by the developer calls another object that doesn’t exist in that version of the package.


2. A developer is writing code and testing it periodically as he develops. At this point, it is almost certain that method signatures are changing and new methods are being added, renamed, or removed. When deploying this code to an application server, something goes wrong with the deployment and more than one version of the code lives on the server without the developer realizing it. For me this happened when I was using weblogic 7 and switched between hot deployment (where I dropped a new version of the ear file into a directory) and deploying via the web interface. The class loaders were apparently not peers in the class loader tree and both versions of my application were “partially” deployed.

The worst part of this problem is that it is not obvious and not intuitive what’s going on. The problem may not manifest any symptoms right away and when symptoms appear, they almost never seem related to the class loader in any way. Generally, I’ve realized the mistake after spending three days debugging code that hasn’t changed and always used to work. Somewhere around the point when I start to question my sanity and my abilities as a developer, I realize that this is the dreaded “hot deployment” issue. The problem is easily fixed by reinstalling the server instance. (Sometimes undeploying and redeploying an application isn’t sufficient and it’s not obvious where the server keeps all of its cached files.)

Enter the ounce of prevention. Sealing a jar involves placing a line inside the manifest file that lists the jar (or some subset of it like a particular package) as being sealed. (The <jar> ant task also has an option to seal the jar.) That line instructs the class loader hierarchy to only retrieve classes in that package from exactly one file. A jar sealing exception, java.lang.SecurityException: sealing violation is thrown if the class loader attempts to get its files from more that one jar. This prevents all of the headaches listed above and, generally, the class loader “does the right thing” on the edge cases. (for example, if one version of a jar is sealed but not another)

The only place that I’ve run into problems with jar sealing is when developers want to build test classes in the same package and directory as the code itself. Usually, they use ant tasks to create a deliverable jar and a test jar that only contains the test classes. Considering the pain that can be caused when class loaders go wrong, I would recommend placing test code in its own package (Sub-packages can live in a separate jar with no problems.) or building a “test” jar that contains both the base code and the test classes.

Separating Advanced Java Programmers from Competent Ones: “Stump the Chump” Interview Questions Part 1

Having participated in a number of technical interviews and conducted others, I’ve noticed a pattern. About two thirds of the way through the interview, the interviewer will throw out a specific type of question, one that I’ve come to think of as a “stump the chump” question. This question will generally be fairly obscure in nature and the interviewee isn’t generally penalized for not knowing the answer. (At least it doesn’t appear to hurt the interviewee’s chances of getting hired. On the other hand, knowing the answer really impresses the interviewer.)

The purpose of the stump the chump question is to determine whether the interviewee is merely competent or really knows his or her stuff. What I’ve noticed about these questions though, is that it can give fairly good insight into what kinds of nasty, low-level problems the company’s alpha geeks have spent their time on. Here is a list of the stump the chump questions I’ve run across and what they relate to.

Q: When a Java object calls wait(), what happens to the mutex lock that it’s holding?
A: The mutex lock is silently released and the thread sleeps. When another thread acquires the lock and calls notify(), the lock is again silently released and, sometime later, is returned to the waiting thread. It is possible for a third thread to acquire the lock at any time that the lock is released. This behavior is implemented deep within the virtual machine and requires support from the underlying operating system. However, the code can confuse programmers because the lock is actually released for a time even though it is in a synchronized block. Consider the following code that implements a rudimentary blocking queue. (Please note: As of Java 1.5 a blocking queue is supplied in a standard API and you shouldn’t need to code your own in most cases.):

import java.util.LinkedList;

public class BlockingQueue {
private LinkedList items = new LinkedList();

public synchronized T getItem() {
while (items.isEmpty()) {
try {
this.wait();
}
catch (InterruptedException e) {
return null;
}
}

//TODO Check for race condiditon here.
T returnValue = items.getFirst();
items.remove(0);
return returnValue;
}

public synchronized void addItem(T newItem){
items.add(newItem);
this.notify();
}
}

Note that it isn't necessarily obvious that the lock is lost inside the synchronized block.

Q: What is an “old” object?
A: This question relates to the inner workings of the garbage collector (and most of the time you shouldn’t care). Basically, the designers of garbage collectors noticed that objects tended to have one of two lifespans: either very short (like variables declared in a fairly tight for loop), or very long (like members of a long-lived object). As such, when the garbage collector starts to recover memory that is no longer in use, it tends to start by examining the very short lived objects and not checking the long lived objects as often. Certain implementations divided the object lifespans into three groups but the effect was basically the same: objects that are still in use after enough iterations of the garbage collector are promoted from the "new" bucket to the "old" bucket and the collection of new objects is swept more frequently.

Q: What is a soft reference? How is it different from a weak reference?
A: This is another garbage collector question. The short answer is to compare it to a strong reference. A strong reference is any reference to a variable that can be accessed from any running thread. The garbage collector will never recover anything that is accessible through a strong reference. However, it may choose to recover objects that are only available through a soft reference. This can be useful when implementing things like caches where the information may be re-obtained or re-derived if needed but the garbage collector can still recover the memory if it’s about to run out. Weak references are references that are not available as either strong or soft references. The final type is a phantom reference. It refers to any object that has already been reclaimed by the garbage collector. Weak and phantom references are primarily useful for determining whether or not the garbage collector has started to reclaim an object. A far more detailed explanation of these reference types can be found here.

The final “stump the chump question will be posted as a separate entry because it involves a fair bit of background explanation.