12 CPU的各种调度原理及各种调度算法
一、 CUP调度的背景介绍
上下文切换的概念：切换CPU当前的任务，从一个进程或者线程到另一个，操作系统此时要保存当前进程或者线程的在PCB/TCB中执行的上下文（即CPU的状态），然后读取下一个进程或者线程的上下文
CPU调度：操作系统从就绪队列中挑选一个进程或者线程作为CPU将要运行的下一个进程或者线程。调度的程序是进程或者线程的内核函数（通过一些调度策略实现）
进行调度的时机：即操作系统什么时候执行进程或者线程的内核函数（调度程度），内核运行调度程序的的条件为一个进程从运行状态切换到等待状态或者当前进程被终结
调度策略可以分为抢占式和非抢占式
不可抢占：调度程序的执行必须等待当前运行时间的结束
抢占式：调度程序在发出的中断请求被响应之后就可执行，中断响应后当前的进程从运行态切换到就绪态，且要满足一个条件是当前执行的进程可以被换出
二、调度算法（策略）的一些衡量准则
CPU使用率：指的是CPU处于忙状态的时间百分比
吞吐量：单位时间内完成的进程数量
周转时间：进程从初始化到结束（包括进程的等待时间）的总时间
等待时间：进程在就绪队列中的总时间
响应时间：从提交请求到产生响应所花费的总时间
三、CPU或者处理机进行调度的目标
响应时间目标：响应时间是操作系统计算延迟的指标，一个好的调度策略应该做到以下两点
- 减少响应时间，即使处理用户的输入请求，尽快将输出反馈给用户
- 减少平均响应时间的波动
吞吐量目标：吞吐量是操作系统计算带宽的重要指标，一个好的调度策略应该做到以下两点
- 增加吞吐量，减少开销（操作系统进行上下文切换的开销），保证系统的资源得到高效利用（CPU、I/O设备）
- 减少每个进程的等待时间
公平性目标：保证每个进程占用相同的CPU时间，保证每个进程的等待时间相同（即每一个进程都有可能得到操作系统的服务）
前言：根据计算的功能，调度算法大致可以分为批处理调度，交互式调度、以及实时调度
四、下面首先介绍一些批处理调度算法
1. 分为批处理调度
1）、先来先服务算法（FCFS: First Come，First Served）
依据进程进入就绪状态队列的先后顺序排序，运行态进程进入等待或结束状态时，就绪队列中的下一个进程就会占用CPU执行，下面举一个先来先服务的示例，三个进程的处理时间分别为12，3，3，分两种进程到达顺序讨论（它们在接近同一时刻到达，但是也有先后顺序）
优点：调度算法简单
缺点：
- 平均等待时间波动较大，短的进程可能排在长的进程后面得到执行
- I/O资源和CPU资源利用率较低，CPU密集型进程会导致I/O设备闲置，I/O密集型进程会导致CPU闲置
2）、短进程优先算法（SPN：Shortest Process Next ）
选择就绪队列中执行时间最短的进程占用CPU进行入运行状态，就绪队列按照预期的执行时间来排序（准确的进程云运行时间在未执行结束，不可知，只能通过预判断来获取大致运行时间，然后排序）
这种调度算法又可分为抢占式和非抢占式
可抢占：又可称为Shortest-Remaining-Time(SPT)(最短剩余时间),它选择剩余运行时间最短的进程来调度执行，比如队列中来了一个执行时间为3的进程，CPU当前运行的进程剩余执行时间为8，则该调度算法会有限让新进的执行时间为3的进程先运行，因为该进程的剩余运行时间只有3，小于8
特点：最短进程优先算法具有最优的平均周转时间
最短进程优先算法缺点：可能长进程饥饿，因为就绪队列中连续的输入短进程流使得长进程长时间无法获得操作系统的服务（CPU的资源）
3）、最高响应比优先算法（Highest Response Ratio Nest）
特点：选择就绪队列中响应比R值最高的进程作为下一个运行进程，响应比定义如下：
它在短进程优先算法的基础之上改进，不可抢占，关注的是进程的等待时间，防止长进程的无限推迟
4）、时间片轮转算法（RR Round Robin）
时间片的概念：分配给CPU或者处理机资源基本时间单元，时间片结束时，按照FCFS算法切换到下一个就绪进程执行
轮循算法需要一个额外的系统开销，就是较为频繁的对上下文进行切换
时间片设计需要避免的两点：
- 时间片太大，等待的时间过长，极限的情况下退化成为
FCFS算法 - 时间片太小，反应过于迅速，产生大量的上下文切换，会影响到系统的吞吐量
5）、多级反馈队列算法（MLFQ Multilevel Feedback Queues）
特征：进程就绪队列被划分成多个独立的子队列，每个队列都拥有自己的调度策略；队列间的调度是进程可以在不同队列间移动，也就是说某个进程在执行过程中优先级可能会发生改变；
注意点：
- 时间片的大小随着优先级的增加而增加
- 如果当前进程在时间片内没有执行完成、则降低到下一个优先级
- I/O密集型进程停留在高优先级，CPU密集型进程的优先级下降的很快
2、 实时系统调度
实时操作系统的定义：进程或线程执行的正确性依赖于时间和功能两方面的操作系统（例如机床的嵌入式操作系统，它就要求在一个时间段内某个进程必须执行完毕，否则将会发生比较严重的后果）
实时操作系统的性能指标：时间约束的即时性（deadline），速度和平均性能相对不重要
实时操作系统的分类
- 强实时操作系统:要求在指定的时间内必须完成重要的任务
- 弱实时操作系统，重要进程有高优先级，要求尽量但非必须完成
实时操作系统的调度算法
速率单调调度算法（RM Rate Monotonic）:通过周期安排进程的优先级，周期越短的进程的优先级越高，也就是说CPU执行的是周期最短的任务
最早截止时间优先算法（EDF Earliest Deadline First）:截止时间越早的进程优先级越高，即执行截止时间最早的任务
3 、 多处理器调度
多处理器的特征：多个处理器组成一个多核的系统，处理器之间可负载共享
对称多处理器（SMP Symmetric multiprocessing）调度：每个处理器运行自己的调度程序，调度程序对共享资源访问需要进行同步
对称多处理器的进程调度
静态进程分配：进程从开始到结束都被分配到一个固定的处理器上去执行；每个处理器有自己的就绪队列；调度开销小。但存在的缺点是各处理器可能忙闲不均
动态进程分配：进程在执行的过程当可分配到任意空闲的处理器上去执行，所有处理器共享一个公共的就绪队列，各处理器负载是均衡的。缺点是调度的开销大
4、 优先级反转（Priority Inversion）
定义：操作系统中出现高优先级的进程长时间等待低优先级进程所占用的资源的现象
举例说明：
三个进程的优先级为：T1>T2>T3,
- 开始时刻
T3执行，执行时间段为t1~t2, -
t2时刻T1占用公共资源并进行锁定，继续执行到t3时刻 -
t3时刻进程T1想要开始执行，由于T1优先级高，因此T1开始执行，执行时间段为t3~t4,t4时刻T1想要访问共享资源，但由于共享资源被T3占用并锁定，因此T1进程此时需要等待 -
t4~t5时间段，T3接着执行，到t5时刻时，进程T2想要开始执行，因为T2的优先级高于T3，因此T2在t5~t6时间段得到执行，并于t6时刻,T2进程执行完毕 -
T3在t6~t7时间段继续执行，并在t7时刻，进程T3执行完毕，并释放了公共资源 -
t1时刻进程T1获得公共资源，继续执行至进程结束
整个过程分析：T1由于想要访问共享资源而等待T3释放共享资源，该过程中T3又被T2抢占，导致优先级高的继承T1得不到及时的执行
解决方案一：优先级继承（Priority Inheritance）
基本思路：占用资源的低优先级进程继承申请资源的高优先级的优先级，只有在占有资源的低优先级进程被阻塞时，才提高占有资源进程的优先级
分析：T3占用共享资源，T1想要访问共享资源，此时优先级T1>T3，提升T3的优先级等于T1，即T3=T1>T2，这样改变之后T3在执行的过程中就不会被T2抢占，因此T3可以及时获取共享资源，完成进程的执行。
解决方案二：优先级天花板协议（Priority Ceiling Protocol）
基本思想：占用共享资源的优先级和所有可能申请该共享资源的进程的最高优先级相同，不管是否发生等待，都提升占用资源进程的优先级，优先级高于系统中所所有被锁定的资源的优先级上限，任务执行到临界区时就不会发生阻塞
欢迎关注博主微信公众号，扫一扫我们一起Happy呀！！！