处理机管理-进程的调度

《处理机管理-进程的调度》由会员分享，可在线阅读，更多相关《处理机管理-进程的调度（52页珍藏版）》请在金锄头文库上搜索。

1、软件技术基础,制作 主讲,段景山,段景山,处理机管理,进程的调度,2,处理机的管理功能分为： 进程的描述 进程的控制 进程的同步 进程的通信 进程的调度,处理机管理,3,第四章 进程的调度,第二篇 操作系统,进程调度的模型,进程调度的算法,死锁及解决,4,进程调度引言,引言 处理机调度的主要目的：分配处理机 调度影响的因素： 响应的及时性 进程是否能在限定时间内获得处理机，对用户进行响应 周转时间（等待时间+使用CPU时间） 进程是否等待时间太长 系统吞吐量（进程时间+系统开销） CPU是否总是用在刀刃上,5,调度类型,4.1调度的类型与模型 4.1.1调度类型 从调度层次： 高级调度 低级调

2、度 中级调度 从OS类型： 批处理、分时、实时、多处理机调度,6,作业调度,（1）高级调度作业调度 对象： 外存上后备队列中的作业 动作： 调入内存、创建进程、分配资源、新进程进入就绪队列 决策内容： 接纳作业量、作业类型,其它,作业成批进入,输入井,输出井,内存,CPU,高级调度,7,进程调度,（2）低级调度进程调度 对象： 就绪队列中的进程 动作： 决定由哪个进程获得CPU 调度方式： 非抢占式 抢占式,低级调度 进程并发执行,其它,作业成批进入,输入井,输出井,内存,CPU,高级调度,8,进程调度过程,进程调度对象：就绪队列中的进程 进程调度功能及过程 纪录当前进程的状态、保存CPU现场

3、 选取适当的就绪进程 进程调度算法 分配处理机：恢复选取进程的现场,CPU,就绪队列,交互用户,1,2,3,进程调度,9,进程调度方式,进程调度的方式 非抢占式（非剥夺式） 现运行进程的CPU使用权不能被中途强行剥夺 除非进程主动放弃 抢占式（剥夺式） 系统按照某种原则剥夺现行进程的CPU使用权 将CPU使用权分配给其他进程 抢占原则 优先权原则 时间片原则 短进程优先原则,10,中级调度,（3）中级调度 对象： 外存中因暂时不能运行而被挂起的进程 动作： 将外存挂起的进程激活，调入内存，进入就绪队列 目的： 提高内存利用率,11,单级调度队列模型,4.1.2调度队列模型,阻塞队列,交互用户,

4、阻塞,进程调度是最基本的调度， 必须配置,1)单级调度模型,CPU,进程调度,就绪队列,结束,时间片完/被中断,唤醒,12,二级调度队列模型,2）二级调度模型,CPU,就绪队列,阻塞队列,时间片完,阻塞,唤醒,进程调度,作业调度,在批处理或类似系统中 需要从外存后备队列中调入作业,13,3）三级调度模型,CPU,就绪队列,阻塞队列,时间片完,阻塞,唤醒,挂起,挂起,事件出现,外存阻塞队列,外存就绪队列,配置中级 调度机制 可以提高 内存利用率,进程调度,作业调度,中级 调度,14,进程调度原因,4.1.3进程调度原因（调度时刻）,阻塞队列,交互用户,阻塞,进程调度,就绪队列,结束,时间片完,唤

5、醒,现进程运行完毕,现进程阻塞,优先权高的进程进入就绪队列,现进程“超时”,/被中断,CPU,15,进程调度算法准则,4.2调度算法 从多个目标（就绪进程）中选取一个 算法准则,面向用户,面向系统,周转时间,响应时间,截止时间,优先权,系统吞吐量,处理机利用率,各类资源的利用,短,快,保证,可设置,大,高,平衡,16,进程调度算法类型,算法类型,简单的调度算法,先来先服务算法,短进程优先,轮转法,等时间片轮转,不等时间片轮转,优先权法,抢占式优先权,非抢占式优先权,静态优先权,动态优先权,多级反馈队列算法,17,FCFS,1）先来先服务算法FCFS 按照就绪进程进入就绪队列的先后次序进行调度

