进程与线程

第二章_进程与线程

2.1 进程管理

2.1.1 进程的基本概念和组成

从不同视角出发，进程可有不同的定义，比较典型的定义如下。

1. 进程是正在执行的程序实例。
2. 进程是程序及其数据从外存加载到内存后，在 CPU 上运行的过程。
3. 进程是具有独立功能的程序在一个特定数据集合上的执行活动。

在传统操作系统中，进程被正式定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。这里所说的 “系统资源” 不仅包括内存空间、I/O 设备等硬件资源，也包括 CPU 的使用权，而 CPU 的使用权通常通过时间片的分配来实现。正因进程是资源分配与调度的基本单位，它必然不是静态的程序，而必须是一个动态的、具有生命周期的过程性实体。

进程的组成 总体如下图所示： 通过简单讲述一个 进程的运行过程 来说明 PCB（进城控制块） 的概念，如下图所示：

2.1.2 进程的特征

进程是动态的，程序是静态的，相比于程序，进程拥有一下特征：

1. 动态性（进程最基本的特征）： 进程是程序的一次执行过程，是动态地产生、变化和消亡的
2. 并发性： 内存中有多个进程实体，各进程可并发执行
3. 独立性： 进程是能独立运行、独立获得资源、独立接受调度的基本单位
4. 异步性： 各进程按各自独立的、不可预知的速度向前推进，操作系统要提供 “进程同步机制” 来解决异步问题
5. 结构性： 每个进程都会配置一个 PCB。结构上看，进程由程序段、数据段、PCB 组成

2.1.3 进程的状态和转换

进程的状态和转换如下图所示（耳熟能详的丁字裤模型）： 一个进程的状态具体是由进程 PCB 中的 state 变量进行标识（1 为就绪态，2 为阻塞态）的，为了方便管理，操作系统还会将处于同一状态的进程进行组织起来，具体怎么组织如下图所示：

2.1.4 进程控制

所谓进程控制就是操作系统实现 具体怎么实现进程的状态的转换。

实现状态转换的操作需要使用 原语 来实现，原语用开 / 关中断来实现，是一种特殊的程序，必须一气呵成不能中断。具体原语怎么实现，如下图所示： 而与 进程控制相关的原语 有下面这些：

1. 进程的创建
2. 进程的终止
3. 进程的阻塞（阻塞和唤醒要成对出现）
4. 进程的唤醒
5. 进程的切换

2.1.5 进程通信

2.1.5.1 进程通信

进程通信就是指两个进程之间进行数据的交互。 由于不同进程间无法直接访问对方的地址空间，这是为了保证安全。所以要实现进程间的通信必须要操作系统的支持，操作系统给出的进程通信方式有三种：共享存储、消息传递、管道通信。 如下图所示：

2.1.5.2 信号

本小节思维导图如下： 信号：用于通知进程某个特定事件已经发生，进程收到一个信号后，对该信号进行处理。（不是信号量，也不要去类比成中断信号的那个信号！） 信号的接收与处理全流程 如下图所示： 常见的信号默认处理 如下图所示： 常见疑难点 如下图所示：

2.2 线程管理

2.2.1 线程的基本概念

为什么要引入线程 如下图所示： 引入线程之后带来的变化 如图所示： 线程的基本属性 如图所示：

2.2.2 线程的实现方式和多线程模型

2.2.2.1 用户级线程

在早期操作系统只支持进程的情况下，用户程序想要实现线程，只能通过 线程库 的方式实现纯用户级线程，举例代码如下所示：

int main() {
int i = 0;
while (true) {
  if (i==0){处理视频聊天的代码;}
  if (i==1){处理文字聊天的代码;}
  if (i==2){处理文件传输的代码;}
  i = (i+1)%3;  //i的值为 0,1,2,0,1,2...
  }
}

从代码上看这种线程其实就是一段代码逻辑，上述三段代码逻辑分别看成一段线程。while 循环就是个最弱智的线程库。

