多线程

（摘自《程序员的自我修养》）

1.线程基础

1.1 什么是线程

  线程（thread），有时被称为轻量级进程（LightWeight Process，LWP），是程序执行流的最小单元。一个标准的线程由线程ID、当前指令指针（PC）、寄存器集合和堆栈组成。通常意义上，一个进程由一个到多个线程组成，各个线程之间共享程序的内存空间（包括代码段、数据段、堆等）及一些进程级的资源（如打开文件和信号）。
  通常来说，使用多线程的原因有如下几点：

• 某个操作可能会陷入长时间等待，等待的线程会进入睡眠状态，无法继续执行。多线程执行可以有效利用等待的时间。典型的例子就是等待网路响应，这可能要花费数秒甚至数十秒。
• 某个操作会消耗大量的时间，如果只有一个线程，程序和用户之间的交互会中断。多线程可以让一个线程负责交互，另一个线程负责计算。
• 程序逻辑本身就要求并发操作，例如一个多端下载软件。
• 多CPU或多核计算机，本身具备同时执行多个线程的能力，因此单线程程序无法全面地发挥计算机的全部计算力。
• 相对于多进程应用，多线程在数据共享方面效率要高很多。

1.2 线程的访问权限

  线程可以访问进程内存里的所有数据，甚至包括其他线程的堆栈（如果它知道其他线程的堆栈地址，比较少见），实际应用中线程也拥有自己的私有存储空间，也包括以下几个方面。

• 栈（尽管并非完全无法被其他线程访问，但是一般情况下可以认为是私有的数据）。
• 线程局部存储。线程局部存储是某些操作系统单独为线程提供的私有空间，但通常情况下空间有限。
• 寄存器。寄存器是执行流的基本数据，因此为栈私有。
    从C程序员的角度来看，数据在线程之间是否私有如表所示

线程私有	线程之间共享（进程所有）
局部变量、函数的参数、TLS数据	全局变量、堆上的数据、函数里的静态变量、程序代码、打开的文件

1.3 线程调度与优先级

  在单处理器对应多线程的情况下，并发是一种模拟出来的状态，操作系统会让这些多线程程序轮流执行，每次仅执行一小段时间，这样每个线程就看起来在同时执行，这样一个不断在处理器上切换不同线程的行为称之为线程调度（Thread Schedule），在线程调度中，线程通常拥有至少三种状态，分别是：

• 运行（Running）
• 就绪（Ready）
• 等待（Waiting）
    处于运行中的线程拥有一段可以执行的时间，这段时间称为时间片（Time Slice），当时间片用尽的时候，该程序将进入就绪状态。如果时间片用尽之前线程就开始等待某事件，那么它将进入等待状态。每当一个线程离开运行状态时，系统就会选择一个其他的就绪线程继续执行。在一个处于等待状态的线程所等待的时间发生以后，该线程将进入等待状态。
    现在主流的调度方式尽管各不相同，但都带有优先级调度（Priority Schedule）和轮转法（Round Robin）的痕迹。
    我们一般把频繁等待的线程称之为IO密集型线程（IO Bound Thread），而把很少等待的线程称为CPU密集型线程（CPU Bound Thread），IO密集型线程总是比CPU密集型线程容易得到优先级的提升。
    在优先级调度下，存在一种饿死（Starvation）的现象，一个线程被饿死，是说它的优先级较低，在它执行之前，总是有较高优先级的线程要执行，因此这个低优先级的线程始终无法执行。CPU密集型线程一般更容易导致其他线程饿死。为了避免饿死现象，调度系统往往会逐步提升那些等待了过长时间的得不到执行的线程的优先级。
    线程的优先级更改一般有以下方式：
• 用户指定优先级
• 根据进入等待状态的频繁程度提升或降低系统的优先级（系统更喜欢频繁进入等待状态的线程）
• 长时间得不到执行而被提升优先级

1.4 可抢占线程和不可抢占线程

  线程在时间片用尽之后会被强制剥夺继续执行的权利而进入就绪状态，这个过程叫做抢占（Preemption），即之后执行的线程抢占了当前线程。早期的一些系统中，线程是不可抢占的，如今已经非常少见。

2. 线程安全

2.1 竞争与原子操作

  多线程访问共享数据会造成恶劣后果，以下是一个例子

线程1	线程2
i=1;	--i;
++i;

  在许多体系机构上，++i 的实现方式会如下：

1. 读取 i 到某个寄存器X
2. X++
3. 将X的内容存储回 i
     因为线程1和线程2并发执行，因此两个线程的执行顺序可能如下（寄存器X的内容在不同的线程中是不一样的）：

