计算机操作系统-第三章-进程管理

1、计算机操作系统（2015版） 讲 授： Email: MyTel: 福州大学数学与计算机科学学院福建省网络计算与智能信息处理重点实验室第3章 进程管理3.1 进程的概念3.2 进程的描述3.3 进程状态及其转换3.4 进程控制3.5 进程互斥3.6 进程同步3.7 进程通信3.8 死锁问题讲授课时：10.0引入进程的目的刻画系统的动态性。同程序相比较，进程具有动态性，有生命周期，从创建到消亡，进程处于不断的动态过程中。因此，引入进程概念能更好系统内部的“动态性”。3.1 进程的概念 引入进程的目的 描述共享性。 可再入程序：执行中自身不改变的纯代码。 可再入程序在系统中可生成多个执行实体，共享

2、系统资源。而程序是静止的，无法描述共享属性。（共享链接库等） 3.1 进程的概念 进程的定义 定义：进程是具有独立功能的程序（段）在某个数据集上的一次运行活动。 进程是系统资源分配的独立单位。 从定义看出，进程与程序是有区别的，具有其本身的特征和属性。3.1 进程的概念 进程的属性（1） 动态性：是一次执行过程，有生命周期。 并发性：多个进程可并发执行。 结构性：由程序块、数据块、进程控制块等多个部分组成。 独立性：是系统资源分配和调度的独立单位。3.1 进程的概念 进程的属性（2） 共享性：多个进程共享同一程序。 交互性：多个进程之间可能有制约关系。 异步性：每个进程都以各自的、不可预知的速

3、度向前推进。3.1 进程的概念 进程与程序的关系 进程是动态的，程序是静态的； 进程是由程序和数据等多个部分组成的; 多个进程可以对应一个程序； 进程有生命周期，是短暂的；而程序是相对长久的； 进程具有并发性，而程序没有。3.1 进程的概念1、进程的静态描述 从处理机调度出发，对进程实体的描述称为进程的静态描述（逻辑描述）。 进程静态结构由三部分组成：进程控制块PCB，程序段和数据集。3.2 进程的描述 进程控制块PCB 系统利用PCB来控制和管理进程，PCB是系统感知进程存在的唯一标志。 进程与PCB是一一对应的。 一般，PCB中包含三类信息：描述信息、控制信息和现场信息。3.2 进程的描述

4、 进程控制块PCB 描述信息 进程标识符(process ID)，唯一，通常是一个整数； 进程名，通常基于可执行文件名（不唯一）； 用户标识符(user ID)：所属用户； 进程家族关系；3.2 进程的描述 Windows命令行 进程列表：TASKLIST /v c:process.txt 终止进程：TASKKILL /PID 230 /PID 12413.2 进程的描述 进程控制块PCB 控制信息 进程状态state和优先级priority ； 代码执行入口地址和程序的外存地址； 运行统计信息：执行时间、页面调度； 进程的队列指针； 进程的消息队列指针：同步信号； 资源列表：所需资源、打开文

5、件列表等；3.2 进程的描述 进程控制块PCB 现场信息 当进程中断时即把现场信息保存到进程控制块中，当进程再次运行时恢复现场。 寄存器内容：通用、程序计数器PC、状态PSW，栈指针等； 指向赋予该进程的段/页表的指针；3.2 进程的描述2、进程的内存映像（Process Image） 进程在系统中的具体实现，即在内存中的描述称为“进程映像”，即进程的动态结构。 进程映像主要包括PCB、程序块、数据块和堆栈等部分。 3.2 进程的描述3.2 进程的描述在虚存中的进程映像进程标识信息进程现场信息进程控制信息用户堆栈用户私有空间（代码、数据）共享地址空间PCB 进程的上下文（Process con

6、text） 把 “进程映像+运行环境”称为进程上下文（process context），包括： 用户级上下文（user -level context）：包括用户程序块、数据块和堆栈等空间。 系统级上下文（system -level context）：包括PCB，进程环境，系统堆栈等。3.2 进程的描述 进程的上下文（Process context） 寄存器上下文（register context）：由程序状态字寄存器、各类控制寄存器、地址寄存器、通用寄存器、用户栈指针等组成。3.2 进程的描述 进程三种基本状态 运行态running：正在占有处理器运行。 就绪态ready：具备运行条件，但由于

