操作系统3-进程管理

收录于爱编程爱技术的孩子

2020-08-10 2020-08-16 约 7100 字预计阅读 15 分钟

警告

本文最后更新于 2020-08-16，文中内容可能已过时。

本文介绍操作系统最重要的一部分功能之一：进程管理，从进程的概念到进程的通信，再到死锁问题，最后结束进程的调度。

1. 进程与线程

1.1 进程

进程一个最简单的理解就是正在运行的程序，但与静态的程序只是简单的一段代码不同，进程在运行过程中会访问和影响系统的许多不同部分，这些部分包括

内存：进程对应的代码，它要读取和写入的数据都在内存中
寄存器：进程在执行指令时需要读取和更新寄存器
CPU：指令的执行需要 CPU 完成
其它：I/O 设备、文件句柄等

所有的这些统一构成了进程这个概念。我们可以很容易的理解，进程作为一个动态的概念，就需要完成创建、销毁、调度等许多工作，这些工作都由操作系统完成。操作系统完成这些工作依靠的是一个名为进程控制块（PCB）的结构，它是进程静态描述的一部分。

进程的静态描述分为三部分：程序、数据集、进程控制块（PCB）。

PCB 是进程动态特征的集中反映，也是系统感知进程的唯一途径，主要包括四部分：

进程描述信息：进程名、进程标识符、用户名、用户标识符，进程间的关系等
进程控制信息：进程当前状态，进程优先级，程序开始地址，各种计时信息，进程通信信息等
资源管理信息：内存管理、输入输出设备和文件系统的相关信息
CPU 现场保护结构

由于 PCB 包含的信息较多，其本身也不是常驻内存的，常驻内存的只有进程描述信息、控制信息和 CPU 现场保护等。

一开始的时候代码和数据位于外存，但进程创建时，操作系统就会把它们读入内存（尽管以前是一次性读入，但现在都是需要的时候才读入），然后为程序的运行时栈分配一些内存，用于存放局部变量、函数参数和返回地址，再为程序的堆分配一些内存，用于显式的内存申请。最后执行一些其它的初始化任务，比如与输入输出相关的，这些工作都完成后，操作系统开始启动程序并从入口处运行，将 CPU 的控制权移交新创建的进程，然后一条一条的执行对应的指令。

进程是资源分配的一个基本单位，但不是处理器调度的基本单位，调度的基本单位是线程。

1.2 线程

每个进程的创建都要涉及大量的内存分配和初始化任务，进程之间的切换需要保持寄存器、堆栈、PCB等相关信息，当进程数量较多时，这部分开销会明显增大。为了减少进程创建和切换的开销，提高执行效率和节省资源，人们在操作系统中引入了「线程」的概念。

线程是进程的一部分，这一句话理解如下：

一个进程可以拥有一个或多个线程
线程自己不拥有资源，而是共享进程的地址空间和资源，它仅拥有一些控制信息、栈和寄存器状态信息，如下图

线程是计算机调度的基本单位。与进程相似的是，操作系统通过线程控制块（TCB）来管理线程。

1.3 比较

拥有资源：进程是资源分配的基本单位，线程不拥有资源，但可以访问其所隶属的进程的资源（比如进程的代码段、数据段、打开的文件、I/O设备等）
调度：线程是处理器调度的基本单位。同一进程中，线程的切换不会引起进程切换，但从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换
系统开销：进程创建、撤销、切换的开销显著大于线程。
通信：由于同进程内线程间共享进程的代码、数据、内存和文件资源，因此可以通过共享内存通信；而进程间的通信需要内核提供保护和通信所需机制
并发性：进程间可并发执行，同一进程的线程间也可以并发执行

2. 进程状态及其转换

在进程的生命周期内，至少有5种基本状态：初始状态、执行状态、等待状态、就绪状态和终止状态。如下图

进程创建方式有两种：由系统根据任务统一创建和由父进程创建，创建的进程随后进入就绪态。

处于就绪状态的进程已经得到除 CPU 之外的所有其它资源，只要得到调度，就可以开始执行。

