计算机操作系统(第三章)_3.7.2(进程的通信与死锁)

1、计算机操作系统第三章 进程管理_33.7 进 程 通 信 通信（communication）意味着在进程间传送数据 进程间的通信根据通信内容可以划分为二种：即控制信息的传送与大批量数据传送。 低级通信：进程间控制信息的交换。 高级通信：进程间大批量数据的交换。 低级通信一般只传送一个或几个字节的信息，以达到控制进程执行速度的作用。高级通信要传送大量数据。高级通信的目的不是为了控制进程的执行速度，而是为了交换信息。第三章 进程管理第2页2022-6-9在单机系统中，进程间通信可分为4种形式：(1) 主从式：终端控制进程和终端进程(2) 会话式：通信进程双方可分别称为使用进程和服务进程(3) 消息

2、或邮箱机制；(4) 共享存储区方式。第三章 进程管理第3页2022-6-9主从式通信系统的主要特点是： 主进程可自由地使用从进程的资源或数据； 从进程的动作受主进程的控制； 主进程和从进程的关系是固定的。 主从式通信系统的典型例子是终端控制进程和终端进程。第三章 进程管理第4页2022-6-9会话方式具有如下特点： 使用进程在使用服务进程所提供的服务之前，必须得到服务进程的许可； 服务进程根据使用进程的要求提供服务，但对所提供服务的控制由服务进程自身完成。 使用进程和服务进程在通信时有固定连接关系。 用户进程与磁盘管理进程之间的通信是会话系统的一个例子第三章 进程管理第5页2022-6-9 会

3、话方式中，通信进程双方可分别称为使用进程和服务进程。其中，使用进程调用服务进程提供的服务。它们具有如下特点： 使用进程在使用服务进程所提供的服务之前，必须得到服务进程的许可； 服务进程根据使用进程的要求提供服务，但对所提供服务的控制由服务进程自身完成。 使用进程和服务进程在通信时有固定连接关系。 各用户进程向磁盘管理进程提出使用要求并得到许可之后，才可以使用相应的存储区。而且，由磁盘管理进程自身完成对磁盘存储区的管理和控制。另外，用户进程与磁盘管理进程之间，只有在用户进程要求使用磁盘存储区时才有通信关系。第三章 进程管理第6页2022-6-9 消息的一般形式为个部分组成。即：发送进程名、接收进

4、程名、数据和有关数据的操作（图3.15）。图图3.15消息的组成消息的组成第三章 进程管理第7页2022-6-9消息或邮箱机制的特点 无论接收进程是否已准备好接收消息，发送进程都将把所要发送的消息送入缓冲区或邮箱。消息或邮箱机制的特点是：消息或邮箱机制的特点是： 只要存在空缓冲区或邮箱，发送进程就可以发送消息。 与会话系统不同，发送进程和接收进程之间无直接连接关系，接收进程可能在收到某个发送进程发来的消息之后，又转去接收另一个发送进程发来的消息。 发送进程和接收进程之间存在缓冲区或邮箱（图3.16）用来存放被传送消息图图3.16缓冲区或邮箱通信结构缓冲区或邮箱通信结构flash演示演示: 生产

5、者、消费者生产者、消费者第三章 进程管理第8页2022-6-9共享存储区方式： 共享存储区方式不要求数据移动。两个需要互相交换信息的进程通过对同一共享数据区（shared memory）的操作来达到互相通信的目的。这个共享数据区是每个互相通信进程的一个组成部分。 以上几种通信方式都可用于大量数据传送，而且，由于其通信方式不同，需要使用不同的控制方式来达到通信进程之间同步或互斥的目的。第三章 进程管理第9页2022-6-93.7.2 消息缓冲机制 发送进程和接收进程采用消息缓冲机制进行数据传送时，发送进程在发送消息前，先在自己的内存空间设置一个发送区，把欲发送的消息填入其中，然后再用发送过程将其

6、发送出去。接收进程则在接收消息之前，在自己的内存空间内设置相应的接收区，然后用接收过程接收消息。发送进程在自己的内存空间设置一个把要发送的消息填入发送区发送区接收区接收进程在自己的内存空间设置一个公用缓冲区PCBPCB.Send(RSend(R, M), M).SIZE:SIZE:消息长度消息长度TEXT:TEXT:消息正文消息正文.消息链指针消息链指针.Receive(pidReceive(pid, N), N).SIZE:SIZE:消息长度消息长度TEXT:TEXT:消息正文消息正文.M:M:N:N:接收进程接收进程 R R发送进程发送进程 S S消息消息消息消息消息消息消息消息 由于消息

