参考内容： 深入理解LINUX内核(第三版) linux 创建实时进程 深入 Linux 的进程优先级 Linux进程优先级系统——设置实时进程优先级 Linux 系统的调度基于分时技术，

参考内容： Linux内核开发_1_编译LInux内核 编译linux内核报错：flex: not foundscripts 编译kernel5.14报错fatal error: openssl/opensslv.h 编译内核错误——*** 没有规则可制作目标“debian/canonical-certs.pem” 内核错误：BTF: .tmp_vmlinux.btf: pahole (pahole) is not available # 切换到 root 账户 sudo su # 查看操作系统版本 cat /etc/issue # 查看 Linux 内核版本 cat /proc/version # 进入 root 账户目录 cd /home/root # 下载 Linux 内核源码 wget https://cdn.kernel.org/pub/linux/kernel/v5.x/linux-5.10.157.tar.xz # Linux 其它版本源码 https://www.kernel.org/ # xz 解压 xz -d linux-5.10.157.tar.xz # tar 解压到 /usr/src/linux-5.10.157 目录下 tar -xf linux-5.10.157.tar -C /usr/src/. # 进入源码目录 cd /usr/src/linux-5.10.157 # 查看源码结构 tree . -L 2 # 若没有 tree 命令，可以执行下面命令 # apt-get install tree # 配置编译选项 make menuconfig # 若没有 make，可以执行下面命令 # apt-get install make # 若执行 make 后报错找不到 curses.h，可以执行下面命令 # apt-get install libncurses5-dev # 若报错找不到 flex not found，可以执行下面两条命令 # apt-get install flex # apt-get install bison # 再次运行 make menuconfig 弹出图形化配置页面后 # 若使用默认配置，则直接按两次 Esc 键退出即可 # 此时会在当前目录下生成 .config 文件 # 编译 Linux 源码 make bzImage -j4 # 在编译过程中若报错 fatal error: openssl/opensslv.h，可执行下面命令 # apt-get install libssl-dev # 若还出现同样的问题，可参考 https://blog.csdn.net/ComputerInBook/article/details/107380796 源码编译安装 openssl # 若出现「没有规则可制作目标“debian/canonical-certs.pem”」报错 # 需要删除 .config 中相应的字段，总共有两处 # 一处为 CONFIG_SYSTEM_TRUSTED_KEYS="debian/canonical-certs.pem" # 一处为 CONFIG_SYSTEM_REVOCATION_KEYS="debian/canonical-revoked-certs.pem" vim .config # 删除之后的样子如下（需要保留引号）： # 一处为 CONFIG_SYSTEM_TRUSTED_KEYS="" # 一处为 CONFIG_SYSTEM_REVOCATION_KEYS="" # 若出现 BTF: .tmp_vmlinux.btf: pahole (pahole) is not available 错误，则执行下面命令 # apt-get install dwarves # 若在过程中还出现其它问题，大多是因为缺少相关库导致的，直接用 apt-get install 即可

C 语言的编译需要经过很多步骤，其中第一个步骤称为预处理阶段。这个阶段的主要任务包括删除注释、插入被#include指令包含的文件的内容、定义和替换#define指令定义的符号以及确定代码的部分内容是否应该跟绝一些条件编译指令进行编译。 #define #define指令就是为数值命名一个符号。比如#define name stuff指令，有了它之后，每当有符号name出现在这条指令后面时，预处理器就会把它替换成stuff，比如下面几个例子： // 为关键字 register 创建了一个简短的别名 #define reg register // 声明了一个更具描述性的符号用来替代实现无限循环的 for 语句 #define do_forever for(;;) // 定义了一个简短记法，在 switch 语句中使用，可以自动把一个 break 放在每个 case 之前 #define CASE break;case 当然如果定义中的stuff非常长，那么也可以将它分成几行，除了最后一行之外，每行的末尾都需要加一个反斜杠。比如： #define log_debug printf("File[%s]line[%d]:" \ " x=[%d], y=[%d], z=[%d]", \ __FILE__, __LINE__, \ x, y, z) // 那么我们将可以很方便的插入一条调试语句打印 x *= 2; y += x; z = x * y; log_debug; 很容易就发现上面的log_debug定义无法进行泛化，当然设计者也考虑到了这个问题，所以#define机制包括了一个规定，即允许把参数替换到文本中，这种实现一般称为宏，其声明方式如下： define name(parameter-list) stuff 需要注意的是parameter-list是一个由逗号分隔的符号列表，他们可能出现在stuff中。参数列表的左括号必须与name紧邻，如果两者之间有任何空白存在，参数列表就会被解释为stuff的一部分。下面我们看一个具体的列子，以此了解宏定义的机制，并将它逐步优化改进： #define SQUARE(x) x * x // 使用 SQUARE(5) // 效果：5 * 5 考虑一下下面的代码段： a = 5; printf("%d\n", SQUARE(a + 1)); 乍一看觉得这段代码将打印36这个值。但实际它却会打印11，我们仔细观察一下被替换的宏文本，即参数x被文本a + 1替换： a = 5; printf("%d\n", a + 1 * a + 1); 很容易想到对参数 x 加一个括号解决上述问题，即： #define SQUARE(x) (x) * (x) // 上述打印将会被替换为 a = 5; printf("%d\n", (a + 1) * (a + 1)); 类似的我们可以再定义一个DOUBLE宏，即： #define DOUBLE(x) (x) + (x) 但是考虑下面的使用方式： a = 5; printf("%d\n", 10 * DOUBLE(5)); 看上去它应该打印的结果是100，但事实上它打印的是55，我们再通过宏替换产生的文本观察问题： printf("%d\n", 10 * (5) + (5)); 所以我们需要在整个表达式两边加上一对括号。所有用于对数值表达式进行求值的宏定义都应该使用下面这种方式加上括号，避免在使用宏时，由于参数中的操作符或邻近的操作符之间不可预料的相互作用。 #define DOUBLE(x) ((x) + (x)) 宏与函数 宏非常频繁的用于执行简单的计算，比如在两个表达式中寻找其中较大（小）的一个： #define MAX(a, b) ((a) > (b) ? (a) : (b)) 那么为什么不使用函数来完成这个任务呢？首先用于调用和从函数返回的代码很可能比实际执行这个小型计算工作的代码更大，所以使用宏比使用函数在程序的规模和速度方面都更胜一筹。 更为重要的是函数必须声明为一种特定的类型，所以它只能在类型合适的表达式上使用。但是上面的这个宏可以用于整型、长整型、单浮点型、双浮点型以及任何其它可以使用>操作符比较值大小的类型，即宏与类型无关。 当然宏也有它的不利之处，因为每次在使用宏时，一份宏定义代码的拷贝都将插入到程序中，除非宏的定义非常短，否则使用宏将会大幅增加程序的长度。 也有一些任务根本无法使用函数实现，比如下面这个宏的第二个参数是一种类型，它无法作为函数参数进行传递。 #define MALLOC(n, type) ((type *)malloc((n) * sizeof(type))) 当宏参数在宏定义中出现的次数超过一次时，如果这个参数具有副作用，那么当使用这个宏的时候就可能出现危险，导致一些不可预料的后果。比如x++就是一个具有副作用的表达式，它会改变x的值，直接会导致下面的代码段出现不可预知的后果： #define MAX(a, b) ((a) > (b) > (a) : (b)) x = 5; y = 8; z = MAX(x++, y++); // z = ((x++) > (y++) > (x++) : (y++)) 属性 #define 宏 函数 代码长度 每次使用时，宏代码都被插入到程序中。除了非常小的宏志伟，程序的长度将大幅度增长 函数代码只出现于一个地方，每次使用这个函数时，都调用那个地方的同一份代码 执行速度 更快 存在函数调用/返回的额外开销 操作符优先级 宏参数的求值是在所有周围表达式的上下文环境里，除非它们加上括号，否则邻近操作符的优先级可能回产生不可预料的结果 函数参数只在函数调用时求值一次，它的结果传递给参数。表达式的求值结果更容易预测 参数求值 参数每次用于宏定义时，它们都将重新求值。由于多次求值，具有副作用的参数可能会产生不可预料的结果 参数在函数被调用前求值一次。在函数中多次使用参数并不会导致多种求值过程。参数的副作用不会造成任何特殊的问题 参数类型 宏与类型无关。只要对参数的操作是合法的，它可以使用于任何参数类型 函数的参数是与类型有关的。如果参数的类型不同，就需要使用不同的函数，即使它们执行的任务时相同的 文件包含 我们知道#include指令可以使另一个文件的内容被编译，就像它实际出现于#include指令出现的位置一样。这种替换的执行方式很简单：预处理器删除这条指令，并用包含头文件的内容取而代之。这样一个头文件如果被包含到 10 个源文件中，它实际上被编译了 10 次。 基于这种替换的方式，当出现嵌套#include文件被多次包含时，就会出现问题： #include "a.h" #include "b.h" // 如果 a.h 和 b.h 中都包含一个 #include x.h // 那么 x.h 在此处就出现了两次 这种多重包含在绝大多数情况下出现于大型程序中，它往往需要很多头文件，所以要发现这种情况并不容易。但是我们可以使用条件编译来解决这个问题： #ifndef _HEADER_NAME_H_ #define _HEADER_NAME_H_ /* * All the stuff that you want in the header file */ #endif