6、简单易实现 利于长进程，CPU繁忙型作业 不利于短进程 排队时间相对过长,CPU,就绪队列,1,2,3,18,SCBF,2）短进程优先算法 对系统服务时间需求短的进程优先被调度 短进程估算： 依赖于前一周期的实际CPU时间和估计时间 系统性能改善，平均带权周转时间优于FCFS 不利于长作业，当不断有短进程到达时，不保证长进程响应的及时性，甚至可能得不到调度,其中 n为估计的第n个CPU 周期。tn 为实际值。 为控制值，0 1，常取 0.5,19,典型如分时系统，从用户敲键到字符显示在用户终端屏幕上,调度算法评价指标,响应时间RT（Response Time） 从提交一个请求开始到计算作出响应

7、，显示结果在屏幕上,RT q N,q：时间片大小,20,调度算法评价指标,周转时间（Trunaround Time）,进程第一次进入就绪队列到进程运行结束的时间间隔,TT 等待时间(WT) 服务时间(ST),平均周转时间（ATT）,系统各进程周转时间的平均值,ATT TT / N,带权周转时间（QTT）,进程周转时间与系统服务时间的比值,QTT = TT / 服务时间,平均带权周转时间（AQTT）,例,AQTT = QTT / N,21,调度算法比较例,例：A请求系统服务时间5s，B请求系统服务时间为100s， 设第0到第5秒前，CPU运行C进程。 第1秒时B进入系统内存，第2秒时A进入内存

8、当CPU空闲，需要调度进程时根据不同的算法选择A或B 问：分别计算FCFS算法下和SCBF算法下，A和B的周转时间，带权周转时间和系统平均周转时间,B,A,22,FCFS算法先来先服务 A：周转时间为 3+100+5108s 带权周转时间为108/5 20.4 B：周转时间为 4100104s 带权周转时间为104/100 1.04 平均带权周转时间为(20.4 +1.04)2 10.72 SCBF算法短进程优先 A：周转时间为 3+59s 带权周转时间为8/5 1.6 B：周转时间为 4+5+100109s 带权周转时间为109/100 1.09 平均带权周转时间为(1.6+1.09)2 1

9、.345,调度算法比较例,先调度B 后调度A,先调度A 后调度B,调度顺序,调度顺序,23,RR等时间片,3）等时间片轮转 保证人机交互的及时性 （1）按照FCFS顺序从就绪队列选取进程 （2）每个进程分配给相同的CPU时间片 （3）时间片到后将进程排到就绪队列尾 公平性的保证 响应及时性的保证,24,RR时间片,时间片q的选择,q,N,T,q：时间片大小,T：响应时间,N：就绪队列进程数,=,q,N,T,=,当N一定时：,q与T成正比。,q不能太大,当T一定时：,q与N成反比,q不能太小,保证响应时间,减少开销,25,RR不等时间片,4）不等时间片轮转法 短时间片满足快速响应的需要 长时间片

10、使周转时间降低 在保证及时响应的基础上，为不同的需求分配大小不等的时间片降低周转时间,长进程,短进程,I/O频繁型,CPU密集型,长时间片,短时间片,引入“前台”、“后台”,提高系统资源利用率,课 堂 练 习,26,前、后台调度,“前台”、“后台”进程调度 进程分为前台和后台两种。 前台：频繁和用户交互的进程，要求及时响应。如，支持界面的进程。 后台：需要大量时间运行，与用户交互较少的进程。如，查病毒进程。可见Windows系统右下角的驻留进程。 只要前台就绪队列里有进程，就不会调度后台进程。 前台进程按时间片轮转，后台进程按FCFS调度（也可按时间片轮转）,27,前、后台调度,“前台”、“后

