如何优雅的在java中统计代码块耗时

在我们的实际开发中，多多少少会遇到统计一段代码片段的耗时的情况，我们一般的写法如下

1
2
3
4
5
6

复制代码long start = System.currentTimeMillis();
try {
    // .... 具体的代码段
} finally {
    System.out.println("cost: " + (System.currentTimeMillis() - start));
}

上面的写法没有什么毛病，但是看起来就不太美观了，那么有没有什么更优雅的写法呢？

1. 代理方式

了解 Spring AOP 的同学可能立马会想到一个解决方法，如果想要统计某个方法耗时，使用切面可以无侵入的实现，如

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

复制代码// 定义切点，拦截所有满足条件的方法
@Pointcut("execution(public * com.git.hui.boot.aop.demo.*.*(*))")
public void point() {
}

@Around("point()")
public Object doAround(ProceedingJoinPoint joinPoint) throws Throwable {
    long start = System.currentTimeMillis();
    try{
        return joinPoint.proceed();
    } finally {
        System.out.println("cost: " + (System.currentTimeMillis() - start));
    }
}

Spring AOP 的底层支持原理为代理模式，为目标对象提供增强功能；在 Spring 的生态体系下，使用 aop 的方式来统计方法耗时，可以说少侵入且实现简单，但是有以下几个问题

• 统计粒度为方法级别
• 类内部方法调用无法生效（详情可以参考博文：【SpringBoot 基础系列教程】AOP 之高级使用技能）

2. AutoCloseable

在 JDK1.7 引入了一个新的接口AutoCloseable, 通常它的实现类配合try{}使用，可在 IO 流的使用上，经常可以看到下面这种写法

1
2
3
4
5
6
7

复制代码// 读取文件内容并输出
try (Reader stream = new BufferedReader(new InputStreamReader(new FileInputStream("/tmp")))) {
    List<String> list = ((BufferedReader) stream).lines().collect(Collectors.toList());
    System.out.println(list);
} catch (IOException e) {
    e.printStackTrace();
}

注意上面的写法中，最值得关注一点是，不需要再主动的写stream.close了，主要原因就是在try(){}执行完毕之后，会调用方法AutoCloseable#close方法；

基于此，我们就会有一个大单的想法，下一个Cost类实现AutoCloseable接口，创建时记录一个时间，close 方法中记录一个时间，并输出时间差值；将需要统计耗时的逻辑放入try(){}代码块

下面是一个具体的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

复制代码public static class Cost implements AutoCloseable {
    private long start;

    public Cost() {
        this.start = System.currentTimeMillis();
    }

    @Override
    public void close() {
        System.out.println("cost: " + (System.currentTimeMillis() - start));
    }
}