约定：本文所说的标准均为 ANSI (C89) 标准 三字母词 标准定义了几个三字母词，三字母词就是三个字符的序列，合起来表示另一个字符。三字母词使得 C 环境可以在某些缺少一些必需字符的字符集上实现，它使用两个问号开头再尾随一个字符，这种形式一般不会出现在其它表达形式中，这样就不容易引起误解了，下面是一些三字母词的对应关系： ??( [ ??) ] ??! | ??< { ??> } ??' ^ ??= # ??/ \ ??- ~ 所以在一些特殊情况下可能出现下面的情况，希望你不要被意外到。 printf("Delete file (are you really sure??): "); // result is: Delete file (are you really sure]: 字符 直接操作字符会降低代码的可移植性，应该尽可能使用库函数完成。比如下面的代码试图测试ch是否为一个大写字符，它在使用ASCII字符集的机器上能够运行，但是在使用EBCDIC字符集的机器上将会失败。 if( ch >= 'A' && ch <= 'Z') 使用if(isupper(ch))语句则能保证无论在哪种机器上都能正常运行。 字符串比较 库函数提供了int strcmp(const char *s1, const char *s2)函数用于比较两个字符串是否相等，需要注意的是在标准中并没有规定用于提示不相等的具体值。它只是说如果第 1 个字符串大于第 2 个字符串就返回一个大于零的值，如果第 1 个字符串小于第 2 个字符串就返回一个小于零的值。一个常见的错误是以为返回值是1和-1，分别代表大于和小于。 初学者常常会编写下面的表达式。认为如果两个字符串相等，那么它返回的结果将为真。但是这个结果恰好相反，两个字符串相等的情况下返回值是零（假）。 if(strcmp(a, b)) strlen strlen的返回值是一个size_t类型的值，这个类型是在头文件stddef.h中定义的，它是一个无符号整数类型，所以会导致下面表达式的条件永远为真。 if(strlen(x) - strlen(y) >= 0) { // do something } 第二点需要注意的是strlen的返回值没有计算\0的长度，所以下面的代码在一些检查严格或老版本的编译器中会报错，其原因在于少分配了一个存储单位。 // 假设 str 是一个字符串 char *cpy = malloc(strlen(str)); strcpy(cpy, str); // 正确写法应为 char *cpy = malloc(strlen(str) + 1); strcpy(cpy, str); 赋值截断 表达式a = x = y + 3;中x和a被赋予相同值的说法是错误的，因为如果x是一个字符型变量，那么y+3的值就会被截去一段，以便容纳于字符型的变量中，那么a所赋的值就是这个被截短后的值。下面也是一个非常常见的错误。 char ch; // do something while((ch = getchar()) != EOF) { // do something } EOF所需要的位数比字符型值所能提供的位数要多，这也是getchar返回一个整型值而不是字符值的原因。例子中把getchar的返回值存储于字符型变量会导致被截短，然后再把这个被截短的值提升为整型与EOF进行比较，在某些机器的特定场景下就会导致问题。比如在使用有符号字符集的机器上，如果读取了一个的值为\377的字节，上述循环就将终止，因为这个值截短再提升之后与EOF相等。而当这段代码在使用无符号字符集的机器上运行时，这个循环将永远不会终止。 指针与数组 因为数组和指针都具有指针值，都可以进行间接访问和下标操作，所以很多同学都想当然的将它们认为是一样的，为了说明它们是不相等的，我们可以考虑下面的两个声明： int a[5]; int *b; 声明一个数组时，编译器将根据声明所指定的元素数量为数组保留空间，然后再创建数组名，它的值是一个常量，指向这段空间的起始位置。声明一个指针变量时，编译器只为指针本身保留内存空间，它并不为任何整型值分配内存空间。而且，指针变量并未被初始化为任何指向现有的内存空间。所以在上述声明之后，表达式*a是完全合法的，但是表达式*b将访问内存中某个不确定的位置，或者导致程序终止。 硬件操作 我们知道其实表示就是内存中一个地址，所以理论上*100 = 25是一种可行的操作，即让内存中位置为100的地方存储25。但实际上这条语句是非法的，因为字面值100的类型是整型，而间接访问操作只能用于指针类型表达式，所以合法的写法必须使用强制转换，即*(int *)100 = 25。 需要说明的是使用这种技巧的机会是绝无仅有的，只有偶尔需要通过地址访问内存中某个特定的位置才可使用，它并不是访问某个变量，而是访问硬件本身。比如在某些机器上，操作系统需要与输入输出设备控制器通信，启动 I/O 操作并从前面的操作中获得结果，此时这些地址是预先已知的。 += 与 ?: 操作符 我们在这里讨论一下+=操作符，它的用法为a += expr，读作把 expr 加到 a，其实际功能相当于表达式a = a + expr的作用，唯一不同的是+=操作符的左操作数a只会求值一次。可能到目前为止没有感觉到设计两种增加一个变量值的方法有什么意义？下面给出代码示例： // 形式 1 a[ 2 * (y - 6*f(x)) ] = a[ 2 * (y - 6*f(x)) ] + 1; // 形式 2 a[ 2 * (y - 6*f(x)) ] += 1; 在第一种形式中，用于选择增值位置的表达式必须书写两次，一次在赋值号左边，一次在赋值号右边。由于编译器无法知道函数f是否具有副作用，所以它必须两次计算下标表达式的值，而第二种形式的效率会更高，因为下标表达式的值只会被计算一次。同时第二种形式也减少了代码书写错误的概率。 同理三目运算符也可以起到类似的效果。 // 形式 1 if(a > 5) { b[ 2 * c + d * (e / 5) ] = 3; } else { b[ 2 * c + d * (e / 5) ] = -20; } // 形式 2 b[ 2 * c + d * (e / 5) ] = a > 5 ? 3 : -20; 逗号操作符 逗号操作符可以将多个表达式分隔开来。这些表达式自左向右逐个进行求值，整个表达式的值就是最后那个表达式的值。例如： if(b + 1, c / 2, d > 0) { // do something} 当然，正常人不会编写这样的代码，因为对前两个表达式的求值毫无意义，它们的值只是被简单的丢弃了。但是我们可以看看下面的代码： // 形式 1 a = get_value(); count_value(a); while(a > 0) { // do something a = get_value(); count_value(a); } // 形式 2 while(a = get_value(), count_value(), a > 0) { // do something } 指针 int* a, b, c; 人们会很自然的认为上述语句是把所有三个变量都声明为指向整型的指针，但事实上并非如此，星号实际上只是表达式*a的一部分，只对这个标识符有作用。如果要声明三个指针，那么应该使用下面的形式进行初始化。 int *a, *b, *c; 在声明指针变量时可以为它指定初始值，比如下面的代码段，它声明了一个指针，并用一个字符串常量对其进行初始化。 char *msg = "Hello World!"; 需要注意的是，这种类型的声明会让人很容易误解它的意思，看起来初始值似乎是赋给表达式*msg的，但实际上它是赋值给msg本身的，也就是上述声明实际形式如下： char *msg; msg = "Hello World!"; 指针常量： int *pi中pi是一个普通的指向整型的指针， 而变量int const *pci则是一个指向整型常量的指针，你可以修改指针的值，但是不能修改它所指向的值。相比之下int * const cpi则声明cpi为一个指向整型的常量指针。此时指针是常量，它的值无法修改，但是可以修改它所指向的整型的值。在int const * const cpci中，无论是指针本身还是它所指向的值都是常量，无法修改。 枚举类型 枚举（enumerated） 类型就是指它的的值为符号常量而不是字面值的类型，比如下面的语句声明了Jar_Type类型： enum Jar_Type { CUP, PINT, QUART, HALF_GALLON, GALLON }; 需要注意的是，枚举类型实际上是以整型方式存储的，代码段中的符号名实际上都是整型值。在这里CUP的值是0，PINT的值是1，依次类推。 在适当的时候，可以为这些符号名指定特定的值整型值。并且只对部分符号名进行赋值也是合法的，如果某个符号名没有显示的赋值，那么它的值就比前面一个符号名的值大 1。 enum Jar_Type { CUP = 8, PINT = 16, QUART = 32, HALF_GALLON = 64, GALLON = 128 }; 符号名被当作整型处理，这意味着可以把HALF_GALLON这样的值赋给任何整型变量，但是在编程活动中应该避免这种方式使用枚举，因为这样会削弱它们的含义。 typedef 与 define 在实际应用过程中应该使用typedef而不是#define来创建新的类型名，因为#define无法正确的处理指针类型，比如下面的代码段正确的声明了a，但是b却被声明为了一个字符。 #define ptr_to_char char * ptr_to_char a, b; 联合（union） 联合看起来很像结构体，与结构体不同的是联合的所有成员共用同一块内存，所以在同一时刻联合中的有效成员永远只有一个。我们可以看下面一个例子，当一个variable类型的变量被创建时，解释器就创建一个这样的结构并记录变量类型。然后根据变量类型，把变量的值存储在这三个值字段的其中一个。 struct variable { enum { INT, FLOAT, STRING } type; int int_val; float float_val; char *str_val; } 不难发现上述结构的低效之处在于它所使用的内存，每个variable结构存在两个未使用的值字段，造成了内存空间上的不少浪费。使用联合就可以减少这种空间上的浪费，它把这三个值字段的每一个都存储在同一个内存位置。我们知道这三个字段并不会冲突，因为每个变量只可能具有一种类型，所以在具体的某一时刻，联合的这几个字段只有一个被使用。 struct variable { enum { INT, FLOAT, STRING } type; union { int i; float f; char *s; } val; } 现在，对于整型变量，我们只需要将type字段设为INT，并把整型值存储于val.i即可。如果联合中各成员的长度不一样，联合的长度就是它最长成员的长度。 联合的变量也可以被初始化，但是这个初始值必须是联合第 1 个成员的类型，而且它必须位于一对花括号里面。比如： union { int a; float b; chat c[4]; } x = { 5 }; 结构体 在实际编程活动中，存在链表、二叉树等结点自引用的情况，那么结构体的自引用如何编写呢？ struct node { int data; struct node next; } 上述写法是非法的，因为成员next是一个完整的结构，其内部还将包含自己的成员next，这第 2 个成员又是另一个完整结构，它还将包含自己的成员next，如此重复下去将永无止境。正确的自引用写法如下： struct node { int data; struct node *next; } 我们需要注意下面的这个陷阱： /* 错误写法：因为类型名 node_t 直到声明末尾才定义 所以在结构中声明的内部 node_t 尚未定义 */ typedef struct { int data; node_t *next; } node_t; // 正确写法 typedef struct node_tag { int data; struct node_tag *next; } node_t; 编译器在实际分配时会按照结构体成员列表的顺序一个接一个的分配内存，并且只有当存储成员需要满足正确的边界对齐要求时，成员之间可能会出现用于填充的额外内存空间。 ```c struct align { char a; int b; char c; } 如果某个机器的整型值长度为 4 个字节，并且它的起始存储位置必须能够被 4 整除，那么这个结构在内存中的存储将是下面这种形式 a b b b b c 我们可以通过改变成员列表的声明顺序，让那些对边界要求严格的成员首先出现，对边界要求弱的成员最后出现，这样可以减少因为边界对齐而带来的空间损失。 struct align { int b; char a; char c; } b b b b a c 当程序创建几百个甚至几千个结构时，减少内存浪费的要求就比程序的可读性更为急迫。我们可以使用sizeof操作符来得出一个结构的整体长度。如果必须要确定结构某个成员的实际位置，则可以使用offsetof(type, member)宏，例如： offset(struct align, b); 一句话 标识符：标识符就是变量、函数、类型等的名字，标识符的长度没有限制，但是 ANSI 标准允许编译器忽略第 31 个字符以后的字符，并且允许编译器对用于表示外部名字（由链接器操作的名字）的标识符进行限制，只识别前 6 位不区分大小写的字符。 注释：代码中所有的注释都会被预处理器拿掉，取而代之的是一个空格。因此，注释可以出现在任何空格可以出现的地方。 类型：C 语言中仅有 4 种基本数据类型，即整型、浮点型、指针和聚合类型（数组、结构等），所有其它的类型都是从这 4 中基本类型的某种组合派生而来。 类型长度：标准只规定了short int至少是 16 位，long int至少是 32 位，至于缺省的int是多少位则直接由编译器设计者决定。并且标准也没有规定这 2 个值必须不一样。如果某种机器的环境字长是 32 位，而且也没有什么指令能够更有效的处理更短的整型值，那它很可能把这 3 个整型值都设定为 32 位。 位域：基于 int 位域被当作有符号还是无符号数、位域成员的内存是从左向右还是从右向左分配、运行在 32 位整数的位域声明可能在 16 位机器无法运行等原因，注重可移植性的程序应该避免使用位域。 结构与指针：什么时候应该向函数传递一个结构而不是一个指向结构的指针呢？很少有这种情况。只有当一个结构特别小（长度和指针相同或更小）时，结构传递方案的效率才不会输给指针传递方案。

