处理机调度
字数
3596 字
阅读时间
14 分钟
一、处理机调度的基本概念
在选择调度算法时，需要考虑算法的特性（一）算法选择的重要指标
1. CPU利用率
- CPU是计算机中最重要的资源之一，所以应尽可能使CPU保持忙碌的状态，使这一资源的利用率最高
- CPU利用率是指CPU处于忙碌状态占所有状态的比例
2. 系统吞吐量
- 表示单位时间内CPU完成作业的数量
3. 周转时间
- 周转时间：从作业提交到作业完成所经历的时间
- 平均周转时间：多个作业周转时间的平均值
- 带权周转时间：作业周转时间与作业实际运行时间的比值
- 平均带权周转时间：多个作业带权周转时间的平均值
4. 等待时间
- 等待时间：进程处于等待处理机状态的时间之和
5. 响应时间
- 响应时间：用户从提交请求到系统首次产生相应所用的时间
- 在交互式系统中，一般采用响应时间作为衡量调度算法的重要准则之一
（二）调度的层次
作业，即用户在计算机系统中完成一个任务的过程。
作业由程序、数据及作业说明书组成，一个作业从进入系统到退出系统一般要经过提交、后备、执行、完成这4个状态。
1.提交状态：作业通过用户由输入设备进入输入系统。
2.后备状态：作业提交后，由系统为该作业建立作业控制块(JCB，JobContrd Block)，并把它插入后备作业队列中，等待作业调度程序的调度。
3.执行状态：后备状态的作业若被作业调度选中，并且分配了必要的资源，由作业调度程序建立相应的进程。
4.完成状态：当作业执行结束后，进入作业完成状态。此时，由作业调度程序对该作业进行善后处理，主要表现为撤消作业的作业控制块，并回收此作业占用的系统中的资源数。最后，将作业的结果输出到外设之中。1. 作业调度（高级调度）
- 按照一定的原则从外存中处于后备状态的作业中挑选一个或者多个作业，为它们分配内存、I/O资源等必要资源，并建立相应的进程（分配PCB），以使它们获得竞争处理机的权利
- 作业由外存调入内存中
- 后备队列（外存）
分配资源，建立进程，从创建态变为就绪态，进入就绪队列（内存）
2. 内存调度（中级调度）
- 作用：提高内存利用率和系统吞吐量
- 将挂起的作业从外存调回内存中
- 引入虚拟内存后，OS可以将暂时不用的进程放到外存中（该进程进入挂起状态），等到空闲时再将其重新调入内存，通过不断地调入调出，内存调度的频率比作业调度的频率高
- 暂时调到外存等待的进程状态为挂起状态。值得注意的是，PCB并不会一起调到外存，而是会常驻内存。PCB中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到的挂起队列中。（注：这个PCB是仍然放在内存中的）
3. 进程调度（低级调度）
- 按照某种方法和策略从就绪队列（内存）中选取一个进程，将处理机（CPU）分配给它，使该进程由就绪态变为运行态
- 进程调度的频率是三种调度方法中最高的
进程的七状态模型
（三）进程调度方式
1. 非剥夺调度方式（非抢占方式）
- 只允许进程主动放弃CPU，在运行过程中，即便有更为紧迫的进程到达，该进程仍会继续使用CPU，直到该进程终止或主动要求进入阻塞态时，才会将CPU让给其他进程
- 系统开销更小，但无法及时处理更加紧急的任务
2. 剥夺调度方式（抢占方式）
- 当某一优先级更高的进程进入就绪队列并需要使用CPU，那么正在使用CPU的进程将会被动地放弃CPU，将CPU让给更为紧迫的进程使用
- 能够提高系统吞吐量和响应效率
（四）进程调度的时机
- 当前进程主动放弃处理机
- 进程正常终止（执行完毕）
- 进程运行过程中发生异常而终止
- 进程主动请求阻塞（如：请求系统分配资源等）
- 当前进程被动放弃处理机
- 分配给当前进程的时间片用完
- 有更紧急的事件需要处理，如：I/O事件，I/O中断等等
- 有更高优先级的进程进入就绪队列（抢占式）
注意！！！
进程在操作系统内核程序临界区中不能进行调度和切换 -------（对） 进程处于临界区时不能进行处理机调度 -------（错）
- 因为内核程序临界区一般会将访问内的临界资源上锁，导致其他内核程序无法调度，而就绪队列也被锁了，所以无法访问就绪队列，也就无法进行进程调度[1]
（五）调度算法（这几种算法都可能在大题中出现，需要进行做题练习）[2]
周转时间 = 完成时间 - 提交时间(或：到达时间)
带权周转时间 = 周转时间/运行时间(/表示除号)抢占式算法
只有时间片轮转调度算法和多级反馈队列调度算法是抢占式的算法
1. FCFS算法（先来先服务算法）
- 算法思想：按照作业/进程到达的先后顺序进行调度
- 适用情况：可用于作业调度，也可用于进程调度
- 作业调度：先调度系统中等待时间长的作业
- 进程调度：每次调度会从就绪队列中选取最先进入该队列的进程，为其分配CPU
- 优缺点：
- 优点：算法实现简单
- 缺点：对长作业有利，对短作业不利（长作业的带权周转时间更短，短作业的带权周转时间更长，短作业更容易处于
饥饿状态）- 长作业：运行时间长的作业
2. SJF算法（短作业优先算法）
- 算法思想：按照作业的长短来计算优先级，作业越短，其优先级越高
- 适用情况：可用于作业调度，也可用于进程调度
- 作业调度：作业越短，优先级越高
- 进程调度：进程越短，即：需要的服务时间（运行时间）越短，其优先级就越高
- 优缺点：
- 对短作业有利，可以获得
最短的平均等待时间和平均周转时间 - 缺点：
- 必须事先知道作业的运行时间
- 对长作业不利，会出现
饥饿现象 - 没有考虑作业的紧迫程度
- 对短作业有利，可以获得
3. 优先级算法
- 算法思想：基于进程/作业的紧迫程度，由外部赋予该进程相应的优先级，根据优先级进行调度
- 适用情况：可用于作业调度，也可用于进程调度甚至
I/O调度 - 由于该算法的优先级是由外部赋予的，故有以下两种方式：
- 抢占式优先级调度算法：只要出现另一个优先级更高的进程，调度就会发生变化
- 非抢占式优先级调度算法：进程主动放弃
- 优先级类型：
- 静态优先级：在创建进程时就已经确定，在进程运行的期间不会发生变化
- 动态优先级：在创建进程时先给予一个优先级，在推进过程中（或：等待时间增加时），动态调整其优先级
- 优缺点：
- 优点：用优先级区分紧急程度，运用于
实时OS - 可能导致
饥饿（低优先级进程的饥饿）
- 优点：用优先级区分紧急程度，运用于
- 如果进程的优先级相同，则根据到达时间来判断先后，先到达的先运行
4. 时间片轮转算法（RR算法）
- 算法思想：公平轮流地为每个进程服务，让每个进程在一定的时间间隔内都可以得到响应。
- 算法规则：按照各个进程到达就绪队列的顺序，轮流让每个进程执行一个时间片（时间片长度会事先设置好）。如果进程在一个时间片中未执行完成，则剥夺处理机，将进程放到就绪队列
队尾重新排队. - 适用情况：可用于进程调度。
- 是否属于抢占式算法？
- 如果进程在时间片内未执行完成，将被强行剥夺处理机使用权，因此
时间片轮转算法属于抢占式算法。是由时钟装置发出时钟中断来提醒CPU时间片已经用完。
- 如果进程在时间片内未执行完成，将被强行剥夺处理机使用权，因此
- 优缺点：
- 优点：公平；响应快，适用于分时OS
- 缺点：不能区分进程的紧急程度，只按照时间片的大小来进行进程的切换（时间片用完了就换下一个进程），由于需要进行进程的切换，所以消耗也较大
易错重点！！！
如果进程A用完时间片的同时，进程B到达，则进程A进入就绪队列的队尾，进程B将被直接调度
5. 🌟高响应比优先算法
- 算法思想：综合考虑作业或进程的等待时间和要求服务的时间
- 算法规则：在每次调度作业或进程时，先计算其响应比（优先级），选择响应比最高的作业或进程进行调度
- 计算公式：
- 计算公式：
- 适用情况：可用于作业调度及进程调度
- 优缺点：
- 优点：综合考虑了等待时间和运行时间，较好地实现了折中
- 缺点：每次调度都需要计算响应比，增加了系统开销
- 第一个到达的作业会先运行，因为哪怕是所有作业同一时间到达，那么此时这些作业的等待时间均为
0，则响应比相同，所以此时选择最先到达的作业或进程进行调度 - 要求服务时间 = 运行时间
注意！！！
高响应比优先算法不会出现饥饿现象，因为该算法综合考虑了等待时间和运行时间
6. 多级反馈队列调度算法
- 算法思想：对其他调度算法的折中
- 算法规则：
- 设置多个就绪队列，每个队列优先级从高到低，时间片从小到大
- 每个队列都采用
FCFS调度算法- 所谓的FCFS是对于多级队列来说的
- 🌟说明：当一个新进程进入时，先将其放到最高级队列，即：第
1级队列的队尾，如果该进程在一个时间片中完成执行，则将其撤离系统；若该进程在第1级队列的一个时间片内未完成执行，则剥夺其CPU，并将该进程放到第2级队列的队尾，以此循环，直至该进程能在某级队列的一个时间片内完成执行
- ⭐按队列优先级调度。只有当第
~ 队列均为空时，才会调度第 i队列中的进程
- 示意图/示例图：
- 适用情况：可用于进程调度
- 类型：属于抢占式的算法
- 优缺点：
- 优点：用优先级区分紧急情况，运用于实时OS
- 缺点：可能导致饥饿（低优先级进程）
贡献者
freeway348