一篇快速入门操作系统的进程管理

1. 什么是进程

进程即正在运行的程序的一个实例。

当启动一个程序，程序会从磁盘被读取到内存，CPU 再从内存中读取指令，对其解码，然后执行指令（比如两数相加，访问内存，检查条件，跳转函数等）。完成这条指令后，CPU 继续重复上述操作。这样子就可以实现一个 CPU 可以对一个进程，以一对一的形式进行指令读取与执行。

我们把操作系统做某件事，抽象成一种概念，称之为一个任务。一个进程可以对应一个任务，也可以对应多个任务。

早期的计算机只有一个 CPU，多个任务需要运行怎么办？需要依次排队等待，串行执行，一个任务执行完毕，才能执行下一个。这种方式存在着明显的弊端，假设排在前面的 A 任务需要执行5小时，而排后面的B任务仅需要1分钟，那么 B 任务必须等待 A 任务5小时完成后，才能执行，这种方式显得极其不灵活。

后来就有了多任务系统，在CPU同一时间只能处理一个任务的前提下，每个任务有一定的执行时长，比如任务A执行0.001s，切换到任务B执行0.05s，再切换到任务C执行0.01s...不断循环。这种机制也就可以在一定程度上解决上述任务B需要长时间等待的问题。

由于 CPU 速度非常快，这种多个任务不断切换，会给用户一种任务并行执行的错觉，这种也被称为是伪并行调度。既然有伪并行，那么也会有真并行。在现代计算机中，常见的CPU核数可以达到8核甚至更多，操作系统可将每一个核视为一个CPU，那么8核CPU就可以真并行执行8个任务。还有更进一步的，即一个计算机内，有多个CPU。至于多个CPU与多核的区别，感兴趣的读者可以参考多核 CPU 和多个 CPU 有何区别？。

那么我们继续基于伪并行进一步探讨。伪并行虽然可以解决上述任务等待的问题，但是依然还存在一系列未解之谜：

• 每个任务应该执行多长时间？
• 如何找到要执行的下一个任务？
• 有些任务涉及了资源操作，执行到一半，切换任务，那么这些资源怎么办？

......

为了解决上面一系列谜题，我们需要一种模型对任务进行详尽的描述记录。一个进程可以对应一个任务，也可以对应多个任务，当前还未涉及多线程，我们可以在此先把进程和任务当作是一对一的关系（这并不是为了理解而创造出来的一种暂时错误的假设）。下面我们将进一步探讨关于进程更详细的内容，这些内容将有助于解释上面的问题。

2. 进程模型

2.1 PCB

对于一个被执行的程序，操作系统会为该程序创建一个进程。进程作为一种抽象概念，可将其视为一个容器，该容器聚集了相关资源，包括地址空间，线程，打开的文件，保护许可等。而操作系统本身是一个程序，有一句经典的话 程序 = 算法 + 数据结构，因此对于单个进程，可以基于一种数据结构来表示它，这种数据结构称之为进程控制块(PCB)，有一些教材也将其称为进程表。不同的操作系统，PCB中包含的信息存在差异，大体上都会包含这些信息（该图来自《现代操作系统》）。

2.2 进程状态

那么什么原因会导致进程会被创建，从而生成PCB呢？常见的有以下几种

1. 系统初始化
2. 用户通过系统提供的API创建新进程
3. 批处理作业初始化 (什么是批处理作业)
4. 由现有进程派生子进程

一个进程，因为某种原因被创建了，那么它可以按照以下步骤进行一系列的初始化

1. 给新进程分配一个进程ID
2. 分配内存空间
3. 初始化PCB
4. 进入就绪队列

2.2.1 五状态模型

如图，进入就绪队列，其状态就会变为就绪态。各个状态之间的关系描述如下：

就绪 -> 运行：当操作系统内存在着调度程序，当需要运行一个新进程时，调度程序选择一个就绪态的进程，让其进入运行态。

