技术奇异点

业界有两次事件刺激了关于多线程在桌面开发中的应用和相关讨论：Windows 95 将抢占式多线程（preemptive threading）引入主流桌面平台；AMD 和 Intel 把多核处理器引入桌面。前者让桌面的主流开发者开始关心锁（lock、mutex [1]）的使用。后者是硬件设计者无计可施的体现 —— 无法进一步提高时钟频率，也无法进一步提高硬件自动对代码的执行进行并行化处理的程度，关于这方面的评论 Herb Sutter 的《不再有免费的午餐》最为精彩，他用了『撞上物理定律铁壁』（reach hard physical limits）这样的描述。

写过《不再有免费的午餐》之后 Herb Sutter 又对锁的应用写了一系列文章（1，2，3）[2]。在他看来这是对《不再有免费的午餐》一文的自然延续。可能很多人也同意这点。但我认为这后三篇文章和《不再有免费的午餐》讨论的是两个不同问题，也就是说，锁和多核 —— 虽然它们有必然的协作需求 —— 但是主要是为了应对不同的问题而出现的。把它们分别要解决的两个问题在同一个主题下讨论是并行软件开发领域很多讨论混乱的根源。

计算的本质

什么是计算的本质，关于这个问题计算机科学家会告诉你关于图灵机、寻径问题、判定性问题等等概念。而我只想找一个让普通开发者看的舒服的说法。基本上，计算是把一种形式的数据变换成为另一种形式。

硬件制造者试图通过两种方式提高执行『算法』的效率 [3] ：提高 CPU 的时钟频率；试图让硬件自动找到算法中没有相互依赖的部分并且最大可能的并行执行它们。前者遇到了『物理定律铁壁』。后者主要通过乱序执行（out-of-order）和超标量流水线（super-scalar pipeline）实现，也已经接近优化的极限。

并行执行

所以，硬件制造者决定把第二种优化方式的控制权直接丢给软件开发者，而不再试图用硬件自动寻找可以并发的部分。这就是『免费午餐』的终结。

这种『并发执行』的关键是如何把数据分割成在算法处理中互不依赖的，而在处理之后又能重新汇合成完整数据的片段。这个过程中除了在最后的数据合并阶段需要少量的同步操作，关键在于数据分割的方法。锁在这个模式中并没有非常重要的作用。

其实把『并发执行』的控制权 —— 也就是数据分割的责任 —— 丢给软件开发者并非始于多核，从 MMX 时代开始流行的 SIMD 指令就是一个例子。

并发访问

锁的重要性，正如上文所述，其实和业界第二次刺激多线程开发的原因 —— 多核并没有绝对的联系。多核是硬件制造者将 out-of-order 和超标量的等效作用向上转移到软件设计的决定。其关键在于数据的无依赖分割。

而第一次刺激多线程开发的因由，Windows 95 将 preemptive threading 引入主流桌面开发，才是锁占据主导地位的事件。这次事件远在多 CPU 引入桌面系统之前。这时多线程的应用并非为了提高算法的执行效率，而是为了改善用户界面的响应速度。

如果从『数据 A』到『数据 B』的处理时间非常久，让用户能够稍感满意的做法是不时的显示处理的中间状态。这需要把算法分割成一系列步骤，把每个步骤产生的中间结果交给负责显示的代码处理。这种方式中，负责数据处理的代码和负责（中间）结果显示的代码处于不同线程。锁对于两个线程的协作起了至关重要的作用，因为整个算法只有某几个特定点才能产生对用户有意义的显示（保证数据 integrity）。这个方式和上文的『并行方式』有两个区别。

第一，这个方式的关键是算法分割而不是数据分割。『并行执行』注重数据分割，分割的要求是对算法处理不会产生相互依赖。『并发访问』注重算法分割，分割的要求是数据的呈现对用户有意义。

第二，『并发访问』并不关心访问的确定性。如果显示代码显示『数据格式 A1』的速度比较慢，它完全可以忽略『格式 A2』，只要最后能正确显示『数据 B』。如果有多个显示代码线程要同时显示中间结果和最终结果，它们显示了哪些中间结果，显示中间结果的前后顺序，是完全没有关系的，只要保证每个线程中前期步骤的结果不会在后续步骤的结果之后显示，并且最终都显示最终结果就行。

执行 vs. 访问

所以，多核的目的是『并行执行』，而锁的作用在于『并发访问』。有时实际问题需要混合两种方式的方案。例如，如果数据分割不能做到完全的消除依赖，那么各个算法线程之间就会进行少量的并发访问。但是，把两种方式完全混合的方式并不多，实际的系统总是非常偏向某个方式。

有一点点讽刺的是多核和锁似乎都没有真正成为解决原本期待用它们来解决的问题的利器。适合『并行执行』的任务往往符合两种情况：一是分割后的数据相互关联程度很低，完全没有必要通过共享地址空间来协作，这时其实通过简单的多进程处理就能提高 through-put 。常见的并行编译即属于此类。另一种情况是在处理每个数据片段的时候较少用到分支，这正是向量处理和 SIMD 的强项。所以『并行执行』的任务实际更多的被 Cuda 或者 OpenCL 之类的通用 GPU 计算担当。对多核的利用应该从对锁的注意，迁移到对数据分割的理论研究。

需要『并发访问』的问题，其实在单线程和协作式多任务处理中就通过消息循环定期发送 timer 消息得到了解决。被分割后的算法放到一系列 timer handler 中和负责显示中间结果的代码在同一个线程里交替运行。使用 timer handler 过多的一个并不严重的缺点是代码的静态表现不能直观的体现其静态流程，出现问题的时候 call-stack 也不够明晰，对调试和查找 bug 增加了一定的困难。把『并发访问』的问题由 timer 模式迁移到多线程加锁的模式，虽然提高了算法线程的代码流畅程度，也由于同步操作的设置极大的增加了整体复杂度。所以大量的开发实际还是停留在协作式的方式，比如 Cocoa 开发中的动画和拖放就提倡使用 timer 来完成。在 ActionScript 这类没有线程模型的运行环境 timer 也是唯一的途径。

多核和锁都和多线程都紧密的联系，但是这种联系更多的是表面层次的。本质上它们倾向于解决各自的问题。而在分析这些多核和锁『各自的问题』时一旦很好的消除了另一种方式的干扰因素，问题本身又可以通过其它方式得到解决。

注释：

1. 线程同步操作有很多种。Mutex 只是多线程同步化操作的一种（一般在 UNIX 中 mutex 指那些利用内核等待队列让暂时不能取得执行临界区（critical region）的线程放弃 CPU 的操作）。此外还有 bus lock，spin lock，memory barrier 等等操作。本文在不必涉及具体区别的地方统一称为锁。
2. Sutter 的后两篇名为 lock-free 。但是正如注释 [1] 所说，这里还是需要用到 bus lock 或者 memory barrier 一类的同步操作。
3. 第三种方式是通过高速片内缓存（on-die cache）。这是利用的算法执行对数据和代码局部化（locality）特性。因为和算法本身的逻辑执行效率没有关系，所以不做讨论。

This entry was posted on 2010/10/04 at 10:33 上午 and is filed under 软件开发. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.