一、调度背景
1、CPU调度
- 将程序切换到运行态，那么就可以占用CPU运行。一旦从运行态切换到其他状态，就会不能再占用CPU运行了。
- 那么什么时候切，以及切换原则呢？
- 那么就更CPU调度有关了。
在某一个时刻绝对选择让哪一个进程让CPU将要运行的下一个进程。 - 调度需要考虑两种情况：.
- 不可抢占。大部分我们调用的是应用程序，应用程序运行的时候，是以用户态的进程形式存在。这个进程从开始到结束，中间是不允许打断。早期操作系统设计的情况 ——不可抢占策略。这样其他的程序需要进行等待，效率不高。比如说运行程序中，处于堵塞状态，这时CPU是停止的。所以效率不高
- 可以抢占：用户进程程序在运行中，可能感觉不到，但是操作系统会决定某个时刻打断用户执行，让操作系统去选择另外一个进程。现在操作系统很常用的调度策略。当一个用户进程执行系统调用，在内核中不会导致进程处于等待状态，那么这时当系统访问时，内核中不会出现抢占状态。
二、调度准则
1、调度策略
进程在计算机运行时处于的状态，进程更多的是访问内存和i/o，让CPU做计算。
2、程序执行模型
在某个进程在等待I/o时，可以切换到其他进程中，可以使CPU处于一直工作状态。
3、比较调度算法的准则
- 可以用来评测分析调度算法的指标。
- CPU利用率越高，那么认为当前系统效率越好。说明进程调度很好。 CPU利用率是一方面。
- 吞吐量越高，意味着进程的效率越好。
- 周转时间：启动后需要等待一段时间才能会被CPU执行，从而完成想对的工作，才会结束。等待时间+服务时间=周转时间。时间越少越好。
- 等待时间：处于就绪态的进程，变为运行态所等待的时间。
- 响应时间：外设发出请求，到请求被进程处理完毕，为相应时间。
4、吞吐量VS延迟
什么是更快，对快的解释？
- 传输文件时的高宽带：出水量大
- 玩游戏时的低延迟：响应时间块
- 这两个因素是独立的
和“水管”类比
- 低延迟：喝水的时候想要一打开水龙头就流出来。
- 高带宽：给游泳池冲水时希望水龙头同时流出大量的水，并且不介意是否存在延迟。
对于算法来说，我们希望算法达到什么样的效果呢？
- 响应时间：及时处理用户的输出并且尽管输出提供给用户。
- 减少平均响应时间的波动：在交互系统中，可预测性比高差异低，平均更重要。
- 增加吞吐量-两个方面
1.减少开销（操作系统开销、上下文切换）
2.系统资源的高效利用（CPU、I/o设备） - 减少等待时间：减少每个进程的等待时间。等待时间越小越好，程序已启动，马上可以执行。
这四点：是有矛盾的，最小响应时间和最大吞吐量，在操作系统中设置中，不能同时顾及，只能做偏一方面或者折中。
所以在不同的应用场合，选择不同的优点。
- 低延迟调度增加了交互式表现：比如说桌面系统（鼠标键盘），更多的需要交互性。那么就是低延迟比较高。
- 操作系统需要保证吞吐量不收影响：数据的服务器，更需要吞吐量，需要提供很大带宽，比如视频等等…
- 吞吐量是操作系统的计算带宽
- 相应时间是操作系统的计算延迟
5、公平的目标
并不是以效率（延迟、吞吐量），而是以公平作为很重要的调度指标。
期望是调用算法，系统运行了每一个进程的公平得到CPU服务。也就是说“得到CPU的时间，大致是公平的”，等待CPU时间，大概也是公平的。
公平通常会增加平均响应时间
三、调度算法
实际调度算法比这几个都复杂， 但是实际调度算法对于这些基本特征都是有所体现的。
- FCFS：比较简单先来先服务。
- SPN/SRT考虑是时间短的进程，后果是：长进程一直得不到操作系统调度。
- HRRN：将等待时间考虑进去了。想对前面等待时间很长的进程，也有机会执行。
- round Robin：每个进程都有机会被执行。想对公平，但是会引入上下文切换问题
- MLFQ：动态根据执行过程（CPU、I/o密集）（根据消耗时间片）来动态调整优先级。使得操作系统根据进程的动态特点来选择优先级。
- 公平调度：强调用户请求，在不同级别公平调度。
1、调度算法1（通常操作系统桌面和服务器涉及最基本的调度算法。）
1. FCFS：先来先服务，最简单的算法
在一个队列中，先来的程序，排在前面，CPU进行先处理，后来的排在后面。按着顺序进行处理。
例子中三个进程，根据任务到达顺序，进行任务先后。
可以看出前面程序越长，那么后面程序等待的时间也就越长，从而影响整个系统的周转时间。
那么调整方法有：将最短的时间放在前面，把最长的程序放在后面。那么优先调度时间很短的进程。短进程优先的算法
- 优点：
简单 - 缺点：
平均等待时间和周转时间波动较大
花费时间少的任务可能排在花费时间长的任务后面
可能导致I/o和CPU之间的重叠处理（CPU密集型进程会导致I/o设备空闲时，I/o密集型进程也在等待）
2.SPN：选择下一个最短的进程——考虑时间的进程
将时间短的进程放在前面，可能提高效率。进程的时间决定优先级，时间越短优先级越高。
将几个进程进行排序，排序后，在调用时，根据排序结果进行执行。如果有来了新程序，不会打断当前程序。“不抢占程序。”
-
新来了程序，与前面进行比较，如果新来的程序，比前面的程序段，会进行抢占前面程序的顺序。而SPN不会进行抢占。
所以说这个平均等待时间最小的 -
缺点是：
连续的段任务流会使长任务饥饿
短任务可用时的任何长任务的CPU时间都会增加平均等待时间 -
需要预知未来
怎么预估下一个CPU突发的持续时间
简单的解决办法：询问用户
如果用户欺骗就杀死进程
如果用户不知道怎么办 -
既然不知道进程执行多长时间，可以进行预估之前执行历史，来判断什么时候结束。
-
对下一次时刻的预估，根据预估时间进行对调度排序。在操作系统很常用的方法是：根据过去预知未来。
3. HRRN：最高响应比优先——最短剩余时间有限
HRRN比前面多考虑了一个多等待时间，SPN只考虑了执行时间，没有考虑等待时间
公式：R越大，那么等待时间越长，优先调度该进程。
最高响应：综合考虑进程的执行时间和等待时间。
从而可以设计出了，交互性、相互性更好的调度算法。
4. Round Robin：CPU轮流执行进程任务。对公平有一定的考虑
让各个进程轮流占用CPU去执行。衡量效率：等待时间。
每个进程都有机会占用CPU执行。平均等待时间很大
多级队列：将进程分析成很多队列，不同队列采取不同调度算法。高级队列：最短优先
5. MFQ：强调了公平，也强调了变化。进程等待执行时间，根据动态执行过程，进程动态执行调整。
- 多级反馈队列：反馈体现在进程执行的特征，在队列中有所反应。比如说一个进程开始是交互式，开始设为级别较高，最先执行，执行完后，做I/o交互，所以大量等待时间。时间越长优先级越高，那么占用CPU时间越长，时间片很快，一旦发现，那么就可以把优先级进行降级队列。时间片用的越多，就越降级。使得让一些交互性比较好的进程，提高优先级。从而整体提高效率。
I/o密集型的交互性高：提高优先级，让得到很快的执行。
CPU密集型的消耗很多计算机资源的：优先级降低，跑慢一点。
6. FSS：共享是指CPU的时间——等待和执行可以公平的共享
强调公平，
2、调度算法2（嵌入式实时系统中的特殊调度的算法）
3、调度算法3（多CPU多核调度算法的考虑）
四、实时调度
实时调度和通信调度有很大区别：实时调度面临的系统不一样
1、实时系统
-
定义：正确依赖于其时间和功能 两方面的一种操作系统。比如说一些工业性质。在某一段时间内，必须完成一些任务。以进程的形式，能够满足实时实时的特征。
-
性能指标：
时间约束的及时性
速度和平均性能想对不重要 -
主要特征：时间约束的可预测性
实时系统分为两种：
-
强实时系统：需要在保证的时间内完成重要的任务，必须完成。
当系统的某一个关键任务，如果不能再规定时间完成，会引起灾难性后果。必须在强实时系统中，所有任务，在设定的时间段，必须要完成。例如：控制水坝。 -
弱实时系统：要求重要的进程的优先级更高，尽量完成，并非必须。
比如说看视频，就算出现卡顿，不会产生严重后果。 -
如何衡量一个任务能够完成实时需求呢？
Released相当于进程中的就绪态，就绪可能不会马上执行，等待一段时间。
执行时间（Execution time）：这一段时间开始执行，结束时间是蓝色这一块终止时间。
最终期限（Absolute deadline）：执行时间一定不能超过，此期限。
2、可调度性
静态优先级调度：在任务执行之前，将优先级确定，按着优先级在规定时间去完成，相应工作。
动态优先级调度：任务优先级，随着执行过程，优先级会动态变化。动态变化可能影响不同时刻执行顺序。所以会可能先、延长调度。
3、单调速率（RM）
静态：优先级在执行前，就已经确定了（周期和优先级）。
周期越短，优先级越高。
4、截止日期最早优先（EDF）
随着任务执行，动态调整优先级。离着Dealine越早，优先级越高。
五、多处理器调度
-
多处理器调度：在实际系统中，多核处理器和并行处理器越来越多。前面调度主要考虑一个CPU，其实现在多个CPU。
-
单处理器：进程只在一个CPU中进行。多处理器的CPU调度更加复杂
1.多个相同的处理器组成一个多处理器：那么来了一个进程后，操作系统应该考据，将进程放在哪个CPU中运行。
2.多CPU，空闲和忙碌CPU，如何均衡的运行。
3.优点：负载共享 -
对称多处理器（SMP）
1.每个处理器运行自己的调度程序
2.需要在调度程序中同步
六、优先级反转
如果第一个进程，没有及时完成的话，那么系统会认为是不稳定现象。就会重启系统。
t1虽然比t2的优先级高，t1执行时间受制于t2执行时间，t2抢占用了t3的CPU时间去执行。t1必须等着t3，导致t1的执行时间被t2延长。 从而出现了：t1不能及时完成任务，导致整个系统不稳定现象。从而重启。 低优先级任务影响高优先级任务。