运行 -> 就绪：运行态的进程，会占有CPU（参照一开始的饼状图）。每个进程会被分配一定的执行时间，当时间结束后，重新回到就绪态。

运行 -> 阻塞：进程请求调用系统的某些服务，但是操作系统没法立即给它（比如这种服务可能要耗时初始化，比如I/O资源需要等待），那么它就会进入阻塞态。

阻塞 -> 就绪：当等待结束了，就由阻塞态进入就绪态。

运行 -> 终止：当进程表示自己已经完成了，它会被操作系统终止。

这便是对于单个进程，经典的五状态模型。当存在多个进程时，由于同一时间只能有一个进程在执行，那么如何去管理这一系列的处于阻塞态和就绪态的进程呢？一般来说，会使用就绪队列，和阻塞队列，让处于阻塞态和就绪态的进程进入队列，排队执行。下图是一个单一阻塞队列模型。

基于此，还可以扩展出多个就绪队列，每个优先级对应一个队列，这样子操作系统在选择要调度哪一个进程时，可以有更大的灵活性。下面将进一步探讨队列与进程之间如何组织管理。也可以有多条阻塞队列，每一个事件对应一个阻塞队列，当事件发生时，该队列所有进程都进入就绪态。

2.2.2 七状态模型

上面所讲的进程状态存在一个前提：每个进程都必须完全载入内存。一旦排队的进程多了，对于有限的内存空间将会是极大的考验。为了解决内存占用问题，可以将一部分内存中的进程交换到磁盘中，这些被交换到磁盘的进程，会进入挂起状态，进一步还可细分为就绪/挂起，阻塞/挂起。对于单个进程的状态转换如下图。

整体上对于挂起队列的转换关系，如下图。

关于图中的几种调度，将会在下面第4章进一步描述。

2.2.3 进程切换

当一个正在运行中的进程被中断，操作系统指定另一个就绪态的进程进入运行态，这个过程就是进程切换，也可以叫上下文切换。

该切换过程一般涉及以下步骤：
1.保存处理器上下文环境：将CPU程序计数器和寄存器的值保存到当前进程的私有堆栈里
2.更新当前进程的PCB（包括状态更变）
3.将当前进程移到就绪队列或者阻塞队列
4.根据调度算法，选择就绪队列中一个合适的新进程，将其更改为运行态
5.更新内存管理的数据结构
6.新进程内对堆栈所保存的上下文信息载入到CPU的寄存器和程序计数器，占有CPU

2.3 进程组织

每一个PCB表示一个进程，多个进程同时存在时，需要一定的方式将这些PCB组织起来，便于操作系统访问。常见的组织方式有如下3种。

2.3.1 线性表

所有的PCB存放于一张线性表中，每次查找时需要遍历线性表。比较适用于进程数量不多的情况，如果有几百上千个进程，每次操作都进行遍历，那将是十分耗时的。

2.3.2 链表

上面提到的就绪队列和阻塞队列，他们可以以链表的形式组织。从图中可以看出就绪队列指向PCB1，PCB1右边的数字“2”表示链表指向的下一个节点PCB2。依此类推，PBC以如下链表形式串联起来。

执行指针 -> PCB4
就绪队列指针 -> PCB1 -> PCB2 -> PCB3 -> PCB5
阻塞队列指针 -> PCB7 -> PCB8 -> PCB6

优点：非常直观，进程调度查找起来方便。

缺点：查找的时候需要从链表的头部开始进行遍历。如果进程状态发生变化，那么链表中进程节点的指针指向需要发生变动。

2.3.3 索引

优点：基于链表的方式进行进一步的优化，通过索引查找进程，可以将查找的时间复杂度由O(n)优化到O(1)。如果进程状态发生变化，只需要操作索引表，相比于操作整个链表更便捷。

缺点：建立了索引表，需要额外的内存空间。相当于是利用空间去换取时间。

3. 线程

3.1 线程结构

基于前面所描述，进程包含了两大特点：

