引言

这篇文章是基于《操作系统导论》的第一部分的总结，这是一本很好很好的书，如果大家真的想要了解更多的操作系统知识，阅读这本书还是很有必要的。

抽象：进程

操作系统正在为运行的程序提供的抽象，就是所谓的进程。

进程的创建

如何将程序转化为进程？因为操控硬件的指令在内存之中，所以我们很容易的可以想到，进程的运行也是要在内存之中的。

所以操作系统运行程序的第一件事就是把代码和所有的静态数据都加载到内存之中。而这些数据一开始都是在磁盘上面，所以需要进行磁盘I/O。这里的磁盘I/O把数据加载到内存之中和内存管理有关系，如果大家想要了解这个部分，可以看写文章-CSDN创作中心https://mp.csdn.net/mp_blog/creation/editor/160717244

那么除了一个程序的必要数据，我们肯定还需要栈和堆，操作系统需要把栈和堆分配给这个进程。

进程的状态

进程的状态主要分成三种：运行，就绪，阻塞。

我们大概来陈述一下这几个之间的关系：

首先一个要运行的程序一开始是就绪态，就绪态实际上是一个队列，每一个需要CPU来调度的程序都在这个队列里面等待着CPU的调度，当CPU选中了这个幸运的程序，程序就从队列里面出来，从就绪态变成了运行态，那么在运行态里面，一个程序因为时间调度的问题。当时间片到的时候，这个程序就会从运行态变成就绪态，然后从就绪态的队列里面拿出一个进程变成运行态。

但是还有一种情况，就是这个正在运行的程序变成了阻塞态，比如进行I/O操作，这个时候程序就会从运行态变成阻塞态，然后从就绪态的队列里面拿出一个进程变成运行态。

对于阻塞态的程序，他如果要运行，那就必须要到就绪态，但是阻塞态是不会被CPU照顾的，所以当阻塞态的进程变成就绪态是需要发生中断操作的。

当然，以上的描述还是相当的简略，所以我们马上就会来解释这一切

第一个面临的就是：当CPU调度了一个程序之后，它怎么知道该从哪里开始执行这个程序

为了解决这个问题，我们的操作系统就会为所有的进程保留一个数据结构，叫PCB。这个数据结构会记录这个进程的重要信息。当一个进程停止的时候，操作系统会把它的寄存器的内容保留在内存里面，当下一次再次调用这个进程的时候，通过PCB的信息找到这个内存的地址，让寄存器取出其上下文，继续运行这个程序。

插叙：进程API

这个章节在《操作系统导论》里面是属于选读的，但是在书中也说了，只知道理论而不去实践是没有任何用的，所以我们选择总结这一章的内容。

fork（）

这是一个创建子进程的函数，原来的进程叫做父进程，而新创建出来的进程叫做子进程。子进程不是从main开始执行的，而是从fork（）系统调用返回，就好像是子进程自己调用了fork（）。

fork（）是有返回值的，对于父进程，它的返回值是创建的子进程的PID号，对于子进程，返回值是0。

那CPU是先调用子进程还是父进程呢，其实这是不确定的，因为这两个进程会竞争CPU。

wait（）

到目前为止，我们没有做太多的事情，就是创建了一个子进程，有时候父进程需要等待子进程结束才会结束，所以我们有wait（）函数。

exec（）

这个是一个很有用的函数，我们可以思考一下，每一次我们创建的子进程，那个子进程的环境永远和父进程的环境一个样子，那如果我们要运行不同的程序呢，exec（）就派上了用场。exec（）会从可执行程序中加载代码和静态数据，然后重新初始化栈和堆空间，操作系统就会执行该程序，就像执行一个新的进程一样，但实际上这是原来的那个进程。

说了这么多话，这个函数到底有什么用呢？首先，它给我们程序员一个空间，一个从fork（）到exec（）之间的空间，来重新初始化我们需要的环境。

