大家好，又见面了，我是你们的朋友全栈君。涉及到并行/并发计算时，通常都会想到使用锁来保护共享的数据，但锁的使用也存在一些问题：
- 效率降低：由于临界区无法并发运行，进入临界区需要等待，锁的使用导致效率下降。多核CPU也无法充分发挥其性能。
- 死锁风险：在复杂的情况下，很容易造成死锁，导致并发进程或线程之间无止境地互相等待。
- 中断/信号处理函数中的限制：在中断或信号处理函数中不能使用锁，这给并发处理带来了困难。
- 影响实时性：锁会影响实时性，等待时间不确定。
- 优先级反转：高优先级的线程可能需要等待低优先级的线程。
- 线程挂起问题：如果一个线程在持有锁的情况下挂起，会影响其他等待该锁的线程。
总之，在基于锁的多线程/多进程编程中，你需要确保对竞争条件敏感的共享数据上的任何操作，都通过加锁或解锁一个互斥锁（mutex）来实现原子操作。
现有的加锁和无锁编程的种类如下：
其中，标注为红色字体的方案为Blocking synchronization（需要锁），黑色字体的为Non-blocking synchronization（无锁）。Lock-based和Lockless-based两者之间的区别仅仅是加锁粒度的不同。图中最底层的方案就是大家经常使用的mutex和semaphore等方案，代码复杂度低，但运行效率也最低。
立即学习“C++免费学习笔记（深入）”；
可以使用std::atomic来实现lock free编程，但这里并不是真正的无锁，只有atomic_flag是无锁的，其他atomic内部都是有锁的，只不过粒度很小。atomic::compare_exchange_weak/strong等同于CAS（比较并交换）操作，在C++11之前该操作是平台相关的，现在atomic将其实现为成员函数。
下面是一个lock free的栈的示例：
#include <atomic>
#include <memory>
<p>template<typename T>
class lock_free_stack // 栈的底层数据结构采用单向链表实现
{
private:
struct node
{
std::shared_ptr<T> data; // 这里采用shared<em>ptr管理的好处在于：若栈内存放对象，pop中return栈顶对象可能拷贝异常，栈内只存储指针还可以提高性能
node* next;
node(T const& data</em>) : data(std::make<em>shared<T>(data</em>)) // 注意make_shared比直接shared_ptr构造的内存开销小
{}
};
std::atomic<node*> head; // 采用原子类型管理栈顶元素，主要利用atomic::compare_exchange_weak实现lock free</p><p>public:
void push(T const& data)
{
node* const new_node = new node(data);
new_node->next = head.load(); // 每次从链表头插入
while (!head.compare_exchange_weak(new_node->next, new_node)); // 若head==new_node->next则更新head为new_node，返回true结束循环，插入成功；若head!=new_node->next表明有其它线程在此期间对head操作了，将new_node->next更新为新的head，返回false，继续进入下一次while循环。这里采用atomic::compare_exchange_weak比atomic::compare_exchange_strong快，因为compare_exchange_weak可能在元素相等的时候返回false所以适合在循环中，而atomic::compare_exchange_strong保证了比较的正确性，不适合用于循环
}</p><pre class="brush:php;toolbar:false;"><code>std::shared_ptr<T> pop()
{
node* old_head = head.load(); // 拿住栈顶元素，但是可能后续被更新，更新发生在head!=old_head时
while (old_head && !head.compare_exchange_weak(old_head, old_head->next)); // 这里注意首先要先判断old_head是否为nullptr防止操作空链表，然后按照compare_exchange_weak语义更新链表头结点。若head==old_head则更新head为old_head->next并返回true，结束循环，删除栈顶元素成功；若head!=old_head表明在此期间有其它线程操作了head，因此更新old_head为新的head，返回false进入下一轮循环，直至删除成功。
return old_head ? old_head->data : std::shared_ptr<T>(); // 这里注意空链表时返回的是一个空的shared_ptr对象
} // 这里只是lock free，由于while循环可能无限期循环不能在有限步骤内完成，故不是wait free};
发布者：全栈程序员栈长，转载请注明出处：https://www.php.cn/link/46c6a6c72edf42b1335217a9eb4b2325 原文链接：https://www.php.cn/link/c8377ad2a50fb65de28b11cfc628d75c