7、缓冲机制中所使用的缓冲区为公用缓冲区，使用消息缓冲机制传送数据时，两通信进程必须满足如下条件： 在发送进程把消息写入缓冲区和把缓冲区挂入消息队列时，应禁止其他进程对该缓冲区消息队列的访问。否则，将引起消息队列的混乱。同理，当接收进程正从消息队列中取消息缓冲时，也应禁止其他进程对该队列的访问。 当缓冲区中无消息存在时，接收进程不能接收到任何消息。 至于发送进程是否可以发送消息，则由发送进程是否申请到缓冲区决定。第三章 进程管理第12页2022-6-9例：设公用信号量mutex 为控制对缓冲区访问的互斥信号量，其初值为1 。设SM为接收进程的私用信号量，表示等待接收的消息个数，其初值为0 。设发送

8、进程调用过程send(m)将消息m 送往缓冲区，接收进程调用过程Receive(m)将消息m从缓冲区读往自己的数据区，则Send(m)和Receive(n)可分别描述为：Send(m):begin向系统申请一个消息缓冲区 （mutex） P（SM）将发送区消息m送入新申请的消息缓冲区把消息缓冲区挂入接收进程的消息队列（mutex）（SM）end第三章 进程管理第13页2022-6-9Receive(n):begin（SM）（mutex） 摘下消息队列中的消息n 将消息n从缓冲区复制到接收区V(SM) 释放缓冲区（mutex）end3.7.3 邮箱通信 邮箱通信就是由发送进程申请建立一与接收进程

9、链接的邮箱。 发送进程把消息送往邮箱，接收进程从邮箱中取出消息，从而完成进程间信息交换。 设置邮箱的最大好处就是发送进程和接收进程之间没有处理时间上的限制。一个邮箱可考虑成发送进程与接收进程之间的大小固定的私有数据结构，它不像缓冲区那样被系统内所有进程共享。第三章 进程管理第14页2022-6-9 邮箱由邮箱头和邮箱体组成。其中邮箱头描述邮箱名称、邮箱大小、邮箱方向以及拥有该邮箱的进程名等。邮箱体主要用来存放消息（图3.17）。图图3.17 邮箱通信结构邮箱通信结构对于只有一发送进程和一接收进程使用的邮箱，则进程间通信应满对于只有一发送进程和一接收进程使用的邮箱，则进程间通信应满足如下条件：足

10、如下条件： 发送进程发送消息时，邮箱中至少要有一个空格能存放该消息。发送进程发送消息时，邮箱中至少要有一个空格能存放该消息。 接收进程接收消息时，邮箱中至少要有一个消息存在。接收进程接收消息时，邮箱中至少要有一个消息存在。第三章 进程管理第15页2022-6-9deposit(m)和remove(m)可描述如下：deposit(m):begin local x（fromnum）选择空格x将消息m放入空格x中置格x的标志为满（mesnum）end第三章 进程管理第16页2022-6-9例：设发送进程调用过程 deposit(m)将消息发送到邮箱，接收进程调用过程remove(m)将消息m 从邮箱

11、中取出。另外，为了记录邮箱中空格个数和消息个数，信号量fromnum 为发送进程的私用信号量，信号量mesnum为接收进程的私用信号量。fromnum 的初值为信箱的空格数 n，mesnum 的初值为 0。remove(m):begin local x（mesnum）选择满格x把满格x中的消息取出放m中 置格x标志为空（fromnum）end3.7.4 进程通信的实例和控制台的通信 通用计算机中，除了用户终端之外，还有一台由系统操作员控制的控制台终端。各用户进程可将消息送到控制台进程，操作员在读到这些消息后做出相应的处理。图图3.18 和控制台通信示例和控制台通信示例第三章 进程管理第17页2