用户级线程具有下面这些 特点：

1. 线程的管理工作由谁来完成？ 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）
2. 线程切换是否需要 CPU 进行变态？ 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。
3. 操作系统能否意识到用户级线程的存在？ 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。“用户级线程” 就是 “从用户视角看能看到的线程”
4. 用户级线程的优缺点？ 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。

2.2.2.2 内核级线程

所谓操作系统支持线程，支持的就是内核级线程。内核级线程才是处理机调度的基本单位。大多数现代操作系统都实现了内核级线程。

如图所示，下图右侧的问题回答，对应的问题和上方用户级线程是一样的：

2.2.2.3 多线程模型

用户级线程和内核级线程各有优缺点，现代程序设计喜欢将两者综合，即在操作系统支持内核级线程的情况下，在程序设计时才用线程库（去捏造假线程），使得既有用户级线程，又有内核级线程。一个或多个用户级线程能够映射到一个内核级线程。 由此分为三种类型，分别如下图所示：

2.2.3 线程的状态与转换

线程的组织与控制 和进程非常类似，会为每个线程维护一个线程控制快（TCB），如图所示： 同一进程中的线程共享该进程的地址空间和全局变量。每一个线程拥有 独立的私有栈，这些栈位于进程的地址空间内，因此从技术上讲，一个线程可以访问另一个线程的栈内容，然而，这种做法 严格违反编程规范，会破坏线程封装性和程序正确性，实际开发中应严格避免。

线程的状态转换 也和进程几乎一样，只需要重点记忆下面三种即可：

2.3 CPU 调度

2.3.1 调度的概念和层次

在多道程序系统中，进程的数量通常远多于 CPU 的个数，因此多个进程争用 CPU 的情况在所难免。CPU 调度 是指按照一定的算法（兼顾公平性与效率），从就绪队列中选择一个进程，并将 CPU 分配给它运行，从而实现多个进程的并发执行。

CPU 调度是多道程序操作系统的基础，也是操作系统设计的核心问题之一。

一个作业从提交到完成，通常需要经历一下三级调度： 作业：就是用户提交给操作系统的一项完整任务（如 “编译整个工程并输出结果”），通常会由一个或者多个进程完成，一个进程也能同时服务多个作业（比如 Web 进程）

1. 高级调度（作业调度）：
2. 中级调度（内存调度）：
3. 低级调度（进程调度）：

补充知识： 在中级调度中提到了挂起这个概念，关于挂起这个概念其实存在一个 七状态模型（408 大纲貌似没有要求掌握，自命题可能会考），如下图所示： 三种层次调度 对比如下：

2.3.2 进程调度的时机、切换与过程、方式

本小节思维导图如下图所示： 进程调度的时机 如下图所示： 进程调度的方式 如下图所示： 进程的切换与过程 如下图所示；

2.3.3 调度机和闲逛进程

2.3.3.1 调度机 / 调度程序

调度机 / 调度程序的概念 如图所示： 注意：调度机不是一个硬件结构，是一个程序！平时存放在操作系统内核代码里，平时驻留在内存中。

2.3.3.2 闲逛进程

闲逛进程 的基本概念如图所示，就是 CPU 永远的备胎：

2.3.4 调度的目标（调度算法的评价指标）

本小节思维导图如下： 不同的调度算法具有不同的特性，因此在选择调度算法的时候，必须考虑其适用场景与性能表现。为了客观比较 CPU 调度算法的优劣，人们提出了多种衡量标准，下面主要介绍几种：

1. CPU 利用率：CPU 利用率 = CPU 有效工作时间 / (CPU 有效工作时间 + CPU 空闲等待时间)
2. 系统吞吐量：单位时间内系统完成作业的数量。
3. 周转时间：
4. 等待时间：
5. 响应时间：响应时间是指从用户提交请求到系统首次响应请求所经历的时间。在交互式系统中比等待时间根据有实际意义。

2.3.5 调度算法

