一个CPU 对应多个进程同时运行 —— 伪并发 ， 区分多处理器系统。
操作系统的设计者开发了用于描述并行的一种概念模型(顺序进程)， 使得并行更容易出离。 —— 进程的概念模型
2.1.1. 进程模型
1）计算机上所有可运行的软件，通常也包括操作系统，被组织成若干顺序进程(sequential process) , 简称： 进程
2）一个进程就是一个正在执行程序的实例， 包括程序计数器、寄存器和变量的当前值。
3）关键思想： 已给进程是某种类型的一个活动， 它有程序、输入、输出以及状态。
4） 单个CPU可以被若干进程共享， 它使用某种调度算法决定何时停止一个进程的工作，并转而为另一个进程提供服务。
2.1.2 进程创建
4种事件会导致进程的创建：
1）系统初始化
2）正在运行的程序执行了创建进程的系统调用，Unix （fork）
3）用户请求创建一个新进程
4）一个批处理作业的初始化
在UNix和windows中， 进程创建之后，父进程和子进程有各自的不同的地址空间。 如果其中某个进程在其他空间中修改一个字， 这个修改对其他进程而言是不可见的。
1）在Unix中， 子进程的初始地址空间是父进程的一个副本，但是这里涉及两个不同的地址空间，不可写的内存区是共享的。某些Unix的实现使程序正文在两者间共享， 因为它不可能被修改。 或者，子进程共享父进程的所有内存，但这种情况下内存通过写时赋值(copy-on-write) 共享， 这意味着一旦两者之一想要修改部分内存， 则这快内存首先被明确地复制，以确保修改发生在私有内存区域。再次强调，可写的内存是不可以共享的，但是， 对于一个新创建的进程而言，确实有可能共享其创建者的其他资源，诸如打开文件等，
2）在windows中，一开始父进程的地址空间和子进程的地址空间就不同。
2.1.3 进程终止
进程终止引起的条件：
1）正常退出（自愿）
2）出错退出 （自愿）
3）严重错误 （非自愿）
4）被其他进程杀死（非自愿）
Unix 某个继承执行系统的调用通知操作系统杀死某个其他进程。kill。
2.1.4 进程的层次结构
进程是一个独立的实体，包含有：程序计数器和内部状态。。。
进程之间是需要交互的， 一个进程的结果可能是另外一个进程的输入
cat home_rec.json home_rec1.json info_stream.json | grep display_type
- cat 将3个文件接连输出， grep程序从中选择所有包含单词display_type的那一行。
- 根据这两个进程的相对速度，可能发生这种情况： grep 准备就绪可以运行， 但输入还没有完成。于是，必须阻塞grep，直到输入的到来。
一个进程在逻辑上不能够运行时， 就会阻塞。
1） 等待可以使用的输入
2）能够运行的进程被迫停止， 因为操作系统调度另一个进程占用了CPU。
进程的3种状态：
1）运行态（该时刻进程实际占用CPU）
2）就绪态 （可运行，但因为其他进程正在运行而暂时停止）
3）阻塞态 （除非某种外部事件发生，否则进程不能运行）
进程状态的转换图
1）1: 操作系统发现进程不能继续运行下去时； 在一些系统中，pause的执行系统进入阻塞状态。 在其他系统中（包括Unix）， 但一个进程从管道或设备文件（例如：终端）读取数据时， 如果没有有效的输入存在，则进程会被自动阻塞。
2）2、3： 由进程调度引起的；
进程调度是操作系统的一部分， 进程甚至感觉不到调度程序的存在。 调度程序决定应当运行哪个进程、何时运行及它应该运行多长时间。 这是很重要的一点。 调度算法：力图在整体效率和进程的竞争公平性之间取得平衡。
系统认为一个运行进程占用处理器时间已经过长， 决定让其他进程使用CPU运行时， 会发生2。
在系统已经让所有其他进程享有了它们应有的公平待遇而重新轮到第一个进程再次占用CPU运行时， 会发生3。
3）当进程等待一个外部事件发生时，则发生转换4。 如果此时没有其他进程运行， 则立即触发转换3，该进程便开始运行，否则该进程将处于就绪态。 等待CPU空闲并且轮到它运行。
使用进程模型使得我们易于想象系统内部的操作情况。 一些进程正在运行执行用户键入命令所对应的程序。 另一些进程是系统的一部分， 它们的任务是完成下列工作：
eg：执行文件服务请求、管理磁盘驱动器、 磁带机的运行细节等。
当发生一个磁盘中断时， 系统会做出决定，停止运行当前进程， 转而运行磁盘进程，该进程在此之前因等待终端而处于阻塞状态。 这样，我们就可以不在考虑终端，而只是考虑用户进程、磁盘进程、终端 进程等。 这些进程在等待时总是处于阻塞状态。 在已经读入磁盘或键入字符后， 等待它们进程就被解除阻塞，并成为可调度运行的进程。
操作系统的最底层是调度程序， 在它上面有许多进程。 所有关于终端处理、启动进程和停止进程的具体细节都隐藏在调度程序中。
实际上， 调度程序是一段非常小的程序。 操作系统的其他部分被简单地组织成进程的形式。
2.1.6 进程的实现
操作系统维护着一张表格(一个结构数组)，即进程表(process table)。 每个进程占用一个进程表项[进程控制块]。
表项：包括程序计数器、堆栈指针、内存分配状况、锁打开文件的状态、账号和调度信息，以及其他在进程由运行状态转换到就绪或阻塞时必须保存的信息。 —— 从而保证该进程随后能够再次启动， 就像从未被中断一样。
进程表项中管理的范畴： 进程管理、存储管理、文件管理
- 与每个I/O类关联的是一个称作终端向量(interrupt vector)的位置【靠近内存底部的固定区域】。 它包含终端服务程序的入口地址。 eg: 当一个磁盘中断发生时，用户进程3正在运行，则中断硬件将程序计数器、程序状态字，有时候还有一个或者多个寄存器压入堆栈， 计算机随即跳转到中断向量指示的地址。 这些是硬件完成的所有操作， 然后软件特别是中断服务例程就接管一切剩余的工作。
- 所有的中断都从保存寄存器开始， 对于当前进程而言，通常是在进程表项中。 随后， 会从堆栈中删除由中断硬件机制存入堆栈的部分信息， 并将堆栈指针指向一个进程处理程序所使用的临时堆栈。
- 当该例程结束后， 它调用一个C过程处理某个特定的中断类型剩余的工作。 在完成有关工作会后， 大概就会使某些进程就绪，，接着调用调度程序，决定随后改运行那个进程。 随后将控制转给一段汇编语言代码，， 为当前的进程装入寄存器值以及内存映射并启动该进程运行。
2.1.7: 多道程序设计模型
—— 提高CPU的利用率
概率： CPU利用率 = 1 - p^n
n ： n个进程同时都在等待IO的概率 p^n
2.2 线程
传统操作系统中： 每个进程有一个地址空间和一个控制线程。 —— 进程的定义。
进程存在同一个的控制空间中准并运行多个控制线程的情形，这些线程就像分类的进程【共享地址空间除外】。
2.2.1 线程的使用
为什么人们需要在一个进程中再有一类进程？
1）主要原因：在许多应用中同事发生这多种活动。 其中某些活动随着时间的推移会被阻塞。 通过将这些应用程序分解成可以准并运行的多个顺序线程， 程序设计模型会变更加简单。
关于进程模型的讨论。 我们不惜要考虑中断、定时器和上下文切换， 而只需要考察并行进程。 只有在多线程概念之后， 我们才加入了一种新的元素： 并行实体共享同一个地址空间和所有可用数据的能力。 而多进程模型(它们具有不同的地址空间)所无法表达的。
2）线程比进程更加轻量级，更加容易创建和销毁。 可能相差2~3个数量级。 在大量线程需动态和快速修改时，这个特性很有用。
3）性能方面： 若多个线程是CPU密集型的， 那么并不能获得性性能上的增强， 但是如果存在着大量的计算和大量的I/O处理， 拥有多个线程允许这些互动功能彼此重叠进行，从而会加快应用程序的执行速度。
4）在多CPU 系统中， 多线程是有溢的， 这样的系统中， 真正的并行有了实现的可能。
一个写字的软件， 用户交互、格式重置、文本备份。
上面的两个例子， 前面进程的“顺序进程”模型消失了。 每次服务器从为某个请求工作的状态切换到另一个状态时，都必须显式地 保存或重新装入相应的计算状态。 事实上， 我们以一种困难的方式模拟了线程以及堆栈。 每个计算都有一个被保存的状态，存在一个会发生并且使得相关的状态发生改变的事件集合， 把这类设计称为 有限状态机[finite-state machine]
- 多线程使得 顺序进程的思想得以保留下来， 这种顺序进程阻塞了系统调用(eg：磁盘IO)， 但是仍然实现了并行性。
- 对系统调用进行阻塞使程序设计变得较为简单，并行性改善了性能。 单线程服务器虽然保留了阻塞系统调用的简易性，但是确放弃了性能。
运用非阻塞调用和中断， 通过并行性是瞎按了高性能，但是给变成增加了困难。
2.2.2 经典的线程模型
进程模型基于两种独立概念： 资源分组处理与执行
【以后会研究模型进程与线程分界线 的Linux线程模型】
进程理解的角度：
1）用某种方法吧相关的资源集中在一起， 进程有存放程序正文和数据以及其他资源的地址空间。 这些资源中包括：打开的文件、子进程、即将发生的报警、幸好处理程序、账号信息等。把他们都放到进程中可以更容易管理。
2）进程拥有一个执行的线程[简称：线程]。在线程中有一个成功需计数器，用来记录接着要执行哪一条指令。线程拥有寄存器，用来保存线程当前的工作变量。 线程还拥有一个堆栈，用来记录执行历史， 其中每一帧都报尺寸了一个已经调用的但是还灭有从返中返回的过程。 尽管线程必须在某个进程中执行，但是线程和它的进程是不同的概念了，并且可以分别处理。 进程用于吧资源集中大搜一起， 而线程则是在CPU上被调度执行的实体。
- 线程给进程模型增加了一项你额偶人那个， 即在同一个进程环境中， 允许彼此之间有较大的独立性的多个线程执行。在同一个进程中并行运行多个线程，是对同一台计算机上并行运行多个进程的模拟。 在前一种清新乡下，多个线程共享同一个地址空间和其他资源，后面一种， 多个进程共享物理内存、磁盘、打印机和其他资源。 由于线程具有进程的某些性质，所以有时被称为
轻量级进程【light weight process】. 多线程： 描述了同一个进程中允许多个线程的情形。
线程的概念是视图实现的是：共享一组资源的多个线程的执行能力， 以便这些线程可以为完成某一个任务而共同工作。
线程和传统的进程一样，可以多个状态中的任何一个： 运行、阻塞、就绪、终止。
每个线程有自己的堆栈， 这个是慎重啊哟的， x调用y,y调用z，当执行到z的时候，堆栈会把x/y/z 使用的帧全部存放到堆栈中。 通常每个线程调用不同的过程，从而有一个各自不同的执行历史。 这就是为什么每个线程需要有自己的堆栈的原因。
在一个线程中，调用一个库函数【thread_create】创建一个新的线程，一般来说，线程之间都是平等的。
当线程完成了工作之后，会调用库函函数[thread_exit]退出，改线程就销毁了。
Q: 如果父进程有多线程，那么它的子进程也应该拥有这些线程吗？ 如果不是，则该进程可能会工作不正常，因为在该子进程都是绝对必要的。
如果子进程拥有了父进程一样的多线程，如果父进程在read系统调用(eg：键盘)上被阻塞了会发生什么情况？ 是两个线程被阻塞在键盘上(一个属于父进程、一个属于子进程)吗？ 在键盘输入一行输入之后，这两个线程都得到改输入的副本吗？还是仅有父进程得到改输入的副本？ 或者仅有子进程得到？ 类似的问题在进行网络连接时也会出现。 ？？？ 这个问题怎么理解？
另一类问题和线程共享许多数据结构的事实有关。 如果一个线程关闭某个文件，而另一个线程还在该文件上进行操作时会怎么样？假设有一个线程注意到几乎没有内存了， 并开始分配更多的聂村。 在工作一半的饿时候， 发生线程切换，该线程也注意到几乎没有内存了， 并且也开始分配更多的内存。 这样， 内存可能会分配两次。 不过这些问题通过努力是可以解决的。
2.2.3 POSIX 线程
PThread 线程都有某些特性。 每个都含有一个标识符、一组寄存器（包括程序计数器）和一组存储在结构中的属性、 属性包括：堆栈大小、调度参数以及使用线程需要的其他项目。
2.2.4 在用户空间中实现线程
两种方式实现线程包： 用户空间中和内核中
1）把整个线程包放在用户空间中， 内核对线程包一无所知。 从内核角度考虑，就是按正常的方式管理，即单线程进程。 最优点：用户线程包可以在不支持线程的操作系统上实现。
1） 线程在一个运行时系统的顶部运行， 这个运行时系统是一个管理线程的过程集合。
2）每个进程需要有其专用的线程表（thread table）， 用来跟踪该进程中的线程。这些表和内核中的进程表类似， 不过它仅仅记录各个线程的属性，eg:线程的程序计数器、堆栈指针、寄存器和状态等。在该线程表中存放重新启动该线程所需的信息， 与内核在进程表中存放进程信息完全一样。
3）当某个线程做了一些会引起在本地阻塞的事情之后，
eg: 等待进程中另一个线程完成某项操作， 它调用一个运行时系统的过程，这个过程检查该线程是否必须进入阻塞状态。 如果是， 它再线程中保存改线程的寄存器，查看表中可运行的就绪线程，并把新线程的保存至重新装入机器的寄存器中。只要堆栈指针和程序计数器一旦被切换，新的线程就又自动投入运行。如果机器有一条保存所有寄存器的指令和另一条装入全部寄存器的指令， 那么整个线程就又自动投入运行。 如果机器有一条保存所有寄存器的指令和另一条装入全部寄存器的指令， 那么整个线程的切换可以在几条指令内完成。 这样的线程切换比陷入内核要快一个数量级。 —— 用户线程包的极大的优点。
4）线程和进程一个关键的差别：在线程运行完成的时， eg：调用thread_yield 代码可以把该线程的信息保存在线程表中，进而，它可以调用线程调度程序来选择另一个要运行的线程。（1）保存改线程状态的过程和调度程序只是本地过程，所以启动它们比进行内核调用效率更高。 （2）不需要陷阱，不需要上下文切换，也不需要对内存告诉缓存进行刷新，这个就使得线程调度非常快捷。
5）还有的另一个优点，它允许每个进程有自己定制的调度算法。eg：某些应用程序中，那些有垃圾收集线程的应用程序就不用担心线程会在不合适的时刻停止。 用户级的线程有比较好的扩展性， 这是因为在内核空间中内核线程需要一些固定表格空间和堆栈空间。如果内核线程的数量非常大，就会出现问题。
缺点：
1）如何实现阻塞系统调用。假设在还没有任何击键之前，一个线程读取键盘。让该线程实际进行该系统调用是不可接受的，因为这会停止所有的线程。使用线程的一个主要目标是，首先要允许每个线程使用阻塞调用，但是还要避免被阻塞的线程影响其他的线程。 有了阻塞系统调用， 这个目标不是轻易地能够实现的。
2） 系统调用可以修改成为非阻塞的，但是这个需要修改操作系统，并且用户级的线程最理想的目的就是在操作系统之上实现的额。
3）如果某个调用会阻塞，就提前通知。 eg：select获取数据调用read， 判断是否阻塞，如果不阻塞并且安全，就进行read。否则，运行另一个线程。到下一次运行系统取得控制权之后，在判断read。 这个方法需要重写系统调用库，效率不高不优雅。 在系统调用周围从事检查的种类代码成为包装器(jacket /wrapper)
4） 如果一个线程开始运行，那么在该进程中的其他线程就不能运行， 除非第一个线程自动放弃CPU。 在一个单独的进程内部， 没有时钟中断， 所以不可能用轮流调度(轮流)的方式调度进程。 除非某个线程能够按照自己的意志进入运行时系统，否则调度程序就没有任何机会。 可以通过运行时系统请求1次/s 的时钟信号[中断]，这样生硬、并且耗费很多资源，同时扰乱运行时系统使用的时钟。
image.png
2.2.5 在内核中实现线程
内核的线程，就不需要运行时系统了。 并且每个进程中也没有线程表。在内核中用来记录系统中所有线程的线程表。 当某个线程希望创建一个新线程或者撤销一个已有线程时， 它进行一个系统调用， 这个系统调用通过对线程表的更新完成线程的创建或撤销工作。
- 内核的线程表保存了每个线程的寄存器、状态和其他信息。 这些信息和在用户空间中(在运行时系统中)的线程是一样的， 但是现在保存在内核中。 这些信息是传统内核锁维护的每个线程进程信息(即进程状态)的字迹。另外，内核还维护了传统的进程表以便跟踪进程的状态。
- 所有能够阻塞线程的调用都以新系统调用的形式实现的， 这与运行时系统过程相比，代价是相当可观的。 当一个线程阻塞时， 内核根据其选择，可以运行同一个进程额另一个线程，或者运行另一个进程中的线程。直达内核剥夺了它的CPU(或者没有课运行的线程存在了)为止。
- 由于内核中创建或撤销线程的代价较大时，某些系统采取"环保"的处理方式， 回收其线程。 当某个线程被撤销时，就把它标志为不可运行的， 但是其内核数据结构没有收到影响。 稍后，在必须创建一个新线程时，就重新启动某个旧的线程， 从而节省了一些开销。 在用户级线程中线程回收也是可能的，但是由于其线程管理的代价很小， 所以没有必要进行这项工作。
4） 内核线程不需要任何新的、非阻塞系统调用。如果某个进程中的线程引起了页面故障，内核可以很方便地检查改进程是否有任何其他可运行的线程， 如果有，在等待所需要的页面从磁盘读入时，就选择一个可运行的线程运行。 这样做的主要缺点是系统调用的代价比较大，所以如果线程的操作(创建、终止等)比较多，就会带来很大的开销。
5）虽然内核线程解决了很多问题，但是不会解决所有的问题。 例如：当一个多线程创建新的进程时，会发生什么？ 新进程是拥有与原进程相同数量的线程， 还是只有一个线程？ —— 很多情况下， 最好的选择取决于进程计划的下一步做什么。 如果它要调用exec来启动一个新的程序， 或许一个线程是正确的选择； 但是如果它继续执行，则应该复制所有的线程。
6）信号是发给进程而不是线程的， 至少在经典模型中是这样的。 当一个信号到达时，应该由哪个线程处理它？ 线程可以注册它们感兴趣的某些信号， 因此当一个信号到达的时候，可把它交给需要它的线程。 但是如果两个或更多的线程注册相同的信号，会发生什么？
2.2.6 混合实现
试图将用户级线程的有点和内核级线程的有点结合起来的方法。
使用内核级线程，然后将用户级线程与某些或者全部内核线程多路复用起来。 变成人员可以决定有多少个内核级线程和多少个用户线程彼此多路复用。 这一模型带来最大的灵活度。 —— 采用这种方法， 内核只识别内核线程，并对其进行调度。 其中一些内核级线程会被多个用户级线程多路复用。 如同在没有多线程能力操作系统中某个进程中的用户级线程一样，可以创建、销毁和调度这些用户级线程。 这种模型中，每个内核线程有一个可以轮流使用的用户级线程集合。
2.2.7 调度程序激活机制 —— 类似调用的机制
内核级线程在一些关键点上优于用户进程， 但无可争议的是内核线程的速度慢。
设计保证优良特性的前提下改进其速度的方法 —— 调度程序激活(scheduler activation)机制。
调度程序激活工作的目标是模拟内核线程的功能，但是为线程包提供通常在用户空间中才能实现的更好的性能和更大的灵活性。 如果用户线程从事某种系统调时是安全的，那就不应该进行专门的非阻塞调用或者进行提前检查。 无论如何， 如果线程阻塞在某个系统调用或者页面故障上， 只要在同一个进程中有任何就绪的线程，就应该有可能运行其他的线程。
为了避免了在用户空间和内核空间之间的不必要转换， 从而提高了效率。 eg：如果某个线程由于等待另一个线程的工作而阻塞，此时没有理由请求内核，这样就减少了内核—用户转换的开销。 用户空间的运行时系统可以阻塞同步的线程而另外调度一个新线程。
当使用调度程序激活机制时，内核给每个进程安排一定数量的虚拟处理器，并且让(用户空间)运行时系统将线程分配到处理器上。这一机制也可以用在多处理器中，此时虚拟处理器可能能成为真实的CPU。 分配给一个进程的虚拟处理器的初始数量是一个，但是该进程可以申请更多的处理器并且在不用时退回。内核也可以取回已经分配出去的虚拟处理器，以便于把它们分给需要更多处理器的进程。
使该机制工作的基本思想是：当内核了解到一个线程被阻塞之后(eg: 由于执行一个阻塞系统调用或产生一个页面故障)，内核通知该进程的运行时系统，并且在堆栈中以参数形式传递有问题的线程编号和所发生事件的一个描述。内核通过在一个已知的起始地址启动运行时系统，从而发出了通知，这是对Unix中信号的一种粗略模拟。 —— 这个机制成为上行调用(upcall)。
一旦如此激活，运行时系统就重新调度其线程，这个过程通常是这样的： 把当线程标记为阻塞并从就绪表中取出另一个线程， 设置其寄存器，然后再启动之。稍后，当内核知道原来的线程有可运行时(eg: 原先视图读取的管道中有了数据， 或者已经从磁盘中读入了故障的页面)，内核就又一次上行调用运行时系统，通知它这一事件。 此时改运行时系统按照自己的判断，或者立即重启动被阻塞的线程，或者把它放入就绪表中稍后运行。
当某个用户线程运行的同时发生一个硬件中断时，被中断的CPU切换进核心态。 如果被中断的进程对引起改中断的时间不感兴趣，eg： 是另一个进程的IO完成了，那么在中断处理程序结束时候，就把终端店额线程回复到中断之前的状态。 不过，如果该进程对中断感兴趣，eg: 是该进程的某个线程锁需要的页面到达了，那么被中断的线程就不再启动，代之为挂起被中断的线程。 在运行时系统则启动对饮的虚拟CPU，此时被中断线程的状态保存在堆栈中。 随后，运行时系统决定在该CPU上调度那个线程： 被中断的线程，新就绪的线程还是某个第三种选择。
调度程序激活机制的一个目标是作为上行调用的信赖基础， 这是一种违反分层次系统内在结构的概念。 通常，n层提供 n+1 层可调用的特定服务，但是n层不能调用n+1层中的过程。 上行调用并不遵守这个基本原理。
2.2.8 弹出式线程 【暂时略过】
在分布式系统中经常使用线程。 一个有意义的例子是如何处理到来的消息。eg：服务请求。 传统的方法是将进程或线程阻塞在一个receive系统上， 等待消息到来。 当消息到达时， 该系统调用接收消息， 并打开消息检查其内容。 然后进行处理。
不过， 也可能有另一种完全不同的处理方式， 在该处理中， 一个消息的到达导致系统创建一个处理该消息的线程， 这种线程成为弹出式线程
2.2.9 使单线程代码多线程化
—— 感觉这里是否和 “协成”类似；
序偶多已有的陈旭是为了单线程进程编写的， 这些吧程序改写成多线程需要比直接写多线程程序更高的技巧。
一个线程的代码就像进程一样，通常包含多个过程，会有局部变量，全局变量和过程参数。
2.3 进程间通信
进程进程需要与其他进程通信。
eg： 一个shell管道中，第一个进程的输出必须传给第二个级才能拿，这样沿着管道传递下去。 因此这个进程之间需要通信，而且最好使用一种结构良好的方式， 不要使用中断。 导论一些有关进程间通信(inter process communication ，IPC)的问题。
三个问题：
1）一个进程如何把信息传递给另一个。
2）确保两个或更多的进程在关键活动中不会出现交叉，
3）与正确的顺序有关 ， eg: 如果进程A产生数据而进程B打印数据，那么B在打印之前必须等待， 知道A已经产生一些数据。
【这三个问题对于线程来说是同样适用的】
第一个问题对线程比较容易， 因为共享地址空间。
进程间的一些问以及解决方案， 同样适用在线程。
2.3.1 竞争条件
在一些操作系统中， 协作的进程可能共享一些彼此都能读写的公用存储区。 这个公共存储区可能在内存中(可能是在内核数据结构中)， 也可能是一个共享文件。 这里的共享存储区的位置并不影响通信的本质及其带来的问题。【例子： 一个假脱机打印程序。 当一个进程需要打印一个文件时， 它将文件名放在一个特殊的假脱机目录(spooler directory)下。 另一个进程(打印机守护进程)则周期性地检查是否有文件需要打印， 若有就打印并将改文件名从目录下删掉。(脱机 —— 竞争条件[race condition]) 】。
2.3.2 临界区 —— 避免竞争条件
怎么避免竞争条件？ 产生的场景： 共享内存、共享文件以及共享任何资源的情况都会引发与前面类似的错误。
——> 关键是要找出某种途径来阻止多个进程同事读写共享的数据。 —— 也就是我们需要的是互斥(mutual exclusion), 即以某种收端确保当一个进程在使用一个共享白能量或文件时，其他进程不能做同样的操作。
—— 为了实现互斥而选择适当的源语是任何操作系统的主要设计内容之一。
一个进程的一部分时间内部计算或另外一些不会引发竞争条件的操作。 在某些时候进程可能需要访问共享内存或共享文件，或执行另外一些会导致竞争的操作。 我们把共享内存进行访问的程序片断称作临界域(cirtical region)或者临界区(critical section)。 使得两个进程不可能同时处于临界区中，就能够避免竞争条件。
尽管这样的要求避免了竞争条件， 但它还不能够使用共享数据的并发进程能够正确和高效的进行协作。
好的解决方案，包括4个条件：
1） 任何两个进程不能同事处于临界区
2）不应对CPU的速度和数量做任何的假设
3）临界区外运行的进程不得阻塞其他进程
4）不得使进程无限期等待进入临界区
进程A在T1时刻进入临界区， 稍后， 在T2时刻进程B视图进入临界区， 但是失败了，因为另一个进程已经在该临界区内，而一个时刻只允许一个进程在理解区内。 随后， B被暂时挂起直到T3时刻A离开临界 区为止， 从而允许B立即进入。 最后,B离开(在时刻T4)， 会到了在临界区中没有进程的原始状态。
2.3.3 忙等待的互斥
当一个进程在临界区中更新共享内存时， 其他进程将不会进入其临界区， 也不会带来任何麻烦。
1、屏蔽中断
在单处理器系统中，最简单的方法是使每个进程在刚刚进入临界区后立即屏蔽所有中断，并在就要离开之前再打开中断。 屏蔽中断后， 时钟中断也被屏蔽。 CPU只有发生时钟中断或其他中断时才会进行进程切换， 这样，在屏蔽中断之后CPU将不会被切换到其他进程。 于是，一旦某个进程屏蔽中断之后，它就可以检查和修改共享内存，而不必担心其他进程介入。
—— 这个方案并不好，因为把屏蔽中断的权利交给用户进程是不明智的。 设想一下， 若一个进程屏蔽中断后不再打断中断，其结果将会如何？ 整个系统可能会因此终止。 而且，如果系统是多处理系统,则屏蔽中断仅仅对执行disable指令的那个CPU有效。 其他的CPU仍然继续运行，并可以访问共享内存。
—— 另一方面， 对内核来说，当它再更新变量或列表的几条指令期间将中断屏蔽是很方便的。 当就绪进程队列之类的数据状态不一致时发生中断，则将导致竞争条件。 所以结论是：屏蔽中断对操作系统本身而言是一项很有用的技术，但对于用户进程则不是一种合适的通用互斥机制。
—— 由于多核芯片的数量越来越多， 屏蔽一个CPU的中断不会组织其他CPU干预第一个CPU所做的操作。 结果是人们需要更加复杂的计划。
2、 锁变量
寻找一种软件解决 方案。 设想一下一个共享（锁）变量， 其初始值为0。 当一个进程想进入其临界区域时， 它首先测试这把锁。 如果改锁的值为0， 则该进程将其设置为1并进入临界区。若这把锁的值已经为1， 则该进程将等待直到其值变成为0. 于是，0 就表会死临界区内没有进程，1表示已经有某个进程进入临界区。
但是，这样也有可能出现竞争的资源的条件。 和脱机目录一样。
3、严格轮换法 —— 自旋锁
整个变量turn， 初始值为0， 用于记录轮到那个进程进入临界区，并检查或更新共享内存。 开始时，进程0检查turn，发现其值为0，于是进入临界区。 进程1也发现其值为0，所以在一个等待循环中不停地测试turn，看其值何时变成1. 连续测试一个变量知道某个值出现位置，称为
忙等待(busy waiting)。这种方式浪费CPU时间，所以通常应该避免。只有在有理由认为等待时间是非常段的情形下，才使用忙等待。 用于忙等待的锁， 成为 自
旋锁 (spin lock)
进程0离开临界区时，它将turn值设置为1， 以便允许进程1进入临界区。 假设进程1很快便离开了临界区，则此时两个进程都处于临界区之外， turn的值又被设置0。 现在进程0很快就执行完整个循环， 它退出临界区， 并将turn 的值设置为1. 此时turn的值为1，两个进程都在其临界区外执行。 突然， 进程0结束了非临界区的操作并且返回到循环的开始。 但是，这时它不可进入临界区，因为turn的当前值为1， 而此时进程1还在忙于非临界区的操作， 进程0只有继续while循环，知道进程1吧turn的值改为0。这说明， 在一个进程比另一个慢了很多的情况下，轮流进入临界区并不是一个好办法。
这种情况
违反了前面叙述的条件3： 进程0被一个临界区之外的进程阻塞。 再会到前面假脱机目录的问题，如果我们现在将临界区域读写假脱机目录相联系， 则进程0有可能因为进程1在其他事情而被禁止打印另一个文件。
实际上，改方案要求两个进程严格地轮流进入它们的临界区， 如假脱机文件等。 任何一个进程都不可能在议论中打印两个文件。尽管算法的确避免了所有的竞争条件， 但由于它违反了条件3，所以不能所谓一个很好的备选方案。
4、Peterson 解法
将锁变量与警告变量的思想相结合 —— 最早提出了一个不需要严格轮换的软件互斥算法。
(1)在使用共享变量（即进入其他临界区）之前， 各个进程使用其进程号0或1作为参数来调用enter_region。该调用在需要时将使进程等待， 直到能够安全进入临界区。 在完成对共享变量的操作之后， 进程将调用leave_regioin, 表示操作已完成， 若其他的进程希望进入临界区，则现在就可以进入。
(2) 现在来看看这个方案是如何工作的。 一开始，没有任何进程处于临界区中， 现在进程0调用enter_region。它通过设置其数组元素和将turn置为0来表示它希望进入临界区。 由于进程1并不想进入临界区， 所以enter_region 很快便返回。 如果进程1现在调用enter_region，进程1将在此外挂起直到interested[0] 变成False， 该事件只有在进程0调用leave_region退出临界区时发生。
(3) 现在考虑两个进程几乎同时调用enter_region的情况。 它们都将自己的进程号存入turn， 但只有后保存进去的进程号才有效， 前一个因被重写而丢失。 假设进程1是后进入的，则turn为1。 当两个进程都运行到while语句时，进程0将循环0次并进入临界区，而进程1则将不停地循环切不能进入临界区，知道进程0退临界区为止。
5、 TSL指令 —— 需要硬件支持的一种方案
TSL RX , LOCK
测试并枷锁[Test and Set Lock]
它将一个内存字lock读到寄存器RX中， 然后在该内存地址上存一个非零的值。 读字和写字操作保证是不可分割的， 即该指令结束之前其他处理器均不允许访问该内存字。 执行TSL指令的CPU将锁住内存总线， 以禁止其他CPU在本指令结束之前访问内存。
锁住存储总线不同于屏蔽中断。 屏蔽中断， 然后在读内存字之后跟着写操作并不能阻止总线上的第二个处理器在读操作和写操作之间访问该内存字。 事实上，在处理器1上屏蔽中断对处理器2根本没有任何影响。 让处理器2原理内存知道处理器1完成的唯一方法就是锁住总线， 这需要一个特殊的硬件设施(基本上， 一根总线就可以确保总线由锁住它的处理器使用， 而其他的处理器不能用)。
为了使用TSL指令， 要使用一个共享变量lock来协调对共享内存的访问。 当lock为0时， 任何进程都可以使用TSL指令将其设置为1， 并读写共享内存。 当操作结束时， 进程用一条普通的move指令将lock的值重新设置为0。
这条指令如何防止两个进程同时进入临界区呢？
假定存在如下共4条指令的汇编语言子程序。 第一条指令将lock原来的值复制到寄存器中并将lock设置为1， 随后这个原来的值与0相比较。 如果它非零， 则说明以前已被枷锁， 则程序将回到开始并再次测试。 经过或长或短的一段时间后， 该值将变为0(当前处于临界区中的进程退出临界区时) ， 于是过程返回， 此时已加锁。 要清除这个锁非常简单， 程序只需要将0存入lock即可，不需要特殊的同步指令。
进程在进入临界区之前先调用enter_region, 这将导致忙等待，直到锁空闲为止， 随后它获得该锁并返回。 在进程从临界区返回时它调用leave_region ，这将把lock设置为0。 与基于临界区问题的所有解法一样，进程必须在真确的时间调用enter_region 和leave_region, 解法才能奏效。 如果一个进程有欺诈行为， 则互斥将会失败。
一个可替代TSL的指令是XCHG， 它原子性地交换了两个位置的内容， 例如， 一个寄存器与一个存储字。 本质上和TSL解决方法一样。
2.3.4 睡眠与唤醒
peterson 和TSL以及XCHG解法都是正确的， 但是它们都有忙等待的缺点。 本质上是：当一个进程想进入临界区时，先检查是否允许进入， 若不允许，则该进程将原地等待， 直到允许位置2.
缺点：浪费CPU时间， 而且可能引起预想不到的结果。
考虑一台计算机有两个进程， H优先级较高， L优先级较低。
调度规则规定：只要H处于就绪态它就可以运行。 在某一时刻， L处于临界区中， 此时H变到了就绪态， 准备运行(eg： 一条I/O操作结束)。 现在H开始忙等待， 但由于当H就绪时L不会被调度， 也就无法离开临界区， 所以H将无法忙等待下去。 这种情况有时称作优先级反转问题(priority inversion problem)
进程通信原语: 它们在无法进入临界区时将阻塞， 而不是忙等待。
最简单的是sleep 和wakeup 。 sleep是一个将引起调用进程阻塞的系统调用， 即被挂起， 直到另外一个进程将其唤醒。 wakeup 调用有一个参数， 即要被唤醒的进程。 另一种方法是让sleep和wakeup各有一个参数， 即有一个用于匹配sleep和wakeup的内存地址。
生产者和消费者问题：
作为使用这些原语的一个例子， 我们考虑生产者-消费者(producer-consumer) 问题。 也称作有界缓冲区[bounded-buffer] 问题。 两个进程共享一个公共的固定大小的缓冲区。 其中一个是生产者， 将信息放入缓冲区； 另一个是消费者， 从缓冲区中取出信息。【也可以把这个问题一般化为m个生产者和n个消费者问题， 但是这里只讨论一个生产者和一个消费者的情况， 这样可以简化解决方案】
问题在于当缓冲区已满， 而此时生产者还想向其中放入一个新的数据项的情况。 其解决方法是让生产者睡眠， 待消费者从缓冲区中取出一个或多个数据项时再唤醒它。 同样地，当消费者视图从缓冲区中取数据而发现缓冲区为空时， 消费者就睡眠， 直到生产者向其中放入一些数据时再讲其唤醒。
—— 这个方法听起来很简单，但是它包含了前面假脱机目录问题一样的竞争条件。 为了跟踪缓冲区中的数据项数， 需要一个白能量count。 如果缓冲区最多存放N个数据项，
—— 则生产者代码将首先检查count是否达到N，若是， 则生产者睡眠； 否则生产者向缓冲区中放入一个数据项并增量count的值。
—— 消费者代码类似， 首先测试count是否为0， 若是，则睡眠，否则从中取出一个数据项并递减count的值。 每个进程同时也检测另一个进程是否应被唤醒，若是则唤醒之。 生成这和消费者的代码
- 这里可能会出现竞争条件， 其原因是对count的访问未加限制。 有可能出现以下情况： 缓冲区为空， 消费者刚刚读取count的值发现它为0. 此时调度程序决定暂时消费者并启动运行生产者。 生产者向缓冲区中加入一个数据项， count加1. 现在count的值变成了1. 它推断认为由于count刚才为0， 所以消费此时一定在睡眠，于是生产者调用wakeupo来唤醒消费者。
- 但是，消费者此时在逻辑上并未睡眠， 所以wakeup信号丢失。 当消费者下次运行时，它将测试先前读到的count值， 发现它为0，于是睡眠。 生产者迟早会填满整个缓冲区，然后睡眠。 这样一来， 两个进程将永远睡眠下去。
- 问题的实质在于发给一个(尚)未睡眠进程的wakeup信号丢失了。如果它没有丢失，则一切都很正常。 一种快速的弥补方法是修改规则，加上一个环形等待位。 当一个wakup信号发送给一个清醒的进程信号时，将该位置1. 随后，当该进程要睡眠时，如果环形等待位为1， 则将该位清除， 而该进程仍然保持清醒。 环形等待位知己上就是wakeup信号的一个小仓库。
4)尽管在这个简单例子中用环形等待位的方法解决了问题。 但是，我们可以很容易就构造一些例子，其中有三个或者更多的进程，这个时候环形等待位就不够使用了。 于是我们可以再打一个补丁，加入第二唤醒等待位。 甚至8个、32个等， 但原则上讲， 这并没有从根本上解决问题。
2.3.5 信号量
它使用一个整型变量来累计唤醒次数， 供以后使用 —— 信号量(semaphore) 。 一个信号量的取值可以为0(表示没有保存下来的唤醒操作)或者为正值(表示有一个或多个唤醒操作)。
Dijkstra 建议设立两种操作： down和up（分别是一般化后的sleep和wakeup）。
1> 对信号量执行down操作， 则是检查其值是否大于0。若该值大于0，则将其值减1（即为用掉一个保存的唤醒信号）并继续； 该值为0， 则进程将睡眠， 而且此时down操作并未结束。 检查数值，修改变量值以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作完成。保证一旦一个信号量操作开始， 则在该操作完成或阻塞之前， 其他进程均不允许访问该信号量。 这种原子性对于解决同步问题和避免竞争条件是绝对必要的。
原子操作：是指一组相关联的操作要么都不间断地执行，要么都不执行。 原子操作在计算机可续的其他领域也是非常重要的。
2> up 操作对信号量的值增1. 如果一个或多个进程在该信号量上睡眠，无法完成一个先前的d0wn操作， 则由系统选择其中一个并允许该进程完成它的down操作。 于是，对一个有进程在其上睡眠的信号量执行一次up操作之后， 该信号量的值仍旧是0， 但在其上睡眠的进程确少了一个。 信号量的值增1和唤醒一个进程同样也是不可分割的。 不会有某个进程因执行up而阻塞，正如在前面的模型中不会有进程因执行wakeup而阻塞一样。
用信号量解决生产者 —— 消费者问题
用信号量解决丢失的wakeup问题。
操作系统只需执行一下操作时暂时屏蔽全部中断：测试信号量、更新信号量以及在需要时使某个进程睡眠。 由于这些动作只需要几条指令，所以，屏蔽中断不会带来什么副作用。 如果使用多个CPU， 则每个信号量应由一个锁变量进行保护。 通过TSL或XCHG指令来确保同一时刻只有一个CPU在对信号量进行操作。
使用TSL和XCHG指令来防止几个CPU同事访问一个信号量， 这与生产者或消费者使用忙等待对方腾出或填充缓冲区是完全不同的。 信号量操作仅仅需要几个毫秒， 而生产者或消费者则可能需要任意长的时间。
解决方案使用了三个信号量： 一个称为full，用来记录充满的缓冲槽数目， 一个成为empty， 记录空的缓冲槽数目， 一个mutex, 用来确保生产者和消费者不会同时访问缓冲区。
full的初始值为0， empty的初始值为缓冲区中槽的数量， mutex 初值为1.
供两个或多个进程使用的信号量，其初始值为1，保证同时只有 一个进程可以进入临界区，称作二元信号量(binary semaphore)。如果每个进程在进入临界区前都执行一个down操作， 并在刚刚退出时执行一个up操作，就能够实现互斥。
在上面2-5的中断顺序； 在使用信号量系统中， 隐藏中断的最自然的方法是为每个IO设备设置一个信号量，初始值为0。在启动一个IO设备之后，管理进程就立即对相关联的信号执行一个down操作，于是进程立即被阻塞。 当中断到来时， 中断处理程序随后对相关信号量执行一个up操作， 从而将相关的进程设置为就绪状态。 2-5中的第5步包括在设备的信号量执行一个up操作，这样在第6步中，调度程序将能够执行设备管理程序。 如果这时有几个进程就绪，则调度程序下次可以选择一个更为中啊哟的进程来运行。
上图使用了两种不同的方式来使用信号量的，两者之间的区别是很重要的。信号量mutex用于互斥，它用于保证任一时刻只有一个进程读写缓冲区和相关的变量。互斥是避免混乱所必须的操作。
信号量 的另一种用户是用于实现同步(synchronization)。 信号量full和empty用来保证某种事件的顺序发生或不发生。
本例：我们保证缓冲区满的时候生产者停止运行，以及当缓冲区空的时候消费者停止运行。这种用法和互斥是不同的
2.3.6 互斥量
如果不需要信号量的技术能力，有时可以使用信号量的一个简化版本，称为
互斥量(mutex)
互斥量仅仅适用于管理共享资源或一小段代码。由于互斥量在实现时即容易又有效， 这使得互斥量在实现用户空间线程包时非常有用。
互斥量是一个可以处于两态之一的变量：解锁 和 加锁。 可以使用二进制位来表示。 不过实际上使用了一个整型量，0表示解锁， 而其他所有的值则表示加锁。 互斥量使用两个过程。 当一个线程（或进程）需要访问临界区时， 它调用mutex_lock。 如果该互斥量当前是解锁的(即临界区可用)， 次调用成功，调用线程可以自由进入临界区。
另一方面： 如果该互斥量已经加锁， 调用线程被阻塞，知道在临界区中的线程完成并调用mutex_unlock 。 如果多线程被阻塞、在该互斥量上，将随机选择一个线程并允许它获得锁。
由于互斥量非常简单，所以，如果有的TSL和XCHG指令，就可以很容易地在用户空间中实现它们。用于用户级线程包的mutex_lock 和mutex_unlock。
1、快速用户去互斥量futex
2、pthread中的互斥量
2.3.7 管程
2.3.8 消息传递
2.3.9 屏障
2.3.10 避免锁： 读—复制—更新
——————————————————————————————-
2.4 调度
网友评论