Chinese Yellow Pages | Classifieds | Knowledge | Tax | IME

C++ how to replace mutex code with CAS ( compare and exchange ) ( lock-less programming )

It is well known that if  mutex protected codes could potentially be replaced by atomic compare exchange,  thus we cab achieve lock-less programming.

In practice, it may need several techniques to get it working.

Let’s look at a subscription example:

Normal mutex

An subscriber  can subscribe some content from a publisher, in other word, a publisher can contain a subscription which contains several subscribers.

We can use a container to  hold it, for example:

struct: subscriber {   // could be some complicated struct here }
std::vector<  subscriber  > subs;

If we have one thread to add subs, another thread to distribute content using subs, we need mutex to protect/synchronize the access.

std::mutex mutex;
using Guard = std::scoped_lock<std::mutex>;
//thread 1 , add a new subscription
add_subscriber(sub) { Guard(mutex); subs.push_back( new_sub ); }
// thread 2, remove an subscription
rm_subscriber(old_sub) { Guard(mutex); subs.erase( old_sub ); }
// thread3
show_content_to_subscribers() { Guard(mutex);  for( sub: subs ) { show_content(sub)} ; };

CAS version

We will use a std::shared_ptr to hold those subs,

std::shared_ptr<  const std::vector<subscriber > >  subs;

note we use const, so we make sure our subs will point to a const content.

now the add_subsriber use CAS to modify it:

// thread1
add_subscriber ( const subcriber& sub) {
  // see http://www.comrite.com/wp/c-why-need-atomic_store-atomic_load-on-shared_ptr-atomic-shared_ptr/
  // to know why we need atomic_load here.
  // this guarantee we got a valid shared_ptr to a const subscriptions
  // we could move this inside a while, but
  // atomic_compare_exchange_strong will load it for us for free
  auto old_subs = std::atomic_load(&subs) ;

  while( true ) { // we may need to try several times, since subs may change while we are doing this
      // make a copy of old_subs first
     auto new_subs = std::make_shared< std::vector<subscriber > >( *subs );
     // now add a new sub
     new_subs.push_back( sub );
     // make a new std::shared_ptr to a const place
    std::shared_ptr<const std::vector<subscriber > > const_new_subs = new_subs;
    // now let's CAS it 
    // The key is following
    // C++ will do the following complicated operation atomically for us!!!
    //   if subs == old_subs 
    //     subs = new_subs  // replace subs with new const subs 
    //     return true
    //   else
    //     old_subs = subs // load subs to the old_subs for us for free!
    //     return false
    if(std::atomic_compare_exchange_strong( &subs, &old_subs, const_new_subs))
    {
     // CAS OK, 
     break;
    }
   }
}

With this we can add subscriber  using CAS without any mutex.  The cost we have to pay is some memory copies etc.

Now in thread 2, we can load the subs, and send contend to subscribers

show_content_to_subscriber { 
  // this automic_load will guarantee us 
  // that we got a valid shared_ptr to a const subscriptions 
  auto my_subs = std::atomic_load(&subs) ;
  for( sub: my_subs ) { show_content(sub)} ; 
}

 

 

References:

https://en.cppreference.com/w/cpp/atomic/atomic_compare_exchange

 

c++ why std::shared_ptr need atomic_store, atomic_load or why we need atomic shared_ptr

 

 

 

 

Please rate this


Comments are closed here.