01 Concurrency

线程(thread)

下面我们要引入一个新的抽象：线程。计算机上运行的不同程序称为不同的进程，在原先的讨论中，我们默认了我们会按顺序执行一个进程中的每条指令，我们把这种运行方式称为“单线程”。进程与进程之间的内存是独立的，想要同时运行多个进程需要频繁地上下文切换。现在假如我们想同时运行一个进程中的多条指令，那么我们也可以类似地进行上下文切换，这种运行方式就是“多线程”。但是与进程切换不同，线程与线程之间是共享内存的，每次切换只需要保存寄存器状态就好了。同样地，线程切换的选择也由调度程序来决策。（还有与进程不同的一点时，每个线程都需要一个独立的栈来储存临时变量等等，因此其内存空间中需要分更多的段）

然而，由于不同线程会访问相同的内存，这将引发许多复杂的问题。例如，当两个线程都要修改某个全局变量的值时，可能会导致输出结果的不确定性(indeterministic)。例如x=x+1这一语句在汇编中分为三条指令：把x的值读取到寄存器、把值增加一、写回。我们期望发生这样的事：线程1执行完三条指令，切换到线程2，执行完三条指令。这样x的值最终增加了2。但是，假如线程1在只执行了前两条指令的时候就发生了时钟中断并且调度程序决定运行线程2，那么会在线程1写回之前执行线程2的赋值，执行完线程2的三条指令再切换回线程1执行写回，这样x的值最终只增加了1。所以我们发现，程序的结果会因为上下文切换的时间点的选取而有所不同，这就是共享内存的多线程带来的问题。在操作系统的术语中，访问共享资源的代码称为临界区(critical section)，多个线程在大致相同的时间访问临界区的情形称为竞争条件(race condition)。我们希望线程间是互斥(mutual exclusion)的：当一个线程处于临界区时，其它线程能被禁止进入临界区。

锁(lock)

出现竞争条件的原因是我们希望一个线程中某几个指令总是以整体的方式执行的，不会在执行到前若干条后因为发生时钟中断进而被切换。我们希望某些指令集合是以原子性(atomically)的方式被整体执行的。

一个简单的想法是，我们设置一个每个线程都能看到的“全局变量”。在每个线程进入临界区之前，先检查全局变量是否为0，为0代表当前没有线程进入这个临界区，那么此时这个线程把全局变量修改为1并进入临界区。当一个线程在进入临界区时如果全局变量为1，代表临界区正在被占用，则必须陷入循环等待(spin-wait)，不断检查这个全局变量直到其值变为0，此时再进入临界区。这个全局变量就被称为锁(lock)，我们上面描述的是一种特殊的锁，这个锁在被一个线程占用时别的线程必须循环等待，因此称为自旋锁(spin lock)。

上面的自旋锁如果没有硬件的支持的话还会存在一点问题：如果在修改全局变量和占用临界区的间隔内发生时钟中断，那么检测和修改锁的值就可能割裂开了。换言之，在上面的过程中我们无法保证检测和设置锁是原子化的。为此，我们需要硬件能够提供一个基本的原子化指令：检测并设置(test and set)一个变量的值。这样我们就通过硬件的帮助实现了一个可行的自旋锁。

对于单CPU的处理器，自旋锁可能是效率低下的。因为当一个线程占用锁的时候，剩下的所有要进入临界区的线程都陷入自选等待什么也做不了，如果调度是周转执行的意味着大量的时间片被浪费。所以我们还应当增加一点操作系统的支持：一个简单的方法就是利用操作系统的调度让自旋等待的线程让出CPU而不占用整个时间片，这样就节省了很多时间。但是这样还是没法节省上下文切换的成本，能不能根本地从调度本身出发提出一个解决方案呢？有的操作系统会设置一个队列，让等待的线程进入休眠状态并在队列中排队。有的操作系统会结合以上两种，比如在Linux中等待的线程会先进行固定次数的自旋，然后被休眠加入等待队列。不同的操作系统对于锁有不同的实现，这些工作中需要的支持都可以分为硬件支持和操作系统支持两类。

在给代码加锁的时候，我们总可以给整个大的临界区加一把大锁，这样总能保证正确性。但是有时大锁会带来大的开销，使用小锁有时会性能更好。这当然也会带来实现起来的诸多麻烦。这就是锁的粗颗粒都与细颗粒度的问题，需要具体问题具体分析。

条件变量(condition variable)

锁并不能解决所有并发的问题。很多时候，线程需要检查某一条件满足之后，才会继续运行。例如，父线程需要检查子线程是否执行完毕才能继续运行。一个最简单的方法就是用一个共享变量，