1. 资源所有权：进程是一个容器，聚集了内存，I/O 设备，文件等资源，拥有这些资源的控制或所有权。
2. 调度/执行：具有执行状态（运行，就绪，阻塞等），可被操作系统的调度程序所调度。

早期的操作系统中，一般一个进程内只有一个线程，即为单线程进程模型。如下图，其中所包含的用户栈和内核栈，用于管理调度和返回的行为。当进程不运行的时候，CPU的寄存器中的内容将被保存起来，以便于下一次运行该进程时，恢复当时的状态。

那么为什么需要多线程？

1. 许多应用同时发生着多种活动，其中一些活动会被阻塞，将进程进一步分解为多个线程，可以更灵活地处理各种类型的活动。
2. 线程更加轻量级，创建和终止速度更快，且线程之间切换的速度会比进程切换更快。
3. 对于一些 I/O 密集型任务，多个线程允许这些并排执行，加快整体的速度。对于CPU密集型任务多线程没这个优势，因为本质上CPU同一时间只做一件事（什么是CPU密集型、I/O密集型？）。
4. 线程间通信的效率会高于进程间通信。一般进程间通信需要内核介入，而同一进程内的线程间共享该进程的内存和文件，不需要调用内核就可以实现通信。

上图为多线程进程模型，其中线程控制块，也被称为TCB（Thread Control Block）。

对于进程来说，进程 = 线程+资源。

我们一开始提及过，操作系统底层存在调度程序，调度程序可调度任务，而单线程进程，每个进程可以对应一个任务。现在，对于多线程的进程，每一个线程最终对于调度程序来说，都是一个任务，如下图（Linux系统）。因此也有一种流行的说法线程是CPU调度的基本单位

3.2 线程状态

和进程状态模型类似，线程的状态也有新建，运行，就绪，阻塞，终止。与进程状态相似，终止线程时将进入终止状态。但是区别于进程的是当一个进程被终止了，其内部的所有线程都会被终止。由于线程之间的并行关系，同一进程内，一个线程被阻塞了，不会影响到其他线程。

4. 进程调度

处理器调度，按照相对时间长短，可以分为长程调度，中程调度，短程调度。（常见调度还有I/O调度，但不属于处理器调度）。几种调度和进程的状态转换关系如下图

4.1 几种调度方式

4.1.1 长程调度

长程调度又称为高级调度，作业调度。
它控制系统的并发度，决定着哪一个批处理作业或者用户程序可以进入系统中处理，一旦运行进入，批处理作业或者用户程序就会变成进程，进入就绪队列。

4.1.2 中程调度

中程调度又称交换调度，中级调度。
核心思想是将进程从内存或CPU竞争中移出，之后进程能重新被调入内存，通过这种方式可控制内存中进程数量。如图中，从就绪队列中挂起的进程进入就绪挂起队列，从阻塞队列中挂起的进程进入阻塞挂起队列。就绪挂起队列中的进程激活，则进入就绪队列。

4.1.3 短程调度

短程调度又称为低级调度，大部分时候讲的进程调度都是特指短程调度，短程调度将就绪队列中的进程调度到CPU中执行。其中按照一定策略将CPU分配给一个就绪状态的进程，分为抢占式调度和非抢占式调度。

非抢占式调度：
非抢占式调度，就是挑选一个进程，将CPU分配给它，该进程一直运行到终止或者因为等待事件进入阻塞状态(图中红字标注)。显然这种调度方式存在一个硬伤：正在运行的进程如果需要运行很长时间，那么排在它后面的进程，只能一直等，直到它结束或阻塞。

抢占式调度：
抢占式调度就是允许进程执行到一半时，将进程停下，CPU分配给其它进程。

4.2 进程调度算法

常见的进程调度算法有：

• 先来先服服务
• 时间片轮转
• 最短作业优先
• 最短剩余时间优先
• 优先级调度
• 多级反馈队列调度

由于篇幅有限，每一种调度算法本文只做精要的介绍，想更进一步了解，可以根据最后的参考资料。

