第十二章、并发编程
现代操作系统提供了三种基本的构造并发程序的方法：
1、进程： 每个逻辑控制流都是一个进程，由内核来调度和维护。因为进程由独立的虚拟地址空间，想要和其他流通信，控制流必须使用某种显式的进程间通信机制。
2、I/O多路复用：在这种形式的并发编程中，应用程序在一个进程的上下文中显式的调度他们自己的逻辑流。逻辑流被模型化为状态机，数据到达文件描述符后，主程序显式的从一个状态转移到另一个状态。因为程序是一个单独的进程，所以所有的流都共享同一个地址空间。
3、线程：线程是运行在一个单一进程上下文中的逻辑流，由内核进行调度。你可以把线程看成是其他两种方式的混合体，像进程流一样由内核进行调度，而像I/O多路复用流一样共享同一个虚拟地址空间。
12.1 基于进程的并发编程
例如，一个构造并发服务器的自然方法就是，在父进程中接受客户端连接请求，然后创建一个新的子进程为每个新客户端提供服务。
假设我们有两个客户端和一个服务器：
1、服务器正在监听一个描述符（如socket 3，监听socket）上的连接请求。现在假设服务器接受了客户端1的连接请求，并返回一个已连接描述符（如socket 4， 连接socket）。
2、在接受连接请求之后，服务器派生一个子进程，这个子进程获得服务器描述符的完整拷贝。子进程关闭它的拷贝中的监听描述符3，而父进程关闭它以连接描述符4的拷贝，因为不需要这些描述符了。 这之后，子进程正忙于为客户端提供服务。因为父、子进程中的已连接描述符都指向同一个文件表表项，所以父进程关闭它的已连接描述符的拷贝是至关重要的。否则，将永远不会释放已连接描述符4的文件表条目，而且由此引起的存储器泄漏将最终消耗尽可用的存储器，使系统崩溃。
3、现在，假设父进程为客户端1创建了子进程之后，它接受一个新的客户端2的连接请求，并返回一个新的已连接描述符（如socket 5），然后父进程又派生另一个子进程，这个子进程用已连接描述符5位客户端提供服务，如2中处理，此时，父进程等待下一个连接请求，而两个子进程正在并发地为它们各自的客户端提供服务。
总结：
服务器端父进程：
监听套接字监听->收到连接请求->返回连接套接字->派生子进程->释放连接套接字->继续监听
子进程： 得到父进程完整拷贝->释放监听套接字->提供服务
12.1.2 关于进程的优劣
1、父子进程共享状态信息，进程有一个非常清晰的模型：共享文件表，但是不共享用户地址空间。进程有独立的地址空间即是优点也是缺点。这样一来，一个进程不会覆盖另一个进程的虚拟存储器，这就消除了许多令人迷惑的错误（优点）。
2、独立的地址空间使得进程共享状态信息变得更加困难。为了共享信息，它们必须使用显式的IPC（进程间通信）机制。这样往往比较慢，因为进程控制和IPC的开销很高。
12.2 基于I/O多路复用的并发编程
假设要求你编写一个echo服务器，它也能对用户从标准输入键入的交互命令做出响应。在这种情况下，服务器必须响应两个互相独立的I/O时间：1）网络客户端发起连接请求，2）用户在键盘上键入命令行。一个问题就是我们先等待哪个事件呢？没有哪个选择是理想的。如果在accept中等待一个连接请求，我们就不能响应输入命令。类似的，如果在read中等待输入命令，我们就不能响应任何连接请求。
针对这种困境的一个解决方法就是I/O多路复用技术。基本的思路就是使用select函数，要求内核挂起进程，只有在一个或多个I/O事件发生后，才将控制返回给应用程序。就像下面的示例：
当集合{0，4}中任意描述符准备好读时返回。
当集合{1，2，7}中任意描述符准备好写时返回。
如果等待一个I/O事件发生时过了152.13秒，就超时。
select函数处理类型为fd_set的集合，也叫作描述符集合。逻辑上，我们将描述符集合看成是一个的大小为n的位向量：
每个为bk对应于描述符k。当且仅当bk=1，描述符k才表明是描述符集合的一个元素。只允许对描述符集合做三件事1）分配它们，2）将一个此种类型的变量赋值给另一个变量，3）用FD_ZERO、FD_SET、FD_CLR和FD_ISSET宏指令来修改和检查它们。
针对我们的目的，select函数有两个输入：一个称为读集合的描述符集合（fdset）和该集合的基数（n）（实际上是任何描述符集合的最大基数）。select函数会一直阻塞，直到读集合中至少有一个描述符准备好可以读。当且仅当一个从描述符读取一个字节的请求不会阻塞时，描述符k就表示准备好可以读了。作为一个副作用，select修改了参数fdset指向的fd_set，指明读集合中一个称为准备好集合（ready set）的子集，这个集合是由读集合中准备好可以读了的描述符组成的。函数返回的值指明了准备好集合的基数。注意，由于这个副作用，我们必须在每次调用select时都更新读集合。
理解select的最好办法就是研究一个具体例子。
1、一开始打开一个监听描述符，然后创建一个空的读集合：
2、接下来，定义由描述符0（标准输入）和描述符3（监听描述符）组成的读集合：
3、然后开始典型的服务器循环。但是我们不是调用accept函数来等待一个连接请求，而是调用select函数，这个函数会一直阻塞，直到监听描述符或者标准输入准备好可以读。例如，下面是当用户按下回车键，因此使得标准输入描述符变为可读时，select会返回ready_set的值：
4、一旦select返回，我们就用宏指令来判断哪个描述符准备好可以读了。如果是标准输入准备好了，就调用command函数，如果是监听描述符准备好了，就调用accept函数。
12.2.2 I/O多路复用技术的优劣
优点：
1、比基于进程的设计给了程序员更多的对程序行为的控制。
2、一个基于I/O多路复用的时间驱动服务器是在运行在单一进程上下文中的，因此每个逻辑流都能访问该进程的全部地址空间。这使得在流之间共享数据变得很容易。
3、时间驱动设计常常比基于进程的设计要高效的多，因为它们不需要进程上下文切换来调度新的流。
缺点：
1、编码复杂。我们的时间驱动的并发echo服务器需要代码比基于进程的服务器多三倍。
12.3 基于线程的并发编程
已经了解了两种创建并发逻辑流的方法。在第一种方法中，我们为每个流使用了单独的进程。内核会自动调度每个进程。每个进程有它自己的私有地址空间，这使得流共享数据很困难。在第二种方法中，我们创建了自己的逻辑流，并利用I/O多路复用来显式地调度流。因为只有一个进程，所有的流共享整个地址空间。而基于线程的并发编程，则是以上两种方式的混合。
线程是运行在进程上下文的逻辑流（进程是资源分配的单位，线程是调度和执行的单位，进程由操作系统看到，线程由CPU看到）。
每个线程都有它自己的线程上下文，包括一个唯一的整数线程ID（tid）、栈、栈指针、程序计数器、通用目的寄存器和条件码。所有的运行在一个进程里的线程共享该进程的虚拟地址空间。
两种方式混合的理解：
1、同进程一样，线程由内核自动调度，并且内核通过一个整数ID来识别线程。
2、同基于I/O多路复用一样，多个线程运行在单一进程的上下文中，因此共享这个进程的虚拟地址空间的整个内容，包括它的代码、数据、堆、共享库和打开的文件。（线程有自己的栈区，没有自己的堆区）。
12.3.1 线程执行模型
每个进程开始生命周期时都是单一线程，这个线程成为主线程。在某一时刻，主线程会创建一个对等线程，从这个时间点开始，两个线程就并发的运行。
线程执行是不同于进程的：
1、因为一个线程的上下文要比一个进程的上下文小得多，线程的上下文切换要比进程的上下文切换快的多。
2、线程不像进程那样，不是按照严格的父子层来组织的。和一个进程相关的线程组成一个线程池，独立于其他进程创建的线程。在一个线程池中的主线程和其他线程的区别仅仅在于主线程总是进程中第一个运行的线程。线程池概念的主要影响是，一个线程可以杀死它的任何对等线程，或者等待它的任意对等线程终止。另外，每个对等线程都能读写相同的共享数据。
12.3.3 创建线程
线程通过调用pthread_create函数来创建其他线程。
12.3.4 终止线程
一个线程是以以下方式之一来终止的：
1、当顶层的线程例程返回时，线程会隐式的终止。
2、通过调用pthread_exit函数，线程会显式的终止。
3、某个对等线程调用Unix的exit函数，该函数终止进程以及所有与该进程相关的线程。
4、另一个对等线程通过以当前线程ID作为参数调用pthread_cancle函数来终止当前线程。
12.3.5 回收已终止的线程的资源
线程通过调用pthread_join函数等待其他线程终止。
pthread_join函数会阻塞，直到线程tid终止，将线程例程返回的指针赋值为thread_return指向的位置，然后回收已终止线程占用的所有存储器资源。
12.3.6 分离线程
在任意时间点上，线程是可分离的或可结合的。
1、一个可结合的线程能够被其他线程回收资源和杀死。在被其他线程回收之前，它的存储器资源（如栈）是没有被释放的。
2、一个分离的线程是不能被其他线程回收或杀死的。它的存储器资源在它终止时由系统自动释放。
默认情况下，线程被创建为可结合的。但是为了避免存储器泄漏，每个可结合线程都应该要么被其他线程显式的回收，要么调用pthread_detch函数被分离。这样是为了确保释放其存储器资源。
12.4 多线程程序中的共享变量
12.4.1 线程存储器模型
一组并发线程运行在一个进程的上下文中。每个线程都有它自己独立的线程上下文，包括线程ID，栈，栈指针，程序计数器，条件码，和通用目的寄存器值。每个线程和其他线程一起共享进程上下文的剩余部分。这包括整个用户虚拟地址空间，它是由制度文件（代码）、读/写数据、堆，以及所有的共享库代码和数据区域组成的。线程也共享同样的打开文件的集合。
在线程之间寄存器是从不共享的，而虚拟存储器总是共享的。
虽然每个线程有自己的栈空间，但是不同线程栈是不对其他线程设防的。所以，如果一个线程以某种方式得到一个指向其他线程栈的指针，那么它就可以读写这个栈的任何部分。
12.4.2 将变量映射到存储器
线程化的程序中变量根据它们的存储类型被映射到虚拟存储器中：
1、全局变量：全局变量是定义在函数之外的变量。
在运行时，虚拟存储器的读/写区域只包含每个全局变量的一个实例，任何线程都可以引用。
2、本地自动变量：本地自动变量就是定义在函数内部但没有static属性的变量。
在运行时，每个线程的栈都包含它自己所有本地变量的实例。
3、本地静态变量：本地静态变量时定义在函数内部并有static属性的变量。
和全局变量一样，虚拟存储器的读/写区域只包含在程序中声明的每个本地静态变量的一个实例。在运行时，每个对等线程都读和写这个实例。
12.5 用信号量同步线程
共享变量是十分方便的，但是也引入了同步错误的可能性。
对于下面一个同步不正确的计数器程序：
它创建了两个线程，每个线程都对共享计数变量cnt加1.因为每个线程都对计数器增加了niters次，我们预计它的最终值为2×niters。但是当运行程序是，每次得到的答案都是不同的。
为了理解这个问题，我们需要研究计数器循环（39~40行）的汇编代码，线程i的循环代码可以分为五个部分：
Hi：在循环头部的指令块；
Li：加载共享变量cnt到寄存器%eax_i的指令，这里%eax_i为线程i中的寄存器的值；
Ui：更新（增加）%eax_i的指令；
Si：将%eax_i的更新值返回到共享变量cnt的指令；
Ti：循环尾部指令块。
注意头和尾只操作本地栈变量，而Li，Ui和Si操作共享计数器变量的内容。
当程序的两个对等线程在一个单处理器上并发运行时，机器指令以某种顺序一个接一个完成。因此，每个并发执行定义了两个线程中的指令的某种全序。不行的是：这些顺序中的一些会产生正确结果，但是其他的不会。而我们无法预测操作系统是否将线程选择一个正确的顺序。
下图为两种不同顺序下得到的不同结果示意图：
12.5.1 进度图
进度图将n个并发线程的执行模型转化为一个n为空间中的轨迹线。每条轴k对应进程k的进度。每个点Ik代表线程k已经完成了指令Ik这一状态。
一个程序的执行历史被模型化为空间中的一条轨迹线。如下图所示：
进度图中只允许向上或向右移动。
对于线程i操作共享变量cnt内容的指令为（Li，Ui，Si）构成了一个共享变量cnt的临界区，这个临界区不应该和其他线程的临界区交替执行。换句话说，我们想要确保每个线程在执行它的临界区中的指令时，拥有对共享变量的互斥的访问。
两个临界区的交集形成的状态空间区域称为不安全区。经过不安全区的轨迹则为不安全轨迹线。
任何安全轨迹线都将正确的更新共享计数器。为了保证线程化程序示例的正确执行，我们必须以某种方式同步线程，使它们总是有一条安全轨迹线。一个经典的方法就是基于信号量的思想。
12.5.2 信号量
信号量s是具有非负整数值的全局变量，只能用两种特殊的操作来处理，这两种操作称为P和V：
P（s）：如果s是非零的，则P将s减1，并立即返回。如果s为0，就挂起这个线程（可以理解为加锁）。
V（s）：V操作将s加1，如果任何线程阻塞在P操作等待s变为非0，那么V操作会重启这些线程中的一个，然后改线程s减1，完成它的P操作（可以理解为解锁）。
P和V的定义确保了一个正在运行的程序绝不可能进入这样一种状态，也就是一个正在初始化的信号量有一个负值。这个属性成为信号量的不变性，为控制并发程序的轨迹提供了强有力的工具。
12.5.3 使用信号量来实现互斥
信号量提供了一种很方便的方法来确保对共享变量的互斥访问。基本思想就是将每个共享变量与一个信号量s（初始化为1）联系起来，然后通过P和V操作将相应的临界区包围起来。
以这种方式来保护共享变量的信号量叫做二元信号量，因为它的值总是0或者1。以提供互斥为目的的二元信号量常常也成为互斥锁。在一个互斥锁上执行P操作称为加锁。V操作称为解锁。
与二元信号量相对应的还有计数信号量。
12.5.4 利用信号量来调度共享资源
两个经典而有用的例子是生产者-消费者和读者-写者问题。
1、生产者-消费者问题
模型描述：生产者和消费者线程共享一个有n个槽的有限缓冲区。生产者线程反复生成新的item，并把它们插入到缓冲区中。消费者线程不断地从缓冲区中取出这些item，然后消费（使用）它们。
模型产生的问题：
1、因为插入和取出item都涉及更新共享变量，所以必须保证对缓冲区的访问是互斥的。
2、但是只保证互斥访问时不够的，还需要调度对缓冲区的访问。如果缓冲区是满的（没有空的槽位），那么生产者必须等待知道有一个槽位变为可用。与之相似，如果缓冲区是空的（没有可取用的item），那么消费者必须等待直到有一个item变为可用。
因此生产者消费者模型主要考虑两个问题：一个是生产者消费者互斥，另一个是调度缓冲区的访问。
模型实例：
1、图形用户接口设计。生产者检测到鼠标和键盘事件，并将它们插入到缓冲区。消费者以某种基于优先级的方式从缓冲区取出这些事件，并显示在屏幕上。
2、在一个多媒体系统中，生产者编码视频帧，消费者解码并在屏幕上呈现出来。缓冲区的目的是为了减少视频流的抖动，而这种抖动是由各个帧的编码和解码时与数据相关的差异引起的。缓冲区为生产者提供了一个槽位池，而为消费者提供了一个已编码的帧值。
实际操作：
需要三个信号量同步对缓冲区的访问。一个提供互斥的缓冲区访问，另外两个信号量分别记录空槽位和可用项目的数量。
2、读者-写者问题
问题描述：
一组并发的线程要访问一个共享对象，例如一个主存中的数据结构，或者一个磁盘上的数据库。有些线程只读对象，而其他的线程只修改对象。修改对象的线程叫做写者。只读对象的线程叫做读者。
写者必须拥有对对象的独占的访问，而读者可以和无限多个其他读者共享对象。
总结来说：写者之间需要互斥，写者与读者也需要互斥，而读者之间不需要互斥。
模型实例：
1、一个在线航空预定系统中，允许有无限多个客户同时查询作为分配，但是正在预定作为的客户必须拥有对数据库的独占的访问。
2、在一个多线程缓存Web代理中，无限多个线程可以从共享页面缓存中取出已有的页面，但是任何向缓存中写入一个新页面的线程必须拥有独占的访问。
读者写者问题有两种形式：
1、读者优先：不要让读者等待，除非已经把使用对象的权限赋予了一个写者。换句话说，读者不会因为有一个写者在等待而等待。
2、写者优先：要求一旦一个写者准备好可以写，它就会尽可能快的完成它的写操作。同1问题不同，在一个写者后到达的读者必须等待，即使这个写者也是在等待。
解决方式：
通过信号量w控制对访问对象的临界区的访问。信号量mutex保护对共享变量readcnt的访问，readcnt统计当前在临界区中的读者数量。每当一个写者进入临界区时，w加锁，每当它离开临界区时，w解锁。这就保证了任意时刻临界区中最多只有一个写者。
另一方面，只有第一个进入临界区的读者对w加锁，而只有最后一个离开临界区的读者对w解锁。当一个读者进入和离开临界区时，如果还有其他读者在临界区中，那么读者会忽略互斥锁w。这就意味着主要还有一个读者占用互斥锁w，无限多数量的读者就可以没有障碍的进入到临界区中。
12.6 使用线程提高并行性
1、多线程可以使用多核。下图中给出了顺序、并发和并行程序之间的集合关系。所有程序的集合能够划分成不相交的顺序程序集合和并发程序的结合。写顺序程序只要一条逻辑流。写并发程序需要多条并发流。并行程序是在一个运行在多处理器上的并发程序。
2、单核上多线程运行时间反而会长，因为线程同步的开销，而并行程序则可以解决这一问题。在一个四核处理器上的多线程运行效率图如下：
当线程数量小于核心数时，运行效率提高，当线程数量大于核心数时，反而运行效率降低就是因为线程之间上下文切换等同步问题造成的开销。
由此理解单核下的多进程或多线程编程是为了进程或线程间的公平性问题，而效率并不会提高。
12.7 其他并发问题
1、线程安全
2、可重入性
3、在线程化的程序中使用已存在的库函数
4、竞争
5、死锁：可以通过下图来进一步理解死锁
【参考】
[1] 《深入理解计算机系统》
欢迎转载，转载请注明出处 wenmingxing 你好呀《CSAPP》
