计算机那些事(7)——线程
现代软件系统中，除了进程，线程也是一个非常重要的概念。随着CPU频率增长开始出现停滞，处理器逐渐开始想多核方向发展。多线程，作为实现软件并发执行的重要方法之一，也开始被重视。
线程基础
线程概念
线程（Thread），也称轻量级进程（Lightweight Process，LWP），是程序执行流的最小单元。一个标准的线程由线程ID、当前指令指针（PC）、寄存器集合、堆栈组成。通常，一个进程由一个到多个线程组成，各个线程之间共享程序的内存空间（包括代码段、数据段、堆等）以及一些进程级的资源（如打开文件和信号）。
同一进程中的多个线程可以互不干扰地并发执行，并且共享进程的全局变量和堆的数据。相对于单线程进程，使用多线程的原因有一下几点：
- 某个操作可能会陷入长时间等待，等待的线程会进入睡眠状态，无法继续执行。多线程执行可以有效利用等待时间进行线程切换。如等待网络响应。
- 某个操作可能会消耗大量的时间，如果只有一个线程，程序和用户之间的交互会被中断。多线程可以让一个线程负责交互，另一个线程负责计算。
- 程序本身要求并发操作，如一个多端下载软件（如Bittorrent）。
- 多CPU或多核处理器，本身具备同时执行多个线程的能力，因此单线程程序无法全面发挥计算机的全部计算能力。
- 相对于多进程应用，多线程在数据共享方面效率更高。
线程访问权限
线程可以访问进程内存中的所有的数据，包括如下几个方面：
- 全局变量
- 堆数据
- 函数里的静态变量
- 程序代码，任何线程都有权利读取并执行任何代码
- 打开的文件，A线程打开的文件可以由B线程读取
当然实际上线程也拥有自己的私有存储空间，包括如下几个方面：
- 栈：尽管并非完全无法被其他线程访问，但是一般情况下还是认为栈是私有数据。
- 线程局部存储（Thread Local Storage，TLS）：线程局部存储是某些操作系统为线程单独提供的私有空间，容量有限。
- 寄存器：寄存器是执行流的基本数据，为线程私有。
线程调度与优先级
当线程数量小于等于处理器数量时（并且操作系统支持多处理器），线程的并发是真正的并发，不同的线程运行在不同的处理器上。当线程数据大于处理器数量时，此时至少有一个处理器会运行多个线程。
在单处理器运行多线程情况下，并发是一种模拟出来的状态。操作系统会让这些多线程轮流执行，每次仅执行一小段时间（通常是几十到几百毫秒），这样每个线程“看起来”在同时执行。这样一个不断在处理器上切换不同的线程的行为称为 线程调度。
在线程调度中，线程通常拥有至少三种状态，分别是：
- 运行（Running）：此时线程正在执行。
- 就绪（Ready）：此时线程可以立刻运行，但CPI已被占用。
- 等待（Waiting）：此时线程正在等待某一事件（通常是I/O或同步）发生，无法执行。
处于运行中的线程拥有一段可以执行的时间，这段时间称为 时间片（Time Slice）。当时间片用尽时，线程进入就绪状态。如果线程在时间片用尽前就开始等待某事件，则它将进入等待状态。当一个线程离开运行状态时，系统会选择一个处于就绪状态的线程继续执行。在一个处于等待状态的线程所等待的事件发生后，该线程将进入就绪状态。如下图所示为线程的状态转移图。
在线程调度中，主要有两种调度算法：
- 优先级调度（Priority Schedule）：线程拥有各自的 线程优先级（Thread Priority），高优先级的线程会更早执行，低优先级的线程需要等待系统中没有高优先级的可执行线程存在时才能执行。
- 轮转调度（Round Robin Schedule）：让各个线程轮流执行一段时间片。
实际应用中，系统还会根据不同线程的表现自动调整优先级，提高线程调度效率。在系统中，一般把频繁等待的线程称为 IO密集型线程（IO Bound Thread）；把很少等待的线程称为 CPU密集型线程（CPU Bound Thread）。通常，IO 密集型线程比 CPU 密集型线程更容易得到优先级的提升。
在优先级调度中，存在一种 饿死（Starvation） 现象，即一个线程的优先级较低，在它执行之前，总是有较高优先级的线程在它之前执行。当一个CPU密集型的线程获得较高优先级时，许多低优先级的进程就可能饿死。当一个IO密集型的线程获得较高优先级时，由于大部分之间处于等待状态，因此相对不容易造成其他线程饿死。为了避免饿死现象，调度系统通常会逐步提升那些等待时间过长且未得到执行的线程的优先级。
可抢占线程和不可抢占线程
轮转调度中，线程在用尽时间片后会被强制剥夺继续执行的权利，而进入就绪状态，该过程称为 抢占（Preemption）。在早期的一些操作系统中，线程是不可抢占的。在这种调度模型下，线程必须主动进入就绪状态，而不是靠时间片用尽来被强制进入。如果线程始终拒绝进入就绪状态，并且不进行任何等待操作，其他线程将永远无法执行。
在不可抢占线程中，线程会在两种情况下主动放弃执行：
- 当线程试图等待某些事件时（如I/O事件）。
- 线程主动放弃时间片。
线程安全
多线程程序处于一个多变的环境中，可以访问的全局变量和堆数据随时都可能被其他的线程改变。因此，多线程程序在并发时数据的一致性非常重要。
竞争与原子操作
多线程同时访问一个共享数据，可能会造成严重的后果。以一个著名的例子为例，假设有两个线程分别执行如下所示的
C 代码。 1
2
3
4
5
6// 线程 1
i = 1;
++i;
// 线程 2
--i;
- 读取 i 到某个寄存器 X
- X++
- 将 X 的内容存储至 i
由于线程 1 和线程 2并发执行，因此两个线程的执行可能如下（注意，寄存器 X 的 内容在不同的线程中是不一样的，这里用 X[1] 和 X[2] 分别表示线程 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，但从表中的执行序列可以看到，i 的实际值是 0。实际上，这两个线程如果同时执行，i 的结果有可能是 0 或 1 或 2。
很明显，由于 i++ 操作在多线程环境下会出现错误是因为该操作被编译成汇编代码后不止一条指令，因此在执行时可能会被调度系统打断，去执行别的代码。通常，我们把单指令的操作称为 原子操作，因为单条指令的执行是不会被打断的。很多体系结构都提供了一些常用的原子指令，如 i386 就有一条 inc 指令可以直接增加一个内存单元值，可以避免上例的错误情况。
尽管原子操作指令非常方便，但是它们仅适用于比较简单特定的场合。在复杂的场合下，比如要保证一个复杂的数据结构更改的原子性，原子操作指令就力不从心了。这里需要更加通用的手段：锁。
同步与锁
为了避免多个线程同时读写同一个数据而产生不可预料的后果，需要将各个线程对同一个数据的访问进行 同步（Synchronization）。即在一个线程访问数据未结束时，其他线程不得对同一个数据进行访问。
同步最常见的方法是使用 锁（Lock）。锁是一种非强制机制，每个线程在访问数据或资源之前首先试图 获取（Acquire） 锁，并在访问结束之后 释放（Release） 锁。在锁已经被占用时试图获取锁时，线程会等待，直到锁重新可用。
二元信号量
二元信号量（Binary Semaphore） 是最简单的一种锁，只有两种状态：占用、非占用。二元信号量适合只能被唯一一个线程独占访问的资源。当二元信号量处于非占用状态时，第一个试图获取该二元信号量的线程会获得该锁，并将二元信号量置为占用状态，此后其他所有试图获取该二元信号量的线程将会等待，直到该锁被释放。
多元信号量
多元信号量是二元信号量的扩展，简称 信号量（Semaphore）。一个初始值为 N 的信号量允许 N 个线程并发访问。
当线程访问资源时，首先获取信号量，进行如下操作：
- 将信号量减 1。
- 如果信号量的值小于 0，则进入等待状态，否则继续执行。
当线程结束访问资源后，线程释放信号量，进行如下操作：
- 将信号量的值加 1。
- 如果信号量的值小于 1，唤醒一个等待中的线程。
互斥量
互斥量（Mutex） 和二元信号量很相似，资源仅同时允许一个线程访问，但和信号量不同的是：信号量在整个系统中可以被任意线程获取并释放，即同一个信号量可以被系统中的一个线程获取之后由另一个线程释放；互斥量则要求哪个线程获取了互斥量，哪个线程就要负责释放这个锁。
临界区
临界区（Read-Write Lock） 是比互斥量更加严格的同步手段。在术语中，把临界区的锁的获取称为进入临界区，而把锁的释放称为离开临界区。临界区和互斥量与信号量的区别在于：互斥量和信号量在系统的任何进程里都是可见的，即一个进程创建了一个互斥量或信号量，另一个进程试图获取该锁是合法的；临界区的作用范围仅限于本进程，其他的进程无法获取该锁。
读写锁
读写锁（Read-Write Lock） 致力于一种更加特定的场合的同步。对于一段数据，多个线程同时读取总是没有问题的，但假设操作都不是原子型，只要有任何一个线程试图对该数据进行修改，就必须使用同步手段来避免出错。对此，可以使用上述的信号量、互斥量或临界区中的任何一种来进行同步。虽然这样可以保证程序正确执行，但是对于读取频繁的程序，会显得非常低效。读写锁就是用来提高这种情况下的执行效率的。
读写锁有两种获取方式：共享的（Shared）、独占的（Exclusive）。当锁处于自由状态时，试图以任何一种方式获取锁都能成功，并将锁置于对应的状态。如果锁处于共享状态，其他线程以共享的方式获取锁仍然会成功，此时这个锁分配给了多个线程。如果其他线程试图以独占的方式获取已经处于共享状态的锁，那么它必须等待锁被所有线程释放。处于独占状态的锁将阻止任何其他线程获取该锁。
条件变量
条件变量（Condition Variable） 作为一种同步手段，作用类似于一个栅栏。对于条件变量，线程可以有两种操作：首先，线程可以等待条件变量，一个条件变量可以被多个线程等待。其次，线程可以唤醒条件变量，此时所有等待此条件变量的线程都会被唤醒并继续执行。
线程模型
线程的并发执行是由多处理器或操作系统调度来实现的。但实际情况要更为复杂：大多数操作系统，包括 Windows 和 Linux，都在内核里提供线程的支持，内核态线程由多处理器或调度来实现并发。然而用户实际使用的线程并不是内核态线程，而是用户态线程。用户态线程并不一定在操作系统内核里对应同等数量的内核态线程。它们之间的对应关系有三种类型。
一对一模型
对于直接支持线程的系统，一对一模型始终是最简单的模型。对于一对一模型，一个用户态线程唯一对应一个内核态线程，但一个内核态线程并不一定存在相应的用户态线程。模型示意图如下所示。
一对一模型中，用户态线程具有和内核态线程一致的优点，线程之间的并发是真正的并发，一个线程因为某原因阻塞时，其他线程的执行不会受到影响。此外，一对一模型也可以让多线程程序在多处理器的系统上有更高的效率。
一对一线程模型也有两个缺点：
- 由于许多操作系统限制了内核态线程的数量，因此一对一线程会让用户态线程的数量受到限制。
- 许多操作系统内核线程调度时，上下文切换的开销较大，导致用户线程的执行效率下降。
多对一模型
多对一模型将多个用户态线程映射到一个内核态线程上，线程之间的切换由用户态的代码完成。因此相对于一对一模型，多对一模型的切换要快速许多。模型示意图如下所示。
多对一模型的问题在于：如果其中一个用户态线程阻塞，将导致所有线程都无法执行。另外，在多处理器系统中，处理器的增多对于多对一模型的线程性能也不会有明显的提升。多对一模型的优点在于高效的上下文切换和几乎无限制的线程数量。
多对多模型
多对多模型结合了多对一模型和一对一模型的特点，将多个用户态线程映射到少数但不止一个内核态线程。模型示意图如下所示。
多对多模型中，一个用户态线程阻塞并不会导致所有的用户态线程阻塞，因为此时还有其他的线程可以被调度来执行。此外，多对多模型对用户线程的数量也没什么限制，在多处理器系统中，多对多模型的线程也能得到一定的性能提升，但是提升幅度步入一对一模型。
参考
- 《程序员的自我修养——链接、装载与库》
- 《深入理解计算机系统》
（完）