前言

https://gitee.com/liwenhao12/note/blob/main/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E5%88%97/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E5%AF%BC%E8%AE%BA.md

PS: 强烈建议看网页版，星球的格式一言难尽，网址就是那个本文开源那个

本文的主要内容：《操作系统导论》的大部分知识 + 我对书中内容的理解记录。我强烈推荐你也去看看这本书，也许你也会和我一样忍不住想写一些东西来记录自己的思考。

我针对整本书进行了一个梳理，如果你不确定你是否对下面的内容感兴趣可以看看大纲 😁

大纲链接：https://www.mubu.com/doc/L_9qNbJoK6

本文开源：https://gitee.com/liwenhao12/note/blob/main/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E5%88%97/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E5%AF%BC%E8%AE%BA.md

如果文章有什么错误或者有不妥的地方可以提Issue

操作系统的发展

1. 第一阶段：操作系统还只是一些简单的底层API
2. 那时候操作系统只是一些控制设备的API，比如关于IO的API
3. 第二阶段：操作系统的第一个功能
4. 人们逐渐意识到控制设备的这部分代码，不能被随意访问。系统调用的概念就是这个时期出来的。
5. 第三阶段：多道程序时代
6. 随着硬件的成本下降，拥有计算机的成本降低，人们希望充分利用CPU资源，一次指定多个程序。为了满足这个要求，现代化的操作系统就此诞生了，比如内存保护，进程隔离等等。

通过操作系统的演化过程不难发现，从只是提供功能复用的'OS'变成了一个管理硬件资源的大管家。

虚拟化

接下来的内容，如果没有特别说明，讨论的是单核CPU的情况

虚拟化硬件，是为了更好的管理硬件，更好的为应用程序分配资源，比如Linux将硬件虚拟化为文件，从而实现更好的管理和控制。

虚拟CPU

将CPU虚拟化，目的就是让应用程序看到这样一个假象：应用程序独占一个CPU。

举个租房的例子，我有一间房子，有两个租客，他们都想要租这个房子，而作为房东的我，很贪心，想要收他们两个人的房租。但是我只有一个房间，正当我放弃的时候，我突然发现他们的租房时间很有趣，租客甲他说我只会在上午使用房子，其他时间在公司工作，而租客乙恰恰相反，他除了晚上使用房子，其他时候也在公司工作。于是我起来贪心，收了这两位租客的房租，然后他们两个成功入住了。但是为了不让他们起疑心，我必须保证甲回来时，房子中的环境和以往一样，乙回来时，也得和他上次看到的一样。于是我不得不在甲离开房子，乙回来之前，将房子还原成乙的环境。虽然很辛苦，但是我收了两份房租，而且在他们看来，这个房子就只有他们一个人租。

上面的例子解释了虚拟CPU的具体实现，即如何让应用程序认为他们独占一个CPU。在这个例子当中，房东就是操作系统，租客甲/乙就是普通的应用程序。

在程序甲要使用CPU之前，需要恢复程序甲之前的运行环境(比如寄存器中的值，以及CPU中的缓存数据)。通过这种保存环境，恢复环境的方式，让应用程序以为他自己独占一个CPU核心。而这里的保存环境以及恢复环境的过程就是我们通常说的上下文切换。

既然就了解到这里了，不如我们继续深入下去，看看虚拟化的CPU到底是怎么做的？简单来说：CPU的时分共享 + 调度策略。时分共享：不同时间段，有不同的进程占用CPU，在进程的视角上看，他们独占CPU，但是从上帝视角上看，CPU是被许多进程共享的。之所以能保证在进程的视角上是独占视角的，这得多亏上下文切换，能够保留环境和恢复环境。调度策略：主要是决定运行哪个进程，是否需要进行上下文切换。

设计思想

时分共享更多的是一种底层的运行机制，而调度策略是上层的一种解决方案。

时分共享更多的是提供一种解决思路，而调度策略更多的是提供一种具体实现。类似于接口与实现类的关系。

进程

通俗的讲，进程 = 正在运行的程序，这句话描述的够准确，但不够细节，进程是对正在运行的程序的抽象，那一个进程究竟包括什么呢？首先我们先想想运行一个程序需要什么？对于运行的程序，我们首先需要代码，它承载了我们的逻辑，会产生数据，这些承载了我们的结果，代码和数据得有地方存，这个时候有硬盘和内存可选，但是为了高效，快速，选择了内存，代码只是逻辑的体现，只是一套执行方案，还需要执行者，那就是我们的CPU。所以我们知道进程至少需要包含的硬件资源：内存 + CPU，硬件资源也不尽相同，比如内存的规格和性能，为了更好的管理硬件资源以及更好的分配资源给进程，我们需要虚拟化硬件，实现统一的管理。

