bsls_spinlock Component

Provide a spin lock. More...

Namespaces
namespace	bsls

Detailed Description

Outline

Purpose
Classes
Description
- Usage
  - Example 1: Maintaining Static Count/Max Values
  - Example 2: Fine-Grained Locking

Purpose:: Provide a spin lock.

Classes:

bsls::SpinLock	A mutex using "busy waiting" atomic operations
bsls::SpinLockGuard	Automatic locking-unlocking of SpinLock

Description:: This component provides a "busy wait" mutual exclusion lock primitive ("mutex"). A SpinLock is small and statically-initializable, but because it "spins" in a tight loop rather than using system operations to block the thread of execution, it is unsuited for use cases involving high contention or long critical regions. Additionally, this component does not provide any guarantee of fairness when multiple threads are contending for the same lock. Use SpinLockGuard for automatic locking-unlocking in a scope.

WARNING: A bsls::SpinLock must be aggregate initialized to BSLS_SPINLOCK_UNLOCKED. For example:

  bsls::SpinLock lock = BSLS_SPINLOCK_UNLOCKED;

Note that SpinLock is a struct requiring aggregate initialization to allow lock variables to be statically initialized when using a C++03 compiler (i.e., without using constexpr).

Usage:: In this section we show intended use of this component.

Example 1: Maintaining Static Count/Max Values:: Suppose that we want to determine the maximum number of threads executing a block of code concurrently. Note that such a use case naturally calls for a statically initialized lock and the critical region involves a few integer operations; SpinLock may be suitable.

First, we define a type to manage the count within a scope:

 class MaxConcurrencyCounter {
     // This type manages a count and high-water-mark within a scope.
     // It decrements the count in its destructor upon leaving the scope.

     // DATA
     int            *d_count_p;
     bsls::SpinLock *d_lock_p;

   public:
     // CREATORS
     MaxConcurrencyCounter(int *count, int *max, bsls::SpinLock *lock);
         // Acquire the specified 'lock' and increment the specified 'count'.
         // If the resulting value is larger than the specified 'max',
         // load it into 'max'. Release 'lock' and create a scoped guard to
         // decrement 'count' on destruction.

     ~MaxConcurrencyCounter();
         // Acquire the lock specified at construction, decrement the count
         // variable, and release the lock.
   };

   MaxConcurrencyCounter::MaxConcurrencyCounter(int            *count,
                                                int            *max,
                                                bsls::SpinLock *lock)
   : d_count_p(count)
   , d_lock_p(lock) {
      bsls::SpinLockGuard guard(lock);
      int result = ++(*count);
      if (result > *max) {
         *max = result;
      }
   }

   MaxConcurrencyCounter::~MaxConcurrencyCounter() {
      bsls::SpinLockGuard guard(d_lock_p);
      --(*d_count_p);
   }