最近主要时间都放在知识图谱构建中，但是还是需要给自己充电。想在近段时间好好把 JVM 的垃圾回收好好看一下，学习然后输出，是我新找到的有效学习方法，希望你看了之后能有收获。 什么是垃圾 垃圾回收（常称做GC——Garbage Collection）诞生于1960年 MIT 的 Lisp 语言，垃圾回收机制也已经用在了很多编程语言中，比如 Java、Python、C# 等。我们这里主要说 Java 中的垃圾回收。 在JVM中，程序计数器、虚拟机栈、本地方法栈都是随线程生而生，随线程灭而灭；栈帧随着方法的进入和退出做入栈和出栈操作，实现了自动的内存清理；常说的垃圾回收主要集中在堆和方法区，这部分内存是随着程序运行动态分配的。 既然要回收垃圾，那么我们首先需要知道的就是，什么样的对象是垃圾。一般有两种方式： 引用计数 每个对象有一个引用计数属性，新增一个引用时计数加 1，引用释放时计数减 1，当引用计数变为 0 的时候，这个对象就可以回收了。但是这个方法无法解决对象循环引用的问题。 // 对象循环引用示例 Object objectA = new Object(); Object objectB = new Object(); objectA.instance = objectB; objectB.instance = objectA; objectA = null; objectB = null; 假设我们有上面的代码。程序启动后，objectA和objectB两个对象被创建并在堆中分配内存，它们都相互持有对方的引用，但是除了它们相互持有的引用之外，再无别的引用。而实际上，引用已经被置空，这两个对象不可能再被访问了，但是因为它们相互引用着对方，导致它们的引用计数都不为 0，因此引用计数算法无法通知GC回收它们，造成了内存的浪费。如下图：对象之间的引用形成一个有环图。 可达性分析 或者叫根搜索算法，在主流的JVM中，都是使用的这种方法来判断对象是否存活的。这个算法的思路很简单，它把内存中的每一个对象都看作一个结点，然后定义了一些可以作为根结点的对象，我们称之为「GC Roots」。果一个对象中有另一个对象的引用，那么就认这个对象有一条指向另一个对象的边。 像上面这张图，JVM会起一个线程从所有的GC Roots开始往下遍历，当遍历完之后如果发现有一些对象不可到达，那么就认为这些对象已经没有用了，需要被回收。（这里多说一句，我们的JVM一起动，就至少有两个线程启动，一个是垃圾回收线程，一个是我们自己的主线程。） 那么现在问题就变成了——什么样的对象可以当作 GC Roots？共有四种对象可以作为 GC Roots。 虚拟机栈中的引用的对象 们在程序中正常创建一个对象，对象会在堆上开辟一块空间，同时会将这块空间的地址作为引用保存到虚拟机栈中，如果对象生命周期结束了，那么引用就会从虚拟机栈中出栈，因此如果在虚拟机栈中有引用，就说明这个对象还是有用的，这种对象可以作为 GC Roots。 全局的静态的对象 也就是使用了static关键字定义了的对象，这种对象的引用保存在共有的方法区中，因为虚拟机栈是线程私有的，如果保存在栈里，就不叫全局了，很显然，这种对象是要作为 GC Roots 的。 常量引用 就是使用了static final关键字，由于这种引用初始化之后不会修改，所以方法区常量池里的引用的对象也作为GC Roots。 本地方法栈中JNI引用的对象 有时候单纯的java代码不能满足我们的需求，就可能需要调用 C 或 C++ 代码（Java 本身就是用 C 和 C++ 写的嘛），因此会使用native方法，JVM 内存中专门有一块本地方法栈，用来保存这些对象的引用，所以本地方法栈中引用的对象也会被作为 GC Roots。 垃圾回收算法 有意思的是在 JVM 规范中，并没有明确指明 GC 的运作方式，各个厂商可以采用不同的方式去实现垃圾收集器。这篇文章简单介绍常见的垃圾回收算法。 标记-清除算法 标记-清除算法分两个步骤，分别为「标记」和「清除」，字如其人。它是一个最基础的垃圾回收算法，更高级的垃圾回收算法都是基于它改进的。 它的运行过程是这样的：首先标记出所有需要回收的对象，标记完成后，再统一回收掉所有被标记的对象。 标记-清除算法的缺点有两个，一个是空间问题，标记清除之后会产生大量的不连续内存碎片。内存碎片太多，程序在之后的运行过程中就有可能找不到足够的连续内存来分配较大的对象，进而不得不提前触发另一次垃圾回收，导致程序效率降低。标记-清除算法的另一个缺点是效率问题，标记和清除的效率都不高，两次扫描耗时严重。 复制算法 复制算法把内存按容量划分为大小相等的两块，每次只使用其中的一块。如果正在用的这块没有足够的可使用空间了，那么就将还活着的对象复制到另一块去，再把使用过的内存一次性清掉。 这样就实现了简单高效的做法，每一次进行内存回收时，就不用再去考虑内存碎片这些复杂的情况，只需要移动堆顶指针就可以。但是缺点也很明显，可使用内存只有原来的一半了，而且持续复制生命力很旺盛的对象也会让效率降低哇。复制算法适用于存活对象少、垃圾对象多的情况，这种情况在新生代比较常见。 标记-压缩算法 在老年代，大部分对象都是存活的对象，复制算法在这里就不靠谱了，所以有人提出了标记压缩算法，标记过程和标记清除算法一样，但是清理时不是简单的清理，而是让所有存活的对象都向一端移动，然后直接清理掉边界以外的内存，需要移动对象的成本。 分代算法 前面的几种垃圾回收算法中，没有一种可以完全替代其他算法，他们具备各自的特点与优势，因此更好的方法是根据垃圾对象的特性来选择合适的回收算法。 分代算法的思想就是将内存空间根据对象的特点不同进行划分，选择合适的垃圾回收算法来提高回收效率。分代的思想已经被现有的虚拟机广泛采用。 分区算法 分区算法就是将整个堆空间再划分为连续的不同小区间，每一个小区间独立使用，也独立回收。 一般在相同条件下，堆空间越大，那么一次GC的时间就越长，因此而产生的停顿时间也就越长。为了控制GC的停顿时间，根据目标停顿时间，每次合理回收若干个小区间，而不是整个堆空间，进而减少一个GC的停顿时间。 垃圾收集器 上面讲的是垃圾收集算法，讲的是理论，垃圾收集器就是这些理论的具体实现。下面介绍一些垃圾收集器 Serial收集器 串行收集器是高效率的、古老的收集器，它只用了一个线程去回收垃圾。新生代、老年代使用串行回收；新生代复制算法、老年代标记-压缩算法。串行是指 GC 过程和用户过程是串行的，在垃圾收集过程中会 stop the world，JVM在后台自动发起垃圾回收，会在用户不可见的情况下，把用户的线程全部停掉，就是 GC 停顿，给用户带来不良体验。 红色代表 GC 线程，灰色代表用户线程，下同。 ParNew收集器 ParNew 收集器就是 Serial 收集器的多线程版本，除了多线程以外，其余行为都和 Serial 收集器一样。新生代并行收集，老年代串行收集；新生代使用复制算法、老年代使用标记-压缩算法。 Parallel Scavenge收集器 Parallel Scavenge 收集器类似于 ParNew 收集器，因为与吞吐量密切，也称为吞吐量收集器。可以通过参数来打开自适应调节策略，虚拟机会根据当前系统的运行情况收集性能监控信息，动态调整这些参数以提供最合适的停顿时间或最大的吞吐量；也可以通过参数控制 GC 的时间不大于多少毫秒或者比例。Parallel Scavenge 收集器以高吞吐量为目标，减少垃圾收集时间，让用户代码获得更长的运行时间；GC 停顿时间的缩短，是用牺牲吞吐量和新生代空间来换取的。 Parallel Old收集器 Parallel Old 收集器是 Parallel Scavenge 收集器的老年代版本，使用多线程和「标记-压缩」算法，在 JDK1.6 版本才开始提供。 CMS收集器 CMS（Concorrect mask sweep）收集器是一种以获取最短停顿时间为目标的收集器；也称为并发低停顿收集器。常用在 WEB、B/S 架构的服务系统中，因为这类应用很注重响应速度，尽可能减少系统停顿时间，给用户带来较好的体验。从名字上就可以看出来，它是基于「标记-清除」算法实现的，整个过程分为 4 步： 初始标记 初始标记仅仅标记 GC Roots 能直接关联到的对象，所以速度很快，需要停止服务（Stop The World）。 并发标记 并发标记是进行 GC Roots Tracing 的过程，为了标记上一步集合中的存活对象，因为用户程序这段时间也在运行，所以并不能保证可以标记出所有的存活对象。 重新标记 重新标记阶段是为了修正并发标记阶段因用户程序继续运作而导致标记变动的那一部分对象，采用多线程并行来提升效率，会停止服务，时间上远比并发标记短，较初始标记稍长。 并发清除 这个阶段即并发收集垃圾对象，可以与用户线程一起工作。 虽然 CMS 收集器线程可以和用户线程一起进行，但是它肯定会占用 CPU 资源，拖慢应用程序是肯定的，总的吞吐量会降低。 G1收集器 （看下垃圾回收算法中的分区算法）这是目前最新的前沿成果，它基于“标记-压缩”算法，可以进行空间整理，不会产生碎片。前面的垃圾收集器，收集范围都是整个新生代或老年代，但是 G1 收集器不是这样，使用 G1 收集器时，java堆的内存模型不同，它还保留有新生代和老年代的概念，它们都是一部分区域（可以不连续）的集合。除此之外，G1 收集器还能建立可预测的停顿时间模型，可以明确指定M毫秒时间片内，垃圾收集消耗的时间不超过N毫秒。G1 跟踪各个区域（Region）获得其收集价值大小，在后台维护一个优先列表，每次根据允许的收集时间，优先回收价值最大的 Region。G1 垃圾回收也分4步： 初始标记 仅标记 GC Roots 能直接关联到的对象。 并发标记 进行 GC Roots Tracing 的过程，并不能保证可以标记出所有的存活对象。这个阶段若发现区域对象中的所有对象都是垃圾，那个这个区域会被立即回收。 最终标记 为了修正并发标记期间因用户程序继续运作而导致标记变动的那一部分对象的标记记录，G1 中采用了比 CMS 更快的初始快照算法: snapshot-at-the-beginning (SATB)。 筛选回收 首先排序各个 Region 的回收价值和成本，然后根据用户期望的 GC 停顿时间来制定回收计划，最后按计划回收一些价值高的 Region 中垃圾对象，回收时采用"复制"算法，从一个或多个 Region 复制存活对象到堆上的另一个空的 Region，并且在此过程中压缩和释放内存。

