Atomics And Concurrency | Zaid Humayun’s Weblog

2024-01-12 00:28:43

That is going to be an extended submit, however I hope you get worth out of it. This wasn’t a simple subject to sort out nevertheless it was undoubtedly worthwhile!

Hopefully, you allow with a good understanding of how reminiscence ordering works and learn how to use atomics at the side of reminiscence ordering to construct a lock-free queue in C++.

Notice: If you wish to really compile the code and run it, ensure to take action with the TSan flag enabled for the CLang compiler. TSan is a dependable approach of detecting information races in your code, as a substitute of attempting to repeatedly run the code in a loop hoping for an information race to happen.

Think about you may have both some concurrent code working on some shared information in reminiscence. You might have two threads or processes, one writing and one studying on some shared piece of state.

The “protected” approach of coping with that is mutexes. Nonetheless, mutexes have a tendency so as to add overhead. Atomics are a extra performant however far more sophisticated approach of coping with concurrent operations.

Atomics

This part may be very easy. Atomics are merely operations or directions that can not be cut up by the compiler or the CPU or re-ordered in any approach.

The only attainable instance of an atomic in C++ is an atomic flag

#embrace <atomic>

std::atomic<bool> flag(false);

int predominant() {
  flag.retailer(true);
  assert(flag.load() == true);
}

We outline an atomic boolean, initialise it after which name retailer on it. This methodology units the worth on the flag. You’ll be able to then load the flag from reminiscence and assert its worth.

Operations With Atomics

The operations you may carry out with atomics are easy:

You’ll be able to retailer some worth into them with a retailer() methodology. It is a write operation.
You’ll be able to load some worth from them with a load() methodology. It is a learn operation,
You are able to do a Evaluate-and-Set(CAS) with them utilizing a compare_exchange_weak() or compare_exchange_strong() methodology. It is a read-modify-write(RMW) operation.

The necessary factor to recollect is that every of those can’t be cut up into separate directions.

Notice: There are extra strategies accessible, however that is all we’d like for now

There are numerous atomics accessible in C++ and you need to use them together with reminiscence orderings.

Reminiscence Ordering

This part is much more sophisticated and is the meat of the matter. There are some nice references for understanding this I’ve linked on the backside.

Why It Issues

The compiler and CPU are able to re-ordering your program directions, usually independently of each other. That’s, your compiler can re-order directions and your CPU can re-order directions once more. See here.

Nonetheless, that is solely allowed if the compiler can undoubtedly not set up a relationship between the 2 units of directions.

For example, this may be re-ordered as a result of there isn’t any relationship between the task to x and the task to y. That’s, the compiler or CPU would possibly assign y first after which x. However, this doesn’t change the semantic which means of your program.

Nonetheless, the code beneath can’t be re-ordered as a result of the compiler can’t set up the absence of a relationship between x and y. It’s apparent to see right here as a result of y will depend on the worth of x.

int x = 10;
int y = x + 1;

It doesn’t appear to be a giant drawback till there’s multi-threaded code.

Instinct For Ordering

#embrace <cassert>
#embrace <thread>

int information = 0;

void producer() {
  information = 100;  // Write information
}

void shopper() {
  assert(information == 100);
}

int predominant() {
  std::thread t1(producer);
  std::thread t2(shopper);
  t1.be part of();
  t2.be part of();
  return 0;
}

The multi-threaded instance above will fail to compile with TSan as a result of there’s a clear information race when thread 1 is attempting to set the worth of information and thread 2 is attempting to learn the worth of information. The simple reply here’s a mutex to guard the write & learn of information however there’s a approach to do that with an atomic boolean.

We loop on the atomic boolean till we discover that it’s set to the worth we’re in search of after which test the the worth of information.

#embrace <atomic>
#embrace <cassert>
#embrace <thread>

int information = 0;
std::atomic<bool> prepared(false);

void producer() {
  information = 100;
  prepared.retailer(true);  // Set flag
}

void shopper() {
  whereas (!prepared.load())
    ;
  assert(information == 100);
}

int predominant() {
  std::thread t1(producer);
  std::thread t2(shopper);
  t1.be part of();
  t2.be part of();
  return 0;
}

Once you compile this with TSan, it doesn’t complain about any race situations. Notice: I’m going to refer again to why TSan doesn’t complain right here.

