单处理器调度_1105

《单处理器调度_1105》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第9章单处理器调度处理机调度的调度类型执行等待就绪等待就绪完成状态收容状态提交状态进程调度交换调度作业调度内存外存长程调度：作业调度中程调度：交换调度短程调度：进程调度短程调度时机（当前阻塞或被剥夺）时钟中断I/O中断操作系统调用信号（信号量）两种占用CPU的方式：可剥夺式：当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用不可剥夺式：某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去短程调度准则面向用户：响应时间-提交一条请求到响应出现在输出的时间间隔面向系统：吞吐量、处理器利用率调度准则：一般来说，调度目

2、标主要是以下五点(1)公平合理：对所有作业应该是公平合理的；(2)高利用率：应使设备有高的利用率，(3)吞吐量大：执行尽可能多的作业（进程）；(4)响应迅速：有快的响应时间。(5)周转时间：尽可能短任一调度算法要想同时满足上述目标是不可能的：1）如要想吞吐量大，调度算法就应选择那些估计执行时间短的作业。这对那些估计执行时间长的作业不公平，并且可能使它们的得不到调度执行或响应时间很长。2）如果考虑的因素过多，调度算法就会变得非常复杂。其结果是系统开销增加，资源利用率下降。衡量调度策略的常用指标周转时间：指将一个作业提交给计算机系统后到该作业完成所需要的时间。吞吐量：指在给定的时间内，一个

3、计算机系统所完成的总工作量(进程数)。响应时间：指从用户向计算机发出一个命令到计算机把相应的执行结果返回给用户所需要的时间。设备利用率：设备的使用情况周转时间：作业i的周转时间Ti为Tr＝Tei-TsiTei为作业i的完成时间；Tsi为作业的提交时间。N个作业的平均周转时间T=（T1+T2+…+TN）/N带权(归一化)周转时间：周转时间Ti可分解为两部分Tr＝Twi+TriTwi等待时间Tri执行时间周转时间与执行时间的比：Wi＝Ti／TriN个作业的平均带权周转时间W＝(W1+W2+…+WN)/N调度策略先来先服务(FirstComeFirstServed)短作业优先(Shortes

4、tProcessNext)短剩余优先(ShortestRemainingTime)高响应比优先(HighestResponseRatioNext)时间片轮转(RoundRobin)优先级(HighestPriorityFirst)多级队列反馈(MultilevelFeedback)常用作业调度算法1先来先服务（Firstcomefirstserve,FCFS）方式：执行时间很短的作业是在那些长作业的后面到达系统的话，则必须等待很长时间2短作业优先(ShortestJobfirst，SJF)方式选择那些估计需要执行时间最短的作业投入执行，为它们创建进程和分配资源。有可能使得那些长作业永远

5、得不到调度执行3响应比高者优先（HighestResponse-ratioNext，HRN)方式响应比R＝(W+T)／T＝1+W／TT：为估计需要的执行时间W：在后备状态队列中的等待时间作业调度时，系统计算每个作业的响应比，选择R最大者投入执行。长作业有机会获得调度执行(随着它等待时间的增加，W／T也就随着增加)。HRN的吞吐量小于SJF，由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法。系统开销增加：每次调度前要计算响应比。HRN是对FCFS方式和SJF方式的一种综合平衡。时间片轮转程序调度算法(RR）把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一

6、个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行本算法主要用于进程调度分时系统和事务处理系统中常用时间片轮转法利于CPU限制的进程，不利于I/O限制的进程时间片长度的确定时间片长度变化的影响过长－>退化为FCFS算法，进程在一个时间片内都执行完。过短－>用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。时间片长度的影响因素：就绪进程的数目：数目越多，时间片越小（当响应时间一定时）系统的处理能力：应当交互中使用户输入通常在一个时间片内能处理完优先级每个进程被赋予一个优先级，

7、每次调度选取就绪队列中优先级最高的进程投入运行*首先系统中设置多个就绪队列*每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大优先级越高时间片越小：2i*各个队列按照先进先出调度算法，最后一级时间轮转*一个新进程就绪后进入第一级队列*进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列*当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程降级就绪队列末尾*当第一级