并发编程

使用应用级并发的应用程序称为并发程序。操作系统提供了三种基本的构造并发程序的方法：

• 进程。用这种方法，每个逻辑控制流都是一个进程，由内核来调度和维护。因为进程有独立的虚拟地址空间，想要和其它流通信，控制流必须使用某种显式的进程间通信（interprocess communication，IPC）机制。
• I/O多路复用。在这种形式的并发编程中，应用程序在一个进程的上下文中显式地调度它们自己的逻辑流。逻辑流被模型化为状态机，数据到达文件描述符后，主程序显式地从一个状态转换到另一个状态。因为程序是一个单独的进程，所以所有的流都共享同一个地址空间。
• 线程。线程是运行在一个单一进程上下文中的逻辑流，由内核进行调度。可以把线程看成是其它两种方式的混合体，像进程流一样由内核进程调度，而像I/O多路复用流一样共享同一个虚拟地址空间。

构造并发程序最简单的方法就是用进程，使用fork、exec和waitpid。例如，一个构造并发服务器的自然方法就是，在父进程中接受客户端连接请求，然后创建一个新的子进程来为每个新客户端提供服务。

对于在父、子进程间共享状态信息，进程有一个非常清晰的模型：共享文件表，但是不共享用户地址空间。进程有独立的地址空间既是优点也是缺点。这样一来，一个进程不可能不小心覆盖另一个进程的虚拟存储器，这就消除了许多令人迷惑的错误。另一方面，独立的地址空间使得进程共享状态信息变得更加困难。为了共享信息，它们必须使用显式的IPC（进程间通信）机制。基于进程设计的另一个缺点是，它们往往比较慢，因为进程控制和IPC的开销都很高。

I/O多路复用技术的基本思路就是使用select函数，要求内核挂起进程，只有在一个或多个I/O事件发生后，才将控制返回给应用程序。select是一个复杂的函数，有许多不同的使用场景，其中一个就是等待一组描述符准备好读。

I/O多路复用可以用作并发事件驱动（event-driven）程序的基础，在事件驱动程序中，流是因为某种事件而前进的。一般概念是将逻辑流模型化为状态机。不严格地说，一个状态机（state machine）就是一组状态（state）、输入事件（input event）和转移（transition），其中转移就是将状态和输入事件映射到状态。每个转移都将一个（输入状态，输入事件）对映射到一个输出状态。自循环（self-loop）是同一输入和输出状态之间的转移。事件驱动设计常常比基于进程的设计要高效得多，但是编码复杂，并且会随着并发粒度的减小，复杂性还会上升。

服务器使用I/O多路复用，借助select函数检测输入事件的发生。当每个已连接描述符准备好可读时，服务器就为相应的状态机执行转移，在这里就是从描述符读和写回一个文本行。

线程（thread）就是运行在进程上下文中的逻辑流。基于线程的逻辑流结合了基于进程和基于I/O多路复用的流的特性。同进程一样，线程由内核自动调度，并且内核通过一个整数ID来识别线程。同基于I/O多路复用的流一样，多个线程运行在单一进程的上下文中，因此共享这个进程虚拟地址空间的整个内容，包括它的代码、数据、堆、共享库和打开的文件。

多线程的执行模型在某些方面和多进程的执行模型是相似的。每个进程开始生命周期时都是单一线程，这个线程称为主线程（main thread）。在某一时刻，主线程创建一个对等线程（peer thread），从这个时间点开始，两个线程就并发地运行。最后，因为主线程执行一个慢速系统调用，例如read或sleep，或者因为它被系统的间隔计时器中断，控制就会通过上下文切换传递到对等线程。对等线程会执行一段时间，然后控制传递回主线程，依次类推。

多线程程序中的共享变量

为了理解C程序中的一个变量是否是共享的，有一些基本的问题要解答：1）线程的基础存储器模型是什么？2）根据这个模型，变量实例是如何映射到存储器的？3）最后，有多少线程引用这些实例？我们说一个变量是共享的，当且仅当它的一个实例被一个以上的线程引用。

一组并发线程运行在一个进程的上下文中。每个线程都有它自己独立的线程上下文，包括线程ID、栈、栈指针、程序计数器、条件码和通用目的寄存器值。每个线程和其它线程一起共享进程上下文的其余部分。这包括整个用户虚拟地址空间，它是由只读文本（代码）、读/写数据、堆以及所有的共享库代码和数据区域组成的。线程也共享同样的打开文件的集合。

