计算机操作系统第三章处理机调度与死锁ppt培训课件

《计算机操作系统第三章处理机调度与死锁ppt培训课件》由会员分享，可在线阅读，更多相关《计算机操作系统第三章处理机调度与死锁ppt培训课件（82页珍藏版）》请在金锄头文库上搜索。

1、第三章 处理机调度与死锁,本章内容,处理机调度 常用调度算法介绍 死锁与预防死锁的方法 本章讨论处理器资源的管理问题。 处理器调度问题决定着整个系统的综合性能。不同的CPU管理方法将为用户提供不同性能的操作系统。,3.1 处理机调度的层次,从处理器调度的对象、时间、层次等不同角度，可把处理器调度分成不同类型。 按照调度涉及的层次不同，从用户作业从进入系统成为后备作业开始，直到运行结束退出系统为止，可把处理器调度分成： 高级调度 中级调度 低级调度,3.1.1 高级调度,高级调度概念 也称为作业调度、长程调度或接纳调度。 按照系统预定的调度策略，决定把外存上处于后备队列中的哪些作业调入内存，并为

2、它们创建进程、分配必要的资源，然后再将创建的进程排在就绪队列上，准备执行。 在批处理操作系统中，作业首先进入系统在辅存上的后备作业队列等候调度，因此，作业调度是必须的。在纯粹的分时或实时操作系统中，通常不需要配备作业调度。,作业相关概念,作业：程序+数据+作业说明书 作业步：相对独立相互关联的顺序加工步骤 作业流 作业控制块JCB：作业在系统中的标识，保存有系统对作业进行管理与调试所需要的全部信息 作业标识 用户名称、用户帐户 作业类型、作业状态 资源需求 调度信息 进入时间、开始处理时间、需求时间 ,作业调度时要做的决定： （1）接纳多少个作业 （2）接纳哪些作业（调度算法） 作业调度的目标

3、： （1）对所有作业尽量做到公平合理 （2）高设备利用率 （3）执行尽可能多的作业 （4）尽量短的响应时间,3.1.2 低级调度,也称为进程调度、短程调度。 用于决定就绪队列中的哪个进程获得处理机。低级调度程序是操作系统最为核心的部分，低级调度策略的优劣直接影响到整个系统的性能。 最初的调度对象是传统操作系统中的进程，随着现代操作系统引入了多线程技术，进程演变成资源管理的单位，从而只作为中级调度的对象，内核级线程则替代进程成为低级调度的对象。,1. 进程调度功能,（1）记录系统中所有进程的执行情况 （2）选择占有处理机的进程(选择算法) （3）进行进程上下文切换 个进程的上下文(context

4、)包括进程的状态、有关变量和数据结构的值、机器寄存器的值等相关程序、数据。当正在执行的进程让出处理机时，系统要做进程上下文切换，以使另一个进程得以执行。,2.进程调试中的三个基本机制,排队器：负责组织各进程队列 分派器：将选中的进程从就绪队列中取出，分配处理机 上下文切换机制两对上下文切换： 保存当前进程上下文，装入分派程序上下文 移出分派程序上下文，装入新选进程现场信息,3. 进程调度方式,1）非抢占方式 进程一旦获得处理机后便一起执行下去，直至该进程完成或发生某事件被阻塞时，才把处理机分配给其他进程。决不允许某进程抢占已经分配出去的处理机。 当前进程无论在用户态还是核心态都不可以被抢用CP

5、U。不可抢先式OS：Windows98/95，在这些OS中，进程从运行态退出只能是自愿或阻塞，不能强迫运行态就绪态。,引起进程调度的因素： （1）进程执行完毕，或发生某事件不能再继续执行 （2）I/O请求 （3）进程通信或同步过程中执行了原语操作 优点：实现实现简单，系统开销小，适用于批处理系统。 缺点：不能满足紧急任务的要求，不适用于实时系统。,2）抢占方式,当一个进程正在运行时，调度程序可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。 剥夺原则有： （1）优先权原则 （2）短进程优先原则 （3）时间片原则。,内核完全不可抢先,当前进程在用户态时可随时被抢用CPU，但处于核心态