12、022-6-93.7.5 进程通信的实例管道1. 管道pipe 进程通信的实用例子之一是UNIX系统的管道通信。UNIX系统从System开始，提供有名管道和无名管道两种数据通信方式. 无名管道为建立管道的进程及其子孙提供一条以比特流方式传送消息的通信管道。该管道在逻辑上被看作管道文件，在物理上则由文件系统的高速缓冲区构成，而很少启动外设。发送进程利用文件系统的系统调用write(fd1,buf,size)，把buf中的长度为size字符的消息送入管道入口fd1，接收进程则使用系统调用read(fd0,buf,size)从管道出口fd0 读出size字符的消息置入buf 中。这里，管道按FIF

13、O（先进先出）方式传送消息，且只能单向传送消息（图3.20）。第三章 进程管理第18页2022-6-9 利用UNIX提供的系统调用pipe，可建立一条同步通信管道。其格式为：pipe(fd)intfd2；这里，fd1 为写入端，fd0为读出端。 例: p71图3.20 管道通信第三章 进程管理第19页2022-6-9发送进程发送进程接收进程接收进程例2： 编写一程序，建立一个管道。同时，父进程生成子进程P1，P2，这两个子进程分别向管道中写入各自的字符串，父进程读出它们（如图3.21）。图3.21 父进程和子进程P1，P2通信例子解：程序框图如图3.22所示：第三章 进程管理第20页2022-

14、6-9图图3.22 例例2程序流图程序流图源程序如下p72第三章 进程管理第21页2022-6-93.8 3.8 死死 锁锁3.8.1 死锁的概念3.8.2 死锁的排出方法第三章 进程管理第22页2022-6-9Bridge Crossing Example 车辆只允许单向通行。 桥上的每个位置可以看作一个资源。 如果发生死锁， 可以通过让一辆车后退来解决 (剥夺资源，回滚)。 死锁时，可能要求多辆车后退。 可能会出现饥饿现象（Starvation ）。哲学家进餐问题哲学家进餐问题void philosoper(int i) / i为哲学家号为哲学家号 while (TRUE) think()

15、; / 思考，直至饥饿思考，直至饥饿 P( forki );/ 试图拿左侧叉子试图拿左侧叉子 P( fork( i + 1) % N ); / 试图拿右侧叉子试图拿右侧叉子 eat();/ 取到两把叉子取到两把叉子 V( forki ); / 放下左侧叉子放下左侧叉子 V( fork( i + 1) % N ); / 放下右侧叉子放下右侧叉子 程序有什么问题？程序有什么问题？flash演示：导致死锁的情况演示：导致死锁的情况3.8.1死锁的定义 死锁：各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成大家都想得到资源而又都得不到资源，各

16、并发进程不能继续向前推进的状态。图图3.22 死锁的概念死锁的概念第三章 进程管理第25页2022-6-9死锁的描述 有并发进程P1，P2，Pn，它们共享资源R1，R2，Rm（n0，m0，n=m）。其中，每个Pi（1in）拥有资源Rj（1 j m），直到不再有剩余资源。同时，各Pi又在不释放Rj 的前提下要求得到Rk（kj，1 km），从而造成资源的互相占有和互相等待。在没有外力驱动的情况下，该组并发进程停止往前推进，陷入永久等待状态第三章 进程管理第26页2022-6-92. 死锁的起因 死锁的起因是并发进程的资源竞争。 产生死锁的根本原因系统提供的资源个数少于并发进程所要求的该类资源数。显

17、然，由于资源的有限性，不可能为所有要求资源的进程无限制地提供资源。 消除死锁的方法：采用适当的资源分配算法。第三章 进程管理第27页2022-6-93.产生死锁有四个必要条件： (1) (1) 互斥条件互斥条件: : 并发进程所要求和占有的资源是不能同时被两个以上进程使用或操作的，进程对它所需要的资源进行排他性控制。(2) (2) 不剥夺条件不剥夺条件: : 进程所获得的资源在未使用完毕之前，不能被其他进程强行剥夺，而只能由获得该资源的进程自己释放。(3) (3) 部分分配部分分配: :进程每次申请它所需要的一部分资源，在等待新资源的同时继续占用已分配到的资源。(4) (4) 环路条件环路条件

18、: :存在一种进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求。flash演示：哲学家进餐问题演示：哲学家进餐问题第三章 进程管理第28页2022-6-93.产生死锁有四个必要条件：互斥条件互斥条件： 一个资源一次只能被一个进程使用一个资源一次只能被一个进程使用不剥夺条件不剥夺条件：一个资源仅能被占有它的进程释放一个资源仅能被占有它的进程释放部分分配条件部分分配条件：一个进程已占有了一些资源，但仍然要求一个进程已占有了一些资源，但仍然要求其它资源其它资源环路条件环路条件：系统中存在着一个由若干个进程形成的环形请系统中存在着一个由若干个进程形成的环形请求链求链第三章 进程管理第29页