Now, I’m going to interrupt it by including a reminiscence ordering assure to it. Simply exchange prepared.retailer(true); with prepared.retailer(true, std::memory_order_relaxed); and exchange whereas (!prepared.load()) with whereas (!prepared.load(std::memory_order_relaxed)).

TSan will complain that there’s a information race. However, why is it complaining?

The problem right here is that now we have no order among the many operations of the 2 threads anymore. The compiler or CPU is free to re-order directions within the two threads. If we return to our summary visualisation from earlier, that is what it appears to be like like now.

The visualisation above reveals us that our two processes (threads) don’t have any approach of agreeing upon the present state or the order by which that state has modified.

As soon as course of 2 determines that the flag has been set to true, it tries to learn the worth of information. However, thread 2 believes that the worth of information has not but modified despite the fact that it believes the worth of flag has been set to true.

That is complicated as a result of the basic mannequin of interleaving concurrent operations doesn’t apply right here. Within the basic mannequin of concurrent operations, there may be at all times some order that may be established. For example, we will say that that is one attainable situation of operations.

Thread 1                  Reminiscence                  Thread 2
---------                 -------                 ---------
  |                          |                          |
  |   write(information, 100)       |                          |
  | -----------------------> |                          |
  |                          |     load(prepared) == true  |
  |                          | <----------------------  |
  |                          |                          |
  |   retailer(prepared, true)     |                          |
  | -----------------------> |                          |
  |                          |                          |
  |                          |       learn(information)         |
  |                          | <----------------------  |
  |                          |                          |

However, the above graphic assumes that each threads have agreed upon some world order of occasions, which isn’t true in any respect anymore! That is nonetheless complicated for me to wrap my head round.

In a memory_order_relaxed mode, two threads don’t have any approach of agreeing upon the order of operations on shared variables. From thread 1’s standpoint, the operations it executed have been

write(information, 100)
retailer(prepared, true)

Nonetheless, from thread 2’s standpoint, the order of operations it noticed thread 1 execute have been

retailer(prepared, true)
write(information, 100)

With out agreeing upon the order by which operations occurred on shared variables, it isn’t protected to make adjustments to these variables throughout threads.

Okay, let’s repair the code by changing std::memory_order_relax with std::memory_order_seq_cst.

So, prepared.retailer(true, std::memory_order_relaxed); turns into prepared.retailer(true, std::memory_order_seq_cst); and whereas (!prepared.load(std::memory_order_relaxed)) turns into whereas (!prepared.load(std::memory_order_seq_cst)).

When you run this once more with TSan, there are not any extra information races. However why did that repair it?

Reminiscence Barrier

So, we noticed our drawback earlier was about two threads being unable to agree upon a single view of occasions and we wished to stop that. So, we launched a barrier utilizing sequential consistency.

Thread 1                  Reminiscence                  Thread 2
---------                 -------                 ---------
  |                          |                          |
  |   write(information, 100)       |                          |
  | -----------------------> |                          |
  |                          |                          |
  |  ================Reminiscence Barrier===================  |
  |   retailer(prepared, true)     |                          |
  | -----------------------> |                          |
  |                          |   load(prepared) == true    |                   
  |                          | <----------------------  |
  |  ================Reminiscence Barrier===================  |
  |                          |                          |
  |                          |       learn(information)         |
  |                          | <----------------------  |
  |                          |                          |

The reminiscence barrier right here says that nothing earlier than the shop operation and nothing after the load operation could be re-ordered. That’s, thread 2 now has a assure that the compiler or the CPU is not going to place the write to information after the write to the flag in thread 1. Equally, the learn operation in thread 2 can’t be re-ordered above the reminiscence barrier.

The area contained in the reminiscence barrier is akin to a crucial part {that a} thread must a mutex to enter. We now have a method to synchronise the 2 threads on the order of occasions throughout them.

This brings us again to our basic mannequin of interleaving in concurrency as a result of we now have an order of occasions each threads agree upon.

Sorts Of Reminiscence Order

There are 3 predominant sorts of reminiscence order:

Relaxed reminiscence mannequin (std::memory_order_relaxed)
Launch-acquire reminiscence mannequin (std::memory_order_release and std::memory_order_acquire)
Sequentially constant reminiscence order (std::memory_order_seq_cst)

We already lined 1 & 3 within the examples above. The second reminiscence mannequin actually lies between the opposite two by way of consistency.

#embrace <atomic>
#embrace <cassert>
#embrace <iostream>
#embrace <thread>