操作系统中存在多种调度算法，有的使用于作业调度，有的适用于进程调度。下面介绍几种常用的调度算法： 注意：下方所举的所有例子都是纯计算进程（即只有就绪态和运行态，这样比较简单）。

2.3.5.1 先来先服务、短作业优先、高响应比优先

本小节总结如下：

1. 先来先服务（FCFS）：
2. 短作业优先： 关于短作业优先，有这些点必须要注意：
   1. 如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的
   2. 很多书上都会说“SJF 调度算法的平均等待时间、平均周转时间最少” 严格来说，这个表述是 错误 的，不严谨的。之前的例子表明，最短剩余时间优先算法（SSJF） 得到的平均等待时间、平均周转时间还要更少 应该加上一个条件“在所有进程同时可运行时，采用SJF调度算法的平均等待时间、平均周转时间最少”； 或者说“在所有进程都几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少”； 如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法（最短剩余时间优先, SRNT算法）的平均等待时间、平均周转时间最少”
   3. 虽然严格来说，SJF的平均等待时间、平均周转时间并不一定最少，但相比于其他算法（如FCFS），SJF依然可以获得较少的平均等待时间、平均周转时间
   4. 如果选择题中遇到“SJF 算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项
3. 高响应比优先（HRRN）： 高响应比优先是对先来先服务和短作业优先的一个折中：

2.3.5.2 时间片轮转、优先级、多级反馈队列

本小节总结如下：

1. 时间片轮转算法：

2. 优先级调度算法： 关于优先级调度算法还有一些补充，如下图所示：

3. 多级反馈队列： 是对其他调度算法的一个折中，比较复杂，实际中也能是非抢占式，但是考研以非抢占式为准。

2.3.5.3 多级队列调度算法

很简单，一张图就能说明：

2.3.6 多处理机调度

本小节思维导图如下： 多处理机调度（即多个 CPU 参与调度），主要面临两个核心矛盾：

1. 处理器亲和性：尽量让一个进程调度到同一个 CPU 上运行，以发挥 CPU 中缓存（缓存里存的是热点数据哈，不是原先进程的状态，那在 PCB 里面）的作用。
2. 负载均衡：尽可能让每个 CPU 都同等忙碌。

然而，负载均衡通常会抵消处理器亲和性带来的好处，因此在某些系统中，只有当不平衡到达一种程度后，才会触发进程迁移。

多处理机调度通常有 两种方案，如下所示：

2.4 同步和互斥

2.4.1 同步和互斥的基本概念

前面已经提过 异步 的概念，即多个进程间各忙各的，彼此独立以不可知的速度推进，谁也不用等谁。 而这里提到 同步（直接制约关系） 的概念，即各进程间存在制约关系，不是说进程完全没有异步性了，只是需要协调异步进程间的进行。比如系统为 1 + 2 * 3 创造两个进程，那么乘法进程必须在加法进程之前执行。 所谓 互斥（间接制约关系），即当一个进程正在临界区中使用邻接资源是，其他试图访问该资源的进程必须等待，只有当占用临界资源的进程退出临界区后，其他进程才被允许进入。

互斥和临界资源的关系 如下所示：

2.4.2 进程互斥的软件实现办法

本小节思维导图如下图所示：

2.4.2.1 单标志位法

2.4.2.2 双标志位先检查法

2.4.2.3 双标志位后检查法

2.4.2.4 Peterson 算法

这个算法是前面三种方法的一个综合。

2.4.3 进程互斥的硬件实现办法

本小节思维导图如下：

2.4.3.1 中断屏蔽方法

2.4.3.2 TestAndSet 指令

2.4.3.3 Swap 指令

2.4.4 互斥锁

可以说前面提到的 进程互斥的软硬件实现办法 都是互斥锁的实现办法。而 互斥锁 是这些实现办法的 上层抽象。

可以就把互斥锁的 “锁” 理解为一个布尔型变量。

