深入理解计算机系统--并发编程概述（进程、IO多路复用、线程）_io复用和多线程冲突吗

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

一、基于进程的并发编程

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

注：进程间通信机制包括信号、socket、管道、共享内存、信号量

二、基于I/O多路复用的并发编程

        假如要求你编写一个echo服务器，它能处理网络请求，也能对用户从标准输入输出的交互命令作出相应。在这种情况下，服务器必须响应两个相互独立的I/O事件：(1)网络客户端发起的连接请求 (2)用户在键盘上键入命令行。我们先等待哪个事件呢？没有哪个选择是理想的。如果在accept中等待一个连接请求，我们就不能响应输入的命令。类似的，如果在read中等待一个输入命令，我们就不能响应任何连接请求。

        针对这种困境的一个解决办法就是I/O多路复用技术。基本思路就是使用select函数，要求内核挂起进程，只有在一个或多个I/O事件发生后，才将控制返回给应用程序。

        I/O多路复用可以用作并发事件驱动程序的基础，在事件驱动程序中，某些事情会导致流向前推进。一般思路是将逻辑流模型化为状态机。不严格地说，一个状态机就是一组状态、输入事件和转移，其中转移是将状态和输入事件映射到状态。每个转移是将一个（输入状态、输入事件）对映射到一个输出状态。自循环是同一输入和输出状态之间的转移。

        I/O多路复用优缺点：事件驱动设计的一个优点是，它比基于进程的设计给了程序员更多的对程序行为的控制 。例如，我们可以设想编写一个事件驱动的并发服务器，为某些客户端提供它们需要的服务，而这对于基于进程的并发服务器来说是很困难的。
        另一个优点是，一个基于 I/O 多路复用的事件驱动服务器是运行在单一进程上下文中的，因此每个逻辑流都能访问该进程的全部地址空间。这使得在流之间共享数据变得很容易。一个与作为单个进程运行相关的优点是，你可以利用熟悉的调试工具，例如 GDB来调试你的并发服务器，就像对顺序程序那样 。最后，事件驱动设计常常比基于进程的设计要高效得多，因为它们不需要进程上下文切换来调度新的流。
        事件驱动设计一个明显的缺点就是编码复杂。我们的事件驱动的程序所需要的代码比基于进程的相同功能的程序的代码多三倍，并且很不幸，随着并发粒度的减小，复杂性还会上升 。这里的粒度是指每个逻辑流每个时间片执行的指令数量 。只要某个逻辑流正在运行，其他逻辑流就不可能有进展。基于事件的设计另一个重要的缺点是它们不能充分利用多核处理器。

三、基于线程的并发编程

        基于线程是以上两种方法的混合。线程(thread) 就是运行在进程上下文中的逻辑流 。现代系统 允许我们编写一个进程里同时运行多个线程的程序 。线程由内核自动调度。每个线程都有它自己的线程上下文 (thread context)，包括一个唯一的整数线程 （Thread ID，TID）、栈、栈指针、程序计数器 、通用目的寄存器和条件码 。所有的运行在一个进程里的线程共享该进程的整个虚拟地址空间。
        基于线程的逻辑流结合了基于进程和基于 I/O 多路复用的流的特性 。同进程一样，线程由内核自动调度，并且内核通过一个整数 ID 来识别线程。同基于 I/O 多路复用的流一样，多个线程运行在单一进程的上下文中，因此共享这个进程虚拟地址空间的所有内容，包括它的代码 、数据 、堆 、共享库和打开的文件。        

        在任何一个时间点上，线程是可结合的 (joinable) 或者是分离的(detached)。 一个可结合的线程能够被其他线程收回和杀死 。在被其他线程回收之前，它的内存资源(例如栈)是不释放的 。相反 ，一个分离的线程是不能被其他线程回收或杀死的。它的内存资源在它终止时由系统自动释放。默认情况下，线程被创建成可结合的 。为了避免内存泄漏，每个可结合线程都应该要么被其他线程显式地收回，要么通过调用pthread detach 函数被分离。（join：等待某一线程结束，回收其资源；detach：不需要等待某线程，分离此线程，在此线程终止时会自动释放资源）

        从我们程序员的角度来看，线程很有吸引力的一个方面是多个线程很容易共享相同的程序变量 。然而，这种共享也是很棘手的 。为了编写正确的多线程程序，我们必须对所谓的共享以及它是如何工作的有很清楚的了解。为了理解 C 程序中的一个变量是否是共享的，有一些基本的问题要解答：（1）线程的基础内存模型是什么？（2）根据这个模型，变量实例是如何映射到内存的？（3）最后，有多少线程引用这些实例？一个变量是共享的，当且仅当多个线程引用这个变量的某个实例。