7、无CPU暂时不能运行的状态。 等待态wait：阻塞（blocked）态、睡眠（sleep）态，因等待某种事件的发生而暂时不能运行的状态。3.3 进程状态及其转换 进程三种基本状态 一个新进程创建后是什么状态？ 一个进程执行过程中，它的状态可能会发生改变。3.3 进程状态及其转换 进程状态转换 3.3 进程状态及其转换运行态就绪态等待态所等待事件已发生等待某事件的发生选中落选 进程状态转换 运行态等待态：等待使用资源或某事件发生，如等待外设传输。 等待态就绪态：相应等待事件己经发生，如外设传输结束。（等待结束） 运行态就绪态：时间片到或出现了更高优先权进程。（落选） 就绪态运行态：进程被调度程序

8、选中。3.3 进程状态及其转换3.3 进程状态及其转换 进程的七种状态模型 阻塞挂起状态（Blocked suspend）： 进程在外存并等待某事件的出现； 就绪挂起状态（Ready suspend）： 在外存，但只要进入内存，即可运行；3.3 进程状态及其转换激活挂起事件发生事件发生等待事件挂起调度超时释放激活挂起进程七种状态转换示意图3.3 进程状态及其转换 进程的七种状态模型挂起：当内存不足时，临时将等待进程或就绪进程从内存移到外存，即挂起。激活：当条件满足，将挂起进程重新装入内存，状态发生转变。进程控制的任务 包括创建进程、阻塞进程、唤醒进程、挂起进程、激活进程、终止进程和撤销进程等。

9、 进程控制功能是由OS中的原语来实现的。 3.4 进程控制 原语(Primitive) 原语是指在核心态下执行，且不允许被中断的一个过程，是一个原子操作，一个基本执行单位。 即：原语的执行是顺序的，不可并发。 另外，原语是一个过程，可能包括多条指令代码，与机器指令有差别。 3.4 进程控制 进程的创建何时创建进程？ 用户提交一个交互式作业时，系统创建相应的新进程。 发生系统调用时，系统创建一个新的服务进程。 一个普通进程创建新的子进程，形成父子关系的进程。3.4 进程控制 进程创建的工作 申请一个PCB空间。 初始化进程控制块数据（如状态），分配PID和进程标识符。 把进程PCB加入就绪（挂起

10、）队列，等待进程调度。 fork()，vfork(), execl()等3.4 进程控制 进程的撤消 何时进程被消亡？ (1) 进程完成所有功能，正常终止。 (2) 某种错误导致进程非正常终止。 (3) 通过系统调用（撤销）普通进程。 return()，exit()，kill()等 3.4 进程控制 进程的撤消 父进程撤销，并非一定影响子进程，但子进程可能变为僵死进程，即无意义进程。3.4 进程控制 进程的阻塞与唤醒 进程阻塞是一个进程让出处理器，去等待一个事件。 执行阻塞 进程可以调用阻塞原语阻塞自己，属于进程的自主行为。wait(pid)函数等 当等待事件发生后会产生中断，由操作系统判断并

11、将某个被阻塞的进程唤醒。3.4 进程控制 程序的顺序执行 程序的顺序执行指在计算机系统中只有一个程序在运行，生存期间独占所有资源，其执行不受外界影响。（单道系统） 程序员编写程序时，通常都是这么认为的！程序的执行方式 程序的顺序执行 顺序性：执行过程是一个严格规定过程。 封闭性：最终结果由初始条件决定，不受外界因素影响。 可再现性：只要初始条件相同，则无论何时重复执行该程序都会得到相同结果。程序的执行方式 程序的并发执行 并发即在一个时间段内有2个以上的程序同时处于运行（尚未结束）状态。 此时，多进程运行次序是不确定的。程序的执行方式 程序的并发执行不可再现性：并发程序执行的结果与其执行的相对