解决临界区问题最简单的工具是互斥锁（mutex lock）。一个进程在进入临界区前调用 acquire() 以获得锁；在退出临界区时调用 release() 以释放锁。每个互斥锁包含一个 布尔变量 available，用于表示锁是否可用。若锁可用，则调用 acquire() 会成功，并将锁置为不可用。当一个进程试图获取不可用的锁时，它将被阻塞，直到锁被释放。其过程描述如下：

acquire() {              //获得锁的定义
    while (!available)   //忙等待
        ;
    available = false;   //获得锁
}

release() {              //释放锁的定义
    available = true;    //释放锁
}

acquire() 或 release() 的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。

上述互斥锁也称 自旋锁，其主要缺点是忙等待：当有一个进程在临界区中时，任何其他进程在进入临界区前都必须连续循环调用 acquire ()。类似的还有前面介绍的单标志法、TS 指令和 Swap 指令。当多个进程共享同一 CPU 时，这种连续循环显然浪费了 CPU 周期。因此，自旋锁通常用于多处理器系统，一个线程可以在一个处理器上 “旋转”，而不影响其他线程的执行。自旋锁的优点：进程在等待期间没有上下文切换；若持有锁的时间较短，则等待代价较低。

2.4.5 信号量机制

本小节思维导图如下： 信号量机制是不仅能接解决互斥问题，还能解决同步问题。它仅能通过两个标准的 原语 进行访问（注意是 PV 操作本身是原语，不是临界区是原语）：

1. P 操作（为什么叫这个不用管了）：Wait()
2. V 操作（为什么叫这个不用管了）：signal()

首先思考两个问题：

1. 前面软硬件实现方式都没有满足“让权等待”原则，该怎么满足这个原则？
2. 软件实现方式中，双标志位方式的主要问题就是检查和上锁不能一气呵成。能不能做成原语操作？

2.4.5.1 整型信号量

2.4.5.2 记录型信号量

记录型信号量和整型信号量的 区别 在哪：记录型的信号量是一个结构体，它不仅能表示因为这个临界资源而阻塞的进程队列，他其中的整型变量的负数还有意义，比如 -1 表示一个进程被阻塞。

2.4.5.3 使用信号量机制实现进程互斥、同步与前驱关系

开始我还以为就只是 PV 操作之间夹一段代码那么简单呢，结果是我把信号量机制想着只能用于实现互斥了。本小节思维导图如下：

使用信号量机制实现进程互斥：

使用信号量机制实现进程同步：

使用信号量机制实现进程前驱： 妙啊！

2.4.5.4 生产者消费者问题（互斥同步问题（偏同步））

关于生产者和消费者问题总体的概述如下图所示： 值得注意的是，相邻 P 操作和相邻 V 操作间能不能调换？如下图所示： 生产者消费者问题是一个经典的 PV 操作题目，关于 PV 操作题目的概述 如下：

2.4.5.5 多生产者消费者问题

问题描述： 桌上有一个盘子，最多只能容纳一个水果。爸爸专门向盘中放入苹果，妈妈专门放入橘子；女儿只吃盘中的苹果，儿子只吃盘中的橘子；只有当盘子为空时，爸爸或妈妈才能向其中放入一个水果；只有当盘中有自己所需的水果时，儿子或女儿才能从中取出并食用。

问题分析：

1. 关系分析：爸爸和妈妈在向盘中放入水果时存在互斥关系：爸爸与女儿、妈妈与儿子之间分别构成同步关系（爸爸放苹果后，女儿才能取用；妈妈放橘子后，儿子才能取用）；儿子与女儿各自等待不同的水果，因此他们之间既无互斥也无同步关系。
2. 整理思路：可抽象为两个生产者（爸爸、妈妈）和两个消费者（女儿、儿子），共享一个容量为 1 的缓冲区。由于不同类型的产品（苹果、橘子）需由不同的消费者消费，故不能仅使用一个 full 信号量来表示满状态，而需为每种产品设置独立的同步信号量。
3. 信号量设置：互斥信号量 plate，控制对盘子的互斥访问，初值为 1；同步信号量 apple，表示盘中是否有苹果，初值为 0；同步信号量 orange，表示盘中是否有橘子，初值为 0。

