操作系统进程调度

NetworkOptimizationExpertTeam第三章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除NetworkOptimizationExpertTeam教学目的:掌握优先级、吞吐量、死锁等基本概念熟练掌握处理机的各种调度算法掌握死锁产生原因和必要条件熟练掌握用银行家算法来避免死锁的方法掌握死锁的检测和解除方法重点与难点：处理机的各种调度算法银行家算法死锁的解除方法NetworkOptimizationExpertTeam3.1处理机调度的基本概念3.1.1高级、中级和低级调度3.1.2调度队列模型3.1.3选择调度方式和调度算法的若干原则NetworkOptimizationExpertTeam1.高级调度：又称为作业调度或长程调度。用于决定把后备队列中的哪些作业调入内存，为它们创建进程、分配必要的资源，再将新创建的进程排在就绪队列上，准备执行。在批处理系统中，大多配有作业调度，但在分时和实时系统中，却往往不配置作业调度。作业调度的运行频率较低，通常为几分钟一次。3.1.1高级、中级和低级调度——调度的类型NetworkOptimizationExpertTeam执行作业调度时，需要解决：（1）一次接纳多少作业：即允许多少个作业同时在内存中运行。（2）接纳哪些作业：即哪些作业调入内存，取决于所采用的算法。比如先来先服务调度算法；或者是短作业优先调度算法；还有基于作业优先权的调度算法，响应比高者优先调度算法等。NetworkOptimizationExpertTeam2.低级调度：又称为进程调度、短程调度。用于决定就绪队列中的哪个进程能获得处理器,并将处理机分配给该进程。进程调度程序是操作系统最为核心的部分，进程调度策略的优劣直接影响到整个系统的性能。三种类型的操作系统中，都必须配置此级调度。NetworkOptimizationExpertTeam低级调度方式分两类：(1)非抢占方式一旦把处理机分配给某个进程后，让该进程一直执行，直到该进程完成或者发生某事件而阻塞。引起进程调度的因素：正在执行的进程执行完毕；执行中的进程因为提出I/O请求而暂停执行；进程通信或同步过程中执行了原语操作。NetworkOptimizationExpertTeam(2)抢占方式当一进程正在处理机上执行时，系统可根据某种原则暂停它的执行，并将已分配给它的处理机重新分配给另一个进程。抢占的原则有：优先权原则：就绪的高优先权进程有权抢占低优先权进程的CPU。短作业优先原则：就绪的短作业(进程)有权抢占长作业(进程)的CPU。时间片原则：一个时间片用完后，系统重新进行进程调度。NetworkOptimizationExpertTeam3.中级调度又称平衡负载调度、中程调度。目的是为了提高内存利用率和系统吞吐量。实质是进程的内外存对换功能：将外存中已具备运行条件的进程换入内存，而将内存中处于阻塞状态的某些进程换出至外存。在三种调度中，进程调度的运行频率最高，作业调度的周期较长，中级调度的运行频率在上述两者之间。NetworkOptimizationExpertTeam三级调度之间的关系后备作业操作系统中级调度对换进程高级调度CPU低级调度外存内存NetworkOptimizationExpertTeam3.1.2调度队列模型根据os中所引入的调度的类型，形成了三种类型的调度队列模型：仅有进程调度的调度队列模型；具有高级和低级调度的调度队列模型；同时具有三级调度的调度队列模型。NetworkOptimizationExpertTeam就绪队列阻塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完就绪执行阻塞I/O完成进程调度时间片完I/O请求1.仅具有进程调度的调度队列模型NetworkOptimizationExpertTeam2.具有高级和低级调度的调度队列模型就绪队列进程调度CPU进程完成等待事件1作业调度事件1出现时间片完等待事件2事件2出现……等待事件n事件n出现后备队列……NetworkOptimizationExpertTeam3.同时具有三级调度的调度队列模型就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现NetworkOptimizationExpertTeam3.1.3选择调度方式和调度算法的若干原则1.面向用户的准则(1)周转时间短作业周转时间：作业提交计算机到作业完成为止的时间间隔。它是作业在系统里的等待时间与运行时间之和。平均作业周转时间：带权周转时间：W=T/Ts注意：带权周转时间总大于1。平均作业带权周转时间：主要用于评价批处理系统。iiiTnT11niSiiTTnW11T:作业的周转时间，Ts:作业的运行时间。NetworkOptimizationExpertTeam(2)响应时间快从用户通过键盘提交一个请求到系统首次产生响应之间的时间间隔称响应时间。主要用于评价分时系统。(3)截止时间的保证任务必须开始执行的最迟时间或必须完成的最迟时间称截止时间。主要用于评价实时系统。(4)优先权准则在三种OS中，都可遵循。NetworkOptimizationExpertTeam2.面向系统的准则(1)系统吞吐量高吞吐量:单位时间内系统所完成的作业数。(2)处理机利用率好CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间CPU利用率=CPU有效工作时间/CPU总的运行时间(3)各类资源的平衡利用NetworkOptimizationExpertTeam3.2调度算法3.2.1先来先服务和短作业优先调度算法3.2.2高优先权优先调度算法3.2.3基于时间片轮转调度算法NetworkOptimizationExpertTeam调度算法的概念:根据系统的资源分配策略所规定的资源分配算法称为调度算法。通常将作业或进程归入各种就绪或阻塞队列。有的算法适用于作业调度，有的算法适用于进程调度，有的两者都适应。NetworkOptimizationExpertTeam3.2.1先来先服务和短作业优先调度算法最简单的调度算法。用于作业调度时：按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。用于进程调度时：按照进程就绪的先后次序来调度进程。算法特点：容易实现，效率不高，只顾及作业等候时间，没考虑作业要求服务时间的长短，不利于短作业而优待了长作业。1.先来先服务调度算法（FCFS）NetworkOptimizationExpertTeam例：在单道环境下，某批处理显然有四道作业，已知他们的进入系统的时刻、估计运算时间如下：作业进入时刻(h)运行时间(h)ABCD012311001100用FCFS算法计算作业的运行情况、平均周转时间和平均带权周转时间：NetworkOptimizationExpertTeam作业进入时刻运行时间开始时刻完成时刻周转时间带权周转时间ABCD0123110011000110110211011022021100100199111001.99平均周转时间T＝100（h）平均带权周转时间T’＝26.00（h）NetworkOptimizationExpertTeam2.短作业(进程)优先调度算法（SJF/SPF）用于作业调度时：SJF调度算法。以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。用于进程调度时：SPF调度算法。从就绪队列中选出估计运行时间最短的进程，将处理机分配给它。算法特点：易于实现，能有效降低作业的平均等待时间。缺点是：对长作业不利，有可能导致长作业（进程）长期不被调度；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。NetworkOptimizationExpertTeam例：在单道环境下，某批处理显然有四道作业，已知他们的进入系统的时刻、估计运算时间如下：作业进入时刻(h)运行时间(h)ABCD012311001100用SJF/SPF算法计算作业的运行情况、平均周转时间和平均带权周转时间：NetworkOptimizationExpertTeam作业进入时刻运行时间开始时刻完成时刻周转时间带权周转时间ABCD0123110011000110110211011022021100100199111001.99平均周转时间T＝100（h）平均带权周转时间T’＝26.00（h）思考：如果A、B、C、D四个作业同时到达，那么它们的运行情况如何？试计算并比较。NetworkOptimizationExpertTeamFCFS与SJF的比较作业情况调度算法进程名ABCDE平均到达时间01234服务时间43524计算下面各个进程的完成时间、周转时间、带权周转时间，并比较两种算法的优劣。NetworkOptimizationExpertTeamFCFS与SJF的比较作业情况调度算法进程名ABCDE平均到达时间01234服务时间43524FCFS（a）完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJF（b）完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.1NetworkOptimizationExpertTeam3.2.2高优先权优先调度算法用于作业调度时：系统将从后备队列中选择若干个优先权最高的作业装入内存。用于进程调度时：该算法把处理机分配给就绪队列中优先权最高的进程。非抢占式优先权算法抢占式优先权调度算法非抢占式优先权算法：一旦将CPU分配给优先权最高的进程，该进程就一直执行下去，直至完成或发生某个事件。抢占式优先权算法：要进行优先权的比较，高优先权可以进程可以通过调度程序立即停止当前进程，使得CPU重新分配。NetworkOptimizationExpertTeam优先权的类型：静态优先权在创建进程时确定的，且在进程的整个运行期间保持不变。静态优先权法简单易行，但随着进程的推进，其优先权可能与进程的情况不再相符。动态优先权在创建进程时所确定的优先权，可以随着进程的推进而改变。例如：可以规定就绪进程的优先权随着等待时间的增长以速度a增加；正在执行进程的优先权以速度b下降，这样便可防止一个长作业长期垄断处理机。NetworkOptimizationExpertTeamHRRF实际上是一种动态优先权调度算法。FCFS与SJF/SPF是片面的调度算法。FCFS只考虑作业等候时间而忽视了作业的计算时间，SJF/SPF只考虑用户估计的作业计算时间而忽视了作业等待时间。HRRF是介乎这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。但每次调度前，都要进行响应比的计算，会增加系统开销。3.高响应比优先调度算法（HRRF）：NetworkOptimizationExpertTeam要求服务时间要求服务时间等待时间优先权+优先权的变化规律可描述为：由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：要求服务时间响应时间要求服务时间要求服务时间等待时间RP+NetworkOptimizationExpertTeam如果等待时间相同，短作业容易得到较高优先权。长作业等待时间足够长后，也将获得足够高的优先级。如果要求服务时间相同时，作业的优先权决定于其等待时间，实现的是先来先服务。NetworkOptimizationExpertTeam例如：以下四个作业先后到达系统进入调度：作业名到达时间所需CPU时间作业1020作业2515作业3105作业4