This section provides some explanation of how Java threads are scheduled and synchronized by Jikes RVM.

All Java threads (application threads, garbage collector threads, etc.) derive from RVMThread. Each RVMThread maps directly to one native thread, which may be implemented using whichever C/C++ threading library is in use (currently either pthreads or Harmony threads). Unless -X:forceOneCPU is used, native threads are allowed to be arbitrarily scheduled by the OS using whatever processor resources are available; Jikes RVM does not attempt to control the thread-processor mapping at all.

Using native threading gives Jikes RVM better compatibility for existing JNI code, as well as improved performance, and greater infrastructure simplicity. Scheduling is offloaded entirely to the operating system; this is both what native code would expect and what maximizes the OS scheduler's ability to optimally schedule Java threads. As well, the resulting VM infrastructure is both simpler and more robust, since instead of focusing on scheduling decisions it can take a "hands-off" approach except when Java threads have to be preempted for sampling, on-stack-replacement, garbage collection, Thread.suspend(), or locking. The main task of RVMThread and other code in org.jikesrvm.scheduler is thus to override OS scheduling decisions when the VM demands it.

The remainder of this section is organized as follows. The management of a thread's state is discussed in detail. Mechanisms for blocking and handshaking threads are described. The VM's internal locking mechanism, the Monitor, is described. Finally, the locking implementation is discussed.

Tracking the Thread State

The state of a thread is broken down into two elements:

The first mechanism is provided by the RVMThread.takeYieldpoint field, which is 0 if the thread should not yield, or non-zero if it should yield at the next safe point. Negative versus positive values indicate the type of safe point to yield at (epilogue/prologue, or any, respectively).

But this alone is insufficient to manage threads, as it relies on all threads being able to reach a safe point in a timely fashion. New Java threads may be started at any time, including at the exact moment that the garbage collector is starting; a starting-but-not-yet-started thread may not reach a safe point if the thread that was starting it is already blocked. Java threads may terminate at any time; terminated threads will never again reach a safe point. Any Java thread may call into arbitrary JNI code, which is outside of the VM's control, and may run for an arbitrary amount of time without reaching a Java safe point. As well, other mechanisms of RVMThread may cause a thread to block, thereby making it incapable of reaching a safe point in a timely fashion. However, in each of these cases, the Java thread is "effectively safe" - it is not running Java code that would interfere with the garbage collector, on-stack-replacement, locking, or any other Java runtime mechanism. Thus, a state management system is needed that would notify these runtime services when a thread is "effectively safe" and does not need to be waited on.

RVMThread provides for the following thread states, which describe to other runtime services the state of a Java thread. These states are designed with extreme care to support the following features:

The states used to put these features into effect are listed below.

