The Spin-Trap Technique

• Download demo - 6.0 KB

Introduction

Low-Lock techniques are expected to become more popular as they promise better performance and scalability with more truly parallel threads supported by hardware. A common low-lock technique is the Spin-Lock which works like a lock but keeps the thread busy waiting and constantly polls until the lock has become available. This avoids the overhead of context switching or process-rescheduling in situations where threads are expected to spend only little time inside the lock.

In this article, I extend the concept of a Spin-Lock to a Spin-Trap and show the relevance of this technique to low-lock classes which feature methods that can be divided into:

1. Concurrent lock-free methods
2. Mutual exclusive methods

An example of such a class is the array-based lock-free queue which I will present in a subsequent article.

How Does the Spin-Trap Work?

A Spin-Trap has, similar to a Spin-Lock, an Enter() and Exit() method which marks the Spin-Trap region. However, the thread which enters a Spin-Trap region does not try to acquire a lock, but increments Spin-Trap's EnteredThreadCount counter at Enter() which it decrements at Exit(). This ensures, that the Spin-Trap class will always know how many threads are currently within all of its Enter-Exit-blocks.

Lock-like behaviour comes with traps, that can be passivated or activated. A Trap() marks defined states within a region of code which can be traversed by all threads if passivated (no-lock) or capture any thread in a spin-lock state if activated (lock). Once trapped, a thread will increment the Spin-Trap's TrappedThreadCount. If the traps get deactivated, all trapped threads will exit and each will decrease TrappedThreadCount by one. TrappedThreadCount can be never greater than EnteredThreadCount.

Any thread can activate all traps by using the AcquireLock() method from within an Enter-Exit region. This function behaves just like a spin-lock: if a thread tries to acquire the lock while another thread owns the lock, it will be spin-locked in a trap-state. ReleaseLock() releases the lock and will cause all threads to exit from their traps. Threads which are trapped inside an AcquireLock() function will try to exit the trap and acquire the lock.

All this would not be of much use without the Wait() function which allows the thread which acquired the lock to wait until each thread except the one which owns the lock either leaves the Enter-Exit blocks or gets trapped in a defined state. Wait() will know when all threads are captured in traps if TrappedThreadCount equals EnteredThreadCount. It is important to note that the number of captured threads is not a constant after Wait() and before ReleaseLock() as more threads can enter and be trapped. This means that all code between a Enter and a Trap can still execute after a Wait() and before the ReleaseLock(). A simple solution to this problem is to place all traps just after the entrance of the spin-trap regions.

In summary: the Spin-Trap provides a mechanism to trap ongoing (concurrent) operations in defined states in order to perform a more extensive operation which requires mutual exclusion and a defined state of the object. As an example, one may think of a lock-free array-based self-resizing Queue where:

1. Enqueue, dequeue operations are concurrent lock-free operations until 
2. An array resize has to take place

It is clear that a. and b. will interfere severely until b. can lock all concurrent threads into defined states. It is also clear, that b. can only be executed in a mutual exclusive manner and requires a lock around its code.

Using the Code

The first step is to identify all concurrent (lock-free) operations within your low-lock class and embed them into a Enter-Trap-Exit construction. The trap can be anywhere and there can be multiple traps in the section, as long as the traps relate to defined states of the object. Also there should be no interfering code between the Enter() and the first Trap(). This applies to the Enqueue() and Dequeue() operations of the queue example:

// somewhere inside our Queue<T> ...
SpinTrap m_spinTrap = new SpinTrap();

public void Enqueue(T item) {
  m_spinTrap.Enter();
  try {
    m_spinTrap.Trap(); 

    // the enqueue code goes here, possibly with some more Trap()s
  } finally {
    m_spinTrap.Exit();
  } 
}

A Trap() just after Enter() is in general a safe place as it captures new threads entering the region before they can do anything to our object. The try-finally section resembles the typical Monitor.Enter(), Monitor.Exit() construction and serves the same purpose: if the thread throws an exception we must notify the SpinTrap that we exit. If not, then SpinTrap will have wrong EnteredThreadCount which will cause a dead-lock on Wait() as TrappedThreadCount can never match EnteredThreadCount!

While the traps are deactivated, things will work like this: concurrent enqueues and dequeues will run through the code and just step over the trap. If the trap becomes active, no thread can pass the trap any more but will instead be captured in a spin-lock state until someone releases the lock.

Let's assume that the queue is running many concurrent enqueues and dequeue operations. Now, one of the threads wants to take an snapshot of the queue using the ToArray() method. Obviously, the enqueues and dequeues must be frozen or the copy may contain corrupted data. Also, array copy should be mutual exclusive with other extensive operations.

This is the second step: put all mutual exclusive operations into a lock-like construction which sets up the traps:

// somewhere inside our Queue<T> ...
public T[] ToArray() {
  m_spinTrap.Enter();
  m_spinTrap.AcquireLock();
  try {
    m_spinTrap.Wait(); 

    // the array-copy code goes here
  } finally {
    m_spinTrap.ReleaseLock();
    m_spinTrap.Exit();
  } 
}

As Enter() goes with AcquireLock(), and ReleaseLock() with Exit(), it makes sense to implement two short-cut methods, named EnterAcquire() and ExitRelease() which allow to shorten the code to:

// somewhere inside our Queue<T> ...
public T[] ToArray() {
  m_spinTrap.EnterAcquire();
  try {
    m_spinTrap.Wait();
 
    // the array-copy code goes here
  } finally {
    m_spinTrap.ExitRelease();
  } 
}

EnterAcquire() will block until a lock is acquired and Wait() will block until all threads inside and Enter-Exit are trapped either in a Trap() or inside the EnterAcquire(). Again, a finally section is needed to ensure that the lock is released and the exit function called under all circumstances.

Example Code

The example code is a simple RingBuffer<T> class featuring an lock-free Enqueue() operation and a ToArray() method to take snapshots of the buffer. The demo code fires multiple threads to perform enqueues while the main thread takes array snapshots of the queue. Admittedly, the buffer should be checked for content, but this is a bit difficult with a ring buffer as old values can be overwritten. Content checks will be much easier with a queue algorithm, which will be part of the next article.

Final Thoughts

The reason why I developed the concept of a Spin-Trap was that I needed this mechanism for a lock-free queue implementation. It seems to me that this technique reflects a general design pattern, which can be applied to code which feature lock-free operations in combination with mutual exclusive methods. Once the code and the tests are finished, I will post the full implementation of my fast lock-free queue algorithm which should underline the usefulness of the presented technique.

As for all code that relates to low-lock programming: nothing can be trusted until you either test it a hundred million times in a thousand different applications or until someone else gives a rigid proof.

History

• 16/11/07: Corrected some typos inside the code sections

References

1. Jeffrey Richter: Concurrent Affairs. Performance Conscious Thread Synchronisation
2. Vance Morrison: Understand the Impact of Low-Lock Techniques in Multi-Threaded Apps
3. Chris Brumme: cbrumme's WebLog: Memory Model