线程化的C程序中变量根据它们的存储类型被映射到虚拟存储器：

• 全局变量。全局变量是定义在函数之外的变量。在运行时，虚拟存储器的读/写区域只包含每个全局变量的一个实例，任何线程都可以引用。
• 本地自动变量。本地自动变量就是定义在函数内部但是没有static属性的变量。在运行时，每个线程的栈都包含它自己的所有本地自动变量的实例。即使当多个线程执行同一个线程例程时也是如此。
• 本地静态变量。本地静态变量是定义在函数内部并有static属性的变量。和全局变量一样，虚拟存储器的读/写区域只包含在程序中声明的每个本地静态变量的一个实例。每个对等线程都读和写这个实例。

共享变量是十分方便的，但是它们也引入了同步错误（synchronization error）的可能性。一般而言，你没有办法预测操作系统是否将为你的线程选择一个正确的顺序。我们可以使用一种叫进度图的方法来阐明这些正确的和不正确的指令顺序的概念。

进度图（process graph）将个并发线程的执行模型化为一条维笛卡尔空间中的轨迹线。每条轴对应于线程的进度。每个点（）代表线程）已经完成了指令这个状态。图的原点对应于没有任何线程完成一条指令的初始状态。

进度图将指令执行模型化为从一种状态到另一种状态的转换（transition）。转换被表示为一条从一点到相邻点的有向边。合法的转换是向右或者向上的。一个程序的执行历史被模型化为状态空间中的一条轨迹线。

安全和不安全的轨迹线

对于线程，操作共享变量内容的指令（）构成了一个（关于共享变量的）临界区（critical section），这个临界区不应该和其它进程的临界区交替执行。换句话说，我们想要确保每个线程在执行它的临界区中的指令时，拥有对共享变量的互斥的访问。在进度图中，两个临界区的交集形成的状态空间区域称为不安全区（unsafe region）。不安全区和与它交界的状态相毗邻，但并不包括这些状态。绕开不安全区的轨迹叫做安全轨迹线（safe trajectory），相反，接触到任何不安全区的轨迹线就叫做不安全轨迹线（unsafe trajectory）。

任何安全轨迹线都将正确地更新共享计数器。为了保证线程化程序实例的正确执行，我们必须以某种方式同步线程，使它们总是有一条安全轨迹。一个经典的方法是基于信号量的思想。

信号量s是具有非负整数值的全局变量，只能由两种特殊的操作来处理，这两种操作称为P和V：

• P(s)：如果s是非零的，那么P将s减1，并且立即返回。如果s为零，那么就挂起这个线程，直到s变为非零，而一个V操作会重启这个线程。在重启之后，P操作将s减1，并将控制返回给调用者。
• V(s)：V操作将s加1。如果有任何线程阻塞在P操作等待s变成非零，那么V操作会重启这些线程中的一个，然后该线程将s减1，完成它的P操作。

P中的测试和减1操作是不可分割的，V中的加1操作也是不可分割的。V的定义中没有定义等待线程被重新启动的顺序，唯一的要求是V必须只能重启一个正在等待的线程。因此，当有多个线程在等待同一个信号量时，无法预测V操作要重启哪一个线程。

信号量提供了一种很方便的方法来确保对共享变量的互斥访问。基本思想是将每个共享变量（或者一组相关的共享变量）与一个信号量s（初始为1）联系起来，然后用P(s)和V(s)操作将相应的临界区包围起来。

以这种方式来保护共享变量的信号量叫做二元信号量（binary semaphore），因为它的值总是0或者1。以提供互斥为目的的二元信号量常常也称为互斥锁（mutex）。在一个互斥锁上执行P操作称为对互斥锁加锁；类似地，执行V操作称为对互斥锁解锁。对一个互斥锁加了锁但是还没有解锁的线程称为占用这个互斥锁。一个被用作一组可用资源的计数器的信号量称为计数信号量。

使用信号量来互斥

s<0的不可行状态定义了一个禁止区，禁止区完全包括了不安全区，阻止了实际可行的轨迹线接触到不安全区。

从可操作的意义上来说，由P和V操作创建的禁止区使得在任何时间点上，在被包围的临界区中，不可能有多个线程在执行指令。换句话说，信号量操作确保了对临界区的互斥访问。