操作系统原理及应用（Linux）（第二版） -王红 第3章 处理机调度与死锁.ppt

第3章 处理机调度与死锁 教学内容 3.1 作业管理 3.2分级调度 3.3作业调度 3.4 进程调度 3.5 调度算法 3.6 LINUX系统的调度算法 3.7 死锁问题 3.8 死锁的预防 3.9 死锁的避免 3.10 利用银行家算法避免死锁 3.11 死锁的检测与解除 3.1.1 作业的概念 1．作业 3.2 分级调度 2．对换 3．进程调度 3.3 作业调度 3.3.1 作业调度的功能 3.3.2 调度算法的评价及准则 1．面向用户的准则 2．面向系统的准则 （２）响应时间快 2．面向系统的准则 3.4 进程调度 3.4.2 进程调度的时机 3.4.3 进程上下文的切换 3.4.4 Linux系统中进程调度发生的时机 3.5 调度算法 3.5.3 ．高响应比优先调度算法 3.5.4 优先级调度算法 解： （1）各作业进入时间和结束时间如下： 3.5.5 时间片轮转法 3.5.6 多级队列调度算法 3.5.7多级反馈队列调度算法 2．多级反馈队列调度算法的几点说明 3.6 Linux系统的调度算法 3.6.1 Linux系统的进程调度策略 3.6.2 Linux系统的优先级调度策略 3.6.3 实时进程的调度策略 3.7 死锁问题 3.7.2 产生死锁的原因及必要条件 （2）进程推进顺序不当 2．死锁产生的必要条件 （2）占有且申请条件 （4）环路条件 3.7.3 解决死锁问题的基本方法 3．死锁的检测 4．死锁的解除 3.8 死锁的预防 3.9 死锁的避免 3.9.1 系统的安全状态 3.9.2 由安全状态向不安全状态的转化 3.9.3 银行家算法 3.10 利用银行家算法避免死锁 3.10.2 银行家算法的实现 2．银行家算法的描述 3．安全性算法 安全算法的步骤： 3.10.3 银行家算法的应用 3.11 死锁的检测与解除 3.11.1 死锁检测的时机 3.11.2 死锁的检测 2．资源分配图的简化 4．死锁检测中的算法 3.11.3 死锁的解除 1．终止进程 2．抢占资源 本章小结 例5：有三个客户C1，C2，C3，向银行家贷款。该银行家的资金总额为10个资金单位，其中C1客户要借9个资金单位，C2客户要借3个资金单位，C3客户要借8个资金单位，总计20个资金单位。这时，客户占用及还需资源的状态如下图所示，银行家该如何分配资金？ 4 4 C3 1 2 C2 7 2 C1 还需申请资源 已分配资源 客户 第 3章 处理机调度与死锁 * 剩余的资源单位数是10-（2+2+4）=2。故，此时银行家只有将资金分配给C2，才能最终收回贷款。然后，再将资金依次分配给C3和C1，这样银行家能最终收回所有的贷款。这里就存在一个安全序列，即：{C2，C3，C1}。我们说此时系统是安全的。 第 3章 处理机调度与死锁 * 如果不按照安全序列的顺序分配资源，则系统可能由安全状态进入不安全状态。例如：若在T0时刻以后，C3又申请到2个资金单位，则系统进入不安全状态。因为，此时无法再找到一个安全序列，结果造成系统产生死锁。由此可见，当C3申请资源时，尽管当时系统中还有可用资源，但却不能分配给它，必须让它等待。按银行家的术语说，某客户若无偿还能力时，就不要贷款给它。 第 3章 处理机调度与死锁 * 银行家对当前顾客的贷款操作进行判断，以确定其安全性。看能否支持顾客贷款，即该客户能否运行完成。 安全时，贷款；否则，暂不贷款。 第 3章 处理机调度与死锁 * 3.10.1 银行家算法中的数据结构 1．可利用资源向量Available。 也称为空闲向量。这是一个含有m个元素的数组。其中的每一个元素，代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目。其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。 2．最大需求矩阵Max。 这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示第i个进程需要Rj类资源的最大数目为K。  第 3章 处理机调度与死锁 * 3．分配矩阵Allocation。 也叫做占有矩阵。这也是一个n×m的矩阵，它定义了系统中每一进程已占有的每一类资源数。如果Allocation[i,j]=K，则表示第i个进程当前已分得Rj类资源的数目为K。 4．需求矩阵Need也叫做申请矩阵。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示第i个进程还需要Rj类资源K个，才能完成其任务。 显然，以上三个矩阵