12、速度有关，是不确定的； 随机性（间断性）：程序的执行具有间断性特征，可能走走停停。 非封闭性：由于共享资源等因素，进程之间可能具有一定制约性。程序的执行方式 与时间有关的错误 两个交互（相互通信）的并发进程，其中一个进程对另一个进程的影响常常是不可预期的。此时，程序的执行就可能出现错误。 两种可能的错误： 结果不唯一；举例？ 永远等待；举例？并发执行的问题 与时间有关的错误例1 购买飞机票问题。 （结果不唯一） 假设一个飞机订票系统有两个终端，分别运行进程Tl 和T2。该系统的公共数据区中的一些单元Aj(j=1，2，)分别存放某月某日某次航班的余票数，而xl 和x2 表示进程T1 和T2 执行

13、时所用的工作单元。 飞机票售票程序如下：并发执行的问题 与时间有关的错误process Ti(i=1,2)var Xi:integer;begin按旅客订票要求找到Aj;Xi:=Aj;if Xi=1 then begin Xi:=Xi-1; Aj:=Xi;输出一张票;endelse 输出信息“票已售完”;end;并发执行的问题 与时间有关的错误由于T1 和T2 是两个可同时执行的并发进程，可能出现如下所示的运行情况。T1: X1 := Aj; X1 = m (m0)T2: X2 := Aj; X2 = mT2: X2:=X2-1; Aj:=X2;出票； Aj = m-1T1: X1:=X1-1

14、; Aj:=X1;出票； Aj = m-1显然，此时即把同一张票卖给了两个旅客，但Aj 的值却只减1，造成票务信息出错。并发执行的问题 与时间有关的错误例2 哲学家吃通心粉的故事。（永远等待） 场景：5个哲学家围坐1个圆桌吃通心粉； 规定：要吃通心粉，须先获得2把叉子； 初始条件：在哲学家之间共放5把叉子； 执行：哲学家随机思考，随机就餐； 结果：可能饿死！并发执行的问题一般两种情况： 竞争关系（间接制约） 在同一时间段内竞争使用1个不可共享的资源。 进程的互斥是解决进程间竞争关系(间接制约关系)的手段。进程之间的制约关系 协作关系（直接制约） 指系统中多个进程中发生的事件存在某种时序关系，相

15、互合作，共同完成一项任务。 进程的同步是解决进程间协作关系(直接制约关系)的手段。进程之间的制约关系 临界资源与临界区 临界资源：系统中同时只允许1个进程访问的资源称为临界资源或互斥资源。 临界区：进程中涉及到临界资源的程序段称为临界区（critical region），即不允许多个并发进程交叉执行的一段程序。3.5 进程互斥 临界区的执行原则 有空则进：当无进程执行临界区时，任何进程均可执行自己的临界区； 无空等待：不允许两个以上的进程同时执行临界区；其他进程必须等待； 有限等待：任何执行临界区代码的请求应在有限的时间内得到满足。3.5 进程互斥 什么是互斥 进程的互斥指一组并发进程中的一个

16、或多个程序段，因共享某一互斥资源而被限制，不能以并发方式执行相关代码。 即，不允许两个以上的共享互斥资源的并发进程同时执行临界区称为互斥。 临界资源访问是互斥的，使得临界区的执行应该互斥的。3.5 进程互斥 互斥的加锁实现 一种可能的办法是对临界区加锁以实现互斥。当某个进程进入临界区之后，它将锁上临界区，直到它退出临界区时为止。 并发进程在申请进入临界区时，首先测试该临界区是否是上锁的。如果该临界区已被锁住，则该进程要等到该临界区开锁之后才有可能获得临界区。3.5 进程互斥 加锁后的临界区程序描述如下：lock(keyS)临 界 区unlock(key ) 设key=1时表示类名为的临界区可用

17、，key=0时表示类名为的临界区不可用。 3.5 进程互斥 P、V操作实现 Dijkstra 发明了信号量和P、V 操作（荷兰语中“测试（Proberen）”和“增量（Verhogen）”）。 利用信号量和P、V 操作既可以解决并发进程的竞争问题，又可以解决并发进程的协作问题。3.5 进程互斥 P、V操作 信号量是一个数据类型，定义如下： struc semaphore int value;pointer_PCB queue; 信号量说明： semaphore s; 3.5 进程互斥 P、V操作P(s) s.value = s.value -; if (s.value 0) 改当前进程状态为等