进程需要的硬件资源

1. 内存
2. CPU
3. 硬盘
4. IO

关于进程的介绍，大致就这样，后面我们慢慢补充。

调度策略

调度策略是发展的，是一个演进的过程，于是在理解调度策略的时候，我们也应该用发展的眼光看它，所以这部分内容，我打算从最简单的FIFO策略 → 最短任务优先策略 → 最短完成时间优先策略 → 轮换策略 → 多级反馈队列。

首先要比较不同调度策略，我们需要有一个评价的指标，最直观的指标就是速度，为了衡量不同方面的速度，我们提出了周转时间和响应时间这两套指标。

1. 周转时间 $T_{任务完成时刻}

1. 响应时间 $T_{首次运行时刻}

这里的任务可以理解为进程，根据他们的含义可以看到，周转时间是程序总的运行时间长度，而响应时间是用户提交程序(比如双击图标)到程序真正被执行(获取到CPU资源)的时间差，主要是用来衡量交互性的好坏。

为了更好的展示，调度策略是怎么演化的，我们需要给我们的进程进行一些假设。

1. 每一个工作运行相同的时间
2. 所有的工作同时到达(提交)
3. 一旦开始，每个工作保持运行直到完成
4. 所有的工作只使用CPU，而不使用I/O
5. 每个工作的运行时间已知

1. FIFO调度策略

FIFO，即先进先出，也就是先到先执行，假设我们有三个任务A B C,他们都运行10s,我们这里来计算一下他们的平均周转时间，根据假设，因为他们同时达到，假设A比B早一点点，B比C早一点点。

$周转时间为：[(10 - 0) + (20 - 0) + (30 - 0)] \div 3 = 20s$

FIFO的策略有其优点那就是很容易实现，那缺点是什么呢？我们先把假设1(每一个工作运行相同的时间)放宽，每个任务的运行时间不一定相同，还是上面的例子，A B C三个任务运行时间分别为 100s,10s,10s,那么平均周转时间是多少呢？

周转时间为： $[(100 - 0) + (110 - 0) + (120 - 0)] \div 3 = 110s$ 可以看到，周转时间增加了很多，这被叫为护航响应：一些潜在的消耗较少的消费者排在了重量级的消耗大的资源消费者后面。 FIFO的策略的性能严重依赖进入任务的耗时以及任务被执行的顺序。上个例子，如果B C 先运行，平均周转时间 (10 + 20 + 120) / 3 = 50s,可以看见平均周转时间减少了一半。于是下一个调度策略就解决了这个问题

1. 最短任务优先策略(SJF/Shortest Job First)

先去回顾一下我们的假设，现在为止，我们已经放开了假设1，或者说我们放弃了假设1后，产生了问题，于是这个调度策略就是来解决产生的问题的。

我们知道了FIFO策略的性能严重依赖任务的耗时以及任务执行的顺序，而SJF就是来解决这个问题的。还是任务A B C同时到达，这时候就会根据任务的耗时判断，谁先被调度(执行)。还是上面那个例子 A B C三个任务运行时间分别为 100s,10s,10s。那么平均周转时间是确定的，50s

在开始的时候，对任务耗时的比较，让任务的执行顺序确定而且最优，解决了FIFO策略的性能依赖任务执行顺序的问题,但是之所有能最优是建立在任务同时到达的假设下，也就是我们的假设2(所有的工作同时到达(提交)),可是如果我们放开假设2，就会产生这样的问题？

当任务不是同时达到时，就会产生上面这种情况：长时间任务先到达，然后执行A任务到完成(假设3)，即使B C任务比A时间短。这样的话就让周转时间又下降了。造成这种情况的原因是我们假设任务一旦执行，就必须执行完成(假设3)，如果我们放宽这个假设3，利用上下文切换技术就可以解决这个问题，这个也是我们的下一个策略的原理。

1. STCF策略(最短完成时间优先策略/Shortest Time to Completion First)

为了解决SJF在不是同时达到任务长度比较问题，STCF给出的解决方案是在每次添加新任务进队列的时候，会比较当前执行任务的剩余时间和新进入的任务的剩余时间进行比较，选择其中短的任务执行，如果发生要切换到新的任务，就会进行上下文环境的保存即上下文切换。

通过这种抢占式的调度方式，可以很好的保证短任务一定先于长任务执行。在假设4(只使用CPU不使用IO)和假设5(知道任务的完成时间)成立的条件下，STCF是比较符合直觉的最优的解决方案。