6、时完全不可以被抢用CPU。如：传统的UNIX和Windows。 这类操作系统通常在系统调用或中断时屏蔽中断，系统调用返回或中断返回时开放中断。,内核的部分可抢先,当前进程在用户态时随时被抢用CPU，但处于核心态时则大部分时间不可以被抢用CPU，只在某些时刻点（可抢先点）可以被抢用CPU。如：UNIX SVR4。 SVR4内核定义了抢先点：内核代码中的这样一些位置，内核的数据结构处在一个稳定的状态，并且内核马上要开始长时间的、大量的计算。此时，内核检查是否有实时进程就绪需要运行，若有则抢先当前进程。,完全可抢先或内核完全可抢先,无论当前进程处于用户态还是核心态，都可以随时可被抢用CPU。如：SU

7、N Solaris（最成功的UNIX商业变种之一）。 为做到完全可抢先，Solaris对SVR4的核心代码做了全面修改，大部分的内核全局数据结构都用正确的同步对象如互斥 锁或信号量来保护，并通过特殊内核线程实现中断来避免用提高优先级的方法保护临界区。Solaris内核中只有极少的不可抢先代码段。,3.1.3 中级调度,中级调度实现进程在主存与外存间的对换。反映到进程状态上就是挂起和解除挂起。 中级调度将那些暂时不能运行的进程调出主存，此时这些进程处于挂起状态。当被挂起的进程具备了运行条件，且主存又有空闲区域时，再由中级调度决定一部分这样的进程重新调回主存工作。 中级调度起到短期调整系统负荷的作

8、用，调度的依据是存储资源量和进程的当前状态，目的是提高内存利用率和系统吞吐量。,3.2 调度队列模型和调度准则,3.2.1 调度队列模型 1只有进程调度的调度队列模型 内存中维护就绪进程队列和阻塞进程队列。系统可能以栈、树、链表的方式组织队列。,2具有高级与低级调度的调度队列模型,外存维护一个后备队列，内存维护就绪进程队列和阻塞进程队列。,3同时具有三级调度的调度队列模型,3.2.2 选择调度方式和调度算法的准则,不同类型及目标的操作系统，其采用的调度方式与调度算法通常不同。 1面向用户的准则 2面向系统的准则,1面向用户的准则,（1）周转时间短 周转时间：作业提交计算机开始到完成返回用户为止

9、的时间间隔。 （2）响应时间快 响应时间：从提交一个请求到首次产生响应的时间间隔。或者说，用户发送指令给计算机到计算机返回结果给用户的时间间隔。,1面向用户的准则,（3）截止时间的保证 评价实时系统的重要指标。 截止时间：任务必须开始执行的最迟时间，或必须完成的最迟时间。 （4）优先权准则：关键任务得到更好的性能指标 （5）公平性：确保每个用户每个进程获得合理的CPU份额或其他资源份额。,2面向系统的准则,（1）系统吞吐量高 吞吐量：单位时间内系统完成的作业数。 （2）处理机利用率高：大中型系统的主要指标 （3）各类资源的平衡利用,3.3 调度算法,常用的作业调度算法有： FCFS（先来先服务

10、）方法 SJP（最短作业优先）法 HRN（最高响应比）法 常用进程调度算法： RR（轮转）法 FCFS（先来先服务）法 优先级法 多级反馈队列算法,3.2.1 先来先服务算法,最简单的调度算法，基本思想是按进程（作业）到达的先后顺序进行调度。 作业调度：按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。 进程调度：按照进程进入就绪队列的先后次序来分配处理器。先进入就绪队列的进程优先被挑选，运行进程一旦占有处理器将一直运行下去直到运行结束或阻塞，即采用非抢占调度方式。,FCFS的特点： 比较有利于长作业，而不利于短作业（进程）。 有利于CPU繁忙型作业，而不利于I/O繁忙型作业。

11、 实现简单 平均周转时间长,3.2.1 短作业（进程）优先算法,这是对FCFS算法的改进，其目标是减少平均周转时间。 SJF：从后备队列中选择估计运行时间最短的一个或几个作业调入内存。 SPF：从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它。,短进程优先法调度方式,短进程优先算法既可以是非抢占式，也可以是抢占式。 当一个进程正在执行时，一个新进程进入就绪状态，如果新进程需要的CPU时间比当前正在执行的进程剩余下来还需的CPU时间短，抡占式短进程优先算法强行赶走当前正在执行进程，这种方式也叫最短剩余时间优先算法(Shortest Remaining Time First) 。,短作