处于执行状态的进程由于时间片到期会转为就绪状态，继续等待调度，但如果产生了事件等待（比如键盘输入数据、其它进程产生的结果等），就会进入等待状态（也叫做阻塞状态）。

处于等待状态的进程等到自己需要的资源后，由系统或事件发生进程唤醒，进入就绪状态。

处于执行状态的进程可能由于如下几种原因终止：已完成所有的要求而正常终止、由于某种错误非正常终止、祖先进程要求终止。

终止状态完成如资源回收等后续处理工作。

注意：只有就绪态和运行态可以相互转换，其它都是单向的。

进程的状态信息记录在 PCB 中，另外，可以很清楚的看到，进程间的切换是一个必要的过程，进程从执行态离开意味着另一个进程开始了执行，而它本身可能并没有完成的所有的任务，这时候就需要保持进程离开前的执行状态。这就涉及到了进程上下文的概念。

进程的上下文是一个抽象的概念，指的是每个进程执行过的、执行时的以及待执行的指令和数据，在寄存器和堆栈中的内容。我们将已执行过的进程指令和数据在相关寄存器与堆栈中的内容称为上文，正在执行的指令和数据在寄存器与堆栈中的内容称为正文，待执行的指令和数据在寄存器与堆栈中的内容称为下文。

当进程不发生调度时，上下文的切换是由线程产生的，仅包括指令寄存器、程序计数器、栈指针等，当发生进程间调度时，上下文的切换就会包括代码段、数据、PCB等。所以进程上下文主要分为三种

用户级上下文：代码、数据、栈
寄存器级上下文：PC、PSW的值、栈指针、通用寄存器的值
系统级上下文：PCB 结构

当进程从执行态换出时，其上下文被保持到内存中，当进程重新被调度时，就可以从内存读取这些值进行恢复。

3. 进程调度

进程调度的主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理机。

3.1 先来先服务

先来先服务（First Come First Serve, FCFS）的含义很容易理解，就像它的名字，先转换成就绪状态的进程在就绪队列中占据更靠前的位置，也先被调度。

但是，执行时间短的进程如果排在执行时间长的进程之后，可能会等待很长时间，这是不公平的。

FCFS 是一种非抢占式的调度。

3.2 最短任务优先

可以用一种很简单的方式解决 FCFS 中的不公平现象，那就是让运行时间短的任务排在就绪队列的前面，先被调度。这叫做最短任务优先（Short Job First，SJF）。

这种方法的缺点是，执行时间长的进程可能永远得不到调度。

3.3 最高响应比优先

最高响应比优先（Highest Response-ratio Next, HRN）是对 FCFS 和 SJF 的平衡，它同时考虑每个进程的等待时间长短和执行时间长短，从中选出响应比最高的进程投入执行。

响应比 R 定义为 $R = (W+T)/T = 1 + W/T$，其中 $T$ 是执行时间，$W$ 是等待时间。

这样，即使是长作业，随着等待时间的增加，优先级也会增加，从而得到调度机会。

3.4 轮转法

前面三种算法的基本思路都是进程被调度后一直执行到任务完成，但我们通常还要考虑响应时间的问题，即要让所有执行的进程的响应时间都尽可能的良好。

轮转法（Round robin）用来解决响应时间问题，其基本思路是将 CPU 的处理时间划分为固定大小的时间片，如果一个进程在被调度选中后用完了自己的时间片还没有完成任务，就转为就绪状态并添加到就绪队列的末尾，同时，调度程序调度就绪队列的第一个进程。

轮转法的效率和时间片的长短有很大关系，时间片太短，频繁的上下文切换会影响系统性能，时间片过长，响应时间问题就不会得到改善。

轮转法可以看作一种基于CPU时间进行抢占的算法。

3.5 优先级法

优先级算法是指系统或用户按某种原则为进程定义优先级，然后根据优先级决定进程的调度优先权。优先级的选取有两种类型

