【操作系统-进程】进程的概念

0 补充

• 并发：指两个或多个事件在同一时间间隔内发生。
• 并行：指两个或多个事件在同一时刻发生。

【注】对于单处理机，在多道程序环境下，一段时间内，宏观上有多道程序在同时执行，而在每个时刻，单处理机仅能有一道程序执行。此时操作系统
是通过分时来实现并发性的，没有真正实现并行性。

1 进程

1.1 进程的组成（进程实体/进程映像）

一个进程实体（进程映像）由 PCB、程序段、数据段组成。进程是动态的，进程实体（进程映像）是静态的。进程是进程实体的运行过程，是系统进行资源分配、拥有资源和调度的一个基本单位。

程序和进程的区别：

• 进程控制块（PCB）：PCB 是进程存在的唯一标志，当进程被创建时，操作系统为其创建 PCB，当进程结束时，会回收其 PCB。

• 程序段：即程序的代码（指令序列）。
• 数据段：运行过程中产生的数据。

1.2 进程的状态

• 进程的状态：

• 进程的状态转换：

【注 1】假设一个单处理器系统，若同时存在 m 个进程，则 m 个进程不可能同时处于就绪态，但 m 个进程可能同时处于阻塞态（此时就绪队列为空），这时 CPU 将调度闲逛进程（idel）。
【注 2】系统中有 n 个进程，其中至少有一个进程运行，则就绪队列中最多有 n–1 个进程。

• 原语：原语的执行具有原子性，即执行过程只能一气呵成，期间不允许被中断，可以用“关中断指令”和“开中断指令”这两个特权指令实现原子性。

原语执行的一般过程：

• 更新 PCB 信息：（a）修改当前进程状态标志；（b）往 PCB 保存当前进程的运行环境；（c）根据 PCB 恢复欲切换进程的运行环境
• 将 PCB 插入对应的队列
• 分配/回收资源

【注】切换原语（切换到阻塞态）和唤醒原语需一一对应。

1.3 进程的通信（IPC）

• 共享存储：划分一块共享空间，通过对这片共享空间进行读写操作实现进程通信，需要使用同步互斥工具（PV操作）。

• 消息传递：进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。

间接通信方式：可以多个进程往同一个信箱 send 消息，也可以多个进程从同一个信箱中 receive 消息。

• 管道通信

管道文件：“管道”是一个特殊的共享文件，又名 pipe 文件，其实就是在内存中开辟一个大小固定的内存缓冲区。

【注】多进程读一个管道的解决方案：一个管道允许多个写进程，一个读进程。

2 线程

2.1 线程与进程的比较

2.2 线程的实现

2.3 多线程模型

2.4 相关例题

下面是一道将进程与线程、互斥结合在一起的考题：

【例】进程 P1 和 P2 均包含并发执行的线程，部分伪代码描述如下所示：

// 进程 P1
int x=0;
thread1()
{   
    int a; 
    a=1; // 1
    x+=1; // 2
}
thread2()
{   
    int a; 
    a=2; // 3
    x+=2; // 4
}

// 进程 P2
int x=0;
thread3()
{   
     int a; 
     a=x; // 5
     x+=3; // 6
}
thread4()
{   
     int b;
     b=x; // 7
     x+=4; // 8
}

需要互斥执行的操作是（ ）

A．a=1 与 a=2

B．a=x 与 b=x

C．x+=1 与 x+=2

D．x+=1 与 x+=3

【解】进程有独立的地址空间，因而进程 1 和进程 2 的 x 不是同一个 x；线程共享所属进程的地址空间，因而进程 1 的 x 被线程 1 和线程 2 所共享（x 是进程 1 的全局变量），进程 2 的 x 被线程 3 和线程 4 所共享（x 是进程 2 的全局变量）。在线程内定义的 a、b 变量均为线程自己所有，不共享到其他线程（局部变量）。

显然，语句 2、4 和语句 6、8 没有关系，不会发生互斥。语句 1 和 2 不会互斥，语句 5 和 6 也不会互斥，因为 a 和 b 是线程各自的局部变量。但是进程 1 内部的语句 2 和 4 会发生互斥，考虑到机器内部的执行过程，两个线程可能同时访问 x 所在的存储器，而两个线程对存储器同时进行写操作或读操作是不允许的。同理，进程 2 内部的语句 6 和 8 会发生互斥。只有 C 项符合题意。

3 调度

3.1 调度的层次