18、待状态； 将其PCB插入相应等待队列末尾s.queue; 3.5 进程互斥 P、V操作V(s) s.value = s.value +; if (s.value = 0) 唤醒等待队列s.queue中的1个进程； 改被唤醒进程的状态为就绪态； 并将其插入就绪队列； 3.5 进程互斥原语操作功能 V原语操作功能3.5 进程互斥 P、V操作实现进程互斥 用PV 实现进程互斥步骤如下： 每个互斥资源设1个互斥变量Si； 信号量变量赋初始值Si=1； 将各进程中的临界区代码段用P(Si)和V(Si)括起来，即可完成进程互斥。 具体形式如下页:3.5 进程互斥 P、V操作实现进程互斥 用PV 操作实现进

19、程互斥一般形式如下：Var S1: semaphore;S1:= 1;cobegin coend; 3.5 进程互斥process PibeginP(S1);临界区；V(S1);end; 实例分析 例1：写者-写者问题。 要求：一个文件同一时刻不允许两个以上写进程访问。 例2：停车场计数器问题。 要求：监控汽车驶入和开出的进程能够准确修改车库空位数目。3.5 进程互斥 进程同步概念 指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。 具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态。3.6

20、进程同步用PV操作实现进程同步 具体步骤分为三步：为各并发进程设置各自的私用信号量；信号量变量赋初值；利用原语和信号量规定各进程的执行顺序。3.6 进程同步 用PV操作实现进程同步 用PV 操作实现进程同步一般形式如下：Var S1，S2: semaphore;S1:= n; /n大于0 ；S20；cobegin coend; ；3.6 进程同步process PibeginP(S1);临界区；V(S2);end;process PjbeginP(S2);临界区；V(S1);end; 实例分析 例1：经典的生产者消费者问题。1-1-13.6 进程同步 实例分析 补充：1生产者1消费者-多缓冲区

21、问题； 1个生产者和1个消费者，多缓冲区； （下标访问方法） 默认条件：缓冲区不能同时访问；3.6 进程同步 实例分析 例2：多生产者多消费者问题； 多生产者和多消费者，单缓冲区； 多生产者和多消费者，多缓冲区； 多个生产者和多个消费者，不限缓冲区； 3.6 进程同步3.6 进程同步process producer_ibeginL1:produce a product;P(empty);P(S);Bin := product;in:=(in+1) mod k;V(S);V(full);goto L1;end;process consumer_jbeginL2:P(full);P(S);Prod

22、uct:= Bout;out:=(out+1) mod k;V(S);V(empty);consume a product;goto L2;end;此解两个P操作的顺序是不可交换的！ 实例分析 例3：多读者写者问题。 多读者和写者，共享一个文件F，要求：（1）允许多个读者同时执行读操作；（2）写者在完成写操作前不允许其他读者或写者执行；（3）写者欲执行，若已有读者在读，则必须等待所有读者完成读操作后才能执行写操作；3.6 进程同步 实例分析 例4：父女、母子吃水果问题. 描述：桌子有一个盘子,每次只能放入一个水果,爸爸专向盘中放苹果,妈妈专向盘中放桔子,女儿专等吃盘中的苹果,儿子专等吃盘中的桔

23、子.试用P, V操作写出他们能正确同步的并发程序. 3.6 进程同步 互斥与同步的关系 互斥是一种特殊的同步。 互斥进程之间等待的同步信号是同一个信号，且信号量初始值必须为1。3.6 进程同步 进程之间的交换信息称为进程通信IPC（Inter-Process Communication ）。 低级通信与高级通信机制 低级通信一般只传送少量的信息，以达到控制进程执行速度的作用。 高级通信要传送大量数据。高级通信的目的主要是为了交换信息。3.7 进程通信 低级通信与高级通信机制 进程间通信方式主要包括： 共享内存：信号(signal)、管程等； 共享文件：管道（pipeline）； 消息机制：消息

24、缓冲方式、信箱方式等。 其中，共享内存属于低级通信机制，其他属于高级通信机制。3.7 进程通信 信号通信机制 信号（signal）机制又称软中断，是一种进程之间进行通信的简单通信机制，通过发送一个指定信号来通知进程某个异常事件发生，并进行适当处理。 常用于进程的同步控制。3.7 进程通信消息传递方式消息传递：是相互合作的并发进程交换信息的一种方式，进程间的数据交换以消息为单位。消息队列：每个进程有一个与之相关的消息队列，发送者：指定发送的每个消息的类型，类型可以被接收者用作选择原则，接收者可以按先进先出的顺序接收消息，或者按类型接收。当进程向一个满队列发送消息时，它将被挂起；当进程从一个空队列