在讲解下一个调度方式的时候，不知道你注意到没，我们现在还没有使用响应时间这个指标，为什么呢？因为我们的任务没有使用IO，没有IO就没有输入/输出,那么就没有交互，没有交互谈响应时间的意义就不是很大。不过我们也可以利用响应时间公式来算算上面那个STCF中的例子，因为A到达后，就立马执行，所以A的响应时间为0s,B也一样，到达了就执行了，只有C，在达到后，需要等待B执行完后，才能执行，所以C的响应时间=10s。从这个例子可以看出来，无论B中有无IO操作，都会等待B完全执行完毕后，才开始执行C，如果我们执行的这个C任务是一个与用户交互的程序，那么用户端将会明显的感觉到卡顿。为了解决这个问题，优化响应时间，提升交互程序的易用性，于是诞生了下面这种调度方式 -- 轮换

1. 轮转(RR)

为了极致的优化响应时间，这种调度策略以一个很小的时间片段为单位，一个进程只运行这么一个时间片，然后就会进行上下文切换，执行另一个进程。

在图中每个时间片的大小为1s,那么C的响应时间就为(4-3) = 1s,可以看到响应时间被大大的优化了，但是这个优化是有代价的，代价就是上下文切换。上下文切换最少就是要做的保存寄存器的值到内存，然后将寄存器的值从内存恢复到寄存器中。虽然这种切换很快，但是如果频繁操作依然影响性能，不过上下文切换的代价是稳定的，可以利用均摊的思想，来降低上下文切换带来的性能影响。上面的调度方式其实是基于假设4(只使用CPU而不使用IO)但是程序不可能不使用IO，于是我们放开假设4，程序都可以使用IO和CPU。

时间片内发出IO操作，会自动放弃CPU资源，这个时候就会调度其他任务，当IO完成后，就又会将A任务设置为就绪状态，等待被调度，充分利用了上一个任务在时间片内等待IO的时间。"疯狂压榨CPU"(提升了CPU的利用率)

1. 多级反馈队列

目前为止，我们的假设1,2,3,4都已经被我们放宽了，就只剩下假设5（每个工作的运行时间已知），这是这5个假设中最离谱，最不切实际的假设，因为根本无法知道程序到底需要运行多久。那么如果我们放宽这个假设，就会产生很多问题，比如基于时间的SJF和STCF策略都没法用了。于是就出现了现代化操作系统在用的调度方式 -- 多级反馈队列（MLFQ）

基本规则

1. 存在多个队列，每个队列有不同的优先级
2. 每个队列中可以存在多个任务
3. 一个任务只能属于一个队列

工作方式

初始阶段，每个任务的优先级都是最高的，然后在同一个队列中的任务采用轮转的策略进行调度执行，在执行期间（一个时间片）如果主动放弃CPU会被视为交互程序，优先级保持不变，如果执行期间没有放弃CPU，那么被视为计算密集的任务，降低优先级。这种在运行过程中动态调整优先级的方式被称为用历史预测未来，只有高优先级的队列任务执行完之后，才会执行低优先级的队列中的任务。

但是这种方式并不完美，存在一个很大的问题，那就是饥饿问题，比如AB是交互性程序，C是计算型程序

如果A B任务没有停止，那么C任务在后面就不可能被执行。于是就产生了饥饿问题，解决饥饿问题的方式就是经过一个时间段，将其他优先级的任务又重新添加到最高优先级的队列中，于是关键的问题在于如何确定时间段的大小，因为如果设置的过短，交互性程序得不到合适的CPU比例，过长，长时间的任务又会饥饿。于是这个时间段也被称为巫毒常量，其实除了这个问题以外，还有一个小问题，出现在确定优先级的策略上，目前我们的确定优先级的策略是：如果在一个轮转时间片中主动放弃CPU，那么就会保持优先级不变，如果没有放弃CPU，那么就会降低到下一个优先级队列中。有一些聪明的程序可以利用这个策略，在执行到时间片99.99%的时候主动放弃CPU，即便他是计算型任务也不会降低优先级。于是我们需要升级这个策略：每个任务在每个队列中存在总时间限制。确定优先级的策略变成了这样：在执行期间，如果一个任务在该队列中执行的总时间超过了配额，就会降低到下一个优先级队列中。这样就规避了上面这种投机取巧的方法。目前我们的多级反馈队列的调度方式已经很完美了，但是还是存在一个小小的优化点。那就是每个队列中，轮转执行的时间片是一致的，我们知道优先级越低的队列中，更多的是计算密集的任务，而轮转的调度方式需要进行上下文切换，有一定的性能开销，所以为了优化性能，我们可以将优先级低的队列的时间片设置的长一些，减少不必要的上下文切换。

小结

到此，主流的调度策略的演化过程就结束了。这里面有一种学习方法：在一个条件非常特殊的情况下讨论问题，给出解决方案，然后一步一步的放宽条件，放宽条件的同时一定会出现新问题，我们可以根据出现的新问题，提出新的解决方案，最后形成了我们最终的解决方案。有一种分而治之的味道在里面。