03 第三章 中断与处理机调度.pptx

第1页：第三章中断与处理机调度

3.1中断与中断系统3.2处理机调度3.3调度级别与多级调度3.4实时调度3.5多处理机调度3.5系统举例操作系统是中断驱动的！Interrupt driven

第2页：3.1 中断与中断系统

• 3.1 中断与中断系统
• 3.1.1 中断的概念
• 3.1.2 中断装置
• 3.1.3 中断处理程序

第3页：3.1.1 中断的概念

• 定义：程序在运行过程中出现某种紧急事件，必须中止正在运行的程序，转去处理这个事件，然后再恢复原来运行的程序，这一过程称为中断。
• 中断系统：
  • 中断装置(硬件)
  • 中断处理程序(软件)不见得是原来的程序

第4页：3.1.2 中断装置

定义

发现并响应中断的硬件机构。

工作步骤

⑴识别中断源，当有多个中断源时，按紧迫程度排队；⑵保存现场: (PSW, PC)=>系统栈；⑶引出中断处理程序。

第5页：3.1.2 中断装置（续）

• 3.1.2中断装置正运行的程序中断响应和处理的过程HALOS系统栈…………..…………..…………..top
• ①中断发生PSW, PC
• ②psw, pc中断处理程序(psw’, pc’)
• ③
• ④pc’
• ⑤⑥

第6页：3.1.2 中断装置（续3）

• 1.中断源与中断字
• 中断源：引起中断的事件。
• 中断寄存器保存与中断事件相关信息的寄存器。
• 中断字中断寄存器的内容。例：I/O中断：设备状态寄存器。

第7页：3.1.2 中断装置（续4）

• 2.中断类型与中断向量强迫性中断：运行程序不期望的
• 时钟中断
• I/O中断
• 控制台中断
• 硬件故障中断
  • power failure
  • 内存校验错
• 程序错误中断越界，越权，缺页/段溢出，除0非法指令(特权指令)自愿性中断：运行程序期望的
• 系统调用fd=open(fname,mode)
• 访管指令
  • 准备参数
  • svc n
  • 取返回值

第8页：3.1.2 中断装置（续5）

正在运行程序访管指令中断装置中断处理程序自愿性中断：SVC ntrap n中断装置中断处理程序时钟中断I/O中断控制台中断硬件故障中断程序错误中断强迫性中断：正在运行程序

第9页：3.1.2 中断装置（续6）

• 中断向量：中断处理程序的运行环境与入口地址(PSW, PC)。
• 每类中断事件有一个中断向量；
• 中断向量存放在内存的固定单元；
• 中断向量的内容是OS在系统初始化时设置好的。中断向量mode应为系统态

第10页：3.1.2 中断装置（续7）

PSW1, PC1时钟中断向量PSW2, PC2 I/O中断向量PSW3, PC3 console中断向量PSW4, PC4硬件故障中断向量PSW5, PC5程序错误中断向量… …PSWn, PCn访管中断向量00000008001600240032…0090时钟中断处理程序PC1:I/O中断处理程序PC2:访管中断处理程序PCn:…系统空间

第11页：3.1.2 中断装置（续8）

3.中断嵌套与系统栈

中断嵌套

中断处理过程中又响应了新的中断。

一般原则

高优先级别中断可以嵌入低优先级中断；因此，中断嵌套层数不会超过中断优先级的个数。

实现方法

中断响应后立即屏蔽不高于当前中断优先级的中断源。

第12页：1 目态中断嵌套与系统栈示意图系统栈

• 返回3.1.2.3中断嵌套与系统栈
• 系统栈
  • 位置由硬件确定；
  • 被中断程序的PSW和PC由硬件中断装置压入系统栈；
  • 中断处理程序保存其它现场信息。…………PSW1,PC1PSW2,PC2管态……PSW2,PC2中断返回栈顶指针............PSWk-1,PCk-1……PSWk,PCk管态中断……..中断返回……PSW1,PC

第13页：3.1.2 中断装置

• 4.中断优先级别与中断屏蔽
• 中断优先级别根据引起中断的重要性和紧迫程度，硬件将中断源分为若干个级别，称作中断优先级别。
• 硬件规定的中断响应次序
  • 先响应优先级别高的中断请求；
  • 优先级别相同的，硬件按系统规定好的次序响应。
• 中断屏蔽
  • 高优先级中断事件处理不受低优先级中断打扰；
  • 中断优先级是由硬件规定的，级别不能改变；但程序可以通过中断屏蔽调整中断响应次序。

第14页：3.1.2 中断装置（续）

3.1.3中断处理程序强迫性中断事件进一步保存现场信息到系统栈取出中断码分析中断产生原因转相应中断处理程序，如等待转dispatcher继续处理中断是否嵌套中断由系统栈恢复现场返回上层中断自愿性中断事件取出访管号分析系统调用类型需要切换进程由系统栈恢复现场返回目态程序转dispatcherTTFF关中断关中断进一步保存现场信息到系统栈开放高优先级别中断开放高优先级别中断关中断开放高优先级别中断关中断开中断？！

