804、第三章 中断与处理机调度

3.2处理机调度处理机调度的任务是控制协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。确定算法的原则具有公平性。资源利用率高（特别是CPU利用率）。在交互式系统情况下要追求响应时间（越短越好）。在批处理系统情况下要追求系统吞吐量。1、先到先服务算法（FCFS）按照进程就绪的先后次序来调度进程。优点：实现简单。缺点：没考虑进程的优先级。2、优先数算法（HPF）优先选择就绪队列中优先级最高的进程投入运行。优先级根据优先数来决定。确定优先数的方法静态优先数法：在进程创建时指定优先数，在进程运行时优先数不变。动态优先数法：在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变。两种占用CPU的方式可剥夺式（可抢占式Preemptive）：当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用。不可剥夺式（不可抢占式Non-Preemptive）：某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去。3、循环轮转算法（RR）把CPU划分成若干时间片，并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列的末尾。同时系统选择另一个进程运行。3、循环轮转算法（RR）分时系统中常用时间片轮转算法。时间片选择问题：固定时间片可变时间片与时间片大小有关的因素：系统响应时间就绪进程个数CPU能力时间片取选的两个极端时间片取值太小：多数进程不能在一个时间片内运行完毕，切换就会频繁，系统开销显著增大。时间片取值过大：每个进程均可在一个时间片内运行完毕，循环轮转算法就退化成了先来先服务算法，不能达到充分利用资源的目的。4、反馈排队算法（FB）将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间片越长，级别越小，时间片越短，最后一级采用时间片轮转算法，其他队列采用先到先服务算法；系统从第一级调度，当第一级为空时，系统转向第二个队列，……当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入第一级队列；当进程第一次就绪时，进入第一级队列。4、反馈排队算法首先系统中设置多个就绪队列。每个就绪队列分配给不同的时间片，优先级高的为第一队列，时间片最小，随着队列优先级的降低，时间片加大。各个队列按照先进先出的调度算法。一个新进程就绪后进入第一级队列。进程由于等待而放弃CPU后，进入等待队列，一但等待的事件发生，则回到第一级队列。当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到第一级队列末尾。当第一级队列为空时，就去调度第二级队列，以此类推。当时间片用尽后，进程放弃CPU，回到下一级队列。3.2.2处理机调度时机当一个进程运行完毕，或由于某种错误而终止运行。当一个进程在运行中处于等待状态（等待I/O）。分时系统中时间片用尽。当有一个优先级更高的进程就绪（可抢占）。例如：新创建一个进程，一个等待进程变成就绪。在进程通信中，执行中的进程执行了某种原语操作（P操作、阻塞原语、唤醒原语）。3.2.3处理机调度过程进程切换：一个进程让出处理机，由另一个进程占用处理机的过程。进程的切换使系统中的各进程均有机会占用CPU。进程的切换是由进程状态的变化引起的，而进程状态的变化又与出现中断的事件有关。3.2.3处理机调度过程当有中断事件发生时，当前运行的进程被中断，中断响应后由操作系统处理出现的中断事件。中断处理后。某些进程的状态会发生变化，也可能又创建了一些新的进程。因此，要进行队列的调整。然后，进程调度根据预定的调度算法从就绪队列选一个进程占用CPU。这个占用CPU运行的进程可能仍是被中断的进程，也可能是另一个进程。何时切换进程只要OS取得对CPU的控制，进程切换就可能发生。如：超级用户调用来自程序的显式请求（如：打开文件），该进程通常会被阻塞。陷阱最末一条指令导致出错，会引起进程移至退出状态。中断外部因素影响当前指令的执行，控制被转移至IH（中断处理程序）。3.2.3处理机调度过程保存现场：顺序保存，最后一步保存PSW。选择要运行的程序：如果没有就绪进程，系统会安排一个闲逛进程（idle），没有其他进程时，在执行过程中可接收中断。恢复现场：最后一步恢复选中进程的PSW。在进程（上下文）中切换的步骤保存处理机的上下文，包括程序计数器和其他寄存器。用新状态和其他信息更新正在运行进程的PCB。把原来的进程移至合适的队列-就绪、阻塞。选择另一个要执行的进程。更新被选中进程的PCB。从被选中进程中重装入CPU上下文。2.4作业所谓作业就是用户要求计算机给以计算（或处理）的一个相对独立的任务。作业由程序、数据和作业说明书三部分组成。一个作业一般可以分为几个逻辑上必须顺序处理的工作单位（或步骤），称为作业步。2.4作业通常，程序在计算机上运行要分成三个步骤：第一步：编译；第二步：连接；第三步：运行已经装配好的可执行程序。2.4作业在作业执行过程中，各个作业步之间联系密切，上一个作业步的执行结果作为下一个作业步的执行前提。准准准准准准准准准准准准准准准准准准准准准准准作业、作业步、进程之间的关系用户作业作业步作业步进程进程............2.4作业按系统的作业处理方式，作业可分为：脱机作业和联机作业。脱机作业是指用户不能和计算机直接交互，需要通过操作员从中干预的作业。（后台作业）联机作业是用户通过外围设备直接与计算机系统进行交互，从而控制作业的运行，这种作业也叫交互型作业。（前台作业）联机作业多出现在分时系统中，而脱机作业进场出现在批处理系统中。作业的状态作业在整个活动期间经历的四种状态：1、提交状态2、后备状态（收容态）3、执行状态（执行态）4、完成状态作业的状态及转换提交状态后备状态提交状态运行就绪等待运行状态作业调度SPOOLing作业控制块（JCB）JCB是一个作业存在的标志。每个JCB记录了与该作业有关的信息，其具体内容根据作业调度的要求而定。对于不同的系统，JCB的内容有所不同。作业调度什么是作业调度？作业管理程序要按照一定的策略从后备作业中选取若干个作业，把它们装入内存并为它们分配必要的资源，让它们能够同时执行，这就是作业调度。作用：完成作业从后备状态到执行状态和从执行状态到完成状态的转变。调度算法应达到的目标1、每次运行尽可能多的作业；2、让处理机保持忙碌状态；3、使输入输出设备得以充分利用；4、对所有的作业公平合理；确定调度算法时应考虑的因素1、调度算法应与系统的总体设计目标一致。2、注意系统资源的均衡使用，使输入输出繁忙的作业与CPU繁忙的作业搭配运行。3、应保证进入系统的作业在规定的截止期内能够运行结束。衡量调度算法性能的指标平均周转时间和平均带权周转时间在分时系统和实时系统中一般采用平均响应时间来衡量调度策略的优劣。1、周转时间作业i的周转时间定义为：Ti=Tsi-Tti其中Tsi为i作业完成时间，Tti为作业的提交时间。11nniTiT确定调度算法时应考虑的因素一个作业的周转时间可分为两个部分：一是等待时间（从后备态到执行态）；一是执行时间。可表示为：Ti=Twi+Tri2、带权周转时间如果对任意的n个作业来说（n=1），其平均带权周转时间为：11nniWiT作业调度算法1、先来先服务调度算法（First-ComeFirst-Served,FCFS）先来先服务调度算法是严格按照作业先来后到的次序进行调度的。例：假定有如下四个作业，它们的提交时间、运行时间如下表：按先来先服务的调度算法进行调度，算得的平均周转时间和平均带权周转时间分别为2.8和5.25。作业号提交时间执行时间开始时间完成时间周转时间带权周转时间111.02.011.013.02.01.0211.21.013.014.02.82.8311.40.514.014.53.16.2411.50.314.514.83.311.0作业调度算法2、短作业优先调度算法（Shortest-Job-First,SJF）短作业优先调度算法是选取执行时间最短的作业做为下一次服务的对象。这种算法能够使系统的平均周转时间最短，因此，有很高的系统吞吐量。例：对上例的作业采用短作业优先调度算法来进行调度，算出的平均周转时间和平均带权周转时间分别为2.45和3.85。作业号提交时间执行时间开始时间完成时间周转时间带权周转时间111.02.011.013.02.01.0411.50.313.013.31.86.0311.40.513.313.82.44.8211.21.013.814.83.63.6作业调度算法3、最高响应比优先调度算法（Highest-Response-Ratio-Next,HRN）最高响应比优先调度算法（HRN）是介于先到先服务调度算法（FCFS）与短作业优先调度算法（SJF）之间的调度算法，是对二者的折中。响应比：我们把作业的响应时间与执行时间的比值称为响应比。响应比=（等待时间+执行时间）/执行时间=1+等待时间/执行时间例：假定有如下四个作业，它们的提交时间、运行时间如下表，如采用最高响应比优先调度算法，计算平均周转时间和平均带权周转时间。（其中时间单位为小时，按十进制计算）作业号提交时间执行时间开始时间周转时间带权周转时间18.02.08.02.01.028.30.510.12.34.638.50.110.01.616.049.00.410.62.05.0例：在8：00时，因为只有作业1提交，系统将作业1投入运行。作业1运行2小时（即10.0时）完成。由于该算法采用响应比高者优先调度，这样在作业1执行完后，要计算剩下三个作业的响应比，然后选响应比高者去运行，剩下三个作业的响应比为：R2=1+(10.0-8.3)/0.5=4.4R3=1+(10.0-8.5)/0.1=16.0R4=1+(10.0-9.0)/0.4=2.5例：从计算结果看，作业3的响应比高，所以让作业3先运行。作业3运行0.1小时（即10.1时）完成，此时，作业2和作业4的响应比为：R2=1+(10.1-8.3)/0.5=4.6R4=1+(10.1-9.0)/0.4=3.75从上述计算结果看，作业2的响应比高，所以让作业2先运行，因此四个作业的执行次序为：作业1、作业3、作业2、作业4故平均周转时间为1.975，平均带权周转时间为6.65作业调度算法4、优先数调度算法（Highest-Priority-First,HPF）这种算法可以综合考虑有关因素，如作业缓急程度、作业长短、等待时间的多少、外部设备的使用情况，并根据系统设计目标分析这些因素的重要程度，按比例确定各作业的优先数，系统按优先数的高低调度作业。