操作系统进程管理

操作系统 赵辉zhaohui kejian 密码 kejian 第2章 进程管理 本章内容 2 1进程的概念2 2进程控制2 3线程的基本概念2 4进程的同步与互斥2 5进程调度2 6死锁问题 4 2 1进程的概念 2 1 1单道程序的顺序执行2 1 2多道程序的并发执行2 1 3进程的定义2 1 4进程与程序的区别2 1 5进程的状态及其转换2 1 6进程控制块 目标 理解单道程序顺序执行和多道程序并发执行的过程 掌握进程的概念 理解进程和程序的关系与区别 掌握进程的三种基本状态及转换过程 理解进程控制块的作用和结构 6 2 1 1单道程序的顺序执行 单道程序顺序执行的过程 includevoidmain inta b c cin a b c a b cout c endl 2 1 1单道程序的顺序执行 单道程序顺序执行的特点顺序性 处理机的操作严格按照程序所规定的顺序执行 封闭性 程序运行时独占全机资源 资源的状态只有本程序才能改变 可再现性 只要程序执行时的环境和初始条件相同 不管怎样执行 都将获得相同的结果 7 2 1 2多道程序的并发执行 多道程序并发执行的过程若有4个程序同时进入内存 每个程序都包括输入 计算和打印 那么4个程序的执行过程是怎样的 8 2 1 2多道程序的并发执行 多道程序并发执行的特点间断性多道程序并发执行时 由于它们之间相互影响 导致执行的程序具有 执行 暂停 执行 这种间断性的活动规律 9 2 1 2多道程序的并发执行 多道程序并发执行的特点相互制约性由于内存中同时运行多个程序 它们共享系统内的资源 程序之间必然会呈现出各种各样的制约关系 10 2 1 2多道程序的并发执行 多道程序并发执行的特点不可再现性多道程序在并发执行时 由于它们相互制约 也将导致失去可再现性 11 12 temp1 n temp2 n temp1 temp1 1 temp2 temp2 1 n temp1 n temp2 2 1 3进程的定义 重点 进程是具有独立功能的可并发执行的程序在一个数据集合上的运行过程 是系统进行资源分配和调度的独立单位 13 2 1 4进程和程序的区别 进程是程序的一次执行过程 进程是一个动态的概念 而程序是一个静止的概念 程序是永久的 而进程是暂时的 进程能并发执行 而程序不能 进程和程序的组成不同 进程是由程序 数据和进程控制块三部分组成的 一个程序可以由多个进程去执行 而一个进程可以执行多个程序 14 2 1 5进程的状态及转换 重点 进程的三种基本状态就绪状态进程已分配到除CPU以外的所有必要资源时 只要再获得CPU 便可立即执行的状态 在一个系统中 可以有多个进程同时处于就绪状态 通常把这些进程排成一个或多个队列 称为就绪队列 15 2 1 5进程的状态及转换 重点 进程的三种基本状态执行状态进程已获得CPU 其程序正在执行的状态 在单处理机的系统中 处于执行状态的进程只能有一个 而在多处理机的系统中 可能有多个进程同时处于执行状态 16 2 1 5进程的状态及转换 重点 进程的三种基本状态阻塞状态正在执行的进程由于发生某事件 如I O请求 申请缓冲区失败 而暂时无法继续执行时的状态 阻塞状态的进程排成的队列称为阻塞队列 根据阻塞原因的不同可把阻塞状态的进程排成多个队列 17 2 1 5进程的状态及转换 重点 进程三种状态的转换就绪 执行处于就绪状态的进程 当进程调度程序为之分配了处理机后 该进程便可以执行 相应地 其状态就由就绪状态变为执行状态 18 2 1 5进程的状态及转换 重点 进程三种状态的转换执行 就绪在分时系统中 正在执行的进程 又称当前进程 如果因为分配给它的时间片已经用完而被暂停执行时 该进程便由执行状态变为就绪状态 19 2 1 5进程的状态及转换 重点 进程三种状态的转换执行 阻塞如果正在执行的进程因为等待某事件而受阻 无法继续执行 则该进程便从执行状态转变为阻塞状态 20 2 1 5进程的状态及转换 重点 进程三种状态的转换阻塞 就绪处于阻塞状态的进程 如果其等待的事件已经发生 则该进程便由阻塞状态变为就绪状态 21 2 1 5进程的状态及转换 重点 进程三种状态的转换 22 2 1 6进程控制块 进程控制块的作用进程是由程序 数据和进程控制块 PCB 三部分组成的 PCB中包括了操作系统所需的 用于描述进程情况及控制进程运行所需的全部信息 PCB是进程存在的惟一标志 操作系统是根据PCB来对并发执行进程进行控制和管理的 23 2 1 6进程控制块 进程控制块中的信息进程标识符信息进程标识符用于惟一地标识一个进程 一个进程通常分为内部标识符和外部标识符 处理机状态信息处理机状态信息主要由处理机的各种寄存器中的内容组成 24 2 1 6进程控制块 进程控制块中的信息进程调度信息主要是与进程调度有关的信息 如进程的当前状态 进程优先级和阻塞事件等 进程控制信息主要是与进程控制有关的信息 如程序和数据的地址 资源清单和链接指针等 25 2 1 6进程控制块 进程控制块的组织方式线性表方式不论进程的状态如何 将所有的PCB连续地存放在内存的系统区中 实现起来比较简单 但检索速度慢 26 2 1 6进程控制块 进程控制块的组织方式链接表方式把具有相同状态的PCB链接成一个队列 这样可形成就绪队列 若干个阻塞队列和空闲队列等 27 2 1 6进程控制块 进程控制块的组织方式链接表方式 28 2 1 6进程控制块 进程控制块的组织方式索引表方式系统根据所有进程的状态建立几张索引表 并将各索引表在内存中的首地址记录在内存中的一些专用单元中 29 2 1 6进程控制块 进程控制块的组织方式索引表方式 30 31 2 2进程控制 2 2 1进程控制概述2 2 2进程创建原语2 2 3进程撤销原语2 2 4进程阻塞原语2 2 5进程唤醒原语 2 2 1进程控制概述 进程控制的作用进程控制的作用是对系统中的全部进程实行有效的管理 其主要表现在创建 撤消进程以及完成进程各状态间的转换 进程控制是操作系统通过原语来实现的 32 2 2 1进程控制概述 原语原语是操作系统内核中由若干条机器指令构成用于完成特定功能的一个程序段 操作系统内核在执行原语时是不可分割的 即表现为原子操作 所谓原子操作就是指 一个操作中的所有动作 要么全做 要么全不做 33 2 2 2进程创建原语 进程的树型结构在OS中 允许一个进程创建另一个进程 通常把创建进程的进程称为父进程 而把被创建的进程称为子进程 34 2 2 2进程创建原语 进程创建原语的执行过程为新进程申请空闲PCB 并分配惟一的数字标识符 为新进程分配内存空间等资源 初始化PCB中的信息 标识符 处理机状态 进程状态 优先级 程序地址等 将新进程插入到就绪队列中 35 2 2 3进程撤销原语 根据被撤销进程的标识符从PCB集合中检索出该进程的PCB 从中读出该进程的状态 若被撤销进程正处于执行状态 应立即终止该进程的执行并设置调度标志为真 用于指示该进程被撤销后进程调度程序应重新进行调度 选择一新进程 把处理机分配给它 若该进程还有子孙进程 还应撤销其所有子孙进程 将该进程所拥有的全部资源 或者归还其父进程或者归还给系统 36 2 2 4进程阻塞原语 终止该进程的执行 将该进程的状态由 执行 改为 阻塞 将该进程插入到相应的阻塞队列中 转进程调度程序重新进行调度 37 2 2 5进程唤醒原语 把要唤醒的进程从相应的阻塞队列中移出 将该进程的状态由 阻塞 改为 就绪 将该进程插入到就绪队列中 38 总结 本次课主要讲授内容单道程序的顺序执行多道程序的并发执行进程的定义 进程与程序的区别进程的状态及其转换 进程控制块进程创建 撤销 阻塞和唤醒的过程 上节回顾 进程的状态及其转换 进程控制块的作用进程创建 撤销 阻塞和唤醒的过程 41 2 3线程的基本概念 2 3 1线程的引入2 3 2线程与进程的比较 2 3 1线程的引入 进程引入的原因使多个程序能够并发执行 提高系统资源的利用率和吞吐量 进程的两个基本属性进程是一个资源分配的单位 进程是一个独立调度的单位 42 2 3 1线程的引入 系统对进程进行的操作创建进程 申请PCB 分配资源 撤销进程 回收资源 撤销PCB 进程切换 保存和重新设置进程CPU环境 43 2 3 1线程的引入 进程存在的问题进程是资源的拥有者 系统在进程的创建 撤销和切换中必须付出较大的时空开销 系统中进程数目不宜太多 进程切换频率不宜太快 限制了进程并发执行程度的进一步提高 44 2 3 1线程的引入 线程的引入在引入线程的OS中 线程是进程中的一个实体 是系统独立调度的基本单位 线程基本不拥有资源 但可访问其所隶属的进程的全部资源 45 2 3 2线程与进程的比较 调度在传统的操作系统中 进程既是拥有资源的基本单位 又是独立调度的基本单位 在引入线程的操作系统中 进程只是拥有资源的基本单位 而线程则作为独立调度的基本单位 46 2 3 2线程与进程的比较 并发性传统的操作系统中 只有进程之间能够并发执行 在引入线程的操作系统中 不仅进程间可以并发执行 而且同一个进程中的多个线程间也可以并发执行 因而使系统具有更好的并发性 从而能够更有效地利用系统资源和提高系统吞吐量 47 2 3 2线程与进程的比较 拥有资源不论是传统的操作系统 还是设有线程的操作系统 进程都是系统中拥有资源的一个独立单位 线程几乎不拥有系统资源 但它可以访问其所隶属的进程的资源 48 2 3 2线程与进程的比较 系统开销创建和撤销进程时 系统要为之分配或回收资源 所以创建进程的开销远大于创建线程的开销 进程切换时 系统既要保存当前进程的CPU环境 又要设置新被调度进程的CPU环境 而线程的切换只需保存少量信息 所以进程切换的开销远大于线程切换的开销 49 总结 本次课主要讲授内容线程引入的原因线程与进程的关系线程与进程的区别 51 2 4进程同步与互斥 2 4 1互斥问题与同步问题2 4 2信号量及P V操作2 4 3用P V操作实现进程同步与互斥2 4 4经典进程同步与互斥问题 2 4 1互斥问题与同步问题 互斥问题 52 voidP1 voidP2 n n 2 4 1互斥问题与同步问题 互斥问题 53 voidP1 voidP2 Register1 n Register2 n Register1 Register1 1 Register2 Register2 1 n Register1 n Register2 2 4 1互斥问题与同步问题 互斥问题 54 在分时系统中n 100 2 4 1互斥问题与同步问题 互斥问题 重点 临界资源 在同一段时间内只允许一个进程访问的资源 临界区 指一个进程访问临界资源的那段程序代码 进程互斥 禁止两个或两个以上的进程同时进入访问同一临界资源的临界区 55 2 4 1互斥问题与同步问题 同步问题 重点 进程同步 两个或多个进程为了合作完成同一个任务 在执行顺序上必须相互协调 56 2 4 2信号量及P V操作 lock和unlock原语在这两个原语中设置一个公共变量x代表某个临界资源的状态 x 0可用 x 1不可用 进程进入临界区之前执行lock原语 退出临界区之后执行unlock原语 57 2 4 2信号量及P V操作 lock和unlock原语 58 lock x unlock x L ifx 1thenx 0 gotoL elsex 1 2 4 2信号量及P V操作 lock和unlock原语X表示变量n的使用情况 x 0表示未使用 x 1表示使用 59 P1P2 lock x lock x Register1 n Register2 n Register1 Register1 1 Register2 Register2 1 n Register1 n Register2 unlock x unlock x 2 4 2信号量及P V操作 P V操作原语 重点 信号量 一个具有非负初值的整型变量 并且有一个队列与它关联 60 2 4 2信号量及P V操作 P V操作原语 重点 61 P s V s s s 1 s s 1 if s 0 if s 0 block s l wakeup s l 1 s表示临界资源的数目 2 s l表示与临界资源s相关的阻塞队列 3 s 0时 s的绝对值表示临界资源的数目 4 s 0时 s的绝对值表示与s相关的阻塞队列中阻塞进程的数目 2 4 2信号量及P V操作 P V操作原语 重点 62 s表示临界资源变量n的数目 s 1 P1P2 P s P s Register1 n Register2 n Register1 Register1 1 Register2 Register2 1 n Register1 n Register2 V s V s 2 4 3用P V操作实现进程同步与互斥 用P V操作实现进程互斥 重点 例1 63 2 4 3用P V操作实现进程同步与互斥 用P V操作实现进程互斥 重点 例2 4个进程使用2台打印机的情况 64 2 4 3用P V操作实现进程同步与互斥 用P V操作实现进程同步 重点 例1 65 2 4 3用P V操作实现进程同步与互斥 用P V操作实现进程同步 重点 66 2 4 3用P V操作实现进程同步与互斥 用P V操作实现进程同步 重点 例2 用P V操作实现下图所示的进程同步关系 67 68 2 4 3用P V操作实现进程同步与互斥 用P V操作实现进程同步 重点 例3P1 inti j P2 i 10 P3 j i 20 69 2 4 3用P V操作实现进程同步与互斥 用P V操作实现进程同步 重点 70 2 4 4经典进程同步与互斥问题 生产者和消费者问题 重点 有一群生产者进程在生产产品 并将这些产品提供给消费者进程去消费 在生产者进程和消费者进程之间设置了一个具有n个缓冲区的缓冲池 生产者进程可将它生产的产品放入一个缓冲区中 消费者进程可从一个缓冲区取得一个产品消费 71 2 4 4经典进程同步与互斥问题 生产者和消费者问题 重点 信号量mutex 初值为1 用于实现临界区互斥 信号量empty 初值为n 指示空缓冲区数目 信号量full 初值为0 指示满缓冲区数目 整型数组buffer n 代表n个缓冲区 整型量in和out初值均为0 in指示首个空缓冲区序号 out指示首个满缓冲区序号 72 73 2 4 4经典进程同步与互斥问题 读者和写者问题 重点 一个共享的对象可以允许多个读进程同时去读 但不允许一个写进程和其他读进程或写进程同时访问该共享对象 读者和写者问题 就是保证一个写进程必须和其他进程互斥地访问共享对象的同步问题 74 75 2 4 4经典进程同步与互斥问题 哲学家进餐问题 重点 五个哲学家共用一张圆桌 在圆桌上有五个碗和五只筷子 他们的生活方式是交替的进行思考和进餐 当某个哲学家饥饿时便试图取用其左右最靠近他的筷子 只有在他拿到两只筷子时才能进餐 76 77 intchopstick 5 1 1 1 1 1 Pi while 1 P chopstick i P chopstick i 1 5 eat V chopstick i V chopstick i 1 5 think 是否存在问题 2 4 4经典进程同步与互斥问题 哲学家进餐问题 重点 解决方案一 最多只允许四个哲学家同时去拿左边的筷子 最终能保证至少有一位哲学家能够进餐 78 79 intchopstick 5 1 1 1 1 1 intmutex 4 Pi while 1 P mutex P chopstick i P chopstick i 1 5 V mutex eat V chopstick i V chopstick i 1 5 think 2 4 4经典进程同步与互斥问题 哲学家进餐问题 重点 解决方案二 规定奇数哲学家先拿起他左边的筷子 接着拿他右边的筷子 而偶数哲学家先拿起他右边的筷子 接着再拿他左边的筷子 80 81 intchopstick 5 1 1 1 1 1 Pi while 1 if i 2 1 P chopstick i P chopstick i 1 5 else P chopstick i 1 5 P chopstick i eat V chopstick i V chopstick i 1 5 think 总结 本次课主要讲授内容临界资源和临界区的概念 进程互斥和进程同步的概念 P V操作原语的定义 用P V操作原语解决进程同步与互斥的方法 上节回顾 临界资源和临界区的概念 进程互斥和进程同步的概念 P V操作原语的定义 用P V操作原语解决进程同步与互斥的方法 经典进程同步互斥问题 84 2 5进程调度 2 5 1进程调度的基本概念2 5 2进程调度的功能和原因2 5 3进程调度算法 2 5 1进程调度的基本概念 进程调度的定义 重点 进程调度也称为处理机调度 它决定将处理机分配给就绪队列里的某个进程 并使之运行 从而协调和控制各进程对处理机的使用 执行处理机调度的程序称为进程调度程序 85 2 5 1进程调度的基本概念 进程调度的方式 重点 非剥夺方式 进程调度程序一旦把处理机分配给某个进程后 便让该进程一直执行 直到该进程运行完毕或发生某事件而阻塞时 才把处理机分配给另一个进程 剥夺方式 当一个进程正在运行时 系统可以基于某种原则 暂停该进程的执行 将分配给它的处理机重新分配给另一进程 86 2 5 2进程调度的功能和原因 进程调度的功能记录系统中所有进程的执行情况 选择进程占用处理机 进行进程的上下文切换 87 2 5 2进程调度的功能和原因 进程调度的原因正在执行的进程执行完毕 正在执行的进程提出I O请求后被阻塞 执行中的进程调用了P V原语操作 在剥夺调度方式中 当就绪队列中的某进程的优先级高于当前执行进程的优先级 在分时系统中时间片已经用完 88 2 5 3进程调度算法 进程调度性能的衡量指标 重点 周转时间T周转时间 T完成时间 T提交时间平均周转时间J T周转时间 N平均带权周转时间W T周转时间 T运行时间 N一般J W越小 系统对进程的吞吐量越大 系统的性能越高 89 2 5 3进程调度算法 先来先服务调度算法 重点 先来先服务 FCFS 算法以进程到达就绪队列的先后次序为标准来选择占用处理机的进程 优点 实现简单 缺点 有利于长进程 CPU繁忙型进程 而不利于短进程 I O繁忙型进程 90 2 5 3进程调度算法 先来先服务调度算法 重点 91 2 5 3进程调度算法 先来先服务调度算法 重点 J 2 00 2 90 3 00 3 2 63W 2 00 2 2 90 1 3 00 0 25 3 5 30 92 2 5 3进程调度算法 短进程优先调度算法 重点 短进程优先 SPF 调度算法 是从就绪队列中选择一运行时间最短的进程 将处理机分配给它 优点 有利于短进程 缺点 不利于长进程 93 2 5 3进程调度算法 短进程优先调度算法 重点 94 2 5 3进程调度算法 短进程优先调度算法 重点 J 2 00 3 15 2 00 3 2 38W 2 00 2 3 15 1 2 00 0 25 3 4 05 95 2 5 3进程调度算法 优先级调度算法该算法是指当发生进程调度时 将CPU分配给就绪队列中优先级最高的进程 进程优先级分为静态优先级和动态优先级 96 2 5 3进程调度算法 优先级调度算法静态优先级在进程创建时确定的 且在进程的整个运行期间保持不变 优点 简单 系统开销少 缺点 不能动态反应进程的情况 系统调度性差 97 2 5 3进程调度算法 优先级调度算法动态优先级 重点 在创建进程时所赋予的优先级 是可以随进程的执行或随其等待时间的增加而改变的 以便获得更好的调度性能 98 2 5 3进程调度算法 优先级调度算法动态优先级 重点 99 2 5 3进程调度算法 优先级调度算法动态优先级 重点 J 2 00 2 1 1 10 1 30 4 1 625W 2 00 2 2 1 0 5 1 10 0 1 1 30 0 2 4 5 675 100 2 5 3进程调度算法 时间片轮转调度算法 重点 该算法是将CPU的处理时间分成固定大小的时间片 优先分配给就绪队列的第一个进程 当运行进程用完规定的时间片时 被迫释放CPU给下一个就绪队列中的第一个进程 时间片大小的设定是一个影响系统效率的重要因素 太长用户进程不能及时得到相应 太短增加调度开销 降低效率 101 2 5 3进程调度算法 时间片轮转调度算法 重点 系统的响应时间和时间片的关系为 T N qT 系统的响应时间 q 时间片的大小 N 就绪队列中进程的数目 102 2 5 3进程调度算法 多级反馈队列调度算法多级反馈队列调度算法是时间片轮转调度算法与优先级调度算法的结合 实行该算法时 系统将设置多个就绪队列 每个就绪队列具有不同的调度优先级 可以获得不同长度的时间片 103 2 5 3进程调度算法 多级反馈队列调度算法 104 总结 本次课主要讲授内容进程调度的概念 进程调度的两种方式 进程调度的功能与原因进程调度的算法 上节回顾 进程调度的概念 进程调度的两种方式 进程调度的功能与原因进程调度的算法 107 2 6死锁 2 6 1死锁的概念2 6 2死锁产生的原因和必要条件2 6 3预防死锁的方法2 6 4避免死锁的方法2 6 5检测死锁的方法2 6 6解除死锁的方法 2 6 1死锁的概念 引例若当前系统中就有1台打印机和1台磁带机 108 进程P1进程P2 申请打印机P申请磁带机Tr1 申请磁带机Tr2 申请打印机P 释放磁带机T释放打印机P释放打印机P释放磁带机T 2 6 1死锁的概念 引例若当前系统中就有1台打印机和1台磁带机 109 2 6 1死锁的概念 死锁的概念 重点 死锁是指多个进程因竞争资源而造成的一种僵局 若无外力作用 这些进程将永远不能再向前推进 110 2 6 2死锁产生的原因和必要条件 死锁产生的原因 重点 竞争资源 进程推进顺序不当 111 2 6 2死锁产生的原因和必要条件 死锁产生的必要条件 重点 互斥条件进程对所需要的资源进行互斥地使用 即在一段时间内某资源只能由一个进程使用 请求和保持条件当进程因请求资源而阻塞时 对已获得的资源保持不放 112 2 6 2死锁产生的原因和必要条件 死锁产生的必要条件 重点 不剥夺条件进程所获得的资源在未使用完之前 不能被其他进程强行剥夺 只能使用完自己释放 环路等待条件存在一种进程循环链 链中每一个进程已获得的资源同时被下一个进程所请求 113 2 6 3预防死锁的方法 保证在任何时刻产生死锁的四个必要条件中至少一个不能成立 就可以起到预防死锁的目的 114 2 6 3预防死锁的方法 破坏 请求和保持条件 方法 系统要求所有进程在运行前一次性地申请其所需的全部资源 只要有一个资源申请不到就不能运行 优点 简单 安全 易于实现 缺点 资源浪费严重 进程运行延迟 115 2 6 3预防死锁的方法 破坏 不剥夺条件 方法 一个已经获得了某些资源的进程 若新的资源请求不能立即得到满足 它必须释放其已占有的所有资源 以后再需要时重新申请 缺点 实现较复杂 系统开销大 116 2 6 3预防死锁的方法 破坏 环路等待条件 方法 将系统中的所有资源按类型进行线性排队 并赋予不同的序号 所有进程只能严格按照序号递增的顺序去请求资源 优点 利用率和吞吐量都有较明显的改善 缺点 限制了新类型设备的增加 限制了用户编程 117 2 6 4避免死锁的方法 避免死锁的含义避免死锁是指系统采用动态分配资源的策略 保证系统不进入可能导致系统陷入死锁状态的所谓不安全状态 以避免死锁的发生 118 2 6 4避免死锁的方法 安全状态 重点 安全状态是指系统能按某种进程推进顺序 P1 P2 Pn 为每个进程Pi分配其所需资源 直至满足每个进程对资源的最大需求 使每个进程都可顺利地完成 此时称 P1 P2 Pn 为安全序列 注意 系统在某一时刻的安全序列不唯一 如果系统无法找到这样一个安全序列 则称系统处于不安全状态 119 2 6 4避免死锁的方法 安全状态例 假定系统中有三个进程P1 P2和P3 共有12台磁带机 资源分配情况如下表所示 此时系统是否安全 此时存在一个安全序列P2 P1 P3 即系统是安全的 120 2 6 4避免死锁的方法 银行家算法 重点 1 银行家算法中的数据结构可利用资源向量Available 是一个含有m个元素的数组 Available j K表示系统中现有Rj类资源K个 最大需求矩阵Max 是一个n m的矩阵 Max i j K表示进程i需要Rj类资源的最大数目为K 121 2 6 4避免死锁的方法 银行家算法 重点 1 银行家算法中的数据结构分配矩阵Allocation 是一个n m的矩阵 Allocation i j K表示进程i当前已分得Rj类资源的数目为K 需求矩阵Need 是一个n m的矩阵 Need i j K表示进程i还需要Rj类资源K个 方能完成其任务 122 2 6 4避免死锁的方法 银行家算法 重点 1 银行家算法中的数据结构 123 2 6 4避免死锁的方法 银行家算法 重点 2 银行家算法描述如果Requesti j Need i j 则跳转到第2步 否则认为出错 因为进程Pi已经超过了它的最大需求量 如果Requesti j Available j 则跳转到第3步 否则Pi必须等待 因为没有足够的资源 124 2 6 4避免死锁的方法 银行家算法 重点 2 银行家算法描述假定系统可以分配给进程Pi所请求的资源 并按如下方式修改数据结构中数值 Available j Available j Requesti j Allocation i j Allocation i j Requesti j Need i j Need i j Requesti j 125 2 6 4避免死锁的方法 银行家算法 重点 2 银行家算法描述P2发出资源请求Request2 1 0 1 系统能否将资源分配给它 126 2 6 4避免死锁的方法 银行家算法 重点 2 银行家算法描述系统执行安全性算法 检查此次资源分配后 系统是否处于安全状态 若安全 才正式将资源分配给进程Pi 以完成本次分配 否则 将本次的试探分配作废 恢复原来的资源分配状态 让进程Pi等待 127 2 6 4避免死锁的方法 银行家算法 重点 3 安全性算法设置2个向量 工作向量Work 它表示系统可提供给进程继续运行所需的各类资源数目 执行安全性算法时 Work Available 判断向量Finish 它表示系统是否有足够的资源分配给进程使之运行完成 开始时Finish i 0 当有足够资源分配给进程时 令Finish i 1 128 2 6 4避免死锁的方法 银行家算法 重点 3 安全性算法从进程集合中找出一个能满足下列条件的进程 Finish i 0 Need i j Work j 若找到 则执行步骤 否则执行步骤 129 2 6 4避免死锁的方法 银行家算法 重点 3 安全性算法当进程Pi获得资源后 便可顺利执行 直到运行完毕释放分配给它的资源 故应执行 Work j Work j Allocation i j Finish i 1 gotostep2 130 2 6 4