第15页：3.1.2 中断装置（续3）

3.1.3中断处理程序无终止运行kernel等待就绪运行user创建事件发生调度选中等待事件嵌套返回中断返回结束中断考虑系统状态的进程状态转换剥夺

第16页：3.1.3 中断处理程序

• 1.输入输出中断处理
• 正常结束
  • 继续传输；
  • 唤醒相关进程。
• 传输错误
  • 重复执行(eg. 3次,认定设备故障)；
  • 报告系统操作员。

第17页：3.1.3 中断处理程序（续）

2.时钟中断处理时钟分为硬时钟和软时钟。本质上，硬件时钟产生中断，软时钟只是完成某种处理。

①进程管理

分时系统的进程切换；重新计算进程调度参数(eg.动态优先数)；

②作业管理

记录作业等待时间及优先级别；

③资源管理

统计运行进程占用处理器等资源的时间；

④事件处理

实时系统中定时发控制信号；

⑤系统维护

定时启动死锁检测程序、定时记账；

⑥实现软时钟，启动定时程序硬时钟5ms发生一次中断，软时钟50ms.

第18页：3.1.3 中断处理程序（续3）

3.控制台中断处理控制台一个控制按键，产生一个中断信号，相当于一个操作命令，对应一个中断向量，转一个中断处理程序。

第19页：3.1.3 中断处理程序（续4）

• 4.硬件故障中断处理(1)电源故障处理
• 掉电：
  • 内存，寄存器→外存
  • 停止设备
  • 停止处理机
• 恢复：
  • 启动处理机
  • 启动设备
  • 外存→内存，寄存器Use UPS for criticalapplications

第20页：3.1.3 中断处理程序（续5）

• (2)主存故障处理
• 海明校验，奇偶校验错误
  • 下雨检查
  • 划出系统
  • 报告操作员

第21页：也可由用户自己处理

• 5.程序错误中断处理
• 只能由操作系统处理的中断
  • 影响系统或其它进程越界，非法指令，(处理：终止进程、调试)
  • 需要系统管理或协助页故障，缺段，(处理：动态调入)
• 可以由用户自己处理的中断不影响系统和其它进程：浮点数溢出、阶码下溢、除数为0等。3.1.3中断处理程序阶码上溢系统进行中断处理；阶码下溢系统将数的各位强置为

第22页：应用程序自己处理中断调试语句

应用程序自己处理中断调试语句：on <中断条件> goto<中断续元入口>例如：on <divide_zero> goto LA;除0中断时转LA处理除0中断时转LB处理on <divide_zero> goto LB除

第23页：应用程序自行处理中断编译时

应用程序自行处理中断编译时：生成中断续元表运行时：执行调试语句，填写中断续元表。中断时：根据中断原因查中断续元表，为0，用户未规定中断续元，由OS标准处理；非0，用户已规定中断续元，由用户处理。调试语句的处理方法：中断续元1入口中断续元1运行环境中断事件1：中断续元2入口中断续元2运行环境中断事件2：…………………………………………中断续元m入口中断续元m运行环境中断事件m：

第24页：应用程序自行处理中断编译时（续）

• 用户处理中断的过程(P58图3-10)
• （P58）图3-10步骤：
• ①发生溢出中断
• ②保存旧PSW和PC
• ③取中断向量
• ④转到中断处理程序
• ⑤访问中断续元表（假定非0）
• ⑥系统栈中现场转移到用户栈
• ⑦中断续元入口送寄存器（OS中断处理完成）
• ⑧执行中断续元
• ⑨用户栈PSW和PC送寄存器
• ⑩返回中断断点

第25页：应用程序自行处理中断编译时（续3）

• 硬件操作系统中断处理程序PC1系统栈……PSW,PC寄存器用户栈…………PSW’,LA……LA:用户程序…...iret中断续元表中断续元
• ①溢出中断
• ②PSW,PCPSW1, PC1③用户处理中断的过程
• ⑦
• ⑨
• ⑥PSW,PC
• ⑤
• ④⑧

第26页：3.1.3 中断处理程序

6.自愿性中断处理访管指令(SuperVisor Call)形式：准备参数SVC n取返回值系统调用(system call)形式：返回值=系统调用名称(实参1,…,实参n)参数和返回值的存放位置是由OS规定的

第27页：3.1.3 中断处理程序（续）

系统调用驱动表：(table driven)服务程序入口addr0…………addrm-1访管号：0……...m-1Eg. UNIX

第28页：3.2 处理机调度

• 3.2 处理机调度
• 3.2.1 处理机调度算法按什么原则分配
• 3.2.2 处理机调度时机何时重新分配
• 3.2.3 处理机调度过程如何完成分配

第29页：3.2.1 处理机调度算法考虑因素

