搜索
2020/1/201计算机操作系统第三章处理机调度与死锁2020/1/2022009年2个选择（调度、死锁各占1个）2010年1个选择（调度）2011年2个选择（调度、银行家算法）2012年3个选择（调度、银行家算法）2013年2个选择(调度、银行家算法)处理机调度部分是操作系统对CPU的管理，这部分要求考生理解作业和进程的关系，掌握作业调度和进程调度的策略和算法，重点要掌握几种典型的调度算法的基本思想、适用的范围和特点，要能指出各种调度算法的调度顺序并能计算它们的周转时间。•调度算法的难点在于计算不同调度算法下调度的效率，建议使用时间轴（甘特图Gantt）的方法解决相关的调度时间计算问题。•银行家算法是系统进行资源分配的时候防止发生死锁的一种方法，该算法的难点在于搞清楚各种不同表格的含义，能够看懂并且会做出相关的表格，由表格推出结果。2020/1/203本章目录3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度(略)3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除基础要点练习题常见知识分析实战练习2020/1/204第三章处理机调度与死锁3.1处理机调度的层次1、高级调度：作业调度、长程调度、接纳调度。目标是把外存上在于后备队列中的那些作业调入内存。调度对象是作业。1)作业和作业步(1)作业：包括程序、数据和作业说明书。批处理系统中以作业为单位，从外存调入内存。(2)作业步：每个作业必须经过若干个相对独立、又相互关联的加工步骤才能得到结果。每个加工步骤称为一个作业步，各作业步是相互联系的。典型的作业分三步走：编译、链接装配和运行。(3)作业流：作业后备队列。2020/1/2052)作业控制块JCB：系统为每个作业设置一个JCB，是作业在系统中存在的标志：作业标识、用户名称、用户帐号、作业类型、作业状态、调度信息、资源需求、资源使用等。作业到达系统，由作业注册程序为作业建立JCB，根据作业类型放到相应的后备队列中3)作业调度：由作业调度程序根据JCB中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法调度它们。创建进程、分配必要的资源。接纳调度。2020/1/2064）作业运行的三个阶段和三种状态三个阶段：收容、运行和完成收容：提交作业、输入到硬盘上，建立JCB，放入后备队列。为后备状态。运行：被调度进入内存，建立进程，每一次放入就绪队列，直到运行结束。动行状态。完成：任务完成或异常结束，由终止作业程序回收JCB和资源，将结果信息形成输出文件输出。完成状态。2020/1/2075）作业调度的主要任务(1)决定接纳多少作业：单道、多道(2)决定接纳哪些作业：作业调度算法一般系统总是优先选择I/O型和计算型作业均衡个作业投入运行。2、低级调度：进程调度或短程调度，频率最高。由短期调度程序或CPU调度程序执行。Scheduler功能：(1)保存处理机的现场信息：程序计数器、通用寄存器的内容。(2)按某种算法选取进程，将其改为运行状态。(3)由分派程序Dispatcher把处理器分配给进程。恢复现场，从断点处继续运行。•进程切换一定发生在核心态而非用户态2020/1/208三个基本机制：(1)排队器。形成就绪队列。就绪队列可实现为：FIFO队列，优先队列，树或简单的无序链表。(2)分派器。选择就绪进程，切换上下文，分配处理机，切换到用户模式，跳转到用户程序的合适位置，以重新启动程序，停止一个进程而启动另一个进程的时间称为分派延迟（dispatchlatency）。(3)上下文切换机制：两对切换。当前进程和分派程序，分派程序和新进程。2020/1/209•进程上下文切换步骤：•保存被中断程序的处理器现场信息•修改被中断进程的PCB有关信息，如状态•把被中断进程的PCB加入相应队列•选择占用处理器运行的另一个进程•修改被选中进程的PCB信息，就绪。•设置被选中进程的地址空间，恢复存储管理信息•根据被选中进程的上下文信息恢复处理器现场2020/1/2010•处理器模式切换步骤•保存被中断进程的处理器现场信息•处理器从用户态切换到核心态，以便执行系统服务程序或中断处理程序的地址。•如果处理中断，可根据所规定的中断级别设置中断屏蔽位。•根据系统调用号或中断号，从系统调用表中或入口地址表中找到系统服务程序或中断处理程序的地址。•模式切换不同于进程切换，它不一定引起进程状态的切换，也不一定引起进程切换。2020/1/2011•CPU调度决策可以如下4种环境下发生（1）当一个进程从运行状态切换到等待状态（如：I/O请求，或调用P等待一个子进程的终止）（2）当一个进程从运行状态切换到就绪状态（如：当出现中断时）（3）当一个进程从等待状态切换到就绪状态（如：I/O完成，抢占式调度）（4）当一个进程终止时对于1和4,没有选择而只有调度。当调度只能发生在1和4时，调度方案是非抢占的。Windowx3.x是非抢占的，Windows95开始是抢占的。MacOSX是抢占的。2020/1/2012进程调度方式1)非抢占式2)抢占式基于的原则(1)优先权原则(2)短作业优先(3)时间片原则。2020/1/20133、中级调度：中程调度目的：提高内存利用率和系统吞吐量。实际是存储器管理中的对换功能。作业1：处理机的三级调度分别在什么情况下发生？各级调度分别完成什么工作？（西北大学2000年研究生试题）解：（1）高级调度主要用在批处理系统中，并在需要从外存的后备队列向内存调入作业运行时发生；中级调度在内存紧张而无法满足运行作业的要求时发生；低级调度是在执行进程运行完毕、执行进程转入阻塞状态、执行进程的时间片用完、有比现行进程更紧迫的进程到达并允许它抢占CPU等情况下发生的。2020/1/2014（2）高级调度的主要工作是根据调度算法决定把外存后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后，再将新创建的进程插入到就绪队列上等待执行。中级调度的工作是在内存紧张时，将内存中暂时不能运行的进程调出至外存，并在内存空闲时再将外存中具备运行条件的就绪进程调入内存。低级调度的主要工作是根据一定的调度算法，决定就绪进程中的哪一个进程将获得CPU，并将CPU分派给它。2020/1/2015例：引起进程调度的原因有哪些？解：（1）进程正常终止或异常终止（2）正在执行的进程因某种原因而阻塞a.提出I/O请求后被阻塞b.在调用P操作时因资源不足而阻塞c.因其他原因执行block原语而阻塞等。（3）在引入时间片的系统中，时间片用完（4）在抢占调度方式中，就绪队列中某进程的优先权变得比当前正在执行的进程高，或者有优先权更高的进程进入就绪队列。2020/1/2016注意：当系统中只有一个进程且它具备执行条件时，或者系统中只有一个进程具备执行条件而其他的进程均处于阻塞状态时，系统中便会出现只存在运行进程却没有就绪进程的现象。如果系统中的所有进程均处于阻塞状态，则系统中便会出现既没有运行进程也没有就绪进程的现象。系统中不会出现只有就绪进程，却没有运行进程的现象。2020/1/20173.2调度队列模型和调度准则1、仅有进程调度的调度队列模型进程的运行情况：(1)在规定的时间内完成(2)时间片用完(3)提出了I/O请求。2020/1/20182、具有高级和低级调度的调度队列模型(1)就绪队列的形式：最高优先级优先调度算法。(2)设置多个阻塞队列。3、同时具有三级调度的调度队列模型4、选择调度方式和调度算法的若干准则(1)面向用户的准则：周转时间T和带权周转时间W。•周转时间T＝后备作业队列+就绪队列+阻塞队列+CPU运行时间•＝等待时间和运行时间•＝完成时间-到达时间•带权周转时间W＝周转时间/服务时间•＝1+等待时间/服务时间2020/1/2019(2)面向系统的准则：系统吞吐量，处理机利用率，各类资源的平衡利用。整体准则：使CPU使用率和吞吐量最大化，使周转时间、等待时间和响应时间最小化，需要优化平均值，有些情况需要优化最小值或最大值。2020/1/2020批处理作业的调度：先来先服务算法：计算时间短的作业优先算法：响应比高者优先算法:仅适用于作业调度优先数调度算法2020/1/20213.3调度算法：根据系统的资源分配策略所规定的资源分配算法。1、先来先服务和短作业(进程)优先调度算法。1)FCFS：先形成FIFO队列，作业调度和进程调度。甘特图Gantt特点：非抢占，有利于长作业，不利于短作业，有利于CPU繁忙型作业，不利于I/O繁忙型作业。或CPU区间时间变化大，其平均等待时间变化就很大。所有进程等待一个大进程释放CPU，称为护航效果convoyeffect，不适于分时系统。允许一个进程保持CPU时间过长是个严重错误。P1P2P302427302020/1/2022•甘特图，也称为横道图(Barchart)。是在1917年由亨利•甘特开发的，其内在思想简单，基本是一条线条图，横轴表示时间，纵轴表示活动(项目)，线条表示在整个期间上计划和实际的活动完成情况。它直观地表明任务计划在什么时候进行，及实际进展与计划要求的对比。2020/1/20232)SJF或SPF：特点：抢占（最短剩余时间优先）或非抢占对长作业不利，未考虑作业的紧迫程序，作业的长短只能估计。•SJF算法可证明在长期调度中为最佳的（前提条件是所有作业同时到达或所有作业都到达后才进行调度），通过将短进程移到长进程之前，短进程等待时间的减少大于长进程等待时间的增加，因而，平均等待时间减少了。问题：如何知道下一个CPU区间的长度。在短期调度中不容易实现。P1P2P3P403916242020/1/2024进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.992020/1/2025调度算法作业情况2.12.251.53.22.671带权周转时间8931684周转时间1361894完成时间2.83.55.5221带权周转时间914111064周转时间18141274完成时间42534服务时间43210到达时间平均EDCBA进程名FCFS(a)SJF(b)2020/1/2026作业2：若在后备作业队列中等待运行的同时有三个作业1、2、3，已知它们各自的运行时间为a,b,c，且满足关系abc，试证明采用短作业优先算法能获得最小平均周转时间。2020/1/2027例：试证明，短作业优先的作业调试算法可以得到最短的平均响应时间。（北京大学1990年研究生试题）证明：假设有n个作业J1，J2,……，Jn，它们各自的运行时间分别为T1,T2,……，Tn，当作业的调度次序为Ji1,Ji2,…….,Jin时，则平均响应时间T为：T＝[Ti1+(Ti1+Ti2)+(Ti1+Ti2+Ti3)+……+(Ti1+Ti2+…+Tin)]/n=[n×Ti1+(n-1)×Ti2+……+1×Tin]/n。由于nn-1n-2…….1，因此，当Ti1=Ti2=…….=Tin时，平均响应时间T最短。故短作业优先的作业调度算法可以得到最短的平均响应时间。2020/1/20282、高优先权优先调度算法HPFSJF属于简单优先级算法，其优先级为下一个CPU区间的倒数。实质上FCFS也属于简单优先级算法，其优先级为等待时间。1)优先权调度算法的类型(1)非抢占式(2)抢占式2020/1/2029优先级可通过内部或外部方式定义：•内部定义优先级使用一些测量数据以计算进程优先级。如：时间极限、内存要求、打开文件的数量和平均I/O区间与平均CPU区间之比等。•外部定义优先级通过操作系统之外的准则来定义，如：进程的重要性，用于支付的费用类型和数量、赞助工作的单位、其他（政治）等因素。2020/1/2030问题：无穷阻塞或饥饿。1973年关闭MIT的IBM7094时，发现有一个低优先级进程是1967年提交但是一直还未运行。低优先级进程无穷等待问题的解决之一是老化aging