25、读取时也会被挂起。消息：一段文本。消息格式设计与应用环境和要求有关固定长度消息：可以减小处理和存储的开销基于文件的：传送大量的数据可变长度消息：灵活消息的一般格式消息头：源标识、目的标识、 长度域、类型域、控制域消息体消息传递方式消息消息传递方式消息队列UNIX消息队列APImsgget依据用户给出的整数值key，创建新消息队列或打开现有消息队列，返回一个消息队列ID；msgsnd发送消息；msgrcv接收消息，可以指定消息类型；没有消息时，返回-1；msgctl对消息队列进行控制，如删除消息队列；消息传递方式类型直接通信：必须明确命名通信的接收者或发送者，原语send和receive的定义如

26、下：Send(P,message):发送消息到进程PReceive(Q,message):接收来自进程Q的消息。消息传递方式类型间接通信：消息通过邮箱或端口来发送和接收。原语定义如下：Send（A,message）；receive（A,message）；思考：设P1，P2和P3都共享邮箱A，进程P1发送一个消息到A，而进程P2和P3都对A执行reveive。哪个进程能接收到P1所发送的消息？（P85） 信箱方式 采用间接通信方式时，进程间发送或接收消息通过一个共享的数据结构信箱来进行，消息可以被理解成信件，每个信箱有一个唯一的标识符。 间接通信方式解除了发送进程和接收进程之间的直接联系，在消息

27、的使用上灵活性较大。3.7 进程通信 信箱方式 一个进程可以分别与多个进程共享信箱，同时和多个进程进行通信。 一对一的关系允许在两个进程间建立专用通信链接； 多对一的关系对客户机/服务器间的交互非常有用； 一对多的关系适用于一个发送者和多个接收者，适用于广播消息。3.7 进程通信 信箱方式 此时，“发送”和“接收”原语的形式如下： send(A，信件)：把消息传送到信箱A。 receive(A，信件)：从信箱A 接收消息。 信箱是存放信件的存储区域，每个信箱可以分成信箱头和信箱体两部分。信箱头指出信箱容量、信件格式、存放信件位置的指针等；信箱体用来存放信件。3.7 进程通信 信箱方式 “发送”

28、和“接收”两条原语的功能为： 发送信件：如果指定信箱未满，则将信件送入信箱中由指针所指位置，并释放等待该信箱中信件的等待者；否则，发送信件者被置成等待信箱状态。 接收信件：如果指定信箱有信，则取出一封信件，并释放等待信箱的等待者；否则，接收信件者被置成等待信件状态。3.7 进程通信 管道机制 管道（pipe）是UNIX 传统通信方式。管道是单向的，发送进程写入(字节流)信息，接收进程接收信息，先写入的先读出。 管道的实质是一个共享文件，即利用辅存来进行数据通信。因此，管道通信基本上可以借助于文件系统原有的机制实现，包括（管道）文件的创建、打开、关闭和读写。3.7 进程通信 管道机制3.7 进程

29、通信 管道机制 传统的管道技术已在操作系统中广泛使用。但管道临时建立，且难全局服务。 后来，UNIX又推出了有名管道技术。这是一种永久性通信机制，具有UNIX 文件名、访问权限，能像一般文件一样被打开、关闭、删除。3.7 进程通信 管道机制 在命令层面上也可以使用管道，例如： sort|more 等命令； 管道和消息队列的主要区别在于：管道中的消息是无界的，它存于外存；消息队列是位于内存的，且大小有限。3.7 进程通信 两个实例分析：（1）生产者-消费者问题中两个P操作顺序；（2）哲学家吃通心面问题； 3.8 死锁 死锁的定义 所谓死锁- 一组进程中，每个进程都无限等待被该组进程中另一进程所占

