第三章 中断与处理机调度

中断与中断系统

中断的概念

处理机在运行过程中，出现了某一事件，必须中止正在运行的程序，转去处理这个事件，然后再返回原来运行的程序，这一过程称为中断。

中断装置

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

• 识别中断源，当有多个中断源时，按紧迫程度排队；
• 保存现场；
• 引出中断处理程序。

中断源

引起中断的事件。

中断字

中断寄存器的内容。

强迫性中断

运行程序不期望的

• 时钟中断
• IO中断
• 控制台中断
• 硬件故障中断
  -power failure
  -内存校验错
• 程序性中断
  -越界，越权
  -缺页
  -溢出，除0
  -非法指令

自愿性中断

运行程序期望的

• 系统调用
  -fd=open(fname,mode)

• 访管指令
  -准备参数
  -svc n
  -取返回值

中断向量

中断向量：中断处理程序的运行环境与入口地址（PSW，PC）

• 每类中断事件有一个中断向量,
• 中断向量的存放位置是由硬件规定的,
• 中断向量的内容是OS在系统初始化时设置好的。

中断嵌套

• 一般原则：
  高优先级别中断可以嵌入低优先级中断

• 实现方法：
  中断响应后立即屏蔽不高于当前中断优先级的中断源。

系统栈

中断优先级

硬件规定的中断响应次序，依据:

• 紧迫程度；
• 处理时间。

中断屏蔽

• 高优先级中断事件处理不受低优先级中断打扰；
• 程序调整中断响应次序。

中断处理程序

考虑系统状态的进程状态转化图

程序性中断

只能由操作系统处理的中断

• 影响系统或其它进程
  越界，非法指令，（处理：终止进程、调试）
• 需要系统管理或协助
  页故障，缺段，（处理：动态调入）

可以由用户自己处理的中断

• 不影响系统和其它进程
  除0，溢出，（处理：用户处理，或OS处理）

处理机调度

考虑因素

考虑因素（scheduling criteria）

• CPU利用率 ; (max)
• 吞吐量 ; (max)
• 周转时间 ; (min)
• 响应时间 ; (min)
• 系统开销 ; (min)

调度参数

• 周转时间：完成时间-进入时间
  $T=t_f-t_s$T=tf​−ts​
• 平均周转时间：周转时间的平均值
  $\overline T=\frac{1}{n} (\sum\limits_{i=1}^{n}T_i)$T=n1​(i=1∑n​Ti​)
• 带权周转时间：周转时间/运行时间
  $W=\frac{T}{R}$W=RT​
• 平均带权周转时间：带权周转时间的平均值
  $\overline W=\frac{1}{n}(\sum\limits_{i=1}^{n}W_i)=\frac{1}{n}(\sum\limits_{i=1}^{n}\frac{T_i}{R_i})$W=n1​(i=1∑n​Wi​)=n1​(i=1∑n​Ri​Ti​​)

阵发期

下一个CPU burst的长度估算

• 令$T_n$Tn​是估计的第n个CPU阵发期的长度， $t_n$tn​的值是进程最近一次CPU阵发期长度，则有如下估算公式：
• $T_{n+1}=αt_n + (1-α)T_n$Tn+1​=αtn​+(1−α)Tn​
• 参数α(0≤α≤1)控制tn和τn在公式中起的作用：当α=0时，τn+1=τn；当α=1时，τn+1=tn。通常α取0.5。

剥夺式调度和非剥夺式调度

剥夺式：

• 就绪进程可以从运行进程手中抢占CPU。
• 进程运行,直到结束、等待或被抢先
  非剥夺式：
• 就绪进程不可从运行进程手中抢占CPU。
• 进程运行,直到结束或等待

先到先服务算法（FCFS）

优点：

• “公平”；
  缺点:
• 短作业等待时间长。

短作业优先（SJF）

优点：

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

最短剩余时间优先算法(SRTN)

相当于可剥夺的SJF

最高响应比优先(HRN)

• RR=(BT+WT)/BT=1+WT/BT
• 其中:
  BT=burst time
  WT=wait time
• 优点:
  同时到达任务, 短者优先
  长作业随等待时间增加响应比增加

最高优先数算法(HPF)

• 静态优先数(static)
  优先数在进程创建时分配，生存期内不变。
  响应速度慢，开销小。
  适合批处理进程
• 动态优先数(dynamic)
  进程创建时继承优先数，生存期内可以修改。
  响应速度快，开销大。
  适用于实时系统