1.线程内存模型

        一组并发线程运行在一个进程的上下文中。每个线程都有它自己独立的线程上下文，包括线程 ID、栈、栈指针 、程序计数器 、条件码和通用目的寄存器值 。每个线程和其他线程一起共享进程上下文的剩余部分。这包括整个用户虚拟地址空间，它是由只读文本(代码 )、 读 / 写数据 、堆以及所有的共享库代码和数据区域组成的。线程也共享相同的打开文件的集合。
        从实际操作的角度来说，让一个线程去读或写另一个线程的寄存器值是不可能的 。另一方面 ,任何线程都可以访问共享虚拟内存的任意位置 。如果某个线程修改了一个内存位置，那么其他每个线程最终都能在它读这个位置时发现这个变化。因此，寄存器是从不共享的，而虚拟内存总是共 享的。

2.将变量映射到内存
        多线程的C程序中变量根据它们的存储类型被映射到虚拟内存:
        （1）全局变量。 全局变量是定义在函数之外的变量 。在运行时，虚拟内存的读 /写区域只包含每个全局变量的一个实例，任何线程都可以引用。
        （2）本地自动变量 。本地自动变量就是定义在函数内部但是没有 static 属性的变量。在运行时，每个线程的栈都包含它自己的所有本地自动变量的实例。即使多个线程执行同一个线程例程时也是如此 。
        （3）本地静态变量 。本地静态变量是定义在函数内部并有 static 属性的变量。 和全局变量一样，虚拟内存的读 / 写区域只包含在程序中声明的每个本地静态变量的一个实例 。

3.共享变量

        我们说一个变量是共享的，当且仅当它的一个实例被一个以上的线程引用。

4.用信号量同步线程

        信号量是一种经典的解决同步不同执行线程的问题的方法。信号量s是具有非负整数值的全局变量，只能由两种特殊操作来处理，这两种操作称为P和V

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

        P中的测试和减一操作是不可分割的，也就是说，一旦预测信号量s变成非0，就会将s减一，不能有中断。V中的加一操作也是不可分割的，也就是加载、加一和存储信号量的过程中没有中断。但是需要注意的是，V的定义中没有定义等待线程被重新启动的顺序，唯一的要求是V必须只能重启一个正在等待的线程。因此，当有多个线程在等待同一个信号量时，你不能预测V操作要重启那一个线程。

        P和V的定义确保了一个正在运行的程序绝不可能进入这样一个状态，也就是一个正确初始化了的信号量有一个负值。这个属性称为信号量不变性（semaphore invariant）

4.1 使用信号量来实现互斥

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

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

4.2 利用信号量来调度共享资源

        除了提供互斥之外，信号量的另一个重要作用是调度对共享资源的访问。在这种场景中，一个线程用信号量操作来通知另一个线程，程序状态中的某个条件已经为真了。两个经典有用的例子是生产者-消费者和读者-写者问题。

4.2.1 生产者-消费者问题

        生产者和消费者线程共享一个有n个槽的有限缓冲区。生产者线程反复的生成新的项目，并把它们插入到缓冲区中。消费者线程不断地从缓冲区中取出这些项目，然后消费他们。

        因为插入和取出项目都涉及更新共享变量，所以我们必须保证对缓冲区的访问是互斥的。但是只保证互斥访问是不够的，我们还需要调度对缓冲区的访问。如果缓冲区是慢的，那么生产者必须等待直到有一个槽位变为可用。与之相似，如果缓冲区是空的，那么消费者必须等待直到有一个项目变为可用。

 4.2.2 读者-写者问题

        读者-写者是互斥问题的一个概括。一组并发的线程要访问一个共享对象，例如一个主存中的数据结构，或者一个磁盘上的数据库。有些线程只读对象，而其他线程只修改对象。修改对象的线程叫做写者。只读对象的线程叫做读者。写者必须拥有对对象的独占的访问，而读者可以和无限多个其他的读者共享对象。一般来说，有无限多个并发的读者和写者。

I/O多路复用不是编写事件驱动程序的唯一方法，也可以编写基于线程的事件驱动程序

5. 使用线程提高并行性

        大多数现代机器具有多核处理器。并发程序通常在这样的机器上运行的更快，因为操作系统内核在多个核上并行的调度这些并发线程，而不是在单个核上顺序的调度。

        顺序、并发和并行程序之间的集合关系如下图所示

         所有程序的集合能够被划分成不相交的顺序程序集合和并发程序集合。写顺序程序只有一条逻辑流。写并发程序有多条并发流。并行程序是一个运行在多个处理器上的并发程序。因此，并行程序的集合是并发程序集合的真子集。

        并行编程的一项重要教训：同步开销巨大，要尽可能避免。如果无法避免，必须要用尽可能多的有用计算弥补这个开销。