(scheduling criteria)

①CPU利用率(max)：使CPU尽量处于忙碌状态；

②吞吐量(max)

Throughput单位时间内CPU处理计算任务的数量；

③周转时间(min)

turnaround time计算任务从就绪到处理完毕的时间；

④响应时间(min)

response time就绪到开始处理所用的时间；

⑤系统开销(min)

system overhead系统调度进程(线程)过程中所用的时间和空间。

第30页：3.2.1处理机调度算法调度参数计算周…

3.2.1处理机调度算法调度参数计算周转时间＝完成时间－进入时间Tc= Tf-Tr平均周转时间：周转时间的平均值Tc= (∑ Tci)带权周转时间＝周转时间/运行时间W =平均带权周转时间：带权周转时间的平均值W = (∑ Wi )= (∑ )i=1n1─n─Tc─Ri=1n1─n─i=1n1─nTci─Ri

第31页：3.2.1处理机调度算法调度参数计算周

调度参数计算等待时间＝周转时间－处理时间Tw= Tc-Tp3.2.1处理机调度算法等待时间是进程在就绪队列中耗费时间的总和。平均等待时间：等待时间的平均值Tw= (∑ Twi)i=1n1─n─

第32页：3.2.1 处理机调度算法

• 阵发期:
  • CPU burst cycle:进程(线程)使用CPU计算；
  • CPU burst timeis an assumption of how long aprocess requires the cpu between I/O waits.
  • I/O burst cycle:进程(线程)使用设备I/O。
• 进程运行行为：
  • CPU burst, I/O burst, CPU burst, I/O burst,…
• CPU调度：考虑处于CPU阵发期内的进程集合
  • CPU burst time根据以前行为推定。CPU burst vs. I/O burst

第33页：3.2.1 处理机调度算法（续）

• 下一个CPU burst time的长度估算，令
  • τn是估算的第n个CPU阵发时间的长度，tn是进程最近一次CPU burst时间，则有如下估算公式：
  • τn+1＝αtn＋(1－α)τn
  • 参数α(0≤α≤1)控制tn和τn在公式中起的作用：当α＝0时，τn+1＝τn；当α＝1时，τn+1＝tn3.2.1处理机调度算法τn包含过去的历史信息；tn包含了最近的信息。通常：α取0.5，表示历史信息和最近信息权重相当；τ0取所有进程CPU burst的平均值，比如取10。

第34页：3.2.1 处理机调度算法（续3）

• 剥夺式调度与非剥夺式调度剥夺式(preemptive)
• 就绪进程可以从运行进程手中抢占CPU。进程运行,直到结束、等待或被抢先；非剥夺式(non-preemptive)
• 就绪进程不可从运行进程手中抢占CPU。进程运行,直到结束或等待；

第35页：3.2.1.1 先到先服务算法

• 1.FCFS(First Come First Serve)非抢占式，不适合分时系统。
  • 按进程申请CPU（就绪）的次序。ProcessArrival timeBurst timeP1 0 27P2 1 3P3 2 5
  • CPU调度状况可用Gantt图表示:P3P2P10 27 30 35

第36页：3.2.1.1 先到先服务算法（续）

3.2.1.1先到先服务算法带权周转时间周转时间完成时间开始时间运行时间到达时间进程127270270P19.6729302731P26.633353052P3平均周转时间＝(27+29+33)/3=29.67平均带权周转时间＝(1+9.67+6.6)/3=5.76平均等待时间＝(0+26+28)/ 3＝18(ms)P3P2P10 27 30 35

第37页：3.2.1.1 先到先服务算法优点

：“公平”，不会出现饿死情况；缺点：短作业等待时间长，导致平均等待时间长。

第38页：3.2.1.2 最短作业优先算法

• 2.SJF(Shortest Job First)：可抢占、或非抢占将CPU分配给下一个CPU burst time最短的进程。通常通过估算方法来得到进程的下一个CPU burst time.
  • 按CPU burst长度ProcessArrival timeBurst timeP1 0 12P2 0 5P3 0 7P4 0 3
  • Gantt ChartP1P3P2P40 3 8 15 27

第39页：3.2.1.2 最短作业优先算法（续）

3.2.1.2最短作业优先算法带权周转时间周转时间完成时间开始时间运行时间到达时间进程2.25272715120P11.688350P22.141515870P3133030P4平均周转时间＝(27+8+15+3)/4=13.25平均带权周转时间＝(2.25+1.6+2.14+1)/4=1.75平均等待时间＝(15+3+8+0)/ 4＝6.5(ms)P1P3P2P40 3 8 15 27

第40页：3.2.1.2 最短作业优先算法（续3）

• 特点：
  • 假定所有任务同时到达，平均等待时间最短；
  • 长作业可能被饿死。

第41页：3.2.1.3 最短剩余时间优先算法