12、业优先法的特性,优点： 与FCFS相比，改善平均周转时间和平均带权周转时间，缩短作业的平均等待时间。 易于实现，系统吞吐量高。 缺点： 忽视了作业等待时间 对长作业非常不利，长作业（进程）可能长时间得不到执行； 未能依据作业的紧迫程度来划分执行的优先级； 难以准确估计作业（进程）的执行时间，从而影响调度性能。,短作业优先算法的变型： “最短剩余时间优先”(Shortest Remaining Time First)允许比当前进程剩余时间更短的进程抢占当前进程 “最高响应比优先” (Highest Response Ratio Next)响应比R = (等待时间 + 要求执行时间) / 要求执行

13、时间 是FCFS和SJF的折衷,3.3.2 最高优先权优先算法（FPF）,作业调度：从后备队列中选择若干个优先权最高的作业进入内存。 进程调度：每一个进程给出一个优先数，处理器调度每次选择就绪进程队列中优先数最大者，让它占用处理器运行。,1优先权调度算法的类型,（1）非抢占式优先权算法 系统一旦将处理机分配给优先权最高的进程后，该进程便一直执行下去直到完成。主要用于批处理系统，也用于某些实时要求不严的实时系统中。 （2）抢占式优先权调度算法 系统按最高优先权分配处理机。只要出现另一个优先权更高的进程，则进程调度程序停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。 常用于严格的实时

14、系统中，或对性能要求较高的批处理和分时系统中。,2优先权的类型,（1）静态优先权 静态优先权是在创建进程时确定的，在整个运行期间不再改变。 确定优先权的依据有： 进程类型。如系统进程优先权高于用户进程。 进程对资源的需求。如估计运行时间、内存需求等。 用户要求。由用户或操作员根据作业的紧急程序指定一个优先级。 静态优先权法简单易行，系统开销小，但不够精确。,2优先权的类型,（2）动态优先权 创建进程时所赋予的优先权，在进程周期内可以动态变化。如随等待时间的增加而改变。 优先权确定依据： 根据进程占用有CPU时间的长短来决定。 根据就绪进程等待CPU的时间长短来决定。,3. 高响应比优先算法,最

15、高响应比优先法（HRN）是对FCFS方式和SJF方式的一种综合平衡。 HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。 响应比=（等待时间+要求服务时间）/要求服务时间,特点： （1）在等待时间相同时，此算法是优待短作业的，实现的是SJF。 （2）在要求服务时间相同时，优先权决定于等待时间，实现的是FCFS。 （3）长作业在等待足够长时，也可获得处理机。 这种算法是介于FCFS和SJF之间的一种折中算法。但是由于每次调度前要计算响应比，系统开销也要相应增加。,3.3.3 基于时间片的轮转调度算法,1. 时间片轮转法 系统将所有就绪进程按F

16、IFS规则排队，每个进程轮流运行一个相同的时间片。 每次调度时将CPU分派给队首进程，让其执行一个时间片。在一个时间片结束时，发生时钟中断，调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，再将处理机分配给就绪队列的队首进程。这样可保证就绪队列中的所有进程在一定时间内均能获得一时间片的处理机，即系统在能在给定时间内响应所有用户的请求。,好处：使系统及时响应。 缺点：轮转法调度是一种剥夺式调度，系统耗费在进程切换上的开销比较大， 时间片长度变化的影响: 过长退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。 过短用户的一次请求需要多个时间片才能处理完，切换次数增加，系统开销大。,时间片长度的确定： （1）系统效率 （2）对响应时间的要求：T(响应时间)=N(进程数目)*q(时间片) （3）就绪进程的数目：数目越多，时间片越小 （4）CPU的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。,2. 多级反馈队列调度算法,多级反馈队列算法是时间片轮转算法和 优先级算法的综合和发展。 1）实现 （1）系统中设置多个就绪队列，分别赋予不同的优先级，并逐级降低。 （2）为不同队列所规定的时间片长度不同，优先权越高的队列分配的时间片越小。如逐级加倍。,