4.2.1 先来先服务

先来先服务（First Come First Serverd, FCFS）。先进就绪队列，则先被调度，先来先服务是最简单的调度算法。

先来先服务存在上面谈论过的问题：当前面任务耗费很长时间执行，那么后面的任务即使只需要执行很短的时间，也必须一直等待。属于非抢占式

4.2.2 时间片轮转调度

时间片轮转调度，即上面第一章所描述的方式。
每一个进程会被分配一个时间片，表示允许该进程在这个时间段运行，如果时间结束了，进程还没运行完毕，那么会通过抢占式调度，将CPU分配给其他进程，该进程回到就绪队列。这是一种最简单最公平的调度算法，但是有可能会存在问题。由于进程的切换，需要耗费时间，如果时间片太短，频繁进行切换，会影响效率。如果进程时间片太长，有可能导致排后面的进程等待太长时间。因此时间片的长度，需要有大致合理的数值。（《现代操作系统》的观点是建议时间片长度在20ms~50ms）。

4.2.3 最短作业优先

最短作业优先（Shortest Job First, SJF），顾名思义即进程按照作业时间长短排队，作业时间段的排前面先执行，如 下图。

4.2.4 最短剩余时间优先

最短剩余时间优先（Shortest Remaining Time Next），从就绪队列中选择剩余时间最短的进程进行调度。该算法可以理解最短作业优先和时间片轮转的结合。如果没有时间片，那么最短剩余时间其实就是最短作业时间，因为每个进程都是从头执行到尾。

4.2.5 优先级调度

假设就绪队列中有如下进程

按照优先级调度，执行顺序为p1->p3->p2。如果多个进程优先级相同，则按照先来先服务的方式依次执行。

优先级调度可以进一步细分为抢占式和非抢占式。

非抢占式：和上面提及的非抢占式类似，一旦该进程占有CPU就将一直执行到结束或者阻塞。

抢占式：进程执行期间，一旦有更高优先级的进程进入就绪队列，那么该进程就会被暂停，重回就绪队列，让更高优先级的进程执行。但是为了防止最高优先级进程一直执行，每个进程依然有自己的时间片，每次时间片结束后，会根据一定规则降低该进程优先级，避免某些最高优先级长作业进程一直占用CPU。

4.2.6 多级反馈队列调度

多级反馈队列调度基于时间片轮转和优先级调度，设置多个就绪队列，赋予每个就绪队列优先级，优先级越高的队列进程的时间片越短。如下图，第1级就绪队列优先级最高，进程的时间片长度最短，第2级就绪队列次之，以此类推。

当有新的进程创建时，先进入第1级就绪队列，时间片结束之前就运行完毕，则终止，否则进入第2级队列等待下一次调度。在n级队列之前，进程按照先到先服务规则依次调度，到了第n级队列（最后一级）采用时间片轮转调度。仅当第1级队列为空时，才调度第2级队列的进程，如果第i级队列的进程正在运行，此时有一个更高优先级的进程进入，则会停下第i级的进程，让它回到第i级队列尾部，转而执行更高优先级的进程，即满足优先级调度算法的原则。

5.进程间通信

进程间通信目的一般有共享数据，数据传输，消息通知，进程控制等。以 Unix/Linux 为例，介绍几种重要的进程间通信方式：共享内存，管道，消息，共享内存，信号量，信号

5.1 共享内存

多个进程可以读写同一块内存区域，是效率最高的进程间通信方式。

由于多个进程都可以读写内存，所以需要一定的同步机制来保证数据读写安全问题，关于这种机制，需要花费较大篇幅，这里读者可根据文章末尾提供的参考资料查看，笔者后续也会再另起一篇专门介绍。

5.2 管道

首先简单介绍一下什么是生产者/消费者问题。一个或多个生产者，生产一些数据，将其放置到共享缓冲区中，由消费者从缓冲区中取走数据。同一个缓冲区同一时间内只允许生产者或者消费者一方访问，不能同时访问。当缓冲区满了，生产者不再向其中添加数据，当缓冲区空了，消费者不再向其读取数据。