19、2022-6-9资源分配图的实例存在死锁的资源分配图存在环路但是没有死锁3.8.2死锁的排出方法 解决死锁的方法一般可分为预防、避免、检测与恢复等三种。 预防是采用某种策略，限制并发进程对资源的请求，从而使得死锁的必要条件在系统执行的任何时间都不满足。 避免是指系统在分配资源时，根据资源的使用情况提前做出预测，从而避免死锁的发生。 死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得并发进程从死锁状态中恢复出来。 注意：在实际操作系统中大都使用检测与恢复法排除死锁。第三章 进程管理第33页2022-6-91.死锁

20、的预防破坏第一个条件破坏第一个条件 使资源可同时访问而不是互斥使用 破坏第二个条件破坏第二个条件 采用剥夺式调度方法 当进程在申请资源未获准许的情况下,如主动释放资源(一种剥夺式),然后才去等待破坏第三个条件破坏第三个条件 预先分配各并发进程所需要的全部资源，并且直到它所要的资源都得到满足后才开始执行破坏第四个条件破坏第四个条件把资源分类按顺序排列，使进程在申请、保持资源时不形成环路第三章 进程管理第34页2022-6-9死锁的预防的缺点(1) 在许多情况下，一个进程在执行之前不可能提出它所需要的全部资源。(2) 无论所需资源何时用到，一个进程只有在所有要求资源都得到满足之后才开始执行。(3)

21、 对于那些不经常使用的资源，进程在生存过程期间一直占用它们是一种极大的浪费。(4) 降低了进程的并发性。(5)限制了进程对资源的请求，而且对资源的分类编序也耗去一定的系统开销第三章 进程管理第35页2022-6-92、死锁的避免 死锁避免即动态预防，因为系统采用动态分配资源，在分配过程中预测出死锁发生的可能性并加以避免的方法。 死锁避免：资源被分成多个层次当进程得到某一层的一个资源后，它只能再申请较高层次的资源当进程要释放某层的一个资源时，必须先释放占有的较高层次的资源当进程得到某一层的一个资源后，它想申请该层的另一个资源时，必须先释放该层中的已占资源第三章 进程管理第36页2022-6-92

22、022-6-9第三章 进程管理第37页银行家算法银行家算法（Bankers Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格迪杰斯特拉在1965年为T.H.E系统设计的一种避免死结产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。系统安全状态系统安全状态

