An Introduction to Lock-Free Programming / Wunder Fund Blog

wunder_editor February 20, 2017 at 16:02

Introduction to lock-free programming

Transfer

In this post, we would like to once again raise the topic of programming without blocking, first giving it a definition, and then highlighting several key points from the entire variety of information. We will show how these provisions relate to each other using flowcharts, and then we will touch on the details a bit. The minimum requirement for a lock-free developer is the ability to write the correct multi-threaded code using mutexes or other high-level synchronization objects, such as semaphores or events.

Programming without locks (Lock-free) is a kind of test, and not so much because of the complexity of the task itself, but because of the difficulty of understanding the essence of the subject.

I’m fortunate enough to get the first idea of lock-free from Bruce Dawson’s excellent detailed article “Lockless Programming Considerations . " And like so many others, I had the opportunity to apply Bruce's advice in practice, developing and debugging non-blocking code on platforms such as the Xbox 360.

Since then, a lot of good work has been published, starting with abstract theory and proof of correctness and ending with practical examples and details of the hardware level. I will list the links in the notes. Sometimes the information in one source contradicts the other, for example, some jobs require sequential consistency (sequential consistency), which allows you to bypass the memory ordering problems (memory ordering) - a disaster for the C / C ++ code. At the same time, the new C ++ 11 standard atomic operations library It forces us to look at the problem in a new light and abandon the usual way for many to present lock-free algorithms.

What is it?

Usually, non-blocking programming is described as programming without mutexes, which are also called locks . This is true, but it is only part of the picture. The generally accepted definition based on academic literature is a bit wider. “Without locks” is essentially a property that allows you to describe the code without going into details about how it is written.

As a rule, if some part of your program satisfies the conditions listed below, then this part can be fully considered lock-free. And vice versa, if this part does not satisfy these conditions, it will not be lock-free.

Translation: Do you work with multiple threads (interrupts, signal handlers, etc.)? - Yes. - Do threads have access to shared memory? - Yes. - Can threads block each other (in other words, is it possible to plan flows so that they are blocked for an indefinite time)? - Not. - This is programming without locks.

In this sense, the term lock(locking) in lock-free does not refer directly to mutexes, but rather to the possibility that the application itself will somehow be blocked, be it deadlock, dynamic deadlock, or hypothetical thread scheduling by your worst enemy . The last point may seem funny, but it is the key. Shared mutexes are easy to disable: as soon as one thread receives a mutex, your ill-wisher may simply never schedule this thread again. Of course, real operating systems do not work this way, as long as we simply define the terms.

Here is a simple example of an operation that does not contain mutexes, but is still not lock-free. First, X = 0. As an exercise, think about how to plan two threads in such a way that none can exit the loop.

while (X == 0)
{
    X = 1 - X;
}

No one expects a large application to be completely lock-free. Usually, we select a subset of lock-free operations from all the code. For example, in a lock-free queue may be some amount bezblokrovochnyh operations: push, popmay isEmptyetc.

Herlichi and Chavit, the authors of The Art of Multiprocessor Programming , tend to present such operations as class methods and propose the following brief definition of lock-free: "at infinite execution, the method invoked infinitely often always terminates." In other words, while a program can call such lock-free operations, the number of completedCalls will increase. During such operations, locking the system is algorithmically impossible.

One of the important consequences of programming without locks: even if one thread is in the standby state, it will not interfere with the progress of the other threads in their own lock-free operations. This determines the value of programming without blocking when writing interrupt handlers and real-time systems, when a certain task must be completed in a limited period of time, regardless of the state of the rest of the program.

Final clarification: operations specifically designedto lock, do not deprive the algorithm of lock-free status. For example, a pop queue operation may be intentionally blocked if the queue is empty. The remaining paths will still be considered non-blocking.

Programming Mechanisms Without Locks

It turns out that in order to satisfy the condition of the absence of locks, there is a whole family of mechanisms: atomic operations (atomic operations), memory barriers (memory barriers), avoiding ABA problems - these are just some of them. And at that moment everything becomes hellishly complicated.

How do all these mechanisms relate? For illustration, I drew the following flowchart. I will decode each block below.

Atomic change operations (RMW, read-modify-write)

Atomic operations are operations that produce indivisible memory manipulations: no thread can observe such an operation at an intermediate stage of execution. In modern processors, many operations are already atomic. For example, atomic aligned read / write operations of simple types are usually atomic.

RMW operations go even further, allowing atomic execution of more complex transactions. They are especially useful when an algorithm without locks should support multiple threads for writing, because if several threads try to run RMW to a single address, they will quickly line up and perform these operations one at a time. I already touched RMW on this blog when I talked about implementing a lightweight mutex , a recursive mutex, andlightweight logging system .

