操作系统-第四章.ppt

第四章调度与死锁4.1调度的类型和模型4.2调度算法4.3实时系统中的调度4.4多处理机调度4.6死锁的基本概念4.7死锁的预防和避免4.8死锁的检测和解除4.1调度的类型和模型在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。进程调度要解决的问题WHAT：按什么原则分配CPU—进程调度算法WHEN：何时分配CPU—进程调度的时机HOW：如何分配CPU—CPU调度过程（进程的上下文切换）1.高级、中级和低级调度处理机是计算机系统中的重要资源处理机调度算法对整个计算机系统的综合性能指标有重要影响可把处理机调度分成三个层次：高级调度中级调度低级调度高级调度也称为作业调度或宏观调度高级调度的时间尺度通常是分钟、小时或天中级调度涉及进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问低级调度也称微观调度，从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效2.进程调度的任务进程调度的任务是控制协调进程对CPU的竞争,即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程3.确定算法的原则具有公平性资源利用率高（特别是CPU利用率）在交互式系统情况下要追求响应时间（越短越好）在批处理系统情况下要追求系统吞吐量4.进程调度方式非剥夺方式：分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。剥夺方式：当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程优先原则、时间片原则。5.进程调度模型1)只有进程调度的调度队列模型2)具有高低级调度的调度队列模型3)具有三级调度的调度队列模型6.选择进程调度方式的准则面向用户的准则：周转时间短；响应时间快；截止时间的保证；优先权准则面向系统的准则：系统吞吐量高；处理机利用率好；各类资源的平衡利用7、几个概念周转时间T：是指作业提交给系统开始，到作业完成为止的这段时间间隔。平均周转时间：带权周转时间W：作业的周转时间与系统为它提供的实际服务时间之比。平均带权周转时间：响应时间：是指用户通过键盘提交一个请求开始，直到系统首次产生响应为止的时间间隔或屏幕上显示出结果为止的一段时间间隔。4.2进程调度算法先进先出(FIFO)算法最短CPU运行期优先调度算法最高优先权优先调度算法轮转法1.先进先出(FIFO)算法该算法总是把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便执行下去，直到该进程完成或阻塞时，才释放处理机。优点:实现简单.缺点:没考虑进程的优先级2.最短CPU运行期优先调度算法该算法从就绪队列中选出“下一个CPU执行期”最短的进程，为之分配处理机。该算法虽可获得较好的调度性能，但难以准确地知道下一个CPU执行期，而只能根据每一个进行的执行历史来预测。4.最高优先权优先调度算法该算法总是把处理机分配给就绪队列中具有最高优先权的进程。常用以下两种方法来确定进程的优先权(优先级根据优先数来决定)静态优先数法：静态优先权是在创建进程时确定的，在整个运行期间不再改变。依据有：进程类型、进程对资源的要求、用户要求的优先权。动态优先数法：在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变6.轮转法把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行简单轮转法：系统将所有就绪进程按FIFO规则排队，按一定的时间间隔把处理机分配给队列中的进程。这样，就绪队列中所有进程均可获得一个时间片的处理机而运行。多级队列方法：将系统中所有进程分成若干类，每类为一级。7.分时系统中常用时间片轮转法时间片选择问题：固定时间片可变时间片与时间片大小有关的因素：