23、1. 安全状态安全状态 在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，令进程等待。 所谓安全状态，是指系统能按某种进程顺序(P1, P2, ，Pn)(称P1, P2, , Pn序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。 2. 安全状态之例安全状态之例 我们通过一个例子来说明安全性。假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1总共要

24、求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示： 进 程 最 大 需 求 已 分 配 可 用 P1P2P310495223安全序列：p2p1p3 3. 由安全状态向不安全状态的转换由安全状态向不安全状态的转换 如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。 因为，此时也无法再找到一个安全序列， 例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P

25、1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。 进程进程最大需求最大需求已分配已分配可用可用P11052P242P393银行家算法原理2022-6-9第三章 进程管理第41页我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 为保证资金的安全,银行家规定: (1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客; (2) 顾客可以分期贷款,但贷款的总数不能超过最大需求量; (3) 当银行家现有的资金不能满足顾客尚需的贷款数

26、额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款; (4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金. 操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。 1. 银行家算法中的数据结构银行家算法中的数据结构 (1) 可利用资源向量Available。这是一个含有m个元素

27、的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej=K，则表示系统中现有Rj类资源K个。 (2) 最大需求矩阵Max。这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。 (4) 需求矩阵Need。这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 Needi,j=Maxi,j-Allocationi,j (3)

28、 分配矩阵Allocation。这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的数目为K。 2. 银行家算法银行家算法 设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1) 如果RequestijNeedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果RequestijAvailablej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。

29、reqi=needierrorreqi=availiblock (3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej =Availablej-Requestij; Allocationi,j =Allocationi,j+Requestij; Needi,j =Needi,j-Requestij; (4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 avail=avail-reqialloci=alloci+reqi

30、needi=needi-reqifinishi=.F.needi=workwork=work+allocifinishi=.T.3. 安全性算法安全性算法 (1) 设置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行所 需 的 各 类 资 源 数 目 ， 它 含 有 m 个 元 素 ， 在 执 行 安 全 算 法 开 始 时 ，Work =Available; Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi =false; 当有足够资源分配给进程时， 再令Finishi =true。 (2) 从进程集合中找到一个能满足下述条件的进程：

31、 Finishi=false; Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。 (3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj =Worki+Allocationi,j; Finishi =true; go to step 2; (4) 如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。 银行家算法之例银行家算法之例 假定系统中有五个进程P0, P1, P2, P3, P4和三类资源A, B, C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 3

32、-15 所示。 图 3-15 T0时刻的资源分配表 Max A B C Allocation A B C Need A B C Available A B C p0 7 5 3 0 1 0 7 4 3 3 3 2(2 3 0) p1 3 2 2 2 0 0(3 0 2) 1 2 2(0 2 0) p2 9 0 2 3 0 2 6 0 0 p3 2 2 2 2 1 1 0 1 1 p4 4 3 3 0 0 2 4 3 1(1) T0时刻的安全性： 图 3-16 T0时刻的安全序列 Work A B CNeed A B C Alloc A B CWork+alloc A B C Finish p1

33、 3 3 2 1 2 2 2 0 0 5 3 2 true p3 5 3 2 0 1 1 2 1 1 7 4 3 true p4 7 4 3 4 3 1 0 0 2 7 4 5 true p2 7 4 5 6 0 0 3 0 2 10 4 7 true p0 10 4 7 7 4 3 0 1 0 10 5 7 true (2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系统先假定可为P1分配资源，并修改Avai

34、lable, Allocation1和Need1向量，由此形成的资源变化情况如图 3-15 中的圆括号所示。 再利用安全性算法检查此时系统是否安全。 图 3-17 P1申请资源时的安全性检查 Work A B CNeed A B C Alloc A B CWork+alloc A B C Finish p1 2 3 0 0 2 0 3 0 2 5 3 2 true p3 5 3 2 0 1 1 2 1 1 7 4 3 true p4 7 4 3 4 3 1 0 0 2 7 4 5 true p0 7 4 5 7 4 3 0 1 0 7 5 5 true p2 7 5 5 6 0 0 3 0 2

35、 10 5 7 true2022-6-9第三章 进程管理第53页 例如：例如：进程进程PA，使用资源的顺序是，使用资源的顺序是R1，R2； 进程进程PBPB，使用资源的顺序是，使用资源的顺序是R2R2，R1R1；若采用动态分配有可能形成环路条件，造成死锁。若采用动态分配有可能形成环路条件，造成死锁。采用有序资源分配法：采用有序资源分配法：R1R1的编号为的编号为1 1，R2R2的编号为的编号为2 2； PA：申请次序应是：申请次序应是：R1，R2 PB：申请次序应是：申请次序应是：R1，R2 这样就破坏了环路条件，避免了死锁的发生。这样就破坏了环路条件，避免了死锁的发生。第三章 进程管理第54

36、页2022-6-9 2. 2. 银行家算法银行家算法 检查申请者对各类资源的最大需求量，如果系统现存的各类资源可以满足它的最大需求量，就满足当前的申请。 缺点： 必须事先知道每个进程的资源最大需求量。 算法过于保守。 要求系统资源与用户数不变。第三章 进程管理第55页2022-6-9 例子：假定系统有10个资源（为了说明问题的简单，不管它是什么资源），目前分配的情况如上表： 此时，系统中只剩下2个资源，这时就要考察能满足哪个进程，不能满足P和R的最大要求，能满足Q，于是将剩下的2个资源分配给Q，Q就能完成，然后释放所占用的6个资源。 可满足P，也可满足R，这时不论分给谁都能保证完成。第三章 进

37、程管理第56页2022-6-93. 3. 死锁的检测与恢复死锁的检测与恢复 1. 1. 死锁的检测死锁的检测 由系统提供检测算法由系统提供检测算法 由计算机操作员检测由计算机操作员检测 通常的方法是程序员的经验，如通常的方法是程序员的经验，如UNIX系统中，系统中，可考察进程的运行时间。在可考察进程的运行时间。在UNIX系统中有命令系统中有命令PS可显示进程占用可显示进程占用CPU的时间，若发现有一组进程在的时间，若发现有一组进程在一段时间内没有占用一段时间内没有占用CPU，就认为这类进程出现了，就认为这类进程出现了死锁。死锁。第三章 进程管理第57页2022-6-9 2. 2. 死锁的恢复死

38、锁的恢复 撤消陷于死锁的全部进程； 逐个撤消陷于死锁的进程，直到死锁不存在； 从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失； 从某个存在的中间检测点重新启动各死锁进程。第三章 进程管理第58页2022-6-93.9 3.9 线程线程n3.9.1 为什么要引入线程n3.9.2 线程的基本概念n3.9.3 线程与进程的区别n3.9.4 线程的实用范围第三章 进程管理第59页2022-6-93.9.1 线程的引入（1）创建进程。系统在创建进程时，必须为之分配其所必需的、除处理机以外的所有资源。如内存空间、I/O设备以及建立相应的PCB结构。（2）撤消进程。系统在撤消进程时，又必须先对这些

39、资源进行回收操作，然后再撤消PCB结构。（3）进程切换。在对进程进行切换时，由于要保留当前进程的CPU环境和设置新选中进程的CPU环境，为此需花费不少处理机时间。 为了减少进程切换和创建、撤销进程的开销，提高执行效率和节省资源，人们开始在操作系统中引进“线程”的概念。 第三章 进程管理第60页2022-6-93.9.2 线程的基本概念 引入线程主要是为了提高系统的执行效率，减少处理机的空转时间和调度切换（保护现场信息）的时间，以及便于系统管理 线程线程是进程内的一个执行单元，也是进程内的一个可调度是进程内的一个执行单元，也是进程内的一个可调度实体。实体。 一个进程内的基本调度单位称为线程或称为

40、轻权一个进程内的基本调度单位称为线程或称为轻权进程（进程（Light weight process），这个调度单位既可以由），这个调度单位既可以由操作系统内核控制，也可以由用户程序控制操作系统内核控制，也可以由用户程序控制第三章 进程管理第61页2022-6-93.9.2 线程的概念 进程是程序的一次执行过程和资源分配的基本单位。 线程是一个进程内的基本调度单位，又称为轻权进程（Light weight process） 调度单位既可以由操作系统内核控制，也可以由用户程序控制 引入线程的目的：为了提高系统的执行效率，减少处理机的空转时间和调度切换（保护现场信息）的时间，以及便于系统管理。第三章

41、 进程管理第62页2022-6-93.9.3 线程与进程的比较 1调度：在传统的操作系统中，拥有资源的基本单位和独立调度、分派的基本单位都是进程。 2并发性：在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。 3拥有资源：不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。 4系统开销：由于在创建或撤消进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等。因此，操作系统所付出的开销将明显地大于在创建或撤消线程时的开销。

42、第三章 进程管理第63页2022-6-9 二二. . 线程和进程的关系线程和进程的关系 线程是进程的一个组成部分。线程是进程的一个组成部分。 一个进程可以有多个线程，一个进程的多个线程都一个进程可以有多个线程，一个进程的多个线程都在进程的地址空间内活动。在进程的地址空间内活动。 资源分配的对象是进程，而不是线程。资源分配的对象是进程，而不是线程。 处理机调度的基本单位是线程而不是进程，但线程处理机调度的基本单位是线程而不是进程，但线程使用的资源是进程分到的资源。使用的资源是进程分到的资源。 线程在执行过程中，需要协作同步。线程在执行过程中，需要协作同步。第三章 进程管理第64页2022-6-9进程进程进程进程线程线程线程线程指令计数器指令计数器指令计数器指令计数器(a) 三个进程，各有一个线程三个进程，各有一个线程(b) 一个进程有三个线程一个进程有三个线程进程和线程进程和线程第三章 进程管理第65页2022-6-93.9.4线程的实用范围 使用进程最大的好处是在多个任务需要处理机处理时，减少处理机的切换时间。 线程的三个典型应用 （1）服务器中的文件管理或通信控制 （2）前后台处理 （3）异步处理第三章 进程管理第66页2022-6-9 引入线程的优点引入线程的优点 创建一个线程的开销比创建一个进程的开销小。 C