6. 并发问题

6.1 线程安全

        当用线程编写程序时，必须小心的编写那些具有称为线程安全性属性的函数。一个函数被称为线程安全的，当且仅当被多个并发线程反复的调用时，他会一直产生正确的结果。如果一个函数不是线程安全的，我们就说她是线程不安全的

        我们能够定义出四个线程不安全函数类：

        第一类：不保护共享变量的函数。将这类线程不安全函数变成线程安全的，相对而言比较容易：利用像P和V操作这样的同步操作来保护共享的变量。这个方法的优点是在调用程序中不需要做任何修改，缺点是同步操作将减慢程序的执行时间。

        第二类：保持跨越多个调用的状态的函数。

        

         rand函数是线程不安全的，因为当前调用的结果依赖于前次调用的中间结果。如果我们在一个单线程中重复的调用rand，能够预期得到一个可重复的随机数字序列。然而，如果多线程的调用rand函数，这种假设就不再成立了

        使得像rand这样的函数线程安全的唯一方法就是重写他，使得它不再使用任何static数据，而是依靠调用者在参数中传递状态信息。这样做的缺点是，程序员现在还要被迫修改调用程序中的代码，在一个大的程序中，可能有成百上千个调用位置，这样做的修改是非常麻烦的，而且容易出错。

        第三类：返回指向静态变量的指针的函数。某些函数，例如ctime将计算结果放在一个static变量中，然后返回一个指向这个变量的指针。如果我们从并发线程中调用这些函数，那么将可能发生灾难，因为正在被一个线程使用的结果会被另一个线程悄悄地覆盖了。

        有两种办法来处理这类线程不安全函数。一种选择是重写函数，使得调用者传递存放结果的变量的地址。这就消除了所有共享数据，但是他要求程序员能够修改函数的源代码。

        如果线程不安全函数是难以修改或不可能修改（例如代码非常复杂或者没有源代码），那么另一种选择就是使用加锁-复制技术。基本思想是将线程不安全函数与互斥锁联系起来。在每一个调用位置，对互斥锁加锁，调用线程不安全函数，将函数返回的结果复制到一个私有的内存位置，然后对互斥锁解锁。为了尽可能减少对调用者的修改，你应该定义一个线程安全的包装函数，他执行加锁-复制，然后通过调用这个包装函数来取代所有对线程不安全函数的调用，下图给出了ctime的一个线程安全的版本，利用的就是加锁-复制技术

         第四类：调用线程不安全函数的函数。如果函数f调用线程不安全函数g，那么f就是线程不安全的吗？不一定。如果g是第二类函数，即依赖于跨越多次调用的状态，那么f也是线程不安全的，而且除了重写g之外，没有什么别的办法。然而，如果g是第一类或者第三类函数，那么只要你用一个互斥锁保护调用位置和任何得到的共享数据，f任然可能是线程安全的，如上图所示。

6.2 可重入性

        有一类重要的线程安全函数，叫做可重入函数，其特点在于他们具有这样一种属性：当他们被多个线程调用时，不会引入任何共享数据。尽管线程安全和可重入有时会被用作同义词，但是他们之间还是有清晰的技术差别，值得留意。下图展示了可重入函数、线程安全函数和线程不安全函数之间的集合关系。

         可重入函数通常比不可重入的线程安全函数高效一些，因为他们不需要同步操作。更进一步来说，将第二类线程不安全函数转化为线程安全函数的唯一办法就是重写他，使之变为可重入的。下图为rand函数的一个可重入版本。关键思想是我们用一个调用者传递进来的指针取代了静态的next变量

        linux系统提供了大多数线程不安全函数的可重入版本，可重入版本的名字总是以“_r”后缀结尾。

6.3 竞争 

        当一个程序的正确性依赖于一个线程要在另一个线程到达y点之前到达他的控制流中的x点时，就会发生竞争。通常发生竞争是因为程序员假定线程将按照某种特殊的轨迹线穿过执行状态空间，而忘记了另一条准则规定：多线程的程序必须对任何可行的轨迹线都正确工作。

6.4 死锁

        信号量引入了一种潜在的令人厌恶的运行时错误，叫做死锁，他指的是一组线程被阻塞了，等待一个永远也不会为真的条件。

        互斥锁加锁顺序规则：给定所有互斥操作的一个全序，如果每个线程都是以一种顺序获得互斥锁并且以相反的顺序释放，那么这个程序就是无死锁的。