第章 处理机调度与死锁新.ppt

第3章 处理机调度与死锁 教学内容 3.1 处理机调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 3.1 处理机调度的层次 一个作业从用户提交后驻留在外存设备开始，直到作业运行结束，可能要经历多级调度才能实现。 高级调度（作业调度） 低级调度（进程调度） 中级调度（交换） 3.1.1 高级调度 3.1.1 高级调度 3.1.1 高级调度 3.1.2 低级调度 2.进程调度方式 3.进程调度功能 3.1.3 中级调度 3.2 调度队列模型和调度准则 3.2.2 调度算法的评价及准则 1．面向用户的准则 2．面向系统的准则 （２）响应时间快（评价分时系统性能的准则） 2．面向系统的准则 3.3 调度算法 3.3.2 高优先级优先调度算法 3．高响应比优先调度算法（HRN） 3.3.3 基于时间片的轮转调度算法 思想： 该算法为每个进程分配一个时间片。如果在时间片一到，即进程还没有运行完，也要让出CPU。如果进程在时间片还没结束之前阻塞或结束，则CPU当即进行切换。 3.3.3 基于时间片的轮转调度算法 思想： 该算法设立了优先级类。其原则是优先级越高的进程，时间片越少，优先级越低的进程，时间片越多。 同时当一个进程用完其时间片的时候，被移到下一级类。 这种算法较好地实现了进程调度的公平性与系统资源利用率之间的平衡。 3.5 产生死锁的原因和必要条件 3.5.1 产生死锁的原因及必要条件 3.5.2．死锁产生的必要条件 （2）占有且申请条件 （4）环路条件 3.5.3 解决死锁问题的基本方法 3．死锁的检测 4．死锁的解除 3.6 预防死锁的方法 3.6.1 预防死锁 死锁的避免 3.6.2 系统的安全状态 3.6.2 系统的安全状态 安全状态例 由安全状态向不安全状态的转化 课堂练习 3.6.3 银行家算法 基本思想： 利用银行家算法避免死锁 银行家算法的实现 2．银行家算法的描述 3．安全性算法 安全算法的步骤： （1）T0时刻是否为安全状态？若是，给出安全序列。 （2）若在T0时刻进程P2请求资源（0，3，4），是否能实施资源分配？为什么？ （3）在（2）的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？ 银行家算法的应用 3.7 死锁的检测与解除 死锁检测的时机 死锁的检测 2．资源分配图的简化 4．死锁检测中的算法 死锁的解除 1．撤销进程 2．剥夺资源 习题 习题 习题 （1）T0时刻是否为安全状态？若是，给出安全序列。 （2）若在T0时刻进程P2请求资源（0，3，4），是否能实施资源分配？为什么？ 习题 设系统中有3中类型的资源（A,B,C）和5个进程P0、P1、P2、P3、P4，A类资源的数目为10，B类资源的数目为5，C类资源的数目为7。在T0时刻系统状态如下表所示。系统采用银行家算法实施死锁避免策略。 4 3 1 4 3 3 P4 0 1 1 2 2 2 P3 6 0 0 9 0 2 P2 1 2 2 3 2 2 P1 3 3 2 7 4 3 7 5 3 P0 Available A B C Need A B C Max A B C Allocation A B C 0 1 0 2 0 0 3 0 2 2 1 1 0 0 2 （1）T0时刻是否安全？ （2）P1请求资源，发出请求向量Request1(1,0,2，能否分配给它？ （3）之后，若P4又发出资源请求向量Request4（3，3，0），能否分配给它？ （4）P0发出请求向量Request0(0,2,0），能否分配给它？ 第 3章 处理机调度与死锁 * P1申请向量进行银行家算法检查后，此时还需要对其进行安全性检查： 4 3 1 4 3 3 P4 0 1 1 2 2 2 P3 6 0 0 9 0 2 P2 0 2 0 3 2 2 P1 2 3 0 7 4 3 7 5 3 P0 Available A B C