一、CPU调度概述
1.长程调度
- 又称作业调度或高级调度
- 处于新建状态的进程一般首先被放到外存的进程池中，当内存进程的数量没有达到最多进程数时，操作系统的调度程序才从新建状态选择一个进入内存并转换为就绪状态
- “新建”状态转换到“就绪”状态
- 由调度程序选择
- 控制多道程序的“道/度”
2.短程调度
- 又称为CPU调度或低级调度
- 在就绪队列中可能存在不止一个进程，当CPU空闲时，操作系统就需要从就绪队列中挑选一个进程让它运行
3.长程调度与段称调度的比较
4.中程调度
- 又称为交换
- 从本质上讲，中程调度不属于进程管理的内容，而应该属于内存管理
- 一个进程在内存和外存间的换进换出，最大的目的是节省内存
- 当一个进程在内存中长期不运行时，会造成内存浪费，为此，操作系统把这些进程从内存换道外存，从而腾出内存空间供运行进程使用
- 当一个在外存的进程接下来需要运行时，操作系统则执行还如操作，把这个进程从外存换入内存
5.进程调度队列
- 为了方便进行CPU调度，操作系统需要对不同状态的进程进行组织和管理。为此操作系统为某些特定的状态设立了一个或多个进程队列，用于管理这些进程
- 作业队列：在系统中的所有进程的集合
- 就绪队列：在主存中的，就绪并等待执行的所有进程的集合,不必是先进先出队列，队列中的记录通常是进程控制块(PCB)
- 设备队列：等待某一I/O设备的进程队列
- 进程的执行过程实际上就是进程在各种队列之间的迁移
6.CPU调度过程
- 调度程序
- 根据某种策略选择内存中的一个就绪进程
- 一个CPU同时只能运行一个进程
- 做选择
- 分派程序
- 负责把CPU的控制权转交CPU调度程序
- 切换上下文
- 切换到用户态
- 跳转到用户程序的适当位置并重新运行之
- 分派延迟：分派程序终止一个进程的运行并启动另一个进程运行所花的时间
7.调度方式
- 非抢占式调度
- 一旦把CPU分配给某个进程后，系统不可以抢占已分配的CPU并分配给其他进程
- 只有进程自愿释放CPU，才可以把CPU分配给其他进程
- 优点：容易实现，调度开销小，适合批处理系统
- 缺点：响应时间长，不合适交互系统
- 抢占式调度
- 调度程序可以根据某种原则暂停某个正在执行的进程，将已分配给它的CPU重新分配给另一个进程
- 可防止单一进程长时间独占CPU
- 系统开销大
- 受中断影响的代码应加以保护，从而避免同时使用
- 抢占式与非抢占式的区分
- 运行进程是否是自愿放弃CPU
- 运行进程是否是自愿放弃CPU
8.CPU调度时机
- CPU调度可能发生在当一个进程
- 从运行转到等待(非抢占式)
- 从运行转到就绪(抢占式)
- 从等待转到就绪(抢占式)
- 终止运行(非抢占式)
二、调度准则
- CPU利用率：固定时间内CPU运行时间的比例
- 吞吐量：单位时间内运行完的进程数
- 周转时间：进程从提交到运行结束的全部时间
- 等待时间：进程等待调度(不在运行)的时间片总和
- 响应时间：从进程提出请求到首次被响应(而不是输出结果)的时间段(在分时系统环境下)，也就是第一段的等待时间
- 周转时间=等待时间+运行时间
- 带权周转时间:周转时间/运行时间
三、调度算法
1.先来先服务调度算法(FCFS)
- 调度策略：按照进程请求CPU的先后顺序来使用CPU
- 调度依据：进入就绪队列的时间
- 调度方法：先进入就绪队列的进程被优先选中运行
- 使用FIFO队列实现
- 特点：
- 实现简单，可使用FIFO队列实现
- 非抢占式调度
- 公平，每个进程都有被调度的机会
- 适用于长程调度，后台批处理系统的短程调度
- 对长CPU脉冲的进程有利，对短CPU脉冲的进程不利
- 护航效果：当一个长进程后面的多个短进程，让长进程先执行，会让后面的短进程等待较长时间，从而导致CPU和设备利用率降低
- 例：
2.短作业优先调度算法(SJF)
- 调度策略：关联到每个进程下次运行的CPU脉冲长度，调度最短的进程
- 调度依据：每个进程下次运行的CPU脉冲长度
- 调度方法：调度最短的进程运行
- 两种模式：
- 非抢占式调度：一旦进程拥有CPU，它可在该CPU脉冲结束后让出CPU
- 抢占式调度：有比当前进程剩余时间更短的进程到达时，新来的进程抢占当前运行进程的CPU，也称为最短剩余时间优先调度
- SJF最优：对一组的进程而言，它给出了最短的平均等待时间
- SJF算法困难：如何知道下一个CPU区间的长度
- SJF通常用于长程调度
- 指数估算法：通过先前的CPU区间长度及其指数平均进行预测
- 饥饿：长进程可能长时间等待
- 例：
3.优先级调度算法
- 目前主流的操作系统调度算法
- 调度依据：优先级
- 就绪队列中的排列方式：优先级高的在前，优先级低的在后
- 调度方法：调度优先级最高进程运行
- 优先数：表示优先级的整数
- 可以参考不同的因素来设置(时间极限，内存要求，进程的重要性)
- 优先数可用某一范围的整数来表示
- 静态优先级：
- 进程创建时确定，在运行期间不变
- 简单易行，系统开销小
- 不够精确，可能会出现饥饿问题
- 动态优先级：
- 进程创建时的优先级随进程推进或等待时间增加而改变
- 调度模式：
- 抢占式调度
- 非抢占式调度
- 特点：
- 实现简单，考虑了进程的紧迫程度
- 策略灵活，可模拟其他算法
- 存在问题：饥饿(低优先级的进程可能永远得不到运行)
- 解决问题：视进程等待时间的延长提高其优先级
- 例：
4.时间片轮转
- 为分时系统设计
- 算法原理：把一段时间分割成若干个小碎片，每个需要运行的进程获得一个碎片运行，即在这段时间内，每个进程都得到运行
- 时间片：较小单位的CPU时间，通常为10-100毫秒
- RR算法的性能很大程度上取决于时间片的大小
- 时间片大->FCFS
- 时间片小->系统开销大
- 一般准则：时间片/10>进程上下文切换时间
- 周转时间也依赖时间片的大小
- 调度依据：进入就绪队列的时间
- 调度方法：每个进程运行时间长度为一个时间片，时间片用完后，该进程被抢占并插入就绪队列末尾
- 假定就绪队列中有n个进程、时间片q
- 则每个进程每次得到不超过q单位的成块CPU时间
- 没有一个进程的等待时间会超过(n-1)q
- 在不超过nq时间内，n个进程都运行一次
- 例：