The states are stored in RVMThread.execStatus, an integer field that may be rapidly manipulated using compare-and-swap. This field uses a hybrid synchronization protocol, which includes both compare-and-swap and conventional locking (using the thread's Monitor, accessible via the RVMThread.monitor() method). The rules are as follows:

The typical algorithm for requesting a thread to block looks as follows:

thread.monitor().lockNoHandshake();
if (thread is running) {
   thread.takeYieldpoint=1;

   // transitions IN_JAVA -> IN_JAVA_TO_BLOCK, IN_NATIVE->BLOCKED_IN_NATIVE, etc.
   thread.setBlockedExecStatus(); 
   
   if (thread.isInJava()) {
      // Thread will reach safe point soon, or else notify 
      // us that it left to native code.
      // In either case, since we are holding the lock, 
      // the thread will effectively block on either the safe point
      // or on the attempt to go to native code, since performing
      // either state transition requires acquiring the lock,
      // which we are now holding.
   } else {
      // Thread is in native code, and thus is "effectively safe",
      // and cannot go back to running Java code so long as we hold
      // the lock, since that state transition requires
      // acquiring the lock.
   }
}
thread.monitor().unlock();

Most of the time, you do not have to write such code, as the cases of blocking threads are already implemented. For examples of how to utilize these mechanisms, see RVMThread.block(), RVMThread.hardHandshakeSuspend(), and RVMThread.softHandshake(). A discussion of how to use these methods follows in the section below.

Finally, the valid state transitions are as follows.

Blocking and Handshaking

Various VM services, such as the garbage collector and locking, may wish to request a thread to block. In some cases, we want to block all threads except for the thread that makes the request. As well, some VM services may only wish for a "soft handshake", where we wait for each non-collector thread to perform some action exactly once and then continue (in this case, the only thread that blocks is the thread requesting the soft handshake, but all other non-collector threads must "yield" in order to perform the requested action; in most cases that action is non-blocking). A unified facility for performing all of these requests is provided by RVMThread.

Four types of thread blocking and handshaking are supported:

The Monitor API

The VM internally uses an OS-based locking implementation, augmented with support for safe lock recursion and awareness of handshakes. The Monitor API provides locking and notification, similar to a Java lock, and may be implemented using either a pthread_mutex and a pthread_cond, or using Harmony's monitor API.

Acquiring a Monitor lock, or awaiting notification, may cause the calling RVMThread to block. This prevents the calling thread from acknowledging handshakes until the blocking call returns. In some cases, this is desirable. For example:

But in all other cases, the calling thread must ensure that the handshake mechanism is notified that thread will block. Hence, all blocking Monitor methods have both a "NoHandshake" and "WithHandshake" version. Consider the following code:

someMonitor.lockNoHandshake();
// perform fast, bounded-time critical section
someMonitor.unlock(); // non-blocking

In this code, lock acquisition is done without notifying handshakes. This makes the acquisition faster. In this case, it is safe because the critical section is bounded-time. As well, we require that in this case, any other critical sections protected by someMonitor are bounded-time as well. If, on the other hand, the critical section was not bounded-time, we would do:

someMonitor.lockWithHandshake();
// perform potentially long critical section
someMonitor.unlock();

In this case, the lockWithHandshake() operation will transition the calling thread to the IN_NATIVE state before acquiring the lock, and then transition it back to IN_JAVA once the lock is acquired. This may cause the thread to block, if a handshake is in progress. As an added safety provision, if the lockWithHandshake() operation blocks due to a handshake, it will ensure that it does so without holding the someMonitor lock.

A special Monitor is provided with each thread. This monitor is of the type NoYieldpointsMonitor and will also ensure that yieldpoints (safe points) are disabled while the lock is held. This is necessary because any safe point may release the Monitor lock by waiting on it, thereby breaking atomicity of the critical section. The NoYieldpointsMonitor for any RVMThread may be accessed using the RVMThread.monitor() method.

Additional information about how to use this API is found in the following section, which discusses the implementation of Java locking.

Thin and Biased Locking

Jikes RVM uses a hybrid thin/biased locking implementation that is designed for very high performance under any of the following loads:

Thin locking has a relatively simple implementation; roughly 20 bits in the object header are used to represent the current lock state, and compare-and-swap is used to manipulate it. Biased locking and contended locking are more complicated, and are described below.

Biased locking makes the optimistic assumption that only one thread will ever want to acquire the lock. So long as this assumption holds, acquisition of the lock is a simple non-atomic increment/decrement. However, if the assumption is violated (a thread other than the one to which the lock is biased attempts to acquire the lock), a fallback mechanism is used to turn the lock into either a thin or contended lock. This works by using RVMThread.beginPairHandshake() to bring both the thread that is requesting the lock and the thread to which the lock is biased to a safe point. No other threads are affected; hence this system is very scalable. Once the pair handshake begins, the thread requesting the lock changes the lock into either a thin or contended lock, and then ends the pair handshake, allowing the thread to which the lock was biased to resume execution, while the thread requesting the lock may now contend on it using normal thin/contended mechanisms.

Contended locks, or "fat locks", consist of three mechanisms:

The spin lock is a org.jikesrvm.scheduler.SpinLock. The queue is implemented in org.jikesrvm.scheduler.ThreadQueue. And the blocking/unblocking mechanism leverages org.jikesrvm.scheduler.Monitor; in particular, it uses the Monitor that is attached to each thread, accessible via RVMThread.monitor(). The basic algorithm for lock acquisition is:

spinLock.lock();
while (true) {
   if (lock available) {
      acquire the lock;
      break;
   } else {
      queue.enqueue(me);
      spinLock.unlock();

      me.monitor().lockNoHandshake();
      while (queue.isQueued(me)) {
         // put this thread to sleep waiting to be dequeued, 
         // and do so while the thread is IN_NATIVE to ensure 
         // that other threads don't wait on this one for
         // handshakes while we're blocked.
         me.monitor().waitWithHandshake();
      }
      me.monitor().unlock();
      spinLock.lock();
   }
}
spinLock.unlock();

The algorithm for unlocking dequeues the thread at the head of the queue (if there is one) and notifies its Monitor using the lockedBroadcastNoHandshake() method. Note that these algorithms span multiple methods in org.jikesrvm.scheduler.ThinLock and org.jikesrvm.scheduler.Lock; in particular, lockHeavy(), lockHeavyLocked(), unlockHeavy(), lock(), and unlock().