操作系统4.处理机.ppt

四、处理机;处理机调度和反死锁策略;处理机调度的层次;处理机调度算法的共同目标;批处理系统的目标;分时系统的目标;实时系统的目标;处理机调度和反死锁策略;批处理系统中的作业及调度;批处理系统中的作业及调度;批处理系统中的作业及调度;先来先服务调度算法（FCFS）;短作业优先调度算法（SJF）;优先级调度算法;高响应比优先调度算法 ;处理机调度和反死锁策略;进程调度的目的;进程调度的任务;进程调度机制;进程调度机制;进程调度方式;进程调度方式;下一个最短CPU区间算法;CPU区间长度估算;下一个最短CPU区间算法;轮转调度算法;轮转调度算法;轮转调度算法;q=1时，进程执行顺序ABCDEABCDEABCEACE;优先级调度算法;优先级调度算法;多级队列调度算法（静态优先级）;多级反馈队列调度算法（动态优先级）;基于公平原则的调度算法;多处理器调度;亲和性与负载平衡;超线程技术(Hyper-Threading);处理机调度和反死锁策略;实现实时调度的基本条件;实现实时调度的基本条件;实时调度算法的分类;非抢占式调度算法;抢占式调度算法;实时调度算法的分类;最早截止时间优先算法;最早截止时间优先算法;最低松弛度优先算法;最低松弛度优先算法;优先级倒置;优先级倒置：例子;优先级倒置的解决方法;处理机调度和反死锁策略;可重用资源和消耗性资源;可重用资源和消耗性资源;可抢占资源和不可抢占资源;死锁;死锁;产生死锁的必要条件;处理死锁的方法;处理死锁的方法;处理机调度和反死锁策略;破坏“请求和保持”条件;破坏“请求和保持”条件;破坏“不可抢占”条件;破坏“循环等待”条件;处理机调度和反死锁策略;系统安全状态;系统安全状态;利用银行家算法避免死锁;银行家算法;安全检查算法;银行家算法案例;1、T0时刻的资源分配情况;1、T0时刻的安全性;2、 P1请求Request1(1,0,2);2、 P1请求Request1(1,0,2);3、P4请求Request4(3,3,0);4、P0请求Request0(0,2,0);4、P0请求Request0(0,2,0);处理机调度和反死锁策略;死锁检测;资源分配图;资源分配图;死锁定理;资源分配图简化方法;资源分配图简化方法;资源分配图简化方法;资源分配图简化方法;死锁检测中的数据结构;死锁检测的方法;死锁检测的方法;死锁解除;终止进程的方法;付出代价最小的死锁解除算法;作业;设n个进程的处理顺序是P1、P2、…、Pn，执行时间是t1、t2、…、tn，进程的平均完成时间为 若进程不全按短作业优先原则，即存在Pj和Pk进程，满足jk且tjtk，则将Pj和Pk进程的交换，形成新的处理顺序P1、…、Pj-1、Pk 、Pj+1 …、Pk-1、Pj 、Pk+1、…、Pn ，进程的平均完成时间为;两个周期任务平均每秒运算次数L=n1/m1+n2/m2 ，设 For i=0 to k //i表示第一种CPU数量 //j表示第二种CPU数量 c=c1*i+c2*j //c表示总成本 将最小的c对应的i和j作为第一种和第二种CPU的配置数量;P1、P3、P4、P2、P0;对于进程P1、P2、…、Pn，若资源分配图的两种简化方法涉及的进程（Pj1、Pj2、…、Pjm）相同，仅简化的顺序不同。由于资源简化的方法是将与进程节点有关的边都删除形成孤立节点，与执行顺序无关。资源分配图的初始值相同，故简化后也相同。 若方法一与方法二涉及不同的进程，不妨设方法一中有Pjk进程，而方法二中没有，则将Pjk进程补到方法二最后一个进程后。方法一在处理Pjk进程时仅回收了Pj1、Pj2、…、Pjk-1的资源，而方法二已回收了除Pjk外Pj1、Pj2、…、Pjm的资源，故有足够资源供Pjk完成，因此方法二不是不可简化图，与已知矛盾。 不同的简化方法涉及的进程相同，顺序可能不同，故得到相同的不可简化图。;若资源分配图可完全简化，则必然存在一个简化顺序P1、P2、…、Pn ，该顺序即为进程能够顺序执行完毕的一种方法。故存在死锁时，资源分配图是不可完全简化的。 同理，当进程能够顺序执行完毕时，必然存在一个执行顺序P1、P2、…、Pn ，该顺序即为资源分配图的完全简化顺序。故若资源分配图是不可完全简化的，则存在死锁。;将空集以及对应的代价0作为第一个元素放入队列中 循环执行 取队列首个元素A 若终止A中进程可解除死锁状态，则退出循环，A包含的进程为需终止进程，对应最小代价 分别在A中添加一个不在A中的其他进程，计算代价，并根据代价大小，与队列中已有的元素按从小到大的顺序排序，重新放入队列中