安全状态的例子 例：假定系统有三个进程P1、P2、P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和九台。设在T0时刻，进程P1、P2和P3已经获得5台、2台和2台，还有3台空闲没有分配。 进程 最大需求 已分配 可用 P1 10 5 3 P2 4 2 P3 9 2 T0时刻系统时安全的。这时存在一个安全序列<P2，P1，P3>

虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质是如何使系统不进入不安全状态。 系统的状态可能通过下述来描述： 进程剩余申请数＝最大申请数－占有数。 可分配资源数＝总数－占有数之和。

银行家算法 银行家算法是最有代表性的避免死锁算法，是Dijkstra提出的银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名。为实现银行家算法，系统中必须设置若干数据结构。

一、银行家算法中的数据结构 1 可利用资源向量Available 是一个含有m个元素，其中的每一个元素代表一类可利用的资源数目，其初值是系统中所配置的该类全部可用资源数目。如果Available[j]=k， 表示系统中现有Rj类资源k个。 2 最大需求矩阵Max 是一个含有nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max(i,j)=k， 表示进程i需要Rj类资源的最大数目为k。 Available= 3 5 4 2 8 3 8 6 1

3 分配矩阵Allocation 是一个含有nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation(i,j)=k， 表示进程i当前已分得Rj类资源k个。 4 需求矩阵Need 是一个含有nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Need(i,j)=k， 表示进程i还需要Rj类资源k个，方能完成其任务。 Need(i,j)= Max(i,j)-Allocation(i,j)

设Requesti是进程Pi的请求向量，如果进程Pi需要K个Rj类资源，当Pi发出资源请求后，系统按下述步骤进行检查： 二、银行家算法 设Requesti是进程Pi的请求向量，如果进程Pi需要K个Rj类资源，当Pi发出资源请求后，系统按下述步骤进行检查： 1 如果Requesti≤Needi,则转向步骤2；否则认为出错。（因为它所需要的资源数已超过它所宣布的最大值。 2如果Requesti≤Available,则转向步骤3；否则，表示系统中尚无足够的资源，Pi必须等待 3 系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值： Available:=Available-Requesti; Allocation:=Allocation+Requesti; Needi:= Needi- Requesti; 4 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

三、安全性算法 系统所执行的安全性算法可描述如下： 1 设置两个向量 ①工作向量Work.它表示系统可提供给进程继续运行所需要的各类资源的数目，它含有m个元素，执行安全算法开始时，Work:=Available。 ②Finish.它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]:=false；当有足够的资源分配给进程时，令Finish[i]:=true. 2 从进程集合中找到一个能满足下述条件的进程：①Finish[i]=false; ②Needi≤Work. 如找到，执行步骤3；否则执行步骤4。 3 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故执行： Work:=Work+Allocation; Finish[i]:=true; Goto step2; 4 如果所有进程的Finish[i]=true，则表示系统处于安全状态；否则，系统处于不安全状态。

要记住的一些变量的名称 1 Available（可利用资源向量） 某类可利用的资源数目，其初值是系统中所配置的该类全部可用资源数目。 2 Max最大需求矩阵 某个进程对某类资源的最大需求数 3 Allocation分配矩阵 某类资源当前非配给某进程的资源数。 4 Need需求矩阵 某个进程还需要的各类资源数。 Need= Max-Allocation 系统把进程请求的资源分配给它以后要修改的变量 Available:=Available-Request; Allocation:=Allocation+Request; Need:= Need- Request;

银行家算法之例 假定系统中有五个进程{P0、P1、P2、P3、P4}和三种类型的资源{A，B，C}，每一种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 资源情况 Max A B C Allocation A B C Need A B C Available A B C 进程 P0 P1 P2 P3 P4 0 1 0 7 4 3 3 3 2 ( 2 3 0 ) 3 2 2 2 0 0 1 2 2 ( 3 0 2 ) ( 0 2 0 ) 9 0 2 3 0 2 0 0 2 2 2 2 1 1 0 1 1 4 3 3 0 0 2 4 3 1

