写在开头：本章一个比较重要的算法是临界区管理以及信号量与PV操作，本博客没有对这些内容进行记录，仅仅记录了本章的基础知识。
第三章 并发进程
1.顺序程序设计的特点：
- 程序执行的顺序性：一个程序在处理器上的执行是严格按序的，即每个操作必须在下一个操作开始之前结束。
- 程序环境的封闭性：运行程序独占全部资源，除初始状态外，其所处的环境由程序本身决定，只有程序本身的动作才能改变其环境。
- 程序执行结果的确定性：程序执行过程中允许被中断，但这种中断对程序的最终结果无影响，也即程序的执行结果与它的执行速率无关。
- 计算过程的可再现性：在同一个数据集合上重复执行一个程序会得到相同结果，因而错误也可以重现，便于分析。
2.进程的并发性
宏观上看：并发性反映一个时间段中几个进程都在同一处理器上处于运行还未运行结束的状态。
微观上看：任一时刻仅有一个进程在处理器上运行。
并发的实质：一个处理器在几个进程之间的多路复用，并发是对有限的物理资源强制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率。
2.1并发程序设计的特征
- 并行性：进程的执行在时间上可以重叠，在单处理器系统中可以并发执行，在多处理器环境中可以并行执行。
- 共享性：并发进程通过引用共享变量交换信号，从而，程序运行的环境不再是封闭的。
- 制约性：进程并发执行或协同完成同一任务时，会产生相互制约关系，必须对它们并发执行的次序加以协调。
- 交互性：由于并发进程共享某些变量，所以，一个进程的执行可能影响其他进程的执行结果，程序运行结果可能不确定，计算过程具有不可再现性。因此，这种交互必须是有控制的，否则会出现不正确的结果。
2.2并发程序设计的优点
- 对于单处理器系统,可让处理器和各I/O设备、I/O设备与I/O设备同时工作,发挥硬部件的并行能力。
- 对于多处理器系统,可让各进程在不同处理器上物理地并行，加快计算速度。
- 简化了程序设计任务。
2.3采用并发程序设计的目的
充分发挥硬件的并行性，提高系统效率。
2.4与时间有关的错误
- 结果不唯一
- 永远等待
3.进程的交互
3.1进程间的关系
- 进程互斥：是解决进程间竞争关系(间接制约关系)的手段。进程互斥是指若干进程要使用同一共享资源时，任何时刻最多允许一个进程使用，其他要使用该资源的进程必须等待，直到占有资源的进程释放该资源。
- 进程同步：指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤醒。进程的同步是解决进程间协作关系(直接制约关系)的手段。
进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上的一种协调。
4.临界区管理
并发进程中与共享变量有关的程序段叫“临界区”，共享变量代表的资源叫“临界资源”。
4.1互斥与临界区
与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预知。如果能保证进程在临界区执行时，不让另一个进程进入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误。
4.2临界区的调度原则
- 一次至多允许一个进程进入临界区。
- 一个进程不能无限地停留在临界区。
- 一个进程不能无限地等待进入临界区。
5.进程通信
进程通信：进程之间的信息交换
5.1进程通信分类
- 低级通信：交换信息量少，通信控制复杂，对用户不透明。如：信号量机制。
- 高级通信：高级通信：用户直接利用OS提供的通信命令传输大量数据，通信控制细节由OS完成，对用户透明。
5.2进程通信的类型
高级通信机制主要有三种类型：管道通信系统、共享存储器系统、消息传递系统。
5.2.1共享文件通信机制
管道属于一种共享文件通信机制
管道：是一个共享文件，连接读写进程实现通信。写进程往管道一端写入信息，读进程从管道另一端读信息。
管道机制应具备的三个协调功能：
- 互斥。一次仅由一个进程读写。
- 同步。睡眠和唤醒功能。
- 确定对方是否存在。
5.2.2共享存储区通信机制
方法：在内存中开辟一个共享存储区,各个进程通过该共享存储区实现通信.进程通信前,从共享存储区申请一个分区段,该分区段属于通信各方进程公用的内存区,通信的某一方进程可能在一个进程申请前已经申请得到,若是这样,则仅向后申请的进程返回分区段的一个标识,各方进程通过该标识向分区段写入信息或从中读取信息。
5.2.3消息传递通信机制
消息传递通信机制的组成：主要由发送(send)原语和接收原语(receive)组成。同步细节均被封装.发送(send)原语和接收原语(receive)包含有阻塞唤醒机制,程序员使用它们进行程序设计时如同进行串行程序设计,而不是并发程序设计。
6.死锁
6.1死锁的定义
操作系统中的死锁指：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生了死锁。
6.2产生死锁的四个必要条件
- 互斥条件：进程互斥使用资源
- 占有和等待条件：申请新资源时不释放已占有资源
- 不剥夺条件：一个进程不能抢夺其他进程占有的资源
- 循环等待条件：存在一组进程循环等待资源的现象
只要破坏四个条件之一，死锁就可防止。
6.3死锁的防止
打破死锁四个必要条件之一。
6.3.1静态分配策略
静态分配是指一个进程必须在执行前就申请它所要的全部资源，并且直到它所要的资源都得到满足后才开始执行。
降低了资源利用率,因为每个进程占有的资源中,有些资源在较后的时间里才使用,有些资源在发生例外时才使用,这样就可能造成一个进程占有了一些几乎不用的资源而使其它想用这些资源的进程产生等待.
6.3.2层次分配策略
资源被分成多个层次
当进程得到某一层的一个资源后，它只能再申请较高层次的资源
当进程要释放某层的一个资源时，必须先释放占有的较高层次的资源
当进程得到某一层的一个资源后，它想申请该层的另一个资源时，必须先释放该层中的已占资源
缺点：
- 限制了新类型设备的增加。
- 进程使用各类资源顺序与系统规定顺序不同时造成资源浪费。
- 限制用户简单、自主编程。
6.4死锁的避免
避免死锁的方法允许系统中同时存在四个必要条件,每当进程提出资源申请时,系统要分析满足该资源请求时系统是否会发生死锁,若不会发生则实施分配,否则拒绝分配.
银行家算法基本思想：
- 系统中的所有进程进入进程集合,
- 在安全状态下系统收到进程的资源请求后,先把资源试探性分配给它。
- 系统用剩下的可用资源和进程集合中其他进程还要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程,从而,保证这个进程运行完毕并归还全部资源。
银行家算法的缺点：
很难在进程运行前知道其所需的资源最大量,而且系统中的进程必须是无关的,相互间没有同步要求,进程的个数和分配的资源数目应该是固定的.这些要求事先难以满足,因而银行家算法缺乏实用价值。
6.5死锁的检测和解除
解决死锁问题的一条途径是死锁检测和解除，这种方法对资源的分配不加任何限制，也不采取死锁避免措施，但系统定时地运行一个“死锁检测”程序，判断系统内是否已出现死锁，如果检测到系统已发性了死锁，再采取措施解除它。
6.5.1资源分配图
操作系统中每一时刻的系统状态都可以用进程—资源分配图来表示，进程—资源分配图是描述进程和资源间申请和分配关系的一种有向图，可用以检测系统是否处于死锁状态。
进程-资源分配图的结构：
进程—资源分配图由进程结点P、资源结点R、有向边组成。
约定Pi→Rj为请求边，表示进程Pi申请资源类Rj中的一个资源得不到满足而处于等待Rj类资源的状态，该有向边从进程开始指到资源方框的边缘，表示进程Pi申请Rj类中的一个资源。
Rj→Pi为分配边，表示Rj类中的一个资源已被进程Pi占用，由于已把一个具体的资源分给了进程Pi，故该有向边从资源方框内的某个黑圆点出发指向进程。
6.5.2进程—资源分配图与死锁判断的关系
- 如果进程—资源分配图中无环路，则此时系统没有发生死锁。
- 如果进程—资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程。
- 如果进程—资源分配图中有环路，且涉及的资源类中有多个资源，则环的存在只是产生死锁的必要条件而不是充分条件。
6.5.3死锁的检测和解除方法
从进程—资源分配图中找到一个既不阻塞又非独立的进程,消去所有与该进程相连的有向边,相当于该进程能够执行完成释放资源,回收资源使之成为孤立结点.然后将所回收的资源分配给其它进程,再从进程—资源分配图中找到下一个既不阻塞又非独立的进程,消去所有与该进程相连的有向边,使之成为孤立结点…….不断重复该过程,直到所有进程成为孤立结点,则称该图是可完全化简的;否则称该图是不可完全化简的.
系统为死锁状态的充分条件是：当且仅当该状态的进程-资源分配图是不可完全简化的。该充分条件称为死锁定理。
6.5.4死锁的接触方法
- 立即结束所有进程的执行，并重新启动操作系统。方法简单,但以前工作全部作废,损失可能很大。
- 剥夺陷于死锁的进程占用的资源，但并不撤销它, 直至死锁解除。
- 撤销陷于死锁的所有进程,解除死锁继续运行。
- 逐个撤销陷于死锁的进程,回收其资源,直至死锁解除。
- 根据系统保存的检查点,让所有进程回退,直到足以解除死锁。
- 当检测到死锁时，如果存在某些未卷入死锁的进程，而这些进程随着建立一些新的抑制进程能执行到结束，则它们可能释放足够的资源来解除死锁。