静态法：即根据进程的静态特征，在进程开始前就确定优先级，在进程执行时优先级不改变。有以下几种方法
- 由用户根据紧急情况给与优先级
- 由系统或管理员根据进程类型给与优先级，比如，可以分为 I/O 繁忙的、CPU繁忙的、两种均衡的等
- 系统根据资源需求的情况确定优先级，比如，根据预估的处理时间、内存大小等确定
动态法：将进程的静态和动态特征结合起来确定优先级，在进程执行过程中优先级会不断变化，由以下几种办法
- 根据进程占有 CPU 时间的长短来确定
- 根据就绪进程等待 CPU 时间的长短来确定

注意，动态法需要不断计算进程的优先级，所以具有一定的开销。

3.6 多级反馈队列

前后的一些算法，如 FCFS、SJF 都需要知道进程将会运行多久，但实际上操作系统无法知道这一点。多级反馈队列（Multi-level Feedback Queue, MLFQ）采用的是一种根据历史数据缺点优先级的办法。

MLFQ 有多个独立的队列，每个队列有不同的优先级。任何时刻，一个进程只能存在于一个队列中，MLFQ 总是执行较高优先级队列中的进程。而且，同一队列的不同进程优先级是相同的。

进程可以简单的分两种：运行时间很短、频繁放弃 CPU 的交互型工作和需要很多 CPU 时间、响应时间不重要的长时间计算密集型工作。我们需要根据一些规则来调整它们的优先级

新加入的进程放在最上层的队列（具有最高的优先级）
进程用完一个时间片后，优先级降低一级（移入下一个队列）
如果进程在时间片未用完之前主动释放 CPU，优先级保持不变

这种设计对长作业比较公平，又能给短作业和交互型工作很好的响应时间，但是一些进程可能被动或主动的经常提前释放 CPU 从而一直占据较高的优先级，解决办法是

经过一段时间，就将系统中的所有工作重新假如最高优先级
一旦进程用完了其在某一层的时间配额，就降低其优先级

多级反馈队列是一种较好的调度算法，对各种情况都有比较好的性能，也是大多数系统目前使用的调度算法。

4. 进程的同步与互斥

由于计算机资源的有限，进程之间存在资源竞争和共享的情况。

如果多个不同进程访问同一段数据，那么把访问公共数据的这段程序叫做临界区。

互斥就是多个进程在同一时刻只有一个能进入临界区，同步就是并发执行的进程的执行条件与对方的执行结果有关，从而产生的执行的先后顺序。

4.1 互斥

互斥的实现办法一般是对临界区加锁，从而保证同一时间只有一个进程处于临界区。

然而，加锁法需要进程自己判断是否存在锁，这样可能出现不公平。举个例子说明，加入某个学生想使用某个人人都可以借用，且不规定使用时间的教室，他必须首先申请获得使用该教室的权利，然后再到教室看看教室是不是被锁上了，如果被锁上，他只好下次再来观察，这种观察持续到它进门为止。然而，两次观察期间，可能被其它获得申请的学生抢占，可能永远得不到使用权。

一种方法是设置一个管理员，记录所有获得申请在等待的学生名字，一旦教室空闲，就通知学生，这样就减少了学生多次检查的时间，也避免了可能出现饥饿情况。操作系统中，这个管理员就是信号量（Semaphore）。

在操作系统中，信号量 sem 是一个整数，在 sem 大于等于零的时候代表可供并发进程使用的资源实体数，在 sem 小于零的时候代表正在等待使用临界区的进程数。当信号量用于互斥时，应声明其所代表的含义，并设置一个大于零的初值。

信号量的数值仅能通过 P、V 原语改变，这两个原语操作的过程如下

P 原语
1. sem 减 1
2. 若 sem 减 1 后仍大于或等于零，则 P 原语返回，该进程继续执行
3. 若 sem 减 1 后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度
V 原语
1. sem 加 1
2. 若相加结果大于零，V 原语停止执行，该进程返回调用除，继续执行
3. 若相加结果小于或等于零，则从该信号的等待队列中唤醒一个等待进程，然后再返回原进程继续执行或转进程调度