管道就是基于生产者/消费者模型来实现通信的，最基本的管道通信由一端的读进程，管道，还有另一端的写进程构成，通信的介质是共享文件，也称为管道文件。管道可以分为匿名管道和命名管道，此处主要介绍命名管道。管道有一个特点：数据一旦被读取了，就从管道中删除，以释放空间便于写入更多数据。如下图

如果需要实现双端通信，则需要两个管道，如下图。

这里有一个注意点：第二个图是半双工通信，即虽然通信可以双向，但是同一时间只能单向传输。管道可以理解为一种共享存储（是磁盘存储而不是内存存储）的优化方式，保证同一缓冲区的数据，只能一端写入，一端读取，无法多端同时进行写操作。

5.3 信号

信号一般用于一些异常情况下的进程间通信，是一种异步通信，它的数据结构一般就是一个数字，比如Unix就提供了如下信号（摘自《操作系统精髓与设计原理》第6版 6.7.5章节）

进程需要为信号设置相应的监听处理，当收到特定信号时，执行相应的操作，类似很多编程语言里的通知机制。

5.4 消息

消息可以作为两个不相关进程传递数据的方式，至少由一对原语构成

send(destination,message)
receive(source,message)

什么是原语：由若干条指令构成的程序段，用以执行特定的操作。消息通信可以分为直接通信和间接通信。

直接通信：发送进程直接发消息发给接收进程，把消息挂在接收进程的消息队列中，接收进程从消息队列中获取消息，是一种一对一的通信关系。

间接通信：消息不直接发送给接收者，而是发送到一个共享数据结构，该结构是一种消息队列，也称为信箱。这种方式相对于直接通信更加灵活，可以一对一，一对多，多对一，多对多。

通过消息格式中指定的id来确保进程的识别，如下是一种常见的消息数据格式（来自《操作系统精髓与设计原理》5.5.3）

消息在消息队列中，按照先进先出的原则。如果有消息比较紧急，发送者可以指定消息的类型，接收者在查询消息队列时，可以根据消息类型读取，不一定完全按照先进先出顺序。

消息相对于管道，有如下区别：

• 在传输中，管道基于字节流，消息基于格式文本。
• 介质上管道是文件，消息是内存
• 管道只能按照先进先出的顺序，消息不一定，它可以根据消息类型选择性接收处理，更加灵活。

5.5 信号量

信号量本质是一个计数器，当多进程共享内存时，用于保护共享内存，确保共享内存在同一时刻只有一个进程独享。

信号量需要初始化为某个值，当有进程对共享内存进行访问时，信号量减1，如果信号量值不为负数，则访问共享内存。当此时其新进程也要访问共享内存时，再次将信号量减一，如果信号量的值为负数，则新进程阻塞等待。

6. 总结

进程是操作系统最重要的概念之一，有比较多的细节点可以介绍，每一点还可以横向纵向再展开。笔者翻阅了大部分主流操作系统的书中关于进程管理的章节，总结出了本篇入门介绍，其中用户进程，内核进程，调度算法评价指标，进程和内存管理等内容这里受限于篇幅没有讨论。同步，并发，锁这几部分相对复杂且重要的内容打算后面另起章节单独描述。感谢阅读，如有疏漏或错误，还请指正????。

7. 参考资料

1. 趣谈 Linux 操作系统
2. 操作系统 ： 精髓与设计原理（原书第6版）
3. 操作系统导论
4. 现代操作系统（第3版）
5. 2019年操作系统考研复习指导
6. 操作系统概念
7. Linux 内核设计与实现
8. 操作系统真象还原
9. 深入理解计算机系统
10. 操作系统原理
11. Understanding User and Kernel Mode
12. 操作系统 CPU（处理器）调度
13. 优先级调度算法及其优缺点
14. 进程间通信IPC

有疑问加站长微信联系（非本文作者）