【注】挂起和阻塞的区别：两种状态都是暂时不能获得CPU的服务，但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中。

3.2 调度的时机

不能进行进程调度与切换的情况：

• 在处理中断的过程中
• 进程在操作系统内核程序临界区中
• 在原子操作（原语）过程中

【注】进程在普通临界区中是可以进行调度、切换的。

3.3 调度的方式

（届时将专门开一篇文章来整理）

• 非抢占式调度：又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
• 抢占式调度：又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

3.4 调度的算法

（届时将专门开一篇文章来整理）

• 先来先服务（FCFS）调度算法
• 短作业优先（SJF）调度算法
• 优先级调度算法
• 高响应比优先调度算法
• 时间片轮转调度算法
• 多级队列调度算法

4 同步和异步

4.1 临界资源和临界区

• 临界资源：一个时间段内只允许一个进程使用的资源称为临界资源。
• 进入区：检查是否可以进入临界区，若可以则上锁。
• 临界区（临界段）：进程中访问临界资源的代码段。
• 退出区：负责解锁。
• 剩余区：其余代码部分。

4.2 同步

同步指的是进程之间的直接制约关系。

同步互斥机制应遵守的四大准则：

• 空闲让进：临界区空闲时，应允许一个进程访问。
• 忙则等待：临界区正在被访问时，其他要访问的进程需等待。
• 有限等待：进程不能一直等待临界区释放，否则出现“饥饿”现象。
• 让权等待：进不了临界区的进程要下处理机，以免进程陷入“忙等”状态。

【注 1】关于“让权等待”的问题，除了信号量方法能解决外，其他方案无法解决，因为这些方案都包含了 while 语句，进程会一直卡在 while 语句死等。

【注 2】注意区别“忙则等待”、“有限等待”和“让权等待”：违反“有限等待”是有人想进临界区，但一直进不了，一直死等；违反“让权等待”是有人进了临界区，其他人在干等这个人退出临界区；违反“忙则等待”是有人进了临界区，其他人也闯进来了。

4.3 互斥

互斥指的是进程之间的间接制约关系。

4.3.1 软件实现

如何分析出这些算法的缺点？注意到这些算法通常由“检查”和“上锁”两个操作组成，而这两个操作必须一气呵成地完成才能达到目的。因此，我们只需让这些操作不再一气呵成地完成，缺点也就自然分析出来了。

如何分析出这些算法是否可能引起饥饿？将算法的缺点分析出来，自然就知道会不会产生饥饿现象了。只有违反“有限等待”的算法可能导致饥饿现象，而违反“忙则等待”则是“喂得过饱”了。

来看下面实例：

（1）单标志检查法

// 全局变量
turn = 1;

// P1 进程
while (trun != 1); // 1（检查）
critical section;
turn = 2;
remainder section;

// P2 进程
while (turn != 2); // 2（检查）
critical section;
turn = 1;
remainder section;

• 缺点分析：交替执行语句 1 和 2 时，语句 1 的循环条件不满足，进程 1 进入临界区，语句 2 的循环条件满足，进程 2 等待。看起来没什么问题，但若进程 1 连续两次申请访问临界区时，turn 值为 2，依然进不去临界区，因此不满足“空闲让进”原则。
• 饥饿分析：不会产生饥饿。

（2）双标志先检查法

// 全局变量
flag[0] = false; 
flag[1] = false;

// P1 进程
while (flag[2]); // 1（检查）
flag[1] = TRUE; // 2（加锁）
critical section;
flag[1] = FALSE;
remainder section;

// P2 进程
while (flag[1]); // 3（检查）
flag[2] = TRUE; // 4（加锁）
critical section;
flag[2] = FALSE;
remainder section;

• 缺点分析：交替执行语句 1、3、2、4，执行语句 1 和 3 时，由于 flag[1] 和 flag[2] 都为 false，因此会跳出循环，这就意味着两个进程都进入了临界区，违反了“忙则等待”原则。
• 饥饿分析：不会产生饥饿现象。

（3）双标志后检查法

// 全局变量
flag[0] = false; 
flag[1] = false;

// P1 进程
flag[1] = TRUE; // 1（加锁）
while (flag[2]); // 2（检查）
critical section;
flag[1] = FALSE;
remainder section;

// P2 进程
flag[2] = TRUE; // 3（加锁）
while (flag[1]); // 4（检查）
critical section;
flag[2] = FALSE;
remainder section;