执行序号	执行指令	语句执行后变量值	线程
1	i=1	i=1,X[1]未知	1
2	X[1]=i	i=1,X[1]=1	1
3	X[2]=i	i=1,X[2]=1	2
4	X[1]++	i=1,X[1]=2	1
5	X[2]--	i=1,X[2]=0	2
6	I=X[1]	i=2,X[1]=2	1
7	I=X[2]	i=0,X[2]=0	2

  从程序逻辑来看，两个线程都执行完毕后 i 的值应该为1，但从上表的执行结果来看，结果可能是0.实际上两个线程如果同时执行的话，i的结果可能是0或1或2。可见，多个线程同时读写同一个共享数据会造成意想不到的结果。
  自增操作在多线程环境下会出错是因为这个操作被编译为汇编代码后不止一条指令，因此可能在执行一半时被调度系统打断，去执行别的代码。为了避免出错，很多系统提供了一些常用操作的原子指令，但这些指令只适用于简单特定的场合，无法应对复杂的场合。

2.2 同步与锁

  为了避免多个线程同时读写同一个数据产生不可预料的后果，我们要将各个线程对同一数据的访问同步（Synchronization）。所谓同步，即指在一个线程访问数据未结束的时候，其他线程不得对数据进行访问。
  同步的最常见使用方式是使用锁（Lock），锁是一种非强制机制，每一个线程在访问数据资源之前首先试图获取锁，并在访问结束之后释放锁，在锁被占用的情况下试图获取锁时，线程会等待，直到锁重新可用。
  二元信号量是最简单的一种锁。它只有两种状态，占用和非占用。
  多元信号量存在一个初始值N，允许N个线程并发访问。线程访问资源时首先获取信号量，进行如下操作：

• 将信号量的值减1
• 如果信号量的值小于0，则进入等待状态，否则继续执行。
    访问完资源之后，进行如下操作：
• 将信号量的值加1
• 如果信号量的值小于1，唤醒一个等待中的线程。

  互斥量和二元信号量类似，资源仅同时允许一个线程访问，和二元信号量不同的是，信号量在某个系统可以被任意线程获取和释放，而互斥量则要求哪个线程获取了互斥量则由哪个线程负责释放锁。
  临界区是比互斥量更严格的同步手段。临界区与互斥量和信号量的区别在于，互斥量和信号量在系统的任何进程里都是可见的，临界区的作用范围仅限于本进程。除此之外，临界区具有与互斥量相同的性质。
  读写锁。对于同一个锁，读写锁有两种获取方式，共享的或独占的。当锁处于自由状态时，以任何一种方式获取锁都可以成功，如果锁处于共享状态，其他锁以共享的方式获取锁都能成功，如果其他线程以独占的方式获取，则必须等待锁被所有的线程释放。处于独占的锁将阻止其他所有线程获取锁。
  条件变量作为一种同步手段，作用类似于一个栅栏。使用条件变量可以让多个线程一起等待某个事件的发生，当事件发生时（条件变量被唤醒），所有的线程可以一起恢复执行。

2.3 可重入与线程安全

  一个函数被重入，表示这个函数没有执行完成，由于外部因素或内部调用，又一次进入该函数执行。一个函数要重入，只有两种情况：
  1. 多个线程同时执行这个函数
  2. 函数自身调用自身
  一个函数被称为可重入的，表示这个函数被重入之后不回产生任何不良后果。一个函数要成为可重入的，必须具备以下几个特点：

• 不使用任何（局部）静态或全局的非const常量
• 不返回任何（局部）静态或全局的非const变量的指针
• 仅依赖于调用方提供的参数
• 不依赖于单个资源的锁
• 不调用任何不可重入的函数

2.4 过度优化

  即使合理地使用了锁，也无法保证线程安全，这是源于落后的编辑器技术已经无法满足日益增长的并发需求。看如下例子：

x = 0;
Thread1    Thread2
lock();    lock();
x++;       x++;
unlock();  unlock();

由于有lock()和unlock()的保护，x++的行为不会被并发所破坏，那么x的值似乎必然是2了。然而，如果编译器为了提高 x 的访问速度而把x放到了某个寄存器里，我们知道不同线程的寄存器是私有的，因此如果Thread1先获取到锁，则程序的执行可能如下所示：

• 【Thread1】读取x到某个寄存器R1（R1=0）
• 【Thread1】R1++（由于之后可能还要访问x，所以不把R1写回x）
• 【Thread2】读取x到某个寄存器R2（R2=0）
• 【Thread2】R2++（R2=1）
• 【Thread2】将R2写回x（x=1）
• 【Thread1】很久之后，将R1写回x（x=1）
    可见即使这种情况下，正确的加锁也不能保证线程安全。
    再看一个例子：

