vlambda博客
学习文章列表

在校学生的编程语言和数据结构的基础还不错，我认为应该在《操作系统》和《计算机体系结构》这两门课上下功夫，然后才去读编程方面的 APUE、UNP 等书。

下面简单谈谈我对学习这两门课的看法和建议，都是站在服务端程序员的角度，从实用主义（pragmatic）的立场出发而言的。

学习操作系统的目的，不是让你去发明自己操作系统内核，打败 Linux；也不是成为内核开发人员；而是理解操作系统为用户态进程提供了怎样的运行环境，作为程序员应该如何才能充分利用好这个环境，哪些做法是有益的，哪些是做无用功，哪些则是帮倒忙。

学习计算机体系结构的目的，不是让你去设计自己的 CPU（新的 ISA 或微架构），打败 Intel 和 ARM；也不是参与到 CPU 设计团队，改进现有的微架构；而是明白现代的处理器的能力与特性（例如流水线、多发射、分支预测、乱序执行等等指令级并行手段，内存局部性与 cache，多处理器的内存模型、能见度、重排序等等），在编程的时候通过适当组织代码和数据来发挥 CPU 的效能，避免 pitfalls。Modern Microprocessors

这两门课程该如何学？看哪些书？这里我告诉你一个通用的办法，去美国计算机系排名靠前的大学的课程主页，找到这两门课最近几年的课程大纲、讲义、参考书目、阅读材料、随堂练习、课后作业、编程实验、期末项目等，然后你就心里有数了。

学习任何一门课程都要善于抓住主要矛盾、分清主次、突出重点，关键是掌握知识框架，学会以后真正有用的知识和技能，而不要把精力平均分配在一些琐事上。

请允许我再次引用孟岩的观点：http://blog.csdn.net/myan/article/details/5877305

我（孟岩）主张，在具备基础之后，学习任何新东西，都要抓住主线，突出重点。对于关键理论的学习，要集中精力，速战速决。而旁枝末节和非本质性的知识内容，完全可以留给实践去零敲碎打。

原因是这样的，任何一个高级的知识内容，其中都只有一小部分是有思想创新、有重大影响的，而其它很多东西都是琐碎的、非本质的。因此，集中学习时必须把握住真正重要那部分，把其它东西留给实践。对于重点知识，只有集中学习其理论，才能确保体系性、连贯性、正确性，而对于那些旁枝末节，只有边干边学能够让你了解它们的真实价值是大是小，才能让你留下更生动的印象。如果你把精力用错了地方，比如用集中大块的时间来学习那些本来只需要查查手册就可以明白的小技巧，而对于真正重要的、思想性东西放在平时零敲碎打，那么肯定是事倍功半，甚至适得其反。

因此我对于市面上绝大部分开发类图书都不满——它们基本上都是面向知识体系本身的，而不是面向读者的。总是把相关的所有知识细节都放在一堆，然后一堆一堆攒起来变成一本书。反映在内容上，就是毫无重点地平铺直叙，不分轻重地陈述细节，往往在第三章以前就用无聊的细节谋杀了读者的热情。

再比方说《计算机网络》，关键之一是理解如何在底层有丢包、重包、乱序的条件下设计出可靠的网络协议，这不算难。难一点的是这个可靠协议能达到“既能充分利用带宽，又能做到足够公平（并发连接大致平均分享带宽）”。而不是学会手算 CRC32，这更适合放到信息论或别的课程里去讲。

注意分清知识的层次。就好比造汽车与开汽车的区别，我认为一个司机的技能主要体现在各种道路条件和天气状况下都能安全驾驶（城市道路、高速公路、乡间公路 X 晴、雨、雪、雾），平安到达目的地。作为一名司机，了解汽车运行的基本原理当然是好事，可以有助于更好地驾驶和排除一些常见故障。但不宜喧宾夺主，只要你不真正从事汽车设计工作，你再怎么研究发动机、传动、转向，也不可能比汽车厂的工程师强，毕竟这是人家的全职工作。而且钻研汽车构造超过一定程度之后，对开好车就没多大影响了，成了个人兴趣爱好。“有的人学着学着成了语言专家，反而忘了自己原本是要解决问题来的。”（语出孟岩 快速掌握一个语言最常用的50%）

