处理器调.pptx

2.7.1 处理机调度的层次作业从进入系统成为后备作业开始，直到运行结束退出系统为止，需经历不同级别的调度。高级调度 中级调度 低级调度处理器三级调度模型处理器低级调度高级调度完成超时挂起就绪队列挂起等待队列等待队列就绪队列等待事件交互式用户事件出现后备作业队列中级调度处理器两级调度模型等待事件事件发生进程完成后备作业队列 就绪 队列高级调度低级调度 等待 队列CPU时间片完2.7.2 选择调度算法的原则(1)l资源利用率 CPU利用率=CPU有效工作时间/CPU总的运行时间，CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间。选择调度算法的原则(2)2响应时间 交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间。使交互式用户的响应时间尽可能短，或尽快处理实时任务。这是分时系统和实时系统衡量调度性能的一个重要指标。选择调度算法的原则(3)3周转时间批处理用户从作业提交给系统开始，到作业完成为止的时间间隔称作业周转时间，应使作业周转时间或平均作业周转时间尽可能短。这是批处理系统衡量调度性能的一个重要指标。选择调度算法的原则(4)4吞吐率单位时间内处理的作业数。5公平性确保每个用户每个进程获得合理的CPU份额或其他资源份额，不会出现饿死情况。作业周转与平均周转时间如果作业i提交给系统的时刻是ts，完成时刻是tf，该作业的周转时间ti为：ti=tf-ts 实际上，它是作业在系统里的等待时间与运行时间之和。为了提高系统的性能，要让若干个用户的平均作业周转时间和平均带权周转时间最小。平均作业周转时间 T=(ti)/n作业带权周转时间和平均作业带权周转时间如果作业i的周转时间为ti，所需运行时间为tk，则称wi=ti/tk为该作业的带权周转时间。ti是等待时间与运行时间之和，故带权周转时间总大于1。平均作业带权周转时间W=(wi)/n2.7.3 作业和进程的关系作业管理任务：一、是作业组织；二、是作业调度；三、是运行控制。作业和进程的关系 作业(JOB)，作业步(Job Step)，作业组织，作业的提交、收容、执行和完成。作业是任务实体，进程是完成任务的执行实体;没有作业任务，进程无事可干，没有进程，作业任务没法完成。作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统。2.7.4 作业组织、调度和控制1批作业的组织和管理1)批作业的输入2)批作业的建立作业控制语言作业说明书作业控制块 作业控制块多道批处理操作系统具有独立的作业管理模块，必须像进程管理一样为每一个作业建立作业控制块（JCB）。JCB通 常 是 在 批 作 业 进 入 系 统 时，由Spooling系统建立的，它是作业存在于系统的标志，作业撤离时，JCB也被撤销。JCB的主要内容包括：(1)作业情况 (2)资源需求 (3)资源使用情况作业生命周期状态输入状态：后备状态：执行状态：完成状态：批作业的调度(1)选择作业：(2)分配资源：(3)创建进程：(4)作业控制：(5)后续处理：作业调度与进程调度的关系 进程调度运行就绪等待输入状态后备状态完成状态预输入完成作业控制作业调度(选中并创建进程)作业调度(作业终止并撤离)SPOOLing作业预输入SPOOLing作业缓输出2 交互作业的组织和管理分时系统的作业就是用户的一次上机交互过程，可认为终端进程的创建是一个交互型作业的开始，退出命令运行结束代表用户交互型作业的中止。交互作业的情况和资源需求通过操作命令告知系统，分时用户逐条输入命令，即提交作业（步）和控制作业运行，系统则逐条执行并给出应答，每键入一条或一组有关操作命令，便在系统内部创建一个进程或若干进程来完成相应命令。键盘命令有：作业控制类；资源申请类；文件操作类；目录操作类；设备控制类等。2.8处理器调度算法2.8.1 低级调度的功能和类型2.8.2 作业调度和低级调度算法2.8.3 实时调度算法2.8.4 多处理机调度算法 2.8.1 低级调度的功能和类型1 低级调度的主要功能 调度程序两项任务：调度和分派。调度实现调度策略，确定就绪进程/线程竞争使用处理器的次序的裁决原则，即进程/线程何时应放弃CPU和选择哪个来执行；分派实现调度机制，确定如何时分复用CPU，处理上下文交换细节，完成进程/线程和CPU的绑定和放弃的实际工作。调度机制逻辑功能程序模块组成 队列管理程序：上下文切换程序：分派程序：2 低级调度的基本类型第一类称剥夺式：两种处理器剥夺原则，一是高优先级进程/线程可剥夺低优先级进程/线程，二是当运行进程/线程时间片用完后被剥夺。第二类称非剥夺式：2.8.2 作业调度和低级调度算法1先来先服务算法三个作业同时到达系统并立即进入调度：作业名/所需CPU时间:作业1/28，作业2/9，作业3/3。采用FCFS算法，平均作业周转时间为35。若三个作业提交顺序改为作业2、1、3，平均作业周转时间约为29。若三个作业提交顺序改为作业3、2、1，平均作业周转时间约为18。FCFS调度算法的平均作业周转时间与作业提交的顺序有关。2最短作业优先算法(1)SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。算法易于实现，效率不高，主要弱点是忽视了作业等待时间。会出现饥饿现象。SJF的平均作业周转时间比FCFS要小，故它的调度性能比FCFS好。实现SJF调度算法需要知道作业所需运行时间，否则调度就没有依据，要精确知道一个作业的运行时间是办不到的。最短作业优先算法(2)四个作业同时到达系统并进入调度：作业名/所需CPU时间:作业1/9，作业2，作业3/10，作业4/8。SJF作业调度顺序为作业2、4、1、3，平均作业周转时间T=17，平均带权作业周转时间W=1.98。如果施行FCFS调度算法，平均作业周转时间T=19，平均带权作业周转时间 W=2.61。3最短剩余时间优先算法(1)SRTF把SJF算法改为抢占式的。一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短，SRTF强行赶走当前正在执行作业。称最短剩余时间优先算法此算法不但适用于JOB调度，同样也适用于进程调度。最短剩余时间优先算法(2)四个作业其到达系统/所需CPU时间如下：Job1-0/8，Job2-1/4，Job3-2/9，Job4-3/5。SRTF调度平均等待时间=6.5毫秒。SJF调度平均等待时间=7.75毫秒。J1 J2 J4 J1 J3015101726shortest next CPU burst time(1)计算进程/线程下一个CPU周期长度 n+1=tn+(1-)ntn是进程/线程最近一个CPU周期长度，是最近信息；n是估算的第n个CPU周期值，是历史信息；4响应比最高者优先算法FCFS与SJF是片面的调度算法。FCFS只考虑作业等候时间而忽视了作业的计算时问，SJF只考虑用户估计的作业计算时间而忽视了作业等待时间。HRRF是介乎这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。响应比定义 响应比 1+已等待时间/估计运行时间 短作业容易得到较高响应比，长作业等待时间足够长后，也将获得足够高的响应比，饥饿现象不会发生。HRRF算法举例 四个作业到达系统时间/所需CPU时间:作业1-0/20，作业2-5/15，作业3-10/5，作业4-15/10。SJF调度顺序为作业1、3、4、2，平均作业周转时间T=25，平均带权作业周转时间W=2.25。FCFS调度顺序为作业1、3、4、2，平均作业周转时间T=28.75，平均带权作业周转时间W=3.125。HRRF调度顺序为作业1、3、4、2，平均作业周转时间T=26.25，平均带权作业周转时间W=2.46。5优先级调度算法(1)静态优先数法使用外围设备频繁者优先数大，这样有利于提高效率；重要算题程序的进程优先数大，这样有利于用户；进入计算机时间长的进程优先数大，这样有利于缩短作业完成的时间；交互式用户的进程优先数大，这样有利于终端用户的响应时间等等,优先权调度算法(2)动态优先数法根据进程占有CPU时间多少来决定,当进程占有CPU时间愈长,那么，在它被阻塞之后再次获得调度的优先级就越低，反之,进程获得调度的可能性越大;根据进程等待CPU时间多少来决定,当进程在就绪队列中等待时间愈长,那么，在它被阻塞之后再次获得调度的优先级就越高，反之,进程获得调度的可能性越小。6时间片轮转调度算法时间片调度做法是：调度程序每次把CPU分配给就绪队列首进程使用一个时间片，例如100ms，就绪队列中的每个进程轮流地运行一个时间片。当这个时间片结束时，强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度轮转策略可防止那些很少使用外围设备的进程过长的占用处理器而使得要使用外围设备的那些进程没有机会去启动外围设备轮转策略与间隔时钟 Example of RR with Time Quantum=20ProcessBurst TimeP153 P2 17 P368 P4 24The Gantt chart is:Typically,higher average turnaround than SJF,but better responseP1P2P3P4P1P3P4P1P3P302037577797117121 134154 1627多级反馈队列调度又称反馈循环队列或多队列策略。主要思想是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。一个三级反馈队列反馈队列调度策略 低级就绪队列高级就绪队列中级就绪队列等待磁盘磁带等待其他外设运行选中,时间片500ms超过时间片启动磁盘磁带启动其他外设选中,时间片200ms选中,时间片100ms8彩票调度算法基本思想：为进程发放针对各种资源（如CPU时间）的彩票。调度程序随机选择一张彩票，持有该彩票的进程获得系统资源。进程都是平等的，有相同的运行机会。如果某些进程需要更多的机会，可被给予更多彩票，增加其中奖机会。2.8.3 实时调度算法实时系统是那些时间因素非常关键的系统。实时系统包括监控系统、自动驾驶系统、安全控制系统等，这些系统中，迟到的响应即使正确，也和没有响应一样糟糕。硬实时系统和软实时系统实时系统通常分为硬实时系统和软实时系统。前者意味着存在必须满足的时间限制；后者意味着偶尔超过时间限制时可以容忍的。周期性和非周期性事件实时系统响应的事件可划分为周期性事件和非周期性事件。例如，m个周期性事件，事件i的周期为Pi，每个事件需要Ci秒的CPU时间来处理，则只有满足以下条件：C1/P1+C2/P2+Cm/Pm 1 时，才可能处理所有的负载。满足该条件的实时系统称作任务可调度的。实时调度算法(1)1）单比率调度算法 基本思想：为每个进程分配一个与事件发生频率成正比的优先数。例如，周期为20ms的进程优先数为50，周期为100ms的进程优先数为10，运行时调度程序总是调度优先数最高的就绪进程，并采取抢占式分配策略。实时调度算法(2)2）限期调度算法 基本思想：当一个事件发生时，对应的进程就按照截止期限被加入就绪进程队列。对于一个周期性事件，其截止期限即为事件下一次发生的时间。该调度算法首先运行队首进程，即截止时间最近的那个进程。实时调度算法(3)3）最少裕度法 (最低松弛度优先算法LLF)基本思想：首先计算各个进程的富裕时间，即裕度（laxity），然后选择裕度最少的进程执行。裕度=截止时间-(就绪时间+计算时间)(=完成时间-运行时间-当前时间)例：假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间为25ms。由此可得知任务A和B每次必须完成的时间分别为：A1,A2,A3,A4,A5和B1,B2,B3，为保证不遗漏任何一次截止时间，应采用最低松弛度优先的抢占调度策略。试画出两个任务的执行推进图。课堂练习题某实时系统中，有两个周期性任务A和B，从两个端口收集数据，其中A的周期为30ms，执行时间为15ms，B的周期为75ms，执行时间为38ms。问此系统能否及时响应。A和B均以开始截至时间开始截至时间为准。（实时调度）注：注：所谓截至时间，是指某任务必须开始执行的最迟时间（开始截至时间），或者必须完成的最迟时间（完成截至时间）2.8.4 多处理器调度1多处理机调度的设计要点 1)如何为进程分配处理机、2)在单个处理机上是否使用多道程序设计技术 3)如何实际指派进程，多处理器调度算法(1)1）负载共享调度算法基本思想：进程并不指派到特定处理机上，系统维护全局性进程就绪队列，当处理机空闲时，就选择进程的一个线程去运行。多处理器调度算法(2)2）群调度算法 基本思想：一群相关线程基于一对一的原则，被同时调度到一组处理机上运行。它具有的优点：当紧密相关的进程同时执行时，同步造成的等待将减少，进程切换也相应减少，系统性能得到提高。由于一次性同时调度一组处理器，调度的代价也将减少。群调度的例子 统一划分组1组2空闲空闲空闲浪费时间37.5%浪费时间15%加权划分组1组2空闲空闲空闲多处理器调度算法(3)3）处理器专派调度算法基本思想：给同属一个进程的一组线程，同时分派到一组处理机上运行，每个线程获得一个处理机，且它专用于处理这个线程，直到进程运行结束，这是群调度的一种极端形式。采用这一算法，处理器将不适用多道程序设计，即该应用的一个线程阻塞后，线程对应的处理器不会被调度给其他线程，而处于空闲状态。多处理器调度算法(4)4）动态调度算法(1)基本思想：由操作系统和应用进程共同完成调度。操作系统负责在应用进程之间划分处理器。应用进程在分配给它的处理器上执行可运行线程的子集，哪一些线程应该执行，哪一些线程应该挂起完全是应用进程自己的事。多处理器调度算法(5)动态调度算法(2)如果有空闲处理器，满足要求。否则，对新到达进程，从当前分配了一个以上处理器的进程中收回一个，并把它分给新到达进程。如果要求不能被满足，则保留申请直到出现可用处理器或要求取消。释放了一个或多个处理器后，扫描申请处理器的进程队列，按照FCFS原则把处理器逐一分配给每个申请进程直到没有可用处理器。