30、有的资源，因而永远无法得到资源，这种现象称为进程死锁，这一组进程就称为死锁进程。3.8 死锁 死锁的原因 产生死锁的原因在于： （1）资源不足导致的资源竞争； （2）并发程序执行的顺序不当； 因此，解决死锁问题成为OS设计中必须考虑的重要问题。3.8 死锁 产生死锁的4个必要条件 (1) 互斥条件。并发进程所要求和占有的资源是不能同时被两个以上进程使用或操作的，进程对它所需要的资源进行排他性控制。 (2) 非剥夺（非抢占）条件。进程所获得的资源在未使用完毕之前，不能被其他进程强行剥夺，而只能由获得该资源的进程自己释放。3.8 死锁 产生死锁的4个必要条件 (3) 占有且等待条件。进程每次申请它

31、所需要的一部分资源，在等待新资源的同时继续占用已分配到的资源。 (4) 环路条件。存在一种进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求。 只要破坏其中一个条件，死锁就可防止。3.8 死锁 解决死锁的方法 解决死锁分为预防、避免、检测与恢复三个方面。Unix系统忽略死锁问题。 预防是采用某种策略，在执行前满足进程所有条件，否则不投入运行。 避免是指当进程动态申请资源时，系统根据资源使用情况提前做出预测，避免死锁的发生。3.8 死锁 解决死锁的方法 死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得

32、并发进程从死锁状态中恢复出来。 通常，死锁的检测和恢复花费的代价比预防与避免更小一些，因此，在实际操作系统中大都使用检测与恢复法排除死锁。3.8 死锁 防止死锁的方法思考 破坏第一个条件（互斥条件），如磁盘可用这种办法管理，但其他资源是不可行的。 破坏第三个条件（不剥夺条件），但这种只适用于主存和CPU的分配。 下面介绍两种比较实用的死锁防止方法，它们能破坏第二个条件或第四个条件。3.8 死锁 死锁预防（防止） 静态分配策略 所谓静态分配是指一个进程必须在执行前就申请它所要的全部资源，并且直到它所要的资源都得到满足后才开始执行。进程执行中不再申请资源，即破坏了第二个条件。 此时，所有并发执行的

33、进程要求的资源总和不超过系统拥有的资源数。(资源利用率较低)3.8 死锁 死锁预防（防止） 层次分配策略 该策略将阻止第四个条件（循环等待条件）的出现。 资源被分成多个层次，一个进程得到某一层资源后，它只能再申请较高一层的资源； 当一个进程要释放某层的一个资源时，必须先释放较高层资源； 当一个进程想再申请同层中另一个资源时，必须先释放该层中的已占资源。3.8 死锁 死锁预防（防止） 层次分配策略 这种策略的一个变种是按序分配策略。把所有资源排成一个顺序，如系统共有m 个资源，用ri 表示第i 个资源。 规定：进程不得在占用资源ri(1im)后再申请rj(ji)。不难证明，按这种策略分配资源时系

34、统不会发生死锁。（如哲学家吃通心面问题）3.8 死锁死锁避免（Deadlock Avoidance）定义：在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。如果一个新的进程的资源请求会导致死锁, 则拒绝启动这个进程；如果满足一个进程新提出的一项资源请求会导致死锁, 则拒绝分配资源给这个进程；系统的安全状态在资源的动态分配过程中, 采用某种策略防止系统进入不安全状态, 从而避免发生死锁。安全状态: 系统能按某种顺序, 如, 为每个进程分配所需资源, 直到最大需求, 使每个进程都可顺序完成,

35、称系统处于安全状态。（安全状态一定是没有死锁发生的)系统的安全状态安全序列: 一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i )当前占有资源量之和，系统处于安全状态。 安全序列可以不唯一!不安全状态: 系统中不存在安全序列。不安全状态不一定导致死锁。 死锁避免 银行家算法（Dijkstra, 1965） Dijkstra提出单资源银行家算法，银行家对客户提出下列约束条件： 客户必须预先说明所需最大资金量； 银行给予分配的条件是银行所剩余额大于客户所需余额；否则拒绝； 银行满足了客户对资金的最大需求量，客户在