• 缺点分析：交替执行语句 1、3、2、4，执行语句 1 和 3 后，flag[1] 和 flag[2] 都为 true。执行语句 2，由于 flag[1] 为 true，因此进程 1 会一直卡在 while 循环；执行语句 4，由于 flag[2] 也为 true，因此进程 2 也会一直卡在 while 循环。两个进程无限等待下去，但是临界区又处于空闲状态，因而违反了“空闲让进”和“有限等待”原则。
• 饥饿分析：违反了“有限等待”原则，可能产生饥饿现象。

（4）Peterson 算法

// 注意 turn 为全局变量

// P1 进程
flag[1] = TRUE; // 1
turn = 2; // 2

while (flag[2] && turn == 2) // 3
critical section,
flag[1] = false;
remainder section;

// P2 进程
flag[2] = TRUE; // 4
turn = 1; // 5

while (flag[1] && turn == 1); // 6
critical section;
flag[2] = false;
remainder section;

• 缺点分析：交替执行语句 1、4、2、5、3、6，执行语句 1、4、2、5 后，flag[1] = TRUE，turn = 1，flag[2] = TRUE。执行语句 3，循环条件不满足，进程 1 进入临界区。执行语句 4，循环条件满足，进程 2 将一直等待下去，这违反了“让权等待”。因而除了“让权等待”没有遵守外，其他三个原则都遵守了。
• 饥饿分析：不会产生饥饿现象。

4.3.2 硬件实现

【注】后两者是用硬件实现的，它把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作，但仍未解决让权等待的问题。

4.4 信号量

P 操作负责分配资源，没有资源的时候就等着（进入阻塞队列）。V 操作负责释放资源，在阻塞队列不为空的时候唤醒某个进程进入临界区。

• P 操作：使信号量 - 1。若信号量 < 0，则执行 P 操作的进程被阻塞，否则进程继续执行。
• V 操作：使信号量 + 1。若信号量 ≤ 0，则被 P 操作阻塞的进程被解除阻塞。

4.4.1 实现进程同步

一般信号量：初值一般为可用物理资源的总数，用于进程同步问题。若期望的消息尚未产生，则初值应设为 0；若期望的消息已存在，则初值应设为一个非零正整数。

• 信号量 > 0：表示某类可用资源的数量。
• 信号量 = 0：表示某类资源已经没有。
• 信号量 < 0：表示某类资源已经没有，还有因请求该资源而被阻塞的进程。
• 信号量 ≤ 0 的绝对值：表示等待该资源的进程数。

实现功能：执行完 A 后才能执行 B。因此，执行 A 后执行 V 操作，再执行 P 操作，然后执行 B。

信号量 S=0;

P1(){
    A;
    V(S);
}

P2(){
    P(S);
    B;
}

4.4.2 实现进程互斥

二元信号量：取值仅为“0”或“1”，用作实现互斥。初值一定为“1”，此时 P、V 操作需夹紧临界区。

实现功能：两个进程对临界资源的互斥访问。

信号量 S=1;

P1(){
    P(S);
    P1的临界区;
    V(S);
}

P2(){
    P(S);
    P2的临界区;
    V(S);
}

4.4.3 实现前驱关系

例如：

• P1–(信号量 a)–>P2
• P1–(信号量 b)–>P3
• P2–(信号量 c)–>P3

分析：

• P1(V(a))–(信号量 a)–>(P(a))P2
• P1(V(b))–(信号量 b)–>(P(b))P3
• P2(V©)–(信号量 c)–>(P©)P3

代码：

信号量 a, b, c = 0;

P1(){
    ...;
    V(a); V(b);
}

P2(){
    P(a);
    ...;
    V(c);
}

P3(){
    P(b); P(c);
    ...;
}

4.5 管程

管程的组成（类似于面向对象的类）：

• 局部于管程的共享数据结构说明；
• 对共享数据结构进行操作的一组过程；
• 对局部于管程的共享数据设置初始值的语句；
• 管程有一个名字。

管程的基本特征：

• 每次仅允许一个进程在管程内执行某个内部过程。
• 一个进程只有通过调用管程内的过程才能进入管程访问共享数据。
• 局部于管程的数据只能被局部于管程的过程所访问。
• 互斥特性由编译器实现。

信号量与条件变量：

阻塞原因定义为条件变量，每个条件变量保存一个等待队列。它们的区别：

5 死锁

5.1 死锁产生的原因