让我们来举个例子吧！shell也是一个用户程序，当用户输入一个命令时，大多数情况下，shell会在文件系统中找到这个可执行程序，然后调用fork创建一个新的进程，并调用exec来执行这个命令，调用wait（）等待这个命令完成。子进程结束之后，shell从wait（）函数返回，再次输入一个提示符，然后等待用户输入下一个命令。

emmm，可能这个例子比较抽象，但是很多命令就是这个样子的，我们再举一个具体的例子。我们需要输出一个结果到一个文件里面，但是如果子进程继承了父进程的环境，那么这个结果就会被直接输出到终端上面，所以shell在fork（）和exec（）之间关闭了标准输出。

这下子应该可以理解了吧！

机制：受限直接执行

在一开始，我们想要一个程序更加快速的执行，我们要求CPU直接运行这个程序上即可。因此，当OS希望启动程序运行的时候，它会在进程列表中为其创建一个进程条目，为其分配一些内存，然后将程序的代码通过磁盘I/O的方式加载到内存上。

这个思路看起来很简单，但是存在很多的问题：

1、如何实现虚拟化CPU

2、操作系统怎么确保程序安全的执行，万一这个程序坏坏的呢。

在我们介绍接下来的机制前，我们必须要了解一些概念：

1、用户模式，在用户模式下运行的代码会受到限制，比如我们用户就不可以向磁盘发起I/O请求

2、内核模式：在这个模式下面，代码就可以做它想做的事情。

但是如果用户希望执行某种特权操作怎么办？

为了实现这个点，现在的所有硬件都提供了用户程序执行系统调用能力。要执行系统调用，程序必须执行特殊的陷阱指令。我们也称为“软中断”。该指令同时跳入内核并将特权级别提升到内核模式。当需求完成之后，操作系统调用一个特殊的从陷阱返回指令，该指令返回到发起调用的用户程序里面，同时将特权模式降成用户模式。

在执行陷阱的时候，硬件需要把寄存器，标志等推送到每个进程的内核栈中，这样子才可以保证系统发出从陷阱返回指令时能够正确返回。

还有一个问题，就是陷阱怎么知道OS内运行哪些代码。显然这个地址不可以是调用者确定的，因为调用者有可能是坏人。

所以在我们机器启动的时候，会初始化一个叫“中断向量表”的东西。操作系统会告诉硬件这个中断向量表的位置，每当有中断发生的时候，硬件就会屁颠屁颠的去查这个表，然后就知道要运行哪些代码。

又到了总结这个过程的时间：

首先在操作系统启动的时候，会初始化这个中断向量表，告诉硬件中断向量表的位置。然后正常的处理程序，直到程序调用了系统调用，这个时候陷阱指令就会就会进入内核，但是在这个之前，硬件会把寄存器保存到内存栈。这个时候硬件去查中断向量表，处理对应的程序，然后陷阱指令返回，先恢复寄存器，并改变特权模式，变成用户模式，然后跳到陷阱之后的程序计数器，继续执行程序。

介绍了这么多，让我们回到正题。进程应该如何得到CPU的照顾？

主动放弃CPU

顾名思义，就是一个进程执行完了，或者发生了系统调用之后，进程主动放弃CPU。然后CPU的控制权转移给了操作系统，这样操作系统又可以控制CPU去调度其他的进程了。

但是这听起来就不是很靠谱，让一个进程主动放弃CPU，如果那个进程是个坏人呢？一直在a++,一直抓着CPU不放，这很糟糕了，操作系统一直在睡觉，得不到CPU的调度，醒不过来，所以只有重启。

时间轮询机制

操作系统可以去调度进程。既然操作系统这么重要，那么我们就必须要给操作系统一定的地位，让操作系统可以经常得到CPU的照顾。可是CPU在运行一个进程，怎么放弃这个进程呢？

时钟中断   