参考内容： Two new system calls: splice() and sync_file_range() Linux 中的零拷贝技术1 Linux 中的零拷贝技术2 Zero Copy I: User-Mode Perspective Linux man-pages splice() Nginx AIO 机制与 sendfile 机制 sendfile 适用场景 扯淡 Nginx 的 sendfile 零拷贝的概念 浅析 Linux 中的零拷贝技术 Linux man-pages sendfile 今天在看 Nginx 配置的时候，看到了一个sendfile配置项，它可以配置在http、server、location三个块中，出于好奇就去查了一下sendfile的作用。 文件下载是服务器的基本功能，其基本流程就是循环的从磁盘读取文件内容到缓冲区，再将缓冲区内容发送到socket文件，程序员基本都会写出类似下面看起来比较高效的程序。 while((n = read(diskfd, buf, BUF_SIZE)) > 0) write(sockfd, buf , n); 上面程序中我们使用了read和write两个系统调用，看起来也已经没有什么优化空间了。这里的read和write屏蔽了系统内部的操作，我们并不知道操作系统做了什么，现实情况却是由于 Linux 的 I/O 操作默认是缓冲 I/O，上面的程序发生了多次不必要的数据拷贝与上下文切换。 上述两行代码执行流程大致可以描述如下： 系统调用read产生一个上下文切换，从用户态切换到内核态； DMA 执行拷贝（现在都是 DMA 了吧！），把文件数据拷贝到内核缓冲区； 文件数据从内核缓冲区拷贝到用户缓冲区； read调用返回，从内核态切换为用户态； 系统调用write产生一个上下文切换，从用户态切换到内核态； 把步骤 3 读到的数据从用户缓冲区拷贝到 Socket 缓冲区； 系统调用write返回，从内核态切换到用户态； DMA 从 Socket 缓冲区把数据拷贝到协议栈。 可以看到两行程序共发生了 4 次拷贝和 4 次上下文切换，其中 DMA 进行的数据拷贝不需要 CPU 访问数据，所以整个过程需要 CPU 访问两次数据。很明显中间有些拷贝和上下文切换是不需要的，sendfile就是来解决这个问题的，它是从 2.1 版本内核开始引入的，这里放个 2.6 版本的源码。 系统调用sendfile是将in_fd的内容发送到out_fd，描述符out_fd在 Linux 2.6.33 之前，必须指向套接字文件，自 2.6.33 开始，out_fd可以是任何文件；in_fd只能是支持mmap的文件（mmap是一种内存映射方法，在被调用进程的虚拟地址空间中创建一个新的指定文件的映射）。 所以当 Nginx 是一个静态服务器时，开启sendfile配置项是可以大大提高 Nginx 性能的，但是当把 Nginx 作为一个反向代理服务器时，sendfile则没有什么用，因为当 Nginx 时反向代理服务器时，in_fd就是一个套接字，这不符合sendfile的参数要求。 可以看到现在我们只需要一次拷贝就可以完成功能了，但是能否把这一次拷贝也省略掉呢？我们可以借助硬件来实现，仅仅需要把缓冲区描述符和文件长度传过去，这样 DMA 直接将缓冲区的数据打包发送到网络中就可以了。 这样就实现了零拷贝技术，需要注意的是这里所说的零拷贝是相对操作系统而言的，即在内核空间不存在冗余数据。数据的实际走向是从硬盘到内存，再从内存到设备。 Nginx 中还有一个aio配置，它的作用是启用内核级别的异步 I/O 功能，要使aio生效需要将directio开启（directio对大文件的读取速度有优化作用），aio很适合大文件的传送。需要注意的是sendfile和aio是互斥的，不可同时兼得二者，因此我们可以设置一个文件大小限制，超过该阀值使用aio，低于该阀值使用sendfile。 location /video/ { sendfile on; sendfile_max_chunk 256k; aio threads; directio 512k; output_buffers 1 128k; } 上面已经提到了零拷贝技术，它可以有效的改善数据传输的性能，但是由于存储体系结构非常复杂，而且网络协议栈有时需要对数据进行必要的处理，所以零拷贝技术有可能会产生很多负面影响，甚至会导致零拷贝技术自身的优点完全丧失。 零拷贝就是一种避免 CPU 将一块存储拷贝到另一块存储的技术。它可以减少数据拷贝和共享总线操作的次数，消除传输数据在存储器之间不必要的中间拷贝次数，从而有效的提高数据传输效率，而且零拷贝技术也减少了内核态与用户态之间切换所带来的开销。进行大量的数据拷贝操作是一件简单的任务，从操作系统的角度来看，如果 CPU 一直被占用着去执行这项简单的任务，是极其浪费资源的。如果是高速网络环境下，很可能就出现这样的场景。 零拷贝技术分类 现在的零拷贝技术种类很多，也并没有一个适合于所有场景的零拷贝零拷贝技术，概括起来总共有下面几种： 直接 I/O：对于这种数据传输方式来说，应用程序可以直接访问硬件存储，操作系统只是辅助数据传输，这类零拷贝技术可以让数据在应用程序空间和磁盘之间直接传输，不需要操作系统提供的页缓存支持。关于直接 I/O 可以参看Linux 中直接 I/O 机制的介绍。 避免数据在内核态与用户态之间传输：在一些场景中，应用程序在数据进行传输的过程中不需要对数据进行访问，那么将数据从页缓存拷贝到用户进程的缓冲区是完全没有必要的，Linux 中提供的类似系统调用主要有mmap()、sendfile()和splice()。 对数据在页缓存和用户进程之间的传输进行优化：这类零拷贝技术侧重于灵活地处理数据在用户进程的缓冲区和操作系统页缓存之间的拷贝操作，此类方法延续了传统的通信方式，但是更加灵活。在 Linux 中主要利用了「写时复制」技术。 前两类方法的目的主要是为了避免在用户态和内核态的缓冲区间拷贝数据，第三类方法则是对数据传输本身进行优化。我们知道硬件和软件之间可以通过 DMA 来解放 CPU，但是在用户空间和内核空间并没有这种工具，所以此类方法主要是改善数据在用户地址空间和操作系统内核地址空间之间传递的效率。 避免在内核与用户空间拷贝 Linux 主要提供了mmap()、sendfile()、splice()三个系统调用来避免数据在内核空间与用户空间进行不必要的拷贝，在Nginx 文件操作优化对sendfile()已经做了比较详细的介绍了，这里就不再赘述了，下面主要介绍mmap()和splice()。 mmap() 当调用mmap()之后，数据会先通过 DMA 拷贝到操作系统的缓冲区，然后应用程序和操作系统共享这个缓冲区，这样用户空间与内核空间就不需要任何数据拷贝了，当大量数据需要传输的时候，这样做就会有一个比较好的效率。 但是这种改进是需要代价的，当对文件进行了内存映射，然后调用write()系统调用，如果此时其它进程截断了这个文件，那么write()系统调用将会被总线错误信号SIGBUG中断，因为此时正在存储的是一个错误的存储访问，这个信号将会导致进程被杀死。 一般可以通过文件租借锁来解决这个问题，我们可以通过内核给文件加读或者写的租借锁，当另外一个进程尝试对用户正在进行传输的文件进行截断时，内核会给用户发一个实时RT_SIGNAL_LEASE信号，这个信号会告诉用户内核破坏了用户加在那个文件上的写或者读租借锁，write()系统调用就会被中断，并且进程会被SIGBUS信号杀死。需要注意的是文件租借锁需要在对文件进行内存映射之前设置。 splice() 和sendfile()类似，splice()也需要两个已经打开的文件描述符，并且其中的一个描述符必须是表示管道设备的描述符，它可以在操作系统地址空间中整块地移动数据，从而减少大多数数据拷贝操作。适用于可以确定数据传输路径的用户应用程序，不需要利用用户地址空间的缓冲区进行显示的数据传输操作。 splice()不局限于sendfile()的功能，也就是说sendfile()是splice()的一个子集，在 Linux 2.6.23 中，sendfile()这种机制的实现已经没有了，但是这个 API 以及相应的功能还存在，只不过内部已经使用了splice()这种机制来实现了。 写时复制 在某些情况下，Linux 操作系统内核中的页缓存可能会被多个应用程序所共享，操作系统有可能会将用户应用程序地址空间缓冲区中的页面映射到操作系统内核地址空间中去。如果某个应用程序想要对这共享的数据调用write()系统调用，那么它就可能破坏内核缓冲区中的共享数据，传统的write()系统调用并没有提供任何显示的加锁操作，Linux 中引入了写时复制这样一种技术用来保护数据。 写时复制的基本思想是如果有多个应用程序需要同时访问同一块数据，那么可以为这些应用程序分配指向这块数据的指针，在每一个应用程序看来，它们都拥有这块数据的一份数据拷贝，当其中一个应用程序需要对自己的这份数据拷贝进行修改的时候，就需要将数据真正地拷贝到该应用程序的地址空间中去，也就是说，该应用程序拥有了一份真正的私有数据拷贝，这样做是为了避免该应用程序对这块数据做的更改被其他应用程序看到。这个过程对于应用程序来说是透明的，如果应用程序永远不会对所访问的这块数据进行任何更改，那么就永远不需要将数据拷贝到应用程序自己的地址空间中去。这也是写时复制的最主要的优点。 写时复制的实现需要 MMU 的支持，MMU 需要知晓进程地址空间中哪些特殊的页面是只读的，当需要往这些页面中写数据的时候，MMU 就会发出一个异常给操作系统内核，操作系统内核就会分配新的物理存储空间，即将被写入数据的页面需要与新的物理存储位置相对应。它最大好处就是可以节约内存，不过对于操作系统内核来说，写时复制增加了其处理过程的复杂性。

