关键词：原子操作，无锁设计

引入问题->   

为什么需要原子操作->

原子操作实现以及原理->

c++原子操作接口->

c++基于原子操作的数据结构设计->

原子操作

什么是原子操作

　　所谓原子操作,就是"不可中断的一个或一系列操作" 。

2.    硬件级的原子操作

在单处理器系统(UniProcessor)中，能够在单条指令中完成的操作都可以认为是" 原子操作"，因为中断只能发生于指令之间。这也是某些CPU指令系统中引入了test_and_set、test_and_clear等指令用于临界资源互斥的原因。

        在对称多处理器(Symmetric Multi-Processor)结构中就不同了，由于系统中有多个处理器在独立地运行，即使能在单条指令中完成的操作也有可能受到干扰。

3.    软件级的原子操作

　　软件级的原子操作实现依赖于硬件原子操作的支持。 对于linux而言，内核提供了两组原子操作接口：一组是针对整数进行操作；另一组是针对单独的位进行操作。

linux内核原子操作

C++原子操作接口

原子指令用于在多个CPU之间维护同步关系。在一些科学计算问题中，通过并行算法把子问题分配到多个cpu上执行，但是各个子问题之间存在合作关系，因此需要硬件机制来实现多个cpu之间同步。

每个 std::atomic 模板的实例化和全特化定义一个原子类型。若一个线程写入原子对象，同时另一线程从它读取，则行为良好定义（数据竞争的细节见内存模型）。

另外，对原子对象的访问可以建立线程间同步，并按 std::memory_order （内存次序）所对非原子内存访问定序。

std::atomic 既不可复制亦不可移动。

还有一些其他的类型别名，可以参见std::atomic。

他们全部具备成员函数is_lock_free()，准许使用者判定某一给定的类型上的操作是由原子指令（atomic instruction）直接实现(x.is_lock_free()返回true)，还是要借助编译器和程序库的内部锁来实现（x.is_lock_free()返回false）。

成员函数

比较-交换

这一操作被称为”比较-交换“（compare-exchange），实现形式是成员函数compare_exchange_weak()和compare_exchange_strong()。

使用者给定一个期望值，原子变量将它和自身的值做比较，如果相等，就传入另一个既定的值；否则，更新期望值所属的变量，向它赋予原子变量的值。

比较交换函数返回布尔类型，如果完成了保存动作（前提是两值相等），则操作成功，函数返回ture,反之操作失败，函数返回false。

compare_exchange_weak()

对于compare_exchange_weak()，即使原子变量的值等于期望值，保存动作还是有可能失败，在这种情形下，原子变量维持不变，compare_exchange_weak()返回false;

原子化的比较-交换必须由一条指令单独完成，而某些处理器没有这种指令，无法保证该操作按原子化方式完成。

要实现比较-交换，负责的线程则必须改为连续运行一些列指令，但在这些计算机上，只要出现线程数量多于处理器数量的情形，线程就有可能执行到中途因系统调度而切出，导致操作失败。

这种计算机最有可能引发上述的保存失败，我们称之为佯败（spurious failure）。其因败因不算变量值本身存在问题，而是函数执行时机不对。

因为compare_exchange_weak()可能佯败，所以它必须配合循环使用。

#include <iostream>
#include <atomic>using namespace std;int main()
{bool expected = false;extern atomic<bool> b; //由其他源文件的代码设定变量的值while(!b.compare_exchange_weak(expected, true) && !expected);{cout << "b=" << b << endl;}return 0;
}atomic<bool> b;

compare_exchange_strong()

只有当原子变量的值不符合预期时，compare_exchange_strong()才返回false。

这让我们得以明确知悉变量是否成功修改，或者是否存在另一线程抢先切入而导致佯败，从而能够摆脱上例所示的循环。

compare_exchange_weak()和compare_exchange_strong()使用场景对比

• 在某些平台上，虽然使用compare_exchange_weak()可能导致佯败，但改用compare_exchange_strong()却会形成双重循环（因为compare_exchange_strong()自身内部含有一个循环），那么采用compare_exchange_weak()比较有利于性能。

• 反之，如果存入的值需要耗时的计算，选择compare_exchange_strong()则更加合理。因为只要预期值没有变化，就可避免重复计算。

特化成员函数

std:atomic<T*>

 std::atomic 模板可用任何满足可复制构造 (CopyConstructible) 及可复制赋值 (CopyAssignable) 的可平凡复制 (TriviallyCopyable) 类型 T 特化。

#include <iostream>
#include <atomic>
#include<cassert>using namespace std;class foo {};int main()
{foo foo_array[5];// 可以和boo类型类比，定义一个foo*指针，初始值是数组的第一个对象。atomic<foo*> p(foo_array);foo* x = p.fetch_add(2);	// 令p+2,返回旧址。assert(x==foo_array);assert(p.load() == &foo_array[2]);x = (p -= 1);     //令p-1,返回新值assert(x == &foo_array[1]);assert(p.load() == &foo_array[1]);return 0;
}

无锁数据结构-无锁队列

待补充！

参考文档：

C++之原子操作（atomic）

C++之原子操作（atomic）_c++ 原子操作_小谢%同学的博客-CSDN博客

【并发编程十三】c++原子操作(1)

https://zhengjunxue.blog.csdn.net/article/details/128727418

C++ 参考手册

C++ 参考手册 - C++中文 - API参考文档

C++ 11 多线程初探-std::memory_order

https://www.cnblogs.com/lizhanzhe/p/10893016.html