这是一个很好的操作，打断CPU对一个进程的处理，而这个中断叫做时钟中断。时钟设备可以每隔几毫秒触发一个中断，产生中断之后，正在运行的系统停止，操作系统先处理预先配置的中断处理程序，此时操作系统就得到了CPU的控制权，然后操作系统就可以干它想做的事情：停止当前的程序然后启动另一个程序。

这个中断是”硬中断“：不知道什么时候发生。

我们也可以总结一下中断这个过程发生了什么：

运行进程a，发生时钟中断，将a的寄存器保存在a的内核栈中，然后转到内核模式，硬件查找中断向量表，去处理中断处理函数，然后操作系统决定选择进程b，于是我们需要把a的寄存器保存到a的进程结构中，也就是把寄存器的内容保存到内存之中，并把这个地址放到PCB这个数据结构里面，然后把进程b的进程结构恢复到寄存器中，陷阱指令进入B中，从B的内核栈恢复b的寄存器，然后指令进入特权模式将其改为用户模式，最后跳到b的程序计数器执行程序B

可能这里有一些细节还不是很清楚，所以要解释一下：

第一个发生时钟中断时硬件保护现场需要把寄存器压入内核栈，而第二个进程间的切换时，为了保护当前进程的数据，操作系统把寄存器保存在该进程的进程结构的内存上面。而之后的陷阱指令进入B是造成一种错觉，好像是B刚刚陷入的内核。

硬件只认识内核栈，所以我们必须要把PCB的值放到寄存器里面，然后押入到内存栈中，最后由硬件统一的取出，所以这可以解释一个点，我们不仅仅需要把B的PCB放到寄存器里面，然后还要把寄存器放到内存栈中。

！！！！我们这里不考虑中断时发生中断

进程的调度

我们既然知道了CPU怎么将操控权还给操作系统，我们接下来就需要考虑操作系统在这么多进程之中选择哪个进程来运行。

先进先出（FIFO）

我们最简单，最基础的方法就是先进先出（FIFO）

但是既然都是最无脑的方法了，那缺点肯定也是非常多的，首先就是效率低。如果我上来一个进程需要花100min，后面的的进程可能只需要1ms，这明显不合适。

所以我们需要换换思路。

最短任务优先（SJF）

在小学的奥数中，我们希望等待的时间最短，所以我们的想法非常的简单，就是时间短的先运行。

每一次我们都会在队列里面选择一个时间最短的任务交给CPU

但是，这也是有缺点的，如果我第一个进程需要一瓶水，但是一直有一些很小的进程进来，我一直拿不到这瓶水，那我不就一直拿不到这瓶水。

不过，在这个巨大的缺点前，我们还需要有一些小小的优化，如果一个进程本来需要5min，已经运行了3min，那么还剩2min，但这个时候时间片到了，同时又来了一个进程，这个进程要3min，所以根据我们的比较，我们会选择新来的进程，这很明显不对，我们应该比较剩余的时间，而不是一开始的时间，所以我们需要更新我们的算法。

最短完成时间优先（STCF）

这里我们的比较点是剩余时间的长度

除了我们上面一个问题，我们还需要思考一个问题：我即使选择了最优的算法，但是依然避免不了一个事实，就是如果一直运行一整个进程，那么就必然有些进程得不到照顾，就会产生饥饿。所以我们必须要新的算法！

轮转

每一次发生时钟中断，我们操作系统抢到CPU之后，会选择新的进程来运行，保证每一个进程都可以和CPU说话，而不是一直睡觉。

对于这个算法，我们必然要考虑的一个问题就是多长时间中断？

时间片长那肯定不行，时间长那不就是之前的那一种算法了

时间片短肯定是对的，但是不能太短，因为每一次中断，上下文的切换都是系统调用，每一次切换都会有大量的性能消耗，也不是很行。

我们再来复习一下这里的上下文切换，其成本有：

1、保存和恢复寄存器

2、CPU高速缓存，TLB也要更新

所以如果要考虑周转时间，那轮转其实是最糟糕的算法，但是它保证了公平性！！！

多级反馈队列（引入）

我们必须要重新思考一下这个问题了，似乎没有这么简单。

