《中断与处理机调度.ppt》由会员分享，可在线阅读，更多相关《中断与处理机调度.ppt（73页珍藏版）》请在三一办公上搜索。
1、3.2 处理机调度,3.2.1 处理机调度算法,考虑因素（scheduling criteria）CPU利用率;(max)吞吐量;(max)周转时间;(min)响应时间;(min)系统开销;(min),调度参数,周转时间：完成时间-进入时间,平均周转时间：周转时间的平均值,带权周转时间：周转时间/运行时间,平均带权周转时间：带权周转时间的平均值,CPU burst vs.I/O burst,阵发期:CPU burst cycle:进程(线程)使用CPU计算；I/O burst cycle:进程(线程)使用设备I/O。进程运行行为：CPU burst,I/O burst,CPU burst,I/
2、O burst,CPU调度：考虑处于CPU burst进程集合 CPU burst时间根据以前行为推定。,CPU burst vs.I/O burst,下一个CPU burst的长度估算令n是估计的第n个CPU阵发期的长度，tn的值是进程最近一次CPU阵发期长度，则有如下估算公式：n+1=tn+(1-)n参数(01)控制tn和n在公式中起的作用：当=0时，n+1=n；当=1时，n+1=tn。通常取0.5。,剥夺式调度与非剥夺式调度,剥夺式(preemptive)就绪进程可以从运行进程手中抢占CPU。进程运行,直到结束、等待或被抢先非剥夺式(non-preemptive)就绪进程不可从运行进程手
3、中抢占CPU。进程运行,直到结束或等待,3.2.1.1 先到先服务算法,FCFS（First Come First Serve)按进程申请CPU（就绪）的次序。Process Arrival time Burst timeP1 0 27P2 1 3P3 2 5CPU调度状况可用Gantt 图表示,3.2.1.1 先到先服务算法(Cont.),3.2.1.1 先到先服务算法(Cont.),优点：“公平”；缺点:短作业等待时间长。,3.2.1.2 短作业优先,SJF（Shortest Job First)按CPU burst长度Process Arrival time Burst time P1
4、0 12 P2 0 5 P3 0 7 P4 0 3Gantt Chart,3.2.1.2 短作业优先,3.2.1.2 短作业优先,特点：假定所有任务同时到达，平均等待时间最短。长作业可能被饿死。,3.2.1.3 最短剩余时间优先算法(SRTN),Shortest Remaining Time Next 可剥夺SJFProcess Arrival time Burst time P1 0 12 P2 1 9 P3 3 6 P4 5 3Gantt图,3.2.1.3 最短剩余时间优先算法(Cont.),最高响应比优先(HRN),Highest Response Ratio NextRR=(BT+WT
5、)/BT=1+WT/BT其中:BT=burst timeWT=wait time优点:同时到达任务,短者优先长作业随等待时间增加响应比增加,3.2.1.5 最高优先数算法(HPF),静态优先数(static)优先数在进程创建时分配，生存期内不变。响应速度慢，开销小。适合批处理进程动态优先数(dynamic)进程创建时继承优先数，生存期内可以修改。响应速度快，开销大。,适用于实时系统,3.2.1.5 最高优先数算法(Cont.),非剥夺式优先数获得处理机的进程运行，直至终止等待剥夺式优先数获得处理机的进程运行，直至终止等待出现高优先级的进程,3.2.1.5 最高优先数算法(Cont.),可抢占C
6、PUProcess Arrival time Priority Burst timeP1 0 0 8P2 2 1 5P3 4 3 7P4 0 2 3P5 5 7 2Gantt Chart,3.2.1.5 最高优先数算法(Cont.),3.2.1.5 最高优先数算法(Cont.),例子UNIX：preemptive+dynamic priority（可抢占CPU动态优先数）。计算公式：p_pri=min127,USER+p_cpu/16+p_nice定义USER=100；p_cpu:运行进程每20ms加1（优先级降低），其它进程每1200ms减10（优先级提高）；p_nice:可以通过系统调用n
7、ice()修改的量：规定用户进程020之间（低），系统进程-20+20之间（高）。调度时取p_pri最小的。,3.2.1.6 循环轮转算法(RR),Round Robin(RR)基本轮转时间片(quantum,time slice)长度固定，不变；所有进程等速向前推进。改进轮转时间片长度不定，可变。,适用于分时系统,3.2.1.6 循环轮转算法(Cont.),时间片长度：几十毫秒几百毫秒(eg.50ms)过长：响应速度慢；过短：系统开销(overhead)大。适应系统：分时,3.2.1.6 循环轮转算法(Cont.),RR可抢占CPU调度：time slice=4msProcess Arriv
8、eral time Burst timeP1 0 17P2 0 10 P3 0 3 Gantt Chart,3.2.1.6 循环轮转算法(Cont.),3.2.1.7 多级队列算法(MLQ),多级队列多个就绪队列，进程所属的队列固定。例如：通用系统中：队列1：实时进程就绪队列（HPF）队列2：分时进程就绪队列（RR）队列3：批处理进程就绪队列（HPF）,3.2.1.8 反馈排队算法(FB),Feed-Back:多个就绪队列，进程所属队列可变。,运行s1时间片,运行s2时间片,.,创建唤醒,优先级 时间片,运行sn时间片,Q1(RR,HPF1),Q2(RR,HPF2),Qn(RR,HPFn),3
9、.2.1.8 反馈排队算法(Cont.),调度效果：资源利用率高P1等待P2占有的资源R,P2释放R,分给P1,P1被唤醒,进入最高级队列,可尽早投入运行,使用资源R；响应速度快交互式进程经常进入等待状态(等待用户输入),一旦被唤醒(输入完成),进入最高级队列,可尽快被调度选中,投入运行,反应及时；系统开销小计算量大的进程用完前面n-1级时间片,没有处理完,落入底层队列,调度频率下降,但每次获得较长的时间片。,Feed Back,3.2.2 处理机调度时机,运行进程结束；运行进程等待；核心级现场=PCB处理机被剥夺。用户级现场=PCB,中断与处理机切换的关系,中断是处理机切换的必要条件，但不是
10、充分条件必然引起进程切换的中断进程自愿结束,exit()进程被强行终止；非法指令，越界，kill可能引起进程切换的中断时钟系统调用,3.2.3 处理机调度过程,dispatcher保存下降进程的现场寄存器(PSW,PC,SP,通用寄存器,地址寄存器)PCB选择上升进程按处理机调度算法恢复上升进程的现场PCB 寄存器先恢复通用寄存器和地址寄存器,最后恢复PSW,PCPSW和PC必须用一条指令恢复,3.3 调度级别与多级调度,3.3.1 交换与中级调度Swapping and mid-level scheduling3.3.2 作业与高级调度Job and high-level schedulin
11、g,处理机调度为低级调度CPU scheduling=low level scheduling,3.3.1 交换与中级调度,术语交换(swapping)中级调度(mid-level scheduling)并发度(degree of multi-programming)目标：控制并发度并发度过高系统开销大响应速度慢内存等资源紧张进程(线程)频繁进入等待状态More deadlocks,3.3.1 交换与中级调度,剥夺,就绪,等待,运行,选中,等待事件,事件发生,就绪挂起,等待挂起,无,终止,创建,创建,结束,换出,换出,换入,换入,事件发生,UNIX的中级调度（sched#0),移入SRUN状态
12、进程如内存不够，移出SWAIT和SSTOP状态进程；如还不够，移出SSLEEP和SRUN状态进程；条件：待移入进程在外存时间=3秒；待移出进程在内存时间=2秒。,3.3.2 作业与高级调度,作业状态:提交:输入机向输入井传送后备:在输入井,尚未进入内存执行:分解为进程,在内存处理完成:处理完毕,结果在输出井退出:由输出井向打印机传送,3.3.2 作业与高级调度,状态转换:提交后备:由SPOOLing输入进程完成Simultaneous Peripheral Operation On-Line后备执行:由作业调度(1)(高级调度)完成高级调度:系统进程执行完成:由作业调度(2)完成完成退出:由S
13、POOLing输出进程完成,提交,后备,执行,完成,退出,SPOOLing输入,作业调度1,作业调度2,SPOOLing输出,作业控制块与作业表,JCB（Job Control Block）：作业存在的数据结构，其中保存系统对作业进行管理的全部信息作业标识所属用户作业状态调度参数输入井地址输出井地址资源需求进入时间处理时间完成时间SPOOling输入建立，作业调度使用，SPOOling输出撤销。,作业表,3.3.2 作业与高级调度(Cont.),批处理作业调度程序(1)：在后备作业集合中选择作业，并为其建立作业控制进程来处理该作业。,作业调度程序(1),内存已有n 道作业,等 待,T,输入井中
14、有后备作业,等 待,F,访问磁盘中JCB表根据调度参数按作业调度算法选择后备作业,作业状态标志为“执行”,为该作业建立作业控制进程,3.3.2 作业与高级调度(Cont.),2.批处理作业调度程序(2)对终止的作业控制进程进行善后处理。,作业调度程序(2),有终止的作业控制进程,等 待,F,作业调度(1)因内存有n道作业而等待,撤销该作业控制进程，做善后处理,取一终止的作业控制进程,对应作业状态改为“完成”,唤醒作业调度(1),T,Spooling输出等待作业完成,唤醒Spooling输出,T,作业调度算法,适合批作业调度的算法先到先服务算法(FCFS)优先数调度算法(HPF)短作业优先调度算
15、法(SJF)最高响应比优先调度算法(HRN)不适合批作业调度的算法时间片轮转算法(RR)最短剩余时间优先(SRTN)反馈排队算法(FB),3.4 实时调度(real-time scheduling),实时任务：具有明确时间约束的计算任务。Eg.某时刻前必须开始处理某时刻前必须处理完毕实时调度：合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度。,实时任务分类,硬实时 vs.软实时 硬实时(hard real-time):必须满足任务截止期要求.软实时(soft real-time):期望满足截止期要求.周期性 vs.随机性 周期性:每隔固定时间发生一次 随机性:由随机事件触发，
16、其发生时刻不确定,术语解释,Ready time:就绪时间Starting deadline:开始截止期Processing time:处理时间Completion deadline:完成截止期Occurring frequency:发生频率,周期性实时事务,周期性实时事务:令Ci为任务Pi处理时间，Ti为任务Pi的发生周期，则任务P1,Pm可调度的必要条件为：,周期性实时事务,例：T1=100,T2=200,T3=500(ms)C1=50,C2=30,C3=100(ms)C1/T1+C2/T2+C3/T3=0.5+0.15+0.2=0.851满足可调度的必要条件,周期性实时事务,10/20+
17、25/50=1,可调度(不考虑开销),例子,Process Arrival time Execution time completion deadline,A(1)A(2)A(3)A(4)A(5).B(1)B(2),020406080.050,10101010102525,20406080100.50100,3.4.1 最早截止期调度,EDF（Earliest Deadline First)优先选择截止期最早的实时任务可抢先可以证明：对EDF来说，可调度充分条件是：在不可调度的条件下，可使错过截止期任务最小化,例子:Earliest Deadline First,0 10 20 30 40 5
18、0 60 70 80 90 100 Time,A2,B1,A3,B2,A5,B2,A4,3.4.2 速率单调调度,RMS（Rate Monotonic Scheduling）提出于1973年面向周期性实时事务，非剥夺式优先调度发生周期最短（频度最高）的实时任务可调度条件：,RMS的上限值,RMS vs.EDFRMS可调度条件强于EDFRMS调度较EDF实现简单,RMS例子：,可调度，具体调度结果：,0 20 60 160 180 220 240 300 320 360 460,3.5 多处理机调度,问题：M processes(threads)N processorsSMP：symmetric
19、 multi-processorsall processors are identical(homogeneous)目标：load-sharingseparate ready queue for each processor,not really balanced;common ready queue Q for all processorseach processor accesses Q on its own,master/slave assignment.,3.5.1 自调度(self scheduling),均衡调度(balanced scheduling)一个就绪队列(多处理机访问互
20、斥)优点不需要专门的处理机从事任务分派工作任务分配均衡缺点当CPU较多时,就绪队列成为瓶颈线程两次调度可能处于不同处理机不能保证同组线程同时调度,自调度(self scheduling),就绪队列,进程(线程),进程(线程),进程(线程),CPU,CPU,CPU,自调度(self scheduling),例子:Mach,改进的自调度全局队列:系统一个局部队列:每个CPU一个调度时首先考虑局部队列然后考虑全局队列,3.5.2 组调度(gang scheduling),将一组相关(合作)的线程同时分派到多个处理机上运行避免合作线程之间的相互等待降低开销,提高运行效率例子:Cm*Task force
21、(一组相关的计算),3.6 系统举例,Linux进程调度Windows2000/XP线程调度UNIX进程调度（见第12章）,三种特征进程 Real-time FIFOReal-time Round RobinTimesharingGoodness-based schedulingpriority0-40,(缺省值20),可通过nice系统调用调整，nice(value)中value的取值范围为(-20,20)之间,取priority=20-value.counter进程尚可运行的剩余时间,3.6.1 Linux 进程调度,Linux 进程调度,counter对于运行进程来说，每个时钟间隔(10
22、ms，称为一个jiffy)，将counter减1 当所有就绪进程的counter配额下降到0时，重新计算所有进程(包括等待进程)的counter值 counter=(counter/2)+prioritygoodnessif(Real-time)goodness=1000+priorityif(Timesharing&counter=0)goodness=0if(Timesharing&counter0)goodness=counter+priority,Linux 进程调度,调度发生时刻：运行进程的counter减至0；运行进程执行系统调用exit;运行进程因等待I/O、信号灯而被封锁;原来
23、具有高goodness的进程被解除封锁.调度效果:实时优先于分时 交互和I/O进程优先于CPU进程,Linux 对称多处理,Linux2.0是支持对称多处理硬件的第一个Linux核心;进程或线程可以同时运行在多个处理机上.为保持核心非剥夺同步要求，SMP通过一个唯一的核心自旋锁(spin-lock)来保证任何时刻最多只有一个处理机执行核心代码,支持真正意义上的SMP：将一个自旋锁分解为若干个相互独立的自旋锁，分别用于保护核心代码不相交的子集.,3.6.2 Windows 2000/XP线程调度,Main Features：Thread level scheduling;Real time+fo
24、reground+background;real time:no deadline scheduling;foreground:GUI windowbackground:non-interactivePreemptive+dynamic priority+RR+Feed back;Symmetric Multi-Processor(SMP)support;,优先级别,16个实时优先级（16-31）一些内核线程应用程序提升为实时优先级需要有权限不是真正意义上的实时调度15个可变线程优先级（1-15）基本优先级线程基本优先级继承进程基本优先级,可上下浮动2如:进程基本优先级4,其线程基本优先级26
25、,当前优先级在基本优先级与15之间浮动可动态提升运行完一个quantum之后自动下降,不低于基本优先级1个系统线程优先级（0）,Windows优先级,实时(系统)线程,可变(用户)线程,页面清0守护线程,当前优先级,基本优先级(继承得到,上下浮动2,最低为1),(下浮),(上浮),优先级提升,优先级提升IO操作完成事件等待结束前台进程中的线程完成一个等待操作由于窗口活动而唤醒GUI线程就绪超过一定时限，未获得处理机优先级提升不会超过15,抢占CPU,抢先情形被唤醒线程优先级高于运行线程优先级；某就绪线程的优先级动态变化被抢先线程回到相应就绪队列时间配额实时线程：重新分配完整时间配额其它线程：保
26、持剩余配额,时间配额(quantum),配额长度：6-36时钟中断（15ms发生一次）减3，2-12次时钟中断（30ms-180ms）配额用完配额用完后进入就绪队列，优先级下降,SMP上的线程调度,线程与CPU的亲合关系每个进程有一个处理器亲合掩码，缺省为所有处理器的集合线程继承其进程的亲合掩码亲合掩码可以修改SetProcessAffinityMask,SetThreadAffinityMask;,SMP上的线程调度,线程的理想处理器（Ideal processor）首选处理器：第二处理器：（在内核线程控制块中）理想处理器确定线程创建时随机确定，分散各个线程与处理机对应关系。线程可修改Set
27、ThreadIdealProcessor,就绪线程对处理器的选择,有空闲处理器首选处理器第二处理器当前执行处理器（正执行调度代码）由高到低顺序找空闲的处理器无空闲处理器，考虑抢先首选处理器第二处理器可运行编号最大处理器不能抢先进入相应的就绪队列,处理器对就绪线程的选择,空闲处理器调度线程上次在此CPU上运行（二级缓冲利用）线程的理想处理器是该CPU处于就绪状态时间超过2个quantum优先级别大于等于24,作业#1,进程切换时需要保存哪些现场信息？请尽量考虑完全。由核心返回目态程序时，进程的PSW和PC为何必须用一条机器指令同时恢复？对如下三个实时任务:T1=100,C1=50;T2=200,C2=30;T3=500,C3=100.采用EDF算法和RMS算法是否可调度?如是画出对应的Gantt图,否则说明原因。,