对于并发编程来说，掌握 mutex、condition variable 的正确用法，避免误用（例如防止 busy-waiting 和 data race）、避免性能 pitfalls，是一般服务端程序员应该掌握的知识。而如何实现高效的 mutex 则是 libc 和 kernel 开发者应该关心的事，随着硬件的发展（CPU 与内存之间互联方式的改变、核数的增加），最优做法也随之改变。

如果你不能持续跟进这一领域的发展，那么你深入钻研之后掌握的知识到了几年之后可能反而成为累赘，当年针对当时硬件的最优特殊做法（好比说定制了自己的 mutex 或 lock-free 数据结构）在几年后有可能反而会拖低性能。还不如按最清晰的方式写代码，利用好语言和库的现成同步设施，让编译器和 libc 的作者去操心“与时俱进”的事。

注意识别过时的知识。比方说《操作系统》讲磁盘IO调度往往会讲电梯算法，但是现在的磁盘普遍内置了这一功能（NCQ），无需操作系统操心了。如果你在一个比较好的学校，操作系统课程的老师应该能指出这些知识点，避免学生浪费精力；如果你全靠自学，我也没什么好办法，尽量用新版的书吧。类似的例子还有《计算机体系结构》中可能会讲 RISC CPU 流水线中的 delay slot，现在似乎也都废弃了。

《计算机网络》中类似的情况也不少，首先是 OSI 七层模型已经被证明是扯淡的，现在国外流行的教材基本都按五层模型来讲（Internet protocol suite），如果你的教材还郑重其事地讲 OSI （还描绘成未来的希望），扔了换一本吧。

其次，局域网层面，以太网一家独大（几乎成了局域网的代名词），FDDI/Token ring/ATM 基本没啥公司在用了。就说以太网，现在也用不到 CSMA/CD 机制（因为 10M 的同轴电缆、10M/100M 的 hub 都过时了，交换机也早就普及了），因此碰撞检测算法要求“以太网的最小帧长大于最大传播延迟的二倍”这种知识点了解一下就行了。

另外一点是 low level 优化的知识非常容易过时，编码时要避免过度拟合（overfitting）。比方说目前国内一些教科书（特别是大一第一门编程语言的教程）还在传授“乘除法比加减法慢、浮点数运算比整数运算慢、位运算最快”这种过时的知识。现代通用 CPU 上的实际情况是整数的加减法和乘法运算几乎一样快，整数除法慢很多；浮点数的加减法和乘法运算几乎和整数一样快，浮点数除法慢很多。

因此用加减法代替乘法（或用位运算代替算术运算）不见得能提速，反而让代码难懂。而且现代编译器可以把除数为小整数的整数除法转变为乘法来做，无需程序员操心。（目前用浮点数乘法代替浮点数除法似乎还是值得一做的，例如除以10改为乘以0.1，因为浮点运算的特殊性（不满足结合律和分配率），阻止了编译器优化。）

类似的 low level 优化过时的例子是早年用汇编语言写了某流行图像格式的编解码器，但随着 CPU 微架构的发展，其并不比现代 C 语言（可能用上 SIMD）的版本更快，反而因为使用了 32-bit 汇编语言，导致往 64-bit 移植时出现麻烦。如果不能派人持续维护更新这个私有库，还不如用第三方的库呢。现在能用汇编语言写出比 C 语言更快的代码几乎只有一种可能：使用 CPU 的面向特定算法的新指令，例如 Intel 的新 CPU （将会）内置了 AES、CRC32、SHA1、SHA256 等算法的指令。

不过主流的第三方库（例如 OpenSSL）肯定会用上这些手段，及时跟进即可，基本无需自己操刀。（再举一个例子，假如公司早先用汇编语言写了一个非常高效的大整数运算库，一直运转良好，原来写这个库的高人也升职或另谋高就了。

