进程管理

线程是最小的执行单元，而进程由至少一个线程组成。

如何调度进程和线程，完全由操作系统决定，程序自己不能决定什么时候执行，执行多长时间。

多进程和多线程的程序涉及到同步、数据共享的问题，编写起来更复杂。

进程概念

进程

我们编译的代码可执行文件只是储存在硬盘的静态文件，运行时被加载到内存，CPU 执行内存中指令，这个运行的程序被称为进程。

进程是对运行时程序的封装，操作系统进行资源调度和分配的基本单位。

如果包含线程的话，进程是资源分配的基本单位，线程是独立调度的基本单位。

线程

1. 线程是轻量级进程 (light-weight process)，也有 PCB，创建线程使用的底层函数和进程⼀样，都是 clone
2. 从内核⾥看进程和线程是⼀样的，都有各自不同的 PCB
3. 进程可以蜕变成线程
4. 在 linux 下，线程最是小的执⾏单位；进程是最小的分配资源单位

进程与线程的区别：

Ⅰ拥有资源

进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。

Ⅱ 调度

线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。

Ⅲ 系统开销

由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。

Ⅳ 通信方面

线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。

进程控制块

为了实现进程模型，操作系统维护着⼀张表格 (⼀个结构数组)，即进程表。

每个进程占有⼀个进程表项 (进程控制块)。

进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。

该表项是进程存在的唯⼀标识，其包括以下信息：

• 进程描述信息： 进程标识符、用户标识符等
• 进程控制和管理信息： 进程状态，进程优先级等
• 进程资源分配清单： 虚拟内存地址空间信息，打开文件列表，IO 设备信息等
• CPU 相关信息： 当进程切换时，CPU 寄存器的值都被保存在相应 PCB 中，以便 CPU 重新执行该进程时能从断点处继续执行

PCB 通过链表形式组织起来，比如有就绪队列、阻塞队列等，方便增删，方便进程管理。

并发与并行

• 单个核心在很短时间内分别执行多个进程，称为并发（同一时间段）
• 多个核⼼同时执行多个进程称为并行（同一时刻）
• 对于并发来说，CPU 需要从⼀个进程切换到另⼀个进程，这个过程需要保存进程的状态信息

进程状态

除了创建和结束⼀般有三个状态：

• 运行态： 该时刻进程占用 CPU

• 就绪态： 可运行，由于其他进程处于运行状态而暂时停止运行 等待被调度

• 阻塞态： 该进程正在等待某⼀事件发生（如等待输⼊/输出操作的完成）而暂时停止运行 等待资源

  阻塞态的进程占用着物理内存，在虚拟内存管理的操作系统中，通常会把阻塞态的进程的物理内存空间换出到硬盘，等需要再次运行的时候，再从硬盘换⼊到物理内存。

挂起态：新的状态，描述进程没有占用实际的物理内存空间的情况，这个状态就是挂起状态

• 阻塞挂起状态： 进程在外存（硬盘）并等待某个事件的出现
• 就绪挂起状态： 进程在外存（硬盘），但只要进⼊内存，马上运行

注意：

• 只有就绪态和运行态可以相互转换，其它的都是单向转换。
• 就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态
• 运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度
• 阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

守护进程

守护进程（Daemon Process），也就是通常说的 Daemon 进程（精灵进程），是 Linux 中的后台服务进程。

1. 它是⼀个生存期较长的进程，通常独立于控制终端并且周期性地执行某种任务或等待处理某些发生的事件
2. ⼀般采用以 d 结尾的名字
3. 所有的服务存在于 etc/init.d
4. 守护进程是个特殊的孤儿进程
5. 之所以脱离于终端是为了避免进程被任何终端所产生的信息所打断，其在执行过程中的信息也不在任何终端上显示
6. Linux 的⼤多数服务器就是用守护进程实现的

僵尸进程

多进程程序，父进程⼀般需要跟踪子进程的退出状态，当子进程退出，父进程在运行，子进程必须等到父进程捕获到了子进程的退出状态才真正结束。在子进程结束后，父进程读取状态前，此时子进程为僵尸进程。

设置僵尸进程的目的是维护子进程的信息，以便父进程在以后某个时候获取。

但是子进程停止在僵尸态会占据内核资源，所以需要避免僵尸进程的产生或立即结束子进程的僵尸态。

