《深入理解计算机系统》第12章笔记
如果逻辑流在时间上重叠，那么它们就是并发（concurrent）的。并发性不仅仅局限于内核，他也可以在应用中也扮演着重要的角色：
- 在多处理器上进行并行计算
- 访问慢速I/O设备
- 与人交互
- 通过推迟工作以减少执行时间
- 服务多个网络客户端
现代操作系统提供了三种基本的构造并发程序的方法：
- 进程。用这种方法，每个逻辑控制流都是一个进程，由内核来调度和维护。因为进程有独立的虚拟地址空间，想要和其他流通信，控制流必须使用某种显式的进程间通信(interprocess communication, IPC)机制。
- I/O 多路复用。在这种形式的并发编程中，应用程序在一个进程的上下文中显式地调度它们自己的逻辑流。逻辑流被模型化为状态机，数据到达文件描述符后，主程序显式地从一个状态转换到另一个状态。因为程序是一个单独的进程，所以所有的流都共享同一个地址空间。
- 线程。线程是运行在一个单一进程上下文中的逻辑流，由内核进行调度。你可以把线程看成是其他两种方式的混合体，像进程流一样由内核进行调度，而像 I/O 多路复用一样共享同一个虚拟地址空间。
基于进程的并发编程
构造并发程序最简单的方法就是用进程，使用那些大家都很熟悉的函数，像 fork, exec 和 waitpid。
对于在父、子进程间共享状态信息，进程有一个非常清晰的模型：共享文件表，但是不共享用户地址空间。进程有独立的地址空间既是优点也是缺点。这样一来，一个进程不可能不小心覆盖另一个进程的虚拟存储器，这就消除了许多令人迷惑的错误。
另一方面，独立的地址空间使得进程共享状态信息变得更加困难。为了共享信息，它们必须使用显式的 IPC 机制。基于进程的设计的另一个缺点是，它们往往比较慢，因为进程控制和 IPC 的开销很高。
基于I/O多路复用的并发编程
I/O 多路复用可以用作并发事件驱动(event-driven)程序的基础，在事件驱动程序中，流是因为某种事件而前进的。一般概念是将逻辑流模型化为状态机。不严格地说，一个状态机(state machine)就是一组状态(state)、输入事件(input event)和转移(transition)，其中转移就是将状态和输入事件映射到状态。每个状态都将一个(输入状态，输入事件)对映射到一个输出状态。自循环(self-loop)是同一组输入和输出状态之间的转移。通常把状态机花城有向图，其中节点表示状态，有向弧表示转移，而弧上的标号表示输入事件。一个状态机从某种初始状态开始执行。每个输入事件都会引发一个从当前状态到下一状态的转移。
事件驱动设计的一个优点是，它比基于进程的设计给了程序员更多的对程序行为的控制。另一个优点是在流之间共享数据变得很容易，而且事件驱动设计常常比基于进程的设计要高效得多，因为它们不需要进程上下文切换来调度新的流。
事件驱动设计的一个明显的缺点就是编码复杂，另一重大缺点时它们不能充分利用多核处理器。
基于线程的并发编程
一个线程（thread）就是运行在一个进程上下文中的一个逻辑流。每个线程都有它自己的线程上下文(thread context)，包括一个唯一的整数线程ID(Thread ID, TID)、栈、栈指针、程序计数器、通用目的寄存器和条件码。所有的运行在一个进程里的线程共享该进程的整个虚拟地址空间。
基于线程的逻辑流结合了基于进程和基于I/O多路复用的流的特点
线程执行模型
多线程程序中的共享变量
线程很有吸引力的一个方面就是多个线程很容易共享相同的程序变量
线程存储器模型
一组并发线程运行在一个进程的上下文中。每个线程都有它自己独立的线程上下文，包括线程 ID、栈、栈指针、程序计数器、条件码和通用目的寄存器。每个线程和其他线程一个共享进程上下文的剩余部分。这包括整个用户虚拟地址空间，它是由只读文本(代码)、读/写数据、堆以及所有的共享库代码和数据区域组成的。
从实际操作的角度来说，让一个线程去读写另一个线程的寄存器是不可能的。寄存器不是共享的，而虚拟存储器是共享的。
将变量映射到存储器
线程化的 C 程序中变量根据它们的存储类型被映射到虚拟存储器：
- 全局变量：在运行时，虚拟存储器的读/写区域只包含每个全局变量的一个实例，任何线程都可以引用
- 本地自动变量：定义在函数内部但是没有 static 属性的变量。在运行时，每个线程的栈都包含它自己的所有本地自动变量的实例
- 本地静态变量：定义在函数内部并有 static 属性的变量，和全局变量一样
用信号量同步线程
共享变量十分方便，但是它们也引入了同步错误（synchronization error）的可能性。
进度图
一个进度图( progress graph)将个并发线程的执行模型化为一条维笛卡儿空间中的轨线。 每条轴k对应于线程k的进度。每个点(1,2…,n)代表线程k(k=1,,n)已经完成了指令I(k)这一个状态
一个进度图将指令执行模型化为一个从一种状态到另一种状态的转換( transition)。一个转换被 表示为一条从一点到相邻点的有向边。合法的转换是向右(线程1中的一条指令完成)或者向上(线 程2中的一条指令完成)的。两个指令不能在同一时刻完成一一对角线转換是不允许的。程序决不 会反向运行,所以向下或者向左移动的转换也是不合法的。
环绕不安全区的轨线叫做安全轨线( safe trajectory)。相反,接触任何不安全区的轨线就叫做不安全轨线( unsafe trajectory)。
任何安全轨迹都将正确地更新共享计数器。
利用信号量访问共享变量
一种经典的解决同步不同执行线程问题的方法：基于一种叫做信号量( semaphore)的特殊类型变量的。信号量s是具有非负整数值的全局变量,只能由两种特殊的操作来处理,这两种操作称为P和V。
- P(s):如果s是非零的,那么P将s减1,并且立即返回。如如果s为零,那么就挂起进程, 直到s变为非零,并且该进程被一个V操作重启。在重启之后,P操作将s减1,并将控制 返回给调用者。
- V(s):操作将s加1。如果有任何进程阻塞在P操作等待s变成非零,那么V操作会重启 这些进程中的一个,然后该进程将s减1,完成它的P操作
P和和V的定义确保了一个运行程序绝不可能进入这样一种状态,也就是一个正确初始化了的信 号量有一个负值。这个属性称为信号量不变性( semaphore invariant),为控制并发程序的轨线而避 免不安全区提供了强有力的工具。
基本的思想是将每个共享变量(或者相关共享变量集合)与一个信号量s(初始为1)联系起来, 然后用P(s)和W(s)操作将相应的临界区包围起来。以这种方式来保护共享变量的信号量叫做二进制 信号量( binary semaphore),因为它的值总是0或者1。
利用信号量来调度共享资源
信号量另一个重要的作用是调度对共享资源的访问，一个线程用信号量来通知另一个线程，程序状态中的某个量已经为真了。
其他并发性问题
线程安全
当我们用线程编写程序时,我们必须小心地编写那些具有称为线程安全性( thread safety)属性 的函数。一个函数被称为线程安全的( thread- safe),当且仅当被多个并发线程反复地调用时,它会 一直产生正确的结果。如果一个函数不是线程安全的,我们就说它是线程不安全的( thread-unsafe)。 我们能够定义出四类(有相交的)线程不安全函数:
- 不保护共享变量的函数
- 保持跨越多个调用的状态的函数
- 返回指向静态变量的指针函数
- 调用线程不安全函数的函数
可重入性
有一类重要的线程安全函数,叫做可重入函数( reentrant function),其特点在于它们具有这样 种属性:当它们被多个线程调用时,不会引用任何共享数据。
竞争
当一个程序的正确性依赖于一个线程要在另一个线程到达y点之前到达它的控制流中的x点时, 就会发生竞争(race)。通常发生竟争是因为程序员假定线程将按照某种特殊的轨线穿过执行状态空 间,而忘记了另一条准则规定定:多线程程序必须对任何可行的轨线都正确工作。
死锁
一组线程被阻塞了，等待一个永远也不会为真的条件
小结
无论哪种并发机制，同步对于共享数据的并发访问都是一个困难的问题。提出对信号的 P 和 V 操作就是为了帮助解决这个问题。信号量操作可以用来提供对共享数据的互斥访问，也对诸如生产者-消费者程序中有限缓冲区和读者-写者系统中的共享对象这样的资源访问进行调度。
并发也引入了其他一些困难的问题。被线程调用的函数必须具有一种称为线程安全的属性。竞争和死锁是并发程序中出现的另一些困难的问题。当程序员错误地假设逻辑流该如何调度时，就会发生竞争。当一个流等待一个永远不会发生的事件时，就会产生死锁。