Next, we declare static variables to track the call count and a SpinLock to guard them. SpinLock may be statically initialized using the BSLS_SPINLOCK_UNLOCKED constant:

   {
      static int            threadCount = 0;
      static int            maxThreads = 0;
      static bsls::SpinLock threadLock = BSLS_SPINLOCK_UNLOCKED;

Next, by creating a MaxConcurrencyCounter object, each thread entering the block of code uses the SpinLock to synchronize manipulation of the static count variables:

      MaxConcurrencyCounter counter(&threadCount, &maxThreads, &threadLock);

Finally, closing the block synchronizes on the SpinLock again to decrement the thread count. Any intervening code can run in parallel.

Example 2: Fine-Grained Locking:: Suppose that we have a large array of objects to be manipulated concurrently by multiple threads, but the size of the array itself does not change. (This might be because it represents an inherently fixed number of objects or because changes to the array size are infrequent and controlled by some other synchronization mechanism like a "reader-writer" lock). Thus one thread can manipulate a particular object in the array concurrently with a different thread manipulating another. If the manipulations are short and contention is likely to be low, SpinLock might be suitable due to its small size.

In particular, imagine we want a threadsafe "multi-queue". In this case, we would have an array of queues, each with a SpinLock member for fine-grained locking. First, we define the type to be held in the array.

  template<typename TYPE>
  class LightweightThreadsafeQueue {
     // This type implements a threadsafe queue with a small memory
     // footprint and low initialization costs. It is designed for
     // low-contention use only.

     // TYPES
     struct Node {
          TYPE  d_item;
          Node *d_next_p;

          Node(const TYPE& item) : d_item(item), d_next_p(0) {}
      };

     // DATA
     Node           *d_front_p; // Front of queue, or 0 if empty
     Node           *d_back_p; // Back of queue, or 0 if empty
     bsls::SpinLock  d_lock;

   public:
     // CREATORS
     LightweightThreadsafeQueue();
       // Create an empty queue.

     ~LightweightThreadsafeQueue();
       // Destroy this object.

     // MANIPULATORS
     int dequeue(TYPE* value);
        // Remove the element at the front of the queue and load it into the
        // specified 'value'. Return '0' on success, or a nonzero value if
        // the queue is empty.

     void enqueue(const TYPE& value);
        // Add the specified 'value' to the back of the queue.
   };

Next, we implement the creators. Note that a different idiom is used to initialize member variables of SpinLock type than is used for static variables:

  template<typename TYPE>
  LightweightThreadsafeQueue<TYPE>::LightweightThreadsafeQueue()
  : d_front_p(0)
  , d_back_p(0)
  , d_lock(bsls::SpinLock::s_unlocked)
  {}

  template<typename TYPE>
  LightweightThreadsafeQueue<TYPE>::~LightweightThreadsafeQueue() {
     for (Node *node = d_front_p; 0 != node; ) {
         Node *next = node->d_next_p;
         delete node;
         node = next;
     }
  }

Then we implement the manipulator functions using SpinLockGuard to ensure thread safety. Note that we do memory allocation and deallocation outside the scope of the lock, as these may involve system calls that should be avoided in the scope of a SpinLock.

  template<typename TYPE>
  int LightweightThreadsafeQueue<TYPE>::dequeue(TYPE* value) {
     Node *front;
     {
        bsls::SpinLockGuard guard(&d_lock);
        front = d_front_p;
        if (0 == front) {
          return 1;
        }

        *value = front->d_item;

        if (d_back_p == front) {
           d_front_p = d_back_p = 0;
        } else {
           d_front_p = front->d_next_p;
        }
     }
     delete front;
     return 0;
  }

  template<typename TYPE>
  void LightweightThreadsafeQueue<TYPE>::enqueue(const TYPE& value) {
     Node *node = new Node(value);
     bsls::SpinLockGuard guard(&d_lock);
     if (0 == d_front_p && 0 == d_back_p) {
        d_front_p = d_back_p = node;
     } else {
        d_back_p->d_next_p = node;
        d_back_p = node;
     }
  }

To illustrate fine-grained locking with this queue, we create a thread function that will manipulate queues out of a large array at random. Since each element in the array is locked independently, these threads will rarely contend for the same queue and can run largely in parallel.

 const int NUM_QUEUES = 10000;
 const int NUM_ITERATIONS = 20000;

 struct QueueElement {
    int d_threadId;
    int d_value;
 };

 struct ThreadParam {
    LightweightThreadsafeQueue<QueueElement> *d_queues_p;
    int                                       d_threadId;
 };

 void *addToRandomQueues(void *paramAddr) {
    ThreadParam *param = (ThreadParam*)paramAddr;
    LightweightThreadsafeQueue<QueueElement> *queues = param->d_queues_p;
    int threadId = param->d_threadId;
    unsigned seed = threadId;
    for (int i = 0; i < NUM_ITERATIONS; ++i) {
       int queueIndex = rand_r(&seed) % NUM_QUEUES;
       LightweightThreadsafeQueue<QueueElement> *queue = queues + queueIndex;
       QueueElement value = { threadId, i };
       queue->enqueue(value);
    }
    return 0;
 }

Finally, we create the "multi-queue" and several of these threads to manipulate it. We assume the existence of a createThread() function that starts a new thread of execution with a parameter, and we omit details of "joining" these threads.

 enum { NUM_THREADS = 3};
 LightweightThreadsafeQueue<QueueElement> multiQueue[NUM_QUEUES];
 ThreadParam threadParams[NUM_THREADS];
 for (int i = 0; i < NUM_THREADS; ++i) {
   threadParams[i].d_queues_p = multiQueue;
   threadParams[i].d_threadId = i + 1;
   createThread(addToRandomQueues, threadParams + i);
 }

Component bsls_spinlock [Package bsls]

Namespaces

Detailed Description

Component bsls_spinlock
[Package bsls]