Running on Multiple Tracks - The Guard, the Suspended, and the Spin

A first installment in what may become a series, this post discusses concurrency patterns with a JAVA flavor. 

And, since we mentioned JAVA, we have to start with the…

… Guarded Suspension Pattern

The guarded suspension pattern is a concurrent pattern which allows a thread that obtained a lock to suspend its execution and temporarily release the lock, waiting for a condition to be satisfied before proceeding any further within the critical section (re-acquiring the lock.)

In JAVA, guarded suspension is implemented via the wait(), and notify() methods, together with their more granular flavors, present in the Object class.

In general, this pattern is used as a signaling mechanism between collaborating threads to let each other know that certain conditions have been met. They would use a common critical section and each of the threads may enter it and suspend its execution waiting for a signal, without blocking other threads (BLOCKING) from entering the critical section, i.e. suspended. Upon being signaled to resume, the suspended (WAITING) thread will continue its execution in the critical section when its turn comes.

And, while we use the most basic threading primitives in these examples, the mechanism is visible in higher level concurrency packages.

In this example, a message producer and a message consumer are passing messages to each other via a queue of a limited size. Both the producer and the consumer may be set to wait for events or to notify each other of events, such as “publish more data, there’s space now”, or “consume more data, there are updates”.

In its most basic form the code will look like this:

waitForWakeUp:

System.out.println(101);

wakeUp:

synchronized (syncObject) {
  syncObject.notify();
}

‍

This is all well and good, except that the code snippets above are not representative of well behaved code if the expectation is that the waiting thread should only be awoken by the signaling thread. In uncommon instances, there is potential for a “spurious wakeup,” a circumstance which has the potential of waking up a waiting thread which then resumes execution without an explicit wake up call. This instance is largely a theoretical issue. It may never happen in practice, but since it may, this is where the guarded pattern comes into play.

It is clearly not enough to use the wait method by itself, as we don’t know if the wake up was triggered by a friend or if it was a random event. We will introduce a guard element (which can be a boolean or may be anything else, as long as it can represent more than one state), and we will re-write the code above as follows.

waitForWakeUp:

synchronized (syncObject) {
  try {
    while(guard) {
      syncObject.wait();    
    }  
  } catch(Exception ex) {    
    // ...  
  }
}

wakeUp:

synchronized (syncObject) {
  // change guard state
  guard = ... 
  // notify of change  
  syncObject.notify();
}

Now we have ensured that the thread will continue its execution when it is supposed toand stays suspended until the guard is changed by the thread that wakes it up. If it’s triggered without the expected guard value (e.g. spurious wake, or explicit wakes that allow other state changes) the thread will just go back to waiting.

It is very important that you actually have something that wakes your threads up from their waiting state. I assume that this is an obvious fact, but you never know. It goes without saying that you have something that wakes your threads up from their  waiting state.   Also, handle the interrupted exceptions when they show up, someone is basically signaling the waiting thread that it should give up whatever it’s doing. 

and, with that said we’ll also cover a non-synchronized approach to locking in…

… Spinning - Spin-lock

Spinning is a technique that sends the current thread in a continuous loop, checking for a condition to become true so it can perform the next operations. It is a method of avoiding normal lock contention for critical sections while allowing access to resources in a manner similar to that of a critical section.

Due to its very CPU intensive nature, spinning is used when it is known that the condition will change very soon and either we want to catch it as soon as it happens, or it is demonstrably less expensive than the cost of relying on contending locks and notifications (e.g. see guarded suspension mechanism.) In some situations, its cost can be somewhat mitigated by introducing pauses in the loop if a good balance between performance and suspension has been found.

A spin-lock is the associated method of obtaining a lock by continuously polling the lock object instead of waiting in a block-wait state for the lock to be assigned.

Since there is no actual synchronization when using a spin-lock, the right structures must be considered during its use, as there is no synchronized state in the fake critical section.

Outside of very specific micro-optimizations, and OS kernel development, there are probably no good reasons to use it, but it’s still an interesting concept.

Here is a small code snippet that shows how the pseudo-locking works:

public class SpinlockSync {
  public volatile int turn = 0;
  Thread th1;
  Thread th2;
  public void start() {
    th1 = new Thread(this::thread1Execute);        
    th2 = new Thread(() -> thread2Execute());        
    // start first thread    
    th1.start();        
    // start second thread    
    th2.start();        
    // main thread spinning until     
    // the other two get close to the end    
    while (turn < 100);
    
    // main thread spinning until    
    // the other two threads are done    
    while (th1.isAlive() || th2.isAlive());
    System.out.println("Done");  
  }  
  public void thread1Execute() {    
    // still in play?    
    while (turn <= 100) {      
      // spin until turn is odd to take over the code      
      while (turn % 2 != 0);
      System.out.println(turn);      
      turn++;
    }    
    System.out.println("Th1 done");  
  }
  
  public void thread2Execute() {    
    // still in play?    
    while (turn <= 100) {      
      // spin until turn is even to take over the code
      while (turn % 2 == 0);
      System.out.println(turn);
      turn++;
    }    
    System.out.println("Th2 done");
  }
  
  public static void main(String[] argv) {    
    (new SpinlockSync()).start();  
  }
}

In the example we are using two threads which contend over executing the same code:

• printing the turn
• incrementing the turn

All the threads are spinning, checking on different conditions to eventually become true so they can move on.

The turn variable is declared as volatile because we need it to be changed by any thread and to be visible in the other, at some point. This approach would not be possible with regular variables that can be cached locally and their value may never reach across the threads.

This code is correct for any version of JAVA, however, keep in mind that volatile, before JAVA 1.4 behaves like the C counterpart, in that a change is eventually reflected in other threads, with no time constraints on what eventually means. After JAVA 1.4, a guarantee was introduced that if one thread reads the value after being set by another thread, it will see the newly set value. This guarantee means that our code will complete fast after 1.4, and it will complete eventually (i.e. fast, today, sometime later this week) before 1.4.

There are alternatives to volatile, such as atomic wrappers, however:

• for our case volatile is faster (after 1.4!)
• if you are on a machine that does not support all the atomic variables, there may be fallback on lock contention for the atomic implementations, which defeats the purpose of our example.

Not using volatile, or atomic, and not managing the conditionals correctly may lead the threads to spin forever and never gaini access to the ”critical” section.