public static void testPrint() {
    for (int i = 0; i < 5; i++) {
        System.out.println("now " + i);
        try {
            Thread.sleep(10);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

public static void main(String[] args) {
    try (Cost c = new Cost()) {
        testPrint();
    }
    System.out.println("------over-------");
}

执行后输出如下:

1
2
3
4
5
6
7

复制代码now 0
now 1
now 2
now 3
now 4
cost: 55
------over-------

如果代码块抛异常，也会正常输出耗时么？

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

复制代码public static void testPrint() {
    for (int i = 0; i < 5; i++) {
        System.out.println("now " + i);
        try {
            Thread.sleep(10);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        if (i == 3) {
            throw new RuntimeException("some exception!");
        }
    }
}

再次输出如下，并没有问题

1
2
3
4
5
6
7
8

复制代码now 0
now 1
now 2
now 3
cost: 46
Exception in thread "main" java.lang.RuntimeException: some exception!
	at com.git.hui.boot.order.Application.testPrint(Application.java:43)
	at com.git.hui.boot.order.Application.main(Application.java:50)

3. 小结

除了上面介绍的两种方式，还有一种在业务开发中不太常见，但是在中间件、偏基础服务的功能组件中可以看到，利用 Java Agent 探针技术来实现，比如阿里的 arthas 就是在 JavaAgent 的基础上做了各种上天的功能，后续介绍 java 探针技术时会专门介绍

下面小结一下三种统计耗时的方式

基本写法

1
2
3
4
5
6

复制代码long start = System.currentTimeMillis();
try {
    // .... 具体的代码段
} finally {
    System.out.println("cost: " + (System.currentTimeMillis() - start));
}

优点是简单，适用范围广泛；缺点是侵入性强，大量的重复代码

Spring AOP

在 Spring 生态下，可以借助 AOP 来拦截目标方法，统计耗时

1
2
3
4
5
6
7
8
9

复制代码@Around("...")
public Object doAround(ProceedingJoinPoint joinPoint) throws Throwable {
    long start = System.currentTimeMillis();
    try{
        return joinPoint.proceed();
    } finally {
        System.out.println("cost: " + (System.currentTimeMillis() - start));
    }
}

优点：无侵入，适合统一管理（比如测试环境输出统计耗时，生产环境不输出）；缺点是适用范围小，且粒度为方法级别，并受限于 AOP 的使用范围

AutoCloseable

这种方式可以看做是第一种写法的进阶版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复制代码// 定义类
public static class Cost implements AutoCloseable {
    private long start;

    public Cost() {
        this.start = System.currentTimeMillis();
    }

    @Override
    public void close() {
        System.out.println("cost: " + (System.currentTimeMillis() - start));
    }
}

// 使用姿势
try (Cost c = new Cost()) {
    ...
}

优点是：简单，适用范围广泛，且适合统一管理；缺点是依然有代码侵入

说明

上面第二种方法看着属于最优雅的方式，但是限制性强；如果有更灵活的需求，建议考虑第三种写法，在代码的简洁性和统一管理上都要优雅很多，相比较第一种可以减少大量冗余代码

II. 其他

1. 一灰灰 Blog： liuyueyi.github.io/hexblog

一灰灰的个人博客，记录所有学习和工作中的博文，欢迎大家前去逛逛

2. 声明

尽信书则不如，已上内容，纯属一家之言，因个人能力有限，难免有疏漏和错误之处，如发现 bug 或者有更好的建议，欢迎批评指正，不吝感激

• 微博地址: 小灰灰 Blog
• QQ： 一灰灰/3302797840

3. 扫描关注

一灰灰 blog

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

我们平常说的进程和线程更多的是基于编程语言的角度来说的，那么你真的了解什么是线程和进程吗？那么我们就从操作系统的角度来了解一下什么是进程和线程。

进程

操作系统中最核心的概念就是 进程，进程是对正在运行中的程序的一个抽象。操作系统的其他所有内容都是围绕着进程展开的。进程是操作系统提供的最古老也是最重要的概念之一。即使可以使用的 CPU 只有一个，它们也支持（伪）并发操作。它们会将一个单独的 CPU 抽象为多个虚拟机的 CPU。可以说：没有进程的抽象，现代操作系统将不复存在。

所有现代的计算机会在同一时刻做很多事情，过去使用计算机的人（单 CPU）可能完全无法理解现在这种变化，举个例子更能说明这一点：首先考虑一个 Web 服务器，请求都来自于 Web 网页。当一个请求到达时，服务器会检查当前页是否在缓存中，如果是在缓存中，就直接把缓存中的内容返回。如果缓存中没有的话，那么请求就会交给磁盘来处理。但是，从 CPU 的角度来看，磁盘请求需要更长的时间，因为磁盘请求会很慢。当硬盘请求完成时，更多其他请求才会进入。如果有多个磁盘的话，可以在第一个请求完成前就可以连续的对其他磁盘发出部分或全部请求。很显然，这是一种并发现象，需要有并发控制条件来控制并发现象。

现在考虑只有一个用户的 PC。当系统启动时，许多进程也在后台启动，用户通常不知道这些进程的启动，试想一下，当你自己的计算机启动的时候，你能知道哪些进程是需要启动的么？这些后台进程可能是一个需要输入电子邮件的电子邮件进程，或者是一个计算机病毒查杀进程来周期性的更新病毒库。某个用户进程可能会在所有用户上网的时候打印文件以及刻录 CD-ROM，这些活动都需要管理。于是一个支持多进程的多道程序系统就会显得很有必要了。

在许多多道程序系统中，CPU 会在进程间快速切换，使每个程序运行几十或者几百毫秒。然而，严格意义来说，在某一个瞬间，CPU 只能运行一个进程，然而我们如果把时间定位为 1 秒内的话，它可能运行多个进程。这样就会让我们产生并行的错觉。有时候人们说的 伪并行(pseudoparallelism) 就是这种情况，以此来区分多处理器系统(该系统由两个或多个 CPU 来共享同一个物理内存)

再来详细解释一下伪并行：伪并行是指单核或多核处理器同时执行多个进程，从而使程序更快。 通过以非常有限的时间间隔在程序之间快速切换CPU，因此会产生并行感。 缺点是 CPU 时间可能分配给下一个进程，也可能不分配给下一个进程。

因为 CPU 执行速度很快，进程间的换进换出也非常迅速，因此我们很难对多个并行进程进行跟踪，所以，在经过多年的努力后，操作系统的设计者开发了用于描述并行的一种概念模型（顺序进程），使得并行更加容易理解和分析，对该模型的探讨，也是本篇文章的主题。下面我们就来探讨一下进程模型

进程模型

在进程模型中，所有计算机上运行的软件，通常也包括操作系统，被组织为若干顺序进程(sequential processes)，简称为 进程(process) 。一个进程就是一个正在执行的程序的实例，进程也包括程序计数器、寄存器和变量的当前值。从概念上来说，每个进程都有各自的虚拟 CPU，但是实际情况是 CPU 会在各个进程之间进行来回切换。

如上图所示，这是一个具有 4 个程序的多道处理程序，在进程不断切换的过程中，程序计数器也在不同的变化。

在上图中，这 4 道程序被抽象为 4 个拥有各自控制流程（即每个自己的程序计数器）的进程，并且每个程序都独立的运行。当然，实际上只有一个物理程序计数器，每个程序要运行时，其逻辑程序计数器会装载到物理程序计数器中。当程序运行结束后，其物理程序计数器就会是真正的程序计数器，然后再把它放回进程的逻辑计数器中。

从下图我们可以看到，在观察足够长的一段时间后，所有的进程都运行了，但在任何一个给定的瞬间仅有一个进程真正运行。

因此，当我们说一个 CPU 只能真正一次运行一个进程的时候，即使有 2 个核（或 CPU），每一个核也只能一次运行一个线程。

由于 CPU 会在各个进程之间来回快速切换，所以每个进程在 CPU 中的运行时间是无法确定的。并且当同一个进程再次在 CPU 中运行时，其在 CPU 内部的运行时间往往也是不固定的。进程和程序之间的区别是非常微妙的，但是通过一个例子可以让你加以区分：想想一位会做饭的计算机科学家正在为他的女儿制作生日蛋糕。他有做生日蛋糕的食谱，厨房里有所需的原谅：面粉、鸡蛋、糖、香草汁等。在这个比喻中，做蛋糕的食谱就是程序、计算机科学家就是 CPU、而做蛋糕的各种原谅都是输入数据。进程就是科学家阅读食谱、取来各种原料以及烘焙蛋糕等一系例了动作的总和。

现在假设科学家的儿子跑过来告诉他，说他的头被蜜蜂蜇了一下，那么此时科学家会记录出来他做蛋糕这个过程到了哪一步，然后拿出急救手册，按照上面的步骤给他儿子实施救助。这里，会涉及到进程之间的切换，科学家（CPU）会从做蛋糕（进程）切换到实施医疗救助（另一个进程）。等待伤口处理完毕后，科学家会回到刚刚记录做蛋糕的那一步，继续制作。

这里的关键思想是认识到一个进程所需的条件，进程是某一类特定活动的总和，它有程序、输入输出以及状态。单个处理器可以被若干进程共享，它使用某种调度算法决定何时停止一个进程的工作，并转而为另外一个进程提供服务。另外需要注意的是，如果一个进程运行了两遍，则被认为是两个进程。那么我们了解到进程模型后，那么进程是如何创建的呢？

进程的创建

操作系统需要一些方式来创建进程。下面是一些创建进程的方式

• 系统初始化（init）
• 正在运行的程序执行了创建进程的系统调用（比如 fork）
• 用户请求创建一个新进程
• 初始化一个批处理工作

系统初始化

启动操作系统时，通常会创建若干个进程。其中有些是前台进程(numerous processes)，也就是同用户进行交互并替他们完成工作的进程。一些运行在后台，并不与特定的用户进行交互，例如，设计一个进程来接收发来的电子邮件，这个进程大部分的时间都在休眠，但是只要邮件到来后这个进程就会被唤醒。还可以设计一个进程来接收对该计算机上网页的传入请求，在请求到达的进程唤醒来处理网页的传入请求。进程运行在后台用来处理一些活动像是 e-mail，web 网页，新闻，打印等等被称为 守护进程(daemons)。大型系统会有很多守护进程。在 UNIX 中，ps 程序可以列出正在运行的进程， 在 Windows 中，可以使用任务管理器。

系统调用创建

除了在启动阶段创建进程之外，一些新的进程也可以在后面创建。通常，一个正在运行的进程会发出系统调用用来创建一个或多个新进程来帮助其完成工作。例如，如果有大量的数据需要经过网络调取并进行顺序处理，那么创建一个进程读数据，并把数据放到共享缓冲区中，而让第二个进程取走并正确处理会比较容易些。在多处理器中，让每个进程运行在不同的 CPU 上也可以使工作做的更快。

用户请求创建

在许多交互式系统中，输入一个命令或者双击图标就可以启动程序，以上任意一种操作都可以选择开启一个新的进程，在基本的 UNIX 系统中运行 X，新进程将接管启动它的窗口。在 Windows 中启动进程时，它一般没有窗口，但是它可以创建一个或多个窗口。每个窗口都可以运行进程。通过鼠标或者命令就可以切换窗口并与进程进行交互。

交互式系统是以人与计算机之间大量交互为特征的计算机系统，比如游戏、web浏览器，IDE 等集成开发环境。

批处理创建

最后一种创建进程的情形会在大型机的批处理系统中应用。用户在这种系统中提交批处理作业。当操作系统决定它有资源来运行另一个任务时，它将创建一个新进程并从其中的输入队列中运行下一个作业。

从技术上讲，在所有这些情况下，让现有流程执行流程是通过创建系统调用来创建新流程的。该进程可能是正在运行的用户进程，是从键盘或鼠标调用的系统进程或批处理程序。这些就是系统调用创建新进程的过程。该系统调用告诉操作系统创建一个新进程，并直接或间接指示在其中运行哪个程序。

在 UNIX 中，仅有一个系统调用来创建一个新的进程，这个系统调用就是 fork。这个调用会创建一个与调用进程相关的副本。在 fork 后，一个父进程和子进程会有相同的内存映像，相同的环境字符串和相同的打开文件。通常，子进程会执行 execve 或者一个简单的系统调用来改变内存映像并运行一个新的程序。例如，当一个用户在 shell 中输出 sort 命令时，shell 会 fork 一个子进程然后子进程去执行 sort 命令。这两步过程的原因是允许子进程在 fork 之后但在 execve 之前操作其文件描述符，以完成标准输入，标准输出和标准错误的重定向。

在 Windows 中，情况正相反，一个简单的 Win32 功能调用 CreateProcess，会处理流程创建并将正确的程序加载到新的进程中。这个调用会有 10 个参数，包括了需要执行的程序、输入给程序的命令行参数、各种安全属性、有关打开的文件是否继承控制位、优先级信息、进程所需要创建的窗口规格以及指向一个结构的指针，在该结构中新创建进程的信息被返回给调用者。除了 CreateProcess Win 32 中大概有 100 个其他的函数用于处理进程的管理，同步以及相关的事务。下面是 UNIX 操作系统和 Windows 操作系统系统调用的对比

在 UNIX 和 Windows 中，进程创建之后，父进程和子进程有各自不同的地址空间。如果其中某个进程在其地址空间中修改了一个词，这个修改将对另一个进程不可见。在 UNIX 中，子进程的地址空间是父进程的一个拷贝，但是确是两个不同的地址空间；不可写的内存区域是共享的。某些 UNIX 实现是正是在两者之间共享，因为它不能被修改。或者，子进程共享父进程的所有内存，但是这种情况下内存通过 写时复制(copy-on-write) 共享，这意味着一旦两者之一想要修改部分内存，则这块内存首先被明确的复制，以确保修改发生在私有内存区域。再次强调，可写的内存是不能被共享的。但是，对于一个新创建的进程来说，确实有可能共享创建者的资源，比如可以共享打开的文件。在 Windows 中，从一开始父进程的地址空间和子进程的地址空间就是不同的。

进程的终止

进程在创建之后，它就开始运行并做完成任务。然而，没有什么事儿是永不停歇的，包括进程也一样。进程早晚会发生终止，但是通常是由于以下情况触发的

• 正常退出(自愿的)
• 错误退出(自愿的)
• 严重错误(非自愿的)
• 被其他进程杀死(非自愿的)

正常退出

多数进程是由于完成了工作而终止。当编译器完成了所给定程序的编译之后，编译器会执行一个系统调用告诉操作系统它完成了工作。这个调用在 UNIX 中是 exit ，在 Windows 中是 ExitProcess。面向屏幕中的软件也支持自愿终止操作。字处理软件、Internet 浏览器和类似的程序中总有一个供用户点击的图标或菜单项，用来通知进程删除它锁打开的任何临时文件，然后终止。

错误退出

进程发生终止的第二个原因是发现严重错误，例如，如果用户执行如下命令

1

复制代码cc foo.c

为了能够编译 foo.c 但是该文件不存在，于是编译器就会发出声明并退出。在给出了错误参数时，面向屏幕的交互式进程通常并不会直接退出，因为这从用户的角度来说并不合理，用户需要知道发生了什么并想要进行重试，所以这时候应用程序通常会弹出一个对话框告知用户发生了系统错误，是需要重试还是退出。

严重错误

进程终止的第三个原因是由进程引起的错误，通常是由于程序中的错误所导致的。例如，执行了一条非法指令，引用不存在的内存，或者除数是 0 等。在有些系统比如 UNIX 中，进程可以通知操作系统，它希望自行处理某种类型的错误，在这类错误中，进程会收到信号（中断），而不是在这类错误出现时直接终止进程。

被其他进程杀死

第四个终止进程的原因是，某个进程执行系统调用告诉操作系统杀死某个进程。在 UNIX 中，这个系统调用是 kill。在 Win32 中对应的函数是 TerminateProcess（注意不是系统调用）。

进程的层次结构

在一些系统中，当一个进程创建了其他进程后，父进程和子进程就会以某种方式进行关联。子进程它自己就会创建更多进程，从而形成一个进程层次结构。

UNIX 进程体系

在 UNIX 中，进程和它的所有子进程以及子进程的子进程共同组成一个进程组。当用户从键盘中发出一个信号后，该信号被发送给当前与键盘相关的进程组中的所有成员（它们通常是在当前窗口创建的所有活动进程）。每个进程可以分别捕获该信号、忽略该信号或采取默认的动作，即被信号 kill 掉。

这里有另一个例子，可以用来说明层次的作用，考虑 UNIX 在启动时如何初始化自己。一个称为 init 的特殊进程出现在启动映像中 。当 init 进程开始运行时，它会读取一个文件，文件会告诉它有多少个终端。然后为每个终端创建一个新进程。这些进程等待用户登录。如果登录成功，该登录进程就执行一个 shell 来等待接收用户输入指令，这些命令可能会启动更多的进程，以此类推。因此，整个操作系统中所有的进程都隶属于一个单个以 init 为根的进程树。

Windows 进程体系

相反，Windows 中没有进程层次的概念，Windows 中所有进程都是平等的，唯一类似于层次结构的是在创建进程的时候，父进程得到一个特别的令牌（称为句柄），该句柄可以用来控制子进程。然而，这个令牌可能也会移交给别的操作系统，这样就不存在层次结构了。而在 UNIX 中，进程不能剥夺其子进程的 进程权。（这样看来，还是 Windows 比较渣）。

进程状态

尽管每个进程是一个独立的实体，有其自己的程序计数器和内部状态，但是，进程之间仍然需要相互帮助。例如，一个进程的结果可以作为另一个进程的输入，在 shell 命令中

1

复制代码cat chapter1 chapter2 chapter3 | grep tree

第一个进程是 cat，将三个文件级联并输出。第二个进程是 grep，它从输入中选择具有包含关键字 tree 的内容，根据这两个进程的相对速度（这取决于两个程序的相对复杂度和各自所分配到的 CPU 时间片），可能会发生下面这种情况，grep 准备就绪开始运行，但是输入进程还没有完成，于是必须阻塞 grep 进程，直到输入完毕。

当一个进程开始运行时，它可能会经历下面这几种状态

图中会涉及三种状态

1. 运行态，运行态指的就是进程实际占用 CPU 时间片运行时
2. 就绪态，就绪态指的是可运行，但因为其他进程正在运行而处于就绪状态
3. 阻塞态，除非某种外部事件发生，否则进程不能运行

逻辑上来说，运行态和就绪态是很相似的。这两种情况下都表示进程可运行，但是第二种情况没有获得 CPU 时间分片。第三种状态与前两种状态不同的原因是这个进程不能运行，CPU 空闲时也不能运行。

三种状态会涉及四种状态间的切换，在操作系统发现进程不能继续执行时会发生状态1的轮转，在某些系统中进程执行系统调用，例如 pause，来获取一个阻塞的状态。在其他系统中包括 UNIX，当进程从管道或特殊文件（例如终端）中读取没有可用的输入时，该进程会被自动终止。

转换 2 和转换 3 都是由进程调度程序（操作系统的一部分）引起的，进程本身不知道调度程序的存在。转换 2 的出现说明进程调度器认定当前进程已经运行了足够长的时间，是时候让其他进程运行 CPU 时间片了。当所有其他进程都运行过后，这时候该是让第一个进程重新获得 CPU 时间片的时候了，就会发生转换 3。

程序调度指的是，决定哪个进程优先被运行和运行多久，这是很重要的一点。已经设计出许多算法来尝试平衡系统整体效率与各个流程之间的竞争需求。

当进程等待的一个外部事件发生时（如从外部输入一些数据后），则发生转换 4。如果此时没有其他进程在运行，则立刻触发转换 3，该进程便开始运行，否则该进程会处于就绪阶段，等待 CPU 空闲后再轮到它运行。

从上面的观点引入了下面的模型

操作系统最底层的就是调度程序，在它上面有许多进程。所有关于中断处理、启动进程和停止进程的具体细节都隐藏在调度程序中。事实上，调度程序只是一段非常小的程序。

进程的实现

操作系统为了执行进程间的切换，会维护着一张表格，这张表就是 进程表(process table)。每个进程占用一个进程表项。该表项包含了进程状态的重要信息，包括程序计数器、堆栈指针、内存分配状况、所打开文件的状态、账号和调度信息，以及其他在进程由运行态转换到就绪态或阻塞态时所必须保存的信息，从而保证该进程随后能再次启动，就像从未被中断过一样。

下面展示了一个典型系统中的关键字段

第一列内容与进程管理有关，第二列内容与 存储管理有关，第三列内容与文件管理有关。

存储管理的 text segment 、 data segment、stack segment 更多了解见下面这篇文章

程序员需要了解的硬核知识之汇编语言(全)

现在我们应该对进程表有个大致的了解了，就可以在对单个 CPU 上如何运行多个顺序进程的错觉做更多的解释。与每一 I/O 类相关联的是一个称作 中断向量(interrupt vector) 的位置（靠近内存底部的固定区域）。它包含中断服务程序的入口地址。假设当一个磁盘中断发生时，用户进程 3 正在运行，则中断硬件将程序计数器、程序状态字、有时还有一个或多个寄存器压入堆栈，计算机随即跳转到中断向量所指示的地址。这就是硬件所做的事情。然后软件就随即接管一切剩余的工作。

当中断结束后，操作系统会调用一个 C 程序来处理中断剩下的工作。在完成剩下的工作后，会使某些进程就绪，接着调用调度程序，决定随后运行哪个进程。然后将控制权转移给一段汇编语言代码，为当前的进程装入寄存器值以及内存映射并启动该进程运行，下面显示了中断处理和调度的过程。

1. 硬件压入堆栈程序计数器等
2. 硬件从中断向量装入新的程序计数器
3. 汇编语言过程保存寄存器的值
4. 汇编语言过程设置新的堆栈
5. C 中断服务器运行（典型的读和缓存写入）
6. 调度器决定下面哪个程序先运行
7. C 过程返回至汇编代码
8. 汇编语言过程开始运行新的当前进程

一个进程在执行过程中可能被中断数千次，但关键每次中断后，被中断的进程都返回到与中断发生前完全相同的状态。

线程

在传统的操作系统中，每个进程都有一个地址空间和一个控制线程。事实上，这是大部分进程的定义。不过，在许多情况下，经常存在同一地址空间中运行多个控制线程的情形，这些线程就像是分离的进程。下面我们就着重探讨一下什么是线程

线程的使用

或许这个疑问也是你的疑问，为什么要在进程的基础上再创建一个线程的概念，准确的说，这其实是进程模型和线程模型的讨论，回答这个问题，可能需要分三步来回答

• 多线程之间会共享同一块地址空间和所有可用数据的能力，这是进程所不具备的
• 线程要比进程更轻量级，由于线程更轻，所以它比进程更容易创建，也更容易撤销。在许多系统中，创建一个线程要比创建一个进程快 10 - 100 倍。
• 第三个原因可能是性能方面的探讨，如果多个线程都是 CPU 密集型的，那么并不能获得性能上的增强，但是如果存在着大量的计算和大量的 I/O 处理，拥有多个线程能在这些活动中彼此重叠进行，从而会加快应用程序的执行速度

多线程解决方案

现在考虑一个线程使用的例子：一个万维网服务器，对页面的请求发送给服务器，而所请求的页面发送回客户端。在多数 web 站点上，某些页面较其他页面相比有更多的访问。例如，索尼的主页比任何一个照相机详情介绍页面具有更多的访问，Web 服务器可以把获得大量访问的页面集合保存在内存中，避免到磁盘去调入这些页面，从而改善性能。这种页面的集合称为 高速缓存(cache)，高速缓存也应用在许多场合中，比如说 CPU 缓存。

上面是一个 web 服务器的组织方式，一个叫做 调度线程(dispatcher thread) 的线程从网络中读入工作请求，在调度线程检查完请求后，它会选择一个空闲的（阻塞的）工作线程来处理请求，通常是将消息的指针写入到每个线程关联的特殊字中。然后调度线程会唤醒正在睡眠中的工作线程，把工作线程的状态从阻塞态变为就绪态。

当工作线程启动后，它会检查请求是否在 web 页面的高速缓存中存在，这个高速缓存是所有线程都可以访问的。如果高速缓存不存在这个 web 页面的话，它会调用一个 read 操作从磁盘中获取页面并且阻塞线程直到磁盘操作完成。当线程阻塞在硬盘操作的期间，为了完成更多的工作，调度线程可能挑选另一个线程运行，也可能把另一个当前就绪的工作线程投入运行。

这种模型允许将服务器编写为顺序线程的集合，在分派线程的程序中包含一个死循环，该循环用来获得工作请求并且把请求派给工作线程。每个工作线程的代码包含一个从调度线程接收的请求，并且检查 web 高速缓存中是否存在所需页面，如果有，直接把该页面返回给客户，接着工作线程阻塞，等待一个新请求的到达。如果没有，工作线程就从磁盘调入该页面，将该页面返回给客户机，然后工作线程阻塞，等待一个新请求。

下面是调度线程和工作线程的代码，这里假设 TRUE 为常数 1 ，buf 和 page 分别是保存工作请求和 Web 页面的相应结构。

调度线程的大致逻辑

1
2
3
4

复制代码while(TRUE){
  get_next_request(&buf);
  handoff_work(&buf);
}

工作线程的大致逻辑

1
2
3
4
5
6
7
8

复制代码while(TRUE){
  wait_for_work(&buf);
  look_for_page_in_cache(&buf,&page);
  if(page_not_in_cache(&page)){
    read_page_from_disk(&buf,&page);
  }
  return _page(&page);
}

单线程解决方案

现在考虑没有多线程的情况下，如何编写 Web 服务器。我们很容易的就想象为单个线程了，Web 服务器的主循环获取请求并检查请求，并争取在下一个请求之前完成工作。在等待磁盘操作时，服务器空转，并且不处理任何到来的其他请求。结果会导致每秒中只有很少的请求被处理，所以这个例子能够说明多线程提高了程序的并行性并提高了程序的性能。

状态机解决方案

到现在为止，我们已经有了两种解决方案，单线程解决方案和多线程解决方案，其实还有一种解决方案就是 状态机解决方案，它的流程如下

如果目前只有一个非阻塞版本的 read 系统调用可以使用，那么当请求到达服务器时，这个唯一的 read 调用的线程会进行检查，如果能够从高速缓存中得到响应，那么直接返回，如果不能，则启动一个非阻塞的磁盘操作

服务器在表中记录当前请求的状态，然后进入并获取下一个事件，紧接着下一个事件可能就是一个新工作的请求或是磁盘对先前操作的回答。如果是新工作的请求，那么就开始处理请求。如果是磁盘的响应，就从表中取出对应的状态信息进行处理。对于非阻塞式磁盘 I/O 而言，这种响应一般都是信号中断响应。

每次服务器从某个请求工作的状态切换到另一个状态时，都必须显示的保存或者重新装入相应的计算状态。这里，每个计算都有一个被保存的状态，存在一个会发生且使得相关状态发生改变的事件集合，我们把这类设计称为有限状态机(finite-state machine)，有限状态机杯广泛的应用在计算机科学中。

这三种解决方案各有各的特性，多线程使得顺序进程的思想得以保留下来，并且实现了并行性，但是顺序进程会阻塞系统调用；单线程服务器保留了阻塞系统的简易性，但是却放弃了性能。有限状态机的处理方法运用了非阻塞调用和中断，通过并行实现了高性能，但是给编程增加了困难。

经典的线程模型

理解进程的另一个角度是，用某种方法把相关的资源集中在一起。进程有存放程序正文和数据以及其他资源的地址空间。这些资源包括打开的文件、子进程、即将发生的定时器、信号处理程序、账号信息等。把这些信息放在进程中会比较容易管理。

另一个概念是，进程中拥有一个执行的线程，通常简写为 线程(thread)。线程会有程序计数器，用来记录接着要执行哪一条指令；线程还拥有寄存器，用来保存线程当前正在使用的变量；线程还会有堆栈，用来记录程序的执行路径。尽管线程必须在某个进程中执行，但是进程和线程完完全全是两个不同的概念，并且他们可以分开处理。进程用于把资源集中在一起，而线程则是 CPU 上调度执行的实体。

线程给进程模型增加了一项内容，即在同一个进程中，允许彼此之间有较大的独立性且互不干扰。在一个进程中并行运行多个线程类似于在一台计算机上运行多个进程。在多个线程中，各个线程共享同一地址空间和其他资源。在多个进程中，进程共享物理内存、磁盘、打印机和其他资源。因为线程会包含有一些进程的属性，所以线程被称为轻量的进程(lightweight processes)。多线程(multithreading)一词还用于描述在同一进程中多个线程的情况。

下图我们可以看到三个传统的进程，每个进程有自己的地址空间和单个控制线程。每个线程都在不同的地址空间中运行

下图中，我们可以看到有一个进程三个线程的情况。每个线程都在相同的地址空间中运行。

线程不像是进程那样具备较强的独立性。同一个进程中的所有线程都会有完全一样的地址空间，这意味着它们也共享同样的全局变量。由于每个线程都可以访问进程地址空间内每个内存地址，因此一个线程可以读取、写入甚至擦除另一个线程的堆栈。线程之间除了共享同一内存空间外，还具有如下不同的内容

上图左边的是同一个进程中每个线程共享的内容，上图右边是每个线程中的内容。也就是说左边的列表是进程的属性，右边的列表是线程的属性。

和进程一样，线程可以处于下面这几种状态：运行中、阻塞、就绪和终止（进程图中没有画）。正在运行的线程拥有 CPU 时间片并且状态是运行中。一个被阻塞的线程会等待某个释放它的事件。例如，当一个线程执行从键盘读入数据的系统调用时，该线程就被阻塞直到有输入为止。线程通常会被阻塞，直到它等待某个外部事件的发生或者有其他线程来释放它。线程之间的状态转换和进程之间的状态转换是一样的。

每个线程都会有自己的堆栈，如下图所示

线程系统调用

进程通常会从当前的某个单线程开始，然后这个线程通过调用一个库函数（比如 thread_create）创建新的线程。线程创建的函数会要求指定新创建线程的名称。创建的线程通常都返回一个线程标识符，该标识符就是新线程的名字。

当一个线程完成工作后，可以通过调用一个函数（比如 thread_exit）来退出。紧接着线程消失，状态变为终止，不能再进行调度。在某些线程的运行过程中，可以通过调用函数例如 thread_join ，表示一个线程可以等待另一个线程退出。这个过程阻塞调用线程直到等待特定的线程退出。在这种情况下，线程的创建和终止非常类似于进程的创建和终止。

另一个常见的线程是调用 thread_yield，它允许线程自动放弃 CPU 从而让另一个线程运行。这样一个调用还是很重要的，因为不同于进程，线程是无法利用时钟中断强制让线程让出 CPU 的。

POSIX 线程

为了使编写可移植线程程序成为可能，IEEE 在 IEEE 标准 1003.1c 中定义了线程标准。线程包被定义为 Pthreads。大部分的 UNIX 系统支持它。这个标准定义了 60 多种功能调用，一一列举不太现实，下面为你列举了一些常用的系统调用。

POSIX线程（通常称为pthreads）是一种独立于语言而存在的执行模型，以及并行执行模型。它允许程序控制时间上重叠的多个不同的工作流程。每个工作流程都称为一个线程，可以通过调用POSIX Threads API来实现对这些流程的创建和控制。可以把它理解为线程的标准。

POSIX Threads 的实现在许多类似且符合POSIX的操作系统上可用，例如 FreeBSD、NetBSD、OpenBSD、Linux、macOS、Android、Solaris，它在现有 Windows API 之上实现了pthread。

IEEE 是世界上最大的技术专业组织，致力于为人类的利益而发展技术。

所有的 Pthreads 都有特定的属性，每一个都含有标识符、一组寄存器（包括程序计数器）和一组存储在结构中的属性。这个属性包括堆栈大小、调度参数以及其他线程需要的项目。

新的线程会通过 pthread_create 创建，新创建的线程的标识符会作为函数值返回。这个调用非常像是 UNIX 中的 fork 系统调用（除了参数之外），其中线程标识符起着 PID 的作用，这么做的目的是为了和其他线程进行区分。

当线程完成指派给他的工作后，会通过 pthread_exit 来终止。这个调用会停止线程并释放堆栈。

一般一个线程在继续运行前需要等待另一个线程完成它的工作并退出。可以通过 pthread_join 线程调用来等待别的特定线程的终止。而要等待线程的线程标识符作为一个参数给出。

有时会出现这种情况：一个线程逻辑上没有阻塞，但感觉上它已经运行了足够长的时间并且希望给另外一个线程机会去运行。这时候可以通过 pthread_yield 来完成。

下面两个线程调用是处理属性的。pthread_attr_init 建立关联一个线程的属性结构并初始化成默认值，这些值（例如优先级）可以通过修改属性结构的值来改变。

最后，pthread_attr_destroy 删除一个线程的结构，释放它占用的内存。它不会影响调用它的线程，这些线程会一直存在。

为了更好的理解 pthread 是如何工作的，考虑下面这个例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

复制代码#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#define NUMBER_OF_THREADS 10

void *print_hello_world(vvoid *tid){
  /* 输出线程的标识符，然后退出 */
  printf("Hello World. Greetings from thread %d\n",tid);
  pthread_exit(NULL);
}

int main(int argc,char *argv[]){
  /* 主程序创建 10 个线程，然后退出 */
  pthread_t threads[NUMBER_OF_THREADS];
  int status,i;
 	
  for(int i = 0;i < NUMBER_OF_THREADS;i++){
    printf("Main here. Creating thread %d\n",i);
    status = pthread_create(&threads[i], NULL, print_hello_world, (void *)i);
    
    if(status != 0){
      printf("Oops. pthread_create returned error code %d\n",status);
      exit(-1);
    }
  }
  exit(NULL);
}

主线程在宣布它的指责之后，循环 NUMBER_OF_THREADS 次，每次创建一个新的线程。如果线程创建失败，会打印出一条信息后退出。在创建完成所有的工作后，主程序退出。

线程实现

主要有三种实现方式

• 在用户空间中实现线程；
• 在内核空间中实现线程；
• 在用户和内核空间中混合实现线程。

下面我们分开讨论一下

在用户空间中实现线程

第一种方法是把整个线程包放在用户空间中，内核对线程一无所知，它不知道线程的存在。所有的这类实现都有同样的通用结构

线程在运行时系统之上运行，运行时系统是管理线程过程的集合，包括前面提到的四个过程： pthread_create, pthread_exit, pthread_join 和 pthread_yield。

运行时系统(Runtime System) 也叫做运行时环境，该运行时系统提供了程序在其中运行的环境。此环境可能会解决许多问题，包括应用程序内存的布局，程序如何访问变量，在过程之间传递参数的机制，与操作系统的接口等等。编译器根据特定的运行时系统进行假设以生成正确的代码。通常，运行时系统将负责设置和管理堆栈，并且会包含诸如垃圾收集，线程或语言内置的其他动态的功能。

在用户空间管理线程时，每个进程需要有其专用的线程表(thread table)，用来跟踪该进程中的线程。这些表和内核中的进程表类似，不过它仅仅记录各个线程的属性，如每个线程的程序计数器、堆栈指针、寄存器和状态。该线程标由运行时系统统一管理。当一个线程转换到就绪状态或阻塞状态时，在该线程表中存放重新启动该线程的所有信息，与内核在进程表中存放的信息完全一样。

在用户空间实现线程的优势

在用户空间中实现线程要比在内核空间中实现线程具有这些方面的优势：考虑如果在线程完成时或者是在调用 pthread_yield 时，必要时会进程线程切换，然后线程的信息会被保存在运行时环境所提供的线程表中，然后，线程调度程序来选择另外一个需要运行的线程。保存线程的状态和调度程序都是本地过程，所以启动他们比进行内核调用效率更高。因而不需要切换到内核，也就不需要上下文切换，也不需要对内存高速缓存进行刷新，因为线程调度非常便捷，因此效率比较高。

在用户空间实现线程还有一个优势就是它允许每个进程有自己定制的调度算法。例如在某些应用程序中，那些具有垃圾收集线程的应用程序（知道是谁了吧）就不用担心自己线程会不会在不合适的时候停止，这是一个优势。用户线程还具有较好的可扩展性，因为内核空间中的内核线程需要一些表空间和堆栈空间，如果内核线程数量比较大，容易造成问题。

在用户空间实现线程的劣势

尽管在用户空间实现线程会具有一定的性能优势，但是劣势还是很明显的，你如何实现阻塞系统调用呢？假设在还没有任何键盘输入之前，一个线程读取键盘，让线程进行系统调用是不可能的，因为这会停止所有的线程。所以，使用线程的一个目标是能够让线程进行阻塞调用，并且要避免被阻塞的线程影响其他线程。

与阻塞调用类似的问题是缺页中断问题，实际上，计算机并不会把所有的程序都一次性的放入内存中，如果某个程序发生函数调用或者跳转指令到了一条不在内存的指令上，就会发生页面故障，而操作系统将到磁盘上取回这个丢失的指令，这就称为缺页故障。而在对所需的指令进行读入和执行时，相关的进程就会被阻塞。如果只有一个线程引起页面故障，内核由于甚至不知道有线程存在，通常会吧整个进程阻塞直到磁盘 I/O 完成为止，尽管其他的线程是可以运行的。

另外一个问题是，如果一个线程开始运行，该线程所在进程中的其他线程都不能运行，除非第一个线程自愿的放弃 CPU，在一个单进程内部，没有时钟中断，所以不可能使用轮转调度的方式调度线程。除非其他线程能够以自己的意愿进入运行时环境，否则调度程序没有可以调度线程的机会。

在内核中实现线程

现在我们考虑使用内核来实现线程的情况，此时不再需要运行时环境了。另外，每个进程中也没有线程表。相反，在内核中会有用来记录系统中所有线程的线程表。当某个线程希望创建一个新线程或撤销一个已有线程时，它会进行一个系统调用，这个系统调用通过对线程表的更新来完成线程创建或销毁工作。

内核中的线程表持有每个线程的寄存器、状态和其他信息。这些信息和用户空间中的线程信息相同，但是位置却被放在了内核中而不是用户空间中。另外，内核还维护了一张进程表用来跟踪系统状态。

所有能够阻塞的调用都会通过系统调用的方式来实现，当一个线程阻塞时，内核可以进行选择，是运行在同一个进程中的另一个线程（如果有就绪线程的话）还是运行一个另一个进程中的线程。但是在用户实现中，运行时系统始终运行自己的线程，直到内核剥夺它的 CPU 时间片（或者没有可运行的线程存在了）为止。

由于在内核中创建或者销毁线程的开销比较大，所以某些系统会采用可循环利用的方式来回收线程。当某个线程被销毁时，就把它标志为不可运行的状态，但是其内部结构没有受到影响。稍后，在必须创建一个新线程时，就会重新启用旧线程，把它标志为可用状态。

如果某个进程中的线程造成缺页故障后，内核很容易的就能检查出来是否有其他可运行的线程，如果有的话，在等待所需要的页面从磁盘读入时，就选择一个可运行的线程运行。这样做的缺点是系统调用的代价比较大，所以如果线程的操作（创建、终止）比较多，就会带来很大的开销。

混合实现

结合用户空间和内核空间的优点，设计人员采用了一种内核级线程的方式，然后将用户级线程与某些或者全部内核线程多路复用起来

在这种模型中，编程人员可以自由控制用户线程和内核线程的数量，具有很大的灵活度。采用这种方法，内核只识别内核级线程，并对其进行调度。其中一些内核级线程会被多个用户级线程多路复用。

进程间通信

进程是需要频繁的和其他进程进行交流的。例如，在一个 shell 管道中，第一个进程的输出必须传递给第二个进程，这样沿着管道进行下去。因此，进程之间如果需要通信的话，必须要使用一种良好的数据结构以至于不能被中断。下面我们会一起讨论有关 进程间通信(Inter Process Communication, IPC) 的问题。

关于进程间的通信，这里有三个问题

• 上面提到了第一个问题，那就是一个进程如何传递消息给其他进程。
• 第二个问题是如何确保两个或多个线程之间不会相互干扰。例如，两个航空公司都试图为不同的顾客抢购飞机上的最后一个座位。
• 第三个问题是数据的先后顺序的问题，如果进程 A 产生数据并且进程 B 打印数据。则进程 B 打印数据之前需要先等 A 产生数据后才能够进行打印。

需要注意的是，这三个问题中的后面两个问题同样也适用于线程

第一个问题在线程间比较好解决，因为它们共享一个地址空间，它们具有相同的运行时环境，可以想象你在用高级语言编写多线程代码的过程中，线程通信问题是不是比较容易解决？

另外两个问题也同样适用于线程，同样的问题可用同样的方法来解决。我们后面会慢慢讨论这三个问题，你现在脑子中大致有个印象即可。

竞态条件

在一些操作系统中，协作的进程可能共享一些彼此都能读写的公共资源。公共资源可能在内存中也可能在一个共享文件。为了讲清楚进程间是如何通信的，这里我们举一个例子：一个后台打印程序。当一个进程需要打印某个文件时，它会将文件名放在一个特殊的后台目录(spooler directory)中。另一个进程 打印后台进程(printer daemon) 会定期的检查是否需要文件被打印，如果有的话，就打印并将该文件名从目录下删除。

假设我们的后台目录有非常多的 槽位(slot)，编号依次为 0，1，2，…，每个槽位存放一个文件名。同时假设有两个共享变量：out，指向下一个需要打印的文件；in，指向目录中下个空闲的槽位。可以把这两个文件保存在一个所有进程都能访问的文件中，该文件的长度为两个字。在某一时刻，0 至 3 号槽位空，4 号至 6 号槽位被占用。在同一时刻，进程 A 和 进程 B 都决定将一个文件排队打印，情况如下

墨菲法则(Murphy) 中说过，任何可能出错的地方终将出错，这句话生效时，可能发生如下情况。

进程 A 读到 in 的值为 7，将 7 存在一个局部变量 next_free_slot 中。此时发生一次时钟中断，CPU 认为进程 A 已经运行了足够长的时间，决定切换到进程 B 。进程 B 也读取 in 的值，发现是 7，然后进程 B 将 7 写入到自己的局部变量 next_free_slot 中，在这一时刻两个进程都认为下一个可用槽位是 7 。

进程 B 现在继续运行，它会将打印文件名写入到 slot 7 中，然后把 in 的指针更改为 8 ，然后进程 B 离开去做其他的事情

现在进程 A 开始恢复运行，由于进程 A 通过检查 next_free_slot也发现 slot 7 的槽位是空的，于是将打印文件名存入 slot 7 中，然后把 in 的值更新为 8 ，由于 slot 7 这个槽位中已经有进程 B 写入的值，所以进程 A 的打印文件名会把进程 B 的文件覆盖，由于打印机内部是无法发现是哪个进程更新的，它的功能比较局限，所以这时候进程 B 永远无法打印输出，类似这种情况，即两个或多个线程同时对一共享数据进行修改，从而影响程序运行的正确性时，这种就被称为竞态条件(race condition)。调试竞态条件是一种非常困难的工作，因为绝大多数情况下程序运行良好，但在极少数的情况下会发生一些无法解释的奇怪现象。

临界区

不仅共享资源会造成竞态条件，事实上共享文件、共享内存也会造成竞态条件、那么该如何避免呢？或许一句话可以概括说明：禁止一个或多个进程在同一时刻对共享资源（包括共享内存、共享文件等）进行读写。换句话说，我们需要一种 互斥(mutual exclusion) 条件，这也就是说，如果一个进程在某种方式下使用共享变量和文件的话，除该进程之外的其他进程就禁止做这种事（访问统一资源）。上面问题的纠结点在于，在进程 A 对共享变量的使用未结束之前进程 B 就使用它。在任何操作系统中，为了实现互斥操作而选用适当的原语是一个主要的设计问题，接下来我们会着重探讨一下。

避免竞争问题的条件可以用一种抽象的方式去描述。大部分时间，进程都会忙于内部计算和其他不会导致竞争条件的计算。然而，有时候进程会访问共享内存或文件，或者做一些能够导致竞态条件的操作。我们把对共享内存进行访问的程序片段称作 临界区域(critical region) 或 临界区(critical section)。如果我们能够正确的操作，使两个不同进程不可能同时处于临界区，就能避免竞争条件，这也是从操作系统设计角度来进行的。

尽管上面这种设计避免了竞争条件，但是不能确保并发线程同时访问共享数据的正确性和高效性。一个好的解决方案，应该包含下面四种条件

1. 任何时候两个进程不能同时处于临界区
2. 不应对 CPU 的速度和数量做任何假设
3. 位于临界区外的进程不得阻塞其他进程
4. 不能使任何进程无限等待进入临界区

从抽象的角度来看，我们通常希望进程的行为如上图所示，在 t1 时刻，进程 A 进入临界区，在 t2 的时刻，进程 B 尝试进入临界区，因为此时进程 A 正在处于临界区中，所以进程 B 会阻塞直到 t3 时刻进程 A 离开临界区，此时进程 B 能够允许进入临界区。最后，在 t4 时刻，进程 B 离开临界区，系统恢复到没有进程的原始状态。

忙等互斥

下面我们会继续探讨实现互斥的各种设计，在这些方案中，当一个进程正忙于更新其关键区域的共享内存时，没有其他进程会进入其关键区域，也不会造成影响。

屏蔽中断

在单处理器系统上，最简单的解决方案是让每个进程在进入临界区后立即屏蔽所有中断，并在离开临界区之前重新启用它们。屏蔽中断后，时钟中断也会被屏蔽。CPU 只有发生时钟中断或其他中断时才会进行进程切换。这样，在屏蔽中断后 CPU 不会切换到其他进程。所以，一旦某个进程屏蔽中断之后，它就可以检查和修改共享内存，而不用担心其他进程介入访问共享数据。

这个方案可行吗？进程进入临界区域是由谁决定的呢？不是用户进程吗？当进程进入临界区域后，用户进程关闭中断，如果经过一段较长时间后进程没有离开，那么中断不就一直启用不了，结果会如何？可能会造成整个系统的终止。而且如果是多处理器的话，屏蔽中断仅仅对执行 disable 指令的 CPU 有效。其他 CPU 仍将继续运行，并可以访问共享内存。

另一方面，对内核来说，当它在执行更新变量或列表的几条指令期间将中断屏蔽是很方便的。例如，如果多个进程处理就绪列表中的时候发生中断，则可能会发生竞态条件的出现。所以，屏蔽中断对于操作系统本身来说是一项很有用的技术，但是对于用户线程来说，屏蔽中断却不是一项通用的互斥机制。

锁变量

作为第二种尝试，可以寻找一种软件层面解决方案。考虑有单个共享的（锁）变量，初始为值为 0 。当一个线程想要进入关键区域时，它首先会查看锁的值是否为 0 ，如果锁的值是 0 ，进程会把它设置为 1 并让进程进入关键区域。如果锁的状态是 1，进程会等待直到锁变量的值变为 0 。因此，锁变量的值是 0 则意味着没有线程进入关键区域。如果是 1 则意味着有进程在关键区域内。我们对上图修改后，如下所示

这种设计方式是否正确呢？是否存在纰漏呢？假设一个进程读出锁变量的值并发现它为 0 ，而恰好在它将其设置为 1 之前，另一个进程调度运行，读出锁的变量为0 ，并将锁的变量设置为 1 。然后第一个线程运行，把锁变量的值再次设置为 1，此时，临界区域就会有两个进程在同时运行。

也许有的读者可以这么认为，在进入前检查一次，在要离开的关键区域再检查一次不就解决了吗？实际上这种情况也是于事无补，因为在第二次检查期间其他线程仍有可能修改锁变量的值，换句话说，这种 set-before-check 不是一种 原子性 操作，所以同样还会发生竞争条件。

严格轮询法

第三种互斥的方式先抛出来一段代码，这里的程序是用 C 语言编写，之所以采用 C 是因为操作系统普遍是用 C 来编写的（偶尔会用 C++），而基本不会使用 Java 、Modula3 或 Pascal 这样的语言，Java 中的 native 关键字底层也是 C 或 C++ 编写的源码。对于编写操作系统而言，需要使用 C 语言这种强大、高效、可预知和有特性的语言，而对于 Java ，它是不可预知的，因为它在关键时刻会用完存储器，而在不合适的时候会调用垃圾回收机制回收内存。在 C 语言中，这种情况不会发生，C 语言中不会主动调用垃圾回收回收内存。有关 C 、C++ 、Java 和其他四种语言的比较可以参考 链接

进程 0 的代码

1
2
3
4
5
6
7
8
9

复制代码while(TRUE){
  while(turn != 0){
    /* 进入关键区域 */
    critical_region();
    turn = 1;
    /* 离开关键区域 */
    noncritical_region();
  }
}

进程 1 的代码

1
2
3
4
5
6
7

复制代码while(TRUE){
  while(turn != 1){
    critical_region();
    turn = 0;
    noncritical_region();
  }
}

在上面代码中，变量 turn，初始值为 0 ，用于记录轮到那个进程进入临界区，并检查或更新共享内存。开始时，进程 0 检查 turn，发现其值为 0 ，于是进入临界区。进程 1 也发现其值为 0 ，所以在一个等待循环中不停的测试 turn，看其值何时变为 1。连续检查一个变量直到某个值出现为止，这种方法称为 忙等待(busywaiting)。由于这种方式浪费 CPU 时间，所以这种方式通常应该要避免。只有在有理由认为等待时间是非常短的情况下，才能够使用忙等待。用于忙等待的锁，称为 自旋锁(spinlock)。

进程 0 离开临界区时，它将 turn 的值设置为 1，以便允许进程 1 进入其临界区。假设进程 1 很快便离开了临界区，则此时两个进程都处于临界区之外，turn 的值又被设置为 0 。现在进程 0 很快就执行完了整个循环，它退出临界区，并将 turn 的值设置为 1。此时，turn 的值为 1，两个进程都在其临界区外执行。

突然，进程 0 结束了非临界区的操作并返回到循环的开始。但是，这时它不能进入临界区，因为 turn 的当前值为 1，此时进程 1 还忙于非临界区的操作，进程 0 只能继续 while 循环，直到进程 1 把 turn 的值改为 0 。这说明，在一个进程比另一个进程执行速度慢了很多的情况下，轮流进入临界区并不是一个好的方法。

这种情况违反了前面的叙述 3 ，即 位于临界区外的进程不得阻塞其他进程，进程 0 被一个临界区外的进程阻塞。由于违反了第三条，所以也不能作为一个好的方案。

Peterson 解法

荷兰数学家 T.Dekker 通过将锁变量与警告变量相结合，最早提出了一个不需要严格轮换的软件互斥算法，关于 Dekker 的算法，参考 链接

后来， G.L.Peterson 发现了一种简单很多的互斥算法，它的算法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

复制代码#define FALSE 0
#define TRUE  1
/* 进程数量 */
#define N     2													

/* 现在轮到谁 */
int turn;					

/* 所有值初始化为 0 (FALSE) */
int interested[N];											

/* 进程是 0 或 1 */
void enter_region(int process){					
  
  /* 另一个进程号 */
  int other;														
  
  /* 另一个进程 */
  other = 1 - process;				
  
  /* 表示愿意进入临界区 */
  interested[process] = TRUE;						
  turn = process;
  
  /* 空循环 */
  while(turn == process 
        && interested[other] == true){} 
  
}

void leave_region(int process){
  
  /* 表示离开临界区 */
  interested[process] == FALSE;				 
}

在使用共享变量时（即进入其临界区）之前，各个进程使用各自的进程号 0 或 1 作为参数来调用 enter_region，这个函数调用在需要时将使进程等待，直到能够安全的临界区。在完成对共享变量的操作之后，进程将调用 leave_region 表示操作完成，并且允许其他进程进入。

现在来看看这个办法是如何工作的。一开始，没有任何进程处于临界区中，现在进程 0 调用 enter_region。它通过设置数组元素和将 turn 置为 0 来表示它希望进入临界区。由于进程 1 并不想进入临界区，所以 enter_region 很快便返回。如果进程现在调用 enter_region，进程 1 将在此处挂起直到 interested[0] 变为 FALSE，这种情况只有在进程 0 调用 leave_region 退出临界区时才会发生。

那么上面讨论的是顺序进入的情况，现在来考虑一种两个进程同时调用 enter_region 的情况。它们都将自己的进程存入 turn，但只有最后保存进去的进程号才有效，前一个进程的进程号因为重写而丢失。假如进程 1 是最后存入的，则 turn 为 1 。当两个进程都运行到 while 的时候，进程 0 将不会循环并进入临界区，而进程 1 将会无限循环且不会进入临界区，直到进程 0 退出位置。

TSL 指令

现在来看一种需要硬件帮助的方案。一些计算机，特别是那些设计为多处理器的计算机，都会有下面这条指令

1

复制代码TSL RX,LOCK

称为 测试并加锁(test and set lock)，它将一个内存字 lock 读到寄存器 RX 中，然后在该内存地址上存储一个非零值。读写指令能保证是一体的，不可分割的，一同执行的。在这个指令结束之前其他处理器均不允许访问内存。执行 TSL 指令的 CPU 将会锁住内存总线，用来禁止其他 CPU 在这个指令结束之前访问内存。

很重要的一点是锁住内存总线和禁用中断不一样。禁用中断并不能保证一个处理器在读写操作之间另一个处理器对内存的读写。也就是说，在处理器 1 上屏蔽中断对处理器 2 没有影响。让处理器 2 远离内存直到处理器 1 完成读写的最好的方式就是锁住总线。这需要一个特殊的硬件（基本上，一根总线就可以确保总线由锁住它的处理器使用，而其他的处理器不能使用）

为了使用 TSL 指令，要使用一个共享变量 lock 来协调对共享内存的访问。当 lock 为 0 时，任何进程都可以使用 TSL 指令将其设置为 1，并读写共享内存。当操作结束时，进程使用 move 指令将 lock 的值重新设置为 0 。

这条指令如何防止两个进程同时进入临界区呢？下面是解决方案

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

复制代码enter_region:
			| 复制锁到寄存器并将锁设为1
			TSL REGISTER,LOCK              
			| 锁是 0 吗？
  		CMP REGISTER,#0						 		
  		| 若不是零，说明锁已被设置，所以循环
  		JNE enter_region					 		
  		| 返回调用者，进入临界区
  		RET												 
       
leave_region:

			| 在锁中存入 0
			MOVE LOCK,#0			      
      | 返回调用者
  		RET

我们可以看到这个解决方案的思想和 Peterson 的思想很相似。假设存在如下共 4 指令的汇编语言程序。第一条指令将 lock 原来的值复制到寄存器中并将 lock 设置为 1 ，随后这个原来的值和 0 做对比。如果它不是零，说明之前已经被加过锁，则程序返回到开始并再次测试。经过一段时间后（可长可短），该值变为 0 （当前处于临界区中的进程退出临界区时），于是过程返回，此时已加锁。要清除这个锁也比较简单，程序只需要将 0 存入 lock 即可，不需要特殊的同步指令。

现在有了一种很明确的做法，那就是进程在进入临界区之前会先调用 enter_region，判断是否进行循环，如果lock 的值是 1 ，进行无限循环，如果 lock 是 0，不进入循环并进入临界区。在进程从临界区返回时它调用 leave_region，这会把 lock 设置为 0 。与基于临界区问题的所有解法一样，进程必须在正确的时间调用 enter_region 和 leave_region ，解法才能奏效。

还有一个可以替换 TSL 的指令是 XCHG，它原子性的交换了两个位置的内容，例如，一个寄存器与一个内存字，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复制代码enter_region:
		| 把 1 放在内存器中
		MOVE REGISTER,#1	
    | 交换寄存器和锁变量的内容
		XCHG REGISTER,LOCK			
    | 锁是 0 吗？
		CMP REGISTER,#0		
    | 若不是 0 ，锁已被设置，进行循环
		JNE enter_region					
    | 返回调用者，进入临界区
		RET														
	
leave_region:				
		| 在锁中存入 0 
		MOVE LOCK,#0	
    | 返回调用者
		RET

XCHG 的本质上与 TSL 的解决办法一样。所有的 Intel x86 CPU 在底层同步中使用 XCHG 指令。

睡眠与唤醒

上面解法中的 Peterson 、TSL 和 XCHG 解法都是正确的，但是它们都有忙等待的缺点。这些解法的本质上都是一样的，先检查是否能够进入临界区，若不允许，则该进程将原地等待，直到允许为止。

这种方式不但浪费了 CPU 时间，而且还可能引起意想不到的结果。考虑一台计算机上有两个进程，这两个进程具有不同的优先级，H 是属于优先级比较高的进程，L 是属于优先级比较低的进程。进程调度的规则是不论何时只要 H 进程处于就绪态 H 就开始运行。在某一时刻，L 处于临界区中，此时 H 变为就绪态，准备运行（例如，一条 I/O 操作结束）。现在 H 要开始忙等，但由于当 H 就绪时 L 就不会被调度，L 从来不会有机会离开关键区域，所以 H 会变成死循环，有时将这种情况称为优先级反转问题(priority inversion problem)。

现在让我们看一下进程间的通信原语，这些原语在不允许它们进入关键区域之前会阻塞而不是浪费 CPU 时间，最简单的是 sleep 和 wakeup。Sleep 是一个能够造成调用者阻塞的系统调用，也就是说，这个系统调用会暂停直到其他进程唤醒它。wakeup 调用有一个参数，即要唤醒的进程。还有一种方式是 wakeup 和 sleep 都有一个参数，即 sleep 和 wakeup 需要匹配的内存地址。

生产者-消费者问题

作为这些私有原语的例子，让我们考虑生产者-消费者(producer-consumer) 问题，也称作 有界缓冲区(bounded-buffer) 问题。两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者(producer)，将信息放入缓冲区， 另一个是消费者(consumer)，会从缓冲区中取出。也可以把这个问题一般化为 m 个生产者和 n 个消费者的问题，但是我们这里只讨论一个生产者和一个消费者的情况，这样可以简化实现方案。

如果缓冲队列已满，那么当生产者仍想要将数据写入缓冲区的时候，会出现问题。它的解决办法是让生产者睡眠，也就是阻塞生产者。等到消费者从缓冲区中取出一个或多个数据项时再唤醒它。同样的，当消费者试图从缓冲区中取数据，但是发现缓冲区为空时，消费者也会睡眠，阻塞。直到生产者向其中放入一个新的数据。

这个逻辑听起来比较简单，而且这种方式也需要一种称作 监听 的变量，这个变量用于监视缓冲区的数据，我们暂定为 count，如果缓冲区最多存放 N 个数据项，生产者会每次判断 count 是否达到 N，否则生产者向缓冲区放入一个数据项并增量 count 的值。消费者的逻辑也很相似：首先测试 count 的值是否为 0 ，如果为 0 则消费者睡眠、阻塞，否则会从缓冲区取出数据并使 count 数量递减。每个进程也会检查检查是否其他线程是否应该被唤醒，如果应该被唤醒，那么就唤醒该线程。下面是生产者消费者的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

复制代码/* 缓冲区 slot 槽的数量 */
#define N 100						
/* 缓冲区数据的数量 */
int count = 0										
  
// 生产者
void producer(void){
  int item;
  
  /* 无限循环 */
  while(TRUE){				
    /* 生成下一项数据 */
    item = produce_item()				
    /* 如果缓存区是满的，就会阻塞 */
    if(count == N){
      sleep();									
    }
    
    /* 把当前数据放在缓冲区中 */
    insert_item(item);
    /* 增加缓冲区 count 的数量 */
    count = count + 1;					
    if(count == 1){
      /* 缓冲区是否为空？ */
      wakeup(consumer);					
    }
  }
}

// 消费者
void consumer(void){
  
  int item;
  
  /* 无限循环 */
  while(TRUE){
    /* 如果缓冲区是空的，就会进行阻塞 */
  	if(count == 0){							
      sleep();
    }
    /* 从缓冲区中取出一个数据 */
   	item = remove_item();			
    /* 将缓冲区的 count 数量减一 */
    count = count - 1
    /* 缓冲区满嘛？ */
    if(count == N - 1){					
      wakeup(producer);		
    }
    /* 打印数据项 */
    consumer_item(item);				
  }
  
}

为了在 C 语言中描述像是 sleep 和 wakeup 的系统调用，我们将以库函数调用的形式来表示。它们不是 C 标准库的一部分，但可以在实际具有这些系统调用的任何系统上使用。代码中未实现的 insert_item 和 remove_item 用来记录将数据项放入缓冲区和从缓冲区取出数据等。

现在让我们回到生产者-消费者问题上来，上面代码中会产生竞争条件，因为 count 这个变量是暴露在大众视野下的。有可能出现下面这种情况：缓冲区为空，此时消费者刚好读取 count 的值发现它为 0 。此时调度程序决定暂停消费者并启动运行生产者。生产者生产了一条数据并把它放在缓冲区中，然后增加 count 的值，并注意到它的值是 1 。由于 count 为 0，消费者必须处于睡眠状态，因此生产者调用 wakeup 来唤醒消费者。但是，消费者此时在逻辑上并没有睡眠，所以 wakeup 信号会丢失。当消费者下次启动后，它会查看之前读取的 count 值，发现它的值是 0 ，然后在此进行睡眠。不久之后生产者会填满整个缓冲区，在这之后会阻塞，这样一来两个进程将永远睡眠下去。

引起上面问题的本质是 唤醒尚未进行睡眠状态的进程会导致唤醒丢失。如果它没有丢失，则一切都很正常。一种快速解决上面问题的方式是增加一个唤醒等待位(wakeup waiting bit)。当一个 wakeup 信号发送给仍在清醒的进程后，该位置为 1 。之后，当进程尝试睡眠的时候，如果唤醒等待位为 1 ，则该位清除，而进程仍然保持清醒。

然而，当进程数量有许多的时候，这时你可以说通过增加唤醒等待位的数量来唤醒等待位，于是就有了 2、4、6、8 个唤醒等待位，但是并没有从根本上解决问题。

信号量

信号量是 E.W.Dijkstra 在 1965 年提出的一种方法，它使用一个整形变量来累计唤醒次数，以供之后使用。在他的观点中，有一个新的变量类型称作 信号量(semaphore)。一个信号量的取值可以是 0 ，或任意正数。0 表示的是不需要任何唤醒，任意的正数表示的就是唤醒次数。

Dijkstra 提出了信号量有两个操作，现在通常使用 down 和 up（分别可以用 sleep 和 wakeup 来表示）。down 这个指令的操作会检查值是否大于 0 。如果大于 0 ，则将其值减 1 ；若该值为 0 ，则进程将睡眠，而且此时 down 操作将会继续执行。检查数值、修改变量值以及可能发生的睡眠操作均为一个单一的、不可分割的 原子操作(atomic action) 完成。这会保证一旦信号量操作开始，没有其他的进程能够访问信号量，直到操作完成或者阻塞。这种原子性对于解决同步问题和避免竞争绝对必不可少。

原子性操作指的是在计算机科学的许多其他领域中，一组相关操作全部执行而没有中断或根本不执行。

up 操作会使信号量的值 + 1。如果一个或者多个进程在信号量上睡眠，无法完成一个先前的 down 操作，则由系统选择其中一个并允许该程完成 down 操作。因此，对一个进程在其上睡眠的信号量执行一次 up 操作之后，该信号量的值仍然是 0 ，但在其上睡眠的进程却少了一个。信号量的值增 1 和唤醒一个进程同样也是不可分割的。不会有某个进程因执行 up 而阻塞，正如在前面的模型中不会有进程因执行 wakeup 而阻塞是一样的道理。

用信号量解决生产者 - 消费者问题

用信号量解决丢失的 wakeup 问题，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

复制代码/* 定义缓冲区槽的数量 */
#define N 100
/* 信号量是一种特殊的 int */
typedef int semaphore;
/* 控制关键区域的访问 */
semaphore mutex = 1;
/* 统计 buffer 空槽的数量 */
semaphore empty = N;
/* 统计 buffer 满槽的数量 */
semaphore full = 0;												

void producer(void){ 
  
  int item;  
  
  /* TRUE 的常量是 1 */
  while(TRUE){			
    /* 产生放在缓冲区的一些数据 */
    item = producer_item();		
    /* 将空槽数量减 1  */
    down(&empty);	
    /* 进入关键区域  */
    down(&mutex);	
    /* 把数据放入缓冲区中 */
    insert_item(item);
    /* 离开临界区 */
    up(&mutex);	
    /* 将 buffer 满槽数量 + 1 */
    up(&full);														
  }
}

void consumer(void){
  
  int item;
  
  /* 无限循环 */
  while(TRUE){
    /* 缓存区满槽数量 - 1 */
    down(&full);
    /* 进入缓冲区 */	
    down(&mutex);
    /* 从缓冲区取出数据 */
    item = remove_item();	
    /* 离开临界区 */
    up(&mutex);	
    /* 将空槽数目 + 1 */
    up(&empty);	
    /* 处理数据 */
    consume_item(item);											
  }
  
}

为了确保信号量能正确工作，最重要的是要采用一种不可分割的方式来实现它。通常是将 up 和 down 作为系统调用来实现。而且操作系统只需在执行以下操作时暂时屏蔽全部中断：检查信号量、更新、必要时使进程睡眠。由于这些操作仅需要非常少的指令，因此中断不会造成影响。如果使用多个 CPU，那么信号量应该被锁进行保护。使用 TSL 或者 XCHG 指令用来确保同一时刻只有一个 CPU 对信号量进行操作。

使用 TSL 或者 XCHG 来防止几个 CPU 同时访问一个信号量，与生产者或消费者使用忙等待来等待其他腾出或填充缓冲区是完全不一样的。前者的操作仅需要几个毫秒，而生产者或消费者可能需要任意长的时间。

上面这个解决方案使用了三种信号量：一个称为 full，用来记录充满的缓冲槽数目；一个称为 empty，记录空的缓冲槽数目；一个称为 mutex，用来确保生产者和消费者不会同时进入缓冲区。Full 被初始化为 0 ，empty 初始化为缓冲区中插槽数，mutex 初始化为 1。信号量初始化为 1 并且由两个或多个进程使用，以确保它们中同时只有一个可以进入关键区域的信号被称为 二进制信号量(binary semaphores)。如果每个进程都在进入关键区域之前执行 down 操作，而在离开关键区域之后执行 up 操作，则可以确保相互互斥。

现在我们有了一个好的进程间原语的保证。然后我们再来看一下中断的顺序保证

1. 硬件压入堆栈程序计数器等
2. 硬件从中断向量装入新的程序计数器
3. 汇编语言过程保存寄存器的值
4. 汇编语言过程设置新的堆栈
5. C 中断服务器运行（典型的读和缓存写入）
6. 调度器决定下面哪个程序先运行
7. C 过程返回至汇编代码
8. 汇编语言过程开始运行新的当前进程

在使用信号量的系统中，隐藏中断的自然方法是让每个 I/O 设备都配备一个信号量，该信号量最初设置为0。在 I/O 设备启动后，中断处理程序立刻对相关联的信号执行一个 down 操作，于是进程立即被阻塞。当中断进入时，中断处理程序随后对相关的信号量执行一个 up操作，能够使已经阻止的进程恢复运行。在上面的中断处理步骤中，其中的第 5 步 C 中断服务器运行 就是中断处理程序在信号量上执行的一个 up 操作，所以在第 6 步中，操作系统能够执行设备驱动程序。当然，如果有几个进程已经处于就绪状态，调度程序可能会选择接下来运行一个更重要的进程，我们会在后面讨论调度的算法。

上面的代码实际上是通过两种不同的方式来使用信号量的，而这两种信号量之间的区别也是很重要的。mutex 信号量用于互斥。它用于确保任意时刻只有一个进程能够对缓冲区和相关变量进行读写。互斥是用于避免进程混乱所必须的一种操作。

另外一个信号量是关于同步(synchronization)的。full 和 empty 信号量用于确保事件的发生或者不发生。在这个事例中，它们确保了缓冲区满时生产者停止运行；缓冲区为空时消费者停止运行。这两个信号量的使用与 mutex 不同。

互斥量

如果不需要信号量的计数能力时，可以使用信号量的一个简单版本，称为 mutex(互斥量)。互斥量的优势就在于在一些共享资源和一段代码中保持互斥。由于互斥的实现既简单又有效，这使得互斥量在实现用户空间线程包时非常有用。

互斥量是一个处于两种状态之一的共享变量：解锁(unlocked) 和 加锁(locked)。这样，只需要一个二进制位来表示它，不过一般情况下，通常会用一个 整形(integer) 来表示。0 表示解锁，其他所有的值表示加锁，比 1 大的值表示加锁的次数。

mutex 使用两个过程，当一个线程（或者进程）需要访问关键区域时，会调用 mutex_lock 进行加锁。如果互斥锁当前处于解锁状态（表示关键区域可用），则调用成功，并且调用线程可以自由进入关键区域。

另一方面，如果 mutex 互斥量已经锁定的话，调用线程会阻塞直到关键区域内的线程执行完毕并且调用了 mutex_unlock 。如果多个线程在 mutex 互斥量上阻塞，将随机选择一个线程并允许它获得锁。

由于 mutex 互斥量非常简单，所以只要有 TSL 或者是 XCHG 指令，就可以很容易地在用户空间实现它们。用于用户级线程包的 mutex_lock 和 mutex_unlock 代码如下，XCHG 的本质也一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

复制代码mutex_lock:
			| 将互斥信号量复制到寄存器，并将互斥信号量置为1
			TSL REGISTER,MUTEX
      | 互斥信号量是 0 吗？
			CMP REGISTER,#0	
      | 如果互斥信号量为0，它被解锁，所以返回
			JZE ok	
      | 互斥信号正在使用；调度其他线程
			CALL thread_yield	
      | 再试一次
			JMP mutex_lock	
      | 返回调用者，进入临界区
ok: 	RET														

mutex_unlcok:
			| 将 mutex 置为 0 
			MOVE MUTEX,#0	
      | 返回调用者
			RET

mutex_lock 的代码和上面 enter_region 的代码很相似，我们可以对比着看一下

上面代码最大的区别你看出来了吗？

• 根据上面我们对 TSL 的分析，我们知道，如果 TSL 判断没有进入临界区的进程会进行无限循环获取锁，而在 TSL 的处理中，如果 mutex 正在使用，那么就调度其他线程进行处理。所以上面最大的区别其实就是在判断 mutex/TSL 之后的处理。
• 在（用户）线程中，情况有所不同，因为没有时钟来停止运行时间过长的线程。结果是通过忙等待的方式来试图获得锁的线程将永远循环下去，决不会得到锁，因为这个运行的线程不会让其他线程运行从而释放锁，其他线程根本没有获得锁的机会。在后者获取锁失败时，它会调用 thread_yield 将 CPU 放弃给另外一个线程。结果就不会进行忙等待。在该线程下次运行时，它再一次对锁进行测试。

上面就是 enter_region 和 mutex_lock 的差别所在。由于 thread_yield 仅仅是一个用户空间的线程调度，所以它的运行非常快捷。这样，mutex_lock 和 mutex_unlock 都不需要任何内核调用。通过使用这些过程，用户线程完全可以实现在用户空间中的同步，这个过程仅仅需要少量的同步。

我们上面描述的互斥量其实是一套调用框架中的指令。从软件角度来说，总是需要更多的特性和同步原语。例如，有时线程包提供一个调用 mutex_trylock，这个调用尝试获取锁或者返回错误码，但是不会进行加锁操作。这就给了调用线程一个灵活性，以决定下一步做什么，是使用替代方法还是等候下去。

Futexes

随着并行的增加，有效的同步(synchronization)和锁定(locking) 对于性能来说是非常重要的。如果进程等待时间很短，那么自旋锁(Spin lock) 是非常有效；但是如果等待时间比较长，那么这会浪费 CPU 周期。如果进程很多，那么阻塞此进程，并仅当锁被释放的时候让内核解除阻塞是更有效的方式。不幸的是，这种方式也会导致另外的问题：它可以在进程竞争频繁的时候运行良好，但是在竞争不是很激烈的情况下内核切换的消耗会非常大，而且更困难的是，预测锁的竞争数量更不容易。

有一种有趣的解决方案是把两者的优点结合起来，提出一种新的思想，称为 futex，或者是 快速用户空间互斥(fast user space mutex)，是不是听起来很有意思？

futex 是 Linux 中的特性实现了基本的锁定（很像是互斥锁）而且避免了陷入内核中，因为内核的切换的开销非常大，这样做可以大大提高性能。futex 由两部分组成：内核服务和用户库。内核服务提供了了一个 等待队列(wait queue) 允许多个进程在锁上排队等待。除非内核明确的对他们解除阻塞，否则它们不会运行。

对于一个进程来说，把它放到等待队列需要昂贵的系统调用，这种方式应该被避免。在没有竞争的情况下，futex 可以直接在用户空间中工作。这些进程共享一个 32 位整数(integer) 作为公共锁变量。假设锁的初始化为 1，我们认为这时锁已经被释放了。线程通过执行原子性的操作减少并测试(decrement and test) 来抢占锁。decrement and set 是 Linux 中的原子功能，由包裹在 C 函数中的内联汇编组成，并在头文件中进行定义。下一步，线程会检查结果来查看锁是否已经被释放。如果锁现在不是锁定状态，那么刚好我们的线程可以成功抢占该锁。然而，如果锁被其他线程持有，抢占锁的线程不得不等待。在这种情况下，futex 库不会自旋，但是会使用一个系统调用来把线程放在内核中的等待队列中。这样一来，切换到内核的开销已经是合情合理的了，因为线程可以在任何时候阻塞。当线程完成了锁的工作时，它会使用原子性的 增加并测试(increment and test) 释放锁，并检查结果以查看内核等待队列上是否仍阻止任何进程。如果有的话，它会通知内核可以对等待队列中的一个或多个进程解除阻塞。如果没有锁竞争，内核则不需要参与竞争。

Pthreads 中的互斥量

Pthreads 提供了一些功能用来同步线程。最基本的机制是使用互斥量变量，可以锁定和解锁，用来保护每个关键区域。希望进入关键区域的线程首先要尝试获取 mutex。如果 mutex 没有加锁，线程能够马上进入并且互斥量能够自动锁定，从而阻止其他线程进入。如果 mutex 已经加锁，调用线程会阻塞，直到 mutex 解锁。如果多个线程在相同的互斥量上等待，当互斥量解锁时，只有一个线程能够进入并且重新加锁。这些锁并不是必须的，程序员需要正确使用它们。

下面是与互斥量有关的函数调用

向我们想象中的一样，mutex 能够被创建和销毁，扮演这两个角色的分别是 Phread_mutex_init 和 Pthread_mutex_destroy。mutex 也可以通过 Pthread_mutex_lock 来进行加锁，如果互斥量已经加锁，则会阻塞调用者。还有一个调用Pthread_mutex_trylock 用来尝试对线程加锁，当 mutex 已经被加锁时，会返回一个错误代码而不是阻塞调用者。这个调用允许线程有效的进行忙等。最后，Pthread_mutex_unlock 会对 mutex 解锁并且释放一个正在等待的线程。

除了互斥量以外，Pthreads 还提供了第二种同步机制： 条件变量(condition variables) 。mutex 可以很好的允许或阻止对关键区域的访问。条件变量允许线程由于未满足某些条件而阻塞。绝大多数情况下这两种方法是一起使用的。下面我们进一步来研究线程、互斥量、条件变量之间的关联。

下面再来重新认识一下生产者和消费者问题：一个线程将东西放在一个缓冲区内，由另一个线程将它们取出。如果生产者发现缓冲区没有空槽可以使用了，生产者线程会阻塞起来直到有一个线程可以使用。生产者使用 mutex 来进行原子性检查从而不受其他线程干扰。但是当发现缓冲区已经满了以后，生产者需要一种方法来阻塞自己并在以后被唤醒。这便是条件变量做的工作。

下面是一些与条件变量有关的最重要的 pthread 调用

上表中给出了一些调用用来创建和销毁条件变量。条件变量上的主要属性是 Pthread_cond_wait 和 Pthread_cond_signal。前者阻塞调用线程，直到其他线程发出信号为止（使用后者调用）。阻塞的线程通常需要等待唤醒的信号以此来释放资源或者执行某些其他活动。只有这样阻塞的线程才能继续工作。条件变量允许等待与阻塞原子性的进程。Pthread_cond_broadcast 用来唤醒多个阻塞的、需要等待信号唤醒的线程。

需要注意的是，条件变量（不像是信号量）不会存在于内存中。如果将一个信号量传递给一个没有线程等待的条件变量，那么这个信号就会丢失，这个需要注意

下面是一个使用互斥量和条件变量的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

复制代码#include <stdio.h>
#include <pthread.h>

/* 需要生产的数量 */
#define MAX 1000000000										
pthread_mutex_t the_mutex;
/* 使用信号量 */
pthread_cond_t condc,condp;								
int buffer = 0;

/* 生产数据 */
void *producer(void *ptr){								
  
  int i;
  
  for(int i = 0;i <= MAX;i++){
    /* 缓冲区独占访问，也就是使用 mutex 获取锁 */
    pthread_mutex_lock(&the_mutex);				
    while(buffer != 0){
      pthread_cond_wait(&condp,&the_mutex);
    }
    /* 把他们放在缓冲区中 */
    buffer = i;			
    /* 唤醒消费者 */
    pthread_cond_signal(&condc);	
    /* 释放缓冲区 */
    pthread_mutex_unlock(&the_mutex);			
  }
  pthread_exit(0);
  
}

/* 消费数据 */
void *consumer(void *ptr){								
  
  int i;
  
  for(int i = 0;i <= MAX;i++){
    /* 缓冲区独占访问，也就是使用 mutex 获取锁 */
    pthread_mutex_lock(&the_mutex);				
    while(buffer == 0){
      pthread_cond_wait(&condc,&the_mutex);
    }
    /* 把他们从缓冲区中取出 */
    buffer = 0;	
    /* 唤醒生产者 */
    pthread_cond_signal(&condp);
    /* 释放缓冲区 */
    pthread_mutex_unlock(&the_mutex);			
  }
  pthread_exit(0);
  
}

管程

为了能够编写更加准确无误的程序，Brinch Hansen 和 Hoare 提出了一个更高级的同步原语叫做 管程(monitor)。他们两个人的提案略有不同，通过下面的描述你就可以知道。管程是程序、变量和数据结构等组成的一个集合，它们组成一个特殊的模块或者包。进程可以在任何需要的时候调用管程中的程序，但是它们不能从管程外部访问数据结构和程序。下面展示了一种抽象的，类似 Pascal 语言展示的简洁的管程。不能用 C 语言进行描述，因为管程是语言概念而 C 语言并不支持管程。

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

复制代码monitor example
	integer i;
	condition c;
	
	procedure producer();
  ...
	end;	
	
	procedure consumer();
	.
	end;
end monitor;

管程有一个很重要的特性，即在任何时候管程中只能有一个活跃的进程，这一特性使管程能够很方便的实现互斥操作。管程是编程语言的特性，所以编译器知道它们的特殊性，因此可以采用与其他过程调用不同的方法来处理对管程的调用。通常情况下，当进程调用管程中的程序时，该程序的前几条指令会检查管程中是否有其他活跃的进程。如果有的话，调用进程将被挂起，直到另一个进程离开管程才将其唤醒。如果没有活跃进程在使用管程，那么该调用进程才可以进入。

进入管程中的互斥由编译器负责，但是一种通用做法是使用 互斥量(mutex) 和 二进制信号量(binary semaphore)。由于编译器而不是程序员在操作，因此出错的几率会大大降低。在任何时候，编写管程的程序员都无需关心编译器是如何处理的。他只需要知道将所有的临界区转换成为管程过程即可。绝不会有两个进程同时执行临界区中的代码。

即使管程提供了一种简单的方式来实现互斥，但在我们看来，这还不够。因为我们还需要一种在进程无法执行被阻塞。在生产者-消费者问题中，很容易将针对缓冲区满和缓冲区空的测试放在管程程序中，但是生产者在发现缓冲区满的时候该如何阻塞呢？

解决的办法是引入条件变量(condition variables) 以及相关的两个操作 wait 和 signal。当一个管程程序发现它不能运行时（例如，生产者发现缓冲区已满），它会在某个条件变量（如 full）上执行 wait 操作。这个操作造成调用进程阻塞，并且还将另一个以前等在管程之外的进程调入管程。在前面的 pthread 中我们已经探讨过条件变量的实现细节了。另一个进程，比如消费者可以通过执行 signal 来唤醒阻塞的调用进程。

Brinch Hansen 和 Hoare 在对进程唤醒上有所不同，Hoare 建议让新唤醒的进程继续运行；而挂起另外的进程。而 Brinch Hansen 建议让执行 signal 的进程必须退出管程，这里我们采用 Brinch Hansen 的建议，因为它在概念上更简单，并且更容易实现。

如果在一个条件变量上有若干进程都在等待，则在对该条件执行 signal 操作后，系统调度程序只能选择其中一个进程恢复运行。

顺便提一下，这里还有上面两位教授没有提出的第三种方式，它的理论是让执行 signal 的进程继续运行，等待这个进程退出管程时，其他进程才能进入管程。

条件变量不是计数器。条件变量也不能像信号量那样积累信号以便以后使用。所以，如果向一个条件变量发送信号，但是该条件变量上没有等待进程，那么信号将会丢失。也就是说，wait 操作必须在 signal 之前执行。

下面是一个使用 Pascal 语言通过管程实现的生产者-消费者问题的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

复制代码monitor ProducerConsumer
		condition full,empty;
		integer count;
		
		procedure insert(item:integer);
		begin
				if count = N then wait(full);
				insert_item(item);
				count := count + 1;
				if count = 1 then signal(empty);
		end;
		
		function remove:integer;
		begin
				if count = 0 then wait(empty);
				remove = remove_item;
				count := count - 1;
				if count = N - 1 then signal(full);
		end;
		
		count := 0;
end monitor;

procedure producer;
begin
			while true do
      begin 
      			item = produce_item;
      			ProducerConsumer.insert(item);
      end
end;

procedure consumer;
begin 
			while true do
			begin
						item = ProducerConsumer.remove;
						consume_item(item);
			end
end;

读者可能觉得 wait 和 signal 操作看起来像是前面提到的 sleep 和 wakeup ，而且后者存在严重的竞争条件。它们确实很像，但是有个关键的区别：sleep 和 wakeup 之所以会失败是因为当一个进程想睡眠时，另一个进程试图去唤醒它。使用管程则不会发生这种情况。管程程序的自动互斥保证了这一点，如果管程过程中的生产者发现缓冲区已满，它将能够完成 wait 操作而不用担心调度程序可能会在 wait 完成之前切换到消费者。甚至，在 wait 执行完成并且把生产者标志为不可运行之前，是不会允许消费者进入管程的。

尽管类 Pascal 是一种想象的语言，但还是有一些真正的编程语言支持，比如 Java （终于轮到大 Java 出场了），Java 是能够支持管程的，它是一种 面向对象的语言，支持用户级线程，还允许将方法划分为类。只要将关键字 synchronized 关键字加到方法中即可。Java 能够保证一旦某个线程执行该方法，就不允许其他线程执行该对象中的任何 synchronized 方法。没有关键字 synchronized ，就不能保证没有交叉执行。

下面是 Java 使用管程解决的生产者-消费者问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

复制代码public class ProducerConsumer {
  // 定义缓冲区大小的长度
  static final int N = 100;
  // 初始化一个新的生产者线程
  static Producer p = new Producer();
  // 初始化一个新的消费者线程
  static Consumer c = new Consumer();		
  // 初始化一个管程
  static Our_monitor mon = new Our_monitor(); 
  
  // run 包含了线程代码
  static class Producer extends Thread{
    public void run(){												
      int item;
      // 生产者循环
      while(true){														
        item = produce_item();
        mon.insert(item);
      }
    }
    // 生产代码
    private int produce_item(){...}						
  }
  
  // run 包含了线程代码
  static class consumer extends Thread {
    public void run( ) {											
   		int item;
      while(true){
        item = mon.remove();
				consume_item(item);
      }
    }
    // 消费代码
    private int produce_item(){...}						
  }
  
  // 这是管程
  static class Our_monitor {									
    private int buffer[] = new int[N];
    // 计数器和索引
    private int count = 0,lo = 0,hi = 0;			
    
    private synchronized void insert(int val){
      if(count == N){
        // 如果缓冲区是满的，则进入休眠
        go_to_sleep();												
      }
      // 向缓冲区插入内容
			buffer[hi] = val;					
      // 找到下一个槽的为止
      hi = (hi + 1) % N; 				
      // 缓冲区中的数目自增 1 
      count = count + 1;											
      if(count == 1){
        // 如果消费者睡眠，则唤醒
        notify();															
      }
    }
    
    private synchronized void remove(int val){
      int val;
      if(count == 0){
        // 缓冲区是空的，进入休眠
        go_to_sleep();												
      }
      // 从缓冲区取出数据
      val = buffer[lo];				
      // 设置待取出数据项的槽
      lo = (lo + 1) % N;					
      // 缓冲区中的数据项数目减 1 
      count = count - 1;											
      if(count = N - 1){
        // 如果生产者睡眠，唤醒它
        notify();															
      }
      return val;
    }
    
    private void go_to_sleep() {
      try{
        wait( );
      }catch(Interr uptedExceptionexc) {};
    }
  }
      
}

上面的代码中主要设计四个类，外部类(outer class) ProducerConsumer 创建并启动两个线程，p 和 c。第二个类和第三个类 Producer 和 Consumer 分别包含生产者和消费者代码。最后，Our_monitor 是管程，它有两个同步线程，用于在共享缓冲区中插入和取出数据。

在前面的所有例子中，生产者和消费者线程在功能上与它们是相同的。生产者有一个无限循环，该无限循环产生数据并将数据放入公共缓冲区中；消费者也有一个等价的无限循环，该无限循环用于从缓冲区取出数据并完成一系列工作。

程序中比较耐人寻味的就是 Our_monitor 了，它包含缓冲区、管理变量以及两个同步方法。当生产者在 insert 内活动时，它保证消费者不能在 remove 方法中运行，从而保证更新变量以及缓冲区的安全性，并且不用担心竞争条件。变量 count 记录在缓冲区中数据的数量。变量 lo 是缓冲区槽的序号，指出将要取出的下一个数据项。类似地，hi 是缓冲区中下一个要放入的数据项序号。允许 lo = hi，含义是在缓冲区中有 0 个或 N 个数据。

Java 中的同步方法与其他经典管程有本质差别：Java 没有内嵌的条件变量。然而，Java 提供了 wait 和 notify 分别与 sleep 和 wakeup 等价。

通过临界区自动的互斥，管程比信号量更容易保证并行编程的正确性。但是管程也有缺点，我们前面说到过管程是一个编程语言的概念，编译器必须要识别管程并用某种方式对其互斥作出保证。C、Pascal 以及大多数其他编程语言都没有管程，所以不能依靠编译器来遵守互斥规则。

与管程和信号量有关的另一个问题是，这些机制都是设计用来解决访问共享内存的一个或多个 CPU 上的互斥问题的。通过将信号量放在共享内存中并用 TSL 或 XCHG 指令来保护它们，可以避免竞争。但是如果是在分布式系统中，可能同时具有多个 CPU 的情况，并且每个 CPU 都有自己的私有内存呢，它们通过网络相连，那么这些原语将会失效。因为信号量太低级了，而管程在少数几种编程语言之外无法使用，所以还需要其他方法。

消息传递

上面提到的其他方法就是 消息传递(messaage passing)。这种进程间通信的方法使用两个原语 send 和 receive ，它们像信号量而不像管程，是系统调用而不是语言级别。示例如下

1
2
3

复制代码send(destination, &message);

receive(source, &message);

send 方法用于向一个给定的目标发送一条消息，receive 从一个给定的源接受一条消息。如果没有消息，接受者可能被阻塞，直到接受一条消息或者带着错误码返回。

消息传递系统的设计要点

消息传递系统现在面临着许多信号量和管程所未涉及的问题和设计难点，尤其对那些在网络中不同机器上的通信状况。例如，消息有可能被网络丢失。为了防止消息丢失，发送方和接收方可以达成一致：一旦接受到消息后，接收方马上回送一条特殊的 确认(acknowledgement) 消息。如果发送方在一段时间间隔内未收到确认，则重发消息。

现在考虑消息本身被正确接收，而返回给发送着的确认消息丢失的情况。发送者将重发消息，这样接受者将收到两次相同的消息。

对于接收者来说，如何区分新的消息和一条重发的老消息是非常重要的。通常采用在每条原始消息中嵌入一个连续的序号来解决此问题。如果接受者收到一条消息，它具有与前面某一条消息一样的序号，就知道这条消息是重复的，可以忽略。

消息系统还必须处理如何命名进程的问题，以便在发送或接收调用中清晰的指明进程。身份验证(authentication) 也是一个问题，比如客户端怎么知道它是在与一个真正的文件服务器通信，从发送方到接收方的信息有可能被中间人所篡改。

用消息传递解决生产者-消费者问题

现在我们考虑如何使用消息传递来解决生产者-消费者问题，而不是共享缓存。下面是一种解决方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

复制代码/* buffer 中槽的数量 */
#define N 100													

void producer(void){
  
  int item;
  /* buffer 中槽的数量 */
  message m;													
  
  while(TRUE){
    /* 生成放入缓冲区的数据 */
    item = produce_item();						
    /* 等待消费者发送空缓冲区 */
    receive(consumer,&m);							
    /* 建立一个待发送的消息 */
    build_message(&m,item);						
    /* 发送给消费者 */
    send(consumer,&m);								
  }
  
}

void consumer(void){
  
  int item,i;
  message m;
  
  /* 循环N次 */
  for(int i = 0;i < N;i++){						
    /* 发送N个缓冲区 */
    send(producer,&m);								
  }
  while(TRUE){
    /* 接受包含数据的消息 */
    receive(producer,&m);							
    /* 将数据从消息中提取出来 */
  	item = extract_item(&m);					
    /* 将空缓冲区发送回生产者 */
    send(producer,&m);								
    /* 处理数据 */
    consume_item(item);								
  }
  
}

假设所有的消息都有相同的大小，并且在尚未接受到发出的消息时，由操作系统自动进行缓冲。在该解决方案中共使用 N 条消息，这就类似于一块共享内存缓冲区的 N 个槽。消费者首先将 N 条空消息发送给生产者。当生产者向消费者传递一个数据项时，它取走一条空消息并返回一条填充了内容的消息。通过这种方式，系统中总的消息数量保持不变，所以消息都可以存放在事先确定数量的内存中。

如果生产者的速度要比消费者快，则所有的消息最终都将被填满，等待消费者，生产者将被阻塞，等待返回一条空消息。如果消费者速度快，那么情况将正相反：所有的消息均为空，等待生产者来填充，消费者将被阻塞，以等待一条填充过的消息。

消息传递的方式有许多变体，下面先介绍如何对消息进行 编址。

• 一种方法是为每个进程分配一个唯一的地址，让消息按进程的地址编址。
• 另一种方式是引入一个新的数据结构，称为 信箱(mailbox)，信箱是一个用来对一定的数据进行缓冲的数据结构，信箱中消息的设置方法也有多种，典型的方法是在信箱创建时确定消息的数量。在使用信箱时，在 send 和 receive 调用的地址参数就是信箱的地址，而不是进程的地址。当一个进程试图向一个满的信箱发送消息时，它将被挂起，直到信箱中有消息被取走，从而为新的消息腾出地址空间。

屏障

最后一个同步机制是准备用于进程组而不是进程间的生产者-消费者情况的。在某些应用中划分了若干阶段，并且规定，除非所有的进程都就绪准备着手下一个阶段，否则任何进程都不能进入下一个阶段，可以通过在每个阶段的结尾安装一个 屏障(barrier) 来实现这种行为。当一个进程到达屏障时，它会被屏障所拦截，直到所有的屏障都到达为止。屏障可用于一组进程同步，如下图所示

在上图中我们可以看到，有四个进程接近屏障，这意味着每个进程都在进行运算，但是还没有到达每个阶段的结尾。过了一段时间后，A、B、D 三个进程都到达了屏障，各自的进程被挂起，但此时还不能进入下一个阶段呢，因为进程 B 还没有执行完毕。结果，当最后一个 C 到达屏障后，这个进程组才能够进入下一个阶段。

避免锁：读-复制-更新

最快的锁是根本没有锁。问题在于没有锁的情况下，我们是否允许对共享数据结构的并发读写进行访问。答案当然是不可以。假设进程 A 正在对一个数字数组进行排序，而进程 B 正在计算其平均值，而此时你进行 A 的移动，会导致 B 会多次读到重复值，而某些值根本没有遇到过。

然而，在某些情况下，我们可以允许写操作来更新数据结构，即便还有其他的进程正在使用。窍门在于确保每个读操作要么读取旧的版本，要么读取新的版本，例如下面的树

上面的树中，读操作从根部到叶子遍历整个树。加入一个新节点 X 后，为了实现这一操作，我们要让这个节点在树中可见之前使它”恰好正确”：我们对节点 X 中的所有值进行初始化，包括它的子节点指针。然后通过原子写操作，使 X 称为 A 的子节点。所有的读操作都不会读到前后不一致的版本

在上面的图中，我们接着移除 B 和 D。首先，将 A 的左子节点指针指向 C 。所有原本在 A 中的读操作将会后续读到节点 C ，而永远不会读到 B 和 D。也就是说，它们将只会读取到新版数据。同样，所有当前在 B 和 D 中的读操作将继续按照原始的数据结构指针并且读取旧版数据。所有操作均能正确运行，我们不需要锁住任何东西。而不需要锁住数据就能够移除 B 和 D 的主要原因就是 读-复制-更新(Ready-Copy-Update,RCU)，将更新过程中的移除和再分配过程分离开。

调度

当一个计算机是多道程序设计系统时，会频繁的有很多进程或者线程来同时竞争 CPU 时间片。当两个或两个以上的进程/线程处于就绪状态时，就会发生这种情况。如果只有一个 CPU 可用，那么必须选择接下来哪个进程/线程可以运行。操作系统中有一个叫做 调度程序(scheduler) 的角色存在，它就是做这件事儿的，该程序使用的算法叫做 调度算法(scheduling algorithm) 。

尽管有一些不同，但许多适用于进程调度的处理方法同样也适用于线程调度。当内核管理线程的时候，调度通常会以线程级别发生，很少或者根本不会考虑线程属于哪个进程。下面我们会首先专注于进程和线程的调度问题，然后会明确的介绍线程调度以及它产生的问题。

调度介绍

让我们回到早期以磁带上的卡片作为输入的批处理系统的时代，那时候的调度算法非常简单：依次运行磁带上的每一个作业。对于多道程序设计系统，会复杂一些，因为通常会有多个用户在等待服务。一些大型机仍然将 批处理和 分时服务结合使用，需要调度程序决定下一个运行的是一个批处理作业还是终端上的用户。由于在这些机器中 CPU 是稀缺资源，所以好的调度程序可以在提高性能和用户的满意度方面取得很大的成果。

进程行为

几乎所有的进程（磁盘或网络）I/O 请求和计算都是交替运行的

如上图所示，CPU 不停顿的运行一段时间，然后发出一个系统调用等待 I/O 读写文件。完成系统调用后，CPU 又开始计算，直到它需要读更多的数据或者写入更多的数据为止。当一个进程等待外部设备完成工作而被阻塞时，才是 I/O 活动。

上面 a 是 CPU 密集型进程；b 是 I/O 密集型进程进程，a 因为在计算的时间上花费时间更长，因此称为计算密集型(compute-bound) 或者 CPU 密集型(CPU-bound)，b 因为I/O 发生频率比较快因此称为 I/O 密集型(I/O-bound)。计算密集型进程有较长的 CPU 集中使用和较小频度的 I/O 等待。I/O 密集型进程有较短的 CPU 使用时间和较频繁的 I/O 等待。注意到上面两种进程的区分关键在于 CPU 的时间占用而不是 I/O 的时间占用。I/O 密集型的原因是因为它们没有在 I/O 之间花费更多的计算、而不是 I/O 请求时间特别长。无论数据到达后需要花费多少时间，它们都需要花费相同的时间来发出读取磁盘块的硬件请求。

值得注意的是，随着 CPU 的速度越来越快，更多的进程倾向于 I/O 密集型。这种情况出现的原因是 CPU 速度的提升要远远高于硬盘。这种情况导致的结果是，未来对 I/O 密集型进程的调度处理似乎更为重要。这里的基本思想是，如果需要运行 I/O 密集型进程，那么就应该让它尽快得到机会，以便发出磁盘请求并保持磁盘始终忙碌。

何时调度

第一个和调度有关的问题是何时进行调度决策。存在着需要调度处理的各种情形。首先，在创建一个新进程后，需要决定是运行父进程还是子进程。因为二者的进程都处于就绪态下，这是正常的调度决策，可以任意选择，也就是说，调度程序可以任意的选择子进程或父进程开始运行。

第二，在进程退出时需要作出调度决定。因为此进程不再运行（因为它将不再存在），因此必须从就绪进程中选择其他进程运行。如果没有进程处于就绪态，系统提供的空闲进程通常会运行

什么是空闲进程

空闲进程(system-supplied idle process) 是 Microsoft 公司 windows 操作系统带有的系统进程，该进程是在各个处理器上运行的单个线程，它唯一的任务是在系统没有处理其他线程时占用处理器时间。System Idle Process 并不是一个真正的进程，它是核心虚拟出来的，多任务操作系统都存在。在没有可用的进程时，系统处于空运行状态，此时就是System Idle Process 在正在运行。你可以简单的理解成，它代表的是 CPU 的空闲状态，数值越大代表处理器越空闲，可以通过 Windows 任务管理器查看 Windows 中的 CPU 利用率

第三种情况是，当进程阻塞在 I/O 、信号量或其他原因时，必须选择另外一个进程来运行。有时，阻塞的原因会成为选择进程运行的关键因素。例如，如果 A 是一个重要进程，并且它正在等待 B 退出关键区域，让 B 退出关键区域从而使 A 得以运行。但是调度程序一般不会对这种情况进行考量。

第四点，当 I/O 中断发生时，可以做出调度决策。如果中断来自 I/O 设备，而 I/O 设备已经完成了其工作，那么那些等待 I/O 的进程现在可以继续运行。由调度程序来决定是否准备运行新的进程还是重新运行已经中断的进程。

如果硬件时钟以 50 或 60 Hz 或其他频率提供周期性中断，可以在每个时钟中断或第 k 个时钟中断处做出调度决策。根据如何处理时钟中断可以把调度算法可以分为两类。非抢占式(nonpreemptive) 调度算法挑选一个进程，让该进程运行直到被阻塞（阻塞在 I/O 上或等待另一个进程），或者直到该进程自动释放 CPU。即使该进程运行了若干个小时后，它也不会被强制挂起。这样会在时钟中断发生时不会进行调度。在处理完时钟中断后，如果没有更高优先级的进程等待，则被中断的进程会继续执行。

另外一种情况是 抢占式 调度算法，它会选择一个进程，并使其在最大固定时间内运行。如果在时间间隔结束后仍在运行，这个进程会被挂起，调度程序会选择其他进程来运行（前提是存在就绪进程）。进行抢占式调度需要在时间间隔结束时发生时钟中断，以将 CPU 的控制权交还给调度程序。如果没有可用的时钟，那么非抢占式就是唯一的选择。

调度算法的分类

毫无疑问，不同的环境下需要不同的调度算法。之所以出现这种情况，是因为不同的应用程序和不同的操作系统有不同的目标。也就是说，在不同的系统中，调度程序的优化也是不同的。这里有必要划分出三种环境

• 批处理(Batch)
• 交互式(Interactive)
• 实时(Real time)

批处理系统广泛应用于商业领域，比如用来处理工资单、存货清单、账目收入、账目支出、利息计算、索赔处理和其他周期性作业。在批处理系统中，一般会选择使用非抢占式算法或者周期性比较长的抢占式算法。这种方法可以减少线程切换因此能够提升性能。

在交互式用户环境中，为了避免一个进程霸占 CPU 拒绝为其他进程服务，所以需要抢占式算法。即使没有进程有意要一直运行下去，但是，由于某个进程出现错误也有可能无限期的排斥其他所有进程。为了避免这种情况，抢占式也是必须的。服务器也属于此类别，因为它们通常为多个（远程）用户提供服务，而这些用户都非常着急。计算机用户总是很忙。

在实时系统中，抢占有时是不需要的，因为进程知道自己可能运行不了很长时间，通常很快的做完自己的工作并阻塞。实时系统与交互式系统的差别是，实时系统只运行那些用来推进现有应用的程序，而交互式系统是通用的，它可以运行任意的非协作甚至是有恶意的程序。

调度算法的目标

为了设计调度算法，有必要考虑一下什么是好的调度算法。有一些目标取决于环境（批处理、交互式或者实时）蛋大部分是适用于所有情况的，下面是一些需要考量的因素，我们会在下面一起讨论。

所有系统

在所有的情况中，公平是很重要的。对一个进程给予相较于其他等价的进程更多的 CPU 时间片对其他进程来说是不公平的。当然，不同类型的进程可以采用不同的处理方式。

与公平有关的是系统的强制执行，什么意思呢？如果某公司的薪资发放系统计划在本月的15号，那么碰上了疫情大家生活都很拮据，此时老板说要在14号晚上发放薪资，那么调度程序必须强制使进程执行 14 号晚上发放薪资的策略。

另一个共同的目标是保持系统的所有部分尽可能的忙碌。如果 CPU 和所有的 I/O 设备能够一直运行，那么相对于让某些部件空转而言，每秒钟就可以完成更多的工作。例如，在批处理系统中，调度程序控制哪个作业调入内存运行。在内存中既有一些 CPU 密集型进程又有一些 I/O 密集型进程是一个比较好的想法，好于先调入和运行所有的 CPU 密集型作业，然后在它们完成之后再调入和运行所有 I/O 密集型作业的做法。使用后者这种方式会在 CPU 密集型进程启动后，争夺 CPU ，而磁盘却在空转，而当 I/O 密集型进程启动后，它们又要为磁盘而竞争，CPU 却又在空转。。。。。。显然，通过结合 I/O 密集型和 CPU 密集型，能够使整个系统运行更流畅，效率更高。

批处理系统

通常有三个指标来衡量系统工作状态：吞吐量、周转时间和 CPU 利用率，吞吐量(throughout) 是系统每小时完成的作业数量。综合考虑，每小时完成 50 个工作要比每小时完成 40 个工作好。周转时间(Turnaround time) 是一种平均时间，它指的是从一个批处理提交开始直到作业完成时刻为止平均时间。该数据度量了用户要得到输出所需的平均等待时间。周转时间越小越好。

CPU 利用率(CPU utilization) 通常作为批处理系统上的指标。即使如此， CPU 利用率也不是一个好的度量指标，真正有价值的衡量指标是系统每小时可以完成多少作业（吞吐量），以及完成作业需要多长时间（周转时间）。把 CPU 利用率作为度量指标，就像是引擎每小时转动了多少次来比较汽车的性能一样。而且知道 CPU 的利用率什么时候接近 100% 要比什么什么时候要求得到更多的计算能力要有用。

交互式系统

对于交互式系统，则有不同的指标。最重要的是尽量减少响应时间。这个时间说的是从执行指令开始到得到结果的时间。再有后台进程运行（例如，从网络上读取和保存 E-mail 文件）的个人计算机上，用户请求启动一个程序或打开一个文件应该优先于后台的工作。能够让所有的交互式请求首先运行的就是一个好的服务。

一个相关的问题是 均衡性(proportionality)，用户对做一件事情需要多长时间总是有一种固定（不过通常不正确）的看法。当认为一个请求很复杂需要较多时间时，用户会认为很正常并且可以接受，但是一个很简单的程序却花费了很长的运行时间，用户就会很恼怒。可以拿彩印和复印来举出一个简单的例子，彩印可能需要1分钟的时间，但是用户觉得复杂并且愿意等待一分钟，相反，复印很简单只需要 5 秒钟，但是复印机花费 1 分钟却没有完成复印操作，用户就会很焦躁。

实时系统

实时系统则有着和交互式系统不同的考量因素，因此也就有不同的调度目标。实时系统的特点是必须满足最后的截止时间。例如，如果计算机控制着以固定速率产生数据的设备，未能按时运行的话可能会导致数据丢失。因此，实时系统中最重要的需求是满足所有（或大多数）时间期限。

在一些实事系统中，特别是涉及到多媒体的，可预测性很重要。偶尔不能满足最后的截止时间不重要，但是如果音频多媒体运行不稳定，声音质量会持续恶化。视频也会造成问题，但是耳朵要比眼睛敏感很多。为了避免这些问题，进程调度必须能够高度可预测的而且是有规律的。

批处理中的调度

现在让我们把目光从一般性的调度转换为特定的调度算法。下面我们会探讨在批处理中的调度。

先来先服务

很像是先到先得。。。可能最简单的非抢占式调度算法的设计就是 先来先服务(first-come,first-serverd)。使用此算法，将按照请求顺序为进程分配 CPU。最基本的，会有一个就绪进程的等待队列。当第一个任务从外部进入系统时，将会立即启动并允许运行任意长的时间。它不会因为运行时间太长而中断。当其他作业进入时，它们排到就绪队列尾部。当正在运行的进程阻塞，处于等待队列的第一个进程就开始运行。当一个阻塞的进程重新处于就绪态时，它会像一个新到达的任务，会排在队列的末尾，即排在所有进程最后。

这个算法的强大之处在于易于理解和编程，在这个算法中，一个单链表记录了所有就绪进程。要选取一个进程运行，只要从该队列的头部移走一个进程即可；要添加一个新的作业或者阻塞一个进程，只要把这个作业或进程附加在队列的末尾即可。这是很简单的一种实现。

不过，先来先服务也是有缺点的，那就是没有优先级的关系，试想一下，如果有 100 个 I/O 进程正在排队，第 101 个是一个 CPU 密集型进程，那岂不是需要等 100 个 I/O 进程运行完毕才会等到一个 CPU 密集型进程运行，这在实际情况下根本不可能，所以需要优先级或者抢占式进程的出现来优先选择重要的进程运行。

最短作业优先

批处理中，第二种调度算法是 最短作业优先(Shortest Job First)，我们假设运行时间已知。例如，一家保险公司，因为每天要做类似的工作，所以人们可以相当精确地预测处理 1000 个索赔的一批作业需要多长时间。当输入队列中有若干个同等重要的作业被启动时，调度程序应使用最短优先作业算法

如上图 a 所示，这里有 4 个作业 A、B、C、D ，运行时间分别为 8、4、4、4 分钟。若按图中的次序运行，则 A 的周转时间为 8 分钟，B 为 12 分钟，C 为 16 分钟，D 为 20 分钟，平均时间内为 14 分钟。

现在考虑使用最短作业优先算法运行 4 个作业，如上图 b 所示，目前的周转时间分别为 4、8、12、20，平均为 11 分钟，可以证明最短作业优先是最优的。考虑有 4 个作业的情况，其运行时间分别为 a、b、c、d。第一个作业在时间 a 结束，第二个在时间 a + b 结束，以此类推。平均周转时间为 (4a + 3b + 2c + d) / 4 。显然 a 对平均值的影响最大，所以 a 应该是最短优先作业，其次是 b，然后是 c ，最后是 d 它就只能影响自己的周转时间了。

需要注意的是，在所有的进程都可以运行的情况下，最短作业优先的算法才是最优的。

最短剩余时间优先

最短作业优先的抢占式版本被称作为 最短剩余时间优先(Shortest Remaining Time Next) 算法。使用这个算法，调度程序总是选择剩余运行时间最短的那个进程运行。当一个新作业到达时，其整个时间同当前进程的剩余时间做比较。如果新的进程比当前运行进程需要更少的时间，当前进程就被挂起，而运行新的进程。这种方式能够使短期作业获得良好的服务。

交互式系统中的调度

交互式系统中在个人计算机、服务器和其他系统中都是很常用的，所以有必要来探讨一下交互式调度

轮询调度

一种最古老、最简单、最公平并且最广泛使用的算法就是 轮询算法(round-robin)。每个进程都会被分配一个时间段，称为时间片(quantum)，在这个时间片内允许进程运行。如果时间片结束时进程还在运行的话，则抢占一个 CPU 并将其分配给另一个进程。如果进程在时间片结束前阻塞或结束，则 CPU 立即进行切换。轮询算法比较容易实现。调度程序所做的就是维护一个可运行进程的列表，就像下图中的 a，当一个进程用完时间片后就被移到队列的末尾，就像下图的 b。

时间片轮询调度中唯一有意思的一点就是时间片的长度。从一个进程切换到另一个进程需要一定的时间进行管理处理，包括保存寄存器的值和内存映射、更新不同的表格和列表、清除和重新调入内存高速缓存等。这种切换称作 进程间切换(process switch) 和 上下文切换(context switch)。如果进程间的切换时间需要 1ms，其中包括内存映射、清除和重新调入高速缓存等，再假设时间片设为 4 ms，那么 CPU 在做完 4 ms 有用的工作之后，CPU 将花费 1 ms 来进行进程间的切换。因此，CPU 的时间片会浪费 20% 的时间在管理开销上。耗费巨大。

为了提高 CPU 的效率，我们把时间片设置为 100 ms。现在时间的浪费只有 1%。但是考虑会发现下面的情况，如果在一个非常短的时间内到达 50 个请求，并且对 CPU 有不同的需求，此时会发生什么？50 个进程都被放在可运行进程列表中。如果 CP画U 是空闲的，第一个进程会立即开始执行，第二个直到 100 ms 以后才会启动，以此类推。不幸的是最后一个进程需要等待 5 秒才能获得执行机会。大部分用户都会觉得对于一个简短的指令运行 5 秒中是很慢的。如果队列末尾的某些请求只需要几号秒钟的运行时间的话，这种设计就非常糟糕了。

另外一个因素是如果时间片设置长度要大于 CPU 使用长度，那么抢占就不会经常发生。相反，在时间片用完之前，大多数进程都已经阻塞了，那么就会引起进程间的切换。消除抢占可提高性能，因为进程切换仅在逻辑上必要时才发生，即流程阻塞且无法继续时才发生。

结论可以表述如下：将上下文切换时间设置得太短会导致过多的进程切换并降低 CPU 效率，但设置时间太长会导致一个短请求很长时间得不到响应。最好的切换时间是在 20 - 50 毫秒之间设置。

优先级调度

轮询调度假设了所有的进程是同等重要的。但事实情况可能不是这样。例如，在一所大学中的等级制度，首先是院长，然后是教授、秘书、后勤人员，最后是学生。这种将外部情况考虑在内就实现了优先级调度(priority scheduling)

它的基本思想很明确，每个进程都被赋予一个优先级，优先级高的进程优先运行。

但是也不意味着高优先级的进程能够永远一直运行下去，调度程序会在每个时钟中断期间降低当前运行进程的优先级。如果此操作导致其优先级降低到下一个最高进程的优先级以下，则会发生进程切换。或者，可以为每个进程分配允许运行的最大时间间隔。当时间间隔用完后，下一个高优先级的进程会得到运行的机会。

可以静态或者动态的为进程分配优先级。在一台军用计算机上，可以把将军所启动的进程设为优先级 100，上校为 90 ，少校为 80，上尉为 70，中尉为 60，以此类推。UNIX 中有一条命令为 nice ，它允许用户为了照顾他人而自愿降低自己进程的优先级，但是一般没人用。

优先级也可以由系统动态分配，用于实现某种目的。例如，有些进程为 I/O 密集型，其多数时间用来等待 I/O 结束。当这样的进程需要 CPU 时，应立即分配 CPU，用来启动下一个 I/O 请求，这样就可以在另一个进程进行计算的同时执行 I/O 操作。这类 I/O 密集型进程长时间的等待 CPU 只会造成它长时间占用内存。使 I/O 密集型进程获得较好的服务的一种简单算法是，将其优先级设为 1/f，f 为该进程在上一时间片中所占的部分。一个在 50 ms 的时间片中只使用 1 ms 的进程将获得优先级 50 ，而在阻塞之前用掉 25 ms 的进程将具有优先级 2，而使用掉全部时间片的进程将得到优先级 1。

可以很方便的将一组进程按优先级分成若干类，并且在各个类之间采用优先级调度，而在各类进程的内部采用轮转调度。下面展示了一个四个优先级类的系统

它的调度算法主要描述如下：上面存在优先级为 4 类的可运行进程，首先会按照轮转法为每个进程运行一个时间片，此时不理会较低优先级的进程。若第 4 类进程为空，则按照轮询的方式运行第三类进程。若第 4 类和第 3 类进程都为空，则按照轮转法运行第 2 类进程。如果不对优先级进行调整，则低优先级的进程很容易产生饥饿现象。

多级队列

最早使用优先级调度的系统是 CTSS(Compatible TimeSharing System)。CTSS 是一种兼容分时系统，它有一个问题就是进程切换太慢，其原因是 IBM 7094 内存只能放进一个进程。

IBM 是哥伦比亚大学计算机中心在 1964 - 1968 年的计算机

CTSS 在每次切换前都需要将当前进程换出到磁盘，并从磁盘上读入一个新进程。CTSS 的设计者很快就认识到，为 CPU 密集型进程设置较长的时间片比频繁地分给他们很短的时间要更有效（减少交换次数）。另一方面，如前所述，长时间片的进程又会影响到响应时间，解决办法是设置优先级类。属于最高优先级的进程运行一个时间片，次高优先级进程运行 2 个时间片，再下面一级运行 4 个时间片，以此类推。当一个进程用完分配的时间片后，它被移到下一类。

最短进程优先

对于批处理系统而言，由于最短作业优先常常伴随着最短响应时间，所以如果能够把它用于交互式进程，那将是非常好的。在某种程度上，的确可以做到这一点。交互式进程通常遵循下列模式：等待命令、执行命令、等待命令、执行命令。。。如果我们把每个命令的执行都看作一个分离的作业，那么我们可以通过首先运行最短的作业来使响应时间最短。这里唯一的问题是如何从当前可运行进程中找出最短的那一个进程。

一种方式是根据进程过去的行为进行推测，并执行估计运行时间最短的那一个。假设每个终端上每条命令的预估运行时间为 T0，现在假设测量到其下一次运行时间为 T1，可以用两个值的加权来改进估计时间，即aT0+ (1- 1)T1。通过选择 a 的值，可以决定是尽快忘掉老的运行时间，还是在一段长时间内始终记住它们。当 a = 1/2 时，可以得到下面这个序列

可以看到，在三轮过后，T0 在新的估计值中所占比重下降至 1/8。

有时把这种通过当前测量值和先前估计值进行加权平均从而得到下一个估计值的技术称作 老化(aging)。这种方法会使用很多预测值基于当前值的情况。

保证调度

一种完全不同的调度方法是对用户做出明确的性能保证。一种实际而且容易实现的保证是：若用户工作时有 n 个用户登录，则每个用户将获得 CPU 处理能力的 1/n。类似地，在一个有 n 个进程运行的单用户系统中，若所有的进程都等价，则每个进程将获得 1/n 的 CPU 时间。

彩票调度

对用户进行承诺并在随后兑现承诺是一件好事，不过很难实现。但是存在着一种简单的方式，有一种既可以给出预测结果而又有一种比较简单的实现方式的算法，就是 彩票调度(lottery scheduling)算法。

其基本思想是为进程提供各种系统资源（例如 CPU 时间）的彩票。当做出一个调度决策的时候，就随机抽出一张彩票，拥有彩票的进程将获得该资源。在应用到 CPU 调度时，系统可以每秒持有 50 次抽奖，每个中奖者将获得比如 20 毫秒的 CPU 时间作为奖励。

George Orwell 关于 所有的进程是平等的，但是某些进程能够更平等一些。一些重要的进程可以给它们额外的彩票，以便增加他们赢得的机会。如果出售了 100 张彩票，而且有一个进程持有了它们中的 20 张，它就会有 20% 的机会去赢得彩票中奖。在长时间的运行中，它就会获得 20% 的CPU。相反，对于优先级调度程序，很难说明拥有优先级 40 究竟是什么意思，这里的规则很清楚，拥有彩票 f 份额的进程大约得到系统资源的 f 份额。

如果希望进程之间协作的话可以交换它们之间的票据。例如，客户端进程给服务器进程发送了一条消息后阻塞，客户端进程可能会把自己所有的票据都交给服务器，来增加下一次服务器运行的机会。当服务完成后，它会把彩票还给客户端让其有机会再次运行。事实上，如果没有客户机，服务器也根本不需要彩票。

可以把彩票理解为 buff，这个 buff 有 15% 的几率能让你产生 速度之靴 的效果。

公平分享调度

到目前为止，我们假设被调度的都是各个进程自身，而不用考虑该进程的拥有者是谁。结果是，如果用户 1 启动了 9 个进程，而用户 2 启动了一个进程，使用轮转或相同优先级调度算法，那么用户 1 将得到 90 % 的 CPU 时间，而用户 2 将之得到 10 % 的 CPU 时间。

为了阻止这种情况的出现，一些系统在调度前会把进程的拥有者考虑在内。在这种模型下，每个用户都会分配一些CPU 时间，而调度程序会选择进程并强制执行。因此如果两个用户每个都会有 50% 的 CPU 时间片保证，那么无论一个用户有多少个进程，都将获得相同的 CPU 份额。

实时系统中的调度

实时系统(real-time) 是一个时间扮演了重要作用的系统。典型的，一种或多种外部物理设备发给计算机一个服务请求，而计算机必须在一个确定的时间范围内恰当的做出反应。例如，在 CD 播放器中的计算机会获得从驱动器过来的位流，然后必须在非常短的时间内将位流转换为音乐播放出来。如果计算时间过长，那么音乐就会听起来有异常。再比如说医院特别护理部门的病人监护装置、飞机中的自动驾驶系统、列车中的烟雾警告装置等，在这些例子中，正确但是却缓慢的响应要比没有响应甚至还糟糕。

实时系统可以分为两类，硬实时(hard real time) 和 软实时(soft real time) 系统，前者意味着必须要满足绝对的截止时间；后者的含义是虽然不希望偶尔错失截止时间，但是可以容忍。在这两种情形中，实时都是通过把程序划分为一组进程而实现的，其中每个进程的行为是可预测和提前可知的。这些进程一般寿命较短，并且极快的运行完成。在检测到一个外部信号时，调度程序的任务就是按照满足所有截止时间的要求调度进程。

实时系统中的事件可以按照响应方式进一步分类为周期性(以规则的时间间隔发生)事件或 非周期性(发生时间不可预知)事件。一个系统可能要响应多个周期性事件流，根据每个事件处理所需的时间，可能甚至无法处理所有事件。例如，如果有 m 个周期事件，事件 i 以周期 Pi 发生，并需要 Ci 秒 CPU 时间处理一个事件，那么可以处理负载的条件是

只有满足这个条件的实时系统称为可调度的，这意味着它实际上能够被实现。一个不满足此检验标准的进程不能被调度，因为这些进程共同需要的 CPU 时间总和大于 CPU 能提供的时间。

举一个例子，考虑一个有三个周期性事件的软实时系统，其周期分别是 100 ms、200 m 和 500 ms。如果这些事件分别需要 50 ms、30 ms 和 100 ms 的 CPU 时间，那么该系统时可调度的，因为 0.5 + 0.15 + 0.2 < 1。如果此时有第四个事件加入，其周期为 1 秒，那么此时这个事件如果不超过 150 ms，那么仍然是可以调度的。忽略上下文切换的时间。

实时系统的调度算法可以是静态的或动态的。前者在系统开始运行之前做出调度决策；后者在运行过程中进行调度决策。只有在可以提前掌握所完成的工作以及必须满足的截止时间等信息时，静态调度才能工作，而动态调度不需要这些限制。

调度策略和机制

到目前为止，我们隐含的假设系统中所有进程属于不同的分组用户并且进程间存在相互竞争 CPU 的情况。通常情况下确实如此，但有时也会发生一个进程会有很多子进程并在其控制下运行的情况。例如，一个数据库管理系统进程会有很多子进程。每一个子进程可能处理不同的请求，或者每个子进程实现不同的功能（如请求分析、磁盘访问等）。主进程完全可能掌握哪一个子进程最重要（或最紧迫），而哪一个最不重要。但是，以上讨论的调度算法中没有一个算法从用户进程接收有关的调度决策信息，这就导致了调度程序很少能够做出最优的选择。

解决问题的办法是将 调度机制(scheduling mechanism) 和 调度策略(scheduling policy) 分开，这是长期一贯的原则。这也就意味着调度算法在某种方式下被参数化了，但是参数可以被用户进程填写。让我们首先考虑数据库的例子。假设内核使用优先级调度算法，并提供了一条可供进程设置优先级的系统调用。这样，尽管父进程本身并不参与调度，但它可以控制如何调度子进程的细节。调度机制位于内核，而调度策略由用户进程决定，调度策略和机制分离是一种关键性思路。

线程调度

当若干进程都有多个线程时，就存在两个层次的并行：进程和线程。在这样的系统中调度处理有本质的差别，这取决于所支持的是用户级线程还是内核级线程（或两者都支持）。

首先考虑用户级线程，由于内核并不知道有线程存在，所以内核还是和以前一样地操作，选取一个进程，假设为 A，并给予 A 以时间片控制。A 中的线程调度程序决定哪个线程运行。假设为 A1。由于多道线程并不存在时钟中断，所以这个线程可以按其意愿任意运行多长时间。如果该线程用完了进程的全部时间片，内核就会选择另一个进程继续运行。

在进程 A 终于又一次运行时，线程 A1 会接着运行。该线程会继续耗费 A 进程的所有时间，直到它完成工作。不过，线程运行不会影响到其他进程。其他进程会得到调度程序所分配的合适份额，不会考虑进程 A 内部发生的事情。

现在考虑 A 线程每次 CPU 计算的工作比较少的情况，例如：在 50 ms 的时间片中有 5 ms 的计算工作。于是，每个线程运行一会儿，然后把 CPU 交回给线程调度程序。这样在内核切换到进程 B 之前，就会有序列 A1,A2,A3,A1,A2,A3,A1,A2,A3,A1 。 如下所示

运行时系统使用的调度算法可以是上面介绍算法的任意一种。从实用方面考虑，轮转调度和优先级调度更为常用。唯一的局限是，缺乏一个时钟中断运行过长的线程。但由于线程之间的合作关系，这通常也不是问题。

现在考虑使用内核线程的情况，内核选择一个特定的线程运行。它不用考虑线程属于哪个进程，不过如果有必要的话，也可以这么做。对被选择的线程赋予一个时间片，而且如果超过了时间片，就会强制挂起该线程。一个线程在 50 ms 的时间片内，5 ms 之后被阻塞，在 30 ms 的时间片中，线程的顺序会是 A1,B1,A2,B2,A3,B3。如下图所示

用户级线程和内核级线程之间的主要差别在于性能。用户级线程的切换需要少量的机器指令（想象一下Java程序的线程切换），而内核线程需要完整的上下文切换，修改内存映像，使高速缓存失效，这会导致了若干数量级的延迟。另一方面，在使用内核级线程时，一旦线程阻塞在 I/O 上就不需要在用户级线程中那样将整个进程挂起。

从进程 A 的一个线程切换到进程 B 的一个线程，其消耗要远高于运行进程 A 的两个线程（涉及修改内存映像，修改高速缓存），内核对这种切换的消耗是了解到，可以通过这些信息作出决定。

文章参考：

《现代操作系统》

《Modern Operating System》forth edition

www.encyclopedia.com/computing/n…

j00ru.vexillium.org/syscalls/nt…

www.bottomupcs.com/process_hie…

en.wikipedia.org/wiki/Runtim…

en.wikipedia.org/wiki/Execut…

zhidao.baidu.com/question/11…

baike.baidu.com/item/等待队列/9…

www.columbia.edu/cu/computin…

baike.baidu.com/item/中断向量/4…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

前言

只有光头才能变强。

文本已收录至我的GitHub精选文章，欢迎Star：github.com/ZhongFuChen…

上一篇已经讲解了「大数据入门」的相关基础概念和知识了，这篇我们来学学HDFS。如果文章有错误的地方，不妨在评论区友善指出~

一、HDFS介绍

上篇文章已经讲到了，随着数据量越来越大，在一台机器上已经无法存储所有的数据了，那我们会将这些数据分配到不同的机器来进行存储，但是这就带来一个问题：不方便管理和维护

所以，我们就希望有一个系统可以将这些分布在不同操作服务器上的数据进行统一管理，这就有了分布式文件系统

• HDFS是分布式文件系统的其中一种（目前用得最广泛的一种）

在使用HDFS的时候是非常简单的：虽然HDFS是将文件存储到不同的机器上，但是我去使用的时候是把这些文件当做是存储在一台机器的方式去使用（背后却是多台机器在执行）：

• 好比：我调用了一个RPC接口，我给他参数，他返回一个response给我。RPC接口做了什么事其实我都不知道的（可能这个RPC接口又调了其他的RPC接口）—–屏蔽掉实现细节，对用户友好

明确一下：HDFS就是一个分布式文件系统，一个文件系统，我们用它来做什么？存数据呀。

下面，我们来了解一下HDFS的一些知识，能够帮我们更好地去「使用」HDFS

二、HDFS学习

从上面我们已经提到了，HDFS作为一个分布式文件系统，那么它的数据是保存在多个系统上的。例如，下面的图：一个1GB的文件，会被切分成几个小的文件，每个服务器都会存放一部分。

那肯定会有人会问：那会切分多少个小文件呢？默认以128MB的大小来切分，每个128MB的文件，在HDFS叫做块(block)

显然，这个128MB大小是可配的。如果设置为太小或者太大都不好。如果切分的文件太小，那一份数据可能分布到多台的机器上（寻址时间就很慢）。如果切分的文件太大，那数据传输时间的时间就很慢。

PS：老版本默认是64MB

一个用户发出了一个1GB的文件请求给HDFS客户端，HDFS客户端会根据配置(现在默认是128MB)，对这个文件进行切分，所以HDFS客户端会切分为8个文件(也叫做block)，然后每个服务器都会存储这些切分后的文件(block)。现在我们假设每个服务器都存储两份。

这些存放真实数据的服务器，在HDFS领域叫做DataNode

现在问题来了，HDFS客户端按照配置切分完以后，怎么知道往哪个服务器（DataNode）放数据呢？这个时候，就需要另一个角色了，管理者（NameNode）。

NameNode实际上就是管理文件的各种信息（这种信息专业点我们叫做MetaData「元数据」），其中包括：文文件路径名，每个Block的ID和存放的位置等等。

所以，无论是读还是写，HDFS客户端都会先去找NameNode，通过NameNode得知相应的信息，再去找DataNode

• 如果是写操作，HDFS切分完文件以后，会询问NameNode应该将这些切分好的block往哪几台DataNode上写。
• 如果是读操作，HDFS拿到文件名，也会去询问NameNode应该往哪几台DataNode上读数据。

2.1 HDFS备份

作为一个分布式系统（把大文件切分为多个小文件，存储到不同的机器上），如果没有备份的话，只要有其中的一台机器挂了，那就会导致「数据」是不可用状态的。

写到这里，如果看过我的Kafka和ElasticSearch的文章可能就懂了。其实思想都是一样的。

Kafka对partition备份，ElasticSearch对分片进行备份，而到HDFS就是对Block进行备份。

尽可能将数据备份到不同的机器上，即便某台机器挂了，那就可以将备份数据拉出来用。

对Kafka和ElasticSearch不了解的同学，可以关注我的GitHub，搜索关键字即可查询（我觉得还算写得比较通俗易懂的）

**注：**这里的备份并不需要HDFS客户端去写，只要DataNode之间互相传递数据就好了。

2.2 NameNode的一些事

从上面我们可以看到，NameNode是需要处理hdfs客户端请求的。（因为它是存储元数据的地方，无论读写都需要经过它）。

现在问题就来了，NameNode是怎么存放元数据的呢？

• 如果NameNode只是把元数据放到内存中，那如果NameNode这台机器重启了，那元数据就没了。
• 如果NameNode将每次写入的数据都存储到硬盘中，那如果只针对磁盘查找和修改又会很慢（因为这个是纯IO的操作）

说到这里，又想起了Kafka。Kafka也是将partition写到磁盘里边的，但人家是怎么写的？顺序IO

NameNode同样也是做了这个事：修改内存中的元数据，然后把修改的信息append（追加）到一个名为editlog的文件上。

由于append是顺序IO，所以效率也不会低。现在我们增删改查都是走内存，只不过增删改的时候往磁盘文件editlog里边追加一条。这样我们即便重启了NameNode，还是可以通过editlog文件将元数据恢复。

现在也有个问题：如果NameNode一直长期运行的话，那editlog文件应该会越来越大（因为所有的修改元数据信息都需要在这追加一条）。重启的时候需要依赖editlog文件来恢复数据，如果文件特别大，那启动的时候不就特别慢了吗？

的确是如此的，那HDFS是怎么做的呢？为了防止editlog过大，导致在重启的时候需要较长的时间恢复数据，所以NameNode会有一个内存快照，叫做fsimage

说到快照，有没有想起Redis的RDB!!

这样一来，重启的时候只需要加载内存快照fsimage+部分的editlog就可以了。

想法很美好，现实还需要解决一些事：我什么时候生成一个内存快照fsimage？我怎么知道加载哪一部分的editlog？

问题看起来好像复杂，其实我们就只需要一个定时任务。

如果让我自己做的话，我可能会想：我们加一份配置，设置个时间就OK了

• 如果editlog大到什么程度或者隔了多长时间，我们就把editlog文件的数据跟内存快照fsiamge给合并起来。然后生成一个新的fsimage，把editlog给清空，覆盖旧的fsimage内存快照
• 这样一来，NameNode每次重启的时候，拿到的都是最新的fsimage文件，editlog里边的都是没合并到fsimage的。根据这两个文件就可以恢复最新的元数据信息了。

HDFS也是类似上面这样干的，只不过它不是在NameNode起个定时的任务跑，而是用了一个新的角色：SecondNameNode。至于为什么？可能HDFS觉得合并所耗费的资源太大了，不同的工作交由不同的服务器来完成，也符合分布式的理念。

现在问题还是来了，此时的架构NameNode是单机的。SecondNameNode的作用只是给NameNode合并editlog和fsimage文件，如果NameNode挂了，那client就请求不到了，而所有的请求都需要走NameNode，这导致整个HDFS集群都不可用了。

于是我们需要保证NameNode是高可用的。一般现在我们会通过Zookeeper来实现。架构图如下：

主NameNode和从NameNode需要保持元数据的信息一致（因为如果主NameNode挂了，那从NameNode需要顶上，这时从NameNode需要有主NameNode的信息）。

所以，引入了Shared Edits来实现主从NameNode之间的同步，Shared Edits也叫做JournalNode。实际上就是主NameNode如果有更新元数据的信息，它的editlog会写到JournalNode，然后从NameNode会在JournalNode读取到变化信息，然后同步。从NameNode也实现了上面所说的SecondNameNode功能（合并editlog和fsimage）

稍微总结一下：

• NameNode需要处理client请求，它是存储元数据的地方
• NameNode的元数据操作都在内存中，会把增删改以editlog持续化到硬盘中（因为是顺序io，所以不会太慢）
• 由于editlog可能存在过大的问题，导致重新启动NameNode过慢（因为要依赖editlog来恢复数据），引出了fsimage内存快照。需要跑一个定时任务来合并fsimage和editlog，引出了SecondNameNode
• 又因为NameNode是单机的，可能存在单机故障的问题。所以我们可以通过Zookeeper来维护主从NameNode，通过JournalNode(Share Edits)来实现主从NameNode元数据的一致性。最终实现NameNode的高可用。

2.3 学点DataNode

从上面我们就知道，我们的数据是存放在DataNode上的（还会备份）。

如果某个DataNode掉线了，那HDFS是怎么知道的呢？

DataNode启动的时候会去NameNode上注册，他俩会维持心跳，如果超过时间阈值没有收到DataNode的心跳，那HDFS就认为这个DataNode挂了。

还有一个问题就是：我们将Block存到DataNode上，那还是有可能这个DataNode的磁盘损坏了部分，而我们DataNode没有下线，但我们也不知道损坏了。

一个Block除了存放数据的本身，还会存放一份元数据（包括数据块的长度，块数据的校验和，以及时间戳）。DataNode还是会定期向NameNode上报所有当前所有Block的信息，通过元数据就可校验当前的Block是不是正常状态。

最后

其实在学习HDFS的时候，你会发现很多的思想跟之前学过的都类似。就比如提到的Kafka、Elasticsearch这些常用的分布式组件。

如果对Kafka、Elasticsearch、Zookeeper、Redis等不了解的同学，可以在我的GitHub或公众号里边找对应的文章哦~我觉得还算写得通俗易懂的。

改天整合一下这些框架的持久化特点，再写一篇（因为可以发现，他们的持久化机制都十分类似）

下一篇无意外的话，会写写MapReduce，感谢你看到这里。

参考资料：

• HDFS漫画
• 《从零开始学大数据 -李智慧》

如果大家想要实时关注我更新的文章以及分享的干货的话，可以关注我的公众号「Java3y」。

• 🔥Java精美脑图
• 🔥Java学习路线
• 🔥开发常用工具

在公众号下回复「888」即可获取！！

本已收录至我的GitHub精选文章，欢迎Star：github.com/ZhongFuChen…

求点赞 求关注️ 求分享👥 求留言💬 对我来说真的 非常有用！！！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

原文链接

能坚持别人不能坚持的，才能拥有别人不能拥有的。
关注编程大道公众号，让我们一同坚持心中所想，一起成长！！

《【面试突击】— Redis篇》– Redis的线程模型了解吗？为啥单线程效率还这么高？

在这个系列里，我整理了一些面试题与大家分享，帮助想要在金三银四准备跳槽的同学。
巩固、突击面试官常问的一些面试题，加油！！

1、面试题

Redis和Memcached有什么区别？

Redis的线程模型是什么？

为什么Redis是单线程的但是还可以支撑高并发？

2、面试官心理分析

问这个的时候就是问你Redis的原理了，看你是不是思考过，研究过。Redis最基本的一个内部原理和特点，就是Redis实际上是个单线程工作模型。你要是连这个都不知道，那后面在使用Redis的时候，如果出了问题岂不是什么都不知道，无从下手？

还有可能面试官会问问你Redis和Memcached的区别。不过说实话，近几年，面试官都不太喜欢这么问了。因为memcached是早些年各大互联网公司常用的缓存方案，但是现在近几年基本都是Redis，没什么公司用memcached了。

3、温馨提醒

如果你要是现在还不知道redis和memcached是啥，那你赶紧百度一下redis入门和memcahced入门，找两篇博客教程什么的简单启动一下，然后试一下几个简单操作，先感受一下，跟博客、教程做个demo程序，一小时以内就搞定了，就能初步了解和入门了。然后接着回来继续看。

另外一个友情提示，要弄明白redis的线程模型的话，前提是你需要了解socket网络相关的基本知识。如果你socket都不了解的话那我觉得你java没学好吧。初学者都该学习java的socket网络通信相关知识的。

4、面试题剖析

（1）redis和memcached有啥区别

这个问题，其实可以比较出很多区别，但是这里还是采取redis作者给出的几个来进行比较吧，毕竟面试不是背博客，不是说的越多越好，你只要答出来关键的那几点其实就可以了。但是并不是说除了这里列出来的几个你就不需要知道别的了，你可以说：要说二者的区别其实还挺多的，这里我就挑几个最典型的说吧。

1）Redis支持服务器端的数据操作
Redis相比Memcached来说，拥有更多的数据结构和并支持更丰富的数据操作，通常在Memcached里，你需要将数据拿到客户端来进行类似的修改再set回去。这大大增加了网络IO的次数和数据体积。在Redis中，这些复杂的操作通常和一般的GET/SET一样高效。所以，如果需要缓存能够支持更复杂的结构和操作，那么Redis会是不错的选择。

2）内存使用效率对比
使用简单的key-value存储的话，Memcached的内存利用率更高，而如果Redis采用hash结构来做key-value存储，由于其组合式的压缩，其内存利用率会高于Memcached。

3）性能对比
由于Redis只使用单核，而Memcached可以使用多核，所以平均每一个核上Redis在存储小数据时比Memcached性能更高。而在100k以上的数据中，Memcached性能要高于Redis，虽然Redis最近也在存储大数据的性能上进行优化，但是比起Memcached，还是稍有逊色。

4）集群模式
memcached没有原生的集群模式，需要依靠客户端来实现往集群中分片写入数据；但是redis目前是原生支持cluster模式的，redis官方就是支持redis cluster集群模式的，比memcached来说要更好。

其实第2、3个说不说都可以，关键是1和4。

（2）redis的线程模型

问这个原理性的问题，其实你可以结合着图来给面试官讲这个问题，边画图边讲最有说服力，面试官在心里会给你默默地竖起大拇指。

1）文件事件处理器

Redis基于Reactor模式开发了网络事件处理器，这个处理器叫做文件事件处理器 file event handler。这个文件事件处理器，它是单线程的，所以 Redis 才叫做单线程的模型，它采用IO多路复用机制来同时监听多个Socket，根据Socket上的事件类型来选择对应的事件处理器来处理这个事件。

如果被监听的 Socket 准备好执行accept、read、write、close等操作的时候，跟操作对应的文件事件就会产生，这个时候文件事件处理器就会调用之前关联好的事件处理器来处理这个事件。

文件事件处理器是单线程模式运行的，但是通过IO多路复用机制监听多个Socket，可以实现高性能的网络通信模型，又可以跟内部其他单线程的模块进行对接，保证了 Redis 内部的线程模型的简单性。

文件事件处理器的结构包含4个部分：多个Socket、IO多路复用程序、文件事件分派器以及事件处理器（命令请求处理器、命令回复处理器、连接应答处理器等）。

多个 Socket 可能并发的产生不同的操作，每个操作对应不同的文件事件，但是IO多路复用程序会监听多个 Socket，会将 Socket 放入一个队列中排队，每次从队列中取出一个 Socket 给事件分派器，事件分派器把 Socket 给对应的事件处理器。

然后一个 Socket 的事件处理完之后，IO多路复用程序才会将队列中的下一个 Socket 给事件分派器。文件事件分派器会根据每个 Socket 当前产生的事件，来选择对应的事件处理器来处理。

2）文件事件

当 Socket 变得可读时（比如客户端对redis执行write操作，或者close操作），或者有新的可以应答的 Sccket 出现时（客户端对redis执行connect操作），Socket就会产生一个AE_READABLE事件。

当 Socket 变得可写的时候（客户端对redis执行read操作），Socket 会产生一个AE_WRITABLE事件。

IO 多路复用程序可以同时监听 AE_REABLE 和 AE_WRITABLE 两种事件，如果一个Socket同时产生了这两种事件，那么文件事件分派器优先处理 AE_READABLE 事件，然后才是 AE_WRITABLE 事件。

3）文件事件处理器

如果是客户端要连接redis，那么会为 Socket 关联连接应答处理器。
如果是客户端要写数据到redis，那么会为 Socket 关联命令请求处理器。
如果是客户端要从redis读数据，那么会为 Socket 关联命令回复处理器。

4）客户端与redis通信的一次流程

在 Redis 启动初始化的时候，Redis 会将连接应答处理器跟 AE_READABLE 事件关联起来，接着如果一个客户端跟Redis发起连接，此时会产生一个 AE_READABLE 事件，然后由连接应答处理器来处理跟客户端建立连接，创建客户端对应的 Socket，同时将这个 Socket 的 AE_READABLE 事件跟命令请求处理器关联起来。

当客户端向Redis发起请求的时候（不管是读请求还是写请求，都一样），首先就会在 Socket 产生一个 AE_READABLE 事件，然后由对应的命令请求处理器来处理。这个命令请求处理器就会从Socket中读取请求相关数据，然后进行执行和处理。

接着Redis这边准备好了给客户端的响应数据之后，就会将Socket的AE_WRITABLE事件跟命令回复处理器关联起来，当客户端这边准备好读取响应数据时，就会在 Socket 上产生一个 AE_WRITABLE 事件，会由对应的命令回复处理器来处理，就是将准备好的响应数据写入 Socket，供客户端来读取。

命令回复处理器写完之后，就会删除这个 Socket 的 AE_WRITABLE 事件和命令回复处理器的关联关系。

（3）为啥Redis单线程模型也能效率这么高？

1）纯内存操作

Redis 将所有数据放在内存中，内存的响应时长大约为 100 纳秒，这是 redis 的 QPS 过万的重要基础。

2）核心是基于非阻塞的IO多路复用机制

有了非阻塞 IO 意味着线程在读写 IO 时可以不必再阻塞了，读写可以瞬间完成然后线程可以继续干别的事了。

redis 需要处理多个 IO 请求，同时把每个请求的结果返回给客户端。由于 redis 是单线程模型，同一时间只能处理一个 IO 事件，于是 redis 需要在合适的时间暂停对某个 IO 事件的处理，转而去处理另一个 IO 事件，这就需要用到IO多路复用技术了， 就好比一个管理者，能够管理个socket的IO事件，当选择了哪个socket，就处理哪个socket上的 IO 事件，其他 IO 事件就暂停处理了。

3）单线程反而避免了多线程的频繁上下文切换带来的性能问题。（百度多线程上下文切换）

第一，单线程可以简化数据结构和算法的实现。并发数据结构实现不但困难而且开发测试比较麻

第二，单线程避免了线程切换和竞态产生的消耗，对于服务端开发来说，锁和线程切换通常是性能杀手。

单线程的问题：对于每个命令的执行时间是有要求的。如果某个命令执行过长，会造成其他命令的阻塞，所以 redis 适用于那些需要快速执行的场景。

本系列文章在于面试突击，不是教程，要是细挖，Redis线程模型能讲好多，而面试你只需要把这个原理说出来就行了。该系列文章在于快速突击，快速拾遗，温习。

****觉得好看，请点****赞哦~****

欢迎支持，欢迎关注

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

概述

有读者反馈，读了文章 一线技术管理者究竟在管什么事？ 收获满满，但还有点不过瘾，还想了解更细的东西…

这篇文章分享开发流程规范，目的是提高产品质量，优化开发流程，供大家参考。

规范是死的，人是活的，希望自己定的规范，不要被打脸。

接下来从以上六个阶段进行逐一拆解。

1 需求评审

作为技术人员肯定都参加过需求评审会，不知道有没有遇到这样的情况？

• 产品经理按照 PRD 文档读一遍，参会人员无动于衷。
• 产品经理刚讲了一个需求点，参会人员就产生了激烈的讨论，都在证明自己是对的。
• 参会人员对需求的目标不明确，对需求点进行发散思维讨论，最终偏离方向。

遇到以上问题，肯定是在参加需求评审之前未做充分准备，那么问题来了，需要提前准备什么？

评审前

不要听产品同学说，该需求是大老板跟进的、非常重要、非常紧急之类的，就问产品三个问题：

1. 解决了什么问题？
2. 提升了什么指标？
3. 有什么商业价值？

这三个问题搞清楚了，再进行评审。

产品经理发出 原型 和 PRD 初稿后，开发人员要有 1-2 天时间（具体时间根据项目大小而定），熟悉文档，有任何疑问可以反馈给开发经理，由开发经理统一收集再反馈给产品经理，产品经理逐一进行答疑。

熟悉完文档后，开发人员和开发经理需要一起确定：

• 技术选型（前端/后端框架、日志中间件、消息中间件、数据库…）
• 技术架构（组件与组件之间如何协同工作，如何部署）
• 技术难点预知（明确存在的技术难点，并确定解决方案）
• 性能瓶颈预知（明确可能存在性能瓶颈的地方，并确定应对措施）
• 上下游系统交互（明确在流程中的哪个位置，约定接口文档提供时间、接口联调时间）
• 功能模块划分（任务拆分和分配）

技术方案确定后，需要输出技术设计文档，包括：总体设计、概要设计、详细设计、接口设计 等。

评审中

开发人员必须参加，有需求不明确的地方当场提出，同时开发人员也需要思考产品需求是否合理，可适当提出自己的产品意见。

一般评审至少有两次（初稿和终稿）。

评审后

评审后，如有需更新技术文档的请及时进行更新。

开发经理首先需要考虑团队现有的资源及项目的优先级，然后根据技术设计文档进行评估排期。

排期模板如下：

2 技术评审

评审前

开发人员一定要重视技术设计！

开发人员一定要重视技术设计！

开发人员一定要重视技术设计！

重要事情说三遍！

技术评审主要评审什么？

• 系统关系图、模块关系图、流程图的设计，画图工具根据自己爱好即可。
• 接口设计，需要考虑接口的 兼容性、扩展性、参数命名遵守 参数命名规范 等。
• 数据库设计，需要遵守 数据库设计规范，并记录 数据表变更文档。
• 详细设计，需要考虑公共类、公共方法、方法定义 遵守 项目框架目录规范。

评审中

开发人员和开发经理必须参加，涉及到总体设计和概要设计时，需要邀请 架构师 参与，涉及到数据库调整时，需要邀请 DBA 参与。

一般评审至少有两次（初稿和终稿）。

评审后

评审后，如有需更新排期文档的请及时进行更新。

排期确定后，通过邮件方式进行回复排期，使用标准化的 回复排期邮件模板。

按部就班，按计划行事。

3 需求开发

编码

开发人员编码过程中，需要遵守团队的 编码规范，同时严格按照设计文档中的技术方案执行，除了保证代码逻辑的正确性外，还需要考虑代码封装性、可维护性、可扩展性，当编码阶段发现技术方案需要调整时，需要及时通知开发经理，经过同意后才能实施，涉及到引入新框架和新技术，也需要提前通知开发经理。

代码审查

开发人员需要控制代码提交的频次和粒度，每次代码提交之后 24 小时内，需要主动联系代码审查人完成检查，开发经理负责检查是否执行到位。

代码审查主要审查什么？

• 规范性检查（是否符合代码规范、提交备注规范等）
• 健壮性检查（是否陷入死循环、资源未释放等）
• 安全性检查（是否存在SQL注入、XSS、SSRF、CSRF、越权、文件上传等）
• 性能检查（是否存在未加缓存频繁连接DB，是否需要连接池）

联调

开发人员积极主动地推动联调工作，如果遇到阻碍及时通知技术经理进行协调。

自测

联调完毕后，开发人员需要同时完成自测，并将标准化的 自测报告 发给测试团队。

对于有性能要求的项目，需要开发人员进行性能测试，并出具标准化的 性能测试报告。

提测

自测完毕后，通过邮件方式进行提测申请，使用标准化的 申请提测邮件模板。

开发人员根据公司运维提供的发布方式，进行部署到测试环境。

4 跟进测试

测试用例评审

开发人员必须参加，避免出现测试与开发对需求理解不一致的情况。

Bug 修复

开发人员及时关注 Bug 列表，快速修复迭代发布，如果测试进度存在延期风险，需要及时通知开发经理。

5 跟进上线

开发人员首先确认 Bug 全部关闭，同时产品人员在测试环境验收通过，然后需要主动推动相关团队理清上线依赖和上线顺序，同时确定回滚预案，最后根据公司运维提供的发布方式，进行部署到线上环境。

线上环境部署完成后，通过邮件方式进行通知产品人员和测试人员，使用标准化的 上线完毕邮件模板，同时积极推动测试人员和产品人员完成线上验证，线上出现问题后第一时间通知开发经理。

6 线上问题复盘

需求在测试环境和正式环境，均未测试出 Bug，上线一段时候后出现 Bug，这种问题用什么制度约束？

出现问题后开发人员及时修复，修复完了就完事了。仅仅做到这些还远远不够。

建议使用如下模板进行复盘。

小结

大家可以数一数上面使用到了多少规范，这时有朋友会说了，这规范也太多了吧，这和工厂工人有什么区别，我们程序员是有创造性的，我们喜欢前沿性、挑战性的工作，我们放荡不羁爱自由…

针对这个问题，首先我不否认开发人员是有创造性的，但并不是所有的程序员都有创造性，在现实工作场景中大部分程序员不是做创造性工作的，也没必要做创造性工作，所以必须按照规范流程执行。

团队管理和团队之间合作，必须要有规范，并严格执行。

就到这吧，以上供参考。

推荐阅读

• Git 分支设计规范
• API 接口设计规范
• 一线技术管理者究竟在管什么事？
• 一个人被提拔，不仅仅是能力，而是信任

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

前言

关于前面讲过的知识点我就不再赘述了，还没看过的朋友可以进入我的首页进行查阅（前言部分附赠飞机票）。这篇文章将是整个专题的总结，而且也是面试官会问到的最高频率的一个问题——“你对 MySQL 的性能优化有什么想法？”

很多出去面试的朋友应该基本上都会被问到这个问题，但是可能能够回答得尽善尽美的比较少，看过我专题且能够消化成自己肚子里的东西的朋友应该可以吊打面试官了哈哈哈哈（针对中高级），希望今天这篇文章之后大家能够对自己脑海中零散知识点进行整合整理，我盼着你们能回来给我报喜（当然吐苦水也可以），也盼着能跟大家一起不断进步。

回到正题，关于这次的 MySQL 性能优化的知识点，我会分成两篇幅的文章来输出，关于 SQL 语句的性能优化我会以单独的篇幅来进行编写，语句优化在实操中是属于性能优化的最高级别的优化点，希望大家也能好好消化。

这个 MySQL 专题是我从年前就一直在准备的，刚好过年在家也没事就一直在思考着要怎么去发表这部分的文章，让大家能够看的时候思路比较清晰，记忆能够更加深刻，最后我是通过先发布脑图，然后再根据脑图的方向进行专题知识点的发表，之后应该也会是这种形式，毕竟，这样我写文章思路清晰，大家看文章的时候思路也清晰嘛，复习知识点的时候也可以根据脑图来。

博文是我从去年开始写的，之前是自己在云笔记上做笔记比较多。我觉得做笔记写总结对自我提升有很大的帮助，而分享出来，也是希望大家能够从中学到新的知识，同时也能帮助我一起不断改进，给我提一些建议，让我在给大家分享总结的东西的同时自己也能查缺补漏（再次感谢一直以来支持我的朋友们 Thanks♪(･ω･)ﾉ）

关于下一个专题我还没想好要写什么，大家如果有什么想法的话可以在公众号给我留言。

这个篇章是性能优化篇章兄弟篇，SQL语句优化，在面试中也是重中之重，希望各位小伙伴重视。

老规矩，先上飞机票：

1. MySQL相关（一）- 一条查询语句是如何执行的
2. MySQL相关（二）- 一条更新语句是如何执行的
3. MySQL相关（番外篇）- innodb 逻辑存储结构；
4. MySQL相关（三）- 索引数据模型推演及 B+Tree 的详细介绍；
5. MySQL相关（四）- 性能优化关键点索引
6. MySQL相关（五）- 事务特性及隔离级别的详细介绍
7. MySQL相关（六）- 事务隔离级别的实现方案（MVCC）
8. MySQL相关（七）- innodb 锁的介绍及使用
9. MySQL相关（八）- innodb行级锁深入剖析
10. MySQL相关（九）- 死锁的发生和避免

前面提到的脑图如下，想要完整高清图片可以到微信我的公众号下【6曦轩】下回复 MySQL 脑图获取：

正文

优化器——SQL 语句分析与优化

优化器就是对我们的 SQL 语句进行分析，生成执行计划。

我们做项目的时候，有时会收到 DBA 的邮件，里面列出了我们项目上几个耗时比较长的查询语句，让我们去优化，这些语句是从哪里来的呢？

我们的服务层每天执行了这么多 SQL 语句，它怎么知道哪些 SQL 语句比较慢呢？首先，我们要把 SQL 执行情况记录下来。

慢查询日志 slow query log

官网说明：dev.mysql.com/doc/refman/…

打开慢日志开关

因为开启慢查询日志是有代价的（跟 binlog、optimizer-trace 一样），所以在 MySQL 中，它默认是关闭的：

1

复制代码show variables like 'slow_query%';

除了这个开关，还有一个参数，控制执行超过多长时间的 SQL 才记录到慢日志，默认是 10 秒。

1

复制代码show variables like '%slow_query%';

可以直接动态修改参数（重启后失效）。

1
2
3
4
5
6
7

复制代码set @@global.slow_query_log=1;	-- 1 开启，0 关闭，重启后失效

set @@global.long_query_time=3;	-- mysql 默认的慢查询时间是 10 秒，另开一个窗口后才会查到最新值

show variables like '%long_query%';

show variables like '%slow_query%';

或者修改配置文件 my.cnf。

以下配置定义了慢查询日志的开关、慢查询的时间、日志文件的存放路径。

1
2
3
4
5

复制代码slow_query_log = ON

long_query_time=2

slow_query_log_file =/var/lib/mysql/localhost-slow.log

模拟慢查询：

1

复制代码select sleep(10);

查询 user_innodb 表的 500 万数据（检查是不是没有索引）。

1

复制代码SELECT * FROM `user_innodb` where phone = '136';

慢日志分析

1. 日志内容

1
2
3

复制代码show global status like 'slow_queries'; -- 查看有多少慢查询 show variables like '%slow_query%'; -- 获取慢日志目录

cat /var/lib/mysql/ localhost-slow.log

有了慢查询日志，怎么去分析统计呢？比如 SQL 语句的出现的慢查询次数最多，平均每次执行了多久？
2. mysqldumpslow

通过官网的说明来看一下：dev.mysql.com/doc/refman/…

MySQL 提供了 mysqldumpslow 的工具，在 MySQL 的 bin 目录下。

1

复制代码mysqldumpslow --help

例如：查询用时最多的 20 条慢 SQL：

1

复制代码mysqldumpslow -s t -t 20 -g 'select' /var/lib/mysql/localhost-slow.log

Count 代表这个 SQL 执行了多少次；

Time 代表执行的时间，括号里面是累计时间；

Lock 表示锁定的时间，括号是累计；

Rows 表示返回的记录数，括号是累计。

除了慢查询日志之外，还有一个 SHOW PROFILE 工具可以使用。

SHOW PROFILE

dev.mysql.com/doc/refman/…

SHOW PROFILE 是谷歌高级架构师 Jeremy Cole 贡献给 MySQL 社区的，可以查看SQL 语句执行的时候使用的资源，比如 CPU、IO 的消耗情况。

在 SQL 中输入 help profile 可以得到详细的帮助信息。

查看是否开启

1
2
3

复制代码select @@profiling;

set @@profiling=1;

查看 profile 统计

1

复制代码show profiles;//命令最后带一个 s

查看最后一个 SQL 的执行详细信息，从中找出耗时较多的环节（没有 s）。

1

复制代码show profile;//没有 s

6.2E-5，小数点左移 5 位，代表 0.000062 秒。
也可以根据 ID 查看执行详细信息，在后面带上 for query + ID。

1

复制代码show profile for query 1;

除了慢日志和 show profile，如果要分析出当前数据库中执行的慢的 SQL，还可以通过查看运行线程状态和服务器运行信息、存储引擎信息来分析。

其他系统命令

1
2
3
4
5

复制代码show processlist 运行线程

https://dev.mysql.com/doc/refman/5.7/en/show-processlist.html

show processlist;

这是很重要的一个命令，用于显示用户运行线程。可以根据 id 号 kill 线程。

也可以查表，效果一样：

1

复制代码select * from information_schema.processlist;

show status 服务器运行状态

dev.mysql.com/doc/refman/…

SHOW STATUS 用于查看 MySQL 服务器运行状态（重启后会清空），有 session

和 global 两种作用域，格式：参数-值。

可以用 like 带通配符过滤。

SHOW GLOBAL STATUS LIKE ‘com_select’; – 查看 select 次数

show engine 存储引擎运行信息

dev.mysql.com/doc/refman/…

show engine 用来显示存储引擎的当前运行信息，包括事务持有的表锁、行锁信息；

事务的锁等待情况；线程信号量等待；文件 IO 请求；buffer pool 统计信息。

例如：

1

复制代码show engine innodb status;

如果需要将监控信息输出到错误信息 error log 中（15 秒钟一次），可以开启输出。

1
2
3
4
5
6
7

复制代码show variables like 'innodb_status_output%';

--开启输出：

SET GLOBAL innodb_status_output=ON;

SET GLOBAL innodb_status_output_locks=ON;

我们现在已经知道了这么多分析服务器状态、存储引擎状态、线程运行信息的命令，如果让你去写一个数据库监控系统，你会怎么做？

其实很多开源的慢查询日志监控工具，他们的原理其实也都是读取的系统的变量和状态。

现在我们已经知道哪些 SQL 慢了，为什么慢呢？慢在哪里？

MySQL 提供了一个执行计划的工具（在架构中我们有讲到，优化器最终生成的就是一个执行计划），其他数据库，例如 Oracle 也有类似的功能。

通过 EXPLAIN 我们可以模拟优化器执行 SQL 查询语句的过程，来知道 MySQL 是怎么处理一条 SQL 语句的。通过这种方式我们可以分析语句或者表的性能瓶颈。

explain 可以分析 update、delete、insert 么？

MySQL 5.6.3 以前只能分析 SELECT; MySQL5.6.3 以后就可以分析 update、delete、 insert 了。

EXPLAIN 执行计划

官方链接：dev.mysql.com/doc/refman/…

我们先创建三张表。一张课程表，一张老师表，一张老师联系方式表（没有任何索引）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

复制代码DROP TABLE IF EXISTS course;

CREATE TABLE `course` (
	`cid` int(3) DEFAULT NULL,
	`cname` varchar(20) DEFAULT NULL,
	`tid` int(3) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

DROP TABLE IF EXISTS teacher;

CREATE TABLE `teacher` (
	`tid` int(3) DEFAULT NULL,
	`tname` varchar(20) DEFAULT NULL,
	`tcid` int(3) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

DROP TABLE IF EXISTS teacher_contact;

CREATE TABLE `teacher_contact` (
	`tcid` int(3) DEFAULT NULL,
	`phone` varchar(200) DEFAULT NULL

) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

​INSERT INTO `course` VALUES ('1', 'mysql', '1');

INSERT INTO `course` VALUES ('2', 'jvm', '1');

INSERT INTO `course` VALUES ('3', 'juc', '2');

INSERT INTO `course` VALUES ('4', 'spring', '3');

INSERT INTO `teacher` VALUES ('1', 'jerry', '1');

INSERT INTO `teacher` VALUES ('2', 'jack', '2');

INSERT INTO `teacher` VALUES ('3', 'mic', '3');

INSERT INTO `teacher_contact` VALUES ('1', '13688888888');

INSERT INTO `teacher_contact` VALUES ('2', '18166669999');

INSERT INTO `teacher_contact` VALUES ('3', '17722225555');

explain 的结果有很多的字段，我们详细地分析一下。

先确认一下环境：

1
2

复制代码select version();
show variables like '%engine%';

id

id 是查询序列编号。

id 值不同

id 值不同的时候，先查询 id 值大的（先大后小）。

–查询 mysql 课程的老师手机号

1
2
3

复制代码EXPLAIN SELECT tc.phone FROM teacher_contact tc WHERE tcid = (
	SELECT tcid FROM teacher t WHERE t.tid = ( SELECT c.tid FROM course c WHERE c.cname = 'mysql')
);

查询顺序：course c——teacher t——teacher_contact tc。

先查课程表，再查老师表，最后查老师联系方式表。子查询只能以这种方式进行，只有拿到内层的结果之后才能进行外层的查询。

id 值相同

–查询课程 ID 为 2，或者联系表 ID 为 3 的老师

1
2
3
4

复制代码EXPLAIN
SELECT t.tname,c.cname,tc.phone
FROM teacher t, course c, teacher_contact tc WHERE t.tid = c.tid
AND t.tcid = tc.tcid AND (c.cid = 2 OR tc.tcid = 3);

id 值相同时，表的查询顺序是从上往下顺序执行。例如这次查询的 id 都是 1，查询的顺序是 teacher t（3 条）——course c（4 条）——teacher_contact tc（3 条）。

teacher 表插入 3 条数据后：

1
2
3
4
5
6
7

复制代码INSERT INTO `teacher` VALUES (4, 'james', 4);

INSERT INTO `teacher` VALUES (5, 'tom', 5);

INSERT INTO `teacher` VALUES (6, 'seven', 6);

COMMIT;

1
2
3
4
5

复制代码--（备份）恢复语句

DELETE FROM teacher where tid in (4,5,6);

COMMIT;

id 也都是 1，但是从上往下查询顺序变成了：teacher_contact tc（3 条）——teacher t（6 条）——course c（4 条）。

为什么数据量不同的时候顺序会发生变化呢？这个是由笛卡尔积决定的。

举例：假如有 a、b、c 三张表，分别有 2、3、4 条数据，如果做三张表的联合查询，当查询顺序是 a→b→c 的时候，它的笛卡尔积是：234=64=24。如果查询顺序是 c →b→a，它的笛卡尔积是 432=122=24。

因为 MySQL 要把查询的结果，包括中间结果和最终结果都保存到内存，所以 MySQL 会优先选择中间结果数据量比较小的顺序进行查询。所以最终联表查询的顺序是 a→b→ c。这个就是为什么 teacher 表插入数据以后查询顺序会发生变化。

（小表驱动大表的思想）

既有相同也有不同如果 ID 有相同也有不同，就是 ID 不同的先大后小，ID 相同的从上往下。

select type 查询类型

这里并没有列举全部（其它：DEPENDENT UNION、DEPENDENT SUBQUERY、MATERIALIZED、UNCACHEABLE SUBQUERY、UNCACHEABLE UNION）。

下面列举了一些常见的查询类型：

• SIMPLE

简单查询，不包含子查询，不包含关联查询 union。
EXPLAIN SELECT * FROM teacher;

再看一个包含子查询的案例：
–查询 mysql 课程的老师手机号
EXPLAIN SELECT tc.phone FROM teacher_contact tc WHERE tcid = (SELECT tcid FROM teacher t WHERE t.tid = ( SELECT c.tid FROM course c WHERE c.cname = 'mysql'));

• PRIMARY

子查询 SQL 语句中的主查询，也就是最外面的那层查询。

• SUBQUERY

子查询中所有的内层查询都是 SUBQUERY 类型的。

• DERIVED

衍生查询，表示在得到最终查询结果之前会用到临时表。例如：
–查询 ID 为 1 或 2 的老师教授的课程
EXPLAIN SELECT cr.cname FROM (SELECT * FROM course WHERE tid = 1UNIONSELECT * FROM course WHERE tid = 2 ) cr;

对于关联查询，先执行右边的 table（UNION），再执行左边的 table，类型是DERIVED。

• UNION

用到了 UNION 查询。同上例。

• UNION RESULT

主要是显示哪些表之间存在 UNION 查询。<union2,3>代表 id=2 和 id=3 的查询存在 UNION。同上例。

type 连接类型

dev.mysql.com/doc/refman/…

所有的连接类型中，上面的最好，越往下越差。

在常用的链接类型中：system > const > eq_ref > ref > range > index > all

这 里 并 没 有 列 举 全 部 （ 其 他 ： fulltext 、 ref_or_null 、 index_merger 、unique_subquery、index_subquery）。

以上访问类型除了 all，都能用到索引。

• const

主键索引或者唯一索引，只能查到一条数据的 SQL。

1 2 3 4 5 6 7 8 9

> 复制代码DROP TABLE IF EXISTS single_data; > CREATE TABLE single_data( > id int(3) PRIMARY KEY, > content varchar(20) > ); > insert into single_data values(1,'a'); > EXPLAIN SELECT * FROM single_data a where id = 1; > >

• system

system 是 const 的一种特例，只有一行满足条件。例如：只有一条数据的系统表。
EXPLAIN SELECT * FROM mysql.proxies_priv;

• eq_ref

通常出现在多表的 join 查询，表示对于前表的每一个结果,，都只能匹配到后表的一行结果。一般是唯一性索引的查询（UNIQUE 或 PRIMARY KEY）。

eq_ref 是除 const 之外最好的访问类型。

先删除 teacher 表中多余的数据，teacher_contact 有 3 条数据，teacher 表有 3 条数据。

1 2 3 4

> 复制代码DELETE FROM teacher where tid in (4,5,6); > commit; > >

1 2 3 4 5 6 7

> 复制代码--备份 > INSERT INTO `teacher` VALUES (4, 'james', 4); > INSERT INTO `teacher` VALUES (5, 'tom', 5); > INSERT INTO `teacher` VALUES (6, 'seven', 6); > commit; > >

为 teacher_contact 表的 tcid（第一个字段）创建主键索引。
--ALTER TABLE teacher_contact DROP PRIMARY KEY; ALTER TABLE teacher_contact ADD PRIMARY KEY(tcid);
为teacher 表的 tcid（第三个字段）创建普通索引。
--ALTER TABLE teacher DROP INDEX idx_tcid; ALTER TABLE teacher ADD INDEX idx_tcid (tcid);
执行以下 SQL 语句：
select t.tcid from teacher t,teacher_contact tc where t.tcid = tc.tcid;

此时的执行计划（teacher_contact 表是 eq_ref）：

小结：

以上三种 system，const，eq_ref，都是可遇而不可求的，基本上很难优化到这个状态。

• ref

查询用到了非唯一性索引，或者关联操作只使用了索引的最左前缀。
例如：使用 tcid 上的普通索引查询：
explain SELECT * FROM teacher where tcid = 3;

• range

索引范围扫描。
如果 where 后面是 between and 或 <或 > 或 >= 或 <=或 in 这些，type 类型就为 range。
不走索引一定是全表扫描（ALL），所以先加上普通索引。
--ALTER TABLE teacher DROP INDEX idx_tid; ALTER TABLE teacher ADD INDEX idx_tid (tid);
执行范围查询（字段上有普通索引）：
EXPLAIN SELECT * FROM teacher t WHERE t.tid <3;
–或
EXPLAIN SELECT * FROM teacher t WHERE tid BETWEEN 1 AND 2;

IN 查询也是 range（字段有主键索引）
EXPLAIN SELECT * FROM teacher_contact t WHERE tcid in (1,2,3);

• index

Full Index Scan，查询全部索引中的数据（比不走索引要快）。
EXPLAIN SELECT tid FROM teacher;

• all

Full Table Scan，如果没有索引或者没有用到索引，type 就是 ALL。代表全表扫描。

• NULL

不用访问表或者索引就能得到结果，例如：
EXPLAIN select 1 from dual where 1=1;

小结：

一般来说，需要保证查询至少达到 range 级别，最好能达到 ref。

ALL（全表扫描）和 index（查询全部索引）都是需要优化的。

possible_key、key

可能用到的索引和实际用到的索引。如果是 NULL 就代表没有用到索引。 possible_key 可以有一个或者多个，可能用到索引不代表一定用到索引。反过来，possible_key 为空，key 可能有值吗？表上创建联合索引：

1
2

复制代码ALTER TABLE user_innodb DROP INDEX comidx_name_phone;
ALTER TABLE user_innodb add INDEX comidx_name_phone (name,phone);

执行计划（改成 select name 也能用到索引）：

1

复制代码explain select phone from user_innodb where phone='126';

结论：是有可能的（这里是覆盖索引的情况）。

如果通过分析发现没有用到索引，就要检查 SQL 或者创建索引。

key_len

索引的长度（使用的字节数）。跟索引字段的类型、长度有关。

rows

MySQL 认为扫描多少行才能返回请求的数据，是一个预估值。一般来说行数越少越好。

filtered

这个字段表示存储引擎返回的数据在 server 层过滤后，剩下多少满足查询的记录数量的比例，它是一个百分比。

ref

使用哪个列或者常数和索引一起从表中筛选数据。

Extra

执行计划给出的额外的信息说明。

using index

用到了覆盖索引，不需要回表。

1

复制代码EXPLAIN SELECT tid FROM teacher ;

using where

使用了 where 过滤，表示存储引擎返回的记录并不是所有的都满足查询条件，需要在 server 层进行过滤（跟是否使用索引没有关系）。

1

复制代码EXPLAIN select * from user_innodb where phone ='13866667777';

Using index condition（索引条件下推）

索引下推，在前面的文章中已经讲解过了。

dev.mysql.com/doc/refman/…

using filesort

不能使用索引来排序，用到了额外的排序（跟磁盘或文件没有关系）。需要优化。（复合索引的前提）

1
2

复制代码ALTER TABLE user_innodb DROP INDEX comidx_name_phone;
ALTER TABLE user_innodb add INDEX comidx_name_phone (name,phone);

1

复制代码EXPLAIN select * from user_innodb where name ='青山' order by id;

（order by id 引起）

using temporary

用到了临时表。例如（以下不是全部的情况）：

1、distinct 非索引列

1

复制代码EXPLAIN select DISTINCT(tid) from teacher t;

2、group by 非索引列

1

复制代码EXPLAIN select tname from teacher group by tname;

3、使用 join 的时候，group 任意列

1

复制代码EXPLAIN select t.tid from teacher t join course c on t.tid = c.tid group by t.tid;

需要优化，例如创建复合索引。

总结一下：

模拟优化器执行 SQL 查询语句的过程，来知道 MySQL 是怎么处理一条 SQL 语句的。

通过这种方式我们可以分析语句或者表的性能瓶颈。

分析出问题之后，就是对 SQL 语句的具体优化。

比如怎么用到索引，怎么减少锁的阻塞等待，在前面两次课已经讲过。

SQL 与索引优化

当我们的 SQL 语句比较复杂，有多个关联和子查询的时候，就要分析 SQL 语句有没有改写的方法。

举个简单的例子，一模一样的数据：

–大偏移量的 limit

1

复制代码select * from user_innodb limit 900000,10;

–改成先过滤 ID，再 limit

1

复制代码SELECT * FROM user_innodb WHERE id >= 900000 LIMIT 10;

对于具体的 SQL 语句的优化，MySQL 官网也提供了很多建议，这个是我们在分析具体的 SQL 语句的时候需要注意的，也是大家在以后的工作里面要去慢慢地积累的（这里我们就不一一地分析了）。

dev.mysql.com/doc/refman/…

存储引擎

存储引擎的选择

为不同的业务表选择不同的存储引擎，例如：查询插入操作多的业务表，用 MyISAM。

临时数据用 Memeroy。常规的并发大更新多的表用 InnoDB。

分区或者分表

分区不推荐。

交易历史表：在年底为下一年度建立 12 个分区，每个月一个分区。

渠道交易表：分成当日表；当月表；历史表，历史表再做分区。

字段定义

原则：使用可以正确存储数据的最小数据类型。

为每一列选择合适的字段类型：

整数类型

INT 有 8 种类型，不同的类型的最大存储范围是不一样的。
性别？用 TINYINT，因为 ENUM 也是整型存储。

字符类型

变长情况下，varchar 更节省空间，但是对于 varchar 字段，需要一个字节来记录长度。

固定长度的用 char，不要用 varchar。

非空

非空字段尽量定义成 NOT NULL，提供默认值，或者使用特殊值、空串代替 null。

NULL 类型的存储、优化、使用都会存在问题。

不要用外键、触发器、视图

降低了可读性；

影响数据库性能，应该把把计算的事情交给程序，数据库专心做存储；

数据的完整性应该在程序中检查。

大文件存储

不要用数据库存储图片（比如 base64 编码）或者大文件；

把文件放在 NAS 上，数据库只需要存储 URI（相对路径），在应用中配置 NAS 服务器地址。

表拆分

将不常用的字段拆分出去，避免列数过多和数据量过大。

比如在业务系统中，要记录所有接收和发送的消息，这个消息是 XML 格式的，用 blob 或者 text 存储，用来追踪和判断重复，可以建立一张表专门用来存储报文。

后话

MySQL 专题到这个篇章就正式结束了，基本上是按照脑图的方向来，所以大家可以对着脑图以及我的博文来进行 MySQL 的复习，基本上面试的问题都有涉及，编写一个专题确实是费脑又费精力费时间的事情，我还是需要大家的关注和点赞来支撑一下哈哈哈~

如果大家觉得写得还有点东西的话帮忙关注一下我的公众号，并且在后台给我留言希望我写哪个专题的东西（现学现卖的如果有什么不对的地方也请帮忙指正，万分感谢），人多的话马上安排上~

还是那样，修整一段时间后会先在公众号推送脑图，然后根据脑图来拟专题的提纲，这样我写得不会云里雾里，大家也会比较有方向地看我的博文，再次感谢大家的支持~

By the way

有问题？可以给我留言或私聊
有收获？那就顺手点个赞呗~

当然，也可以到我的公众号下「6曦轩」，

回复“学习”，即可领取一份
【Java工程师进阶架构师的视频教程】~

回复“面试”，可以获得：
【本人呕心沥血整理的 Java 面试题】

回复“MySQL脑图”，可以获得
【MySQL 知识点梳理高清脑图】

由于我咧，科班出身的程序员，php，Android以及硬件方面都做过，不过最后还是选择专注于做 Java，所以有啥问题可以到公众号提问讨论（技术情感倾诉都可以哈哈哈），看到的话会尽快回复，希望可以跟大家共同学习进步，关于服务端架构，Java 核心知识解析，职业生涯，面试总结等文章会不定期坚持推送输出，欢迎大家关注~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

前言

关于前面讲过的知识点我就不再赘述了，还没看过的朋友可以进入我的首页进行查阅（前言部分附赠飞机票）。这篇文章将是整个专题的总结，而且也是面试官会问到的最高频率的一个问题——“你对 MySQL 的性能优化有什么想法？”

很多出去面试的朋友应该基本上都会被问到这个问题，但是可能能够回答得尽善尽美的比较少，看过我专题且能够消化成自己肚子里的东西的朋友应该可以吊打面试官了哈哈哈哈（针对中高级），希望今天这篇文章之后大家能够对自己脑海中零散知识点进行整合整理，我盼着你们能回来给我报喜（当然吐苦水也可以），也盼着能跟大家一起不断进步。

回到正题，关于这次的 MySQL 性能优化的知识点，我会分成两篇幅的文章来输出，关于 SQL 语句的性能优化我会以单独的篇幅来进行编写，语句优化在实操中是属于性能优化的最高级别的优化点，希望大家也能好好消化。

这个 MySQL 专题是我从年前就一直在准备的，刚好过年在家也没事就一直在思考着要怎么去发表这部分的文章，让大家能够看的时候思路比较清晰，记忆能够更加深刻，最后我是通过先发布脑图，然后再根据脑图的方向进行专题知识点的发表，之后应该也会是这种形式，毕竟，这样我写文章思路清晰，大家看文章的时候思路也清晰嘛，复习知识点的时候也可以根据脑图来。

博文是我从去年开始写的，之前是自己在云笔记上做笔记比较多。我觉得做笔记写总结对自我提升有很大的帮助，而分享出来，也是希望大家能够从中学到新的知识，同时也能帮助我一起不断改进，给我提一些建议，让我在给大家分享总结的东西的同时自己也能查缺补漏（再次感谢一直以来支持我的朋友们 Thanks♪(･ω･)ﾉ）

关于下一个专题我还没想好要写什么，大家如果有什么想法的话可以在公众号给我留言。

老规矩，先上飞机票：

1. MySQL相关（一）- 一条查询语句是如何执行的
2. MySQL相关（二）- 一条更新语句是如何执行的
3. MySQL相关（番外篇）- innodb 逻辑存储结构；
4. MySQL相关（三）- 索引数据模型推演及 B+Tree 的详细介绍；
5. MySQL相关（四）- 性能优化关键点索引
6. MySQL相关（五）- 事务特性及隔离级别的详细介绍
7. MySQL相关（六）- 事务隔离级别的实现方案（MVCC）
8. MySQL相关（七）- innodb 锁的介绍及使用
9. MySQL相关（八）- innodb行级锁深入剖析
10. MySQL相关（九）- 死锁的发生和避免

前面提到的脑图如下，想要完整高清图片可以到微信我的公众号下【6曦轩】下回复 MySQL 脑图获取：

正文

优化思路

容我再絮絮叨叨

作为架构师或者开发人员，说到数据库性能优化，你的思路是什么样的？

或者具体一点，如果在面试的时候遇到这个问题：你会从哪些维度来优化数据库，你会怎么回答？

通过前面的篇章，相信大家已经慢慢建立了数据库的知识体系，和正确的调优的思路。

我们说到性能调优，大部分时候想要实现的目标是让我们的查询更快。一个查询的动作又是由很多个环节组成的，每个环节都会消耗时间，第一篇章里讲 SQL 语句的执行流程的时候已经分析过了。

我们要减少查询所消耗的时间，就要从每一个环节入手（先上大家比较熟悉的一张图）。

连接——配置优化

第一个环节是客户端连接到服务端，连接这一块有可能会出现什么样的性能问题？

有可能是服务端连接数不够导致应用程序获取不到连接。比如报了一个 Mysql: error 1040: Too many connections的错误。

我们可以从两个方面来解决连接数不够的问题：

1. 从服务端来说，我们可以增加服务端的可用连接数。

如果有多个应用或者很多请求同时访问数据库，连接数不够的时候，我们可以：
（1）修改配置参数增加可用连接数，修改 max_connections 的大小：

show variables like 'max_connections';
– 修改最大连接数，当有多个应用连接的时候

（2）或者，或者及时释放不活动的连接。交互式和非交互式的客户端的默认超时时间都是 28800 秒，8 小时，我们可以把这个值调小。

show global variables like 'wait_timeout';
–及时释放不活动的连接，注意不要释放连接池还在使用的连接

2. 从客户端来说，可以减少从服务端获取的连接数，如果我们想要不是每一次执行 SQL 都创建一个新的连接，应该怎么做？

这个时候我们可以引入连接池，实现连接的重用。

我们可以在哪些层面使用连接池？ORM 层面（MyBatis 自带了一个连接池）；或者使用专用的连接池工具（阿里的 Druid、Spring Boot 2.x 版本默认的连接池 Hikari、老牌的 DBCP 和 C3P0）。

当客户端改成从连接池获取连接之后，连接池的大小应该怎么设置呢？大家可能会有一个误解，觉得连接池的最大连接数越大越好，这样在高并发的情况下客户端可以获取的连接数更多，不需要排队。

实际情况并不是这样。连接池并不是越大越好，只要维护一定数量大小的连接池，其他的客户端排队等待获取连接就可以了。有的时候连接池越大，效率反而越低。

• Druid 的默认最大连接池大小是 8。Hikari 的默认最大连接池大小是 10。为什么默认值都是这么小呢？

在 Hikari 的 github 文档中，给出了一个 PostgreSQL 数据库建议的设置连接池大小的公式：
github.com/brettwooldr…

它的建议是机器核数乘以 2 加 1。也就是说，4 核的机器，连接池维护 9 个连接就够了。这个公式从一定程度上来说对其他数据库也是适用的。这里面还有一个减少连接池大小实现提升并发度和吞吐量的案例。

• 为什么有的情况下，减少连接数反而会提升吞吐量呢？为什么建议设置的连接池大小要跟 CPU 的核数相关呢？

每一个连接，服务端都需要创建一个线程去处理它。连接数越多，服务端创建的线程数就会越多。

CPU 是怎么同时执行远远超过它的核数大小的任务的？时间片。上下文切换。

而 CPU 的核数是有限的，频繁的上下文切换会造成比较大的性能开销。

我们这里说到了从数据库配置的层面去优化数据库。不管是数据库本身的配置，还是安装这个数据库服务的操作系统的配置，对于配置进行优化，最终的目标都是为了更好地发挥硬件本身的性能，包括 CPU、内存、磁盘、网络。

在不同的硬件环境下，操作系统和 MySQL 的参数的配置是不同的，没有标准的配置。前面的篇章中我们也接触了很多的 MySQL 和 InnoDB 的配置参数，包括各种开关和数值的配置，大多数参数都提供了一个默认值，比如默认的 buffer_pool_size，默认的页大小，InnoDB 并发线程数等等。

这些默认配置可以满足大部分情况的需求，除非有特殊的需求，在清楚参数的含义的情况下再去修改它。修改配置的工作一般由专业的 DBA 完成。

至于硬件本身的选择，比如使用固态硬盘，搭建磁盘阵列，选择特定的 CPU 型号这些，更不是我们开发人员关注的重点，这个我们就不做过多的介绍了。

如果想要了解一些特定的参数的含义，官网有一份系统的参数列表可以参考：

dev.mysql.com/doc/refman/…

• 除了合理设置服务端的连接数和客户端的连接池大小之外，我们还有哪些减少客户
  端跟数据库服务端的连接数的方案呢？

我们可以引入缓存。

缓存——架构优化

缓存

在应用系统的并发数非常大的情况下，如果没有缓存，会造成两个问题：一方面是会给数据库带来很大的压力。另一方面，从应用的层面来说，操作数据的速度也会受到影响。

我们可以用第三方的缓存服务来解决这个问题，例如 Redis。

运行独立的缓存服务，属于架构层面的优化。
为了减少单台数据库服务器的读写压力，在架构层面我们还可以做其他哪些优化措施？

主从复制

如果单台数据库服务满足不了访问需求，那我们可以做数据库的集群方案。

集群的话必然会面临一个问题，就是不同的节点之间数据一致性的问题。如果同时读写多台数据库节点，怎么让所有的节点数据保持一致？

这个时候我们需要用到复制技术（replication），被复制的节点称为 master，复制的节点称为 slave。slave 本身也可以作为其他节点的数据来源，这个叫做级联复制。

主从复制是怎么实现的呢？更新语句会记录 binlog，它是一种逻辑日志。

有了这个 binlog，从服务器会获取主服务器的 binlog 文件，然后解析里面的 SQL 语句，在从服务器上面执行一遍，保持主从的数据一致。

这里面涉及到三个线程，连接到 master 获取 binlog，并且解析 binlog 写入中继日志，这个线程叫做 I/O 线程。

Master 节点上有一个 log dump 线程，是用来发送 binlog 给 slave 的。

从库的 SQL 线程，是用来读取 relay log，把数据写入到数据库的。

做了主从复制的方案之后，我们只把数据写入 master 节点，而读的请求可以分担到 slave 节点。我们把这种方案叫做读写分离。

读写分离可以一定程度低减轻数据库服务器的访问压力，但是需要特别注意主从数据一致性的问题。如果我们在 master 写入了，马上到 slave 查询，而这个时候 slave 的数据还没有同步过来，怎么办？

所以，基于主从复制的原理，我们需要弄明白，主从复制到底慢在哪里？

单线程

在早期的 MySQL 中，slave 的 SQL 线程是单线程。master 可以支持 SQL 语句的并行执行，配置了多少的最大连接数就是最多同时多少个 SQL 并行执行。

而 slave 的 SQL 却只能单线程排队执行，在主库并发量很大的情况下，同步数据肯定会出现延迟。

为什么从库上的 SQL Thread 不能并行执行呢？举个例子，主库执行了多条 SQL 语句，首先用户发表了一条评论，然后修改了内容，最后把这条评论删除了。这三条语句在从库上的执行顺序肯定是不能颠倒的。

1
2
3

复制代码insert into user_comments (10000009,'nice');
update user_comments set content ='very good' where id =10000009; 
delete from user_comments where id =10000009;

那么怎么解决这个问题呢？怎么减少主从复制的延迟？

异步与全同步

首先我们需要知道，在主从复制的过程中，MySQL 默认是异步复制的。也就是说，对于主节点来说，写入 binlog，事务结束，就返回给客户端了。对于 slave 来说，接收到 binlog，就完事儿了，master 不关心 slave 的数据有没有写入成功。

如果要减少延迟，是不是可以等待全部从库的事务执行完毕，才返回给客户端呢？这样的方式叫做全同步复制。从库写完数据，主库才返回给客户端。
这种方式虽然可以保证在读之前，数据已经同步成功了，但是带来的副作用大家应该能想到，事务执行的时间会变长，它会导致 master 节点性能下降。

有没有更好的办法呢？可以既减少 slave 写入的延迟，又不会明显增加 master 返回给客户端的时间？

半同步复制

介于异步复制和全同步复制之间，还有一种半同步复制的方式。

半同步复制是什么样的呢？

主库在执行完客户端提交的事务后不是立刻返回给客户端，而是等待至少一个从库接收到 binlog 并写到 relay log 中才返回给客户端。master 不会等待很长的时间，但是返回给客户端的时候，数据就即将写入成功了，因为它只剩最后一步了：就是读取 relay log，写入从库。

如果我们要在数据库里面用半同步复制，必须安装一个插件，这个是谷歌的一位工程师贡献的。这个插件在 mysql 的插件目录下已经有提供：
cd /usr/lib64/mysql/plugin/

主库和从库是不同的插件，安装之后需要启用：

–主库执行

1
2
3

复制代码INSTALL PLUGIN rpl_semi_sync_master SONAME 'semisync_master.so';
set global rpl_semi_sync_master_enabled=1;
show variables like '%semi_sync%';

–从库执行

1
2
3

复制代码INSTALL PLUGIN rpl_semi_sync_slave SONAME 'semisync_slave.so'; 
set global rpl_semi_sync_slave_enabled=1; 
show global variables like '%semi%';

相对于异步复制，半同步复制提高了数据的安全性，同时它也造成了一定程度的延迟，它需要等待一个 slave 写入中继日志，这里多了一个网络交互的过程。所以，半同步复制最好在低延时的网络中使用。

这个是从主库和从库连接的角度，来保证 slave 数据的写入。

另一个思路，如果要减少主从同步的延迟，减少 SQL 执行造成的等待的时间，那有没有办法在从库上，让多个 SQL 语句可以并行执行，而不是排队执行呢？

多库并行复制

怎么实现并行复制呢？设想一下，如果 3 条语句是在三个数据库执行，操作各自的数据库，是不是肯定不会产生并发的问题呢？执行的顺序也没有要求。当然是，所以如果是操作三个数据库，这三个数据库的从库的 SQL 线程可以并发执行。这是 MySQL 5.6 版本里面支持的多库并行复制。

但是在大部分的情况下，我们都是单库多表的情况，在一个数据库里面怎么实现并行复制呢？或者说，我们知道，数据库本身就是支持多个事务同时操作的；为什么这些事务在主库上面可以并行执行，却不会出现问题呢？

因为他们本身就是互相不干扰的，比如这些事务是操作不同的表，或者操作不同的行，不存在资源的竞争和数据的干扰。那在主库上并行执行的事务，在从库上肯定也是可以并行执行，是不是？比如在 master 上有三个事务同时分别操作三张表，这三个事务是不是在 slave 上面也可以并行执行呢？

异步复制之 GTID 复制

dev.mysql.com/doc/refman/…

所以，我们可以把那些在主库上并行执行的事务，分为一个组，并且给他们编号，这一个组的事务在从库上面也可以并行执行。这个编号，我们把它叫做 GTID（Global Transaction Identifiers），这种主从复制的方式，我们把它叫做基于 GTID 的复制。

如果我们要使用 GTID 复制，我们可以通过修改配置参数打开它，默认是关闭的：

1

复制代码show global variables like 'gtid_mode';

无论是优化 master 和 slave 的连接方式，还是让从库可以并行执行 SQL，都是从数据库的层面去解决主从复制延迟的问题。

除了数据库本身的层面之外，在应用层面，我们也有一些减少主从同步延迟的方法。

我们在做了主从复制之后，如果单个 master 节点或者单张表存储的数据过大的时候，比如一张表有上亿的数据，单表的查询性能还是会下降，我们要进一步对单台数据库节点的数据分型拆分，这个就是分库分表。

分库分表

垂直分库，减少并发压力。水平分表，解决存储瓶颈。

垂直分库的做法，把一个数据库按照业务拆分成不同的数据库：

水平分库分表的做法，把单张表的数据按照一定的规则分布到多个数据库。

通过主从或者分库分表可以减少单个数据库节点的访问压力和存储压力，达到提升数据库性能的目的，但是如果 master 节点挂了，怎么办？

所以，高可用（High Available）也是高性能的基础。

高可用方案

dev.mysql.com/doc/mysql-h…

主从复制

传统的 HAProxy + keepalived 的方案，基于主从复制。

NDB Cluster

dev.mysql.com/doc/mysql-c…

基于 NDB 集群存储引擎的 MySQL Cluster。

Galera

galeracluster.com/

一种多主同步复制的集群方案。

MHA/MMM

tech.meituan.com/2017/06/29/…

MMM（Master-Master replication manager for MySQL），一种多主的高可用架构，是一个日本人开发的，像美团这样的公司早期也有大量使用 MMM。

MHA（MySQL Master High Available）。
BM和 MHA 都是对外提供一个虚拟 IP，并且监控主节点和从节点，当主节点发生故障的时候，需要把一个从节点提升为主节点，并且把从节点里面比主节点缺少的数据补上，把 VIP 指向新的主节点。

MGR

dev.mysql.com/doc/refman/… dev.mysql.com/doc/refman/…

MySQL 5.7.17 版本推出的 InnoDB Cluster ，也叫 MySQL Group Replicatioin （MGR），这个套件里面包括了 mysql shell 和 mysql-route。

总结一下：
高可用 HA 方案需要解决的问题都是当一个 master 节点宕机的时候，如何提升一个数据最新的 slave 成为 master。如果同时运行多个 master，又必须要解决 master 之间数据复制，以及对于客户端来说连接路由的问题。

不同的方案，实施难度不一样，运维管理的成本也不一样。

以上是架构层面的优化，可以用缓存，主从，分库分表。

第三个环节：
解析器，词法和语法分析，主要保证语句的正确性，语句不出错就没问题。由 Sever 自己处理，跳过。

第四步：优化器
这一节内容我将通过新的篇章来讲述，主要是 SQL 语句性能优化的方面。

总结：优化体系

除了对于代码、SQL 语句、表定义、架构、配置优化之外，业务层面的优化也不能忽视。举几个例子：

1）在某一年的双十一，为什么会做一个充值到余额宝和余额有奖金的活动（充 300 送 50）？

因为使用余额或者余额宝付款是记录本地或者内部数据库，而使用银行卡付款，需要调用接口，操作内部数据库肯定更快。

2）在去年的双十一，为什么在凌晨禁止查询今天之外的账单？

这是一种降级措施，用来保证当前最核心的业务。

3）最近几年的双十一，为什么提前一个多星期就已经有双十一当天的价格了？预售分流。

在应用层面同样有很多其他的方案来优化，达到尽量减轻数据库的压力的目的，比如限流，或者引入 MQ 削峰，等等等等。

为什么同样用 MySQL，有的公司可以扛住百万千万级别的并发，而有的公司几百个并发都扛不住，关键在于怎么用。所以，用数据库慢，不代表数据库本身慢，有的时候还要往上层去优化。

后话

MySQL 专题到这个篇章就正式结束了，基本上是按照脑图的方向来，所以大家可以对着脑图以及我的博文来进行 MySQL 的复习，基本上面试的问题都有涉及，编写一个专题确实是费脑又费精力费时间的事情，我还是需要大家的关注和点赞来支撑一下哈哈哈~

如果大家觉得写得还有点东西的话帮忙关注一下我的公众号，并且在后台给我留言希望我写哪个专题的东西（现学现卖的如果有什么不对的地方也请帮忙指正，万分感谢），人多的话马上安排上~

还是那样，修整一段时间后会先在公众号推送脑图，然后根据脑图来拟专题的提纲，这样我写得不会云里雾里，大家也会比较有方向地看我的博文，再次感谢大家的支持~

By the way

有问题？可以给我留言或私聊
有收获？那就顺手点个赞呗~

当然，也可以到我的公众号下「6曦轩」，

回复“学习”，即可领取一份
【Java工程师进阶架构师的视频教程】~

回复“面试”，可以获得：
【本人呕心沥血整理的 Java 面试题】

回复“MySQL脑图”，可以获得
【MySQL 知识点梳理高清脑图】

由于我咧，科班出身的程序员，php，Android以及硬件方面都做过，不过最后还是选择专注于做 Java，所以有啥问题可以到公众号提问讨论（技术情感倾诉都可以哈哈哈），看到的话会尽快回复，希望可以跟大家共同学习进步，关于服务端架构，Java 核心知识解析，职业生涯，面试总结等文章会不定期坚持推送输出，欢迎大家关注~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

这是why技术的第36篇原创文章

上面的图片是我上周末在家拍的。以后的文章里面我的第一张配图都用自己随手拍下的照片吧。分享生活，分享技术，哈哈。

阳台上的花开了，成都的春天快来了，疫情也应该快要过去了吧。

最近在看《霍乱时期的爱情》，不知道为什么和《大话西游》联系了起来，所以你可以看到玻璃上的倒影，是我在看《大话西游》。

谁都曾经有过大闹天宫的梦想，爱上层楼的忧愁，但是早晚有一天，你也会像他转身之后一样，走在路上，像一条狗。

好了，说回文章

让你看看“浮动垃圾”

上《面试官:你说你熟悉jvm?那你讲一下并发的可达性分析》这篇文章主要聊了 jvm 的可达性分析算法。

借助“三色标记”大法分析了垃圾回收线程扫描的过程中，用户线程同时执行修改引用关系的操作时，可能会出现的“对象消失”问题，以及其对应的两种解决方案

增量更新和原始快照。

在文章中我写道：对象关系图的变化会导致出现两种情况一是“浮动垃圾”，二是“对象消失”。大概率的情况下面试官更加关心第二种情况，因为第二种情况会给程序带来异常。接下来我就做动图分析了“对象消失”的情况

但是我是万万没想到呀，读者更关心的是“浮动垃圾”。有的读者就来问我，浮动垃圾是怎么产生的，你倒是给个图啊。

像我这样的又暖又有料的硬核原创作者，你说你要，那我肯定是要给你的。

下面就给你补上“浮动垃圾”的动图：

当并发标记完成后，对象图就变成了下面这个样子：

你看出来了吧。对象7，8，4，11，10都是浮动垃圾。因为他们被标记成了黑色，所以逃过了本次垃圾回收。

什么？你问我为什么黑色就不回收了？你个假粉丝，建议你先去读一读上周的文章。

G1垃圾回收时新对象怎么处理？
===============

有的读者就提出了另外的很有探讨性的问题：

why哥你好，你《面试官:你说你熟悉jvm?那你讲一下并发的可达性分析》这篇文章主要解决了在并发标记阶段，GC线程和用户线程并发执行时，用户线程修改了对象引用关系，导致“对象消失”的问题。G1是采用原始快照加写前屏障的方式解决这个问题的。

但是我还有另外的一个问题：用户线程执行时不仅修改了对象引用关系，还新分配了新对象，我觉得这个情况是非常常见的，G1是如何找到并处理这些对象的呢？

换句话说，就是文章标题啦：G1收集器是怎么知道这些对象是什么时候应该进行垃圾标记的？

这是一个好问题，一看就是用心读了文章并带有自己的思考。很不错。

这位读者的问题属于第一个问题的连环炮，让我突然有了一种掉进了面试官布好的天罗地网里面的感觉。

面试官先故意漏出破绽，让你聊“对象消失”、“三色标记”、“增量更新”。然后等你得意洋洋的时候，突然抛出第二个问题：刚刚对象消失的问题回答的不错，那如果并发标记的时候用户线程分配了新对象，G1是怎么处理的呢？

说实话，我觉得只要你简历上没有写精通jvm，面试一般问到这种程度的我觉得是真的到了探讨的地步了。答的上来加分，答不上来也不扣分。

遥想2016年，我刚毕业，只身闯北京的时候，一连面试了9家公司，没有一家公司聊到 jvm （当然我当时面的是初级开发）。现在不一样了，不知道什么时候 jvm 从进阶面试题，变成了初级面试题。面试阶段如果没有问 jvm ，就感觉不是一次完整的面试。

我觉得就这几年面试题的变化，其实也就是反映了一个现象：想入行的人越来越多，导致入行的门槛越来越高。

不是jvm的地位变了，而是门槛越来越高了。

好了，瞎逼逼完了，接下来我们聊聊G1。

初识Garbage First(G1)

我不知道你是怎么知道G1的，但是我是从周志明大大的《深入理解Java虚拟机(第2版)》这本书里面第一次知道G1收集器的。

我记得当时读到G1的时候感觉这就是天书啊。

因为作者在介绍G1之前介绍了很多其他的收集器，我先给你看一下目录，带你回顾回顾：

可以看到，3.5.1节到3.5.6节介绍的收集器工作的时候， Java 堆的内存布局是按照新生代，老年代进行整体的区域划分的。

但是到了G1收集器， Java 堆的内存布局就有点”妖艳贱货”了。然后就有点越来越看不懂了，当时的场景就像下面这样：

它虽然还是保留的有新生代和老年代的概念，但是新生代和老年代之前再也不是区域上的隔离了。它将整个 Java 堆划分为多个大小相等的独立区域，叫做 Region 。而新生代和老年代就是由一个个 Region 动态组成的区域，它们可以是不连续的区间。

每一个 Region 都可以根据需要，扮演新生代的 Eden 空间，Survivor 空间，或者老年代空间。除此之外它还有一类特殊的区域叫做 Humongous，专门用来存储大对象。

上面说的是啥意思呢？其实用图片看起来就非常直观了：

比如对于 CMS，使用的堆内存结构如下：

可以看到上面的图片中不论是年轻代、老年代都是逻辑上连续的空间（但是不要求物理上的连续）。

而G1的堆内存被划分为多个大小相等的 Region ，但是 Region 的总个数在 2048 个左右，默认是 2048 。对于一个 Region 来说，是逻辑连续的一段空间，其大小的取值范围是 1MB 到 32MB 之间。

结构如下：

上面的E、S和没有写字母的蓝色方块（可以理解为old）没啥说的。

但是可以看到H是以往的垃圾收集器中没有的概念，它代表 Humongous，这表示这些 Region 存储的是巨型对象（humongous object，H-obj），当新建对象大小超过 Region 大小一半时，直接在新的一个或多个连续 Region 中分配，并标记为H。

说实话上面的这概念已经“烂大街”了，任何一篇写G1都会聊到，包括本文也是。

没办法啊，朋友们，这是引子，必须得先聊几句。就像斗地主，你第一手牌能直接出王炸吗？不能啊，你不得先来一个对三，循序渐进啊。

下面我送你一个小彩蛋吧。

注意到我上面说的几个数据了吗，2048个左右，1MB到32MB，这些数据是哪里来的呢，我说你就信了吗？

很多文章聊到G1的时候都只是说堆内存被划分为多个大小相等的 Region ， Region 大小的取值范围为 1MB 到 32MB ，但是并没有提到 2048 这回事，我来给你寻根问祖一下：

我找到的第一个数据来源于上面的这篇论文，即文末的资料4：

The goal is to have around 2048 regions for the total heap.

这篇论文的作者是Monica Beckwith，你可以去搜一下，她（是的，我没打错，是个妹子）担任过Oracle G1 垃圾收集器性能团队 Leader，权威吧。

第二个数据来源当然是源码了，更权威吧：

http://hg.openjdk.java.net/jdk/jdk/file/fa2f93f99dbc/src/hotspot/share/gc/g1/heapRegionBounds.hpp

知道这个2048重要吗？我觉得不重要。

但是知道了就更牛逼呀！当妹子聊到2048的时候她只知道这是一个游戏，你要告诉她这个数字也是G1的Region的默认个数。

事了拂衣去,深藏功与名。

G1的工作步骤
=======

这一部分，也是耳熟能详的部分，但是忍一忍，马上就要到你高呼：卧槽，牛逼的部分了。

众所周知，一般我们说G1的收集过程分为下面这四个步骤（下面四个步骤的描述来自于《深入理解Java虚拟机(第3版)》）：

说实在的，下面的描述确实看的让人很懵逼的。面试的过程中问到这一部分的时候，我相信大多数朋友都是硬背下来的。

所以，本文的目的就是为了让你理解下面这几个阶段的具体过程。

这么说吧，如果看完这篇文章你还是没搞懂上面这几个阶段的话，那你再读一遍。

再读一遍，还是没懂的话，那我这篇文章就算写失败了。

初始标记(Initial Marking)：这阶段仅仅只是标记GC Roots能直接关联到的对象并修改TAMS(Next Top at Mark Start)的值，让下一阶段用户程序并发运行时，能在正确的可用的Region中创建新对象，这阶段需要停顿线程，但是耗时很短。

而且是借用进行Minor GC的时候同步完成的，所以G1收集器在这个阶段实际并没有额外的停顿。

并发标记(Concurrent Marking)：从GC Roots开始对堆的对象进行可达性分析，递归扫描整个堆里的对象图，找出存活的对象，这阶段耗时较长，但是可以与用户程序并发执行。

当对象图扫描完成以后，还要重新处理SATB记录下的在并发时有引用变动的对象。

最终标记(Final Marking)：对用户线程做另一个短暂的暂停，用于处理并发阶段结束后仍遗留下来的最后那少量的 SATB 记录。

筛选回收(Live Data Counting and Evacuation)：负责更新 Region 的统计数据，对各个 Region 的回收价值和成本进行排序，根据用户所期望的停顿时间来制定回收计划。

可以自由选择任意多个 Region 构成回收集，然后把决定回收的那一部分 Region 的存活对象复制到空的 Region 中，再清理掉整个旧 Region 的全部空间。

这里的操作涉及存活对象的移动，是必须暂停用户线程，由多条收集器线程并行完成的。

上面虽然有4个阶段，但是从上帝视角，我们可以把它分为两大部分，或者说从整个算法的角度，我们可以切分为两大部分：

1.Global Concurrent Marking：全局并发标记。

2.Evacuation Pauses：该阶段是负责把一部分Region里的活对象拷贝到空Region里面去，然后回收原本的Region空间。

为什么我敢这样去划分呢？

一部分原因来自这篇论文中：

《Garbage-First Garbage Collection》这篇论文是 sun 实验室在 2004 年发布的第一篇关于 G1 的论文。够权威吧？

该论文中，2.3小节就是介绍 Evacuation Pauses ，2.5小节就是介绍 Concurrent Marking ，下面是部分内容截图：

另一部分原因是 R大 也这样说的(见文末参考资料)。

接下来，要回答读者提出的问题，我们就需要了解全局并发标记阶段。

全局并发标记

这一节就是回答这个问题：用户线程执行的时候不仅修改了对象引用关系，还新分配了新对象，G1 是如何找到并处理这些对象的呢？

要回答这个问题，就涉及到 TAMS 了。前面我引用的书里说：

初始标记（Initial Marking）：这阶段仅仅只是标记 GC Roots 能直接关联到的对象并修改 TAMS（Next Top at Mark Start）的值，让下一阶段用户程序并发运行时，能在正确的可用的 Region 中创建新对象。

这句话，每个字都能看懂，连在一起读，也品出点儿味道，但是总感觉似懂非懂的样子。

什么是 TAMS？什么是正确可用的 Region？新对象是创建在 Region 中的哪个位置的？

我们先从论文入手，我捡关键点给你说：

1.有两个 bitmap。

2.一个叫 previous，一个叫 next。

3.previous bitmap 是 concurrent marking 阶段完成后的最后一个 bitmap。（有点绕，后面会解释）。

4.next bitmap 是当前将要或正在进行的 concurrent marking 的结果。

5.当标记完成后，两个 bitmap 会交换角色。

1.标记周期的第一个阶段就是清理 next bitmap。

2.然后，初始标记阶段 Stop The World（后面简称STW），目的是标记 GC Roots 能直接关联到的对象。该阶段借助 Minor GC 完成，没有额外的停顿。

3.每个 Region 包含两个 TAMS。

4.一个对应前一轮标记，一个对应下一次标记。

从论文中我们可以知道，G1的Concurrent Marking 用了两个 marking bitmap。

一个 previous Bitmap 记录的是上一轮 Concurrent Marking 后的对象标记状态，因为上一轮已经完成，所以这个bitmap的信息可以直接使用。

一个 next Bitmap 记录的是当前这一轮 Concurrent Marking 的结果。这个bitmap是当前将要或正在进行的 Concurrent Marking 的结果，尚未完成，所以还不能使用。

我们可以假设一次并发标记变成后的 Bitmap（previous Bitmap） 大概长这样:

白色地址之间是可以回收的对象，灰色地址之间是不可以回收的对象。

除了两个 bitmap 外，还有两个 TAMS（top at mark start）。每个 Region 都有两个 TAMS，分别是 previous TAMS 和 next TAMS。

bitmap 和 TAMS 可以用下面的图片来表示：

首先我们可以看到 bottom 和 top 之间是一个 Region 已使用的部分。Top 到 end 之前是一个 Region 未使用的部分。

另外可以看到上面我留了四个问号，接下我们的目的就是填补这些问号。当这些问号被填上之后，所有的问题都会迎刃而解。

两个 Bitmap 和两个 TAMS 是怎么工作的呢？

接下来按照：

初始标记（Initial Marking）

并发标记（Concurrent Marking）

最终标记（final marking，也叫Remark）

清理阶段（Cleanup）

这四个阶段作图说明

初始标记（Initial Marking）

从图片可以看到初始标记阶段 nextBitmap 是清空状态，没有标记任何存活的对象。

接着我们再次回到书中的描述里，我给你逐字描述清楚：

初始标记（Initial Marking）：这阶段仅仅只是标记 GC Roots 能直接关联到的对象并修改 TAMS（Next Top at Mark Start）的值，让下一阶段用户程序并发运行时，能在正确的可用的 Region 中创建新对象。

GC Roots 能直接关联到的对象：就是一个 Region 已经使用过的部分，所以在 Bottom 与 top 之间。

更新：上面这句话是错误的，详情见链接
修改 TAMS 的值：就是让此时的 prevTAMS 指向 Bottom ，也就是一个 Region 内存地址起始值。让此时的 nextTAMS 指向 Top。Top 实际上就是一个 Region 未分配区域和已分配区域的分界点。

**正确的可用的 Region **：对一个 Region 来说，当上面的 nextBitmap 为空、4个指针都准备就绪后，这个 Region 在下一阶段用户程序并发运行时，就是一个正确的 Region。

下一阶段用户程序并发运行时，在正确的可用的 Region 中创建新对象是什么意思呢？

下一阶段用户程序并发运行时指的就是并发标记阶段。

并发标记（Concurrent Marking）

先看前面引用的书中描述：

并发标记（Concurrent Marking）：从 GC Roots 开始对堆的对象进行可达性分析，递归扫描整个堆里的对象图，找出存活的对象，这阶段耗时较长，但是可以与用户程序并发执行。当对象图扫描完成以后，还要重新处理 SATB 记录下的在并发时有引用变动的对象。

再看动图：

从 GC Roots 开始对堆的对象进行可达性分析，递归扫描整个堆里的对象图，找出存活的对象：

意思就是说在并发标记阶段， GC 线程工作在 prevTAMS 和 NextTAMS 之间，对堆里的对象进行可达性分析（回想一下“三色标记”），标记完成后， NextBitmap 就有对应有值了（里面放的是地址值），黑色对应的是存活对象，白色对应的垃圾对象。

这样就找出存活对象了。

但是书中并没有提及用户线程分配对象的情况。所以读者提出的问题，在书中也找不到明确的答案。

答案就是： NextTAMS 与 Top 之间的对象，就是本次并发标记阶段用户线程新分配的对象，它们是隐式存活的。

为什么这么说？你去品一品论文里面我框起来的这句话。

但是面试官想要的是这一句话的答案吗？不是的。

你听到这个问题后，你先微微一皱眉，做出沉思状，然后轻轻说说一句：这个问题问的很好，我先组织一下语言。（先舔他一波）

然后你按照阶段把图画出来，指着给他讲 TAMS 和 Bitmap 是怎么工作的。

另外，关于 NextTAMS 与 Top 为什么是重叠的，也得补充说明一下：并发标记的前一个阶段是初始标记。由于初始标记是 STW 的，所以从动图中我们可以看到：并发标记开始，即初始标记结束的时候， NextTAMS 与 Top 是重叠的。

随着并发标记过程的进行， NextBitmap 被填充上了值。而 NextTAMS 与 Top 之间的区域越来越大，这就是用户线程在并发标记阶段分配的新对象。

同时通过下面的图我们可以看到， GC 线程的工作区间和用户线程的工作区间是有重叠的（用工作区间这个概念去理解其中的一些细节不一定正确，但是可以这样抽象的认为，方便理解）。

而重叠的部分，就是可能产生“对象消失”的部分。对G1来说，就是原始快照（STAB）加写前屏障（Pre-Wirte Barrier）工作的部分。

所以这就是书里为什么说：当 GC 线程扫描完对象图后，还需要重新处理 STAB 记录下的在并发时有引用变动的对象。

最终标记（Remark）

书中是这样的写的：

最终标记（Final Marking）：对用户线程做另一个短暂的暂停，用于处理并发阶段结束后仍遗留下来的最后那少量的 SATB 记录。

最终标记阶段，由于是 STW 的，所以该阶段对应的图是并发标记阶段完成后的图，如下：

处理并发阶段结束后仍遗留下来的最后那少量的 SATB 记录是什么意思呢？

你想，并发标记阶段， GC 线程完成对象图的扫描之后，还会去处理 SATB 记录下的在并发时有引用变动的对象。

在处理 SATB 记录的数据的时候，由于用户线程可能还是在继续修改对象图，继续在产生 SATB 数据，所以还是会有一小部分的 SATB 数据，所以才需要一个短暂的暂停。

清理阶段（Cleanup）

书里写的是筛选回收阶段。其实就包含了清理阶段和回收阶段。这里我们只讨论清理阶段，不讨论回收。

在这个阶段， NextBitmap 和 PrevBitmap 会交换位置：

所以，我们的图就变成了下面的样子：

可以看到，NextBitmap 和 PrevBitmap 交换了位置，NextTAMS 和 PrevTAMS 交换了位置。

而 Region 中， Bitmap 白色部分对应的已使用内存变成了浅灰色。它仅仅是标记了出来，并没有进行清扫操作。

需要注意的是：清理阶段不拷贝任何对象

引用R大的回答来描述这个阶段：

清点和重置标记状态。这个阶段有点像 mark-sweep 中的 sweep 阶段，不过不是在堆上 sweep 实际对象，而是在 marking bitmap 里统计每个 Region 被标记为活的对象有多少。这个阶段如果发现完全没有活对象的 Region 就会将其整体回收到可分配 Region 列表中。

好了，到这里我们就能把前面的那张图给填上了：

然后再看一下论文中的这张图片，你就会发现，我上面的过程都是基于这张图片去分析的，图中展示了两个循环， A-B-C ， D-E-F 。其中 E、F 过程就是 B、C 过程的重复：

我让上面的图片动起来，请细细品。请注意各个阶段 PrevTAMS 、 NextTAMS 指针的交换、 PrevBitmap 和 NextBitmap 位置的交换：

如果一次看不懂，就再看一次。看的时候结合上面的长图和动图一起分析，效果更佳。

参考资料：

1.https://max.book118.com/html/2018/0815/7043143036001143.shtm

2.https://www.oracle.com/webfolder/technetwork/tutorials/obe/java/G1GettingStarted/index.html

3.https://www.oracle.com/technetwork/java/javase/tech/g1-intro-jsp-135488.html

4.https://www.infoq.com/articles/G1-One-Garbage-Collector-To-Rule-Them-All/

5.https://hllvm-group.iteye.com/group/topic/44381

6.《深入理解Java虚拟机(第三版)》

最后说一句（求关注）

本文是对《面试官:你说你熟悉jvm?那你讲一下并发的可达性分析》这篇文章的补充说明。如果你没看过，我建议你去看看。

我觉得有些知识点仅仅靠文章和图片是很难说清楚的，所以我费劲的做了动图。

为了做这篇文章和上篇文章中的几张动图，加起来我截了 80 多张图。你知道我为了把每张图截的一个像素都不差，我有多努力吗？

截的我眼球布满了血丝，眼睛都快瞎了，你不关注一波？

我四级半的英语水平，为了文章的正确性，强行啃英文论文，你不感动吗？

点个关注呀，别白嫖我啊，大哥。写文章很辛苦的，需要来点正反馈。

才疏学浅，难免会有纰漏，如果你发现了错误的地方，还请你留言给我指出来，我对其加以修改。

感谢您的阅读，我坚持原创，十分欢迎并感谢您的关注。

我是why技术，一个不是大佬，但是喜欢分享，又暖又有料的四川好男人。

以上。

欢迎关注公众号【why技术】,坚持输出原创。分享技术、品味生活，愿你我共同进步。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

前言

• 这是 Android 10 源码分析系列的第 2 篇
• 分支：android-10.0.0_r14
• 全文阅读大概 10 分钟

上一篇文章介绍了 0xA01 Android 10 源码分析：APK 是如何生成的，这篇文章接着介绍如何安装 APK，需要说一下 Android 10 及更高版本中, 安装器 PackageInstaller 源码位置有所变动

PackageInstaller 源码所在位置

PackageInstaller 是系统内置的应用程序，用于安装和卸载应用

在 Android 9 及更低版本中，软件包安装和权限控制功能包含在 PackageInstaller 软件包 (//packages/apps/PackageInstaller) 中。在 Android 10 及更高版本中，权限控制功能位于单独的软件包 PermissionController (//packages/apps/PermissionController)，这两个软件包在 Android 10 中的位置如下图所示，更多信息点击这里前往 Android 权限

Android 9 及更低版本中 ：

软件包安装和权限控制功能源码路径：packages/apps/PackageInstaller

Android 10 及更高版本：

• 权限控制功能 PermissionController 源码路径：packages/apps/PermissionController/
• 安装器 PackageInstaller 源码路径：frameworks/base/packages/PackageInstaller/

在 Android 系统不同的目录存放不同类型的应用

• /system/framwork：保存的是资源型的应用程序，它们用来打包资源文件
• /system/app：保存系统自带的应用程序
• /data/app：保存用户安装的应用程序
• /data/data：应用数据目录
• /data/app-private：保存受DRM保护的私有应用程序
• /vendor/app：保存设备厂商提供的应用程序

查看 PackageInstaller 源码方式

• AOSP-PackageInstaller: 包含了安装器 PackageInstaller(7.1.2、8.1.0、9.0.0、10.0.0) 的源码，可以切换分之查看，跟随 Android 版本更新，你永远可以看到最新的源代码
  
• aospxref：这是一个在线查看 Android 源码网站，服务器在阿里云访问速度很快，文末有关这个网站的介绍
• googlesource-PackageInstaller：这是安装器 PackageInstaller 在 googlesource 上的地址

1. APK 的安装方式

安装 APK 主要分为以下三种场景

• 安装系统应用：系统启动后调用 PackageManagerService.main() 初始化注册解析安装工作

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

java复制代码public static PackageManagerService main(Context context, Installer installer,
        boolean factoryTest, boolean onlyCore) {
    // Self-check for initial settings.
    PackageManagerServiceCompilerMapping.checkProperties();

    PackageManagerService m = new PackageManagerService(context, installer,
            factoryTest, onlyCore);
    m.enableSystemUserPackages();
    ServiceManager.addService("package", m);
    final PackageManagerNative pmn = m.new PackageManagerNative();
    ServiceManager.addService("package_native", pmn);
    return m;
}

• 通过 adb 安装：通过 pm 参数，调用 PM 的 runInstall 方法，进入 PackageManagerService 安装安装工作
• 通过系统安装器 PackageInstaller 进行安装：先调用 InstallStart 进行权限检查之后启动 PackageInstallActivity，调用 PackageInstallActivity 的 startInstall 方法，点击 OK 按钮后进入 PackageManagerService 完成拷贝解析安装工作

所有安装方式大致相同，最终就是回到 PackageManagerService 中，安装一个 APK 的大致流程如下：

• 拷贝到 APK 文件到指定目录
• 解压缩 APK，拷贝文件，创建应用的数据目录
• 解析 APK 的 AndroidManifest.xml 文件
• 向 Launcher 应用申请添加创建快捷方式

本文主要来分析通过安装器 PackageInstaller 安装 APK，这是用户最常用的一种方式

2. PackageInstaller 的入口

下面代码一定不会很陌生，这就是我们常用的安装 APK 的代码（PS: 关于静默安装我会后续分享在逆向开发相关的文章）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

scss复制代码Intent intent = new Intent(Intent.ACTION_VIEW);
intent.setFlags(Intent.FLAG_ACTIVITY_NEW_TASK);

/*
* 自Android N开始，是通过FileProvider共享相关文件，但是Android Q对公
* 有目录 File API进行了限制，只能通过Uri来操作
*/
if(Build.VERSION.SDK_INT >= Build.VERSION_CODES.Q){
    // filePath是通过ContentResolver得到的
    intent.setDataAndType(Uri.parse(filePath) ,"application/vnd.android.package-archive");
    intent.addFlags(Intent.FLAG_GRANT_READ_URI_PERMISSION);
}else if (Build.VERSION.SDK_INT >= Build.VERSION_CODES.N) {
    intent.setFlags(Intent.FLAG_GRANT_READ_URI_PERMISSION);
    Uri contentUri = FileProvider.getUriForFile(mContext, "com.dhl.file.fileProvider", file);
    intent.setDataAndType(contentUri, "application/vnd.android.package-archive");
} else {
    intent.setDataAndType(Uri.fromFile(file), "application/vnd.android.package-archive");
}
startActivity(intent);

// 需要在AndroidManifest添加权限
<uses-permission android:name="android.permission.REQUEST_INSTALL_PACKAGES" />

通过 intent.setDataAndType 方法指定 Intent 的数据类型为 application/vnd.android.package-archive，隐式匹配的 Activity 为 InstallStart：

frameworks/base/packages/PackageInstaller/AndroidManifest.xml

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

ini复制代码<activity android:name=".InstallStart"
        android:theme="@android:style/Theme.Translucent.NoTitleBar"
        android:exported="true"
        android:excludeFromRecents="true">
    <intent-filter android:priority="1">
        <action android:name="android.intent.action.VIEW" />
        <action android:name="android.intent.action.INSTALL_PACKAGE" />
        <category android:name="android.intent.category.DEFAULT" />
        <data android:scheme="content" />
        <data android:mimeType="application/vnd.android.package-archive" />
    </intent-filter>
    <intent-filter android:priority="1">
        <action android:name="android.intent.action.INSTALL_PACKAGE" />
        <category android:name="android.intent.category.DEFAULT" />
        <data android:scheme="package" />
        <data android:scheme="content" />
    </intent-filter>
    <intent-filter android:priority="1">
        <action android:name="android.content.pm.action.CONFIRM_INSTALL" />
        <category android:name="android.intent.category.DEFAULT" />
    </intent-filter>
</activity>

• 本文分析的是 10.0 的源码，在 8.0、9.0、10.0 等等版本中隐式匹配的 Activity 是 InstallStart，7.0 隐式匹配的 Activity 是 PackageInstallerActivity
• 安装器 PackageInstaller 的入口 Activity 是 InstallStart，定义了两个 scheme：content 和 package

3. APK 的安装流程

通过上面方式找到了入口 Activity，下面我们来查看一下 APK 是如何安装的

3.1 InstallStart

主要工作：

1. 判断是否勾选“未知来源”选项，若未勾选跳转到设置安装未知来源界面
2. 对于大于等于 Android 8.0 版本，会先检查是否申请安装权限，若没有则中断安装
3. 判断 Uri 的 Scheme 协议，若是 content 则调用 InstallStaging, 若是 package 则调用 PackageInstallerActivity

当我们调用上面安装代码来安装 APK 时。会跳转到 InstallStart, 并调用它的 onCreate 方法：

frameworks/base/packages/PackageInstaller/src/com/android/packageinstaller/InstallStart.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

java复制代码@Override
protected void onCreate(@Nullable Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);
    ...

    final boolean isSessionInstall =
            PackageInstaller.ACTION_CONFIRM_INSTALL.equals(intent.getAction());
    ...

    final ApplicationInfo sourceInfo = getSourceInfo(callingPackage);
    final int originatingUid = getOriginatingUid(sourceInfo);
    boolean isTrustedSource = false;
    // 判断是否勾选“未知来源”选项
    if (sourceInfo != null
            && (sourceInfo.privateFlags & ApplicationInfo.PRIVATE_FLAG_PRIVILEGED) != 0) {
        isTrustedSource = intent.getBooleanExtra(Intent.EXTRA_NOT_UNKNOWN_SOURCE, false);
    }
    if (!isTrustedSource && originatingUid != PackageInstaller.SessionParams.UID_UNKNOWN) {
        final int targetSdkVersion = getMaxTargetSdkVersionForUid(this, originatingUid);
        // 如果targetSdkVerison小于0中止安装
        if (targetSdkVersion < 0) {
            Log.w(LOG_TAG, "Cannot get target sdk version for uid " + originatingUid);
            mAbortInstall = true;

            // 如果targetSdkVersion大于等于26（8.0）, 且获取不到REQUEST_INSTALL_PACKAGES权限中止安装
        } else if (targetSdkVersion >= Build.VERSION_CODES.O && !declaresAppOpPermission(
                originatingUid, Manifest.permission.REQUEST_INSTALL_PACKAGES)) {
            Log.e(LOG_TAG, "Requesting uid " + originatingUid + " needs to declare permission "
                    + Manifest.permission.REQUEST_INSTALL_PACKAGES);
            mAbortInstall = true;
        }
    }

    ...

    // 如果设置了ACTION_CONFIRM_PERMISSIONS，则调用PackageInstallerActivity。
    if (isSessionInstall) {
        nextActivity.setClass(this, PackageInstallerActivity.class);
    } else {
        Uri packageUri = intent.getData();
        // 判断Uri的Scheme协议是否是content
        if (packageUri != null && packageUri.getScheme().equals(
                ContentResolver.SCHEME_CONTENT)) {
            // [IMPORTANT] This path is deprecated, but should still work.
            // 这个路径已经被起用了，但是仍然可以工作

            // 调用InstallStaging来拷贝file/content，防止被修改
            nextActivity.setClass(this, InstallStaging.class);
        } else if (packageUri != null && packageUri.getScheme().equals(
                PackageInstallerActivity.SCHEME_PACKAGE)) {
            // 如果Uri中包含package，则调用PackageInstallerActivity
            nextActivity.setClass(this, PackageInstallerActivity.class);
        } else {
            // Uri不合法
            Intent result = new Intent();
            result.putExtra(Intent.EXTRA_INSTALL_RESULT,
                    PackageManager.INSTALL_FAILED_INVALID_URI);
            setResult(RESULT_FIRST_USER, result);
            nextActivity = null;
        }
    }
    if (nextActivity != null) {
        startActivity(nextActivity);
    }
    finish();
}

根据 Uri 的 Scheme 协议，若是 content 则调用 InstallStaging，查看 InstallStaging 的 onResume方法：

frameworks/base/packages/PackageInstaller/src/com/android/packageinstaller/InstallStaging.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

scss复制代码@Override
protected void onResume() {
    super.onResume();
    if (mStagingTask == null) {
        if (mStagedFile == null) {
            // 创建临时文件 mStagedFile 用来存储数据
            try {
                mStagedFile = TemporaryFileManager.getStagedFile(this);
            } catch (IOException e) {
                showError();
                return;
            }
        }
        // 启动 StagingAsyncTask，并传入了content协议的Uri
        mStagingTask = new StagingAsyncTask();
        mStagingTask.execute(getIntent().getData());
    }
}

1. 创建临时文件 mStagedFile 用来存储数据
2. 启动 StagingAsyncTask，并传入了 content 协议的 Uri

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

scala复制代码private final class StagingAsyncTask extends AsyncTask<Uri, Void, Boolean> {
    @Override
    protected Boolean doInBackground(Uri... params) {
        ...
        Uri packageUri = params[0];
        try (InputStream in = getContentResolver().openInputStream(packageUri)) {
            ...
            // 将packageUri（content协议的Uri）的内容写入到mStagedFile中
            try (OutputStream out = new FileOutputStream(mStagedFile)) {
                byte[] buffer = new byte[1024 * 1024];
                int bytesRead;
                while ((bytesRead = in.read(buffer)) >= 0) {
                    // Be nice and respond to a cancellation
                    if (isCancelled()) {
                        return false;
                    }
                    out.write(buffer, 0, bytesRead);
                }
            }
        } catch (IOException | SecurityException | IllegalStateException e) {
            Log.w(LOG_TAG, "Error staging apk from content URI", e);
            return false;
        }
        return true;
    }

    @Override
    protected void onPostExecute(Boolean success) {
        if (success) {
            // 如果写入成功，调用DeleteStagedFileOnResult
            Intent installIntent = new Intent(getIntent());
            installIntent.setClass(InstallStaging.this, DeleteStagedFileOnResult.class);
            installIntent.setData(Uri.fromFile(mStagedFile));
            ...
            startActivity(installIntent);
            InstallStaging.this.finish();
        } else {
            showError();
        }
    }
}

1. doInBackground 方法中将 packageUri（content 协议的 Uri）的内容写入到 mStagedFile 中
2. 如果写入成功，调用 DeleteStagedFileOnResult 的 OnCreate 方法：

frameworks/base/packages/PackageInstaller/src/com/android/packageinstaller/DeleteStagedFileOnResult.java

1
2
3
4
5
6
7
8
9
10

less复制代码protected void onCreate(@Nullable Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);
    if (savedInstanceState == null) {
        // 启动PackageInstallerActivity
        Intent installIntent = new Intent(getIntent());
        installIntent.setClass(this, PackageInstallerActivity.class);
        installIntent.setFlags(Intent.FLAG_ACTIVITY_NO_ANIMATION);
        startActivityForResult(installIntent, 0);
    }
}

经过分析 InstallStaging 主要起了中转作用，将 content 协议的 Uri 转换为 File 协议，最后跳转到 PackageInstallerActivity

3.2 PackageInstallerActivity

主要工作：

1. 显示安装界面
2. 初始化安装需要用的各种对象，比如 PackageManager、IPackageManager、AppOpsManager、UserManager、PackageInstaller 等等
3. 根据传递过来的 Scheme 协议做不同的处理
4. 检查是否允许、初始化安装
5. 在准备安装的之前，检查应用列表判断该应用是否已安装，若已安装则提示该应用已安装，由用户决定是否替换
6. 在安装界面，提取出 APK 中权限信息并展示出来
7. 点击 OK 按钮确认安装后，会调用 startInstall 开始安装工作

PackageInstallerActivity 才是应用安装器 PackageInstaller 真正的入口 Activity，查看它的 onCreate 方法：

frameworks/base/packages/PackageInstaller/src/com/android/packageinstaller/PackageInstallerActivity.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

scss复制代码protected void onCreate(Bundle icicle) {
    getWindow().addSystemFlags(SYSTEM_FLAG_HIDE_NON_SYSTEM_OVERLAY_WINDOWS);
    super.onCreate(null);
    // 初始化安装需要用到的对象
    mPm = getPackageManager();
    mIpm = AppGlobals.getPackageManager();
    mAppOpsManager = (AppOpsManager) getSystemService(Context.APP_OPS_SERVICE);
    mInstaller = mPm.getPackageInstaller();
    mUserManager = (UserManager) getSystemService(Context.USER_SERVICE);

    // 根据Uri的Scheme做不同的处理
    boolean wasSetUp = processPackageUri(packageUri);
    if (!wasSetUp) {
        return;
    }
    // 显示安装界面
    bindUi();
    // 检查是否允许安装包，如果允许则启动安装。如果不允许显示适当的对话框
    checkIfAllowedAndInitiateInstall();
}

主要做了对象的初始化，解析 Uri 的 Scheme，初始化界面，安装包检查等等工作，接着查看一下 processPackageUri 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

java复制代码private boolean processPackageUri(final Uri packageUri) {
    mPackageURI = packageUri;
    final String scheme = packageUri.getScheme();
    // 根据这个Scheme协议分别对package协议和file协议进行处理
    switch (scheme) {
        case SCHEME_PACKAGE: {
            try {
                // 通过PackageManager对象获取指定包名的包信息
                mPkgInfo = mPm.getPackageInfo(packageUri.getSchemeSpecificPart(),
                        PackageManager.GET_PERMISSIONS
                                | PackageManager.MATCH_UNINSTALLED_PACKAGES);
            } catch (NameNotFoundException e) {
            }
            if (mPkgInfo == null) {
                Log.w(TAG, "Requested package " + packageUri.getScheme()
                        + " not available. Discontinuing installation");
                showDialogInner(DLG_PACKAGE_ERROR);
                setPmResult(PackageManager.INSTALL_FAILED_INVALID_APK);
                return false;
            }
            mAppSnippet = new PackageUtil.AppSnippet(mPm.getApplicationLabel(mPkgInfo.applicationInfo),
                    mPm.getApplicationIcon(mPkgInfo.applicationInfo));
        } break;

        case ContentResolver.SCHEME_FILE: {
            // 根据packageUri创建一个新的File
            File sourceFile = new File(packageUri.getPath());
            // 解析APK得到APK的信息，PackageParser.Package存储了APK的所有信息
            PackageParser.Package parsed = PackageUtil.getPackageInfo(this, sourceFile);

            if (parsed == null) {
                Log.w(TAG, "Parse error when parsing manifest. Discontinuing installation");
                showDialogInner(DLG_PACKAGE_ERROR);
                setPmResult(PackageManager.INSTALL_FAILED_INVALID_APK);
                return false;
            }
            // 根据PackageParser.Package得到的APK信息，生成PackageInfo
            mPkgInfo = PackageParser.generatePackageInfo(parsed, null,
                    PackageManager.GET_PERMISSIONS, 0, 0, null,
                    new PackageUserState());
            mAppSnippet = PackageUtil.getAppSnippet(this, mPkgInfo.applicationInfo, sourceFile);
        } break;

        default: {
            throw new IllegalArgumentException("Unexpected URI scheme " + packageUri);
        }
    }

    return true;
}

主要对 Scheme 协议分别对 package 协议和 file 协议进行处理

SCHEME_PACKAGE：

• 在 package 协议中调用了 PackageManager.getPackageInfo 方法生成 PackageInfo，PackageInfo 是跨进程传递的包数据（activities、receivers、services、providers、permissions等等）包含 APK 的所有信息

SCHEME_FILE：

• 在 file 协议的处理中调用了 PackageUtil.getPackageInfo 方法，方法内部调用了 PackageParser.parsePackage() 把 APK 文件的 manifest 和签名信息都解析完成并保存在了 Package，Package 包含了该 APK 的所有信息
• 调用 PackageParser.generatePackageInfo 生成 PackageInfo

接着往下走，都解析完成之后，回到 onCreate 方法，继续调用 checkIfAllowedAndInitiateInstall 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

scss复制代码private void checkIfAllowedAndInitiateInstall() {
    // 首先检查安装应用程序的用户限制，如果有限制并弹出弹出提示Dialog或者跳转到设置界面
    final int installAppsRestrictionSource = mUserManager.getUserRestrictionSource(
            UserManager.DISALLOW_INSTALL_APPS, Process.myUserHandle());
    if ((installAppsRestrictionSource & UserManager.RESTRICTION_SOURCE_SYSTEM) != 0) {
        showDialogInner(DLG_INSTALL_APPS_RESTRICTED_FOR_USER);
        return;
    } else if (installAppsRestrictionSource != UserManager.RESTRICTION_NOT_SET) {
        startActivity(new Intent(Settings.ACTION_SHOW_ADMIN_SUPPORT_DETAILS));
        finish();
        return;
    }

    // 判断如果允许安装未知来源或者根据Intent判断得出该APK不是未知来源
    if (mAllowUnknownSources || !isInstallRequestFromUnknownSource(getIntent())) {
        initiateInstall();
    } else {
        // 检查未知安装源限制,如果有限制弹出Dialog,显示相应的信息
        final int unknownSourcesRestrictionSource = mUserManager.getUserRestrictionSource(
                UserManager.DISALLOW_INSTALL_UNKNOWN_SOURCES, Process.myUserHandle());
        final int unknownSourcesGlobalRestrictionSource = mUserManager.getUserRestrictionSource(
                UserManager.DISALLOW_INSTALL_UNKNOWN_SOURCES_GLOBALLY, Process.myUserHandle());
        final int systemRestriction = UserManager.RESTRICTION_SOURCE_SYSTEM
                & (unknownSourcesRestrictionSource | unknownSourcesGlobalRestrictionSource);
        if (systemRestriction != 0) {
            showDialogInner(DLG_UNKNOWN_SOURCES_RESTRICTED_FOR_USER);
        } else if (unknownSourcesRestrictionSource != UserManager.RESTRICTION_NOT_SET) {
            startAdminSupportDetailsActivity(UserManager.DISALLOW_INSTALL_UNKNOWN_SOURCES);
        } else if (unknownSourcesGlobalRestrictionSource != UserManager.RESTRICTION_NOT_SET) {
            startAdminSupportDetailsActivity(
                    UserManager.DISALLOW_INSTALL_UNKNOWN_SOURCES_GLOBALLY);
        } else {
            // 处理未知来源的APK
            handleUnknownSources();
        }
    }
}

主要检查安装应用程序的用户限制，当 APK 文件不对或者安装有限制则调用 showDialogInner 方法，弹出 dialog 提示用户，显示相应的错误信息，来看一下都有那些错误信息

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

java复制代码// Dialog identifiers used in showDialog
private static final int DLG_BASE = 0;
// package信息错误
private static final int DLG_PACKAGE_ERROR = DLG_BASE + 2;
// 存储空间不够
private static final int DLG_OUT_OF_SPACE = DLG_BASE + 3;
// 安装错误
private static final int DLG_INSTALL_ERROR = DLG_BASE + 4;
// 用户限制的未知来源
private static final int DLG_UNKNOWN_SOURCES_RESTRICTED_FOR_USER = DLG_BASE + 5;
private static final int DLG_ANONYMOUS_SOURCE = DLG_BASE + 6;
// 在wear上不支持
private static final int DLG_NOT_SUPPORTED_ON_WEAR = DLG_BASE + 7;
private static final int DLG_EXTERNAL_SOURCE_BLOCKED = DLG_BASE + 8;
// 安装限制用户使用的应用程序
private static final int DLG_INSTALL_APPS_RESTRICTED_FOR_USER = DLG_BASE + 9;

如果用户允许安装未知来源，会调用 initiateInstall 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

ini复制代码private void initiateInstall() {
    String pkgName = mPkgInfo.packageName;
    // 检查设备上是否存在相同包名的APK
    String[] oldName = mPm.canonicalToCurrentPackageNames(new String[] { pkgName });
    if (oldName != null && oldName.length > 0 && oldName[0] != null) {
        pkgName = oldName[0];
        mPkgInfo.packageName = pkgName;
        mPkgInfo.applicationInfo.packageName = pkgName;
    }
    // 检查package是否已安装, 如果已经安装则显示对话框提示用户是否替换。
    try {
        mAppInfo = mPm.getApplicationInfo(pkgName,
                PackageManager.MATCH_UNINSTALLED_PACKAGES);
        if ((mAppInfo.flags&ApplicationInfo.FLAG_INSTALLED) == 0) {
            mAppInfo = null;
        }
    } catch (NameNotFoundException e) {
        mAppInfo = null;
    }
    // 初始化确认安装界面
    startInstallConfirm();
}