• (SRTN)3.Shortest Remaining Time Next
• 可剥夺SJF：CPU空闲或有新进程就绪ProcessArrival timeBurst timeP1 0 12P2 1 9P3 3 6P4 5 3
• Gantt图P1P2P3P4P3P2P10 1 3 5 8 12 1930

第42页：3.2.1.3 最短剩余时间优先…（续）

3.2.1.3最短剩余时间优先算法带权周转时间周转时间完成时间开始时间运行时间到达时间进程2.530300120P121819191P21.5912363P3138535P4平均周转时间=(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 1930

第43页：3.2.1.3 最短剩余时间优先算法

• ProcessArrival timeBurst timeP1 0 8P2 1 4P3 2 9P4 3 5
• Gantt图P3P1P4P2P10 1 5 10 17 26

第44页：3.2.1.3 最短剩余时间优先…（续）

3.2.1.3最短剩余时间优先算法P3P1P4P2P10 1 5 10 17 26带权周转时间周转时间完成时间开始时间运行时间到达时间进程2.131717080P1145141P22.6724261792P31.4710553P4平均周转时间=(14+4+24+7)/4=12.25平均带权周转时间=(2.13+1+2.67+1.4)/4=1.8平均等待时间＝(9+0+15+2)/ 4＝6.5(ms)

第45页：3.2.1.4 最高响应比优先算法

• (HRN)Highest Response Ratio Next
• 响应比计算公式RR=(BT+WT)/BT=1+WT/BT其中:
  • BT=burst time
  • WT=wait time
• 优点：先到先服务和短作业优先的折中
  • 先到的作业比新到的作业有较长的等待时间；
  • 同时到达任务,短者优先(由于BT小)；
  • 长作业随等待时间WT增加，响应比增加。因此，长作业不会饿死。每次调度选响应比大的作业

第46页：3.2.1.5 最高优先数优先算法

• (HPF)静态优先数(static)
• 优先数在进程创建时分配，生存期内不变；
• 响应速度慢，开销小；
• 适合批处理进程；
• 可能造成低优先数进程长期等待。动态优先数(dynamic)
• 进程创建时继承优先数，生存期内可以修改；
• 资源利用率高；公平性好；响应速度快；
• 开销大。适用于实时系统何时修改优先数？

第47页：3.2.1.5 最高优先数优先算法（续）

• 非剥夺式静态优先数获得处理机的进程运行，直至
  • 终止
  • 等待
• 剥夺式动(静)态优先数获得处理机的进程运行，直至
  • 终止
  • 等待
  • 出现高优先级的进程

第48页：3.2.1.5 最高优先数优先…（续3）

• 可抢占CPUProcessArrival timePriorityBurst timeP1 0 0 8P2 2 1 5P3 4 3 7P4 0 2 3P55 7 2
• Gantt ChartP1P2P3P5P3P2P40 3 4 5 7 13 17 25

第49页：3.2.1.5 最高优先数优先

3.2.1.5最高优先数优先算法P1P2P3P5P3P2P40 3 4 5 7 13 17 25带权周转时间周转时间完成时间开始时间优先级运行时间到达时间进程3.13252517080P1315173152P21.299134374P31330230P41275725P5平均周转时间=(25+15+9+3+2)/5=10.8平均带权周转时间=(3.13+3+1.29+1+1)/5=1.88平均等待时间=(17+10+2+0+0)/5=5.8

第50页：3.2.1.6 循环轮转算法

• (RR)Round Robin(RR)：适于分时系统；与FCFS类似，但可抢占；
• 基本轮转
  • 时间片(quantum,time slice)长度固定不变；
  • 就绪队列为FIFO进程队列，所有进程等速向前推进。
• 改进轮转时间片长度不定，可变。
• 时间片长度：几十毫秒几百毫秒(eg. 50ms)
  • 过长：响应速度慢；
  • 过短：系统开销(overhead)大。

第51页：3.2.1.6 循环轮转算法（续）

• RR可抢占CPU调度：time slice=4msProcessArriveral timeBurst timeP1 0 17P2 0 10P3 0 3
• Gantt ChartP1P1P2P1P2P1P3P2P10 4 8 11 15 19 23 25 29 30

第52页：3.2.1.6 循环轮转算法（续3）

3.2.1.6循环轮转算法带权周转时间周转时间完成时间开始时间运行时间到达时间进程1.7630300170P12.525254100P23.671111830P3平均周转时间＝(30+25+11)/3=22平均带权周转时间＝(1.76+2.5+3.67)/3=2.64平均等待时间＝(13+15+8)/ 3＝12(ms)P1P1P2P1P2P1P3P2P10 4 8 11 15 19 23 25 29 30

第53页：3.2.1.6 循环轮转算法（续4）

• RR讨论
  • 设就绪队列中有n个进程，时间片=q，则在每个q时间单位内，每个进程能获得CPU时间为q/n，每个进程必须等待(n-1)×q个时间单位才能轮到一个q；
  • q无限大，则RR策略与FCFS相同；q充分小，则RR策略称为处理机共享(Processor Sharing)。

第54页：3.2.1.7 分类排队算法

• (MLQ)
• 分类排队：Multi-Level Queues多个就绪队列，进程所属的队列固定。
• 例如，通用系统中：
  • Q1：实时进程就绪队列(HPF)；
  • Q2：分时进程就绪队列(RR)；
  • Q3：批处理进程就绪队列(HPF or FCFS).Higher PriortyLower Priorty

第55页：3.2.1.8 反馈排队算法

• (FB)
• Feed-Back:多个就绪队列，进程所属队列可变。也叫“多级反馈队列调度算法”Q1 ( RR, H P F1)Q2 ( RR, H P F2)运行S1时间片Qn ( RR, H P Fn)运行S2时间片…………………………………….运行Sn时间片创建唤醒优先级递增时间片递增

第56页：3.2.1.8 反馈排队算法（续）

• (FB)反馈排队调度方法：
• 进程创建或等待事件发生，进入一级就绪队列；
• 某队列进程获得CPU并使用完该队列时间片，若该进程尚未结束，则进入下一级就绪队列；
• 最后一级队列的进程获得CPU并使用完该队列时间片，若该进程尚未结束，则进入同一级队列；
• CPU空闲，选择第一级就绪队列进程，若该队列为空，则选择第二级队列进程，以此类推。

第57页：3.2.1.8 反馈排队算法（续3）

• 资源利用率高P1等待P2占有的资源R；P2释放R，分给P1；P1被唤醒,进入最高级队列,可尽早投入运行,使用资源R；
• 响应速度快交互式进程经常进入等待状态(等待用户输入)，一旦被唤醒(输入完成)，进入最高级队列，可尽快被调度选中，投入运行，反应及时；
• 系统开销小计算量大的进程用完前面n-1级时间片，没有处理完，落入底层队列，调度频率下降，但每次获得较长的时间片。

第58页：3.2.2 处理机调度时机处理机调度时机

• ：
• ⒈当进程从运行状态转换到等待状态时：I/O请求或者是等待一个子进程的终止；
• ⒉当进程从运行状态转换到就绪状态时(发生中断)；
• ⒊当进程从等待状态转换到就绪状态时(I/O完成)；
• ⒋当进程终止时(运行结束或故障强行终止)。进程切换：时刻T1进程P1运行，时刻T2进程P2运行，T2>T1，且P1≠P2，则称在T1和T2之间发生了进程切换，并称P1为下降进程，P2为上升进程。

第59页：3.2.2 处理机调度时机处理机…（续）

3.2.2处理机调度时机中断处理完毕，没有嵌套中断，即将返回目态。目态（Pi运行）目态（Pj运行）管态管态…...中断中断中断返回返回返回中断与系统状态Pi=Pj:未发生进程切换；Pi≠Pj:发生了进程切换。中断是进程切换的必要条件，但不是充分条件。

第60页：3.2.2 处理机调度时机

进程上下文

与进程相关的运行环境称为进程上下文，包括地址映射寄存器、通用寄存器状态以及SP、PSW、PC等；

进程切换

由一个进程上下文转换到另一个进程上下文的过程称为上下文切换，也称为进程切换。

第61页：3.2.2 处理机调度时机（续）

• 必然引起进程切换的中断
  • 进程自愿结束, exit()
  • 进程被强行终止：非法指令，越界，kill
  • 进程等待(资源、数据传输等)
• 可能引起进程切换的中断
  • 时钟
  • I/O中断信号

第62页：3.2.3 处理机调度过程

• 保存下降进程的现场系统栈→PCB
• 选择上升进程按处理机调度算法(可能需要“闲逛”进程)
• 恢复上升进程的现场PCB→寄存器
  • 先恢复通用寄存器和地址寄存器，最后恢复PSW，PC；
  • PSW和PC必须用一条指令恢复。中断响应和中断处理时已把下降进程现场保存在系统栈中。

第63页：3.3 调度级别与多级调度

• 3.3 调度级别与多级调度
• 3.3.1 交换与中级调度
• 3.3.2 作业与高级调度

第64页：3.3.1 交换与中级调度

• 术语
  • 交换(swapping)
  • 中级调度(mid-level scheduling)
  • 并发度(degree of multi-programming)
• 目标：控制并发度并发度过高：
  • 系统开销大；
  • 响应速度慢；
  • 内存等资源紧张；
  • 进程(线程)频繁进入等待状态；
  • More deadlocks

第65页：3.3.1 交换与中级调度（续）

3.3.1交换与中级调度就绪等待运行剥夺等待事件事件发生选中就绪挂起等待挂起无终止创建创建结束挂起解挂事件发生解挂挂起具有中级调度的进程状态转换

第66页：3.3.2 作业与高级调度

• 作业调度：又称高级调度或宏观调度。
  • 把作业由输入井调入内存，并建立进程使其能够运行；
  • 运行结束把作业运行结果转存到输出井。
• 作业状态:
  • 提交:输入机向输入井传送；
  • 后备:在输入井，尚未进入内存；
  • 执行:分解为进程，在内存处理；
  • 完成:处理完毕，结果在输出井；
  • 退出:由输出井向打印机传送。

第67页：3.3.2作业与高级调度状态转换

3.3.2作业与高级调度状态转换:

提交→后备

由SPOOLing输入进程完成Simultaneous Peripheral Operation On-Line

后备→执行

由高级作业调度(1)完成高级调度:系统进程

执行→完成

由作业调度(2)完成

完成→退出

由SPOOLing输出进程完成提交后备执行完成退出SPOOLing输入作业调度

第68页：3.3.2 作业与高级调度

1.批处理作业调度程序(1)：在后备作业集合中选择作业，并为其建立作业控制进程来处理该作业。作业调度程序(1)内存已有n道作业等待T输入井中有后备作业等待F访问磁盘中作业控制表根据作业控制块中控制参数按作业调度算法选择后备作业作业状态标志为“执行”为该作业建立作业控制进程

第69页：3.3.2 作业与高级调度（续）

2.批处理作业调度程序(2)对终止的作业控制进程进行善后处理。作业调度程序(2)有终止的作业控制进程等待F作业调度(1)等待完成撤销该作业控制进程，做善后处理取一终止的作业控制进程对应作业状态改为“完成”唤醒作业调度(1)TSpooling输出等待作业完成唤醒Spooling输出T

第70页：3.3.2 作业与高级调度作业调度算法

• ：
• 适合批作业调度的算法
  • 先到先服务算法(FCFS)
  • 优先数调度算法(HPF)
  • 短作业优先调度算法(SJF)
  • 最高响应比优先调度算法(HRN)
• 不适合批作业调度的算法
  • 时间片轮转算法(RR)
  • 反馈排队算法(FB)

第71页：3.4 实时调度

(Real-time Scheduling)

实时任务

具有明确时间约束的计算任务。

某时刻前必须开始处理；

某时刻前必须处理完毕。

实时调度

合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度。实时任务应该具有高优先级，而且不可改变；实时任务的处理时间应该很短。

第72页：3.4 实时调度（续）

• 实时任务分类
• 硬实时vs.软实时
  • 硬实时:必须满足任务截止期要求；
  • 软实时:期望满足截止期要求。
• 周期性vs.随机性
  • 周期性:每隔固定时间发生一次；
  • 随机性:由随机事件触发，其发生时刻不确定。

第73页：@B1@Ready time

• Ready time:就绪时间实时任务产生并可以开始处理的时间；
• Starting deadline:开始截止期实时任务最迟开始处理的时间；
• Processing time:处理时间实时任务处理所需要的处理器时间；
• Completion deadline:完成截止期实时任务处理最迟完成时间；
• Occurring frequency:发生频率实时任务单位时间内发生的次数；
• Occurring period:发生周期周期性实时任务发生的间隔时间。3.4实时调度术语解释实时任务的紧迫程度用优先级来表示。

第74页：3.4 实时调度发生周期

(ms)完成截止期(ms)处理时间(ms)就绪时间(ms)进程2020100A5050250B140 ms1301201101009080706050403020100例：两个周期性实时任务A1A2A3A4A5A6A7B1B2B3实时任务发生时序：

第75页：13.4 实时调度

• 周期性实时任务可调度的判断令Ci为任务Pi的处理时间，Ti为任务Pi的发生周期，Ci＜Ti，i = 1、2、…、n，则任务P1，…，Pn可调度的必要条件为：CiTi1≤∑ni =

第76页：3.4 实时调度

• 非周期性实时任务可调度的判断设非周期性实时任务Ai单位时间内任务到达的平均次数为λi，则任务Ai的平均到达时间间隔为1/λi，以1/λi作为Ai的平均周期。如果1/λi值较小(≤某个阈值)，即非周期性实时任务Ai发生的频率较高，且λi符合泊松分布，则可将Ai视为周期性实时任务来处理。
  • 每个非周期性实时任务Ai的处理时间Ci是可知的，如何给出Ai发生周期的估算值Ti。

第77页：3.4.1 最早截止期优先调度

• EDF(Earliest Deadline First)
  • 优先选择完成截止期最早的实时任务；
  • 可抢占。
• 对EDF来说，可调度充分条件是：nCiTi1≤∑i=1
• 在不可调度的条件下，可使错过截止期任务最小化。

第78页：3.4.1 最早截止期调度

周期性实时任务(P73表3-6)10/20 + 25/50 = 1可调度(不考虑开销)发生周期完成截止期处理时间就绪时间进程2020100A5050250B

第79页：43.4.1 最早截止期调度

例子: Earliest Deadline First0 10 20 30 40 50 60 70 80 90 100TimeA2A2 dlA3A3 dlA4A4 dlB1A1A1dlB1 dlB2A5B2 dlA5 dlA1B1A2B1A3B2A5B2A

第80页：43.4.1 最早截止期调度（续）

• 3.4.2速率单调调度RMS(Rate Monotonic Scheduling)
• 调度策略(提出于1973年)
  • 面向周期性实时任务，非剥夺式；
  • 优先调度发生周期最短(频度最高)的实时任务。
• 可调度条件：nCiTin ( 21/n–1 )≤∑i=1

第81页：43.4.1 最早截止期调度（续3）

RMS的上限值RMS vs. EDF1)RMS可调度条件强于EDF；2)RMS调度较EDF实现简单。3.4.2速率单调调度n ( 21/n–1 )n1.00.8280.7790.7560.7430.734...Ln2≈0.693123456...∞