如何实现： 解决这类问题的时候 值得注意的 是：

1. 我们发现这个问题其实并 不需要互斥变量： 所以，如果临界资源信号量是 1，那么说不定可以不用设置互斥变量。当然，具体问题具体分析。 其实考试的时候如果来不及，直接加上互斥变量也没问题，只是注意实现互斥操作的 P 操作一定要在实现同步的 P 操作之后，不然可能引起“死锁”。
2. 正确的思考方式：

2.4.5.6 吸烟者问题（同步问题）

抽烟者问题是一个“定向唤醒的条件同步问题”，其中生产者只负责触发条件，消费者根据条件被唯一唤醒执行，不存在共享缓冲区和资源竞争。

问题描述： 假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）

如何实现：

2.4.5.7 读者-写者问题（同步互斥问题（偏互斥））

问题描述与分析： 如何实现（读者优先）： 如何实现（写者优先）：

2.4.5.8 哲学家进餐问题（解决死锁问题）

哲学家进餐问题的关键在于 解决进程死锁，因为每个进程需同时持有两个临界资源（这也是和前面的问题不同的点，每个问题都具有代表性），因此存在这个隐患。

问题描述： 一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

解决问题： 关于哲学家进餐的死锁问题，存在 三种解决方案，如下图所示：

2.4.6 管程

若写程序的时候频繁使用 PV 操作，会导致代码难懂，极其容易出错，于是提出了 管程的概念，如下图所示： 通过看 管程大概的样子，来更加熟悉管程长什么样子：

2.4.7 死锁

2.4.7.1 死锁的基本概念

死锁是指多个进程因竞争资源而陷入相互等待的僵局，每个进程都在等待其他进程所占有的资源，而这些资源又不会被释放，从而形成一个 循环等待链，结果，所有涉及的进程都被永久阻塞，若无外界干预，他们讲无法继续推进。

死锁的产生需要 同时满足以下四个条件：

在以下情况下可能会发生死锁：

1. 对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU）的竞争是不会引起死锁的。
2. 进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程 P1、P2 分别申请并占有了资源 R1、R2，之后进程 P1 又紧接着申请资源 R2，而进程 P2 又申请资源 R1，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
3. 信号量的使用不当也会造成死锁。如生产者 - 消费者问题中，如果实现互斥的 P 操作在实现同步的 P 操作之前，就有可能导致死锁。（可以把互斥信号量、同步信号量也看做是一种抽象的系统资源）

总之，对不可剥夺资源的不合理分配，可能导致死锁。

可能还需要注意下 死锁、饥饿、死循环 的区别：

2.4.7.2 死锁处理策略–预防死锁

预防死锁的核心思想是通过设置严格的限制条件 破坏四个条件中的一个或者多个。

破坏互斥条件： 破坏不可剥夺条件： 破坏请求和保持条件： 破坏循环等待条件：

2.4.7.3 死锁处理策略–避免死锁

避免死锁的核心思想是在资源动态分配的过程中，通过特定算法判断分配后的系统是不是仍然处于安全状态，仅当安全时才允许分配，从而避免进入可能导致死锁的不安全状态。

银行家算法 就是最著名的死锁避免算法，其基本思想如图所示： 那在 实际手工操作 中，我们可以这样来 加快速度，不用像上面那样算： 银行家算法的 系统实现流程 如下图所示：

2.4.7.4 死锁处理策略–检测及解除死锁

本小节思维导图如下图所示： 死锁的检测 如下图所示： 资源分配图的化简，就是不断寻找“能够完成”的进程，然后假装它运行结束并释放资源。 死锁的解除 如下图所示：

附言

牛啊，一共五章，第二章占一半。