并行编程难在哪

写程序是一个模拟现实世界的过程，而现实世界中的事物总是处于不断的变化之中，比如一天中温度有高有低，改革开放以后中国的 GDP 呈指数上涨，每个月养殖场兔子的数量是一个斐波那契数列云云。

有时也叫命令式编程，与此相对的概念是函数式编程。通常我们可以通过“对变量赋值”来刻画这种变化 *，例如：

temperature = 10;    // 10 摄氏度
temperature += 5;    // 升温
temperature -= 8;    // 降温

又比如迎面走来一个漂亮 MM：

distance = 10;     // 相距 10 m ... (1) 
heartbeat = 80;   // 每秒心跳 ......(2) 
distance = 5;      
heartbeat = 110; 

这种方法十分直观，也很符合大脑一根筋的思维模式。

然而现实世界里的很多东西并不是顺序发生的，比如在第二个例子中，距离和心跳可能同时发生变化。事实上因为很多处理器采用了乱序执行技术，所以语句 (1) 和 (2) 确实是同时执行的，不过这种指令级的并行大概在 05 年左右的时候就已经被业界开发得差不多了 * The Free Lunch Is Over by By Herb Sutter ，于是人们把目光转向了多核处理，如果有两段完全没关系的代码，就拿到两个不同的核上去算，也就是所谓的线程级并行。

但这时人们发现了一个新的问题。假设 A 和 B 有一个共享的银行账户，他们都想从账户中取走 50 元，但账户中只剩下了 70，当他们同时调用下面这个“取款”函数时会出问题。

withdraw(x) {
    if (balance >= x) {
        balance -= x; 
    }
}

因为 A、B 很有可能同时读到余额值 70，各自减去 50，然后再把 20 写回余额，原本银行只能让一个人能取款成功，结果两个人都拿到了钱。

为什么原来的串行程序是对的，但改成多线程以后就出了问题呢？可能有人会说是因为我们使用了共享变量，但是共享变量为什么让程序出错呢？问题的本质究竟是什么？

答案是时间。

过去我们从未考虑过时间这个因素，因为没有这个必要，在串行程序中，只要 temperature = 3 出现在 temperature = 4 前面，编译器和处理器就会让程序模拟出温度从 3 度变到 4 度的效果。但是在一段程序中，temperature 可能会等于 3 好几次，但是它们反映的却是不同的状态，因为它们是在不同时刻被赋值的。赫拉克利特说“没有人会重复踏入同一条河流”，也就是这个意思。

换到多线程环境时，虽然同一段代码的时序未变，但不同线程中代码的指令很可能会交错执行。比如取钱的例子之所以会出错就是因为两个线程以错误的顺序执行了代码：A 读余额，B 读余额，A 修改余额，B 修改余额。倘若 A 读取/修改余额发生在 B 前头或 B 读取/修改余额发生在 A 前头，程序也就对了。A 执行 ` balance -= x ` 的大前提是 balance >= x，一旦这个前提被 B 篡改，程序的逻辑自然就不成立。

原来我们只用考虑一条时间线，而现在需要维护有几条甚至几百条的时间线，这就是为什么进入并行时代以后程序设计的复杂度会陡然升高的原因。

时间旅行

这其实就有点像科幻小说中的时间旅行，一个人回到了过去杀死了自己的外婆，这个动作最终会导致“他不存在”的悖论，其实就是因为一个线程修改了共享变量，导致另一个线程在自己的时间线上违背了逻辑（也就是语义）。

if (granny_exists) mummy_exists = true;
if (mummy_exists) I_exist = true; 
if (I_exist) assure_equal(granny_exists, true);   // 报错

原本我们根据“外婆存在”，就可以推出“老妈存在”，继而推出“我存在”，但因为 granny_exists 是一个共享变量，当我们执行到第二句话的时候有个一个天外来客把 granny_exists 改成了 false，于是我们就在程序结束时得到了“我存在” 但“外婆不存在”这个著名的祖父悖论。

为了消除程序中的“悖论”，程序员需要在代码中添加一些互斥访问的机制，例如锁、信号量、原子操作……这些机制都是为了保证线程对共享变量的访问是串行的。

不幸的是无论在哪一种体系结构中，这些机制都特别耗时，因为系统每时每刻只能有一个线程能够通过这段区域，如果考虑到 cache 失效和流水线暂停，性能损失就更严重了，可扩展性也是块心病，而且稍不留神就会发生死锁、饥荒……

过去我们已经习惯于在用变量编程，我们用的计算机模型叫 RAM，它假设我们有一个无限大的内存可以存取，每个变量都是内存里的一个位置，我们把它读出来加加减减，然后写回去，就能轻松地描述出国民生产总值和兔子繁衍后代问题。等到了多核时代，自然就想到让多个处理器共享内存，再用一些机制保护共享变量的安全。也就是说使用变量是既成事实，共享变量则是事物发展到了某个阶段的必然产物。

通信

如果两个线程所处的时空互相平行，没有任何交点的，那么它们上台以后就可以自己干自己的，老死不相往来，但是在这个世界上很少有事情是孤立的，即使是 Jason Bourne 这样孤单特工也会受到组织和情感的牵绊，何况程序员写多线程程序的目的就是想让多个线程齐心协力完成某个任务，那就更加避免不了通信。

通信让那些有依赖关系的事件按正确的顺序发生，相当于把原来的很多条时间轴合成一条，使所有线程在一个“世界时钟”笼罩下按章办事。

时间是一种设施，发明它就是为了不让所有事情同时发生。—— 《计算机程序的构造与解释》

而共享变量的意义就在于它以最小的硬件代价在 RAM 模型中实现了一种通信的机制，不过这是一种落后的通信方式，共享变量和消息传递的区别大概就是天地会通过墙上暗号接头和今天我们用手机发短消息的区别。如果 A 和 B 在取款之前先打一通电话交流一下彼此的情况，也许就能杜绝“错误的可能”，即使余额对它们来说是一个局部变量。

很多算法只需要在做出某些决策时掌握全局信息量（通常也叫同步点），这时我们可以以消息传递的方式让每个线程获取足以做出正确判断的信息量，然后它们就可以继续闷头做自己的事情了，这也就是为什么通常认为 barrier 是一种更好并发控制技术。