可以看到，P、V 原语使用队列避免了加锁法不断的尝试操作，但要注意的是，P 原语的操作持续到进程从等待队列中被取出执行后才完成。最后，P、V 使用原语实现，是因为 P 和 V 的操作都是一系列步骤，如果中间被打断，比如减 1 后为调入队列，就会导致不一致性。

原语特性的实现可以使用加锁法。以 P 原语为例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
begin
    封锁中断
    lock(lockbit)
    val[sem] = val[sem]-1
    if val[sem] < 0
        保护当前进程 CPU 现场
        当前进程状态置为“等待”
        将当前进程插入信号 sem 等待队列
        转进程调度
    fi
    unlock(lockbit)
    开放中断
end

假设信号量的取值范围为 -1, 0, 1，实现两个并发进程 $P_A$ 和 $P_B$ 互斥的描述如下：信号量初值设为 1 表示没有并发进程使用该临界区，当一个进程想要进入临界区时，执行 P 原语操作将信号量减 1，此时信号量为 0，所以进程进入临界区开始执行。在该进程未执行 V 原语操作释放资源前，如果另一个进程想进入临界区，同样限制性 P 原语操作，将信号量减1，此时等于 -1，因此被阻塞进入等待队列。当第一个进程执行完毕，调用 V 原语操作将信号量加1，信号量的值变为0，第二个进程就被唤醒进入就绪队列，然后经由调度开始执行。第二个进程执行完 V 原语操作后，如果没有其它进程申请进入临界区，则信号量恢复到初始值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
typedef int semaphore;
semaphore sem = 1;

void PA() {
   P(sem);
   // 临界区
   V(sem);
}

void PB() {
   P(sem);
   // 临界区
   V(sem);   
}

4.2 同步

互斥是进程间对公共资源的竞争，同步则是进程间的另一种制约关系，比如一个进程的输出结果是另一个进程的执行条件，而且这种情况在操作系统中是普遍存在的。

一种解决办法是相互制约的进程互相给对方进程发送执行条件已具备的信号，这个信号被称为消息或事件，也可以当作信号量看待。但这里的信号量与互斥使用的信号量不同的是，它仅与相互制约的两个进程有关，而不是和所有并发执行的进程有关。

假设计算进程 $P_c$ 和打印进程 $P_p$ 合作完成计算和打印任务，它们使用一个缓冲区队列来传递数据，数据的发送和接收满足如下条件

$P_c$ 至少送一块数据进入缓冲区前，$P_p$ 不可能从缓冲区取出数据
$P_c$ 往缓冲队列送数据时，至少有一个缓冲区是空的
由 $P_c$ 发送的数据块在缓冲区队列中按 FIFO 方式排列

我们设信号量 Buffull 表示缓冲队列满，初始值为 n（缓冲队列的缓冲区长度）；设信号量 Bufempty 表示缓冲队列空，初始值为 0。那么进程同步的过程可以描述如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#define N 100
typedef int semaphore;
semaphore Buffull = N;
semaphore Bufempty = 0;

void PC() {
    P(Bufempty);
    按 FIFO 方式选择一个空缓冲区
    数据送入缓冲区
    V(Buffull);
}

void PP() {
    P(Buffull);
    按 FIFO 方式选择一个装满数据的缓冲区
    数据取出缓冲区
    V(Bufempty)
}

4.3 生产者-消费者问题

将并发进程的互斥与同步问题一般化，就可以得到一个抽象的一般模型，即生产者-消费者问题（producer-consumer problems）。

计算机系统中，每个进程都申请使用和释放各种不同类型的资源，这些资源可以是外设、内存及缓冲区等硬件资源，也可以是临界区、数据和例程等软件资源。我们把系统中使用资源的进程称为该资源的消费者，而把释放资源的进程称为资源的生产者。

在计算进程 $P_c$ 和打印进程 $P_p$ 共用缓冲区的例子中，计算进程把数据送入缓冲区，是生产者，打印进程从缓冲区取数据打印输出，是消费者。4.2 节已经给出了同步的例子，在此基础上，我们假设有界缓冲区是临界资源，那么生产者进程和消费者进程就必须互斥执行，因此我们添加一个互斥信号量 mutex。将整个过程描述如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define N 100
typedef int semaphore;
semaphore Buffull = N;
semaphore Bufempty = 0;
semaphore mutex = 1;