参考内容： 处理器是如何工作的 《编码：隐匿在计算机软硬件背后的语言》——[美] Charles Petzold CPU 大家应该都不会陌生，日常用的手机、电脑中都有 CPU，CPU 作为一个设备的大脑，指挥着其它各种硬件的协同工作，芯片技术也是国内一直没有突破的技术。 我们先来看看怎么让电路去运算呢？比如如何让电路运算1 + 1，直接使用下面这个装置就可以了。 作为一个比较好奇的人，总会想看看那个方框框里面是什么样子的，让我们慢慢解开加法器的外衣。 这个电路你应该不会陌生，它需要两个开关都闭合时灯泡才会发光，也就是说它有两个输入，开关闭合时我们认为输入为 1，未闭合状态视为 0；而灯泡是否发光就是我们的输出，发光为 1，否则为 0。于是就有了下面这张表。 and 0 1 0 0 0 1 0 1 这样的电路我们就把它称之为与(and)门，它接受两个逻辑输入，并会给出我们一个逻辑输出，与它相似的电路还有逻辑或(or)、**异或(xor)**等等，因为太多了，就不一一介绍了，如果感兴趣可以 Google 一下。 为了方便我们把上面的电路做一个简化，抽象成下面这个样子，其它的电路也可以通过 Google 找到它们的样子。 现在直接给出一个可以运算加法的电路，它的样子长下面这样。 我们也可以给它列一个表，显得更清晰，表中之所以有两位是因为加法有可能会产生进位，而我们使用的是二进制表示，所以10表示的是十进制中的2。 + 0 1 0 00 01 1 01 10 有加法就很好办了，减法实际上是加一个负数，除法可以改写成乘法，乘法又可以改写成加法，现在加法一统天下了。 好了，上面说了那么多，还贴了那么多图，只是为了让你相信电路是可以实现我们数学上的运算的，下面就没有那么声情并茂了。 我们可以把一个运算抽象为下面这个模型。 输入数据 --> 运算 --> 输出数据 计算机中把各种像上述加法器一样的运算器放在了同一个小盒子里面，组成成一个运算器集合，我们给它取个名字叫算术逻辑单元（ALU：Arithmetic Logical Unit），它是 CPU 的核心组成部分。 当然我们不可能只进行加法这种简单运算，一个很长很长的算式需要经过多步运算，小学我们就学过梯等式，它实际上有一大推输入，中间那么多梯子，都是临时步骤，临时步骤、数据一类的东西都需要有个东西给它存起来，所以在 CPU 就拿出一个小盒子当做存储器。 # 梯等式 485 - ( 6 × 4 + 32 ) = 485 - ( 24 + 32 ) = 485 - 56 = 429 现在我们有了存储器和运算器两个干事的人，但是没有一个统筹兼顾的领导者，控制器就充当了这个角色，它需要把控制储存器中的数据发送到 ALU 去进行运算，然后再将运算的结果取出来存到储存器中。总的来说，控制器的工作就是完成协调和指挥整个计算机系统的操作。 我们把上面的结构画出来，图中的虚线表示指令流，实线表示数据流，这个结构就是著名的冯 · 诺依曼体系结构，遵循这种结构的计算机都叫做冯诺依曼机，现在所有的机器都是冯诺依曼机。 请注意，我们现在实际上只有硬件，没有软件是什么事情都干不了了，我们这里所说的软件是一堆指令序列，比如加法指令、传送指令等等组成的序列，也就是我们常说的汇编语言。 但是在早期并不是这样的，这台机器上编写的指令序列是无法运行在另一家公司生产的机器上的，即使是同一个公司的机器，如果不是同一代，那也不能运行，所以早期的编程是直接面向硬件的。 这时就有人站出来研究如何实现一次编写多处运行了，IBM 首次在它的 360 系统上引入了ISA的概念，即指令集体系结构。 指令集体系结构将编程所要了解的硬件信息从硬件系统中抽象了出来，这样开发人员就可以直接面向处理器的 ISA 进行编程了。 为什么手机上的软件不能运行在电脑中呢？就是因为个人电脑所使用的 Intel 和 AMD 处理器都是基于 x86 指令集的，而手机大多数都使用的是基于 ARM 指令集的处理器。 现在处理器被分为指令集体系结构、处理器微架构、处理器物理实现三个层次。体系结构相当于需求，微架构好比设计，物理实现则是具体的实现过程。 比如我们规定指令集中必须有加法指令，这个指令你怎么设计、如何实现是你给的事，我只管给出两个加数你能给我输出一个正确的结果，简单来说就是抽象封装。