36、资金运作后，应及时归还银行。3.8 死锁银行家算法中的数据结构设系统中有m种不同资源, n个进程Available向量: 系统中尚未分配的每种资源的总量Availablej: 尚未分配的资源j的数量Max矩阵: 各个进程对每种资源的最大需求量(进程事先声明)Maxi, j（ClaimI,j): 进程i 对资源j 的最大需求量Allocation矩阵: 当前资源分配状况Allocationi, j: 进程i获得的资源j的数量Need矩阵: 每个进程还需要的剩余资源的数量Needi, j: 进程i尚需的资源j的数量各数据间的关系对所有的i , j (i = 1, 2, , n; j = 1, 2,

37、 , m), 有:Resourcej = Availablej + (Allocation1, j + Allocation2, j + + Allocationn, j)Maxi, j = ResourcejAllocationi, j = Maxi, jAllocationi, j + Needi, j =Maxi, j安全性算法1.设Work和Finish 分别是长度为m 和n 的向量，按如下方式进行初始化:Work = AvailableFinish i = false for i - 1,3, , n.2.查找这样的i使其满足: (a) Finish i = false(b) Nee

38、di Work如果没有这样的i存在，那么就转到第4步.3.Work = Work + AllocationiFinishi = True返回到第2步.4.如果对所有的i，Finish i = True ，那么系统处于安全状态一个安全性计算的实例问：T0时刻是否为安全状态？资源分配算法（1）设Requesti 为进程Pi的请求向量。如果Requesti j = k 那么进程Pi 所需要的资源类型Rj.的实例数量为k。当进程pi 做出资源请求时，会采取如下动作：1.如果Requesti Needi 转到 2. 否则，产生出错条件，因为进程Pi请求的数量已超过了其所需的资源数量请求。2.如果 Req

39、uesti Available,则转到第 3步. 否则 Pi 必须等待，这是因为没有足够的可用资源.3.假定系统可以分配给进程Pi 所请求的资源，并按如下方式修改状态:Available = Available - Requesti;Allocationi = Allocationi + Requesti;Needi = Needi Requesti;4.系统执行安全性算法。查看：如果所产生的资源分配是安全的，那么进程Pi可分配到其所需资源;如果新状态不安全，那么进程Pi 必须等待Requesti并恢复到原先资源分配状态资源分配算法（2）银行家算法举例假定系统有三个进程P1，P2，P3，共有1

40、2台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。设在T0时刻进程P1，P2，P3已分别获得5，2，2台，尚有3台空余未分。最大需求已分配尚需可用P110553P2422P39273台空闲可使P2结束P2运行，并释放资源5台空闲可使P1结束P1运行，并释放资源10台空闲可使P3结束P3称 P2，P1，P3 为安全序列银行家算法-例条件同前例，如果：P3提出申请2台资源，问是否可以满足要求？解：先假设能够满足要求且分配资源，则系统状态如下：最大需求已分配尚需可用P110551P2422P3945只剩余 1 台资源，不能使任何一个进程执行结束，因而不存在安全序列，所以系统不安

41、全，因此拒绝分配资源，撤消开始的假设。假设法AllocationMaxNeedR1R2R3R1R2R3R1R2R3ABCD152001100112363421122342211420022230例：R1,R2,R3的数量分别为（9，3，6）；Available(1,1,2)WorkNeedAllocationR1R2R3R1R2R3R1R2R3BACD16791223233412140202 2230512010101012WorkallocationR1R2R367992233 3346 FinishTrueTrueTruetrueT0时刻是否为安全状态？ 安全！MaxAllocationN

42、eedR1R2R3R1R2R3R1R2R3ABCD363421122342252001101112111420021230进程A请求资源Request（1，0，1），能够分配？为什么？RequestA（1，0，1）=Need(2,2,2)RequestA（1，0，1） A （2，3，3） 所以不能满足。解：最大资源需求M已分配资源数量U尚需资源NABCABCABCP1P2P3P4P55544453002961154244231000122544310214300174610剩余向量A = （2，3，3） 在的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？解：因为R（2，0，1）=N4(2, 0, 1) 且 A （2，3，3） 假设可以满足，则N4=(0, 0, 0), A= （0，3，2），在此基础上，（0, 3, 2）P4（4, 3, 7）P5（7, 4, 11）P1（9, 5, 13）P2（13, 5, 15）P3所以是安全的，因此可以实施分配解死锁避免小结优点比死锁预防限制少；无死锁检测方法中的资源剥夺, 进