第三章—a处理机调度

( Scheduling and Deadlock )第三章 处理机调度与死锁在多道程序系统中，一个作业从提交到执行完成，要经历 多级调度 ，调度的好坏要影响系统的运行性能，因此调度是多道系统的关键。为了改善系统 资源 的利用率和提高系统处理能力，多道程序系统中采用多个进程的并发执行， 但它也可能发生死锁的危险，研究死锁的原因和产生条件，采用 预防死锁 、 避免死锁 、 检测死锁 和 解除死锁 等多种方法防止死锁是多道程序系统重要的研究课题。 熟悉 处理机三级调度 概念和 处理机调度模型 ，掌握作业的状态和作业 调度的功能。 掌握进程调度的方式和功能， 熟悉 调度方式 和 算法的选择准则 ， 掌握七种 调度算法及适合范围。 掌握 死锁的定义和产生死锁的原因， 掌握 死锁的四个必要条件 ； 熟悉 预防死锁的方法，熟练掌握银行家算法及其在死锁避免中的应用；掌握资源分配图的简化及其死锁定理， 熟悉 解除死锁的方法。本章要求几种 OS的简单回顾 批处理操作系统 多道程序设计系统 分时系统 实时系统 作业和进程的关系 作业 是用户需要计算机完成某项任务时要求计算机所做的工作的集合。 作业的完成要经过作业提交、作业后备、作业执行和作业完成四个阶段。 进程 是对已提交完毕程序的 执行过程 的描述，是 资源分配的基本单位 。（ 1）作业是用户向计算机 提交任务的实体 ，而进程是 完成用户任务的实体 ； （ 2）一个作业可由 多个进程组成 ，且必须 至少由一个进程组成 。（ 3）作业的概念主要用在 批处理操作系统中 ，而进程的概念则 几乎用在所有的多道程序操作系统中。 提交状态 ：一个作业在其处于输入设备进入外部存储设备的过程称为提交状态 后备状态（收容状态） ：输入管理系统不断地将作业输入到外存对应部分（或称输入井），如果一个作业的全部信息已全部输入到输入井，在它还没有被调度去执行前，该作业处于后备状态。 运行状态 ：作业一旦被作用调度程序选中而被送入主存中投入运行。 完成状态 ：作业运行完毕，但它所占用的资源尚未被系统全部回收时，该作业处于完成状态作业状态及其转换图 spooling系统提交 收容 外存就绪 等待 运行就绪 等待交换调度完成作业调度进程调度3.1处理机调度的层次 引言处理机调度的主要目的：分配处理机调度影响的因素：响应的及时性进程是否能在限定时间内获得处理机，对用户进行响应周转时间（等待时间 +使用 CPU时间）进程是否等待时间太长系统吞吐量CPU是否总是用在刀刃上调度类型 调度的类型与模型 1.调度类型从调度层次：高级调度低级调度中级调度从 OS类型：批处理、分时、实时、多处理机调度 （ 1）高级调度作业调度或长程调度对象：外存上后备队列中的作业动作：调入内存、创建进程 、分配资源、新进程进入就绪队列决策内容：接纳作业量、作业类型其它其它作业成批进入作业成批进入输入井输入井 输出井输出井内存内存 CPU高级调度高级调度3.1.1 高级调度高级调度 （作业调度、长程调度） 按一定原则对外存输入井上的作业进行调度，并 建立进程 PCB。它决定允许哪些作业竞争系统资源。由于这种调度决定哪些作业可以进入系统，所以也称 收容调度 。作业一旦被系统收容，就形成进程。为了管理和调度作业，在多道处理系统中为每个作业设置一个 作业控制块 （ JCB）。l所做的工作： 1 选择作业； 2 分配资源；3 建立作业的进程； 4 建立有关的表格 5 作业的善后处理。3.1.2低级 调度（进程调度 或 短程调度）对象：就绪队列中的进程动作：决定由哪个进程获得 CPU调度方式：非抢占式抢占式 低级调度低级调度进程并发执行进程并发执行其它其它作业成批进入作业成批进入输入井输入井 输出井输出井内存内存 CPU高级调度高级调度低级调度 （进程调度 /短程调度）它决定了存在就绪进程时，哪一个就绪进程将分配到中央处理机，并且把中央处理机实际分配给这个进程（即低级调度是将处理机分配给进程）。低级调度是由每秒可操作许多次的处理机调度程序执行， 处理机调度程序应常驻内存 。进程调度方式 进程调度的方式非抢占式（非剥夺式）现运行进程的 CPU使用权不能被中途强行剥夺除非进程主动放弃抢占式（剥夺式）系统按照某种原则剥夺现行进程的 CPU使用权将 CPU使用权分配给其他进程抢占原则优先权原则时间片原则短进程优先原则进程调度过程 进程调度对象：就绪队列中的进程 进程调度功能及过程记录当前进程的状态、保存 CPU现场选取适当的就绪进程进程调度算法分配处理机：恢复选取进程的 现场CPU就绪队列交互用户 123进程调度进程调度时机（调度时刻）阻塞队列阻塞队列交互用户阻塞阻塞进程调度进程调度就绪队列就绪队列结束结束时间片完时间片完唤醒唤醒现进程运行完毕现进程运行完毕现进程阻塞现进程阻塞优先权高的进程进入就绪队列优先权高的进程进入就绪队列现进程现进程 “超时超时 ”/被中断被中断CPU3.1.3 中级（ Medium-term） 调度 中级调度 中程调度对象：外存中因暂时不能运行而被挂起的进程动作：将外存挂起的进程激活，调入内存，进入就绪队列目的：提高内存利用率和系统吞吐量处理机三级调度中级调度 （中程调度）它决定 允许哪些进程竞争处理机 。中级调度通过使进程临时挂起和激活的方法对系统负载波动作出反映，以便获得平稳的系统操作和实现较好的系统综合性能目标， 中级调度的作用使作为作业进入系统和将中央处理机分配给这些作业二者之间的一个缓冲 。引入中级调度的目的是为了提高 内存的利用率 和 系统吞吐量 。处理机三级调度图：作业调度 作业运行状态外存 (盘 )交换区作业后备状态作业提交状态 作业 完成状态终止 作业就绪态阻塞态主存进程调度 运行态就绪态阻塞态外存中级调度作业是用户向计算机 提交任务的任务实体 。进程是计算机为了 完成用户任务实体而设置的执行实体 。显然，计算机要完成一个任务实体，必须要有一个以上的执行实体， 一个作业总是由一个以上的多个进程组成 。作业与进程的关系作业调度和进程调度的区别 作业调度为进程活动做准备，进程调度使进程活跃起来。 作业调度次数少，进程调度频繁。 有的系统可以 无作业调度，但进程调度必不可少。3. 2调度队列模型和调度准则1.仅有进程调度的调度队列模型在分时系统中通常仅设置了进程调度。此时系统有一个就绪队列，每个进程运行一个时间片，进程运行 一个时间片后如未完成 ，则 被放在就绪队列末尾 。如进程运行中因等待某事件（例如申请 I/O而等待 I/O完成），则需 排入阻塞队列 ，系统因阻塞的原因不同可设几个阻塞队列。1.单级调度队列模型（仅有进程调度）阻塞队列阻塞队列交互用户阻塞阻塞进程调度是最基本的调度，进程调度是最基本的调度，必须配置必须配置CPU进程调度进程调度就绪队列就绪队列结束结束时间片完时间片完 /被中断被中断唤醒唤醒2.具有高级调度和低级调度的调度队列模型在多道批处理系统中，一般处理机管理设置作业和进程两级调度 。它比第一个模型增加了高级调度。模型增加了在磁盘的作业后备队列，作业调度的任务是 从作业后备队列中选一个作业为它创建至少一个进程 ，并分配资源，将它排入内存进程就绪队列末尾。2.二级调度队列模型（作业、进程调度）CPU就绪队列就绪队列阻塞队列阻塞队列时间片完时间片完阻塞阻塞唤醒唤醒进程调度进程调度后备队列后备队列作业调度作业调度在批处理或类似系统中需要从外存后备队列中调入作业3.同时具有三级调度的调度队列模型在通用系统的多模式 OS中，一般采用具有三级调度的调度队列模型，由于多模式OS同时支持批处理、分时和实时处理，所以它必须具有以上模型，具有三级调度的调度队列模型如图所示：CPU就绪队列就绪队列阻塞队列阻塞队列时间片完时间片完阻塞阻塞唤醒唤醒后备队列后备队列 挂起挂起挂起挂起事件出现事件出现外存阻塞队列外存阻塞队列外存就绪队列外存就绪队列配置中级配置中级调度机制调度机制可以提高可以提高内存利用率内存利用率进程调度进程调度作业调度作业调度中级中级调度调度从多个目标（就绪进程）中选取一个进程投入运行准则面向用户面向用户面向系统面向系统周转时间周转时间响应时间响应时间截止时间截止时间优先权优先权系统吞吐量系统吞吐量处理机利用率处理机利用率各类资源的利用各类资源的利用短短快快保证保证可设置可设置大大高高平衡平衡3.2.2 调度方式和算法的选择准则3.2.2 调度方式和算法的选择准则1.面向用户的准则和评价（ 周转时间短 :（ 它是评价批处理系统的重要性能指标。作业周转时间 Ti是指从作业提交给系统开始，到作业完成为止的这段时间间隔。平均周转时间 T = 1/n 平均带权周转时间 W = 1/n 一个作业的带权周转时间 Wi=Ti/Tsi（作业的周转时间 Ti/实际服务时间 Tsi） （ 响应时间快响应时间是评价分时系统的性能指标。响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。 调度方式和算法的选择准则 -1 截止时间的保证它是用来评价实时系统的重要指标，截止时间是某任务必须执行的最迟时间，或完成的最迟时间。（ 优先权准则在选择