int information = 0;
std::atomic<bool> prepared(false);

void producer() {
  information = 100;
  prepared.retailer(true, std::memory_order_release);  // Set flag
}

void shopper() {
  whereas (!prepared.load(std::memory_order_acquire))
    ;
  assert(information == 100);
}

int predominant() {
  std::thread t1(producer);
  std::thread t2(shopper);
  t1.be part of();
  t2.be part of();
  return 0;
}

The above is identical instance from earlier, count on with std::memory_order_release used for prepared.retailer() and memory_order_acquire used for learn.load(). The instinct right here for ordering is much like the pervious reminiscence barrier instance.

Besides, this time the reminiscence barrier is shaped on the pair of prepared.retailer() and prepared.load() operations and can solely work when used on the identical atomic variable throughout threads. Assuming you may have a variable x being modified throughout 2 threads, you could possibly do x.retailer(std::memory_order_release) in thread 1 and x.load(std::memory_order_acquire) in thread 2 and you’ll have a synchronization level throughout the 2 threads on this variable.

The distinction between the sequentially constant mannequin and the release-acquire mannequin is that the previous enforces a world order of operations throughout all threads, whereas the latter enforces an order solely amongst pairs of launch and purchase operations.

Now, we will revisit why TSan didn’t complain a couple of information race initially when there was no reminiscence order specified. It’s as a result of C++ by default assumes a std::memory_order_seq_cst when no reminiscence order is specified. Since that is the strongest reminiscence mannequin, there isn’t any information race attainable.

{Hardware} Concerns

Totally different reminiscence fashions have completely different efficiency penalties on completely different {hardware}.

For example, the x86 architectures instruction set implements one thing referred to as whole retailer ordering (TSO). The gist of it’s that the mannequin resembles all threads studying and writing to a shared reminiscence. You’ll be able to learn extra here

Which means the x86 processors can present sequential consistency for a comparatively low computational penalty.

On the opposite aspect are the ARM household of processors has a weakly ordered instruction set structure. It is because every thread or course of reads and writes to its personal reminiscence. Once more, the hyperlink above supplies context.

Which means the ARM processors present sequential consistency for a a lot increased computational penalty.

Constructing A Concurrent Queue

I’m going to make use of the operations now we have mentioned to date to construct the fundamental operations of a lock-free concurrent queue. That is on no account even an entire implementation, simply my try and re-create one thing primary utilizing atomics.

I’m going to signify the queue utilizing a linked checklist and wrap every node inside an atomic.

class lock_free_queue {
 personal:
  struct node {
    std::shared_ptr<T> information;
    std::atomic<node*> subsequent;

    node() : subsequent(nullptr) {}  //  initialise the node
  };

  std::atomic<node*> head;
  std::atomic<node*> tail;
}

Now, for the enqueue operation, that is what its going to appear to be

void enqueue(T worth) {
    std::shared_ptr<T> new_data = std::make_shared<T>(worth);
    node* new_node = new node();
    new_node->information = new_data;

    //  do an infinite loop to alter the tail
    whereas (true) {
      node* current_tail = this->tail.load(std::memory_order_acquire);
      node* tail_next = current_tail->subsequent;

      //  all the things is right to date, try the swap
      if (current_tail->subsequent.compare_exchange_strong(
              tail_next, new_node, std::memory_order_release)) {
        this->tail = new_node;
        break;
      }
    }
  }

The principle focus is on the load and compare_exchange_strong operations. The load works with a purchase and the CAS works with a launch in order that reads and writes to the tail are synchronized.

Equally for the dequeue operation

std::shared_ptr<T> dequeue() {
    std::shared_ptr<T> return_value = nullptr;

    //  do an infinite loop the change the top
    whereas (true) {
      node* current_head = this->head.load(std::memory_order_acquire);
      node* next_node = current_head->subsequent;

      if (this->head.compare_exchange_strong(current_head, next_node,
                                             std::memory_order_release)) {
        return_value.swap(next_node->information);
        delete current_head;
        break;
      }
    }
    return return_value;
  }

Notice: This queue doesn’t deal with the ABA problem. This weblog submit is just too lengthy to herald hazard pointers, so I’m leaving that out

So there you may have it. Atomics in C++. Very sophisticated and there may be zero probability I’d ever put this into manufacturing. Particularly as a result of I’m pretty sure my concurrent queue would break 😉

If you’d like entry to the code talked about above, take a look at this file and this file.