中断与处理机调度.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《中断与处理机调度.ppt》由会员分享,可在线阅读,更多相关《中断与处理机调度.ppt(73页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、3.2 处理机调度处理机调度3.2.1 处理机调度算法处理机调度算法n考虑因素(考虑因素(scheduling criteria)nCPU利用率利用率;(max)n吞吐量吞吐量;(max)n周转时间周转时间;(min)n响应时间响应时间;(min)n系统开销系统开销;(min)调度参数调度参数周转时间:完成时间周转时间:完成时间-进入时间进入时间平均周转时间:周转时间的平均值平均周转时间:周转时间的平均值带权周转时间:周转时间带权周转时间:周转时间/运行时间运行时间平均带权周转时间:带权周转时间的平均值平均带权周转时间:带权周转时间的平均值CPU burst vs.I/O burst n阵发期
2、阵发期:nCPU burst cycle:进程进程(线程线程)使用使用CPU计算;计算;nI/O burst cycle:进程进程(线程线程)使用设备使用设备I/O。n进程运行行为:进程运行行为:nCPU burst,I/O burst,CPU burst,I/O burst,nCPU调度:考虑处于调度:考虑处于CPU burst进程集合进程集合n CPU burst时间根据以前行为推定。时间根据以前行为推定。CPU burst vs.I/O burstn下一个下一个CPU burst的长度估算的长度估算n令令n是估计的第是估计的第n个个CPU阵发期的长度,阵发期的长度,tn的值是进程最近一次
3、的值是进程最近一次CPU阵发期长度,则有阵发期长度,则有如下估算公式:如下估算公式:nn+1=tn+(1-)nn参数参数(01)控制控制tn和和n在公式中起的作用:在公式中起的作用:当当=0时,时,n+1=n;当;当=1时,时,n+1=tn。通常通常取取0.5。剥夺式调度与非剥夺式调度剥夺式调度与非剥夺式调度n剥夺式剥夺式(preemptive)n就绪进程就绪进程可以可以从运行进程手中从运行进程手中抢占抢占CPU。n进程运行进程运行,直到结束、等待或被抢先直到结束、等待或被抢先n非剥夺式非剥夺式(non-preemptive)n就绪进程就绪进程不可不可从运行进程手中从运行进程手中抢占抢占CPU
4、。n进程运行进程运行,直到结束或等待直到结束或等待3.2.1.1 先到先服务算法先到先服务算法nFCFS(First Come First Serve)n按进程申请按进程申请CPU(就绪)的次序。(就绪)的次序。nProcess Arrival time Burst timenP1 0 27nP2 1 3nP3 2 5nCPU调度状况可用调度状况可用Gantt 图表示图表示0 27 30 35P1P2P33.2.1.1 先到先服务算法先到先服务算法(Cont.)进进程程到达到达时间时间运行运行时间时间开始开始时间时间完成完成时间时间周周转时间转时间带权带权周周转时间转时间P1027027271
5、P2132730299.67P3253035336.6平均周转时间平均周转时间 =(27+29+33)/3=29.67 平均带权周转时间平均带权周转时间 =(1+9.67+6.6)/3=5.76 0 27 30 35P1P2P33.2.1.1 先到先服务算法先到先服务算法(Cont.)n优点:优点:n“公平公平”;n缺点缺点:n短作业等待时间长。短作业等待时间长。3.2.1.2 短作业优先短作业优先nSJF(Shortest Job First)n按按CPU burst长度长度nProcess Arrival time Burst timen P1 0 12n P2 0 5n P3 0 7n
6、P4 0 3nGantt Chart0 3 8 15 27P1P2P3P43.2.1.2 短作业优先短作业优先0 3 8 15 27P1P2P3P4进进程程到达到达时间时间运行运行时间时间开始开始时间时间完成完成时间时间周周转时间转时间带权带权周周转时间转时间P10121527272.25P2053881.6P307815152.14P4030331平均周转时间平均周转时间 =(27+8+15+3)/4=13.25 平均带权周转时间平均带权周转时间 =(2.25+1.6+2.14+1)/4=1.753.2.1.2 短作业优先短作业优先n特点:特点:n假定所有任务同时到达,平均等待假定所有任务同
7、时到达,平均等待时间最短。时间最短。n长作业可能被饿死。长作业可能被饿死。3.2.1.3 最短剩余时间优先算法最短剩余时间优先算法(SRTN)n Shortest Remaining Time Nextn 可剥夺可剥夺SJFnProcess Arrival time Burst timen P1 0 12n P2 1 9n P3 3 6n P4 5 3nGantt图图P1P2P3P4P3P2P10 1 3 5 8 12 19 303.2.1.3 最短剩余时间优先算法最短剩余时间优先算法(Cont.)进进程程到达到达时间时间运行运行时间时间开始开始时间时间完成完成时间时间周周转时间转时间带权带权
8、周周转时间转时间P1012030302.5P219119182P33631291.5P4535831平均周转时间平均周转时间=(30+18+9+3)/4=15平均带权周转时间平均带权周转时间=(2.5+2+1.5+1)/4=1.75 平均等待时间平均等待时间(18+9+3+0)/4 7.5(ms)P1P2P3P4P3P2P10 1 3 5 8 12 19 30最高响应比优先最高响应比优先(HRN)nHighest Response Ratio NextnRR=(BT+WT)/BT=1+WT/BTn其中其中:nBT=burst timenWT=wait timen优点优点:n同时到达任务同时到达
9、任务,短者优先短者优先n长作业随等待时间增加响应比增加长作业随等待时间增加响应比增加3.2.1.5 最高优先数算法最高优先数算法(HPF)n静态优先数静态优先数(static)n优先数在进程创建时分配,生存期内不变。优先数在进程创建时分配,生存期内不变。n响应速度慢,开销小。响应速度慢,开销小。n适合批处理进程适合批处理进程n动态优先数动态优先数(dynamic)n进程创建时继承优先数,生存期内可以修改。进程创建时继承优先数,生存期内可以修改。n响应速度快,开销大。响应速度快,开销大。3.2.1.5 最高优先数算法最高优先数算法(Cont.)n非剥夺式优先数非剥夺式优先数n获得处理机的进程运行
10、,直至获得处理机的进程运行,直至n终止终止n等待等待n剥夺式优先数剥夺式优先数n获得处理机的进程运行,直至获得处理机的进程运行,直至n终止终止n等待等待n出现高优先级的进程出现高优先级的进程3.2.1.5 最高优先数算法最高优先数算法(Cont.)n可抢占CPUnProcess Arrival time Priority Burst timenP1 0 0 8nP2 2 1 5nP3 4 3 7nP4 0 2 3nP5 5 7 2nGantt Chart0 0 3 3 4 4 5 5 7 7 13 13 17 17 2525P1P4P2P2P3P3P53.2.1.5 最高优先数算法最高优先数算
11、法(Cont.)进进程程到达到达时间时间运行运行时间时间优优先先级级开始开始时间时间完成完成时间时间周周转时间转时间带权带权周周转时间转时间P10801725253.13P2251317153P347341391.29P40320331P55275721平均周转时间平均周转时间 =(25+15+9+3+2)/5=38.8 平均带权周转时间平均带权周转时间 =(3.13+3+1.29+1+1)/5=1.88 0 0 3 3 4 4 5 5 7 7 13 13 17 17 2525P1P4P2P2P3P3P53.2.1.5 最高优先数算法最高优先数算法(Cont.)n例子例子UNIX:preemp
12、tive+dynamic priority(可抢占(可抢占CPU动态优先数)。动态优先数)。n计算公式:计算公式:p_pri=min127,USER+p_cpu/16+p_nicen定义定义USER=100;np_cpu:运行进程每运行进程每20ms加加1(优先级降低)(优先级降低),其,其它进程每它进程每1200ms减减10(优先级提高);(优先级提高);np_nice:可以通过系统调用可以通过系统调用nice()修改的量:规修改的量:规定用户进程定用户进程020之间(低),系统进程之间(低),系统进程-20+20之间(高)。之间(高)。n调度时取调度时取p_pri最小的。最小的。3.2.1
13、.6 循环轮转算法循环轮转算法(RR)nRound Robin(RR)n基本轮转基本轮转n时间片时间片(quantum,time slice)长度固定,长度固定,不变;不变;n所有进程等速向前推进。所有进程等速向前推进。n改进轮转改进轮转n时间片长度不定,可变。时间片长度不定,可变。3.2.1.6 循环轮转算法循环轮转算法(Cont.)n时间片长度:时间片长度:几十毫秒几十毫秒 几百毫秒几百毫秒(eg.50ms)n过长:响应速度慢;过长:响应速度慢;n过短:系统开销过短:系统开销(overhead)大。大。n适应系统:适应系统:n分时分时3.2.1.6 循环轮转算法循环轮转算法(Cont.)n
14、 RR可抢占可抢占CPU调度:调度:time slice=4msnProcess Arriveral time Burst timenP1 0 17nP2 0 10 nP3 0 3n Gantt ChartP1P2P3P1P2P1P2P1P10 4 8 11 15 19 23 25 29 303.2.1.6 循环轮转算法循环轮转算法(Cont.)进进程程到达到达时间时间运行运行时间时间开始开始时间时间完成完成时间时间周周转时间转时间带权带权周周转时间转时间P1017030301.76P2010425252.5P303811113.67平均周转时间平均周转时间(30+25+11)/3=22 平均
15、带权周转时间平均带权周转时间(1.76+2.5+3.67)/3=2.64平均等待时间平均等待时间(13+15+8)/3 12(ms)P1P2P3P1P2P1P2P1P10 4 8 11 15 19 23 25 29 303.2.1.7 多级队列算法多级队列算法(MLQ)n多级队列多级队列n多个就绪队列,进程所属的队列固定。多个就绪队列,进程所属的队列固定。n例如:通用系统中:例如:通用系统中:n 队列队列1:实时进程就绪队列(:实时进程就绪队列(HPF)n 队列队列2:分时进程就绪队列:分时进程就绪队列(RR)n 队列队列3:批处理进程就绪队列:批处理进程就绪队列(HPF)3.2.1.8 反馈
16、排队算法反馈排队算法(FB)nFeed-Back:n多个就绪队列,进程所属队列可变。多个就绪队列,进程所属队列可变。运行运行s1时间片时间片运行运行s2时间片时间片.创建创建唤醒唤醒优优先先级级 时时间间片片运行运行sn时间片时间片Q1 (RR,HPF1)Q2 (RR,HPF2)Qn (RR,HPFn)3.2.1.8 反馈排队算法反馈排队算法(Cont.)n调度效果:调度效果:n 资源利用率高资源利用率高nP1等待等待P2占有的资源占有的资源R,P2释放释放R,分给分给P1,P1被唤醒被唤醒,进进入最高级队列入最高级队列,可尽早投入运行可尽早投入运行,使用资源使用资源R;n 响应速度快响应速度
17、快n交互式进程经常进入等待状态交互式进程经常进入等待状态(等待用户输入等待用户输入),一旦被唤醒一旦被唤醒(输入完成输入完成),进入最高级队列进入最高级队列,可尽快被调度选中可尽快被调度选中,投入运行投入运行,反反应及时;应及时;n 系统开销小系统开销小n计算量大的进程用完前面计算量大的进程用完前面n-1级时间片级时间片,没有处理完没有处理完,落入底落入底层队列层队列,调度频率下降调度频率下降,但每次获得较长的时间片。但每次获得较长的时间片。3.2.2 处理机调度时机处理机调度时机l运行进程结束;运行进程结束;l运行进程等待;运行进程等待;l核心级现场核心级现场=PCBl处理机被剥夺。处理机被
18、剥夺。l用户级现场用户级现场=PCB中断与处理机切换的关系中断与处理机切换的关系l中断是处理机切换的必要条件,但不是中断是处理机切换的必要条件,但不是充分条件充分条件l必然引起进程切换的中断必然引起进程切换的中断进程自愿结束进程自愿结束,exit()进程被强行终止;进程被强行终止;l非法指令,越界,非法指令,越界,killl可能引起进程切换的中断可能引起进程切换的中断时钟时钟系统调用系统调用3.2.3 处理机调度过程处理机调度过程ldispatcherl保存下降进程的现场保存下降进程的现场寄存器寄存器(PSW,PC,SP,通用寄存器通用寄存器,地址寄存器地址寄存器)PCBl选择上升进程选择上升
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中断 处理机 调度
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内