Intel 在 2013 年发布了新微架构 Haswell，新增了 MULX 指令，可以进一步提高大整数乘法的效率 GMP on Intel Haswell ，那么贵公司是否有人持续跟进这些 CPU 的进化，并及时更新这个大整数运算库呢？或者直接用开源的 GMP 库，让 GMP 的作者去操心这些事情？）

如果你要记住结论，一定要同时记住前提和适用条件。在错误的场合使用原本正确的结论的搞笑例子举不胜举。

1. 《Linux内核源码情景分析》上分析内核使用 GDT/LDT 表项的状况，得出进程数不超过 4090 的结论。如果你打算记住这个结论，一定要记住这是在 Linux 2.4.0 内核，32-bit Intel x86 平台上成立，新版的内核和其他硬件平台很可能不成立。看完书后千万不要张口就来“书上说 Linux 的最大进程数是 4090”。

   
   

2. 一个 Linux 进程最多创建 300 余个线程，这个结论成立的条件是 3GB 用户空间，线程栈为 10M 或 8M。在 64-bit 下不成立。

   
   

3. Reactor 模式只能支持不超过 64 个 handle，这个结论成立的条件是 Windows 下使用 WaitForMultipleObjects 函数实现的 WFMO_Reactor，对于 Linux 下使用 poll/epoll 实现的 Reactor 则无此限制。

   
   

4. C++ STL 的 vector 容器在 clear() 之后不会释放内存，需要 swap(empty vector)，这是有意为之（C++11 里增加了 shrink_to_fit() 函数）。不要记成了所有 STL 容器都需要 swap(empty one) 来释放内存，事实上其他容器（map/set/list/deque）都只需要 clear() 就能释放内存。只有含 reserve()/capacity() 成员函数的容器才需要用 swap 来释放空间，而 C++ 里只有 vector 和 string 这两个符合条件。
   

一、多机数据处理。有 10 台机器，每台机器上保存着 10 亿个 64-bit 整数（不一定刚好 10 亿个，可能有上下几千万的浮动），一共约 100 亿个整数（其实一共也就 80GB 数据，不算大，选这个量级是考虑了 VPS 虚拟机的容量，便于实验）。编程求出：

1. 这些数的平均数。

2. 这些数的中位数。

3. 出现次数最多的 100 万个数。

*4. （附加题）对这 100 亿个整数排序，结果顺序存放到这 10 台机器上。

*5. （附加健壮性要求）你的程序应该能正确应对输入数据的各种分布（均匀、正态、Zipf）。

*6. （附加伸缩性要求）你的程序应该能平滑扩展到更多的机器，支持更大的数据量。比如 20 台机器、一共 200 亿个整数，或者 50 台机器、一共 500 亿个整数。

二、N-皇后问题的多机并行求解。利用多台机器求出 N-皇后问题有多少个解。（注意目前的世界纪录是 N = 26，A000170 - OEIS ）

1. 8 皇后问题在单机上的运算时间是毫秒级，有 92 个解，编程实现之。

2. 研究 N-皇后问题的并行算法，写一个单机多线程程序，争取达到线性加速比（以 CPU 核数计）。再设法将算法扩展到多机并行。

3. 用 10 台 8 核的机器（一共 80 个 CPU cores），求解 19-皇后和 20-皇后问题，看看分别需要多少运行时间。你的方案能否平滑扩展到更多的机器？

*4. （附加题）如果这 10 台机器的型号不一，有 8 核也有 16 核，有旧 CPU 也有更快的新 CPU，你该采用何种负载均衡策略，以求缩短求解问题的时间（至少比 plain round-robin 算法要好）？

你可以用 Amazon EC2 或 Google GCE 来验证你的程序的正确性和性能，这两家的虚拟机都是按小时（甚至更短）收费，开 10 台虚拟机做一个下午的实验也花不了多少钱。

https://www.zhihu.com/question/22608820/answer/21968467

- EOF -

关注『CPP开发者』

看精选C++技术文章 . 加C++开发者专属圈子

点赞和在看就是最大的支持❤️