第82页：1 周期进程序列如下

RMS例子：CiＴi进程20100A40150B100350C具体调度结果：B2A3A4C2B3A2C1B1A10 20 60 160 180 220 240 300 320 360 4603.4.2速率单调调度C1 C2 C3T1 T2 T3＋＋= 0.2 + 0.267 + 0.286= 0.753≤ 3 ( 21/3–1 ) = 0.779可调度。A1B1B3B2A2A3A4C

第83页：3.5 多处理机调度

问题：

Mprocesses (threads)

Nprocessors

SMP

Symmetric Multi-Processors

All processors are identical (homogeneous)

目标

load-sharing

Separate ready queue for each processor,

Not really balanced;

Common ready queueQfor all processors

each processor accessesQon its own,

master/slave assignment.

第84页：3.5.1 自调度

• (self scheduling)均衡调度(balanced scheduling)一个就绪队列(多处理机访问互斥)
• 优点
  • 不需要专门的处理机从事任务分派工作；
  • 任务分配均衡。
• 缺点
  • 当CPU较多时，就绪队列成为瓶颈；
  • 线程两次调度可能处于不同处理机；
  • 不能保证同组线程同时调度。

第85页：3.5.1 自调度（续）

就绪队列进程(线程)进程(线程)进程(线程)CPU

