Aug
1
- 鹅厂 -
在遥远的2009年，那时候“呵呵”还没有奇怪的意思，我笑呵呵地去参加了鹅厂的实习招聘。
面试被安排在面试官下榻酒店的房间里，校门口的**王朝大酒店，可能一晚上能顶我一个月生活费那种。
过程聊得应该还可以，不过大部分细节都忘了，只记得最后那道代码题，一张纸，一支笔。
题面很简单：写一个 C 函数，合并两个有序数组。
- “最好能通用一点”，面试官补充说。
- “可以用 C++ 模板吗？”
- “最好还是用 C 。”
好多年以后，当我开始面试别人了，发现这道题确实很好用。
- 解 -
学过归并排序的同学应该都会觉得这个题目并不难，只不过是其中的一次归并环节。
其基本思路是，用两个指针，分别从数组的第一个元素开始，依次比较，每次找到最小的元素存入新数组，然后将指针移动到下一位。
需要注意的是当一个数组被取完以后，还得处理另一个数组的剩余元素。
而所谓“通用”，是指数组的元素可以是任意类型，因此需要把数组元素的大小、用于比较的函数也作为参数传进去。
大概就是要实现这样的一个函数：
其中 m、n 分别表示 A、B 这两个数组的长度，size 表示数组元素的大小。
具体实现的 C 代码比较琐碎，就不在这里贴出来了，感兴趣的同学可以自己试着写一下。
- WHY -
我在上一家公司，通常用这道题当笔试的压轴题，但不限制语言，以及去掉了对“通用”的要求。
为什么选它呢？
首先，它很容易理解，不会产生歧义，不需要额外解释。
其次，在纸面上编码（至少是脱离IDE），程序员在编码前得想清楚；涂改较多也说明一些问题。
最重要的是，它有很好的区分度，因为真的有很多程序猿没认真学过归并排序。
但至少每个人都能想到将两个数组合并，然后进行排序。
有些特别直接的小伙伴，就用了 PHP 自带的 sort 函数，后来我们不得不加个说明：“避免使用库函数”。
至于排序算法，有人写冒泡，也有人写快排；快排的实现，又可以考察是不是在数组里做原地划分（大部分是拆到两个数组里再合并）。
并且，我们在题面上特地对 有序 两个字加粗、加下划线，引导候选人使用最优解法。
如果候选人最终仍然实现了排序解法，在面试中还可以再提示，是否能用上“有序”这个条件，进一步提高性能。
这样层层递进，能够较好地帮助我们判断候选人的编码能力。
不过机关算尽，还是遇到了比较挫败的case，比如一个候选人就反问：系统自带的函数效率最高啊，为什么要自己实现？
- 字节 -
到了字节跳动后，我发现这道题有点不够用了，撑死只能算 LeetCode Easy，对于有勇气来面试字节的候选人，通常都不在话下。
为了把它升级到 Medium，我想到了两个改动：
1. 两个不够，m个来凑
2. 数组太简单，得换成链表
然后一看，诶，这 tm 不就是 LeetCode 23 原题吗？
话说回来，这题就变成了：请把 m 个有序链表合并成一个新的有序链表；平均每个链表有 k 个节点。
- 解² -
不用说，所有候选人都能想到每次遍历所有链表、找到最小值加入新的链表。
对于选择这个思路的候选人，接下来的问题是：
Q1：这个方案的时间复杂度是多少呢？
有不少候选人回答 O(m * k)，大概是觉得两个链表合并是 O(2 * k)，m个链表合并自然是 O(m * k) 了。
实际上，使用这种思路，每次找到最小值需要逐个比较 m 个链表，这个操作需要执行 m * k 次（节点总数），因此总的时间复杂度应该是 O(m^2 * k)。
Q2：还有优化空间吗？
有些候选人确实想不到更优的解法，但只要能按这思路完成 bug free 的代码，综合面试中的其他表现，也可以通过我们的考查（详见 程序员面试指北：面试官视角）。
毕竟 LeetCode 23 原题可是 Hard 级别。
- 分治 -
对分治算法比较熟悉的候选人会想到，可以先两两合并，得到的 m / 2 个链表再两两合并，循环这个过程，直到只剩下一个链表。
然后又回到 Q1：这个方案的时间复杂度是多少呢？
这回答就千奇百怪了，O(m * log(k))，O(k * log(m)), O(m * k * log(k))……
这个计算其实不难：
* 第一轮需要 m/2 次两两合并，每次两两合并是 2k 次比较，合计 m*k
* 第二轮需要 m/4 次两两合并，每次两两合并是 4k 次比较（每个链表平均长度变成2k了），合计还是 m*k
* ……
* 对 m 个元素做二分，总共需要 log(m) 轮
所以合理的答案应该是 O(m * k * log(m))。
具体实现又可以分成上下两部分。
下层应该实现一个合并俩链表的逻辑，比较常见的错误是没能正确处理链表的头结点（比如直接当成尾节点用，或者忘记初始化，以及 C++ 小伙伴用了 new 以后常常忘了 delete），还有前面说到的，一个链表摘空了后，需要处理另一个链表剩下的节点。
上层的实现其实和归并排序长得一毛一样，可以 bottom-up，也可以 top-down。bottom-up 的实现常见的错误是没处理好落单的那一个，而 top-down 则需要注意递归的终止条件。
另外有点意外的是，不少 Java 小伙伴被 List 这个 Interface 荼毒还挺深，在编码的时候顺手就用 List.get(i) ，完全不考虑这个 API 的开销。
- 最小堆 -
对常见数据结构比较熟悉的候选人则会提出使用最小堆，这样可以将每次查找最小值的时间复杂度降为 log(m) ，于是总的时间复杂度也可以降为 O(m * k * log(m))。
既然提到了堆，那就可以顺便问一下，最小元素从堆顶被摘掉以后，如何调整堆？
于是那些只知道可以用最小堆、不知道如何实现堆的候选人就暴露出来了。
不过也不打紧，大部分语言的库里都实现了 PriorityQueue 这个数据结构，让候选人直接用语言提供的版本来编码就好。
具体的代码主要有两个坑，一是循环中要注意对摘空链表的处理，二是对链表头结点的处理（前面提到了）。
- 没完 -
面试到上面的程度就足够了，不然 45 分钟实在是不够用。
但其实还有些值得思考的问题没讲完。
比如说，这两种算法，平均时间复杂度都是 O(m * k * log(m))，到底哪一个更好呢？
分治算法的优势是，两两合并时，当一个链表为空，可以直接将另一个链表的剩余节点串起来，相比于堆算法可以节约一些时间。
另一方面，对于这样一个经典的多路归并问题，实际使用场景可能是要合并外存上的多个排好序的文件，这时候堆算法可以节约磁盘IO（只需要一次遍历），相比于分治算法就有了压倒性的优势。
所以具体还是要看场景。
再比如，在这个场景下，堆并不是最高效的数据结构。
实际上，堆算法只是多路归并的早期实现，由于每一层的调整都需要两次比较（先取出两个子节点的较小者，然后再和当前节点比较），其效率还有优化空间。
（堆的调整）
如果我们将用于比较的节点作为叶子节点构建一棵完全二叉树，从叶子节点往上只保存获胜的节点：
这样每一层只需要和其兄弟节点做比较即可。这就是所谓“胜者树”，说起来还是空间换时间的套路(多一倍的节点数）。
还没完 —— 这个方案对每一层的更新仍然需要访问3个节点（自己、兄弟节点，父节点），换个思路，如果我们在路径上只保存失败的值，再用一个额外的变量保存在根节点比较的获胜者：
于是我们对每一层的更新只需要访问当前节点和其父节点就好了。
由于每次保存的是失败者，这个方案又被称为“败者树”。
- 小结 -
这篇没有贴具体的代码，没试过的同学，正好可以用 LeetCode 23 来练手（传送门）。
照例小结一下：
* 笔试/面试题的区分度很重要；
* 归并排序是基础，bottom-up 和 top-down 都要熟；
* 多路归并可以用分治和堆来解决，时间复杂度最优；
* 通过败者树可以进一步优化堆的解法。
喜欢本文的小伙伴，别忘了分享给你的小伙伴，感谢~
---
推荐阅读：
* 程序员面试指北：面试官视角
* 踩坑记：go服务内存暴涨
* TCP：学得越多越不懂
* UTF-8：一些好像没什么用的冷知识
* (译) Ｃ程序员该知道的内存知识 (1)
在遥远的2009年，那时候“呵呵”还没有奇怪的意思，我笑呵呵地去参加了鹅厂的实习招聘。
面试被安排在面试官下榻酒店的房间里，校门口的**王朝大酒店，可能一晚上能顶我一个月生活费那种。
过程聊得应该还可以，不过大部分细节都忘了，只记得最后那道代码题，一张纸，一支笔。
题面很简单：写一个 C 函数，合并两个有序数组。
- “最好能通用一点”，面试官补充说。
- “可以用 C++ 模板吗？”
- “最好还是用 C 。”
好多年以后，当我开始面试别人了，发现这道题确实很好用。
- 解 -
学过归并排序的同学应该都会觉得这个题目并不难，只不过是其中的一次归并环节。
其基本思路是，用两个指针，分别从数组的第一个元素开始，依次比较，每次找到最小的元素存入新数组，然后将指针移动到下一位。
需要注意的是当一个数组被取完以后，还得处理另一个数组的剩余元素。
而所谓“通用”，是指数组的元素可以是任意类型，因此需要把数组元素的大小、用于比较的函数也作为参数传进去。
大概就是要实现这样的一个函数：
typedef int cmpfunc(void *x, void *y);
void* merge(void *A, int m, void *B, int n, int size, cmpfunc f);
void* merge(void *A, int m, void *B, int n, int size, cmpfunc f);
其中 m、n 分别表示 A、B 这两个数组的长度，size 表示数组元素的大小。
具体实现的 C 代码比较琐碎，就不在这里贴出来了，感兴趣的同学可以自己试着写一下。
- WHY -
我在上一家公司，通常用这道题当笔试的压轴题，但不限制语言，以及去掉了对“通用”的要求。
为什么选它呢？
首先，它很容易理解，不会产生歧义，不需要额外解释。
其次，在纸面上编码（至少是脱离IDE），程序员在编码前得想清楚；涂改较多也说明一些问题。
最重要的是，它有很好的区分度，因为真的有很多程序猿没认真学过归并排序。
但至少每个人都能想到将两个数组合并，然后进行排序。
有些特别直接的小伙伴，就用了 PHP 自带的 sort 函数，后来我们不得不加个说明：“避免使用库函数”。
至于排序算法，有人写冒泡，也有人写快排；快排的实现，又可以考察是不是在数组里做原地划分（大部分是拆到两个数组里再合并）。
并且，我们在题面上特地对 有序 两个字加粗、加下划线，引导候选人使用最优解法。
如果候选人最终仍然实现了排序解法，在面试中还可以再提示，是否能用上“有序”这个条件，进一步提高性能。
这样层层递进，能够较好地帮助我们判断候选人的编码能力。
不过机关算尽，还是遇到了比较挫败的case，比如一个候选人就反问：系统自带的函数效率最高啊，为什么要自己实现？
- 字节 -
到了字节跳动后，我发现这道题有点不够用了，撑死只能算 LeetCode Easy，对于有勇气来面试字节的候选人，通常都不在话下。
为了把它升级到 Medium，我想到了两个改动：
1. 两个不够，m个来凑
2. 数组太简单，得换成链表
然后一看，诶，这 tm 不就是 LeetCode 23 原题吗？
话说回来，这题就变成了：请把 m 个有序链表合并成一个新的有序链表；平均每个链表有 k 个节点。
- 解² -
不用说，所有候选人都能想到每次遍历所有链表、找到最小值加入新的链表。
对于选择这个思路的候选人，接下来的问题是：
Q1：这个方案的时间复杂度是多少呢？
有不少候选人回答 O(m * k)，大概是觉得两个链表合并是 O(2 * k)，m个链表合并自然是 O(m * k) 了。
实际上，使用这种思路，每次找到最小值需要逐个比较 m 个链表，这个操作需要执行 m * k 次（节点总数），因此总的时间复杂度应该是 O(m^2 * k)。
Q2：还有优化空间吗？
有些候选人确实想不到更优的解法，但只要能按这思路完成 bug free 的代码，综合面试中的其他表现，也可以通过我们的考查（详见 程序员面试指北：面试官视角）。
毕竟 LeetCode 23 原题可是 Hard 级别。
- 分治 -
对分治算法比较熟悉的候选人会想到，可以先两两合并，得到的 m / 2 个链表再两两合并，循环这个过程，直到只剩下一个链表。
然后又回到 Q1：这个方案的时间复杂度是多少呢？
这回答就千奇百怪了，O(m * log(k))，O(k * log(m)), O(m * k * log(k))……
这个计算其实不难：
* 第一轮需要 m/2 次两两合并，每次两两合并是 2k 次比较，合计 m*k
* 第二轮需要 m/4 次两两合并，每次两两合并是 4k 次比较（每个链表平均长度变成2k了），合计还是 m*k
* ……
* 对 m 个元素做二分，总共需要 log(m) 轮
所以合理的答案应该是 O(m * k * log(m))。
具体实现又可以分成上下两部分。
下层应该实现一个合并俩链表的逻辑，比较常见的错误是没能正确处理链表的头结点（比如直接当成尾节点用，或者忘记初始化，以及 C++ 小伙伴用了 new 以后常常忘了 delete），还有前面说到的，一个链表摘空了后，需要处理另一个链表剩下的节点。
上层的实现其实和归并排序长得一毛一样，可以 bottom-up，也可以 top-down。bottom-up 的实现常见的错误是没处理好落单的那一个，而 top-down 则需要注意递归的终止条件。
另外有点意外的是，不少 Java 小伙伴被 List 这个 Interface 荼毒还挺深，在编码的时候顺手就用 List.get(i) ，完全不考虑这个 API 的开销。
- 最小堆 -
对常见数据结构比较熟悉的候选人则会提出使用最小堆，这样可以将每次查找最小值的时间复杂度降为 log(m) ，于是总的时间复杂度也可以降为 O(m * k * log(m))。
既然提到了堆，那就可以顺便问一下，最小元素从堆顶被摘掉以后，如何调整堆？
于是那些只知道可以用最小堆、不知道如何实现堆的候选人就暴露出来了。
不过也不打紧，大部分语言的库里都实现了 PriorityQueue 这个数据结构，让候选人直接用语言提供的版本来编码就好。
具体的代码主要有两个坑，一是循环中要注意对摘空链表的处理，二是对链表头结点的处理（前面提到了）。
- 没完 -
面试到上面的程度就足够了，不然 45 分钟实在是不够用。
但其实还有些值得思考的问题没讲完。
比如说，这两种算法，平均时间复杂度都是 O(m * k * log(m))，到底哪一个更好呢？
分治算法的优势是，两两合并时，当一个链表为空，可以直接将另一个链表的剩余节点串起来，相比于堆算法可以节约一些时间。
另一方面，对于这样一个经典的多路归并问题，实际使用场景可能是要合并外存上的多个排好序的文件，这时候堆算法可以节约磁盘IO（只需要一次遍历），相比于分治算法就有了压倒性的优势。
所以具体还是要看场景。
再比如，在这个场景下，堆并不是最高效的数据结构。
实际上，堆算法只是多路归并的早期实现，由于每一层的调整都需要两次比较（先取出两个子节点的较小者，然后再和当前节点比较），其效率还有优化空间。
（堆的调整）
如果我们将用于比较的节点作为叶子节点构建一棵完全二叉树，从叶子节点往上只保存获胜的节点：
这样每一层只需要和其兄弟节点做比较即可。这就是所谓“胜者树”，说起来还是空间换时间的套路(多一倍的节点数）。
还没完 —— 这个方案对每一层的更新仍然需要访问3个节点（自己、兄弟节点，父节点），换个思路，如果我们在路径上只保存失败的值，再用一个额外的变量保存在根节点比较的获胜者：
于是我们对每一层的更新只需要访问当前节点和其父节点就好了。
由于每次保存的是失败者，这个方案又被称为“败者树”。
- 小结 -
这篇没有贴具体的代码，没试过的同学，正好可以用 LeetCode 23 来练手（传送门）。
照例小结一下：
* 笔试/面试题的区分度很重要；
* 归并排序是基础，bottom-up 和 top-down 都要熟；
* 多路归并可以用分治和堆来解决，时间复杂度最优；
* 通过败者树可以进一步优化堆的解法。
喜欢本文的小伙伴，别忘了分享给你的小伙伴，感谢~
---
推荐阅读：
* 程序员面试指北：面试官视角
* 踩坑记：go服务内存暴涨
* TCP：学得越多越不懂
* UTF-8：一些好像没什么用的冷知识
* (译) Ｃ程序员该知道的内存知识 (1)
Jul
26
在上一篇《踩坑记：Go服务灵异panic》里我们提到了 mutex 和 atomic ，感觉意犹未尽，这篇再展开一点。
- 锁 -
前面我们讲过好多面试题了，其实锁也很适合用来做套题，比如可以这么切入：sync.Mutex 是悲观锁还是乐观锁？
有些候选人不了解它们的区别，回答靠猜，缺乏逻辑以至于我都记不住。虽然这只是一个概念性的知识，但是却很能反映候选人的工作经验，比如读多写少的并发场景，乐观锁可以减少加锁冲突带来的开销。
当然大多数人还是知道的，于是可以继续问：你有了解过锁是怎么实现的吗？
很多人都能想到：维护一个初值为 false 的变量，当一个线程加锁成功的时候，将它置为 true ，就可以保证其他线程无法再获取。
逻辑是没错，但真正的问题是：两个线程同时检查，发现它的值都是 false ，如何保证只有一个线程会把它置为 true 呢？
这样的提问让不少候选人意识到，自己其实并没有真正理解锁。
- 原子操作 -
学过操作系统原理的同学应该都知道，靠的是原子操作（atomic operations）。
那么具体是什么原子操作呢？
在早期只有单核的系统上只需要关闭中断就可以保证原子地执行一段代码 —— 但这通常效率较低，且还存在些问题，例如因为 bug 或恶意代码导致未能正常开启中断，系统就会锁死；而对于多核系统，通常也无法做到在多个核心上同时关闭中断。
因此 CPU 引入了硬件支持的原子操作，例如 x86 体系下的 LOCK 信号（在汇编里给指令加上 LOCK 前缀），通过锁定总线，禁止其他 CPU 对内存的操作来保证原子性。但这样的锁粒度太粗，其他无关的内存操作也会被阻塞，大幅降低系统性能，而随着核数逐渐增加该问题会愈发显著 —— 要知道现在连家用 CPU 都有16核了。
因此 Intel 在 Pentium 486 开始引入了用于保证缓存一致性的 MESI 协议，通过锁定对应的 cache line，使得其他 core 无法修改指定内存，从而实现了原子操作（缓存锁）。这里不展开了，对细节感兴趣的话，详见参考资料《原子操作是如何实现的》[1]。
- CAS -
针对前面问的“什么原子操作”，大多数候选人的回答是 CAS （compare-and-swap），也有人会提到 test-and-set 等其他操作，原理都一样，就是用前述机制实现的。
下面这段 Go 代码展示了 CAS 的逻辑：
请注意：这不是 CAS 的实现，如前所述，真正的 CAS 是硬件级别的指令支持的，最早出现在 1970 年 IBM 的 System 370 上，在 x86 上则是 80486 开始新增的 CMPXCHG 这个指令。
注：在多核系统上 CMPXCHG 也需要使用 LOCK 前缀，但是如果对应内存已经在 cache 里，就不用发出 LOCK 信号锁定总线，而是使用缓存锁。
由于不用锁定总线，这样的原子操作指令不会限制其余 CPU core 操作非锁定内存，因此对系统整体的吞吐量影响不大。这一点对于当今核数越来越多的系统来说尤为重要。
由于原子操作指令仍然需要在 CPU 之间传递消息用于对 cache line 的锁定，其性能仍有一定损耗，具体来说大概就相当于一个未命中 cache 的 Load Memory 指令[2]。
基于 CAS 我们可以用实现很多实用的原子操作，例如原子加法：
看，这就是一个典型的使用乐观锁的实现了：先做加法，如果更新失败，就换个姿势再来一次。
注：Go 语言 atomic.AddInt32 的实现是直接使用汇编 LOCK XADDL 完成的，不是基于 CAS 和循环。
- 自旋锁 -
回到锁的问题上，基于 CAS 我们可以很容易实现一个锁：
这就是经典的自旋锁[3] —— 通过反复检测锁变量是否可用来完成加锁。在加锁过程中 CPU 是在忙等待，因此仅适用于阻塞较短时间的场合；其优势在于避免了线程切换的开销。
注：spinlock 是 Linux 内核中主要的两种锁之一（另一种是Mutex），感兴趣的同学可以去看看内核源码里的实现，具体位于 include/asm/spinlock.h （吐槽：内核源码真是难读）。
在 Go 版的实现里还要注意：如果 GOMAXPROCS 被设置成 1 （Go Runtime只会给用户代码分配一个系统线程），会导致上述代码陷入死循环，因此更完善的实现是：
通过将当前系统线程的使用权暂时归还给 Go Runtime（相当于其他语言的 yield），可以避免前述情况，但这也在一定程度上破坏了自旋锁的语义、使其变得更重了。
值得一提的是，研究人员发现，如果锁冲突比较频繁，在 CAS 失败时使用指数退避算法（Exponential Backoff）往往能得到更好的整体性能[2]。
- Mutex -
实际上 Go 语言没有提供自带的自旋锁实现，我们在代码中用得更多的是 Mutex 。
对比于 Spinlock 的忙等待，如果 Mutex 未获得锁，会释放对 CPU 的占用。
上一篇 我们在说 Mutex 性能不够好的时候有提到“lock does not scale with the number of the processors”，这里的 lock 指的是用 CPU LOCK信号实现的锁；而通过阅读 Mutex 的源码，我发现实际上 Mutex 底层也是使用原子操作来实现的，所以前述说法不太准确。
Mutex 针对实际应用场景做了许多优化，是一个从轻量级锁逐渐升级到重量级锁的过程，从而平衡了各种场景下的需求和性能。
具体来说有这么几项：
* fastpath：在简单场景下直接使用 CAS 加锁和解锁，缩短执行路径
* spin：当自旋有意义时（多核、GOMAXPROCS > 1 、尝试不超过4次），优先使用自旋
* 饥饿 & 公平：当等待超过 1ms 时，进入饥饿模式，新竞争者需要排队
注：对具体实现感兴趣的同学，可以结合参考资料《golang中的锁源码实现：Mutex》[5] 阅读源码。
这里提到的“公平”，指的是先到先得，这意味着每一个竞争者都需要进入等待队列，而这意味着CPU控制权的切换和对应的开销；而非公平锁，指的是在进入等待队列之前先尝试加锁，如果加锁成功，可以减少排队从而提高性能，但代价是队列中的竞争者可能会处于“饥饿”状态。
- sync -
除了 Mutex，Go 在 sync 包里还实现了很多用于解决并发问题的工具，这里简单介绍下：
· RWMutex
读写锁，通过将资源的访问者分成读者和写者，允许多个读者同时访问资源，从而提高共享资源的并发度。适用于读远多于写的场景。
· WaitGroup
用于对 goroutine 的并发控制，在主 goroutine 里使用 Add(n) 指定并发数量，并使用 Wait() 等待所有任务都调用 Done() （配合 defer 使用效果更佳）。
· Pool
对象池，用于缓存后续会用到的对象，从而缓解 gc 压力。例如 fmt 包用它来缓存输出缓冲区。
· Once
“单例”：once.Do(f) 保证 f 只会被执行一次。f 被执行后，通过原子操作保证了性能。
· Cond
条件同步：当条件不满足时（通常是等待一个任务执行完成），goroutine调用 Wait() 等待通知；另一个 goroutine 完成任务后，调用 Signal() 或 Broadcast() 通知在等待的 goroutine。
· Map
支持并发的 map：通过 Load、Store、LoadOrStore、Delete、Range 等方法提供线程安全的 map 数据结构。
· atomic
提供 Add、CAS、Load、Store、Swap 等对基础数据类型的原子操作，以及 atomic.Value 来支持其他类型的 Load、Store 原子操作。
- 收尾 -
哎呀，这篇写得干巴巴的，连一个表情包都没有（忍住）。
最后照例小结一下：
* 锁是基于原子操作实现的，而原子操作是需要硬件支持的
* 基于 MESI 协议的缓存锁可以提高锁的性能
* 比较常用的原子操作是 CAS
* Go 没有官方自旋锁，我们通常用 sync.Mutex
* sync 包里还有很多解决并发问题的实用工具
下次考虑结合一些具体案例来讲讲，可能更有意思一点儿~
---
推荐阅读：
* 程序员面试指北：面试官视角
* 踩坑记：go服务内存暴涨
* TCP：学得越多越不懂
* UTF-8：一些好像没什么用的冷知识
* (译) Ｃ程序员该知道的内存知识 (1)
---
参考资料：
1. 原子操作是如何实现的？
2. Compare-and-swap
3. 自旋锁
4. 聊聊CPU的LOCK指令
5. golang中的锁源码实现：Mutex
- 锁 -
前面我们讲过好多面试题了，其实锁也很适合用来做套题，比如可以这么切入：sync.Mutex 是悲观锁还是乐观锁？
有些候选人不了解它们的区别，回答靠猜，缺乏逻辑以至于我都记不住。虽然这只是一个概念性的知识，但是却很能反映候选人的工作经验，比如读多写少的并发场景，乐观锁可以减少加锁冲突带来的开销。
当然大多数人还是知道的，于是可以继续问：你有了解过锁是怎么实现的吗？
很多人都能想到：维护一个初值为 false 的变量，当一个线程加锁成功的时候，将它置为 true ，就可以保证其他线程无法再获取。
逻辑是没错，但真正的问题是：两个线程同时检查，发现它的值都是 false ，如何保证只有一个线程会把它置为 true 呢？
这样的提问让不少候选人意识到，自己其实并没有真正理解锁。
- 原子操作 -
学过操作系统原理的同学应该都知道，靠的是原子操作（atomic operations）。
那么具体是什么原子操作呢？
在早期只有单核的系统上只需要关闭中断就可以保证原子地执行一段代码 —— 但这通常效率较低，且还存在些问题，例如因为 bug 或恶意代码导致未能正常开启中断，系统就会锁死；而对于多核系统，通常也无法做到在多个核心上同时关闭中断。
因此 CPU 引入了硬件支持的原子操作，例如 x86 体系下的 LOCK 信号（在汇编里给指令加上 LOCK 前缀），通过锁定总线，禁止其他 CPU 对内存的操作来保证原子性。但这样的锁粒度太粗，其他无关的内存操作也会被阻塞，大幅降低系统性能，而随着核数逐渐增加该问题会愈发显著 —— 要知道现在连家用 CPU 都有16核了。
因此 Intel 在 Pentium 486 开始引入了用于保证缓存一致性的 MESI 协议，通过锁定对应的 cache line，使得其他 core 无法修改指定内存，从而实现了原子操作（缓存锁）。这里不展开了，对细节感兴趣的话，详见参考资料《原子操作是如何实现的》[1]。
- CAS -
针对前面问的“什么原子操作”，大多数候选人的回答是 CAS （compare-and-swap），也有人会提到 test-and-set 等其他操作，原理都一样，就是用前述机制实现的。
下面这段 Go 代码展示了 CAS 的逻辑：
func CompareAndSwap(p *int, oldValue int, newValue int) bool {
if *p != oldValue {
return false
}
*p = newValue
return true
}
if *p != oldValue {
return false
}
*p = newValue
return true
}
请注意：这不是 CAS 的实现，如前所述，真正的 CAS 是硬件级别的指令支持的，最早出现在 1970 年 IBM 的 System 370 上，在 x86 上则是 80486 开始新增的 CMPXCHG 这个指令。
注：在多核系统上 CMPXCHG 也需要使用 LOCK 前缀，但是如果对应内存已经在 cache 里，就不用发出 LOCK 信号锁定总线，而是使用缓存锁。
由于不用锁定总线，这样的原子操作指令不会限制其余 CPU core 操作非锁定内存，因此对系统整体的吞吐量影响不大。这一点对于当今核数越来越多的系统来说尤为重要。
由于原子操作指令仍然需要在 CPU 之间传递消息用于对 cache line 的锁定，其性能仍有一定损耗，具体来说大概就相当于一个未命中 cache 的 Load Memory 指令[2]。
基于 CAS 我们可以用实现很多实用的原子操作，例如原子加法：
func atomicAdd(p *int32, incr int32) int32 {
for {
oldValue := *p
newValue := oldValue + incr
if atomic.CompareAndSwapInt32(p, oldValue, newValue) {
return newValue
}
}
}
for {
oldValue := *p
newValue := oldValue + incr
if atomic.CompareAndSwapInt32(p, oldValue, newValue) {
return newValue
}
}
}
看，这就是一个典型的使用乐观锁的实现了：先做加法，如果更新失败，就换个姿势再来一次。
注：Go 语言 atomic.AddInt32 的实现是直接使用汇编 LOCK XADDL 完成的，不是基于 CAS 和循环。
- 自旋锁 -
回到锁的问题上，基于 CAS 我们可以很容易实现一个锁：
type spinLock int32
func (p *spinLock) Lock() {
for !atomic.CompareAndSwapInt32((*int32)(p), 0, 1) {
}
}
func (p *spinLock) Unlock() {
atomic.StoreInt32((*int32)(p), 0)
}
func (p *spinLock) Lock() {
for !atomic.CompareAndSwapInt32((*int32)(p), 0, 1) {
}
}
func (p *spinLock) Unlock() {
atomic.StoreInt32((*int32)(p), 0)
}
这就是经典的自旋锁[3] —— 通过反复检测锁变量是否可用来完成加锁。在加锁过程中 CPU 是在忙等待，因此仅适用于阻塞较短时间的场合；其优势在于避免了线程切换的开销。
注：spinlock 是 Linux 内核中主要的两种锁之一（另一种是Mutex），感兴趣的同学可以去看看内核源码里的实现，具体位于 include/asm/spinlock.h （吐槽：内核源码真是难读）。
在 Go 版的实现里还要注意：如果 GOMAXPROCS 被设置成 1 （Go Runtime只会给用户代码分配一个系统线程），会导致上述代码陷入死循环，因此更完善的实现是：
func (p *spinLock) Lock() {
for !atomic.CompareAndSwapInt32((*int32)(p), 0, 1) {
runtime.Gosched()
}
}
for !atomic.CompareAndSwapInt32((*int32)(p), 0, 1) {
runtime.Gosched()
}
}
通过将当前系统线程的使用权暂时归还给 Go Runtime（相当于其他语言的 yield），可以避免前述情况，但这也在一定程度上破坏了自旋锁的语义、使其变得更重了。
值得一提的是，研究人员发现，如果锁冲突比较频繁，在 CAS 失败时使用指数退避算法（Exponential Backoff）往往能得到更好的整体性能[2]。
- Mutex -
实际上 Go 语言没有提供自带的自旋锁实现，我们在代码中用得更多的是 Mutex 。
对比于 Spinlock 的忙等待，如果 Mutex 未获得锁，会释放对 CPU 的占用。
上一篇 我们在说 Mutex 性能不够好的时候有提到“lock does not scale with the number of the processors”，这里的 lock 指的是用 CPU LOCK信号实现的锁；而通过阅读 Mutex 的源码，我发现实际上 Mutex 底层也是使用原子操作来实现的，所以前述说法不太准确。
Mutex 针对实际应用场景做了许多优化，是一个从轻量级锁逐渐升级到重量级锁的过程，从而平衡了各种场景下的需求和性能。
具体来说有这么几项：
* fastpath：在简单场景下直接使用 CAS 加锁和解锁，缩短执行路径
* spin：当自旋有意义时（多核、GOMAXPROCS > 1 、尝试不超过4次），优先使用自旋
* 饥饿 & 公平：当等待超过 1ms 时，进入饥饿模式，新竞争者需要排队
注：对具体实现感兴趣的同学，可以结合参考资料《golang中的锁源码实现：Mutex》[5] 阅读源码。
这里提到的“公平”，指的是先到先得，这意味着每一个竞争者都需要进入等待队列，而这意味着CPU控制权的切换和对应的开销；而非公平锁，指的是在进入等待队列之前先尝试加锁，如果加锁成功，可以减少排队从而提高性能，但代价是队列中的竞争者可能会处于“饥饿”状态。
- sync -
除了 Mutex，Go 在 sync 包里还实现了很多用于解决并发问题的工具，这里简单介绍下：
· RWMutex
读写锁，通过将资源的访问者分成读者和写者，允许多个读者同时访问资源，从而提高共享资源的并发度。适用于读远多于写的场景。
· WaitGroup
用于对 goroutine 的并发控制，在主 goroutine 里使用 Add(n) 指定并发数量，并使用 Wait() 等待所有任务都调用 Done() （配合 defer 使用效果更佳）。
· Pool
对象池，用于缓存后续会用到的对象，从而缓解 gc 压力。例如 fmt 包用它来缓存输出缓冲区。
· Once
“单例”：once.Do(f) 保证 f 只会被执行一次。f 被执行后，通过原子操作保证了性能。
· Cond
条件同步：当条件不满足时（通常是等待一个任务执行完成），goroutine调用 Wait() 等待通知；另一个 goroutine 完成任务后，调用 Signal() 或 Broadcast() 通知在等待的 goroutine。
· Map
支持并发的 map：通过 Load、Store、LoadOrStore、Delete、Range 等方法提供线程安全的 map 数据结构。
· atomic
提供 Add、CAS、Load、Store、Swap 等对基础数据类型的原子操作，以及 atomic.Value 来支持其他类型的 Load、Store 原子操作。
- 收尾 -
哎呀，这篇写得干巴巴的，连一个表情包都没有（忍住）。
最后照例小结一下：
* 锁是基于原子操作实现的，而原子操作是需要硬件支持的
* 基于 MESI 协议的缓存锁可以提高锁的性能
* 比较常用的原子操作是 CAS
* Go 没有官方自旋锁，我们通常用 sync.Mutex
* sync 包里还有很多解决并发问题的实用工具
下次考虑结合一些具体案例来讲讲，可能更有意思一点儿~
---
推荐阅读：
* 程序员面试指北：面试官视角
* 踩坑记：go服务内存暴涨
* TCP：学得越多越不懂
* UTF-8：一些好像没什么用的冷知识
* (译) Ｃ程序员该知道的内存知识 (1)
---
参考资料：
1. 原子操作是如何实现的？
2. Compare-and-swap
3. 自旋锁
4. 聊聊CPU的LOCK指令
5. golang中的锁源码实现：Mutex
Jul
18
这个坑比较新鲜，周一刚填完，还冒着冷气。
- 1 -
在字节跳动，我们线上服务的所有 log 都通过统一的日志库采集到流式日志服务、落地 ES 集群，配上字节云超(sang)级(xin)强(bing)大(kuang)的监控能力，每一条 panic log 都可以触发一个打给值班同学的电话。
所以我们常常不选电话，只选飞书 ↓↓↓
但毕竟是 panic，大部分 case 都会迅速被就地正法，除了少数排查费劲、又不对线上产生太大影响的，比如这一个：
注：为了方便阅读，略有简化。
你看，它可以被 recover 兜住（不会把服务搞挂），而且出现频率很低（每天几次甚至没有），考虑到在每天数百亿请求中的占比，解决它的 ROI 实在太低，所以就耽搁了一段时间且不用担心背 P0 的锅。
- 2 -
其实之前 S 同学和我都关注过这个 panic ，从上面的 Error log 可以看到，错误发生在调用 json.Marshal 的时候，调用方的代码大概长这样：
注：实际map有更多key/value，这里略作简化。
看这代码，第一反应是：这**也能 panic ？
找到对应的 json 库源码（encode.go第880行，对应下面第5行）：
—— 也只是从string里逐个读取字符，看着并没什么猫饼。
由于 panic 发生在官方 json 库里，不适合修改并部署到全量机器；引入第三方 json 库又涉及很多依赖问题，所以当时没再跟进。
直到最近 panic 频率逐渐升高， H 和 L 同学实在看不下去了。
- 3 -
L 同学的思路是，既然这个 panic 能被 recover 兜住，那为什么不看看 panic 时这个 map 里装了什么呢？
于是代码就变成了这样：
然后 panic 顺利转移到了 log.Warnf 这一行[doge]
- 4 -
不管怎么说成功地转移了问题，只要把 log.Warnf 这一行注释掉……
作为一个追求极致的 ByteDancer，L 同学抵制住了诱惑并尝试了新的思路，既然从 panic log 看到是跪在了一个 string 上，那至少先看看是哪一个string：
改起来倒是很简单，赶在这个需要上班的 周日下午发了车，晚上就捉到了一个case。
通过线上 log，我们发现错误出现在 "step" 这个 key 上（log里有输出key、但没输出value），value 本应是 ctx.StepName 这个 string。
可是 string 这种看起来人畜无害的 immutable 的 type 为什么会导致 panic 呢？
- 5 -
通过走读代码得知，在遇到异常的时候，我们会往 ctx.StepName 写入这个异常点的名称，就像这样：
一边读一边写，有那么点并发的味道了。
考虑到我们为了降低媒体感知的超时率，将整个广告的召回流程包装成一个带时间限制的任务：
因此在一个请求流程中，确实可能会出现并发读写 ctx.StepName 这个 string object 的情况。
但如何实锤是这儿挖的坑呢？
- 6 -
在线上服务中直接验证这一点不太容易，但是 H 同学做了一个简单的 POC，大概像这样：
代码一跑起来就有点味道了：
虽然没看到 panic，但是确实看到了点奇怪的东西（严正声明：不是故意要吐槽GO的GC）。
再用 go 的 race detector 瞅瞅：
这下可算是实锤了。
- 7 -
那么为什么 string 的并发读写会出现这种现象呢？
这就得从 string 底层的数据结构说起了。在 go 的 reflect 包里有一个 type StringHeader ，对应的就是 string 在 go runtime的表示：
可以看到， string 由一个指针（指向字符串实际内容）和一个长度组成。
比如说我们可以这么玩弄 StringHeader：
对于这样一个 struct ，golang 无法保证原子性地完成赋值，因此可能会出现goroutine 1 刚修改完指针（Data）、还没来得及修改长度（Len），goroutine 2 就读取了这个string 的情况。
因此我们看到了 "WHAT" 这个输出 —— 这就是将 s 从 "F*CK" 改成 "WHAT THE" 时，Data 改了、Len 还没来得及改的情况（仍然等于4）。
至于 "F*CKGOGC" 则正好相反，而且显然是出现了越界，只不过越界访问的地址仍然在进程可访问的地址空间里。
- 8 -
既然问题定位到了，解决起来就很简单了。
最直接的方法是使用 sync.Mutex：
但 Mutex 性能不够好（lock does not scale with the number of the processors），对于这种读写冲突概率很小的场景，性能更好的方案是将 ctx.StepName 类型改成 atomic.Value，然后
注：也可以改成 *string 然后使用 atomic.StorePointer
实际上，Golang 不保证任何单独的操作是原子性的，除非使用 atomic 包里提供的原语或加锁。
- 9 -
大结局：周一下午 H 同学提交了修复代码并完成发布，这个 panic 就再没出现了。
总结一下：
* string 没有看起来那么人畜无害
* 并发的坑可以找 -race 帮帮忙
* 记得使用 mutex 或 atomic
最后留下一个小问题供思考：
这说了半天并没有完全复现 panic，不过文中已经给了足够多的工具，你能想到怎么办吗？
推荐阅读:
* 程序员面试指北：面试官视角
* 踩坑记：go服务内存暴涨
* TCP：学得越多越不懂
* UTF-8：一些好像没什么用的冷知识
* [译] Ｃ程序员该知道的内存知识 (1)
- 1 -
在字节跳动，我们线上服务的所有 log 都通过统一的日志库采集到流式日志服务、落地 ES 集群，配上字节云超(sang)级(xin)强(bing)大(kuang)的监控能力，每一条 panic log 都可以触发一个打给值班同学的电话。
所以我们常常不选电话，只选飞书 ↓↓↓
但毕竟是 panic，大部分 case 都会迅速被就地正法，除了少数排查费劲、又不对线上产生太大影响的，比如这一个：
Error: invalid memory address or nil pointer dereference
Traceback:
goroutine 68532877 [running]:
...
src/encoding/json/encode.go:880 +0x59
encoding/json.stringEncoder(0xcb9fead550, ...)
...
src/encoding/json/encode.go:298 +0xa5
encoding/json.Marshal(0x1ecb9a0, ...)
...
/path/to/util.SendData(0xca813cd300)
Traceback:
goroutine 68532877 [running]:
...
src/encoding/json/encode.go:880 +0x59
encoding/json.stringEncoder(0xcb9fead550, ...)
...
src/encoding/json/encode.go:298 +0xa5
encoding/json.Marshal(0x1ecb9a0, ...)
...
/path/to/util.SendData(0xca813cd300)
注：为了方便阅读，略有简化。
你看，它可以被 recover 兜住（不会把服务搞挂），而且出现频率很低（每天几次甚至没有），考虑到在每天数百亿请求中的占比，解决它的 ROI 实在太低，所以就耽搁了一段时间
- 2 -
其实之前 S 同学和我都关注过这个 panic ，从上面的 Error log 可以看到，错误发生在调用 json.Marshal 的时候，调用方的代码大概长这样：
func SendData(...) {
data := map[string]interface{} {
"code": ctx.ErrorCode,
"message": ctx.Message,
"step": ctx.StepName,
}
msg, err := json.Marshal(data)
...
}
data := map[string]interface{} {
"code": ctx.ErrorCode,
"message": ctx.Message,
"step": ctx.StepName,
}
msg, err := json.Marshal(data)
...
}
注：实际map有更多key/value，这里略作简化。
看这代码，第一反应是：这**也能 panic ？
找到对应的 json 库源码（encode.go第880行，对应下面第5行）：
func (e *encodeState) string(s string, escapeHTML bool) {
e.WriteByte('"')
start := 0
for i := 0; i < len(s); {
if b := s[i]; b < utf8.RuneSelf {
...
e.WriteByte('"')
start := 0
for i := 0; i < len(s); {
if b := s[i]; b < utf8.RuneSelf {
...
—— 也只是从string里逐个读取字符，看着并没什么猫饼。
由于 panic 发生在官方 json 库里，不适合修改并部署到全量机器；引入第三方 json 库又涉及很多依赖问题，所以当时没再跟进。
直到最近 panic 频率逐渐升高， H 和 L 同学实在看不下去了。
- 3 -
L 同学的思路是，既然这个 panic 能被 recover 兜住，那为什么不看看 panic 时这个 map 里装了什么呢？
于是代码就变成了这样：
defer func() {
if p := recover(); p != nil {
log.Warnf("Error: %v, data: %v", p, data)
}
}()
data := map[string]...
if p := recover(); p != nil {
log.Warnf("Error: %v, data: %v", p, data)
}
}()
data := map[string]...
然后 panic 顺利转移到了 log.Warnf 这一行[doge]
- 4 -
不管怎么说成功地转移了问题，只要把 log.Warnf 这一行注释掉……
作为一个追求极致的 ByteDancer，L 同学抵制住了诱惑并尝试了新的思路，既然从 panic log 看到是跪在了一个 string 上，那至少先看看是哪一个string：
data := make(map[string]interface{})
defer func() {
if p := recover(); p != nil {
for k, v := range data {
log.Warnf("CatchMe: k=%v", k)
log.Warnf("CatchMe: v=%v", v)
}
}
}()
...
defer func() {
if p := recover(); p != nil {
for k, v := range data {
log.Warnf("CatchMe: k=%v", k)
log.Warnf("CatchMe: v=%v", v)
}
}
}()
...
改起来倒是很简单，赶在这个
通过线上 log，我们发现错误出现在 "step" 这个 key 上（log里有输出key、但没输出value），value 本应是 ctx.StepName 这个 string。
可是 string 这种看起来人畜无害的 immutable 的 type 为什么会导致 panic 呢？
- 5 -
通过走读代码得知，在遇到异常的时候，我们会往 ctx.StepName 写入这个异常点的名称，就像这样：
const STEP_XX = "XX"
func XX(...) {
if err := process(); err != nil {
ctx.StepName = STEP_XX
}
}
func XX(...) {
if err := process(); err != nil {
ctx.StepName = STEP_XX
}
}
一边读一边写，有那么点并发的味道了。
考虑到我们为了降低媒体感知的超时率，将整个广告的召回流程包装成一个带时间限制的任务：
finished := make(chan struct{})
timer := time.NewTimer(duration)
go recall(finished)
select {
case <-finished:
sendResponse()
case <- timer.C:
sendTimeoutResponse()
}
timer := time.NewTimer(duration)
go recall(finished)
select {
case <-finished:
sendResponse()
case <- timer.C:
sendTimeoutResponse()
}
因此在一个请求流程中，确实可能会出现并发读写 ctx.StepName 这个 string object 的情况。
但如何实锤是这儿挖的坑呢？
- 6 -
在线上服务中直接验证这一点不太容易，但是 H 同学做了一个简单的 POC，大概像这样：
const (
FIRST = "WHAT THE"
SECOND = "F*CK"
)
func main() {
var s string
go func() {
i := 1
for {
i = 1 - i
if i == 0 {
s = FIRST
} else {
s = SECOND
}
time.Sleep(10)
}
}()
for {
fmt.Println(s)
time.Sleep(10)
}
}
FIRST = "WHAT THE"
SECOND = "F*CK"
)
func main() {
var s string
go func() {
i := 1
for {
i = 1 - i
if i == 0 {
s = FIRST
} else {
s = SECOND
}
time.Sleep(10)
}
}()
for {
fmt.Println(s)
time.Sleep(10)
}
}
代码一跑起来就有点味道了：
$ go run poc.go
WHAT THE
F*CK
...
WHAT
WHAT
WHAT
F*CKGOGC
...
WHAT THE
F*CK
...
WHAT
WHAT
WHAT
F*CKGOGC
...
虽然没看到 panic，但是确实看到了点奇怪的东西（严正声明：不是故意要吐槽GO的GC）。
再用 go 的 race detector 瞅瞅：
$ go run -race poc.go >/dev/null
==================
WARNING: DATA RACE
Write at 0x00c00011c1e0 by goroutine 7:
main.main.func1()
poc.go:19 +0x66（赋值那行）
Previous read at 0x00c00011c1e0 by main goroutine:
main.main()
poc.go:28 +0x9d（println那行）
==================
WARNING: DATA RACE
Write at 0x00c00011c1e0 by goroutine 7:
main.main.func1()
poc.go:19 +0x66（赋值那行）
Previous read at 0x00c00011c1e0 by main goroutine:
main.main()
poc.go:28 +0x9d（println那行）
这下可算是实锤了。
- 7 -
那么为什么 string 的并发读写会出现这种现象呢？
这就得从 string 底层的数据结构说起了。在 go 的 reflect 包里有一个 type StringHeader ，对应的就是 string 在 go runtime的表示：
type StringHeader struct {
Data uintptr
Len int
}
Data uintptr
Len int
}
可以看到， string 由一个指针（指向字符串实际内容）和一个长度组成。
比如说我们可以这么玩弄 StringHeader：
s := "hello"
p := *(*reflect.StringHeader)(unsafe.Pointer(&s))
fmt.Println(p.Len)
p := *(*reflect.StringHeader)(unsafe.Pointer(&s))
fmt.Println(p.Len)
对于这样一个 struct ，golang 无法保证原子性地完成赋值，因此可能会出现goroutine 1 刚修改完指针（Data）、还没来得及修改长度（Len），goroutine 2 就读取了这个string 的情况。
因此我们看到了 "WHAT" 这个输出 —— 这就是将 s 从 "F*CK" 改成 "WHAT THE" 时，Data 改了、Len 还没来得及改的情况（仍然等于4）。
至于 "F*CKGOGC" 则正好相反，而且显然是出现了越界，只不过越界访问的地址仍然在进程可访问的地址空间里。
- 8 -
既然问题定位到了，解决起来就很简单了。
最直接的方法是使用 sync.Mutex：
func (ctx *Context) SetStep(step string) {
ctx.Mutex.Lock()
defer ctx.Mutex.Unlock()
ctx.StepName = Step
}
ctx.Mutex.Lock()
defer ctx.Mutex.Unlock()
ctx.StepName = Step
}
但 Mutex 性能不够好（lock does not scale with the number of the processors），对于这种读写冲突概率很小的场景，性能更好的方案是将 ctx.StepName 类型改成 atomic.Value，然后
ctx.StepName.Store(step)
注：也可以改成 *string 然后使用 atomic.StorePointer
实际上，Golang 不保证任何单独的操作是原子性的，除非使用 atomic 包里提供的原语或加锁。
- 9 -
大结局：周一下午 H 同学提交了修复代码并完成发布，这个 panic 就再没出现了。
总结一下：
* string 没有看起来那么人畜无害
* 并发的坑可以找 -race 帮帮忙
* 记得使用 mutex 或 atomic
最后留下一个小问题供思考：
这说了半天并没有完全复现 panic，不过文中已经给了足够多的工具，你能想到怎么办吗？
推荐阅读:
* 程序员面试指北：面试官视角
* 踩坑记：go服务内存暴涨
* TCP：学得越多越不懂
* UTF-8：一些好像没什么用的冷知识
* [译] Ｃ程序员该知道的内存知识 (1)
Jul
11
Linux里养僵尸是怎么回事呢？Linux相信大家都很熟悉，但是Linux里养僵尸是怎么回事呢，下面就让小编带大家一起了解吧。
# - 1 -
上一篇挖了个 SIGHUP 的坑，这篇试着填一下。
之前在《程序员面试指北：面试官视角》里面说过，在结构化面试中，我们会从各个方向去考查候选人，其中之一是操作系统。
上篇介绍了一套题，我还有另一套，一般这么开场：
在终端下启动一个命令，如果在命令结束前关掉终端，它还能正常运行吗？
# - 2 -
这其实是一个很常见的case，但凡 Linux 或者 Mac 用得多一点，都会遇到。
在我还是一个穷酸学生的2009年，每个月都需要支付 20 元巨款（当时能买3根鸭脖），通过一个禁止分享网络的认证客户端接入校园网。
为了共建和谐宿舍节省网费 ，我历经千辛万苦，交叉编译开源的Linux认证客户端，集成到固件里，并刷到了我的 NETGEAR 路由器上。
然后山水 BBS 的 Linux 版主把我的帖子置顶了 11 年。可见他有多痛恨禁止共享网络
这么一回忆，感觉自己的共享经济思维真是前卫，当时怎么就没想到去搞共享单车呢？
扯远了，在捣腾的过程中，我就踩了这么个坑：当我ssh到路由器上、刚启动认证时，能够正常联网；但是退出ssh后一会，网就断了。
经过一番捣腾后发现，只要一退出ssh，认证程序就凉了，而不是继续在后台保持和认证服务器的通信。
# - 3 -
所以前面那个问题，我以为大部分候选人应该会回答“否”，但没想到竟然还有不少人回答“是”。
其实回答“是”也没什么错，因为确实也有些命令不会随着终端关闭而结束。
问题是当我追问当时执行的是什么命令时，候选人往往又说不出个所以然来。
（借学长的表情一用）
然后我就感到很强的挫败感：这不按剧本来，没法问了啊……只好换题。
当然大部分候选人确实被坑过，于是我可以接着问：
如果确实需要在后台继续执行命令怎么办呢？
有些人只记得要在后面加个 & ；但也有不少人知道前面还得加个 nohup，就像这样：
注：其实我更喜欢 screen（或 tmux），偶尔也用 setsid 。
然后就可以放心地关闭终端开始放羊 了。
但我的套题还没结束：为什么加上 nohup 就可以让进程在后台继续运行呢？
（这表情熟悉吗）
# - 4 -
铺垫了这么多，总算是可以开始填坑了。
答案其实很好找，man nohup 就能看到：
nohup工具在启动命令的同时会将 SIGHUP 信号设置为忽略。
而关于 SIGHUP，Wikipedia原文是这样介绍的：
对于 POSIX 兼容的平台（如Unix、Linux、BSD、Mac），当进程所在的控制终端关闭时，系统会给进程发送 SIGHUP 信号（Signal Hang Up，挂断信号）。
为什么叫 SIGHUP 呢？（严正申明：这一问不在套题里[doge])
我们知道，在上古时代，捉 bug 就已经是码农的必备技能（更准确地说是 moth）。
（我总觉得这个图是假的）
到了远古时代，他们不再需要去机房，通过基于 RS-232 协议的串行线路连接到大型机的终端上，就可以开始收福报。
收完福报，程序员通知自己的猫（modem）挂断（Hang Up）连接；大型机的 OS 检测到连接断开，就会给进程发送信号 —— 所以这信号被称为 SIGHUP 。
这果然是毫无卵用的知识啊。
# - 5 -
很多同学在操作系统的课程上学习了“进程间的通信方式有信号、管道、消息队列、共享内存……”，但是对信号到底是个什么东西，并没有现实的概念。
课堂教学的理论和实践往往是割裂的，在此特别推荐《Unix环境高级编程》（简称APUE）。
APUE在 1.9 - 信号 中写到：信号是通知进程已发生某种条件的一种技术。
而在 Linux/Unix 下，进程对信号的处理有三种选择：
* 按系统默认方式处理
* 提供一个回调函数
* 或忽略该信号（有些信号例外，不允许被忽略）
以 SIGHUP 信号为例，系统默认处理方式就是结束进程。
当然终端下打开的第一个进程通常都是shell（例如bash）。shell会给 SIGHUP 信号注册一个回调函数，用于给该 shell 下所有的子进程发送 SIGHUP 信号，然后再主动退出。
对于求生欲很强的程序（例如nohup），可以主动选择忽略该信号。
有一些进程本来就被设计成在后台运行，不需要控制终端，因此它们将 SIGHUP 挪作它用，一个常见的用法就是重新读取配置文件（例如Apache、Nginx），上篇提到的 logrotate 正是利用了这一点。
终于填完了坑。
# - 6 -
说了这么多都还是纸上谈兵，实操中如何主动忽略 SIGHUP 呢？
实际上也很简单，使用 Linux 的 signal 系统调用即可：
不妨试试看，编译运行起来，即使关闭终端，它也会在后台继续运行。
signal 也可以用于指定回调函数（或重置为系统默认处理方式），这里就不展开了，感兴趣的同学可以参考 APUE 里的代码，以及阅读 signal 的manual。
使用回调函数还需要注意一个坑：
由于回调函数可能在任意时刻被触发，因此要避免调用不可重入的函数（典型如printf）。常见的做法是 set 一个 flag，然后在程序的主循环中检测该 flag，再按需执行相应任务。
# - 7 -
SIGHUP 只是常见的一个信号，在 Linux 下，信号还有大量其他的场景和应用。
当你按下 Ctrl + C ，就是给进程发送了一个 SIGINT 信号。
当你执行 kill -TERM $PID，就是给进程发送了一个 SIGTERM 信号。可能和你期望有出入的是，SIGTERM 是可以被进程忽略的。所以有时候你得用 SIGKILL (kill -9) 。
你还可以使用可自定义的 SIGUSR1、SIGUSR2、SIGURG 来实现一些功能，比如《踩坑记#2：Go服务锁死》中提到 Golang 在其 goroutine 调度中使用了 SIGURG 。
# - 8 -
这次就不总结了，最后再用一个和信号有关的 case 收尾。
Linux 内核会为每一个进程分配一个 task_struct 结构体，用于保存进程的相关信息。
在进程死亡后，系统会发送一个 SIGCHLD 信号给它的父进程。
正确的父进程实现，通常应当使用 wait 系统调用来给子进程收尸 —— 父进程往往需要知道子进程结束这个事件，而且可能还需要得知其退出原因（exit code）。
然后内核才会将对应的 task_struct 释放。
如果父进程没有收尸，task_struct 里的 state 会一直保持为 EXIT_ZOMBIE，这时在 ps 或 top 等命令里，就可以看到该进程的状态为 Z ，而且无法被 kill 。
这就是所谓的僵尸进程，这时候你找九叔都没用。
（大半夜找这图还挺渗人的）
所以Linux里养僵尸，其实就是子进程死了父进程不收尸，大家可能会很惊讶Linux里怎么会养僵尸呢？但事实就是这样，小编也感到非常惊讶。
这就是关于Linux里养僵尸的事情了，大家有什么想法呢，欢迎在评论区告诉小编一起讨论哦！
---
推荐阅读
* 程序员面试指北：面试官视角
* 踩坑记：go服务内存暴涨
* TCP：学得越多越不懂
* UTF-8：一些好像没什么用的冷知识
* [译] Ｃ程序员该知道的内存知识 (1)
# - 1 -
上一篇挖了个 SIGHUP 的坑，这篇试着填一下。
之前在《程序员面试指北：面试官视角》里面说过，在结构化面试中，我们会从各个方向去考查候选人，其中之一是操作系统。
上篇介绍了一套题，我还有另一套，一般这么开场：
在终端下启动一个命令，如果在命令结束前关掉终端，它还能正常运行吗？
# - 2 -
这其实是一个很常见的case，但凡 Linux 或者 Mac 用得多一点，都会遇到。
在我还是一个穷酸学生的2009年，每个月都需要支付 20 元巨款（当时能买3根鸭脖），通过一个禁止分享网络的认证客户端接入校园网。
为了共建和谐宿舍
然后山水 BBS 的 Linux 版主把我的帖子置顶了 11 年。
这么一回忆，感觉自己的共享经济思维真是前卫，当时怎么就没想到去搞共享单车呢？
扯远了，在捣腾的过程中，我就踩了这么个坑：当我ssh到路由器上、刚启动认证时，能够正常联网；但是退出ssh后一会，网就断了。
经过一番捣腾后发现，只要一退出ssh，认证程序就凉了，而不是继续在后台保持和认证服务器的通信。
# - 3 -
所以前面那个问题，我以为大部分候选人应该会回答“否”，但没想到竟然还有不少人回答“是”。
其实回答“是”也没什么错，因为确实也有些命令不会随着终端关闭而结束。
问题是当我追问当时执行的是什么命令时，候选人往往又说不出个所以然来。
（借学长的表情一用）
然后我就感到很强的挫败感：这不按剧本来，没法问了啊……只好换题。
当然大部分候选人确实被坑过，于是我可以接着问：
如果确实需要在后台继续执行命令怎么办呢？
有些人只记得要在后面加个 & ；但也有不少人知道前面还得加个 nohup，就像这样：
$ nohup python process.py &
[1] 1806824
nohup: ignoring input and appending output to 'nohup.out'
[1] 1806824
nohup: ignoring input and appending output to 'nohup.out'
注：其实我更喜欢 screen（或 tmux），偶尔也用 setsid 。
然后就可以放心地关闭终端
但我的套题还没结束：为什么加上 nohup 就可以让进程在后台继续运行呢？
（这表情熟悉吗）
# - 4 -
铺垫了这么多，总算是可以开始填坑了。
答案其实很好找，man nohup 就能看到：
引用
The nohup utility invokes utility with its arguments and at this time sets the signal SIGHUP to be ignored
nohup工具在启动命令的同时会将 SIGHUP 信号设置为忽略。
而关于 SIGHUP，Wikipedia原文是这样介绍的：
引用
On POSIX-compliant platforms, SIGHUP ("signal hang up") is a signal sent to a process when its controlling terminal is closed.
wikipedia.org/wiki/SIGHUP
wikipedia.org/wiki/SIGHUP
对于 POSIX 兼容的平台（如Unix、Linux、BSD、Mac），当进程所在的控制终端关闭时，系统会给进程发送 SIGHUP 信号（Signal Hang Up，挂断信号）。
为什么叫 SIGHUP 呢？（严正申明：这一问不在套题里[doge])
我们知道，在上古时代，捉 bug 就已经是码农的必备技能（更准确地说是 moth）。
（我总觉得这个图是假的）
到了远古时代，他们不再需要去机房，通过基于 RS-232 协议的串行线路连接到大型机的终端上，就可以开始收福报。
收完福报，程序员通知自己的猫（modem）挂断（Hang Up）连接；大型机的 OS 检测到连接断开，就会给进程发送信号 —— 所以这信号被称为 SIGHUP 。
这果然是毫无卵用的知识啊。
# - 5 -
很多同学在操作系统的课程上学习了“进程间的通信方式有信号、管道、消息队列、共享内存……”，但是对信号到底是个什么东西，并没有现实的概念。
课堂教学的理论和实践往往是割裂的，在此特别推荐《Unix环境高级编程》（简称APUE）。
APUE在 1.9 - 信号 中写到：信号是通知进程已发生某种条件的一种技术。
而在 Linux/Unix 下，进程对信号的处理有三种选择：
* 按系统默认方式处理
* 提供一个回调函数
* 或忽略该信号（有些信号例外，不允许被忽略）
以 SIGHUP 信号为例，系统默认处理方式就是结束进程。
当然终端下打开的第一个进程通常都是shell（例如bash）。shell会给 SIGHUP 信号注册一个回调函数，用于给该 shell 下所有的子进程发送 SIGHUP 信号，然后再主动退出。
对于求生欲很强的程序（例如nohup），可以主动选择忽略该信号。
有一些进程本来就被设计成在后台运行，不需要控制终端，因此它们将 SIGHUP 挪作它用，一个常见的用法就是重新读取配置文件（例如Apache、Nginx），上篇提到的 logrotate 正是利用了这一点。
终于填完了坑。
# - 6 -
说了这么多都还是纸上谈兵，实操中如何主动忽略 SIGHUP 呢？
实际上也很简单，使用 Linux 的 signal 系统调用即可：
#include <signal.h>
#include <unistd.h>
int main() {
signal(SIGHUP, SIG_IGN);
sleep(1000);
return 0;
}
#include <unistd.h>
int main() {
signal(SIGHUP, SIG_IGN);
sleep(1000);
return 0;
}
不妨试试看，编译运行起来，即使关闭终端，它也会在后台继续运行。
signal 也可以用于指定回调函数（或重置为系统默认处理方式），这里就不展开了，感兴趣的同学可以参考 APUE 里的代码，以及阅读 signal 的manual。
使用回调函数还需要注意一个坑：
由于回调函数可能在任意时刻被触发，因此要避免调用不可重入的函数（典型如printf）。常见的做法是 set 一个 flag，然后在程序的主循环中检测该 flag，再按需执行相应任务。
# - 7 -
SIGHUP 只是常见的一个信号，在 Linux 下，信号还有大量其他的场景和应用。
当你按下 Ctrl + C ，就是给进程发送了一个 SIGINT 信号。
当你执行 kill -TERM $PID，就是给进程发送了一个 SIGTERM 信号。可能和你期望有出入的是，SIGTERM 是可以被进程忽略的。所以有时候你得用 SIGKILL (kill -9) 。
你还可以使用可自定义的 SIGUSR1、SIGUSR2、SIGURG 来实现一些功能，比如《踩坑记#2：Go服务锁死》中提到 Golang 在其 goroutine 调度中使用了 SIGURG 。
# - 8 -
这次就不总结了，最后再用一个和信号有关的 case 收尾。
Linux 内核会为每一个进程分配一个 task_struct 结构体，用于保存进程的相关信息。
在进程死亡后，系统会发送一个 SIGCHLD 信号给它的父进程。
正确的父进程实现，通常应当使用 wait 系统调用来给子进程收尸 —— 父进程往往需要知道子进程结束这个事件，而且可能还需要得知其退出原因（exit code）。
然后内核才会将对应的 task_struct 释放。
如果父进程没有收尸，task_struct 里的 state 会一直保持为 EXIT_ZOMBIE，这时在 ps 或 top 等命令里，就可以看到该进程的状态为 Z ，而且无法被 kill 。
这就是所谓的僵尸进程，这时候你找九叔都没用。
（大半夜找这图还挺渗人的）
所以Linux里养僵尸，其实就是子进程死了父进程不收尸，大家可能会很惊讶Linux里怎么会养僵尸呢？但事实就是这样，小编也感到非常惊讶。
这就是关于Linux里养僵尸的事情了，大家有什么想法呢，欢迎在评论区告诉小编一起讨论哦！
---
推荐阅读
* 程序员面试指北：面试官视角
* 踩坑记：go服务内存暴涨
* TCP：学得越多越不懂
* UTF-8：一些好像没什么用的冷知识
* [译] Ｃ程序员该知道的内存知识 (1)
Jul
6
想了十天十夜不知道写些什么，那就写写面试题吧。
1
在面试应聘者的时候，我常常会问：
在 Linux 下，如何删除一个目录下的所有 log 文件？
不知道是不是我人畜无害的围笑给了应聘者我很好应付的错觉
以至于应聘者全都回答：`rm *.log`
追问：该目录下可能有很多子目录，如何把子目录里的 log 文件也删掉呢？
Jun
25
接着 上一篇-内存暴涨坑 再挖个坟，讲讲去年踩的另一个坑。
---
前方低能
那是去年7月的一天，被透过落地玻璃的宇宙中心五道口的夕阳照着的正在工位搬砖的我，突然听到一阵骚乱，转头一看，收到夺命连环call的D同学反馈，流量严重异常。
点开报警群，一串异常赫然在目：
---
前方低能
那是去年7月的一天，被透过落地玻璃的宇宙中心五道口的夕阳照着的正在工位搬砖的我，突然听到一阵骚乱，转头一看，收到夺命连环call的D同学反馈，流量严重异常。
点开报警群，一串异常赫然在目：
Jun
21
之前从网上找的一段代码，按行读取文件:
看起来没问题，用起来也没问题，直到踩了个坑：针对某个特定的文件，读取到某一行以后就不再继续了。
既然总能复现，那就好解决，我的一个常用方法是：制造一个总能复现的case，并不断缩小case的规模。
例如这个case，把那一行单独拿出来，通过二分找到出问题的位置。
原以为是该行有特殊字符导致触发了什么奇怪的逻辑，但经过不断尝试，发现临界点是该行长度 = 65536 的时候，正好会触发错误。
这么整的数字（2^16, 64KB）必然是代码里的特殊逻辑了，翻了一下 bufio 的源码，果然有一个
搜索这个常量在代码里的引用：
在 for 循环后加上一句：
实锤：
那怎么解决呢？
MaxScanTokenSize 上面的注释是这么写的：
于是最终版的解决方案是这样：
真是丑陋的api啊。
inFile, err := os.Open("xxx.log")
if err != nil {
fmt.Fprintf(os.Stderr, "open failed: %v\n", err)
return
}
defer inFile.Close()
scanner := bufio.NewScanner(inFile)
for scanner.Scan() {
line := scanner.Bytes()
//do sth. with line
}
if err != nil {
fmt.Fprintf(os.Stderr, "open failed: %v\n", err)
return
}
defer inFile.Close()
scanner := bufio.NewScanner(inFile)
for scanner.Scan() {
line := scanner.Bytes()
//do sth. with line
}
看起来没问题，用起来也没问题，直到踩了个坑：针对某个特定的文件，读取到某一行以后就不再继续了。
既然总能复现，那就好解决，我的一个常用方法是：制造一个总能复现的case，并不断缩小case的规模。
例如这个case，把那一行单独拿出来，通过二分找到出问题的位置。
原以为是该行有特殊字符导致触发了什么奇怪的逻辑，但经过不断尝试，发现临界点是该行长度 = 65536 的时候，正好会触发错误。
这么整的数字（2^16, 64KB）必然是代码里的特殊逻辑了，翻了一下 bufio 的源码，果然有一个
const (
//...(一堆注释)...
MaxScanTokenSize = 64 * 1024
)
//...(一堆注释)...
MaxScanTokenSize = 64 * 1024
)
搜索这个常量在代码里的引用：
func NewScanner(r io.Reader) *Scanner {
return &Scanner{
r: r,
split: ScanLines,
maxTokenSize: MaxScanTokenSize,
}
}
...
func (s *Scanner) Scan() bool {
....
if len(s.buf) >= s.maxTokenSize || len(s.buf) > maxInt/2 {
s.setErr(ErrTooLong)
return false
}
...
}
return &Scanner{
r: r,
split: ScanLines,
maxTokenSize: MaxScanTokenSize,
}
}
...
func (s *Scanner) Scan() bool {
....
if len(s.buf) >= s.maxTokenSize || len(s.buf) > maxInt/2 {
s.setErr(ErrTooLong)
return false
}
...
}
在 for 循环后加上一句：
if scanner.Err() != nil {
fmt.Fprintf(os.Stderr, "scan err: %v\n", scanner.Err())
}
fmt.Fprintf(os.Stderr, "scan err: %v\n", scanner.Err())
}
实锤：
引用
scan err: bufio.Scanner: token too long
那怎么解决呢？
MaxScanTokenSize 上面的注释是这么写的：
引用
// MaxScanTokenSize is the maximum size used to buffer a token
// unless the user provides an explicit buffer with Scanner.Buffer.
// The actual maximum token size may be smaller as the buffer
// may need to include, for instance, a newline.
// unless the user provides an explicit buffer with Scanner.Buffer.
// The actual maximum token size may be smaller as the buffer
// may need to include, for instance, a newline.
于是最终版的解决方案是这样：
...
scanner := bufio.NewScanner(inFile)
buf := make([]byte, 0, bufio.MaxScanTokenSize * 10) //根据自己的需要调整这个倍数
scanner.Buffer(buf, cap(buf))
for scanner.Scan() {
line := scanner.Bytes()
//do sth. with line
}
if scanner.Err() != nil {
fmt.Fprintf(os.Stderr, "scan err: %v\n", scanner.Err())
}
scanner := bufio.NewScanner(inFile)
buf := make([]byte, 0, bufio.MaxScanTokenSize * 10) //根据自己的需要调整这个倍数
scanner.Buffer(buf, cap(buf))
for scanner.Scan() {
line := scanner.Bytes()
//do sth. with line
}
if scanner.Err() != nil {
fmt.Fprintf(os.Stderr, "scan err: %v\n", scanner.Err())
}
真是丑陋的api啊。
May
24
系列更新：
* [译] Ｃ程序员该知道的内存知识 (1)
* [译] Ｃ程序员该知道的内存知识 (2)
* [译] Ｃ程序员该知道的内存知识 (3)
这是本系列的第4篇，也是最后一篇，含泪填完这个坑不容易，感谢阅读~
这个系列太干了，阅读量一篇比一篇少，但我仍然认为这个系列非常有价值，在翻译的过程中我也借机进行系统性的梳理、并学习了很多新知识，收获满满。希望你也能有收获（但肯定没我多）。
那，开始吧。
# 理解内存消耗
工具箱：
* vmtouch [2] - portable virtual memory toucher
（译注：vmtouch这个工具用来诊断和控制系统对文件系统的缓存，例如查看某个文件被缓存了多少页，清空某个文件的缓存页，或将某个文件的页面锁定在内存中；基于这些功能可以实现很多有意思的应用；详情参考该工具的文档。）
然而共享内存的概念导致传统方案 —— 测量对内存的占用 —— 变得无效了，因为没有一个公正的方法可以测量你进程的独占空间。这会引起困惑甚至恐惧，可能是两方面的：
用上了基于 mmap 的I/O操作后，我们的应用现在几乎不占用内存.
— CorporateGuy
求救！我这写入共享内存的进程有严重的内存泄漏！！！
— HeavyLifter666
页面有两种状态：清洁(clean)页和脏(dirty)页。区别是，脏页在被回收之前需要被写回到持久存储中（译注：写回文件实际存放的地方）。MADV_FREE 这个建议通过将脏标志位清零这种方式来实现更轻量的内存释放，而不是修改整个页表项（译注：page table entry，常缩写为PTE，记录页面的物理页号及若干标志位，如能否读写、是否脏页、是否在内存中等）。此外，每一页都可能是私有的或共享的，这正是导致困惑的源头。
前面引用的两个都是（部分）真实的，取决于视角。在系统缓冲区的页面需要计入进程的内存消耗里吗？如果进程修改了缓冲区里那些映射文件的那些页面呢？在这混乱中可以整出点有用的东西么？
假设有一个进程，索伦之眼（the_eye）会写入对 魔都（mordor） 的共享映射（译注：指环王的梗）。写入共享内存不计入 RSS（resident set size，常驻内存集）的，对吧？
（译注：$$ 是 bash 变量，保存了在执行当前script的shell的PID；这里应该是用来指代the_eye的PID）
呃，让我们回到小黑板。
## PSS（Proportional Set Size）
PSS（译注：Proportional 意思是 “比例的”） 计入了私有映射，以及按比例计入共享映射。这是我们能得到的最合理的内存计算方式了。关于“比例”，是指将共享内存除以共享它的进程数量。举个例子，有个应用需要读写某个共享内存映射：
（译注：cat /proc/$PID/maps 是从内核中读取进程的所有内存映射）
这是个被简化并截断了的映射，第一列是地址范围，第二列是权限信息，其中 r 表示可读， w 表示可写，x 表示可执行 —— 这都是老知识点了 —— 然后 s 表示共享，p 表示私有。然后是映射文件的偏移量，设备号（OS分配的），inode号（文件系统上的），以及最后是文件的路径名。具体参见这个文档[3]（译注：kernel.org 对 /proc 文件系统的说明文档），超级详细。
我得承认我删掉了一些输出中一些不太有意思的信息。如果你对被私有映射的库感兴趣的话可以读一下 FAQ-为什么“strict overcommit”是个蠢主意[4]（译注：根据这个FAQ，strict overcommit应该是指允许overcommmit、但要为申请的每一个虚拟页分配一个真实页，不管是用物理页还是swap，确实听起来很蠢……）。不过这里我们感兴趣的是魔都（mordor）这个映射：
译注：这个文件大小 32GB，已加载了 1521MB 到内存中，因为只有这一个进程映射了它，所以在这个进程的PSS中占比是100%，也是 1521MB。
在共享映射里的私有页面 —— 搞得我像巫师一样？在Linux上，即使共享内存也会被认为是私有的，除非它真的被共享了（译注：不止一个进程创建共享映射）。让我们看看它是否在系统缓冲区里：
译注：
1. “-m 64G” 表示允许 vmtouch 将小于 64G 的文件加载到内存中，应当是用于需要加载一个目录下的文件、但排除其中过大的文件，似乎不适用于这里；至少忽略这个参数不影响阅读
2. o 表示这一块部分被加载，O 表示全部被加载。因为物理内存有限，虽然全量读取了文件，但只有部分内容被缓存
嗬，只是简单地读取一个文件就会把它缓存起来？先不管这，我们的进程呢？
常见的误解是，映射文件会消耗内存，而通过文件API读取不会。实际上，无论哪一种方式，包含文件内容的页面都会被放进系统缓冲区。但还有个小的区别是，使用mmap的方式需要在进程的页表中创建对应的页表项（PTE），而这些包含文件内容的页面是可以被共享的。有趣的是，我们这个进程的RSS缩小了，因为系统 _需要_ 进程的页面了（译注：因为 mordor 太大，可用物理内存页不够，系统将 the_eye 的部分页面swap了；所以前述命令才会需要等一分钟，因为涉及到磁盘IO）。
## 有时我们的所有想法都是错的
映射文件的内存总是可被回收的，区别只在于该页是否脏页 —— 脏页在回收前需要被清理（译注：写回底层存储）。所以当你在 top 命令发现有一个进程占用了大量内存时是否需要恐慌？当这个进程有很多匿名的脏页的时候才需要恐慌——因为这些页面无法被回收。如果你发现有个匿名映射段在增长，你可能就有麻烦了（而且是双倍的麻烦）。但是不要盲目相信 RSS 甚至 PSS 。
另一个常见错误是认为进程的虚拟内存和实际消耗内存之间总有某种关系，甚至认为所有内存映射都一样。任何可回收的内存，实际上都可以认为是空闲的。简而言之，它不会导致你下次内存分配失败，但_可能_会增加分配的延迟 —— 这点我会解释：
内存管理器需要花很大功夫来决定哪些东西需要保存在物理内存里。它可能会决定将进程内存中的一部分调到swap，以便给系统缓存腾出空间，因此该进程下次访问这一块时需要再将这些页面调回到物理内存中。幸运的是这通常是可以配置的。例如，Linux 有一个叫做 swappiness[5] 的选项，用来指导内核何时开始将匿名映射的内存页调出到swap。当它取值为 0 是表示“直到绝对绝对有必要的时候”（译注：取值[0, 100]，值越低，系统越倾向于先清理系统缓冲区的页面）。
# 终章，一劳永逸地
如果你看到这里，向你致敬！我在工作之余写的这篇文章，希望能用一种更方便的方式，不仅能解释这些说过上千遍的概念，还能帮我整理这些思维，以及帮助其他人。我花了比预期更长的时间。远超预期。
我对文章的作者们只有无尽的敬意，因为写作真是个冗长乏味、令人头秃的过程，需要永无止境的修改和重写。Jeff Atwood（译注：stack overflow的创始人）曾说过，最好的学编程书籍是教你盖房子的那本。我不记得在哪儿了，所以无法引用它。我只能说，第二好的是教你写作的那本。说到底，编程本质上就是写故事，简明扼要。
EDIT：我修正了关于 alloca() 和 将 sizeof(char) 误写为 sizeof(char*) 的错误，多亏了 immibis 和 BonzaiThePenguin。感谢 sWvich 指出在 slab + sizeof(struct slab) 里漏了的类型转换。显然我应该用静态分析跑一下这篇文章，但并没有 —— 涨经验了。
开放问题 —— 有没有比 Markdown 代码块更好的实现？我希望能展示带注释的摘录，并且能下载整个代码块。
写于 2015 年 2 月 20 日。
读到这里都是真爱，喜欢的话请留言支持，让更多人看到，感谢~
照例再贴下之前推送的几篇文章：
* 《踩坑记：go服务内存暴涨》
* 《TCP：学得越多越不懂》
* 《UTF-8：一些好像没什么用的冷知识》
* 《关于RSA的一些趣事》
* 《程序员面试指北：面试官视角》
参考链接：
[1] What a C programmer should know about memory
https://marek.vavrusa.com/memory/
[2] vmtouch - the Virtual Memory Toucher
https://hoytech.com/vmtouch/
[3] kernel.org - THE /proc FILESYSTEM
https://www.kernel.org/doc/Documentation/filesystems/proc.txt
[4] FAQ (Why is “strict overcommit” a dumb idea?)
http://landley.net/writing/memory-faq.txt
[5] wikipedia - Paging - swapinness
https://en.wikipedia.org/wiki/Swappiness
* [译] Ｃ程序员该知道的内存知识 (1)
* [译] Ｃ程序员该知道的内存知识 (2)
* [译] Ｃ程序员该知道的内存知识 (3)
这是本系列的第4篇，也是最后一篇，含泪填完这个坑不容易，感谢阅读~
这个系列太干了，阅读量一篇比一篇少，但我仍然认为这个系列非常有价值，在翻译的过程中我也借机进行系统性的梳理、并学习了很多新知识，收获满满。希望你也能有收获（但肯定没我多）。
那，开始吧。
# 理解内存消耗
工具箱：
* vmtouch [2] - portable virtual memory toucher
（译注：vmtouch这个工具用来诊断和控制系统对文件系统的缓存，例如查看某个文件被缓存了多少页，清空某个文件的缓存页，或将某个文件的页面锁定在内存中；基于这些功能可以实现很多有意思的应用；详情参考该工具的文档。）
然而共享内存的概念导致传统方案 —— 测量对内存的占用 —— 变得无效了，因为没有一个公正的方法可以测量你进程的独占空间。这会引起困惑甚至恐惧，可能是两方面的：
引用
用上了基于 mmap 的I/O操作后，我们的应用现在几乎不占用内存.
— CorporateGuy
求救！我这写入共享内存的进程有严重的内存泄漏！！！
— HeavyLifter666
页面有两种状态：清洁(clean)页和脏(dirty)页。区别是，脏页在被回收之前需要被写回到持久存储中（译注：写回文件实际存放的地方）。MADV_FREE 这个建议通过将脏标志位清零这种方式来实现更轻量的内存释放，而不是修改整个页表项（译注：page table entry，常缩写为PTE，记录页面的物理页号及若干标志位，如能否读写、是否脏页、是否在内存中等）。此外，每一页都可能是私有的或共享的，这正是导致困惑的源头。
前面引用的两个都是（部分）真实的，取决于视角。在系统缓冲区的页面需要计入进程的内存消耗里吗？如果进程修改了缓冲区里那些映射文件的那些页面呢？在这混乱中可以整出点有用的东西么？
假设有一个进程，索伦之眼（the_eye）会写入对 魔都（mordor） 的共享映射（译注：指环王的梗）。写入共享内存不计入 RSS（resident set size，常驻内存集）的，对吧？
$ ps -p $$ -o pid,rss
PID RSS
17906 1574944 # <-- 什么鬼? 占用1.5GB？
PID RSS
17906 1574944 # <-- 什么鬼? 占用1.5GB？
（译注：$$ 是 bash 变量，保存了在执行当前script的shell的PID；这里应该是用来指代the_eye的PID）
呃，让我们回到小黑板。
## PSS（Proportional Set Size）
PSS（译注：Proportional 意思是 “比例的”） 计入了私有映射，以及按比例计入共享映射。这是我们能得到的最合理的内存计算方式了。关于“比例”，是指将共享内存除以共享它的进程数量。举个例子，有个应用需要读写某个共享内存映射：
$ cat /proc/$$/maps
00400000-00410000 r-xp 0000 08:03 1442958 /tmp/the_eye
00bda000-01a3a000 rw-p 0000 00:00 0 [heap]
7efd09d68000-7f0509d68000 rw-s 0000 08:03 4065561 /tmp/mordor.map
7f0509f69000-7f050a108000 r-xp 0000 08:03 2490410 libc-2.19.so
7fffdc9df000-7fffdca00000 rw-p 0000 00:00 0 [stack]
... 以下截断 ...
00400000-00410000 r-xp 0000 08:03 1442958 /tmp/the_eye
00bda000-01a3a000 rw-p 0000 00:00 0 [heap]
7efd09d68000-7f0509d68000 rw-s 0000 08:03 4065561 /tmp/mordor.map
7f0509f69000-7f050a108000 r-xp 0000 08:03 2490410 libc-2.19.so
7fffdc9df000-7fffdca00000 rw-p 0000 00:00 0 [stack]
... 以下截断 ...
（译注：cat /proc/$PID/maps 是从内核中读取进程的所有内存映射）
这是个被简化并截断了的映射，第一列是地址范围，第二列是权限信息，其中 r 表示可读， w 表示可写，x 表示可执行 —— 这都是老知识点了 —— 然后 s 表示共享，p 表示私有。然后是映射文件的偏移量，设备号（OS分配的），inode号（文件系统上的），以及最后是文件的路径名。具体参见这个文档[3]（译注：kernel.org 对 /proc 文件系统的说明文档），超级详细。
我得承认我删掉了一些输出中一些不太有意思的信息。如果你对被私有映射的库感兴趣的话可以读一下 FAQ-为什么“strict overcommit”是个蠢主意[4]（译注：根据这个FAQ，strict overcommit应该是指允许overcommmit、但要为申请的每一个虚拟页分配一个真实页，不管是用物理页还是swap，确实听起来很蠢……）。不过这里我们感兴趣的是魔都（mordor）这个映射：
$ grep -A12 mordor.map /proc/$$/smaps
Size: 33554432 kB
Rss: 1557632 kB
Pss: 1557632 kB
Shared_Clean: 0 kB
Shared_Dirty: 0 kB
Private_Clean: 1557632 kB
Private_Dirty: 0 kB
Referenced: 1557632 kB
Anonymous: 0 kB
AnonHugePages: 0 kB
Swap: 0 kB
KernelPageSize: 4 kB
MMUPageSize: 4 kB
Locked: 0 kB
VmFlags: rd wr sh mr mw me ms sd
Size: 33554432 kB
Rss: 1557632 kB
Pss: 1557632 kB
Shared_Clean: 0 kB
Shared_Dirty: 0 kB
Private_Clean: 1557632 kB
Private_Dirty: 0 kB
Referenced: 1557632 kB
Anonymous: 0 kB
AnonHugePages: 0 kB
Swap: 0 kB
KernelPageSize: 4 kB
MMUPageSize: 4 kB
Locked: 0 kB
VmFlags: rd wr sh mr mw me ms sd
译注：这个文件大小 32GB，已加载了 1521MB 到内存中，因为只有这一个进程映射了它，所以在这个进程的PSS中占比是100%，也是 1521MB。
在共享映射里的私有页面 —— 搞得我像巫师一样？在Linux上，即使共享内存也会被认为是私有的，除非它真的被共享了（译注：不止一个进程创建共享映射）。让我们看看它是否在系统缓冲区里：
# 好像开头的那一块在内存中...
$ vmtouch -m 64G -v mordor.map
[OOo ] 389440/8388608
Files: 1
Directories: 0
Resident Pages: 389440/8388608 1G/32G 4.64%
Elapsed: 0.27624 seconds
# 将它全都载入到Cache!
$ cat mordor.map > /dev/null
$ vmtouch -m 64G -v mordor.map
[ooooooooo oooOOOOO] 2919606/8388608
Files: 1
Directories: 0
Resident Pages: 2919606/8388608 11G/32G 34.8%
Elapsed: 0.59845 seconds
$ vmtouch -m 64G -v mordor.map
[OOo ] 389440/8388608
Files: 1
Directories: 0
Resident Pages: 389440/8388608 1G/32G 4.64%
Elapsed: 0.27624 seconds
# 将它全都载入到Cache!
$ cat mordor.map > /dev/null
$ vmtouch -m 64G -v mordor.map
[ooooooooo oooOOOOO] 2919606/8388608
Files: 1
Directories: 0
Resident Pages: 2919606/8388608 11G/32G 34.8%
Elapsed: 0.59845 seconds
译注：
1. “-m 64G” 表示允许 vmtouch 将小于 64G 的文件加载到内存中，应当是用于需要加载一个目录下的文件、但排除其中过大的文件，似乎不适用于这里；至少忽略这个参数不影响阅读
2. o 表示这一块部分被加载，O 表示全部被加载。因为物理内存有限，虽然全量读取了文件，但只有部分内容被缓存
嗬，只是简单地读取一个文件就会把它缓存起来？先不管这，我们的进程呢？
$ ps -p $$ -o pid,rss
PID RSS
17906 286584 # <-- 等了足足一分钟
PID RSS
17906 286584 # <-- 等了足足一分钟
常见的误解是，映射文件会消耗内存，而通过文件API读取不会。实际上，无论哪一种方式，包含文件内容的页面都会被放进系统缓冲区。但还有个小的区别是，使用mmap的方式需要在进程的页表中创建对应的页表项（PTE），而这些包含文件内容的页面是可以被共享的。有趣的是，我们这个进程的RSS缩小了，因为系统 _需要_ 进程的页面了（译注：因为 mordor 太大，可用物理内存页不够，系统将 the_eye 的部分页面swap了；所以前述命令才会需要等一分钟，因为涉及到磁盘IO）。
## 有时我们的所有想法都是错的
映射文件的内存总是可被回收的，区别只在于该页是否脏页 —— 脏页在回收前需要被清理（译注：写回底层存储）。所以当你在 top 命令发现有一个进程占用了大量内存时是否需要恐慌？当这个进程有很多匿名的脏页的时候才需要恐慌——因为这些页面无法被回收。如果你发现有个匿名映射段在增长，你可能就有麻烦了（而且是双倍的麻烦）。但是不要盲目相信 RSS 甚至 PSS 。
另一个常见错误是认为进程的虚拟内存和实际消耗内存之间总有某种关系，甚至认为所有内存映射都一样。任何可回收的内存，实际上都可以认为是空闲的。简而言之，它不会导致你下次内存分配失败，但_可能_会增加分配的延迟 —— 这点我会解释：
内存管理器需要花很大功夫来决定哪些东西需要保存在物理内存里。它可能会决定将进程内存中的一部分调到swap，以便给系统缓存腾出空间，因此该进程下次访问这一块时需要再将这些页面调回到物理内存中。幸运的是这通常是可以配置的。例如，Linux 有一个叫做 swappiness[5] 的选项，用来指导内核何时开始将匿名映射的内存页调出到swap。当它取值为 0 是表示“直到绝对绝对有必要的时候”（译注：取值[0, 100]，值越低，系统越倾向于先清理系统缓冲区的页面）。
# 终章，一劳永逸地
如果你看到这里，向你致敬！我在工作之余写的这篇文章，希望能用一种更方便的方式，不仅能解释这些说过上千遍的概念，还能帮我整理这些思维，以及帮助其他人。我花了比预期更长的时间。远超预期。
我对文章的作者们只有无尽的敬意，因为写作真是个冗长乏味、令人头秃的过程，需要永无止境的修改和重写。Jeff Atwood（译注：stack overflow的创始人）曾说过，最好的学编程书籍是教你盖房子的那本。我不记得在哪儿了，所以无法引用它。我只能说，第二好的是教你写作的那本。说到底，编程本质上就是写故事，简明扼要。
EDIT：我修正了关于 alloca() 和 将 sizeof(char) 误写为 sizeof(char*) 的错误，多亏了 immibis 和 BonzaiThePenguin。感谢 sWvich 指出在 slab + sizeof(struct slab) 里漏了的类型转换。显然我应该用静态分析跑一下这篇文章，但并没有 —— 涨经验了。
开放问题 —— 有没有比 Markdown 代码块更好的实现？我希望能展示带注释的摘录，并且能下载整个代码块。
写于 2015 年 2 月 20 日。
读到这里都是真爱，喜欢的话请留言支持，让更多人看到，感谢~
照例再贴下之前推送的几篇文章：
* 《踩坑记：go服务内存暴涨》
* 《TCP：学得越多越不懂》
* 《UTF-8：一些好像没什么用的冷知识》
* 《关于RSA的一些趣事》
* 《程序员面试指北：面试官视角》
参考链接：
[1] What a C programmer should know about memory
https://marek.vavrusa.com/memory/
[2] vmtouch - the Virtual Memory Toucher
https://hoytech.com/vmtouch/
[3] kernel.org - THE /proc FILESYSTEM
https://www.kernel.org/doc/Documentation/filesystems/proc.txt
[4] FAQ (Why is “strict overcommit” a dumb idea?)
http://landley.net/writing/memory-faq.txt
[5] wikipedia - Paging - swapinness
https://en.wikipedia.org/wiki/Swappiness