void PC() {
    P(Bufempty);
    P(mutex);
    按 FIFO 方式选择一个空缓冲区
    数据送入缓冲区
    V(Buffull);
    V(mutex);
}

void PP() {
    P(Buffull);
    P(mutex);
    按 FIFO 方式选择一个装满数据的缓冲区
    数据取出缓冲区
    V(Bufempty);
    V(mutex);
}

注：多个信号量的 P、V 原语操作次序很重要，次序混乱可能造成死锁。

5. 进程通信

进程间通信指的是进程间控制信息或大批量数据的传送，控制信息一般只传送一个或几个字节，因此也叫做低级通信，数据传送则需要进行大量数据交换，叫做高级通信。

5.1 信号量

进程间互斥与同步使用的信号量是通信方式的一种，而且是低级通信。

5.2 共享存储区

系统在存储中划出一块共享存储区，各进程间可通过对共享存储区中的数据进行读或写来实现通信

进程在通信之前应向系统申请共享存储区中的一个分区，并指定该分区的关键字，若系统已经给其他进程分配了这样的分区，则将该分区的描述符返回给申请者。接着，申请者把获得的共享存储区连接到本进程上，此后就像读写普通存储器一样。

共享存储区不要求数据移动，因此通信比较快。

共享存储区是一种高级通信。

5.3 消息缓冲

系统设置一组缓冲区，其中每个缓冲区可以存放一个消息。

当发送进程需要发送消息时，执行 send 系统调用，操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程 copy 到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。

在以后某个时刻，当接收进程执行到receive接收原语时，由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容copy到接收进程空间，之后收回缓冲区，如此就完成了消息的接收。

缓冲区应当是一个公共资源，因此，应当设立信号量来实现进程间的互斥操作。

5.4 管道

管道（pipe）是一条在进程间以字节流方式传送消息的通信通道。

逻辑上，我们可以将管道看作一个文件；物理上，管道利用文件系统的高速缓冲区来实现。

使用管道前必须建立管道，然后由发送进程调用文件系统的系统调用 write(fd[1], buf, size) 将 buf 种长度为 size 的消息送入管道入口 fd[1]，由接收进程使用系统调用 read(fd[0], buf, size) 从管道入口 fd[0] 读出 size 个字符到 buf 中。

我们可以举一个父进程和子进程利用管道通信的例子

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include<stdio.h>
main() {
    int x,fd[2];
    char buf[30],s[30];
    pipe(fd); // 创建管道
    while((x=fork())==-1); // 创建子进程失败则循环
    if(x==0){
        sprintf(buf,"this is an example\n");
        write(fd[1],buf,30); // 把 buf 中的字符写入管道
        exit(0)
    }else{ // 父进程返回
        wait(0);
        read(fd[0],s,30); // 父进程读管道中的字符
        printf("%s",s);
    }
}

管道按 FIFO 方式传送消息，而且只能是单向的。

上面描述的管道叫做无名管道，只能用于父子进程之间或父进程安排的各个子进程之间，还有一种叫做命名管道，用于 Server-Client 模式的通信。

6. 死锁

死锁是指各并发进程互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源，从而造成大家都想得到但都得不到资源的情况。

死锁的起因是并发进程的资源竞争，产生死锁的根本原因是系统提供的资源个数少于并发进程所要求的该类资源数。

解除死锁的方法一般分为预防、避免、检测和恢复三种

预防：预防是采用某种策略，限制并发进程对资源的请求，从而使得死锁产生的条件在任何时刻都不满足；
避免：避免是指系统在分配资源时，根据资源的使用情况提前做出预测，从而避免死锁的发生；
检测和恢复：设置专门的机制，在死锁发生时检测发生的位置和原因，然后通过外力破坏死锁条件，解除死锁的方式。

一般来说，通过预防和避免的手段解除死锁比较困难，而且需要较大的系统开销，实际通常使用检测与恢复的方法。

赞赏

支付宝

微信