第86页：3.5.1 自调度（续3）

• 例子: Mach系统
  • 改进的自调度
  • 全局队列:系统一个；
  • 局部队列:每个CPU一个。
  • 调度时
  • 首先考虑局部队列捆绑的线程，可指定系统线程在确定的处理机上工作；
  • 然后考虑全局队列。

第87页：3.5.2 组调度

• (gang scheduling)
• 将一组相关(合作)的线程同时分派到多个处理机上运行
  • 避免合作线程之间的相互等待；
  • 降低开销，提高运行效率。
• 例子:Cm*
  • Task force (一组相关的计算)

第88页：3.5 系统举例

3.5.1 Linux进程调度3.5.2 Windows 2000/XP线程调度

第89页：@B1@三种特征进程

• 三种特征进程
  • Real-time FIFO
  • Real-time Round Robin
  • Timesharing
• Goodness-based scheduling
  • Priority：1～40 (缺省值20 )可通过nice(value)系统调用调整；value取值范围为(-20,20)之间；取priority = 20-value.
  • counter：进程尚可运行的剩余时间。3.5.1 Linux进程调度

第90页：@B1@counter

• counter
  • 对于运行进程来说，每隔一个时钟间隔(10ms，称为一个jiffy)，将counter减1；
  • 当所有就绪进程的counter下降到0时，重新计算所有进程(包括等待进程)的counter值。