多进程

进程结构由以下几个部分组成：代码段、堆栈段、数据段。

代码段是静态的⼆进制代码，多个程序可以共享。

父进程创建子进程之后，父、子进程除了 pid 外，几乎所有的部分几乎⼀样。

父、子进程共享全部数据，子进程在写数据时会使用写时复制技术将公共的数据重新拷贝⼀份，之后在拷贝出的数 据上进行操作；不是对同⼀块数据进行操作；如果子进程想要运行自己的代码段，还可以通过调用 execv() 函数重新加载新的代码段，之后就和父进程独立开了。

进程调度

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

批处理系统

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

先来先服务 First-come first-serverd（FCFS）

非抢占式的调度算法，按照请求的顺序进行调度。

有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

短作业优先 Shortest Job first（SJF）

非抢占式的调度算法，按估计运行时间最短的顺序进行调度。

长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

最短剩余时间优先 Shortest Remaining Time next（SRTN）

最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。

当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

交互式系统

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

时间片轮转

将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。
当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

时间片轮转算法的效率和时间片的大小有很大关系，因为进程切换都要保存进程的信息并且载入新进程的信息

• 如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。
• 而如果时间片过长，那么实时性就不能得到保证。

优先级调度

为每个进程分配一个优先级，按优先级进行调度。

为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

多级反馈队列

一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。

多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，

例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。

每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

实时系统

实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

进程通信

进程同步与进程通信很容易混淆，它们的区别在于：

• 进程同步：控制多个进程按一定顺序执行；
• 进程通信：进程间传输信息。

进程通信是一种手段，而进程同步是一种目的。

• 同一主机

  • 无名管道 ：半双工（单方向交替传输）、只能在父子进程或者兄弟进程中使用
  • 有名管道：（FIFO）去除了管道只能在父子进程中使用的限制。
  • 信号：信号是软件中断，它是在软件层次上对中断机制的⼀种模拟，是⼀种异步通信的方式
  • 消息队列：A 进程要给 B 进程发送消息，A 进程把数据放在对应的消息队列后就可以正常返回了，B 进程需要的时候再去读取数据就可以了。

  相比于 FIFO，消息队列具有以下优点：

  • 消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难；
  • 避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法；
  • 读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收。

  • 共享存储：存储映射 I/O (Memory-mapped I/O) 使⼀个磁盘⽂件与存储空间中的⼀个缓冲区相映射。

  允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制，可以直接读写内存，所以这是最快的一种 IPC

  需要使用信号量用来同步对共享存储的访问。

  多个进程可以将同一个文件映射到它们的地址空间从而实现共享内存。另外 XSI 共享内存不是使用文件，而是使用内存的匿名段。

  • 信号量：它是一个计数器，用于为多个进程提供对共享数据对象的访问。

• 不同主机

  • Socket 套接字

进程同步

临界区

对临界资源进行访问的那段代码称为临界区。

为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。

同步与互斥

• 同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系。
• 互斥：多个进程在同一时刻只有一个进程能进入临界区。

互斥锁 Mutex

也叫互斥量，互斥锁是⼀种简单的加锁的⽅法来控制对共享资源的访问，互斥锁只有两种状态，即加锁 ( lock ) 和解锁 ( unlock )

1. 在访问共享资源后临界区域前，对互斥锁进行加锁
2. 在访问完成后释放互斥锁导上的锁
3. 对互斥锁进行加锁后，任何其他试图再次对互斥锁加锁的线程将会被阻塞，直到锁被释放

互斥锁的数据类型是： pthread_mutex_t

1
2
3
4
5
6
7
8
9
10

#include <pthread.h>
// 创建互斥锁
int pthread_mutex_init(pthread_mutex_t *restrict mutex, const pthread_mutexattr_t *restrict attr);
// 销毁互斥锁
int pthread_mutex_destroy(pthread_mutex_t *mutex);
// 上锁
int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex);
// 解锁
int pthread_mutex_unlock(pthread_mutex_t *mutex);

死锁 DeadLock

如果⼀个进程集合中的每⼀个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么该进程集合就是死锁

必要条件

死锁产生必须同时满足四个条件，只要其中任意一条不成立，死锁就不会发生。

• 互斥条件
  进程要求对所分配的资源（比如打印机）进行排他性控制，即在一段时间内某资源只能由一个进程占有。

  此时若有其他进程请求该资源，则请求进程只能等待。

