![\"BlockingNonBlocking\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/06\/BlockingNonBlocking.png\")
<\/p>\nBlocking, non-blocking, lock-free, and wait-free. Each of these terms describes a key characteristic of an algorithm when executed in a concurrent environment. So, reasoning about the runtime behavior of your program often means putting your algorithm in the right bucket. Therefore, this post is about buckets.<\/p>\n
<\/p>\n
<\/p>\n
An algorithm fall into one of two buckets: blocking or non-blocking.<\/p>\n
<\/p>\n
<\/p>\n
Let’s first talk about blocking.<\/p>\n
Intuitively, it is quite clear what blocking for an algorithm mean. But concurrency is not about intuition, it’s about precise terms. The easiest way to define blocking is to define it with the help of non-blocking.<\/p>\n
There is not any word about locking in this definition. That’s right. Non-blocking is a broader term.<\/p>\n
To block a program is relatively easy. The typical use case is to use more than one mutex and lock them in a different sequence. Nice timing, and you have a deadlock. But there are a lot more ways to produce blocking behavior.<\/p>\n
Each time you have to wait for a resource, a block is possible.<\/p>\n
Here are a few examples for synchronizing access to a resource:<\/p>\n
Even the join call of a thread can be used to block a thread.<\/p>\n
<\/p>\n
\/\/ deadlockWait.cpp<\/span>\r\n\r\n#include <iostream><\/span>\r\n#include <mutex><\/span>\r\n#include <string><\/span>\r\n#include <thread><\/span>\r\n\r\nstd::<\/span>mutex coutMutex;\r\n\r\nint<\/span> main<\/span>(){\r\n\r\n std::<\/span>thread<\/span> t([]{\r\n std::<\/span>cout <<<\/span> \"Still waiting ...\"<\/span> <<<\/span> std::<\/span>endl; \/\/ 2<\/span>\r\n std::<\/span>lock_guard<<\/span>std::<\/span>mutex><\/span> lockGuard(coutMutex); \/\/ 3<\/span>\r\n std::<\/span>cout <<<\/span> \"child: \"<\/span> <<<\/span> std::<\/span>this_thread::<\/span>get_id() <<<\/span> std::<\/span>endl;}\r\n );\r\n\r\n {\r\n\r\n std::<\/span>lock_guard<<\/span>std::<\/span>mutex><\/span> lockGuard(coutMutex); \/\/ 1<\/span>\r\n std::<\/span>cout <<<\/span> \"creator: \"<\/span> <<<\/span> std::<\/span>this_thread::<\/span>get_id() <<<\/span> std::<\/span>endl;\r\n\r\n t.join(); \/\/ 5<\/span>\r\n\r\n } \/\/ 4<\/span>\r\n\r\n}\r\n<\/pre>\n<\/div>\n <\/p>\n
The program run will block immediately. <\/p>\n
![\"deadlockWait\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/06\/deadlockWait.png\")
<\/p>\n
What is happening? The creator thread locks in (1) the mutex. Now, the child thread executes (2). To get the mutex in expression (3), the creator thread has at first to unlock it. But the creator thread will only unlock the mutex if the lockGuard (1) goes in (4) out of scope. That will never happen because the child thread has at first to lock the mutex coutMutex<\/span>.<\/p>\nLet’s have a look at the non-blocking algorithms.<\/p>\n<\/p>\n
Non-blocking<\/h2>\n
![\"NonBlocking\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/06\/NonBlocking.png\")
<\/p>\n
The main categories for non-blocking algorithms are lock-free and wait-free. Each wait-free algorithm is lock-free, and each lock-free is non-blocking. Non-blocking and lock-free are not the same. There is an additional guarantee called obstruction-free, which I will ignore in this post because it is not so relevant.<\/p>\n
Non-blocking algorithms are typically implemented with CAS instructions. CAS stands for compare and swap. CAS is called compare_exchange_strong<\/span> or compare_exchange_weak<\/span> in C++.<\/p>\nI will in this post only refer to the strong version. For more information, read my previous post The Atomic Boolean<\/a>. The key idea of both operations is a call of atomicValue.compare_exchange_strong(expected, desired<\/span>) obeys the following rules in an atomic fashion.<\/p>\n\n- If the atomic comparison of atomicValue<\/span> with expected returns true<\/span>, atomicValue<\/span> will be set in the same atomic operation as desired<\/span>.<\/li>\n
- If the comparison returns false<\/span>, expected<\/span> will be set to atomicValue<\/span>.<\/li>\n<\/ul>\n
Let’s now have a closer look at lock-free versus wait-free. <\/p>\n
At first, the definition of lock-free and wait-free. Both definitions are quite similar. Therefore, it makes a lot of sense to define them together.<\/p>\n
\n- Lock-free:<\/strong> A non-blocking algorithm is lock-free if there is guaranteed system-wide progress.<\/li>\n
- Wait-free:<\/strong> A non-blocking algorithm is wait-free if there is guaranteed per-thread progress.<\/li>\n<\/ul>\n
Lock-free<\/h3>\n
<\/p>\n
<\/p>\n
\n\/\/ fetch_mult.cpp<\/span>\r\n\r\n#include <atomic><\/span>\r\n#include <iostream><\/span>\r\n\r\ntemplate<\/span> <<\/span>typename<\/span> T><\/span>\r\nT fetch_mult(std::<\/span>atomic<<\/span>T>&<\/span> shared, T mult){ \/\/ 1<\/span>\r\n T oldValue =<\/span> shared.load(); \/\/ 2<\/span>\r\n while<\/span> (!<\/span>shared.compare_exchange_strong(oldValue, oldValue *<\/span> mult)); \/\/ 3<\/span>\r\n return<\/span> oldValue;\r\n}\r\n\r\nint<\/span> main(){\r\n std::<\/span>atomic<<\/span>int<\/span>><\/span> myInt{5<\/span>};\r\n std::<\/span>cout <<<\/span> myInt <<<\/span> std::<\/span>endl; \r\n fetch_mult(myInt,5<\/span>);\r\n std::<\/span>cout <<<\/span> myInt <<<\/span> std::<\/span>endl; \r\n}\r\n<\/pre>\n<\/div>\n <\/p>\n
The algorithm fetch_mult<\/span> (1) multiplies an std::atomic shared<\/span> by mult<\/span>. The critical observation is that there is a small time window between the reading of the old value T oldValue = shared Load<\/span> (2) and the comparison with the new value (3). Therefore, another thread can always kick in and change the oldValue<\/span>. If you reason about such a bad interleaving of threads, you see that there can be no per-thread progress guarantee. <\/p>\nTherefore, the algorithm is lock-free but not wait-free.<\/p>\n
Here is the output of the program.<\/p>\n
![\"fetch](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2016\/06\/fetch_mult.PNG\")
<\/p>\n
<\/p>\n
While a lock-free algorithm guarantees system-wide progress, a wait-free algorithm guarantees per-thread progress.<\/p>\n
Wait-free<\/h3>\n
You will see if you reason about the lock-free algorithm in the last example. A compare_exchange_strong<\/span> call involves synchronization. First, you read the old value, and then update the new value if the initial condition already holds. If the initial condition holds, you publish the new value. If not, you do it again if you put the call in a while loop. Therefore compare_exchange_strong<\/span> behaves like an atomic transaction.<\/p>\nThe crucial part of the following program needs no synchronization.<\/p>\n
<\/p>\n
<\/p>\n
\n\/\/ relaxed.cpp<\/span>\r\n\r\n#include <vector><\/span>\r\n#include <iostream><\/span>\r\n#include <thread><\/span>\r\n#include <atomic><\/span>\r\n \r\nstd::<\/span>atomic<<\/span>int<\/span>><\/span> cnt =<\/span> {0<\/span>};\r\n \r\nvoid<\/span> add<\/span>(){ \/\/ 1<\/span>\r\n for<\/span> (int<\/span> n =<\/span> 0<\/span>; n <<\/span> 1000<\/span>; ++<\/span>n) {\r\n cnt.fetch_add(1<\/span>, std::<\/span>memory_order_relaxed); \/\/ 2<\/span>\r\n }\r\n}\r\n \r\nint<\/span> main<\/span>()\r\n{\r\n std::<\/span>vector<<\/span>std::<\/span>thread<\/span>><\/span> v;\r\n for<\/span> (int<\/span> n =<\/span> 0<\/span>; n <<\/span> 10<\/span>; ++<\/span>n) {\r\n v.emplace_back(add);\r\n }\r\n for<\/span> (auto<\/span>&<\/span> t :<\/span> v) {\r\n t.join();\r\n }\r\n std::<\/span>cout <<<\/span> \"Final counter value is \"<\/span> <<<\/span> cnt <<<\/span> '\\n'<\/span>;\r\n}\r\n<\/pre>\n<\/div>\n <\/p>\n
Have a closer look at function add (1). There is no synchronization involved in expression (2). The value 1 is just added to the atomic cnt<\/span>.<\/p>\nAnd here is the output of the program. We always get 100<\/span>00 because 10 threads increment the value 1000 times.<\/p>\n ![\"relaxed\"](\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2016\/07\/relaxed.png\")
<\/p>\n
For simplicity reasons, I ignored a few other guarantees in this post, such as starvation-free as a subset of blocking or wait-free bounded as a subset of wait-free. You can read the details on the blog Concurrency Freaks<\/a>. <\/p>\nWhat’s next?<\/h2>\n