10,5 7 最大值 已分配 还需要 可用 资源情况 进程 Allocation A B C Max Need Available P0 0 1 0 3 2 2 9 0 2 2 2 2 4 3 3 2 0 0 ( 3 0 2 ) 3 0 2 2 1 1 0 0 2 7 4 3 1 2 2 ( 0 2 0 ) 6 0 0 0 1 1 4 3 1 3 3 2 ( 2 3 0 ) 7 5 3 work Work＋Allocation finish 若P1发出请求向量 Request（1，0，2） 工作向量Work.它表示系统可提供给进程继续运行所需要的各类资源的数目 true 3 3 2 1 2 2 2 0 0 5 3 2 5 3 2 0 1 1 2 1 1 7 4 3 true 7 4 3 4 3 1 true 0 0 2 7 4 5 7 4 5 6 0 0 3 0 2 10 4 7 true 10 4 7 7 4 3 0 1 0 10 5 7 true

假定系统中有五个进程{P0、P1、P2、P3、P4}和 三种类型的资源{A，B，C}，每一种资源的数量 思考和练习 假定系统中有五个进程{P0、P1、P2、P3、P4}和 三种类型的资源{A，B，C}，每一种资源的数量 分别为10、5、7，在T0时刻的资源分配情况如图 请找出该表中T0时刻以后存在的安全序列（至少2种） 资源情况 Max A B C Allocation A B C Need A B C Available A B C 进程 P0 P1 P2 P3 P4 7 5 3 0 1 0 7 4 3 3 3 2 3 2 2 2 0 0 1 2 2 9 0 2 3 0 2 6 0 0 2 2 2 2 1 1 0 1 1 4 3 3 0 0 2 4 3 1

3 死锁的检测和恢复 死锁的检测和恢复技术是指定期启动一个软件检测系统的状态，若发现有死锁存在，则采取措施恢复之。 (1)死锁的检测 3 死锁的检测和恢复 死锁的检测和恢复技术是指定期启动一个软件检测系统的状态，若发现有死锁存在，则采取措施恢复之。 (1)死锁的检测 检查死锁的办法就是由软件检查系统中由进程和资源构成的有向图是否构成一个或多个环路，若是，则存在死锁，否则不存在。

死锁的检测：实质是确定是否存在环路等待现象，一旦发现这种环路便认定死锁存在，并识别出该环路所涉及的有关进程，以供系统采取适当的措施来解除死锁。最常用的是一种基于资源分配图RAG和死锁定理的检测死锁算法。

资源分配图（RAG） 系统死锁可用资源分配图来描述，该图是由一组结点N和一组边E所组成的一对偶G=(N,E)。（用圆圈代表一个进程，用方框代表一类资源，由于一种类型的资源可能有多个，可用方框中的一个点代表一类资源中的一个资源） 几个概念：请求边，分配边 P1 请求r2 r2 r1 P2 资源分配图

封锁进程：是指某个进程由于请求了超过了系统中现有的未分配资源数目的资源，而被系统封锁的进程。 非封锁进程：即没有被系统封锁的进程资源分配图的化简方法：假设某个RAG中存在一个进程Pi，此刻Pi是非封锁进程，那么可以进行如下化简：当Pi有请求边时，首先将其请求边变成分配边(即满足Pi的资源请求)，而一旦Pi的所有资源请求都得到满足，Pi就能在有限的时间内运行结束，并释放其所占用的全部资源，此时Pi只有分配边，删去这些分配边（实际上相当于消去了Pi的所有请求边和分配边），使Pi成为孤立结点。（反复进行）  。

系统中某个时刻S为死锁状态的充要条件是S时刻系统的资源分配图是不可完全简化的。 P1 P1 P2 r1 r2 P1 r2 r1 r2 r1 P2 P2 死锁定理： 系统中某个时刻S为死锁状态的充要条件是S时刻系统的资源分配图是不可完全简化的。 在经过一系列的简化后，若能消去图中的所有边，使所有的进程都成为孤立结点，则称该图是可完全简化的；反之的是不可完全简化的。

死锁的恢复。是与检测死锁相配套的一种措施，用于将进程从死锁状态下解脱出来。常用的方法有： 1撤消进程；最简单撤消进程的方法是使全部死锁的进程夭折掉；另一方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，死锁状态消除为止 2挂起进程（剥夺资源）。使用挂起/激活机构挂起一些进程，剥夺它们的资源以解除死锁，待条件满足时，再激活进程。目前挂起法比较受到重视。