Examples of RMW operations: _InterlockedIncrementin Win32, OSAtomicAdd32in iOS, and in C ++ 11. Please note that the C ++ 11 atomic operation standard does not guarantee that the implementation will be lock-free on any platform, so it is best to explore the capabilities of your platform and toolkit. To be sure, you can call . Different processor families support RMW in different ways . Processors such as PowerPC and ARM provide LL / SC instructions (load-link / store-conditional, tagged boot / write attempt), which allows you to implement your own RMW transaction at a low level, although this is not often done. Ordinary RMW is usually enough.std::atomic::fetch_addstd::atomic<>::is_lock_free

As shown in the flowchart, atomic RMWs are a necessary part of non-blocking programming, even on uniprocessor systems. Without atomicity, a thread can be interrupted in the middle of a transaction, which can lead to an inconsistent state.

Compare-And-Swap Cycles

Perhaps the most talked about RMW operation is compare-and-swap (CAS). In Win32, CAS is available using a family of built-in functions such as _InterlockedCompareExchange. Developers often run compare-and-swap in a loop to retry the page. This scenario usually involves copying the shared variable to a local one, doing some work on it, and trying to post the changes using CAS.

void LockFreeQueue::push(Node* newHead)
{
    for (;;)
    {
        // Copy a shared variable (m_Head) to a local.
        Node* oldHead = m_Head;
        // Do some speculative work, not yet visible to other threads.
        newHead->next = oldHead;
        // Next, attempt to publish our changes to the shared variable.
        // If the shared variable hasn't changed, the CAS succeeds and we return.
        // Otherwise, repeat.
        if (_InterlockedCompareExchange(&m_Head, newHead, oldHead) == oldHead)
            return;
    }
}

Such cycles are also considered lock-free, because if the test did not pass in one thread, then it should have passed in another, although some architectures offer a weaker version of CAS , where this is not always the case. During the implementation of the CAS cycle, you must try to avoid the ABA problem .

Sequential consistency

Consistent consistency means that all threads agree with the order in which memory operations were performed, and that this order corresponds to the order of operations in the program source code. With consistent consistency, we will not suffer from the tricks of reordering memory like the one I described in a previous post .

A simple (but obviously impractical) way to achieve consistent consistency is to turn off compiler optimizations and run all threads on the same processor. The memory of one processor will never be in a mess, even if threads are scheduled for a random time.

Some programming languages provide consistent consistency even for optimized code that runs on multiple processors. In C ++ 11, you can declare shared variables as atomic types of C ++ 11 that provide ordering. In Java, you can mark all shared variables as volatile. Here is an example from my previous post rewritten in C ++ 11 style:

std::atomic X(0), Y(0);
int r1, r2;
void thread1()
{
    X.store(1);
    r1 = Y.load();
}
void thread2()
{
    Y.store(1);
    r2 = X.load();
}

Since the atomic types of C ++ 11 guarantee consistent consistency, it is impossible to obtain r1 = r2 = 0 at the output. To get the desired result, the compiler adds additional instructions - usually these are memory barriers or RMW operations. Because of these additional instructions, the implementation may be less efficient than the one where the developer works with memory ordering directly.

Memory reordering

As suggested in the flowchart, each time you lock-free development for a multi-core (or any other SMP -) system, when your environment does not guarantee consistent consistency, you need to think about how to deal with the memory reordering problem .

In modern architectures, there are three groups of tools that ensure the correct ordering of memory both at the compiler level and at the processor level :

Lightweight instructions for synchronization and memory barriers, which I will discuss in future posts ;
Full instructions of memory barriers that I demonstrated before ;
Memory operations based on acquire / release semantics (resource acquisition / release semantics).

Acquire semantics provides memory ordering for subsequent operations, release semantics for previous ones. These semantics are partially suitable for the case of producer / consumer relations, when one thread publishes information and the other reads it. We will discuss this in more detail in a future post .

Different processors have different memory models.

When it comes to memory reordering, all CPU families have their own habits . The rules are fixed in the documentation of each manufacturer and are strictly observed in the production of iron. For example, PowerPC or ARM processors can themselves change the order of instructions, and the x86 / 64 family from Intel and AMD usually do not. They say that the former have a weaker memory model .

There is a great temptation to ignore these low-level details, especially when C ++ 11 provides us with a standard way to write portable code without blocking. But I think that at present, most lock-free developers have at least some idea of the difference in hardware platforms. The key difference that you should definitely remember is that, at the instruction level in x86 / 64, each memory load occurs with acquire semantics, and each memory record with release semantics - at least for non-SSE instructions and not for write-combining memory. As a result, they used to write lock-free code quite often, which worked on x86 / 64, but crashed on other processors .

If you are interested in the technical details of how and why processors reorder memory, I recommend reading Appendix C in Is Parallel Programming Hard . In any case, remember that memory reordering may also occur because the compiler reordered the instructions.

In this post, I almost did not touch on the practical side of programming without locking, for example, when is it worth it? How much do we need it? I also did not mention the importance of checking your lock-free algorithms. Nevertheless, I hope that this introduction allowed some readers to get acquainted with the basic principles of lock-free, so that they can further delve into the topic without feeling completely at a loss.