• goodness计算方法
  • if(Real-time)goodness=1000+priority
  • if(Timesharing && counter=0)goodness=0
  • if(Timesharing && counter>0)goodness=counter+priority3.5.1 Linux进程调度

第91页：@B1@发生调度时刻

• 发生调度时刻
  • 运行进程的counter减至0；
  • 运行进程执行系统调用exit；
  • 运行进程因等待I / O、信号灯而被封锁；
  • 原来具有高goodness的进程被解除封锁。
• 调度效果
  • 实时优先于分时；
  • 交互和I / O进程优先于CPU进程。3.5.1 Linux进程调度

第92页：Linux对称多处理

• Linux对称多处理
• Linux2.0支持对称多处理
  • 进程或线程可以同时运行在多个处理机上；
  • 为保持核心非剥夺同步要求，SMP通过一个唯一的核心自旋锁(spin-lock)来保证任何时刻最多只有一个处理机执行核心代码。
• Linux2.1支持真正意义上的SMP
  • 将一个自旋锁分解为若干个相互独立的自旋锁，分别用于保护核心代码不相交的子集。3.5.1 Linux进程调度

第93页：Linux对称多处理（续）

• 3.5.1 Linux进程调度自旋锁(spin_lock):SMP系统中引入的新的锁机制，以解决不同处理器间的同步问题。自旋锁特点：
• 加锁进程用一个死循环测试锁的状态，直到成功的取得锁；
• 自旋锁避免了调用进程的挂起，用“旋转”来取代进程切换；
• 自旋锁所保护的“临界代码”一般都比较短，否则就会浪费过多的CPU资源。
• 获得自旋锁的CPU才能执行中断处理程序。

