处理器调度
处理器调度
处理机调度的层次
根据分配对象的不同，分为三种层次：
- 高级调度（作业调度、长程调度）
- 调度对象：作业
- 根据某种算法，将后备作业调入内存
- 中级调度（交换调度、中程调度、均衡调度）
- 调度对象：进程是否进入内存
- 负责进程在主存和外存之间的换进换出（挂起与激活）
- 低级调度（进程调度、短程调度）
- 调度对象：进程（或内核级线程）
- 决定就绪队列哪一个可以获得处理机
高级调度（作业调度）
较多存在于多道处理系统中的概念
多道批处理系统：
多道：系统内可同时容纳多个作业。这些作业放在外存中，组成一个后备队列，系统按一定的调度原则每次从后备作业队列中选取一个或多个作业进入内存运行，运行作业结束、退出运行和后备作业进入运行均由系统自动实现，从而在系统中形成一个自动转接的、连续的作业流
成批：在系统运行过程中，不允许用户与其作业发生交互作用，即：作业一旦进入系统，用户就不能直接干预其作业的运行。
作业是什么?
作业（Job）：在某些操作系统中，作业（job）是计算机操作者（或是一个叫做作业调度器的程序）交给操作系统的执行单位。是用户一次请求计算机系统为它完成任务所进行的工作总和
作业的组织：作业 = 程序 + 数据 + 作业说明书
作业步（Job Step）：例如一个c语言程序（作业），需要经过编辑、编译、链接、才能执行，其中编译链接就是这个作业完成所需要的两个作业步
作业步之间的关系：
- 每个作业步运行的结果产生下一个作业步所需要的文件
- 一个作业步能否正确执行依赖于前一个作业步是否成功的完成
作业的控制流程：
装配就是链接，此时载入的库函数是静态库函数，在运行时载入的库函数是动态库函数
作业的类型
根据计算机对作业的处理方式不同，分为两类：
- 脱机作业（批处理作业）
- 使用作业控制语言来写一份作业控制说明书，规定如何控制作业的执行
- 联机作业（交互式作业或终端型作业）
- 使用OS提供的命令语言直接提出对作业控制要求
作业控制块JCB
在多道批处理系统中，为了感知作业的存在，为每一个作业都设立了一个作业控制块，记录了作业有关的信息
内容：
- 作业的基本情况：用户名、作业名、状态、使用的语言等等
- 作业的控制要求：控制方式、类型、优先数、操作顺序和出错处理
- 作业的资源要求：建立的时间、运行的事件、最迟完成的事件等等
作业的状态
一个作业的一生有四个状态：提交、后备（收容）、执行、完成
- 提交状态：通过终端设备向磁盘中输入作业信息
- 后备状态：作业的信息全部输入完毕（输入到输入井），等待作业调度
- 执行状态：被作业调度程序选中，分配资源，开始执行
- 完成状态：完成全部任务，进程撤销，做善后处理
他们之间的转换如图：
作业调度
作为用户来看：希望自己的作业运行时间短
作为系统来看：希望各个作业的平均周转时间尽量短
作业调度主要需要考虑两个问题：
- 接纳多少个作业：决定从后备队列中选取多少调入内存，取决于多道程序度（即决定多少个作业在内存中执行）
- 太少：资源利用率和吞吐率低
- 太多：运行时内存不足发生中断次数频增，导致平均周转时间延长
- 接纳哪些作业：决定从后备队列中选取哪些进入内存，取决于所采用的调度算法
- 先来先服务算法：简单
- 短作业优先：常用
- 基于作业优先级：较常用
- 响应比高者优先：比较好
低级调度（进程调度）
多道批处理、分时和实时系统都必须配置这级调度。
低级调度的任务
- 保存处理器的现场信息：PC、通用寄存器内容等送入PCB
- 按某种算法选取进程
- 把处理器分配给进程，由分派程序（Dispatcher）把处理器分配给进程
对应这三个任务，进程调度就有三个基本机制
- 上下文切换程序：负责进行现场信息的切换
- 分派器：按照预订的算法，将处理器分配给该进程
- 排队器：排成一个或者多个队列
进程调度方式
有两种方式：
非抢占方式：
一旦程序把处理机分配给该进程便让其一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程
- 优点：早期多使用这种方式，简单，系统开销小，适用于批处理系统
- 缺点：难满足紧急任务的要求，实时系统不宜采用
抢占方式：
按照一定的原则，将一个正在运行的进程的处理机分配给另一个进程
- 优先权原则：优先级别高的进程优先运行
- 短进程优先原则：新的短进程抢占长时间的进程
- 时间片原则：各进程按照预分配的时间片轮转运行，时间片使用完后，便重新调度
中级调度
为了提高内存利用率和系统吞吐量，将暂时不能运行的进程调到外存等待。
三种调度方式的比较
| 调度方式 | 区别 |
|---|---|
| 作业调度 | 运行频率最低，作业调度的周期较长 |
| 进程调度 | 运行频率最高，不宜太复杂，避免占用太多CPU时间 |
| 中级调度 | 介于两者之间 |
调度准则
面向用户的准则
周转时间
周转时间：从作业被提交开始，到作业完成为止
作业的周转时间有四个部分：
- 作业在外存后备队列的等待时间
- 进程在就绪队列的等待时间
- 进程在CPU上执行的时间
- 等待IO操作完成的时间
1 | 周转时间 = 结束时刻 - 提交时刻(到达时间) |
由此可得平均周转时间为：
注意：T是作业周转时间，n是作业个数
可以用于：
- 衡量不同调度算法对同一作业流的调度性能
- 平均T越小，该作业调度算法性能越好
- 等待时间越短，用户满意度越高
主要是批处理系统需要考虑的
带权周转时间
1 | W = T / Ts |
常用于：
- 衡量同一调度算法对不同作业流的调度性能(长短任务差别)
- 平均W越小，作业调度算法对该作业流的调度性能越好
主要是批处理系统需要考虑的
响应时间
响应时间：从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。
包括三部分：
- 从键盘输入的请求信息传送到处理机的时间。
- 处理机对请求信息进行处理的时间。
- 响应信息回送回终端显示器的时间。
主要是实时系统中需要考虑的
截止时间
截止时间：某任务必须开始执行的最迟时间或必须完成的最迟时间
主要是实时系统中需要考虑的
面向系统的准则
批处理、实时、分时操作系统都需要考虑的问题
资源利用率
1 | CPU的资源利用率 = CPU有效工作时间 / (CPU有效工作时间 + CPU空闲等待时间) |
公平性
对于相同类型的进程都获得相同合理的CPU时间，不同的类型按照紧要性来分配
平衡性
应使系统中的CPU及各种设备都处于忙碌状态，调度算法应该保持平衡性
策略强制执行
所制定的策略必须执行，受到延迟也要执行
不同系统考虑的因素
批处理操作系统
- 平均周转时间T（平均带权周转时间）短
- 系统吞吐量高
- 吞吐量：单位时间内完成的作业树，如果单纯为了提高吞吐量，应该多选短作业执行
- 处理器利用率高
- 单纯是为了提高CPU的利用率，应该多选用计算量大的作业运行
可以看出，这些要求之间是有矛盾的
分时系统
- 响应时间快
- 均衡性
- 均衡性：系统响应时间的快慢与作业的复杂性相适应
实时系统
截止时间的保证
- 对于HRT（Hard Real-time）硬实时操作系统必须使任务在确定的时间内完成
- 对于SRT（Soft Real-time）软实时操作系统能让绝大多数任务在确定时间内完成
可预测性
调度算法
先来先服务调度算法
既可以用于作业调度，也可以用于进程调度
FCFS（First Come First Server）：
系统按照先后顺序对作业或是进程进行排序，对于先进入后备队列或是就绪队列的作业或进程优先
例如：
我们由公式可以知道
服务时间 = 结束时间 - 开始时间周转时间 = 结束时间 - 提交时间带权周转时间 = 周转时间 - 服务时间
由此运算出各个值，我们发现，对于C来说，只需要运行1，但是却等待了100，对于同类型的调度算法，我们看W，发现C与D的差别非常大，对于与C是非常吃亏的
再看一个正常情况下的表：
对于E来说是非常不公平的
结论：
- 有利于长作业或进程
- 有利于CPU繁忙型作业，不利于IO繁忙型的作业
短作业（进程）优先算法
既可以用于作业调度，也可以用于进程调度
看到FCFS调度算法非常不利于短作业，所以推出了短作业优先算法
短作业优先算法（SJF或SPF）：服务时间短的作业或进程优先选择
例如：
我们看到：
- 除了第一个到达的作业外，都是按照服务时间短的先选的
结论：
- 适用：进程调度、作业调度
- 优点：易于实现，效率比较高，降低作业的平均等待时间。
- 缺点：
- 只照顾短作业而不考虑长作业的利益，长作业长时间等待而“饿死”。
- 未考虑作业的紧迫程度
- 需要预知作业的运行时间，估计执行时间不足，算法无法真正实现
- 人机无法交互
高优先权优先调度算法
既可以用于作业调度，也可以用于进程调度
HPF（Highest Priority First）：抢占式，静态优先级算法
总是把处理机分配给就绪队列中具有最高优先权的进程
分类：
- 非抢占式优先权调度算法：适用于批处理系统
- 抢占式优先权调度算法：适用于分时系统和实时系统
优先权的类型：
- 静态优先权：在创建时就已经确定
- 依据：进程类型、用户需求等等
- 优点：开销小
- 缺点：不精确
- 动态优先权：创建时创立一个优先权，优先数可以动态改变
- 优点：精确
- 缺点：开销大
抢占式优先算法：
从到达时间0开始，P1先运行，在时间为2时，优先权更大的P2（本题数字越小优先权越大），开始运行，直到所有的进程运行完毕
我们可以计算出：周转时间 = 结束时间 - 提交时间
- P1：
15 - 0 = 15 - P2：
10 - 2 = 8 - P3：
16 - 4 = 12（注意是结束时间-提交时间） - P4：
9 - 5 = 4 - 平均周转时间 ：
(15+8+12+4) / 4 = 39 / 4 = 9.75
高响应比优先调度算法
HRP（Highest Response Priority）：非抢占式，动态优先级算法
优先选取响应比值最大的作业。即兼顾等待时间长和运行时间短的作业，它是FCFS和SJF算法的结合。克服了饥饿状态，兼顾了长作业。
响应比：指作业的响应时间与作业估计运行时间的比值
响应比 = 响应时间 / 要求服务时间
= (等待时间 + 要求服务时间) / 要求服务时间
= 1+ 等待时间 / 要求服务时间
例如：
由于算法是非抢占式的，所以当A到达时，B还没到达，所以A到执行完都不用考虑其他进程，对于B也一样，直到B运行完毕后，发现CDE都到达，所以此时要动态计算优先级——响应比：
- C ： 等待时间
9 - 4，服务时间4，所以响应比为( (9-4)+4 ) / 4 =2.25 - D：响应比
( (9-6)+5)/5 = 1.6 - E：响应比
((9-8) + 2)/2 = 1.5
此时，发现C的优先级最高，所以优先运行C，在C运行完毕后，重新运算DE的优先级，再进行运行。
总结：
- 当等待时间相同时，要求服务时间短的进程会优先运行，此时类似于SPF
- 当要求服务时间一样时，等待时间长的进程会优先运行，此时类似于FCFS算法
- 等待时间越长，优先级会增加
基于时间片的轮转调度算法（RR）
分时系统中，为了满足系统对响应时间的要求，通常采用时间片轮转调度算法。
简单轮转法
把所有就绪进程按先后顺序（FCFS）形成一个就绪队列，就绪队列中的所有进程按时间片依次轮流获得处理机
关键在于时间片的大小的选择：
- 时间片很小，利于短作业执行，但是频繁的发生中断与进程上下文转换
- 时间片太长，退化为FCFS算法
- 时间片略大于一次典型的交互所需要的时间，可使大多数进程在一个时间片内完成。
- 根据进程要求系统给出应答的时间（T）和进入系统的进程数（N）来决定：
时间片大小q = T / N
- 根据进程要求系统给出应答的时间（T）和进入系统的进程数（N）来决定：
1 | 有五个任务A, B, C, D, E，它们几乎同时先后到达，预计它们运行时间为10，6，2，4，8min，采用时间片轮转算法，令时间片为2min，计算其平均进程周转时间。（进程切换可不考虑） |
优点：
- 简单、方便
缺点：
- 由于采用固定时间片的方式，调度欠灵活。
- 服务质量不够理想。
改进：
将固定时间片方式改为可变时间片方式
- 固定周期轮转法: 每一轮调度中所得的时间片q值的大小仅在这一轮调度中有效。系统的响应时间T固定，在每一轮调度中，根据当前就绪队列中的进程数n计算这一轮调度
- 时间片的大小取决于优先级的高低，优先级高的进程分得的时间片较大，优先级低的进程分得的时间片较小。
- 短作业的时间片较小，长作业的时间片较大
将单就绪队列改为多就绪队列。
多级反馈队列算法
前面的算法都需要知道进程的长度，如果未知进程需要服务的时间，那么都将无法使用，多级反馈队列算法可以不用事先知道进程的长度
示意图：
特点：
- 有多个队列，每个队列内使用FCFS算法，队列之间的优先级不同
- 从第一个队列到最后一个队列时间片逐渐增加，如果一个进程在一个时间片内未完成，那么它将被分配到下一个队列的队尾
- 最后一个队列使用简单轮转法