11、台”进程调度 前台进程主要与用户交互，除了及时响应外，大量的时间都在等待用户的输入或向用户输出 后台进程可利用前台进程交互的间隙执行运算 这样，即不会因为执行繁重计算工作的进程影响了界面的及时响应，又不会因为频繁与用户交互而使系统无法完成负荷重的工作。,28,HPF,5）最高优先权调度算法（HPF） 保证实时性。（事件响应的及时性） （1）为每个进程设置优先级 （2）调度时选取优先级最高的进程，相同优先级的进程按照FCFS选取 抢占式调度： 高优先权的进程进入就绪队列时引起调度 非抢占式调度： 高优先权的进程进入就绪队列仅引起队列重排,29,HPF,优先级与优先数 易混淆的概念 优先级：高、低

12、 优先数：大、小 在某些系统中：优先机高的，优先数反而小。,30,HPF静态优先权,静态优先权 进程的优先权在进程创建时设定，以后不会改变 优先权设定的一般依据： （1）进程类型 （2）进程对资源的需求 （3）根据用户的需求,优先级设定后可能造成低优先权的进程得不到运行的机会,当不断有高优先进程进入就绪队列时,31,HPF动态优先权,动态优先权 进程的优先权在系统周转过程中动态改变,就绪等待进程优先级随等待时间以速率升高,执行进程的优先级以速率下降,优先权,=,等待时间,+,要求服务时间,要求服务时间,等待时间一定：优先权与要求服务时间成反比,要求服务时间一定：优先权与等待时间成正比,短进程优

13、先,优先权低的进程也能有运行的机会,32,多级反馈队列,6）多级反馈队列调度 综合各种算法长处 设计思想 设置多个就绪队列 各队列优先级不一样， 分配的时间片也不一样，高优先权队列进程的时间片较小 调度算法 （见后）,33,多级反馈队列算法,短时间片,长时间片,（1）在选取进程时，选取高优先权队列里的进程。 分配给相应的时间片。同一队列按照FCFS,（2）进程使用完时间片后，回到就绪态是则进入低一级优先权队列,（3）当高优先权队列里没有进程时，才调度低优先权队列进程,（4）进程创建后进入最高优先权队列,优先级调度,时间片轮转,动态优先权、不等时间片,34,多级反馈队列性能,多级反馈队列的性能

14、（1）短进程 在第一级队列的时间片中完成， 满足及时响应和短进程的周转要求 （2）动态变化的优先权 使优先权低的进程也得到执行的机会 （3）动态变化的时间片 长进程在长时间等待后获得长时间片，可减少周转时间和系统开销,35,死锁,4.3死锁问题（dead lock） 例：,P( s1 ),P( s2 ),临界区,V( s2 ),V( s1 ),P( s2 ),P( s1 ),临界区,V( s1 ),V( s2 ),进程1,进程2,就绪,就绪,执行,执行,阻塞,s1,s2,阻塞,状态：,状态：,死锁,36,死锁,死锁 当两个或两个以上进程因竞争资源而无休止地处于相互等待状态 死锁将使进程已占用的

15、资源的不到利用 严重情况下，死锁“蔓延”开，会导致“死机”,Proc1,s2,Proc2,s1,37,死锁原因,4.3.1死锁原因 资源不够 进程推进顺序不当 死锁解决方法初探 法一：预先让进程获得所有的资源 法二：改变进程推进顺序按序使用资源 在进程内部解决 法三：改变系统调度进程的顺序 在进程外部，系统中解决,P(s1),P(s2),.,V(s2),V(s1),P(s2),P(s1),.,V(s1),V(s2),进程1 P(s1),进程1,进程2,死锁,进程2 P(s1),进程1 P(s2),进程2 P(s2),阻塞进程2,阻塞进程1,38,死锁原因,死锁解决方法初探 法一：预先为进程分配足够资源 资源利用率极低 法二：改变进程推进顺序 各进程申请资源的顺序完全一致。 很难约束进程行为 法三：改变系统调度进程的顺序 如何界定正确的系统推进顺序？,进程1 P(s1),进程1 P(s2),进程2 P(s2),进程1,进程2,39,死锁的解决,如何解决死锁问题？ 开环： 从破坏产生问题的必要条件入手 不使问题出现 闭环： 允许问题存在，研究问题的检测和解除方法,40,死锁产生的必要条件,4.3.2死锁产生的必要条件 死锁和“资源”密切相关 1）资源访问的互斥条件 2）请求和保持