处理机管理 处理机调度
1、处理机调度层次
处理器调度可分为三个级别：
- 高级调度（作业调度、长程调度）
- 中级调度（内存调度）
- 低级调度
低级调度是各类操作系统中必须具有的功能
在纯粹的分时或实时操作系统，作业被直接调入内存，因此通常不需要高级调度
在分时系统或具有虚拟存储器的操作系统中，专门引进了中级调度，控制进程在内存和外存间的对换
2、调度算法选择原则
任何层次的处理器调度，都由操作系统的调度程序实施，调度程序（scheduler）所使用的算法称为调度算法
“效益优先，兼顾公平原则”
调度算法设计通常应考虑如下原则/目标：
- 资源利用率
- 吞吐率
- 公平性
- 响应时间
- 周转时间
- 截至时间的保证
- 优先权原则
（1）资源利用率
-
CPU利用率 = CPU有效工作时间/CPU总的运行时间
-
CPU总的运行时间 = CPU有效工作时间+CPU空闲等待时间
（2）吞吐率
单位时间内CPU处理的作业数
- 长作业多：吞吐率低
- 短作业多：吞吐率高
（3）公平性
确保每个用户每个进程获得合理的CPU份额或其他资源份额，不会出现饿死情况
（4）响应时间
交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间
包括三部分时间：
- 请求信息传到处理机的时间
- 处理机处理请求信息的时间
- 形成的响应回送到终端的时间
使响应时间尽可能的短，是分时系统衡量调度性能的一个重要指标
（5）作业周转时间
作业周转时间：批处理用户从作业提交给系统开始，到作业完成为止的时间间隔
- 如果作业 i 提交给系统的时刻是 t s，完成时刻是 t f，该作业的周转时间 t i为：
t i = t f – t s - 实际上，它是作业在系统里的等待时间与运行时间之和
使作业周转时间或平均作业周转时间尽可能短，是批处理系统衡量调度性能的一个重要指标
| |
|
（6）截止时间保证
截止时间：指某个任务必须开始执行的最迟时间或必须完成的最迟时间，是评价实时系统调度性能的一个重要指标
（7）优先权
实时、分时、批处理均可遵循的原则，让一些紧急的任务尽快被执行
3、作业的管理与调度
（1）作业和进程的关系
-
作业是用户提交给操作系统计算的一个独立任务。每个作业必须经过若干相对独立，且相互关联的顺序加工步骤才能得到结果。其中每个加工步骤称为一个作业步。
进程是已提交完毕并选中运行的作业的执行实体，也是为完成作业任务向系统申请和分配资源的基本单位，它处于运行、就绪、等待等多个状态的变化之中，在CPU上推进。最终完成应用程序任务。 -
作业是任务实体，进程是完成任务的执行实体。没有作业任务，进程无事可做，没有进程，作业任务无法完成。作业的概念更多的用于批处理操作系统中啊，而进程则用于各种多道程序设计系统。
（2）批处理作业
- 批处理作业的输入
- 批处理作业的建立
- 批处理作业的调度
- 选择作业
- 分配资源
- 创建进程
- 作业控制
- 后续处理
（3）交互式作业
交互作业的组织、提交和控制与批处理作业的差别：
- 生命周期，由用户决定
- 作业情况和资源需求通过具体命令来提交和控制
- 输入一条/一组命令，则创建一个/若干进程来完成
具体的键盘命令：
- 作业控制类
- 资源申请类
- 文件操作类
- 目录操作类
- 设备控制类
4、低级调度的功能和类型
（1）调度程序的任务
调度程序担负两项任务：
- 调度：确定就绪进程/线程使用处理器的次序
- 分派：确定如何时分复用CPU
（2）低级调度类型
- 剥夺方式（preemptive），抢占式：
- 当一个进程正在处理器上执行时，系统可以根据规定的原则剥夺分配给它的处理器，而把处理器分配给其他进程使用
- 有两种常见的剥夺原则：高优先级剥夺原则和时间片剥夺原则，前者高优先级进程或线程可以剥夺低优先级进程或线程运行，后者当运行进程时间用完后被剥夺处理器
- 非剥夺方式（nonpreemptive），非抢占式：
- 一旦某个进程或线程开始执行后便不再出让处理器，除非该进程或线程运行结束或发生了某个事件不能继续执行
区别：
5、作业调度和低级调度算法
（1）FCFS：先来先服务算法
| |
|
|
（2）SJF：最短作业优先算法
| |
|
兼顾最近信息与历史信息
历史越久远，对估算值影响越小
（3）SRTF：最短剩余时间优先算法
| |
|
（4）HRRF：响应比高者优先算法
如果服务时间相同，则优先权取决于等待时间，待长作业等待时间足够长后，也将获得足够高的响应比
| |
|
（5）PS：优先级调度算法(Priority Scheduling)
实现方式
- 剥夺式 ：SRTF（静态优先）
- 非剥夺式：SJF（静态优先），HRRF（动态优先）
（6）RR：轮转调度算法
- 基本轮转法：它要求每个进程轮流运行一个相同的时间片
- 改进的轮转法：对于不同的进程给以不同的时间片；时间片的长短可以动态地修改等等
（7）MLFQ：多级反馈队列调度算法
多级反馈队列调度（反馈循环队列或多队列策略）
- 主要思想：是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。处理器调度每次先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。同一队列中的进程按先来先服务原则排队。开始工作时，每当一个新进程进入内存后，首先进入高优先级队列等候调度，若能在该级队列的一个时间片内执行完成，则撤离系统，否则进入低一级的队列等候调度，队列级别越低，时间片就越大，低优先级队列中的进程获得调度时运行的时间就长一些
- 多级反馈队列如图所示：