中断与处理器调度.ppt

第三章 中断与处理机调度,3.1 中断与中断系统 3.2 处理机调度 3.3 调度级别与多级调度 3.4 实时调度 3.5 多处理机调度 3.6 系统举例,操作系统是中断驱动的！ Interrupt driven,3.1 中断与中断系统,3.1.1 中断的概念 3.1.2 中断装置 3.1.3 中断处理程序,3.1.1 中断的概念,处理机在运行过程中，出现了某一事件，必须中止正在运行的程序，转去处理这个事件，然后再返回原来运行的程序，这一过程称为中断。 中断系统： 中断装置(硬件) 中断处理程序(软件),3.1.2 中断装置,发现并响应中断的硬件机构 识别中断源，当有多个中断源时，按紧迫程度排队； 保存现场； 引出中断处理程序。,中断响应和处理的过程,正运行程序 1 6,处理程序 4,PSW，PC,PC:,PSW, PC,系统桟,psw, pc,.,2,5,3,HAL,OS,中断,3.1.2.1 中断源与中断字,中断源 引起中断的事件。 中断寄存器 保存与中断事件相关信息的寄存器。 中断字 中断寄存器的内容。 例：IO中断：设备状态寄存器。,3.1.2.2 中断类型与中断向量,强迫性中断 运行程序不期望的 时钟中断 IO中断 控制台中断 硬件故障中断 power failure 内存校验错 程序性中断 越界，越权 缺页 溢出，除0 非法指令,自愿性中断 运行程序期望的 系统调用 访管指令 系统调用 fd=open(fname,mode) 访管指令 准备参数 svc n 取返回值,3.1.2.2 中断类型与中断向量,中断装置,中断处 理程序,运行程序 访管指令,运行程序,中断装置,中断处 理程序,clock,IO,console,Powerfailure,malfunction,强迫中断：,自愿中断：,SVC n trap n,3.1.2.2 中断类型与中断向量,中断向量：中断处理程序的运行环境与入口地址（PSW，PC） 每类中断事件有一个中断向量, 中断向量的存放位置是由硬件规定的, 中断向量的内容是OS在系统初始化时设置好的。,中断向量mode应为系统态,3.1.2.2 中断类型与中断向量,PSW1, PC1 时钟中断向量 PSW2, PC2 I/O中断向量 PSW3, PC3 console中断向量 PSW4, PC4 硬件故障 PSW5, PC5 程序错误 PSWn, PCn 访管中断向量,0000 0008 0016 0024 0030 0090,时钟中断 处理程序,PC1:,I/O中断 处理程序,PC2:,访管中断 处理程序,PCn:,系统空间,3.1.2.3 中断嵌套与系统栈,一般原则： 高优先级别中断可以嵌入低优先级中断 实现方法： 中断响应后立即屏蔽不高于当前中断优先级的中断源。,3.1.2.3 中断嵌套与系统栈,中断响应后一般需要进一步保存现场 关中断（屏蔽所有中断） 进一步保存现场（通用寄存器等） 开中断（或开放高优先级中断） . 中断处理 . 关中断（屏蔽所有中断） 恢复现场 开中断（或开放高优先级中断） 中断返回,3.1.2.3 中断嵌套与系统栈(Cont.), ,目态,PSW1: PC1, ,管态,PSW2: PC2, ,管态,PSWn: PCn,中断嵌套:,3.1.2.3 中断嵌套与系统栈(Cont.), PSWn-1 PCn-1 PSW2 PC2 PSW1 PC1,栈顶指针:,系统栈:,3.1.2.4 中断优先级与中断屏蔽,中断优先级： 硬件规定的中断响应次序，依据: 紧迫程度； 处理时间。 中断屏蔽： 高优先级中断事件处理不受低优先级中断打扰； 程序调整中断响应次序。,3.1.3 中断处理程序,强迫性中断,自愿性中断,保存现场信息 取中断字 分析中断原因,保存现场信息 取调用号 分析何种系统调用,中断处理 （如等待转dispatcher) 继续处理,嵌套中断,系统栈恢复现场 返回上层中断,需要切换进程,系统栈恢复现场 返回目态程序,转dispatcher,T,F,F,T,3.1.3.1 IO中断处理,正常结束 继续传输； 唤醒相关进程。 传输错误 复执（eg. 3次)； 报告系统操作员。,3.1.3.2 时钟中断处理,Housekeeping 进程管理 重新计算进程调度参数(eg. 动态优先数) 实现软时钟，启动定时程序 硬时钟5ms发生一次中断，软时钟50ms 考虑进程切换,3.1.3.3 控制台中断处理,一个控制按钮，一个中断向量，一个中断处理程序。,3.1.3.4 硬件故障处理,电源故障处理 掉电： 内存，寄存器外存 停止设备 停止处理机 恢复： 启动处理机 启动设备 外存内存，寄存器,Use UPS for critical applications,3.1.3.4 硬件故障处理(cont.),内存故障处理 海明校验，奇偶校验错误 划出系统 报告操作员,3.1.3.5 程序性中断的处理,只能由操作系统处理的中断 影响系统或其它进程 越界，非法指令，（处理：终止进程、调试） 需要系统管理或协助 页故障，缺段，（处理：动态调入） 可以由用户自己处理的中断 不影响系统和其它进程 除0，溢出，（处理：用户处理，或OS处理）,应用程序自己处理中断,调试语句：on 例如：on goto LA;,除0中断时转LA处理,除0中断时转LB处理,on goto LB,除0中 断续元,除0中 断续元,LA:,LB:,相同中断发生在不同位置 可采用不同处理方法,应用程序自行处理中断(Cont.),编译时：生成中断续元表：,中断续元入口0,中断续元入口1,中断续元入口n,中断事件0:,中断事件1:,中断事件n:,.,运行时：执行调试语句，填写中断续元表。 中断时：根据中断原因查中断续元表， 为0，用户未规定中断续元，由OS标准处理； 非0，用户已规定中断续元，由用户处理。,初始时均为0,步骤： （1）发生溢出中断 （2）保存旧PSW和PC （3）取中断向量 （4）转到中断处理程序 （5）访问中断续元表（假定非0） （6）系统栈中现场转移到用户栈 （7）中断续元入口送寄存器（OS中断处理完成） （8）执行中断续元 （9）用户栈PSW和PC送寄存器 （10）返回中断断点,3.1.3.6 自愿性中断的处理,访管指令（SuperVisor Call)形式： 准备参数 SVC n 取返回值,系统调用（system call)形式： 返回值=系统调用名称（实参1,实参n),参数和返回值和存放位置是由OS规定的。,3.1.3.6 自愿性中断的处理,系统调用驱动表：(table driven),Eg. UNIX,3.2 处理机调度,3.2.1 处理机调度算法 按什么原则分配 3.2.2 处理机调度时机 何时重新分配 3.2.3 处理机调度过程 如何完成分配,scheduling,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/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) 就绪进程不可从运行进程手中抢占CPU。 进程运行,直到结束或等待,3.2.1.1 先到先服务算法,FCFS（First Come First Serve) 按进程申请CPU（就绪）的次序。 Process Arrival time Burst time P1 0 27 P2 1 3 P3 2 5 CPU调度状况可用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 0 12 P2 0 5 P3 0 7 P4 0 3 Gantt Chart,3.2.1.2 短作业优先,3.2.1.2 短作业优先,特点： 假定所有任务同时到达，平均等待时间最短。 长作业可能被饿死。,3.2.1.3最高响应比优先(HRN),Highest Response Ratio Next RR=(BT+WT)/BT=1+WT/BT 其中: BT=burst time WT=wait time 优点: 同时到达任务, 短者优先 长作业随等待时间增加响应比增加,3.2.1.4 最高优先数算法(HPF),静态优先数(static) 优先数在进程创建时分配，生存期内不变。 响应速度慢，开销小。 适合批处理进程 动态优先数(dynamic) 进程创建时继承优先数，生存期内可以修改。 响应速度快，开销大。,3.2.1.4 最高优先数算法(Cont.),非剥夺式静态优先数 获得处理机的进程运行，直至 终止 等待 剥夺式动(静)态优先数 获得处理机的进程运行，直至 终止 等待 出现高优先级的进程,3.2.1.4 最高优先数算法(Cont.),可抢占CPU Process Arrival time Priority Burst time P1 0 0 8 P2 2 1 5 P3 4 3 7 P4 0 2 3 P5 5 7 2 Gantt Chart,3.2.1.4 最高优先数算法(Cont.),3.2.1.4 最高优先数算法(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: 可以通过系统调用nice()修改的量：规定用户进程020之间（低），系统进程-20+20之间（高）。 调度时取p_pri最小的。,3.2.1.5 循环轮转算法(RR),Round Robin(RR) 基本轮转 时间片(quantum,time slice)长度固定，不变； 所有进程等速向前推进。 改进轮转 时间片长度不定，可变。,适用于分时系统,3.2.1.5 循环轮转算法 (Cont.),时间片长度： 几十毫秒几百毫秒(eg. 50ms) 过长：响应速度慢； 过短：系统开销(overhead)大。 适应系统： 分时,3.2.1.6 多级队列算法(MLQ),多级队列 多个就绪队列，进程所属的队列固定。 例如：通用系统中： 队列1：实时进程就绪队列（HPF） 队列2：分时进程就绪队列 （RR） 队列3：批处理进程就绪队列 （HPF）,3.2.1.7 最短剩余时间优先(SRTN),Shortest Remaining Time Next 可剥夺SJF Process Arrival time Burst time P1 0 12 P2 1 5 P3 3 7 P4 5 3 Gantt图,3.2.1.7 最短剩余时间优先(SRTN),3. 2.1.8 反馈排队算法(FB),Feed-Back: 多个就绪队列，进程所属队列可变。,Q1（RR,HPF）,Q2（RR,HPF）,Qn（RR,HPF）,运行s1时间片,运行s2时间片,.,创建唤醒,优先级 时间片,运行sn时间片,3.2.1.8 反馈排队算法 (Cont.),调度效果： 资源利用率高 P1等待P2占有的资源R, P2释放R, 分给P1, P1被唤醒, 进入最高级队列, 可尽早投入运行, 使用资源R； 响应速度快 交互式进程经常进入等待状态(等待用户输入),一旦被唤醒(输入完成),进入最高级队列,可尽快被调度选中,投入运行,反应及时； 系统开销小 计算量大的进程用完前面n-1级时间片,没有处理完,落入底层队列,调度频率下降,但每次获得较长的时间片。,Feed Back,3.2.2 处理机调度时机,运行进程结束； 运行进程等待； 处理机被剥夺。,Pi=Pj: 未发生进程切换； PiPj: 发生了进程切换。,3.2.2 处理机调度时机(Cont.),必然引起进程切换的中断 进程自愿结束, exit() 进程被强行终止； 非法指令，越界，kill 进程等待 可能引起进程切换的中断 时钟 系统调用,3.2.3 处理机调度过程,dispatcher 保存下降进程的现场 寄存器(PSW,PC,SP,通用寄存器,地址寄存器)PCB 选择上升进程 按处理机调度算法 恢复上升进程的现场 PCB 寄存器 先恢复通用寄存器和地址寄存器,最后恢复PSW,PC PSW和PC必须用一条指令恢复,3.3 调度级别与多级调度,3.3.1 交换与中级调度 Swapping and mid-level scheduling 3.3.2 作业与高级调度 Job and high-level scheduling,处理机调度为低级调度 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状态进程 如内存不够， 移出SWAIT和SSTOP状态进程； 如还不够，移出SSLEEP和SRUN状态进程； 条件： 待移入进程在外存时间=3秒； 待移出进程在内存时间=2秒。,3.3.2 作业与高级调度,作业状态: 提交: 输入机向输入井传送 后备: 在输入井,尚未进入内存 执行: 分解为进程,在内存处理 完成: 处理完毕,结果在输出井 退出: 由输出井向打印机传送,3.3.2 作业与高级调度,状态转换: 提交后备: 由SPOOLing输入进程完成 Simultaneous Peripheral Operation On-Line 后备执行: 由作业调度(1)(高级调度)完成 高级调度: 系统进程 执行完成: 由作业调度(2)完成 完成退出: 由SPOOLing输出进程完成,提交,后备,执行,完成,退出,SPOOLing输入,作业调度1,作业调度2,SPOOLing输出,作业调度算法,适合批作业调度的算法 先到先服务算法(FCFS) 优先数调度算法(HPF) 短作业优先调度算法(SJF) 最高响应比优先调度算法(HRN) 不适合批作业调度的算法 时间片轮转算法(RR) 最短剩余时间优先(SRTN) 反馈排队算法(FB),3.4 实时调度(real-time scheduling),实时任务： 具有明确时间约束的计算任务。 Eg. 某时刻前必须开始处理 某时刻前必须处理完毕 实时调度： 合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度。,实时任务分类,硬实时 vs. 软实时 硬实时(hard real-time): 必须满足任务截止期要求 . 软实时(soft real-time): 期望满足截止期要求 . 周期性 vs. 随机性 周期性: 每隔固定时间发生一次 随机性: 由随机事件触发，其发生时刻不确定,术语解释,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 + 25/50 = 1, 可调度(不考虑开销),例子,Process Arrival time Execution time completion deadline,A(1) A(2) A(3) A(4) A(5) . B(1) B(2),0 20 40 60 80 . 0 50,10 10 10 10 10 25 25,20 40 60 80 100 . 50 100,3.4.1 最早截止期调度,EDF（Earliest Deadline First) 优先选择截止期最早的实时任务 可抢先 可以证明：对EDF来说，可调度充分条件是： 在不可调度的条件下，可使错过截止期任务最小化,例子: Earliest Deadline First,0 10 20 30 40 50 60 70 80 90 100 Time,A2,B1,A3,B2,A5,B2,A4,3.4.2 速率单调调度,RMS（Rate Monotonic Scheduling） 提出于1973年 面向周期性实时事务，非剥夺式 优先调度发生周期最短（频度最高）的实时任务 可调度条件：,RMS的上限值,RMS vs. EDF RMS可调度条件强于EDF RMS调度较EDF实现简单,RMS例子：,可调度，具体调度结果：,0 20 60 160 180 220 240 300 320 360 460,3.5 多处理机调度,问题： M processes (threads) N processors SMP：symmetric multi-processors all processors are identical (homogeneous) 目标：load-sharing separate ready queue for each processor, not really balanced; common ready queue Q for all processors each processor accesses Q on its own, master/slave assignment.,3.5.1 自调度(self scheduling),均衡调度(balanced scheduling) 一个就绪队列(多处理机访问互斥) 优点 不需要专门的处理机从事任务分派工作 任务分配均衡 缺点 当CPU较多时,就绪队列成为瓶颈 线程两次调度可能处于不同处理机 不能保证同组线程同时调度,自调度(self scheduling),就绪队列,进程(线程),进程(线程),进程(线程),CPU,CPU,CPU,自调度(self scheduling),例子: Mach, 改进的自调度 全局队列:系统一个 局部队列:每个CPU一个 调度时 首先考虑局部队列 然后考虑全局队列,3.5.2 组调度(gang scheduling),将一组相关(合作)的线程同时分派到多个处理机上运行 避免合作线程之间的相互等待 降低开销,提高运行效率 例子: Cm* Task force (一组相关的计算),3.6 系统举例,Linux进程调度 Windows2000/XP线程调度 UNIX进程调度（见第12章）,三种特征进程 Real-time FIFO Real-time Round Robin Timesharing Goodness-based scheduling priority 0-40, (缺省值20 ),可通过nice系统调用调整 ，nice(value)中value的取值范围为(-20,20)之间 ,取priority=20-value. counter 进程尚可运行的剩余时间,3.6.1 Linux 进程调度,Linux 进程调度,counter 对于运行进程来说，每个时钟间隔(10ms，称为一个jiffy)，将counter减1 当所有就绪进程的counter配额下降到0时，重新计算所有进程(包括等待进程)的counter值 counter= (counter/2) + priority goodness if(Real-time)goodness=1000+priority if(Timesharing & counter=0)goodness=0 if(Timesharing & counter0)goodness=counter+priority,Linux 进程调度,调度发生时刻： 运行进程的counter减至0； 运行进程执行系统调用exit ; 运行进程因等待I/O、信号灯而被封锁 ; 原来具有高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 + foreground + background; real time: no deadline scheduling; foreground: GUI window background: non-interactive Preemptive + dynamic priority + RR + Feed back; Symmetric Multi-Processor(SMP) support;,优先级别,16个实时优先级（16-31） 一些内核线程 应用程序提升为实时优先级需要有权限 不是真正意义上的实时调度 15个可变线程优先级（1-15） 基本优先级 vs. 当前优先级 线程基本优先级继承进程基本优先级, 可上下浮动2 如: 进程基本优先级4, 其线程基本优先级26, 当前优先级在215范围内变动. 可动态提升 运行完一个quantum之后自动下降, 不低于基本优先级 1个系统线程优先级（0）,优先级提升,优先级提升 IO操作完成 事件等待结束 前台进程中的线程完成一个等待操作 由于窗口活动而唤醒GUI线程 就绪超过一定时限，未获得处理机 优先级提升不会超过15,抢占CPU,抢先情形 被唤醒线程优先级高于运行线程优先级； 某线程的优先级动态变化 被抢先线程 回到相应就绪队列 时间配额 实时线程：重新分配完整时间配额 其它线程：保持剩余配额,时间配额(quantum),配额长度：6-36 时钟中断（15ms发生一次）减3，2-12次时钟中断（30ms-180ms）配额用完 配额用完后进入就绪队列，优先级下降,SMP上的线程调度,线程与CPU的亲合关系 每个进程有一个处理器亲合掩码，缺省为所有处理器的集合 线程继承其进程的亲合掩码 亲合掩码可以修改 SetProcessAffinityMask, SetThreadAffinityMask;,SMP上的线程调度,线程的理想处理器（Ideal processor） 首选处理器： 第二处理器：（在内核线程控制块中） 理想处理器确定 线程创建时随机确定， 分散各个线程与处理机对应关系。 线程可修改SetThreadIdealProcessor,就绪线程对处理器的选择,有空闲处理器 首选处理器 第二处理器 当前执行处理器（正执行调度代码） 由高到低顺序找空闲的处理器 无空闲处理器，考虑抢先 首选处理器 第二处理器 可运行编号最大处理器 不能抢先进入相应的就绪队列,处理器对就绪线程的选择,空闲处理器调度 线程上次在此CPU上运行（二级缓冲利用） 线程的理想处理器是该CPU 处于就绪状态时间超过2个quantum 优先级别大于等于24,作业 #1,进程切换时需要保存哪些现场信息？请尽量考虑完全。 由核心返回目态程序时，进程的PSW和PC为何必须用一条机器指令同时恢复？ 对如下三个实时任务: T1=100, C1=50; T2=200, C2=30; T3=500, C3=100. 采用EDF算法和RMS算法是否可调度?如是画出对应的Gantt图,否则说明原因。,