例题 1．（北大95）一个OS有20个进程，竞争使用65个同类资源，申请方式是逐个进行的，一旦某个进程获得它所需要的全部资源，则立即归还所有资源。每个进程最多使用三个资源。若仅考虑这类资源，该系统有无可能产生死锁，为什么？ 2．死锁和饥饿的主要差别是什么？

1 答：不可能。因为死锁产生的原因有两点：系统资源不足或推进顺序不当，在本题中，进程所需的最大资源数为60，而系统共有该类资源65个，其资源数已足够系统内各进程使用。 2 答：简言之，死锁是某进程等待一个不会发生的事件的一种现象；而饥饿现象是某进程正等待这样一个事件，它发生了但总是受到其它进程的影响，以至轮不到（或很难轮到）该进程。

作业 1.在某系统中，三个进程共享四台同类型的设备资源，这些资源一次只能一台地为进程服务和释放，每个进程最多需要二台设备资源，试问在系统中是否会产生死锁？ 2.某系统中有n个进程和m台打印机，系统约定：打印机只能一台一台地申请、一台一台地释放，每个进程需要同时使用的打印机台数不超过m。如果n个进程同时使用打印机的总数小于m+n，试讨论，该系统可能发生死锁吗?并简述理由。 3.仅涉及一个进程的死锁有可能存在吗?为什么?

小 结 进程的并发执行，使得它们之间存在着两种制约关系：由共享资源引起的间接制约关系称为互斥；由于协作完成同一任务而引起的直接制约关系称为同步。为了正确地解决进程之间的同步和互斥，系统设置同步机构：锁和信号量机构。这种同步机构称为低级通信。进程之间的高级通信机构有消息缓冲、信箱、管道、共享内存和共享文件等机构，其最大特点是通信双方可交换大量的数据。

系统中并发运行进程由于共享资源或相互通信，如果调度不当，可能导致系统死锁。解决死锁的方法有三种： (1) 预防死锁，它是通过破坏死锁的四个必要条件实现的。 (2) 避免死锁，它是在进程请求分配资源时，采用银行家算法等防止系统进入不安全状态。 (3) 检测和恢复死锁，它是通过设置一个死锁检测机构进行死锁检测，一旦检测出来，通过逐一撤消进程使系统恢复。

3.9 线程(Thread) 3.9.1 线程的概念 引入的线程目的：提高系统的执行效率，减少处理机的空转时间和调度切换（保护现场信息）的时间，便于系统管理。（减少程序并发执行时所付出的时空开销，使OS具有更好的并发性。）  

分析说明： 进程的两个基本属性： 1 进程是一个可拥有资源的独立单位； 2 进程又是一个可独立调度和分配的基本单位。合起来，进程便成为一个能独立运行的基本单位，从而构成了程序并发执行的基础。 简言之，由于进程是一个资源的拥有者，在执行这些操作时会付出较大的时间开销。因此在系统中所设的进程数目不宜过多，切换不宜过于频繁，这就限制了系统的并发程度。

线程的定义 定义：线程是进程中的一个实体，是被系统独立调度和分配的基本单位，故又称为轻权（轻型）进程(Light Weight Process)，它由线程控制表、存储线程上下文的用户栈以及核心栈组成。{传统的进程称为重型进程(Heavy Weight Process)。}

线程与进程的主要区别 １进程是资源管理的基本单位，它拥有自己的地址空间和各种资源；线程只是处理机调度的基本单位，它只和其他线程一起共享进程资源，它自己没有任何资源。 ２以进程为单位进行处理机切换和调度时，处理机切换时间长，资源利用率降低。以线程为单位进行进行处理机切换和调度时，由于不发生资源变化，特别是地址空间的变化，处理机切换时间较短，从而处理机效率较高。

３对用户来说，多线程系统比无线程系统可减少用户的等待时间，提高系统的响应速度。 ４线程和进程一样，都有自己的状态，也有相应的同步机制，不过由于线程没有单独的数据和程序空间，因此线程不能像进程的数据与程序那样，交换到外存存储空间，从而线程没有挂起状态。

５进程的调度、同步等大多由OS内核完成，而线程的控制既可以由OS内核进行，也可以由用户控制。

3.9.2 线程的适用范围 几种典型的应用：1服务器中的文件管理和进程通信控制；2 前后台处理；3 异步处理；4 数据的批处理；5 网络系统中信息发送和接受；6 其他相关的处理。