我们这一次从I/O入手。

我们假设有两个进程A、B，都需要50ms，但是A进程在运行10ms之后要发出I/O请求，那如果我们先运行B，再运行A，那当A发出I/O请求时，CPU就无事可干了，效率很明显不高。

所以对于处于上帝视角的我们，我们会先选择进程A，当进程A发出I/O请求的时候，发出中断，我们CPU再去运行进程B，然后利用STCF的算法进行之后的调度。

好的，我们已经有了新的思路。但是我们也说了，我们处于上帝视角，我们并不知道进程A会发生I/O，所以我们接下来就要设计一些算法，来预测这个进程的未来。

I/O密集型和CPU密集型

I/O密集型就是经常发生I/O操作，例如scanf

CPU密集型就是占据CPU，让CPU不停的工作，例如：

while(true){

    a++;

}

 调度：多级反馈队列（MLFQ）

还是要再次强调我们的目标：判断这个进程是不是I/O密集型，如果是就运行它，如果不是，就后运行它。意思就是你要让CPU相信你是好人。

我们依然选择用队列的方式，但是每个队列的等级是不同的，我们CPU会先运行最高等级的队列里面的进程，当最高等级的队列里面没有了，就会到下一层，依次循环。

但是，我们怎么知道这个进程属于哪个队列的？这是一个很大的问题。唯一的方法就是尝试，我们自定义一个时间，如果超过了这个时间地进程还没有结束，那这个进程就被认为是CPU密集型，等级降低一级，如果在这个时间内放弃了CPU，相当于发生了I/O操作，那么这个进程就被保留在这个队列里面。

那我们为什么需要这么多队列呢？

因为我们需要给每个进程很多的机会，不断去调整这个进程的等级。

所以目前我们MLFQ的规则有5个：

1、如果A的优先级大于B，那么运行A

2、如果A的优先级等于B，那么轮转运行。

3、进程进入系统时，先放在最高优先级

4、如果用完整个时间片，那么等级降低一级

5、如果在时间片内放弃CPU，那么等级保留

emmmm，似乎看起来没什么问题，但其实有很大的问题。

两个进程还好说，如果有太多的I/O交互进程，那些等级低的进程会需要等待很久，直接给那些进程气哭了，那肯定不行。

或者说，这个进程是一个坏人，这个坏人坏得很，每一次这个时间片快要到的时候，他就发起一次I/O，忽悠CPU表明他是一个好人，一直给他放在最高级。

对于饥饿的问题，我们增加一个规则：

6、经过一段时间S，就将系统中所有工作重新加入最高优先级队列

对于坏人，我们需要更新一下原来的规则：

把规则4，和5一起更改：

4、一旦工作用完了其在某一层中的时间配额，就降低其优先级

这个时间配额是等级越高，时间配额越少

最后最后，我们需要总结MLFQ的规则：

1、如果A的优先级大于B，那么运行A

2、如果A的优先级等于B，那么轮转运行。

3、进程进入系统时，先放在最高优先级

4、一旦工作用完了其在某一层中的时间配额，就降低其优先级

5、经过一段时间S，就将系统中所有工作重新加入最高优先级队列

最后还有一些算法：比如彩票算法，是和概率有关的算法，这里就不做过多的介绍了，大家如果有兴趣，自行去学习。

插叙：最低等级的队列

我们需要补充一个书上没有的内容，这个其实是我们很好奇地一件事。在生活中，我们买手表很重要的一点就是续航，一个手表拿出去几小时就没电了，那肯定很垃圾。但是手表在熄屏的时候CPU是在睡觉吗？其实不是，CPU仍然在运行代码，但是这一串代码对于CPU地消耗很少，而这一串代码就是在最低等级的队列里面呆着，如果CPU没有进程可以运行了，那么行，就把这一串代码拿出来运行。但是这个最低等级的代码其他进程无论再怎么倒霉，都是不会进入到这个等级的队列里面的。