告诉你关于多线程的一切

　　进程内的多个线程共享同一虚拟地址空间，每个线程都是一个独立的执行流，所以，多个线程对应多个执行流，多个执行流会竞争同一资源的情况，资源包括内存数据、打开的文件句柄、套接字等，如果不加以控制和协调，则有可能出现数据不一致，而这种数据不一致可能导致结果错误，甚至程序奔溃，因此，需要努力避免。
　　并发编程的错误非常诡谲且难以定位，它总是隐藏在某个的角落，大多数时候，程序运转良好，等代码交付上线后，莫名其妙的出错，就像墨菲定律描述的那样：凡是可能出错，就一定会出错。
　　## 数据不一致源于什么？
　　CPU与内存访问性能差距很大，Cache被作为内存的缓存插入到CPU与内存之间，数据会在Cache里缓存内存数据的副本，内存数据与缓存数据不总是一致。
　　比如修改变量（写入数据），如果采取写穿透（Write Through）的方式，则会在更新缓存中对应的Cache Line的同时把数据写入内存，如果数据不在缓存，则直接写入内存，但每次写操作都写入内存，而内存的访问时延通常高达几十个指令周期，这种写的方式性能太低。而采用写回（Write Back）的方式，如数据在Local Cache里，则更新缓存后就直接返回，这样就减少访问内存的频率，也就提升了性能，但这样的话，内存数据和Cache里的数据是不一致的。
　　现代处理器朝着多CPU多核架构发展，每个核有自己的L1/L2 Cache ，核之间共享L3 Cache，然后再通过总线连接内存，内存被所有CPU/Core所共享，所以，一个内存数据会被多个CPU/Core Cache，不仅内存与Cache中的数据可能不一致，Cache里的多份拷贝也会不一致，Cache一致性协议用于处理这个问题。
　　## CPU如何使用内存数据？ CPU通常不会直接操作内存
　　- 这是因为有些指令对操作数有限制，比如X86-64限制mov指令的源和目的操作数不能都是内存地址，所以把一个字节从一个内存地址复制到另一个内存地址，需要两条mov汇编指令，先从源地址move到寄存器，再从寄存器move到目标地址
　　- 即使mov的一个操作数是内存地址，实际上，CPU处理的时候，也会先将内存地址的数据加载到Cache Line，再作用于Cache Line，而非直接修改内存
　　多CPU多核系统上，如果Core的local Cache没有对应变量的数据，它并不是只有从内存里加载数据到Cache这一条路，而是会通过CPU/Core间消息，从别的CPU/Core的Cache里拿数据的拷贝，这个核间消息不是通过共享的总线传递，而是基于Interconnect的message passing
　　- 当某个Core更新Local Cache里的数据时，它需要通过CPU/Core间消息把这个写入操作传播到其他Core的Cache，如果其他Core也Cache了这个数据，要让对应Cache Line失效，这个叫写传播（Write Propagation），总线嗅探通过感知到核间消息来实现写传播
　　- 另外，某个CPU核心里对数据的操作顺序，必须在其他核心看起来顺序是一样的，这个称为事务的串形化（Transaction Serialization），而做到这一点，则需要CPU的缓存更新需要引入‘锁’的概念，多个核心有相同数据的Cache，那么对于数据的更新，只有拿到锁进行，而基于总线嗅探实现的MESI协议就是为了实现事务串行化，如果一个数据在某个Core的Cache Line是独占（Exclusive）状态，则它相当于拿到了自由修改权，如果一个数据被加载到多个Core的Cache，则是Shared的状态，这时候，需要通过向其他核广播请求，Invalidate其他核里的Cache Line才能修改。
　　## 为什么需要多线程同步？
　　我们先用2个例子来描述，如果不做线程同步，程序会出现什么问题。
　　### 例子1
　　有一个货物售卖程序，变量int item_num记录某商品的数量，它被初始值为100（代表可售卖数量为100）。售卖函数检查剩余商品数，如果剩余商品数大于等于售卖数量，则扣除商品件数，并返回成功；否则，返回失败。代码如下：
　　```c++
　　bool sell(int num) {
　　if (item_num >= num) {
　　item_num -= num;
　　return true;
　　}
　　return false;
　　}
　　```
　　单线程下，sell函数被多次调用，程序运转良好，结果符合预期，但在多线程环境下，会出错。
　　为了理解上述代码行为，需要先了解一个基本事实：程序变量存放在内存中，对变量做加减，会先将变量加载到通用寄存器，再执行算术运算（更新寄存器中的值），最后把寄存器的新值存入内存位置。
　　寄存器里会保存内存变量值的副本，对变量的加减乘除等运算直接作用于副本，而非变量内存位置。不过，如果对变量赋值，则指令会接受一个内存位置作为操作数，指令会直接操作内存位置。
　　#### 多核并行
　　- 假设线程t1和线程t2，分别在core1和core2同时执行，t1执行sell(50), t2执行sell(100)。
　　- 2个线程代表2个执行（指令）流，如果2个执行流同时执行到if (item_num >= num)这一行判断语句。
　　- 内存位置保存的item_num的值会被分别加载到2个核心的寄存器，因为item的值为100，所以加载到寄存器后也都为100，2个线程的条件检查都顺利通过。
　　- 线程t1，执行减法运算item_num -= num，参数num为50，结果为100-50=50，更新寄存器。
　　- 线程t2，执行减法运算item_num -= num，参数num为100，结果为100-100=0，更新寄存器。
　　- 然后，t1和t2线程先后把各自寄存器里的新值store到内存，后一个线程的store操作会覆盖前值。
　　- 如果t1线程先store，内存中的item_num被修改为50，t2线程再执行store，内存中的item_num被覆盖，item_num值被替换为0。
　　- 如果t2线程先store，t1线程后store，则item_num的最终值为50。
　　无论哪种情况，结果都是错误的，我们只有100件商品，却超卖出150件。
　　#### 单核并发
　　- 如果程序在单CPU单Core的机器上运行，t1线程和t2线程并发（非并行）交错执行，因为只有一个CPU，所以同一时刻，只有一个线程在执行。
　　- 假设t1在CPU上执行，它把item_num(100) load到寄存器，判断通过(100 >= 100)。
　　- 这时候，发生线程调度（比如t1的时间配额耗尽），t2被调度到CPU上执行，然后t2依次完成load、check、compute和store操作。
　　- 然后t1又被调度到CPU上恢复执行，t1会直接用寄存器中的item_num副本（100），执行计算，item -= 50的结果为50，更新寄存器，所以t1线程执行后，新值50被store入item_num所在内存。
　　- 我们期望t1或者t2的sell只有一个操作成功，但结果并非如此。
　　CPU核相当于工人，而程序线程相当于任务，核的数量决定了并行度，多个核代表多个任务可以被同时执行，但多线程竞争导致数据的不一致，在单核环境也有可能出现。
　　让我们再看一个计数的例子：
　　### 例子2
　　全局变量int count用来计数，我们启动100个线程，每个线程的处理逻辑：在100次循环里累加count；主函数启动线程并等待所有线程执行完成，程序退出前打印count数值，代码如下:
　　#include #include int count = 0;void thread_proc() { for (int i = 0; i < 100; ++i) { ++count; }}int main() { std::thread threads[100]; for (auto &x : threads) { x = std::move(std::thread(thread_proc)); } for (auto &x : threads) { x.join(); } std::cout << ＂count:＂ << count << std::endl; return 0;}
　　我的机器上打印count:9742，而我们期望的结果是100*100=10000，结果与预期不符，为什么会这样？
　　简单的一行++count，实际上也包括：从内存加载变量的值到寄存器（load），寄存器中更新值（update），将寄存器中的新值存入内存（store）。
　　因为多个线程并发/并行执行，而load/update/store的三步不是原子的，不能在一个cpu cycle内完成，所以多个线程可能加载了相同的旧值，在寄存器中分别更新，再写入变量count的内存位置，导致最终值比期望的1000小，而且运行多次，会出现不同的结果。
　　## 问题出在哪里？
　　上述2个例子都表明：不加控制的多线程并发/并行访问同一数据，会导致数据不一致，从而产生错误的结果，所以，需要某种同步机制，协调多线程的运行，确保结果的正确性。
　　上述问题的根因都出在多线程对数据的竞争访问，数据竞争不仅因为对数据的访问不能在一个指令周期内完成，也因为我们经常要先读一个变量值，再基于它的值做决策，而这2个步骤的组合并非原子的。
　　只有同时满足以下情况，才需要做多线程同步：
　　- 数据竞争是前提条件，多线程对同一数据的并发访问 - 所有线程对数据只读的话，没有问题，不需要同步，必须有线程对数据进行写（修改），多线程混合读写才需要同步 - 对数据的访问在时间上要同时或者交错（多线程对数据读写在开始结束时间上有重叠），如果时间上能错开，也没有问题 - 需要出现数据不一致的情况，是不能忍受的错误（比如的超卖，计数错误），否则，也不必同步（比如只是记一条粗略统计的日志，计数不准确也没有关系），这一点往往被忽略
　　## 保护的到底是什么？
　　- 多线程同步，保护的是数据，而非代码，代码保存在进程的文本段，程序运行过程中，只会从保存文本段的内存位置读取指令序列，而不会修改文本（代码）段。
　　- 细化一下，我们保护的是全局资源/数据、static局部数据、或者通过指针/引用指向的堆内存上的数据；而普通局部变量则通常不需要保护，因为局部变量位于栈上，每个线程有独立的栈，线程栈是相互隔离的，不通过特殊手段不可互访。
　　## 多线程同步机制有哪些？
　　线程间同步的机制有很多，Posix线程同步机制包括互斥锁（Mutex）、读写锁（Reader-Writer Lock）、自旋锁（Spin Lock）、条件变量（Condition Variable）、屏障（Barrier）等。
　　C/C++、Java等编程语言都有类似的线程同步机制和编程接口，细节上不尽相同，但概念和原理上都是相通的，我们主要考查Posix线程同步机制。
　　### 互斥锁
　　互斥锁，某个线程获得锁之后，直到该线程释放锁之前，其他的线程便没法获得锁，表现出排他的特征。
　　互斥锁，本质上是一个内存变量，无他。互斥锁目的是做串行化，即在同一时间点，访问受保护数据的临界代码，只会有一个执行流正在运行，直到这段临界代码执行完，其他执行流才有机会进入这段临界代码，这就从根本上杜绝了某个数据被多个执行流交错访问。
　　互斥锁的用法，通常是在访问共享资源前加锁，完成资源访问后再解锁，当申请加锁的时候，锁已经被其他线程持有，那么申请加锁的线程便会阻塞住，当锁被释放（解锁），则阻塞在该锁上的所有线程，都会被唤醒，只有一个线程会加锁成功，其他线程意识到锁处于加锁状态，则又转入阻塞等待解锁，因此，一次只有一个线程会前进。用mutex对sell做同步的代码如下：
　　```c++
　　bool sell(int num) {
　　mutex.lock();
　　if (item_num >= num) {
　　item_num -= num;
　　mutex.unlock();
　　return true;
　　}
　　mutex.unlock();
　　return false;
　　}
　　```
　　加锁保护后，对item_num的判断和减值这2个行代码，将变成密不可分的原子操作，多线程同时调用sell()都不会出现前述的超卖错误。
　　**RAII**
　　上面的程序，有一个容易出错的点，那就是在两次返回的时候都需要解锁，如果函数有多个返回点，则需要在每个返回点都小心的解锁，如果逻辑更复杂一点，或者调用的其他函数抛出异常，则很难确保unlock得到正确的调用。
　　所以，C++提供一个叫RAII的技术，常用来应对这种情况，RAII利用C++临时对象的析构在对象出作用域时一定会得到调用的特性，来提升安全性，通过构建一个临时对象，在对象的构造函数里加锁，在析构函数里解锁，来完成配对的操作，常用于加/解锁，打开/关闭文件句柄，申请/释放资源等操作。
　　class LockGuard { std::mutex& mutex; LockGuard(const LockGuard&) = delete; LockGuard(LockGuard&&) = delete; LockGuard& operator=(const LockGuard&) = delete; LockGuard& operator=(LockGuard&&) = delete;public: LockGuard(std::mutex& mutex) : mutex(mutex) { mutex.lock(); } ~LockGuard() { mutex.unlock(); }};int item_num = 100;std::mutex item_num_mutex;bool sell(int num) { LockGuard lg(item_num_mutex); if (item_num >= num) { item_num -= num; return true; } return false;}
　　**注意**
　　- 通过互斥锁对数据进行保护，需要开发者遵从约束，按某种规定的方式编写数据访问代码，这种约束是对程序员的隐式约束，它并非某种强制的限制。
　　- 比如使用互斥量对数据x进行并发访问控制，假设有2处代码对该数据竞争访问，其中一处用互斥量做了保护，而另外一处，没有使用互斥锁加以保护，则代码依然能通过编译，程序依然能运行，只是结果上可能是错误，这个跟现实中没有钥匙开锁就不能得到（访问）权限是不一样的。
　　### 原子操作
　　原子操作，从语义上理解，既原子性的执行一系列操作，这一系列操作是密不可分的整体，要么都做，要么都不做，中间也不会被穿插进其他操作。
　　比如对一个整型变量自增（++count），对长度不大于机器字长，且满足数据类型自身对齐要求的变量的Load和Store操作，仅需要一条指令即可完成，都是原子操作（一条指令完成是原子操作的必要非充分条件），其他core无法观察到中间状态，但因为++count需要执行Load/Update/Store三步骤，多核环境下，这三步是可以相互穿插的，不是原子操作。
　　C++提供一种类型为std::atomic的类模板，它提供++/--/+=/-=/fetch_sub/fetch_add等原子操作。
　　原子操作是编写Lock-free多线程程序的基础，原子操作只保证原子性，不保证操作顺序。在Lock-free多线程程序中，光有原子操作是不够的，需要将原子操作和Memory Barrier结合起来，才能实现免锁。
　　原子操作常用于与顺序无关的场景，比如前面例子中的计数，用原子变量改写后，则会输出符合预期的count=10000。
　　```c++
　　std::atomic count = 0;
　　void thread_proc() {
　　for (int i = 0; i < 100; ++i) {
　　++count; // 原子的自增
　　}
　　}
　　```
　　### 程序顺序
　　对单线程程序而言，代码会一行行顺序执行，比如先后对`a = 1; b = 2;`赋值，则执行完`a = 1;`才会执行`b = 2;`，从程序角度看到的代码行一次执行，我们在此基础上构建软件，以此作为讨论的基础。
　　### 内存序
　　内存序是指从某个角度观察到的对于内存的读和写所真正发生的顺序。
　　内存操作顺序并不唯一：在一个包含core0和core1的CPU中，core0和core1有着各自的内存操作顺序，这两个内存操作顺序不一定相同；从包含多个Core的CPU的视角看到的全局内存操作顺序跟单core视角看到的内存操作顺序亦不同，而这种不同，对于有些程序逻辑而言，是不可接受的，所以，需要有同步机制确保内存序的一致。
　　```c++
　　a = 1;
　　b = 2;
　　```
　　程序序要求`a = 1`在`b = 2`之前执行，但内存操作顺序可能并非如此，对a赋值1并不确保发生在对b赋值2之前，如果编译器认为对b赋值没有依赖对a赋值，那它完全可以在编译期为了性能调整编译后的汇编指令顺序，即使编译器不做调整，到了执行期，也有可能对b的赋值先于对a赋值执行。
　　### 乱序执行
　　乱序执行会引起内存顺序跟程序顺序不同，乱序执行的原因是多方面的，比如编译器指令重排、超标量指令流水线、预测执行、Cache-Miss等。内存操作顺序无非精确匹配程序顺序，这有可能带来混乱，既然有副作用，那为什么还需要乱序执行呢？答案是为了性能。
　　我们先看看没有乱序执行之前，早期的有序处理器（In-order Processors）是怎么处理指令的？
　　- 指令获取，从代码节内存区域取指令到I-Cache
　　- 如果指令操作数可用，例如位于寄存器中，则分发指令到对应功能模块中；如果操作数不可用，通常是需要从内存加载，则处理器会stall，一直等到它们就绪，加载到cache或拷贝寄存器
　　- 指令被功能单元执行
　　- 功能单元将结果写回寄存器
　　乱序处理器（Out-of-order Processors）又是怎么处理指令的呢？
　　- 指令获取，相同
　　- 分发指令到指令队列
　　- 指令在指令队列中等待，一旦操作数就绪，指令就离开指令队列，那怕它之前的指令未被执行
　　- 指令被派往功能单元并被执行
　　- 执行结果放入队列（Store Buffer），而不是直接写入Cache
　　- 只有更早请求执行的指令结果写入cache后，指令执行结果才写入cache，通过对指令结果排序写入cache，使得执行看起来是有序的。
　　指令乱序执行主要由两种因素导致：
　　- 编译期：指令重排（编译器），编译器会为了性能而对指令重排，源码上先后的两行，被编译器编译后，可能调换指令顺序，但编译器会基于一套规则做指令重排，有明显依赖的指令不会被随意重排，指令重排不能破坏程序逻辑。
　　- 运行期：乱序执行（CPU），CPU的超标量流水线、以及预测执行、Cache-Miss等都有可能导致指令乱序执行，也就是说，后面的指令有可能先于前面的指令执行。
　　### Store Buffer
　　### Invalidate Queue
　　### 内存屏障
　　#### lock-free
　　未完待续...