• 非剥夺式静态优先数
  获得处理机的进程运行，直至终止或等待
• 剥夺式动(静)态优先数
  获得处理机的进程运行，直至终止、等待或出现高优先级的进程

由核心返回目态程序时，进程的PSW和PC为何必须用一条机器指令同时恢复？

循环轮转算法(RR)

适用于分时系统
基本轮转

• 时间片(quantum,time slice)长度固定，不变；
• 所有进程等速向前推进。
  改进轮转
• 时间片长度不定，可变。

时间片长度：

• 几十毫秒到几百毫秒(eg. 50ms)
• 过长：响应速度慢；
• 过短：系统开销(overhead)大。

多级队列算法(MLQ)

多级队列

• 多个就绪队列，进程所属的队列固定。
  

反馈排队算法

调度效果：

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

处理机调度时机

• 运行进程结束；
• 运行进程等待；
• 处理机被剥夺。

必然引起进程切换的中断

• 进程自愿结束, exit()
• 进程被强行终止；
• 非法指令，越界，kill
• 进程等待

可能引起进程切换的中断

• 时钟
• 设备I/O中断
• 系统调用

处理机调度过程

1. 保存下降进程的现场
   - 寄存器(PSW,PC,SP,通用寄存器,地址寄存器)PCB
2. 选择上升进程
   - 按处理机调度算法
3. 恢复上升进程的现场
   - PCB $\rightarrow$→寄存器
   - 先恢复通用寄存器和地址寄存器,最后恢复PSW,PC
   - PSW和PC必须用一条指令恢复

调度级别与多级调度

低级、中级和高级调度

• 处理机调度为低级调度
• 交换为终极调度
• 作业调度为高级调度

交换与终极调度

目标：控制并发度

并发度过高的危害

• 系统开销大
• 响应速度慢
• 内存等资源紧张
• 进程(线程)频繁进入等待状态
• More deadlocks
  

作业与高级调度

作业状态

• 提交: 输入机向输入井传送
• 后备: 在输入井,尚未进入内存
• 执行: 分解为进程,在内存处理
• 完成: 处理完毕,结果在输出井
• 退出: 由输出井向打印机传送

批处理作业调度：

1. 在后备作业集合中选择作业，并为其建立作业控制进程来处理该作业。
2. 对终止的作业控制进程进行善后处理。

适合批作业调度的算法

• 先到先服务算法(FCFS)
• 优先数调度算法(HPF)
• 短作业优先调度算法(SJF)
• 最高响应比优先调度算法(HRN)

不适合批作业调度的算法

• 时间片轮转算法(RR)
• 最短剩余时间优先(SRTN)
• 反馈排队算法(FB)

实时调度

实时任务

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

实时调度

合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度。

硬实时和软实时

硬实时(hard real-time): 必须满足任务截止期要求 .
软实时(soft real-time): 期望满足截止期要求

周期性和随机性

周期性: 每隔固定时间发生一次
随机性: 由随机事件触发，其发生时刻不确定

周期性实时事务

周期性实时事务可调度的必要条件:
令$C_i$Ci​为任务$P_i$Pi​处理时间，$T_i$Ti​为任务$P_i$Pi​的发生周期，则任务$P_1$P1​,…,$P_m$Pm​可调度的必要条件为$\sum\limits_{i=1}^{n}\frac{C_i}{T_i}\le1$i=1∑n​Ti​Ci​​≤1

最早截止期调度(EDF)

• 优先选择截止期最早的实时任务
• 可抢先
• 对EDF来说，可调度充分条件是：$\sum\limits_{i=1}^{n}\frac{C_i}{T_i}\le1$i=1∑n​Ti​Ci​​≤1
• 在不可调度的条件下，可使错过截止期任务最小化

速率单调调度(RMS)

• 面向周期性实时事务，非剥夺式
• 优先调度发生周期最短（频度最高）的实时任务
• 可调度条件：$\sum\limits_{i=1}^{n}\frac{C_i}{T_i}\le n(2^{\frac{1}{n}}-1)$i=1∑n​Ti​Ci​​≤n(2n1​−1)

EDF与RMS比较

• RMS可调度条件强于EDF
• RMS调度较EDF实现简单

多处理机调度

自调度

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

组调度

• 将一组相关(合作)的线程同时分派到多个处理机上运行
• 避免合作线程之间的相互等待
• 降低开销,提高运行效率