x = y = 0;
Thread1    Thread2
x = 1;     y = 1;
r1 = y;    r2 = x;

  很显然，r1和r2至少有一个为1，逻辑上不可能同时为0。然而事实上r1=r2=0的情况确实可能出现。原因是早在几十年前CPU就发展出了动态调度，在执行程序的时候为了提高执行效率有可能交换指令的顺序。同样，编译器在进行优化的时候也可能交换毫不相干的两条指令的顺序，也就是说，以上代码在执行的时候可能是这样的：

x = y = 0;
Thread1    Thread2
r1 = y;    y = 1;
x = 1;     r2 = x;

那么r1=r2=0就完全可能了。我们可以使用volatile关键字试图阻止过度优化，volatile基本可以做到两件事：
(1) 阻止编译器为了提高速度将一个变量写到寄存器中而不写回
(2) 阻止编译器调整操作volatile变量的执行顺序
  volatile关键字可以完美解决第一个问题，但是无法解决第二个问题，因为volatile无法阻止CPU动态调度换序。
  再看一个例子：

volatile T* pInst = 0;
T* GetInstance() {
    if (pInst == NULL) {
        lock();
        if (pInst == NULL)
            pInst = new T;
        unlock();
    }
    return pInst;
}

  抛开逻辑，这样的代码乍看是没有问题的，当函数返回时，pInst总是指向一个有效的对象，而lock()和unlocl()防止了多线程竞争导致的麻烦。双重的if在这里另有妙用，可以让lock()调用的开销降低到最小。
  但是实际上这样的代码是有问题的，问题的来源仍然是CPU的乱序执行。C++里面的new实际上包含了两个步骤。
(1) 分配内存
(2) 调用构造函数
  所以pInst = new T;包含了三个步骤：
(1) 分配内存
(2) 在内存的位置上调用构造函数
(3) 将内存的地址赋值给pInst
  在这三步中，(2)和(3)的顺序是可以颠倒的。也就是说，完全有可能出现这样的现象：pInst的值已经不是null，但对象仍然没有构造完毕，这时候如果出现另一个对GetInstance()的并发调用，此时第一个if中反而pInst的值不为NULL，所以这个调用会直接返回尚未构造完全的对象的地址提供给用户使用，那么程序这个时候会不会崩溃就取决于这个类的设计如何了。
  从上面两个例子可以看出，要保证线程安全，阻止CPU乱序执行是必需的。遗憾的是，现在并不存在一种可移植的阻止换序的方法。通常情况下是调用CPU的一条指令，这条指令通常被称为barrier，一条barrier指令会阻止CPU将该指令之前的数据交换到该指令之后执行，barrier指令的作用类似于一个拦水坝，阻止换序穿透这个大坝。

volatile T* pInst = 0;
T* GetInstance() {
    if (pInst == NULL) {
        lock();
        if (pInst == NULL)
            T* temp = new T;
            barrier();
            pInst = temp;
        unlock();
    }
    return pInst;
}

由于barrier()的存在，对象的构造一定在对象赋值之前完成，因此当pInst被赋值的时候，对象总是完好的。

3. 多线程的内部情况

3.1 三种线程模型

1. 一对一模型

  一个用户使用的线程就对应一个内核使用的线程（但反过来不一定，一个内核里的线程的用户态不一定有对应的线程存在）。这样用户线程就有了和内核线程一样的优点，线程之间的并发是真正的并发，一个线程阻塞时，其他线程不会受影响。一般使用API或系统调用创建的线程都为一对一的线程。
  一对一线程缺点有两个：

• 由于许多操作系统限制了内核线程的数量，因此一对一线程会让用户的线程数量收到限制。
• 许多操作系统的内核线程调度时上下文切换的开销较大，导致用户线程的执行效率下降。

2. 多对一模型

  多对一模型将多个用户线程映射到一个内核线程上，线程间的切换由用户态的代码来进行，因此相对于一对一模型，多对一模型的线程切换效率更高，同时线程数量不受内核线程数量限制。
  多对一模型的一个大问题是如果一个用户线程阻塞了，那么其他线程都将无法执行下去。此外处理器的增多也不会带来用户线程效率上的明显的提升。

3.多对多模型

  多对多模型将多个用户线程映射到少数但不止一个内核线程上，一个线程阻塞不会影响其他线程。多处理器操作系统中，线程的性能能得到一定提升，但是不如一对一高。