第94页：3.5.2 Windows 2000/…

• 3.5.2 Windows 2000/XP线程调度Main Features：
• Thread level scheduling;
• Real time + foreground + background;
  • real time: no deadline scheduling;
  • foreground: GUI window
  • background: non-interactive
• scheduling：Preemptive+dynamic priority+RR+Feed back;
• Symmetric Multi-Processor(SMP) support。

第95页：优先级别

• 优先级别：0(低)～31(高)
• 16个实时优先级(16-31)
  • 一些内核线程；
  • 应用程序提升为实时优先级需要有权限；
  • 不是真正意义上的实时调度。
• 15个可变线程优先级(1-15)
  • 基本优先级vs.当前优先级；
  • 可动态提升；
  • 运行完一个时间配额之后自动下降。
• 1个系统线程优先级(0)
  • 闲置优先级，系统级守护线程用。3.5.2 Windows 2000/XP线程调度

第96页：优先级别（续）

3.5.2 Windows 2000/XP线程调度31……1615……7……10Windows 2000的调度队列页面清0守护线程可变(用户)线程实时(系统)线程TCB1…TCBmRR调度实际优先级＝基本优先级＋浮动优先级优先级上浮优先级下降TCB1…TCBnRR调度不低于线程基本优先级

第97页：优先级提升

• 优先级提升
• 优先级提升
  • I / O操作完成；
  • 事件等待结束；
  • 前台进程中的线程完成一个等待操作；
  • 由于窗口活动而唤醒GUI线程；
  • 就绪超过一定时限，未获得处理机。
• 优先级提升不会超过15。3.5.2 Windows 2000/XP线程调度

第98页：抢占CPU

• 抢占CPU
• 抢占情形
  • 被唤醒线程优先级高于运行线程优先级；
  • 某线程的优先级动态变化。
• 被抢占线程
  • 回到相应就绪队列；
  • 时间配额
  • 实时线程：重新分配完整时间配额；
  • 其它线程：保持剩余配额。3.5.2 Windows 2000/XP线程调度

第99页：时间配额(quantum)

• 时间配额(quantum)
• 配额长度：6～36；
• 时钟中断(15ms)调整配额
  • 每运行15ms减3；
  • 2～12次时钟中断(30ms～180ms)配额用完。
• 配额用完后进入下一级就绪队列，优先级下降；优先级下降不会低于其基本优先级。3.5.2 Windows 2000/XP线程调度

第100页：时间配额(quantum)（续）

• SMP上的线程调度线程与CPU的亲合关系
• 每个进程有一个处理器亲合掩码，缺省为所有处理器的集合；
• 线程继承其进程的亲合掩码；
• 亲合掩码可以修改：
  • SetProcessAffinityMask,
  • SetThreadAffinityMask;3.5.2 Windows 2000/XP线程调度

第101页：SMP上的线程调度

• SMP上的线程调度
• 线程的理想处理器(Ideal processor)在内核线程控制块TCB中:
  • 首选处理器
  • 第二处理器
• 理想处理器确定
  • 线程创建时随机确定；
  • 分散各个线程与处理机对应关系；
  • 线程可修改SetThreadIdealProcessor.3.5.2 Windows 2000/XP线程调度

第102页：就绪线程的处理器选择顺序

• 就绪线程的处理器选择顺序
• 有空闲处理器
  • 首选处理器
  • 第二处理器
  • 当前执行处理器(正执行调度代码)
  • 由高到低顺序找空闲的处理器
• 无空闲处理器(可抢占)
  • 首选处理器
  • 第二处理器
  • 可运行编号最大处理器
• 进入相应就绪队列不能抢占，则进入相应的就绪队列3.5.2 Windows 2000/XP线程调度

第103页：就绪线程的处理器选择顺序（续）

• 处理器对就绪线程的选择空闲处理器调度
• 线程上次在此CPU上运行(二级缓冲利用)；
• 线程的理想处理器是该CPU；
• 处于就绪状态时间超过2个quantum；
• 优先级别大于等于24.3.5.2 Windows 2000/XP线程调度(Cont.8)

第104页：就绪线程的处理器选择顺序（续3）

• 1.进程切换时需要保存哪些现场信息？请尽量考虑完全。
• 2.进程切换时，上升进程的PSW和PC为何必须用一条机器指令同时恢复？
• 3.对如下三个实时任务:A.T1=100, C1=50;B.T2=200, C2=30;C.T3=500, C3=100.采用EDF算法和RMS算法是否可调度?如可调度，画出对应的Gantt图，否则说明原因。作业# 1