今天在群里看到一个有意思的问题——为什么处理排序数组比处理没有排序的数组要快，这个问题来源于 StackoverFlow，虽然我看到代码略微知道原因，但是模模糊糊不够清晰，搜了很多博客也讲的不够明白，所以就自己来总结了。 首先来看一下问题，下面是很简单的一段代码，随机生成一些数字，对其中大于 128 的元素求和，记录并打印求和所用时间。 import java.util.Arrays; import java.util.Random; public class Main { public static void main(String[] args) { // Generate data int arraySize = 32768; int data[] = new int[arraySize]; Random rnd = new Random(0); for (int c = 0; c < arraySize; ++c) data[c] = rnd.nextInt() % 256; // !!! With this, the next loop runs faster Arrays.sort(data); // Test long start = System.nanoTime(); long sum = 0; for (int i = 0; i < 100000; ++i) { // Primary loop for (int c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } } System.out.println((System.nanoTime() - start) / 1000000000.0); System.out.println("sum = " + sum); } } 我的运行结果：分别在对数组排序和不排序的前提下测试，在不排序时所用的时间比先排好序所用时间平均要多 10 ms。这不是巧合，而是必然的结果。 问题就出在那个if判断上面，在旧文顺序、条件、循环语句的底层解释中其实已经提到了造成这种结果的原因，只是旧文中没有拿出具体的例子来说明。 为了把这个问题搞明白，需要先对流水线有一定的了解。计算机是指令流驱动的，执行的是一个一个的指令，而执行一条指令，又要经过取指、译码、执行、访存、写回、更新六个阶段（不同的划分方式所包含的阶段不一样）。 六个阶段使用的硬件基本是不一样的，如果一条指令执行完再去执行另一条指令，那么在这段时间里会有很多硬件处于空闲状态，要使计算机的速度变快，那么就不能让硬件停下来，所以有了流水线技术。 流水线技术通过将指令重叠来实现几条指令并行处理，下图表示的是三阶段指令时序，即把一个指令分为三个阶段。在第一条指令的 B 阶段，A 阶段相关的硬件是空闲的，于是可以将第二条指令的 A 阶段提前操作。 很明显，这种设计大幅提高了指令运行的效率，聪明的你可能发现问题了，要是不知道下一条指令是什么怎么办，那提前的阶段也就白干了，那样流水线不就失效了？没错，这就是导致开篇问题的原因。 让流水线出问题的情况有三种： 数据相关，后一条指令需要用到前一条指令的运算结果； 控制相关，比如无条件跳转，跳转的地址需要在译码阶段才能知道，所以跳转之后已经被取出的指令流水就需要清空； 结构相关，由于一些指令需要的时钟周期长（比如浮点运算等），长时间占用硬件，导致之后的指令无法进入译码等阶段，即它们在争用同一套硬件。 代码中的if (data[c] >= 128)翻译成机器语言就是跳转指令，处理器事先并不知道要跳转到哪个分支，那难道就等知道了才开始下一条指令的取指工作吗？处理器选择了假装知道会跳转到哪个分支（不是谦虚，是真的假装知道），如果猜中了是运气好，而没有猜中那就浪费一点时间重新来干。 没有排序的数组，元素是随机排列的，每次data[c] >= 128的结果也是随机的，前面的经验就不可参考，所以下一次执行到这里理论上还是会有 50% 的可能会猜错，猜错了肯定就需要花时间来修改犯下的错误，自然就会浪费更多的时间。 对于排好序的数组，开始几次也需要靠猜，但是猜着猜着发现有规律啊，每次都是往同一个分支跳转，所以以后基本上每次都能猜中，当遍历到与 128 分界的地方，才会出现猜不中的情况，但是猜几次之后，发现这又有规律啊，每次都是朝着另外一个相同分支走的。 虽然都会猜错，但是在排好序的情况下猜错的几率远远小于未排序时的几率，最终呈现的结果就是处理排序数组比未排序数组快，其原因就是流水线发生了大量的控制相关现象，下面通俗一点，加深一下理解。 远在他方心仪多年的姑娘突然告诉你，其实她也喜欢你，激动的你三天三夜睡不着觉，决定开车前往她的城市，要和她待在一起，但是要去的路上有很多很多岔路，你只能使用的某某地图导航，作为老司机并且怀着立马要见到爱人心情的你，开车超快，什么样罚单都不在乎了。 地图定位已经跟不上你的速度了，为了尽快到达，遇到岔路你都是随机选一条路前进，遗憾的是，自己的选择不一定对（我们假设高速可以回退），走错路了就要重新回到分岔点，这就对应着未排序的情况。 现在岔路是有规律的，告诉你开始一直朝着一边走，到某个地点后会一直朝着另一边走，你只需要花点时间去探索一下开始朝左边还是右边，到了中间哪个地点会改变方向就可以了，相比之下就能节省不少时间了，尽快见到自己的爱人，这对应着排好序的情况。 最后的故事改编自两个人的现实生活，一位是自己最好的朋友之一，谈恋爱开心的睡不着觉；另一位是微信上的一位好友，为了对方从北京裸辞飞到了深圳。

初级程序员讲究的是术，只知道如何用关键字去拼凑出领导想要的功能；高级程序员脸的是道，理解了底层的逻辑，不仅把功能做的漂漂亮亮，心法也更上一层楼。 顺序结构 数据传送指令 我们都清楚，绝大多数编译器都把汇编语言作为中间语言，把汇编语言程序变成可运行的二进制文件早就解决了，所以现在的高级语言基本上只需要把自己翻译成汇编语言就可以了。 汇编指令总共只有那么多，大多数指令都是对数据进行操作，比如常见的数据传送指令mov。不难理解，被操作数据无非有三种形式，立即数，即用来表示常数值；寄存器，此时的数据即存放在指定寄存器中的内容；内存引用，它会根据计算出来的地址访问某个内存位置。 需要注意的是，到了汇编层级，就不像高级语言那样随随便便int就能和long类型的数据相加减，他们在底层所占有的字节是不一样的，汇编指令是区分操作数据大小的，比如数据传送指令，就有下面这些品种（x86-64 对数据传送指令加了一条限制：两个操作数不能都指向内存位置）。 压栈与弹栈 对于栈，我想不必多讲，IT 行业的同学都清楚，它是一种线性数据结构，其中的数据遵循“先进后出”原则，寄存器%rsp保存着栈顶元素的地址，即栈顶指针。一个程序要运行起来，离不开栈这种数据结构。 栈使用最多的就是弹栈popq和压栈pushq操作。比如将一个四字值压入栈中，栈顶指针首先要减 8（栈向下增长），然后将值写到新的栈顶地址；而弹栈则需要先将栈顶数据读出，然后再将栈指针加 8。所以pushq和popq指令就可以表示为下面的形式。 // 压栈 subq $8, %rsp movq %rbp, (%rsp) // 弹栈 movq (%rsp), %rax addq $8, %rsp 其他还有算术、逻辑、加载有效地址、移位等等指令，可以查阅相关文档了解，不作过多介绍，汇编看起来确实枯燥乏味。 条件结构 前面讲的都是顺序结构，我们的程序中不可能只有顺序结构，条件结构是必不可缺的元素，那么汇编又是如何实现条件结构的呢？ 首先你需要知道，除了整数寄存器，CPU 还维护着一组条件码寄存器，我们主要是了解如何把高级语言的条件结构转换为汇编语言，不去关注这些条件码寄存器，只需要知道汇编可以通过检测这些寄存器来执行条件分支指令。 if-else 语句 下面是 C 语言中的if-else语句的通用形式。 if(test-expr){ then-statement }else{ else-statement } 汇编语言通常会将上面的 C 语言模板转换为下面的控制流形式，只要使用条件跳转和无条件跳转，这种形式的控制流就可以和汇编代码一一对应，我们以 C 语言形式给出。 t = test-expr; if(!t){ goto false; } then-statement; goto done; false: else-statement; done: 但是这种条件控制转移形式的代码在现代处理器上可能会很低效。原因是它无法事先确定要跳转到哪个分支，我们的处理器通过流水线来获得高性能，流水线的要求就是事先明确要执行的指令顺序，而这种形式的代码只有当条件分支求值完成后，才能决定走哪一个分支。即使处理器采用了非常精密的分支预测逻辑，但是还是有错误预测的情况，一旦预测错误，那将会浪费 15 ~ 30 个时钟周期，导致性能下降。 在流水线中，把一条指令分为多个阶段，每个阶段只执行所需操作的一小部分，比如取指令、确定指令类型、读数据、运算、写数据以及更新程序计数器。流水线通过重叠连续指令的步骤来获得高性能，比如在取一条指令的同时，执行它前面指令的算术运算。所以如果事先不知道指令执行顺序，那么事先所做的预备工作就白干了。 为了提高性能，可以改写成使用条件数据传送的代码，比如下面的例子。 v = test-expr ? then-expr : else-expr； // 使用条件数据传送方法 v = then-expr; ve = else-expr; t = test-expr; if(!t){ v = ve; } 这样改写，就能提高程序的性能了，但是并不是所有的条件表达式都可以使用条件传送来编译，一般只有当两个表达式都很容易计算时，编译器才会采用条件数据传送的方式，大部分都还是使用条件控制转移方式编译。 switch 语句 switch语句可以根据一个整数索引值进行多重分支，在处理具有多种可能结果的测试时，这种语句特别有用。为了让switch的实现更加高效，使用了一种叫做跳转表的数据结构（Radis 也是用的跳表）。跳转表是一个数组，表项 i 是一个代码段的地址，当开关情况数量比较多的时候，就会使用跳转表。 我们举个例子，还是采用 C 语言的形式表是控制流，要理解的是执行switch语句的关键步骤就是通过跳转表来访问代码的位置。 void switch_eg(long x, long n, long *dest){ long val = x; switch(n){ case 100: val *= 13; break; case 102: val += 10; case 103: val += 11; break; case 104: case 105: val *= val; break; default: val = 0; } *dest = val; } 要注意的是，上面的代码中有的分支没有break，这种问题在笔试中会经常遇到，没有break会继续执行下面的语句，即变成了顺序执行。上面的代码会被翻译为下面这种控制流。 void switch_eg(long x, long n, long *dest){ static void *jt[7] = { &&loc_A, &&loc_def, &&loc_B, &&loc_C, &&loc_D, &&loc_def, &&loc_D }; unsigned long index = n - 100; long val; if(index > 6){ goto loc_def; } goto *jt[index]; loc_A: val = x * 13; goto done; loc_B: x = x + 10; loc_C: val = x + 11; goto done; loc_D: val = x * x; goto done; loc_def: val = 0; done: *dest = val; } 循环结构 C 语言中有do-while、while和for三种循环结构，它们的通用形式一般都长下面那样。 // do-while do body-statement while(test-expr); // while while(test-expr) body-statement // for for(init-expr; test-expr; update-expr) body-statement do-while的特点是body-statement一定会执行一次，所以我们可以将do-while翻译成下面的控制流形式，很容易就能联想到它的汇编形式。 loop: body-statement; t = test-expr; if(t){ goto loop; } while循环我们给出两种形式的控制流，其中一种包含do-while形式，如下所示。 // 第一种形式 t = test-expr; if(!t){ goto done; } do body-statement; while(test-expr); done: // 第二种形式 goto test; loop: body-statement; test: t = test-expr; if(t){ goto loop; } 面试的时候，有的面试官会问你for循环的执行顺序，现在深入理解了三种循环的机制，再也不怕面试官啦。for循环可以转换成如下的while形式。 init-expr; while(test-expr){ body-statement; update-expr; } 有了这种形式的for循环，我们只需要将其中的while部分再翻译一下就好了，前文给出了两种while翻译的方式，而具体采用哪种方式，取决于编译器优化的等级。 总结 计算机就是用那么几条简简单单的指令就完成了各种复杂的操作，不得不折服于计算机科学家们的魅力。现在人工智能被炒的很火热，然后人是事件、情感驱动的，而计算机是控制流驱动的，所以从架构上就决定了，冯诺依曼体系计算机实现的都是弱人工智能。

我们在编程序的时候，都会把某一个特定功能封装在一个函数里面，对外暴露一个接口，而隐藏了函数行为的具体实现，一个大型的复杂系统里面包含了很多这样的小函数，我们称之为过程。 过程是相对独立的小模块，系统的运行需要这些过程的紧密合作，这种合作就是函数调用。 在一个函数执行时调用别的函数，比如 P 调用 Q，需要执行一些特定的动作。传递控制，在调用 Q 之前，控制权在 P 的手里，既然要调用 Q，那么就需要把控制权交给 Q；传递数据，就是函数传参；分配与释放内存，在开始时，Q 可能需要位局部变量分配空间，结束时又必须释放这些存储空间。 大多数语言都使用栈提供的先进后出机制来管理内存，x86-64 可以通过通用寄存器传递最多 6 个整数值（整数或地址），如果超过 6 个，那就需要在栈中分配内存，并且通过栈传递参数时，所有数据的大小都要向 8 的倍数对齐。将控制权从 P 转交给 Q，只需要将 PC（程序计数器）的值置为 Q 代码的起始位置，并记录好 P 执行的位置，方便 Q 执行完了，继续执行 P 剩余的代码。 在函数的传参、执行中，多多少少都需要空间来保存变量，局部数据能保存在寄存器中就会保存在寄存器中，如果寄存器不够，将会保存在内存中。除了寄存器不够用的情况，还有数组、结构体和地址等局部变量都必须保存在内存中。分配内存很简单，只需要减小栈指针的值就行了，同样释放也只需要增加栈指针。 在函数执行过程中，处理栈指针%rsp，其它寄存器都被分类为被调用者保存寄存器，即当过程 P 调用过程 Q 时，Q 必须保存这些寄存器的值，保证它们的值在 Q 返回到 P 时与 Q 被调用时是一样的。 所以递归也就不难理解了，初学算法总觉得递归有点奇妙，怎么自己调用自己，而实际上对于计算机来说，它和调用其它函数没什么区别，在计算机眼里，没有自身与其它函数的区别，所有被调用者都是其它人。 数组是编程中不可或缺的一种结构，“数组是分配在连续的内存中”这句话已经烂熟于心了，历史上，C 语言只支持大小在编译时就能确定的多维数组，这个多多少少有一些不便利，所以在ISO C99标准中就引入了新的功能，允许数组的维度是表达式。 int A[expr1][expr2] 因为数组是连续的内存，所以很容易就能访问到指定位置的元素，它通过首地址加上偏移量即可计算出对应元素的地址，这个偏移量一定意义上就是由索引给出。 比如现在有一个数组A，那么A[i]就等同于表达式* (A + i)，这是一个指针运算。C 语言的一大特性就是指针，既是优点也是难点，单操作符&和*可以产生指针和简介引用指针，也就是，对于一个表示某个对象的表达式expr，&expr给出该对象地址的一个指针，而对于一个表示地址的表达式Aexpr，*Aexpr给出该地址的值。 即使我们创建嵌套（多维）数组，上面的一般原则也是成立的，比如下面的例子。 int A[5][3]; // 上面声明等价于下面 typedef int row3_t[3]; row3_t A[5]; 这个数组在内存的中就是下面那个样子的。 还有一个重要的概念叫做数据对齐，即很多计算机系统要求某种类型的对象的地址必须是某个值 K（一般是2、4 或 8）的倍数，这种限制简化了处理器和内存接口之间的设计，甚至有的系统没有进行数据对齐，程序就无法正常运行。 比如现在有一个如下的结构体。 struct S1 { int i; char c; int j; } 如果编译器用最小的 9 字节分配，那么将是下面的这个样子。 但是上面这种结构无法满足 i 和 j 的 4 字节对齐要求，所以编译器会在 c 和 j 之间插入 3 个字节的间隙。 在极客时间专栏中有这样一段代码。 int main(int argc, char *argv[]){ int i = 0; int arr[3] = {0}; for(; i <= 3; i++){ arr[i] = 0; printf("Hello world!\n"); } return 0; } 这段代码神奇的是在某种情况下会一直循环的输出Hello world，并不会结束，在计算机系统漫游（补充）中也提到过。 造成上面这种结果是因为函数体内的局部变量存在栈中，并且是连续压栈，而 Linux 中栈又是从高向低增长。数组arr中是 3 个元素，加上 i 是 4 个元素，刚好满足 8 字节对齐（编译器 64 位系统下默认会 8 字节对齐），变量i在数组arr之前，即i的地址与arr相邻且比它大。 代码中很明显访问数组时越界了，当i为 3 时，实际上正好访问到变量i的地址，而循环体中又有一句arr[i] = 0;，即又把i的值设置为了 0，由此就导致了死循环。