• 不可剥夺条件
  进程所获得的资源在未使用完之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放）。

• 请求并保持条件
  进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已经被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。

• 循环等待条件
  存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。

鸵鸟策略

把头埋在沙子里，假装根本没发生问题。

因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。

当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。

大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

死锁检测与死锁恢复

每种类型⼀个资源的死锁检测：

通过检测有向图中是否存在环来实现，从⼀个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁发生。

每种类型多个资源的死锁检测：

每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

从死锁中恢复：

• 利用抢占恢复：将进程挂起，强行取走资源给另⼀个进程使用，用完再放回
• 利用回滚恢复：复位到更早的状态，那时它还没有取得所需的资源
• 通过杀死进程恢复：杀掉环中的⼀个进程或多个，牺牲掉⼀个环外进程

死锁预防

在程序运行之前预防发生死锁，其实就是破坏死锁产生的必要条件，破坏任何一个，死锁都不会发生。

• 破坏互斥条件：例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。
• 破坏请求和保持条件：一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。
• 破坏不可剥夺条件：保证每⼀个进程在任何时刻只能占用⼀个资源，如果请求另⼀个资源必须先释放第⼀个资源。
• 破坏循环等待条件：给资源统一编号，进程只能按编号顺序来请求资源。

死锁避免

• 安全状态：如果没有死锁发⽣，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每⼀个进程运行完毕
• 单个资源的银行家算法：一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。
• 多个资源的银行家算法：如果一个状态不是安全的，需要拒绝进入这个状态。

检查一个状态是否安全的算法如下：

1. 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
2. 假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
3. 重复以上两步，直到所有进程都标记为终止，则状态时安全的。

读写锁

在对数据的读写操作中，更多的是读操作，写操作较少，例如对数据库数据的读写应⽤。

为了满⾜当前能够允许多个读出，但只允许⼀个写入的需求，线程提供了读写锁来实现。

读写锁的特点：

• 如果有其它线程读数据，则允许其它线程执行读操作，但不允许写操作
• 如果有其它线程写数据，则其它线程都不允许读、写操作

POSIX 定义的读写锁的数据类型是： pthread_rwlock_t

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <pthread.h>
// 创建读写锁
int pthread_rwlock_init(pthread_rwlock_t *restrict rwlock, const pthread_rwlockattr_t *restrict attr);
// 销毁读写锁
int pthread_rwlock_destroy(pthread_rwlock_t *rwlock);
// 读锁定
int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock);
// 写锁定
int pthread_rwlock_wrlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_trywrlock(pthread_rwlock_t *rwlock);
// 解锁
int pthread_rwlock_unlock(pthread_rwlock_t *rwlock);

条件变量

与互斥锁不同，条件变量是用来等待而不是用来上锁的，条件变量本身不是锁。

条件变量用来自动阻塞⼀个线程，直到某特殊情况发生为止。

通常条件变量和互斥锁同时使用。相较于 mutex 而言，条件变量可以减少竞争。

条件变量的两个动作：

• 条件不满, 阻塞线程
• 当条件满足 通知阻塞的线程开始工作

1
2
3
4
5
6
7
8
9
10
11
12

#include <pthread.h>
// 创建条件变量
int pthread_cond_init(pthread_cond_t *restrict cond, const pthread_condattr_t *restrict attr);
// 删除条件变量
int pthread_cond_destroy(pthread_cond_t *cond);
// 唤醒线程
int pthread_cond_signal(pthread_cond_t *cond);
int pthread_cond_broadcast(pthread_cond_t *cond);
// 阻塞线程
int pthread_cond_wait(pthread_cond_t *restrict cond, pthread_mutex_t *restrict mutex);
int pthread_cond_timedwait(pthread_cond_t *restrict cond, pthread_mutex_t *restrict mutex,
const struct *restrict abstime);

信号量

信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作。

• down : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；
• up ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。

down 和 up 操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。

如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。

1
2
3
4
5
6
7
8
9
10
11
12
13

typedef int semaphore;
semaphore mutex = 1;
void P1() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

void P2() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

管程

使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。

管程有一个重要特性：在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。

管程引入了条件变量以及相关的操作：

• wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有。
• signal() 操作用于唤醒被阻塞的进程。