• 对不可剥夺资源的竞争，可能引起死锁。
• 请求和释放资源的顺序不当。
• 信号量使用不当。

【注】死锁和饥饿的区别：

5.2 死锁的四个必要条件

• 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。
• 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
• 请求并保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
• 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

【注】发生死锁时一定有循环等待，但是发生循环等待时未必死锁。

由以上四个必要条件，可得以下常用结论：

• 若系统有 x 个进程，每个进程需要 y 个资源，则该系统必然不会发生死锁的最少资源是 x*(y-1) + 1 个。
• 若系统有 x 个资源，每个进程需要 y 个资源，则该系统可能发生死锁的最小进程数为 x / (y-1)。

【推导思路】系统有 x 个进程，每个进程已拥有 y-1 个资源，此时如果资源总数刚好为 x*(y-1) 个，意味着资源已用完，则一定发生死锁，此时再多加一个资源，令其中一个进程获得所需的最大资源，则死锁解除。即使每个进程所需资源数各不相同，一样可以按此思路分析。

5.3 死锁的处理策略

5.3.1 死锁预防（不允许死锁发生-静态策略）

5.3.2 死锁避免（不允许死锁发生-动态策略）

安全性算法和银行家算法：

【例】已知资源可用数为 S(x,y,z)，某时刻状态如下：

则 x、y、z 取以下值时系统处于安全状态？

（1）1,4,0；（2）0,6,2；（3）1,1,1；（4）0,4,7。

（1）【解】S(1,4,0) > A(0,0,1)，S(1,4,0) > C(1,0,0)，说明可以分配给 A 和 C。回收 A、C 资源后 S(1+0+1, 4+0+3, 0+3+5) = S(2,7,8)。

考虑 B、D、E 进程，S(2,7,8) > B(0,7,5)，S(2,7,8) > D(0,6,2)，S(2,7,8) > E(0,6,4)，说明可以分配给 B、D 和 E。回收 B、D、E 资源后 S(2+1+0+0, 7+0+0, 8+0+2+1) = S(3,7,11)。

安全序列可以为 A、C、B、D、E，也可以为 C、A、D、B、E 等，因此处于安全状态。

（2）【解】S(0,6,2) > A(0,0,1)，S(0,6,2) = D(0,6,2)，说明可以分配给 A 和 D。回收 A、D 资源后 S(0+0+0, 6+0+0, 2+3+2) = S(0,6,7)。

考虑 B、D、E 进程，S(0,6,7) > D(0,6,2)，说明可以分配给 D。回收 D 资源后 S(0+0, 6+0, 7+2) = S(0,6,9)。

考虑 B、E 进程，S(0,6,9) < B(0,7,5)，S(0,6,9) < E(0,6,4)，说明不可以分配给 B、E，因此系统处于不安全状态。

（3）【解】S(1,1,1) > A(0,0,1)，S(1,1,1) > C(1,0,0)，说明可以分配给 A 和 C。回收 A、C 资源后 S(1+0+1, 1+0+3, 1+3+5) = S(2,4,9)。

考虑 B、D、E 进程，S(2,4,9) < B(0,7,5)，S(2,4,9) < D(0,6,2)，S(2,4,9) < E(0,6,4)，说明不可以分配给 B、D 和 E。因此处于不安全状态。

（4）【解】S(0,4,7) > A(0,0,1)，说明可以分配给 A。回收 A 资源后 S(0+0, 4+0, 7+3) = S(0,4,10)。

考虑 B、C、D、E 进程，S(0,4,10) < B(0,7,5)，S(0,4,10) < C(1,0,0)，S(0,4,10) < D(0,6,2)，S(0,4,10) < E(0,6,4)，说明不可以分配给 B、C、D、E，因此处于不安全状态。

【注】如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）。

5.3.3 死锁检测和解除（允许死锁发生）

1. 死锁检测

（1）资源分配图的组成：

（2）使用死锁检测算法简化资源分配图：

• 找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。
• 消去它所有的请求边和分配边，使之称为孤立的结点。
• 继续对剩余点进行一系列简化，若能消去图中所有的边，则称该图是可完全简化的。

（3）死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁。注意，并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程。

2. 死锁解除

• 方法：资源剥夺法；撤销进程法；进程回退法。
• 如何决定“对谁动手”：进程优先级；已执行多长时间；还要多久能完成；进程已经使用了多少资源；进程是交互式的还是批处理式的。