计算机基础知识讲义

习惯经验的强大惯性，源自于背景的长期稳定性。软件体系的快速变革，让我们忽视了硬件体系的长期稳定。这种稳定性使得很多习惯经验变成了不言自明的信条。 大多数的软件设计方法的革新只不过是用旧石斧打造出来新石斧。在C中我们使用getc,putc来进行IO,在Java中无非是变成了 System.in.read(),System.out.print ()。为什么IO必定是这种形式呢?这是因为我们长期使用着同一种计算机。我们知道PC/Mac这样的计算机中CPU与IO设备进行通信，需要通过各种总 线。下面这张图演示了CPU与IO设备之间通信的基本过程. 以 C语言为代表的传统的IO,实际上是单CPU上单任务工作模式的投影。在单台计算机上, 传统计算机体系结构决定了CPU处于控制者和决策者的地位。换而言之,我们历来习惯于以CPU的视角来考虑程序的IO逻辑.程序员是将自己假设为CPU. 程序员关心的IO设施只是一个黑盒.我们只需要往IO发送一个请求，然后等待请求回来进行运算,完全不关心这一来一回之间到底发生了什么过程. 但是当我们打开黑盒,观察CPU与IO的通信过程的时候, IO Monad就从幕后走向了台前。以总线的角度看,CPU和外设是等同的，都只是一个具有运算能力和输入输出端口的黑盒.总线正如 Bind/=函数一样不关心这些黑盒子里如何运算的，它只关心从这个黑盒拿数据出来放入那个黑盒. 从整个计算机的体系结构看，传统的IO观念只不过是IO Monad的一个局部化形态。 IO Monad实则上在一些接近操作系统底层的软件中，经常扮演者数据总线这种核心角色。比如说Unix/linux shell的管道命令就是彻头彻尾的IO Monad. cat,命令是return/Unit函数,|管道符就是bind/=函数。例如:cat sample.txt|grep High|wc l .cat 将sample.txt的文件内容包装成stdout,|管道符将stdout的内容传给grep 命令查询所有单词位High的行，查询的结果又被转化为stdout,再通过|管道符传送给wc命令进行行数统计。微软最新的Shell取名为 Monad,其言下之意恐怕无需赘述了. 不仅如此,IO Monad在结构化程序语言的最初演化的阶段也残留了一些踪迹.很多古老的Pascal程序，都保留了在程序首部书写Input Outpu参数的习惯. program fac_n(input,output); var n:integer; function fac(n:integer):integer; begin if n=1 then fac:=1 else fac:=n*fac(n-1); end; 这就是把程序的主体看成IO Monad上的一个计算函数。所有的Pascal函数可以通过操作系统的IO设施串联起来.当然随着程序语言往CPU中心化的演化,这些痕迹就逐渐消失了. Monad仅仅是一个数学框架，并没有提供什么新的软件技术。在Monad 诞生之前，程序员们就已经在广泛的使用类似的软件设计方法。但是这些设计方法本身却无法回答我们一系列的追 问:Exception,IO,Pipeline,为什么这些毫不相关的领域中都会出现相同的数学结构?为什么在不同的领域内呈现的Monad 特性完全不同，有的多有的少有的甚至完全消失?这些相同的结构的背后又预示着什么?以及,我们为什么要问这么多为什么?这些问题的答案对我们的编程实践又 有什么意义? (2)关于两个世界体系的对话 并行计算,是一群顽皮的孩童,充满着生机勃勃的活力，却又不失恶作剧式的顽皮。他们仿佛是一座活跃的“火山”。他们身上惊人的能量只有正确的引导 下，才能完全的绽放出来而不致埋没；他们身上顽皮的天性只有在严格的教导中，才不会变成脱缰的野马而无法驾驭。正如儿童的教育首先需要深入他们的内心世 界，我们也必须深入并行计算的本质，去探究这些孩子内心中的陌生而又神奇的世界。 在这群孩子们中间，并发是与我们最为的亲密也是最让我们头疼的一位。如何对付并发?目前存在两个截然对立的答案,Thread Model Vs Event Driven.对这两个模型，在编程实践的层面上我们都经过了严格的探讨，也有很多人通过各种途径去尝试调和其中的分歧。但是Which is a bad idea?是一个至今争论不休的问题。我认为这不是仅靠分析他们各自优劣就能解决的问题，而是必须解释清楚为什么会产生这两种截然不同的方案。知其然，必 先知其所以然。只有回到问题的源头，才能以更宽广的视野去选择道路。 在我们介绍IO Monad的部分时，曾经略带提过计算机体系结构决定了程序员以CPU为思考中心的习惯。这个计算机模型，就是统治我们现在大多数计算机内部构造的冯诺依曼模型。 在计算机中存在两种不同的流，一种称为控制流(Control Flow),另外一种则是数据流(Data Flow)。计算机要进行工作必须要通过其中一种进行驱动。冯诺依曼机的核心工作方式是控制流(指令流)驱动。即按照指令的执行序列，依次读取指令，然 后根据指令所含的控制信息，调用数据进行处理。冯诺依曼机为了控制指令序列的执行顺序，设置一个程序(指令) 计数器PC(Program Counter)，让它存放当前指令所在的存储单元的地址。如果程序现在是顺序执行的，每取出一条指令后PC内容加l，指示下一条指令该从何处取得。如果 程序将转移到某处，就将转移的目标地址送入PC，以便按新地址读取后继指令。 Program Counter是一个递增的自然数。我们知道，自然数集具有严格的顺序性,123,这种特性的集合在数学上被称为偏序集。如果我们在两个偏序集中找到一个函数 那么我们称f为保序的连续映射. 在冯诺依曼机中,正是通过时钟发生器与PC,PC与内存地址之间的连续映射把CPU时间的顺序性映射到了代码的顺序性。比如X86 CPU大致就可以分为下面几个时钟周期.(FC为取指令周期,SC为源操作数周期,DC为目的操作数周期,EC执行周期,IC中断相应周 期,DMA,DMA传送周期) 冯诺依曼机的数据流是由控制流驱动，比如X86Cpu中，数据是在CPU取指以后在SC周期读取的.这点在大多数人看来是不言自明无足轻重的。但 是他们却涉及到了传统编程语言中最为本质的问题。Fortran之父John Backus在它图林奖领奖演说中, 毫不讳言的道出了这一点: 引用” Von Neumann programming languages use variables to imitate the computers storage cells; control statements elaborate its jump and test instructions; and assignment statements imitate its fetching, storing.The primary statement in that world is the assignment statement itself. All the other statements of the language exist in order to make it possible to perform a computation that must be based on this primitive construct: the assignment statement.” “冯诺依曼型的语言,使用变量来模仿计算机的存储单元;控制语句来描述跳转和测试指令;赋值语句模仿数据的获取，存储.这个世界最核心的语句就是赋值语句本身。所有其它语句的存在，只是为了能使那些根植于赋值语句的计算结构可以正确地运行。”这回答了我们一个问题,为什么在传统语言中IO的行为是与Monad截然对立的? 赋值语句本身是一种CPU内部的隐式IO操作。因此传统IO函数与赋值语句是可复合的，它的确让我们的程序看上去自然舒适，而不像IO Monad那样别扭。但是这种暂时的自然舒适，给我们带来了无尽的麻烦。我们能够放心的让计算机运算1+1是因为有图林机和lambda演作为保障。隐式 的赋值语句将IO混入了计算后,会发生什么呢?显然这是这两个模型无法回答，而又需要我们深入探究的问题。作为结构化语言的发明人John Backus在同一片演说里，反复强调了对赋值语句所带来的困扰 引用” Moreover, the assignment statement splits programming into two worlds.The first world comprises the right sides of assignment statements. This is an orderly world of expressions, a world that has useful algebraic propertiesIt is the world in which most useful computation takes place. The second world of conventional programming languages is the world of statements.This world of statements is a disorderly one, with few useful mathematical properties. Structured programming can be seen as a modest effort to introduce some order into this chaotic world, but it accomplishes little in attacking the fundamental problems created by the word-at-a-time von Neumann style of programming, with its primitive use of loops, subscripts, and branching flow of control.” 更重要的是，赋值语句将程序割裂为两个世界。第一个世界是赋值语句右边的世界。这是一个有序的表达式世界，这个世界有许多有用的代数特 性.。最有用的计算都发生在这里。第二个世界是语句的世界，这是一个无序的世界，在那里找不到什么有用的数学特性。结构化编程一定层度上为这个混乱的 世界带来一些秩序，但是它那些原始的循环,子函数,分支流程技术从未击中过冯诺依曼型语言的本质问题-一次一条指令的控制流模式”John Backus的演讲，已经过去31年了，他老人家也已经驾鹤西去。相比于Backus的年代，我们在编程实践上已经有非常丰富的手段来应付这个混乱的世 界，结构化，面向对象，面向方面,动态语言。在这些方法看来，赋值语句与计算是等价的、同质的、混合使用是天经地义无需置疑的；IO只是局部领域内的专有 问题(比如网络通信)而不是全局性的问题。但是另一方面理论研究者们遵循John Backus观点,用数学理论构建IO世界的内在秩序。这些数学理论的推演告诉我们这样一个结果: 在冯诺依曼型语言中IO问题不是局部的而是全局性的。IO具有并发性，而计算是非并发的，这两种操作需要分别处理。当程序中引入越来越多的并行/并发背景 的时候，John Backus的远见卓识就越显示出他深邃的洞察力。 并发占主流的程序里,IO的并发性意味着单台计算机面对的将不是唯一的时钟。比如两台以TCP连接的服务器,他们时钟速度未必是等同的，即便是等 同的我们也无法忽略时钟信号传递的延时。当两个时序不一样的时钟共同驱动一份代码的时候，冯诺依曼机的根本性难题也随之而来。冯诺依曼机的程序指令是按照 CPU的时序顺序执行的，并发多任务程序也不例外。偏序集的有一个特性叫做传递性,12,24,那么14.这种传递性。这使得自 然数集的若干个子集的并集同样存在偏序性. 在冯诺依曼机上,任何与顺序有关的问题，最为简易的方式就是依靠偏序的传递性,从底层自低向上地一级一级传递CPU的时钟序列。Thread Model模型之所以易于开发，也正是因为操作系统在底层控制了时间片的分配，使得每一个Thread的时钟序列和代码顺序保持一致。换而言之 Thread Model是一个放大了的冯诺依曼机，要在这个模型中处理并发，我们必须面一个问题时钟校准。 时钟校准恐怕是这个世界最本质的问题之一，它直接导致了上世纪最为诡异的理论相对论的诞生。从物理学上讲，信号传递是时钟校准的唯一办法。 在计算机中也不能例外，冯诺依曼机要校准不同的时钟序列，就必须解决如何获取外来信号的问题。控制流驱动模式决定了冯诺依曼机不允许外界的信号直接驱动指 令执行。CPU只能通过本地时钟触发控制流，周期性发起状态查询。CPU在某个周期向其他时钟源发送信号，在收到远端时钟的反馈信号后计算得出本地代码序 列上的同步点,然后移动PC指针指向同步点。无论是早期CPU的轮询模式还是现在广泛采用的中断方式，其基本的校准模式并没有改变,只不过查询对象由最初 的IO设备演变为中断寄存器。 基于信号查询的校准方式，让冯诺依曼机在处理并发问题上就像是带着镣铐跳舞。控制流驱动首先无可避免地导致了锁机制的产生。John Backus 告诉我们赋值语句其实是一种IO,它意味着赋值运算符两边数据的单向的数据流动。但是冯诺依曼机的查询式时钟校准机制，必然意味着一次双向的数据流动。如 果以两条赋值指令来驱动一次双向数据交换，那么势必就要同步两条指令的先后执行顺序。但是要同步指令的执行顺序，又必须先校准时序。于是这里我们陷入了类 似于相对论的逻辑困境。两个惯性系中要校准时钟必须首先知道光速的传播速度，而要知道光速的传播速度必须首先校准时钟。爱因斯坦为了避免这种逻辑无穷倒 退，引入了速度不变的光信号。类似地在冯诺依曼机下我们必须强迫一次双向的数据交换在一个指令中瞬时的完成,比如X86下的test&set, exchange等等。这些指令的使用就导致了Mutex, Semaphore, Critical Section各种五花八门的锁结构。随着锁机制的引入，锁竞争，死锁，粒度控制，各种并发性的麻烦滚滚而来。然而我们的麻烦还远没有结束。 控制流驱动还会导致冯诺依曼综合症中的 “Memory Wall”效应(另外两个效应是”Energy Wall“和“Education Wall“)。因为每一次指令的执行都必须伴随着计算数据地址，状态地址，指令地址等等额外的数据流动开销。随着指令数量的增加Memory Wall会越来越厚，最终会阻塞控制流的运行,使其而无法及时响应IO信号。Context Switch就是最为著名的Memeory Wall.在外界的IO信号未到达之前，Thread必须不间断地定期执行信号查询代码。每次查询完毕让出CPU后就要执行复杂的数据流动(比如 Register save/restore,Cache refill等)。为了避免这种开销,现在很多语言采用消耗更低的Green thread的方案. 这些方案可以一定程度上降低消耗但是无法完全根除。在并发性达一定数量级后即便是Erlang这样的语言也无法忽视“Memory Wall”的存在。因为Thread 模型的困难不是来自于局部实现上的疥癣之痒，而是冯诺依曼模型所带来无法根治的顽疾。 在冯诺依曼机统治计算机业的长达60多年,它带来的Education Wall使得很多人特别是战斗在开发第一线的程序员们很难想象有非冯诺依曼结构的存在。其实令人更加难以想象的是，在冯诺依曼这位教皇统治现代计算机工业 之前,绝大多数的电子计算机是并行计算的。有一个传说流传甚广冯诺依曼制造了第一台计算机ENIAC。其实冯诺依曼本人未曾参与ENIAC的制造,那 篇奠定冯诺依曼机结构的101页报告也是在ENIAC运行了一年后才发表的，更重要的是ENIAC是一台并行计算机。冯诺依曼对计算机的兴趣,来自于曼哈 顿工程中大量的数值计算。1944年冯诺依曼在火车站上偶遇了ENIAC总设计师戈尔斯坦后才参观了当时ENIAC的研制小组。当时冯诺依曼发现， 引用“the machines abilities for parallel operations made programming significantly more complicated. This taught him to focus on single-instruction code where parallel handling of operands was guaranteed not to occur” “这些机器的并行操作的能力使得程序编制极为复杂。这一事实让冯诺依曼更多的关注于顺序指令代码，企图以此来保证并行操作决不会出现。” William Aspray 1990.冯诺依曼其实不只一次地在阴沟里翻过船。相对于量子力学的可加性假设，反对Backus设计Fortran语言来说，冯诺依曼综合症还算不上是一 种失误。因为即便在我们这个软硬件高度发达的年代里,并行计算仍然是一个飘荡的幽灵。可以想象,在那个电子管和打孔机的年代里,并行计算的难度恐怕是连这 位能心算无穷级数的天才级数学大师都望而生畏的东西。但是无论如何，冯诺依曼的设计的确为后世的计算机工业带上了一个难以解套的紧箍咒。今日无数天才程序 员为之殚精竭虑的并行计算，其实是一个非常幽默的问题如何在一台原本设计用来杜绝并行计算的机器上进行并行编程？ 由于冯诺依曼机在并行计算上的困难是本质性的，很难在它之上做零碎的修改来彻底治愈冯诺依曼综合症。我们迫切需要适合并行计算的计算机模型。计算 机科学家们发现,运算之间的时序性其实只取决于运算之间结果依赖性。比如说这样一个计算(2+3)*(4+6)。假设我们有两个CPU,显然两个加法可以 同时进行.他们的开始执行时依赖于两个参数的输入时间，乘法的开始执行时间依赖于最后一个加法的完成时间。 这种计算机模型称为数据流机。在这种计算机上，首先需要依靠编译器分析程序中的数据依赖性。与冯诺依曼结构为每一个内存单元表识一个变量名不同， 编译器为每一个运算上的依赖节点标记一个唯一的Tag.比如上面这个运算,我们可以为所有的Input标记Tag(Input1.Input4),为乘 法运算所依赖的两个加法运算标记两个Tag(Add1,Add2)。编译后的运算指令和Tag一起被合并到一种叫instruction storage的包。比如2+3就变成了(Input1,Input2,+,Add1).当程序运行时这些数据包就会加载到一种叫做CAM的内存中。 CAM(Content-addressable memory)与我们普通使用的线性编址随机访问的RAM(Random Access memory)不同。在RAM中我们给出一个地址，它返回这个地址的存储的data word。而CAM是给它一个data word,它会搜索地址空间给出所有存储这个data-word的地址。当一个instruction storage的所有tag处于到达状态时比如(2,3,+,Add1)，(4,6,+,Add2),就会把运算数据和操作指令打包成 instruction token交给运算单元进行并行运算.一旦运算完成,运算单元会将运算结果和输出Tag打成一个data token数据包发送给CAM.CAM就搜索所有依赖于此Tag的instruction storage搜索出来，将对应的tag标记为到达状态比如(5,Add2,*,Output)。 在DataFlow机上整个计算过程由数据流驱动控制流。每一个指令有一系列类似黑盒的Input Output以及相关的运算操作组成。程序的运算顺序依赖于数据的输入顺序，而不依赖于系统的时钟序列。数据也不会像冯诺依曼机一样长久的存储于内存单元 当中，而变成在instruction storage之间传递的数据消息。这种模式在应对针对外部的并发信号时，程序无需进行毫无必要的轮询操作，而是在信号到达的即刻立即响应处理数据。没有 了控制流带来的Memory wall,也不需要引入锁机制。那个阴魂不散的赋值运算符所带来的混乱也消失的无影无踪。 很多程序员在学习Monad模型时,对它那种抽象违反直觉的模型产生本能的反感，认为Monad只是一种纯粹为了形式化而形式化的奇技淫巧。这 种现象并不奇怪，正所谓不识庐山真面目，只缘身在此山中。我们如果在冯诺依曼机的顺序执行的背景下去考察Monad,看到的势必是并发世界在顺序模型上的 扭曲投影。而在DataFlow模型下，Monad模型自然而然地回归到了并发形态。我提到过一个IO Monad 的例子 getline().DO (X=X.ToUpper().IO().DO (X=putline(X); 我们曾把Monad比作联邦快递，现在来看这个联邦快递所作的工作就是在快递数据。每一个被Bind/=复合的函数都是一个可以 并行计算的instruction storage，而Bind/=则是描述了运算与运算之间的依赖性和数据流的走向。IO Monad的各个部件在数据流驱动模型中一一对应必不可少的。现在我们再回过头去关注一下Unix Pipe和早期的Pascal程序,恐怕就不会对他们具有Monad结构而感到奇怪了。Unix发明人Dennis M. Ritchie在中说道: 引用“Of course, the fundamental idea was by no means new; the pipeline is merely a specific form of coroutine.” “当然，管道的基本概念没有什么新意;它只是一种特别形式的协程”Monad结构之所以会在PipeLine的层面上发扬光大,完全是因为pipeline所需要面对的是一群并发的进程。在Ritchie的同一 片文章里,我们还能看到早期Unix系统中地的并发性问题是依靠管道,消息队列等操作系统机制来完成的。也就是说早期的Unix系统本身就是一个使用 Monad结构来构造的并发系统。传统程序语言只是设计用来编写这个并发系统上的非并发的顺序型代码。随着技术的发展,当操作系统层面上的工具无法应付越 来越复杂的并发问题时,我们才想起往传统编程语言中增加并发性的支持。 Monad模型在并发问题上展现出来的强大能力实非偶然。整个DataFlow的计算过程类似一棵表达式展开树。在更加复杂的例子中，比如引入递 归的情况下,DataFlow就会形成一张网或者说图。在DataFlow诞生以来，计算机科学家们对DataFlow网结构特性进行了大量的研究。比如 Thomas Hildebrandt在1998年工作，给出了一个基于traced monoidial category的模型.Tarmo Uustalu and Varmo Vene,2005年在此基础上直接给出了一个基于Co-Monad的DataFlow interpreter. 随着研究的继续深入，人们甚至发现并发机制可能更多的与代数几何的拓扑性质有关。比如并发实体之间的状态组合会随并发数量的增加而导致状态爆炸 (state space explosion problem).状态爆炸意味着我们无法通过机械的手段来控制和检验并发状态的变换和转移，只能依靠人力来检查。现在学者普遍认为现状态空间之间极有可 能存在代数几何中的同伦变换，如果我们能够找到各个状态空间之间的同伦变换，那么我们就无需遍历所有的状态。（ 现在大多数研究者相信, 顺序型问题与并发并行是两个完全不同的领域。前者可能具有更多的代数性质，而后者则是一个完全几何化的问题。这些前沿的研究方向，不是本文的重点。不过我 们值得注意的是Monad./Co-Monad是代数几何基础理论-Topos的核心方法。我们可以这样猜测，Monad之所以与DataFlow模 型兼容，极有可能是因为它具有与并发系统相一致的几何性质。我们还可以更进一步地猜测， Eugenio Moggi论文中用Monad所描述的6种计算可能都是具有并发性的。比如Exception就是一个并发性的问题。这一点在Erlang中体现的最为自 然，Erlang中Exception演变为进程与进程之间的通信消息，Erlang不在需要一层层的try_catch防卫代码。一个进程中的代码出现 异常自己死亡，在死亡之前给link进程发送一个消息由link进程决定如何处理异常。 如果这些数学理论的猜测都能得到证实的话，我们可能面临的是一个编程观念上的极为重要的转折点。在顺序型领域种种软件结构的代数性质问题，在未 来都需要在并行/并发的几何结构上进行重新探讨。这一点也与代数几何的种种结果不谋而合，在代数几何下几乎全部交换代数定理都有明显的几何意义。当然这些 问题是我们无法深究的还是需要留给数学家们去头疼，不过这些前沿理论给我们的编程实践点亮前进的灯塔“The world is parallel “。Joe Armstrong的这句箴言应该成为未来软件设计的首要准则。 DataFlow虽然在并行/并发中有着巨大的优势,但是至今没有什么成功的商业型的应用。这里有着众多原因，首先是硬件设备的制造，与现在动不 动几个G的RAM来相比，大容量的CAM非常难以制造。所以CAM现在只是用在一些特殊的设备上，比如网络交换机和路由器基本依靠CAM来实现地址查找。 其次是软件设计如何去兼顾硬件的限制，指令与数据的依赖性分析需要对程序进行切分，但是切分到什么样的颗粒度则完全依赖于硬件的限制。如果切分的太细那么 硬件之间的通信网络就无法承受大量的数据流。最后是如何能够充分的兼容冯诺依曼机上的软件。这些都是DataFlow模型在工程实践方面尚不成熟的领域。 但是DataFlow模型上有相当多的成熟技术已经广泛应用于我们日常的软硬件里。在指令级层面，比如X86CPU处理器从Cache预取了一 批指令后，通过数据流分析(data flow analysis)分析找出没有互相依赖的并发执行的指令，送到几个独立的执行单元进行乱序执行(Out-of-order execution),最后依靠Cache恢复指令序列。这就是一个缩减化的DataFlow模型。在高级语言层面,许多编译器都能对源代码做数据依赖分 析从而进行代码重排优化，将可并行的指令尽量靠近排列，以便CPU一次能够尽量取到更多的并行指令。 在软件结构的层面上,最直接的案例就是Event Driven。原始的同步/异步IO仍然是一种轮询信号的做法,唯一的不同在于同步IO是Thread内部轮询，异步IO是程序员手工编写轮询编码。为了 进一步提高并发性能,现在主流的操作系统都提供了触发式的IO,比如windows下的完成端口,Linux下的EPOLL/KQueue.这些 Event Driven的模型是一个放大了的DataFlow模型。它将多个台机器上的独立的运算过程，看成是一个DataFlow整体计算。程序员将事件对应的代 码片断，注册在内存中的一张Hash表或者线性表里。只有当外部IO的信号到达的那一刻程序才会查询事件注册表找到对应的程序片断开始执行。Event Driven相比于Thread的优势是显而易见的，没有Context Switch，外部IO事件几乎可以得到实时地响应，没有锁机制和内存共享，程序的鲁棒性和可扩展性大大提到。但是它的缺点也是难以回避的。我们毕竟还是 在冯诺依曼机器上编写代码,我们的编码仍然要受到Program Counter的限制。与Thread自底向上同步时钟序列的模式不同。Event Driven无法依靠偏序集的传递性自动地将外部IO时序与代码之间的顺序映射起来。这也就意味着它必须以一种自顶向下地方式手工维护两者时序的映射关 系。Event Driven难以编写和维护。原本按照本地时钟顺序自然编写的代码，需要程序员手工切分成若干块，以及手工维护复杂的状态机来驱动代码块切换时所产生的数 据流动。 鱼与熊掌如何兼得，就成为了程序员们在处理并发问题上最为头痛的问题.融合Thread和Event Driven，历来有两种不同方向的解决方案。第一种比较主流的方案，是以冯诺依曼机的角度出发，以Thread设施兼容Event Driven，比如Fiber, co-routine, cooperative-thread等等。这一方案的好处在于，实施简单无需在原先的Thread代码上做太多的更动。缺点在于，第一无法消除冯诺依曼 机的Memory Wall, 是一个用空间复杂度换取时间复杂度的方案。 像Fiber这样的解决方案以Stack switch替代Context Switch. 为每一个Fiber保留Stack受到了内存的限制，在C/C+这样大量使用Stack 变量的语言里需要为每一个Fiber预留1M左右的Stack.第二，我们将在后文看到这种方案虽然能够解决并发问题，但是无法解决并行问题。在多核系统 上，多个Event Loop之间的任务调度是一个巨大的难题。 第二种方案是以DataFlow机的角度出发,用Continuation Monad & Lazy Evaluation将Event Driven的代码片断组合出Thread顺序语义。这一工作是，最早是由Koen Claessen在1999年做出的。2007年由Peng Li, Simon Marlow, Simon Peyton Jones 在Haskell上给出了第一个实现。这回答了我们一个问题,为什么在传统语言中IO的行为是与Monad截然对立的? 赋值语句本身是一种CPU内部的隐式IO操作。因此传统IO函数与赋值语句是可复合的，它的确让我们的程序看上去自然舒适，而不像IO Monad那样别扭。但是这种暂时的自然舒适，给我们带来了无尽的麻烦。我们能够放心的让计算机运算1+1是因为有图林机和lambda演作为保障。隐式的赋值语句将IO混入了计算后,会发生什么呢?显然这是这两个模型无法回答，而又需要我们深入探究的问题。作为结构化语言的发明人John Backus在同一片演说里，反复强调了对赋值语句所带来的困扰引用” Moreover, the assignment statement splits programming into two worlds.Thefirst world comprises the right sides of assignment statements. This is anorderly world of expressions, a world that has useful algebraicpropertiesIt is the world in which most useful computation takes place.The second world of conventional programming languages is the world ofstatements.This world of statements is a disorderly one, with few usefulmathematical properties. Structured programming can be seen as a modesteffort to introduce some order into this chaotic world, but it accomplisheslittle in attacking the fundamental problems created by the word-at-a-timevon Neumann style of programming, with its primitive use of loops,subscripts, and branching flow of control.”更重要的是，赋值语句将程序割裂为两个世界。第一个世界是赋值语句右边的世界。这是一个有序的表达式世界，这个世界有许多有用的代数特性.。最有用的计算都发生在这里。第二个世界是语句的世界，这是一个无序的世界，在那里找不到什么有用的数学特性。结构化编程一定层度上为这个混乱的世界带来一些秩序，但是它那些原始的循环,子函数,分支流程技术从未击中过冯诺依曼型语言的本质问题-一次一条指令的控制流模式”John Backus的演讲，已经过去31年了，他老人家也已经驾鹤西去。相比于Backus的年代，我们在编程实践上已经有非常丰富的手段来应付这个混乱的世界，结构化，面向对象，面向方面,动态语言。在这些方法看来，赋值语句与计算是等价的、同质的、混合使用是天经地义无需置疑的；IO只是局部领域内的专有问题(比如网络通信)而不是全局性的问题。但是另一方面理论研究者们遵循John Backus观点,用数学理论构建IO世界的内在秩序。这些数学理论的推演告诉我们这样一个结果: 在冯诺依曼型语言中IO问题不是局部的而是全局性的。IO具有并发性，而计算是非并发的，这两种操作需要分别处理。当程序中引入越来越多的并行/并发背景的时候，John Backus的远见卓识就越显示出他深邃的洞察力。并发占主流的程序里,IO的并发性意味着单台计算机面对的将不是唯一的时钟。比如两台以TCP连接的服务器,他们时钟速度未必是等同的，即便是等同的我们也无法忽略时钟信号传递的延时。当两个时序不一样的时钟共同驱动一份代码的时候，冯诺依曼机的根本性难题也随之而来。冯诺依曼机的程序指令是按照 CPU的时序顺序执行的，并发多任务程序也不例外。偏序集的有一个特性叫做传递性,12,24,那么14.这种传递性。这使得自然数集的若干个子集的并集同样存在偏序性. 在冯诺依曼机上,任何与顺序有关的问题，最为简易的方式就是依靠偏序的传递性,从底层自低向上地一级一级传递CPU的时钟序列。Thread Model模型之所以易于开发，也正是因为操作系统在底层控制了时间片的分配，使得每一个Thread的时钟序列和代码顺序保持一致。换而言之 Thread Model是一个放大了的冯诺依曼机，要在这个模型中处理并发，我们必须面一个问题时钟校准。时钟校准恐怕是这个世界最本质的问题之一，它直接导致了上世纪最为诡异的理论相对论的诞生。从物理学上讲，信号传递是时钟校准的唯一办法。在计算机中也不能例外，冯诺依曼机要校准不同的时钟序列，就必须解决如何获取外来信号的问题。控制流驱动模式决定了冯诺依曼机不允许外界的信号直接驱动指令执行。CPU只能通过本地时钟触发控制流，周期性发起状态查询。CPU在某个周期向其他时钟源发送信号，在收到远端时钟的反馈信号后计算得出本地代码序列上的同步点,然后移动PC指针指向同步点。无论是早期CPU的轮询模式还是现在广泛采用的中断方式，其基本的校准模式并没有改变,只不过查询对象由最初的IO设备演变为中断寄存器。基于信号查询的校准方式，让冯诺依曼机在处理并发问题上就像是带着镣铐跳舞。控制流驱动首先无可避免地导致了锁机制的产生。John Backus 告诉我们赋值语句其实是一种IO,它意味着赋值运算符两边数据的单向的数据流动。但是冯诺依曼机的查询式时钟校准机制，必然意味着一次双向的数据流动。如果以两条赋值指令来驱动一次双向数据交换，那么势必就要同步两条指令的先后执行顺序。但是要同步指令的执行顺序，又必须先校准时序。于是这里我们陷入了类似于相对论的逻辑困境。两个惯性系中要校准时钟必须首先知道光速的传播速度，而要知道光速的传播速度必须首先校准时钟。爱因斯坦为了避免这种逻辑无穷倒退，引入了速度不变的光信号。类似地在冯诺依曼机下我们必须强迫一次双向的数据交换在一个指令中瞬时的完成,比如X86下的test&set, exchange等等。这些指令的使用就导致了Mutex, Semaphore, Critical Section各种五花八门的锁结构。随着锁机制的引入，锁竞争，死锁，粒度控制，各种并发性的麻烦滚滚而来。然而我们的麻烦还远没有结束。控制流驱动还会导致冯诺依曼综合症中的 “Memory Wall”效应(另外两个效应是”EnergyWall“和“Education Wall“)。因为每一次指令的执行都必须伴随着计算数据地址，状态地址，指令地址等等额外的数据流动开销。随着指令数量的增加Memory Wall会越来越厚，最终会阻塞控制流的运行,使其而无法及时响应IO信号。Context Switch就是最为著名的Memeory Wall.在外界的IO信号未到达之前，Thread必须不间断地定期执行信号查询代码。每次查询完毕让出CPU后就要执行复杂的数据流动(比如 Registersave/restore,Cache refill等)。为了避免这种开销,现在很多语言采用消耗更低的Green thread的方案. 这些方案可以一定程度上降低消耗但是无法完全根除。在并发性达一定数量级后即便是Erlang这样的语言也无法忽视“Memory Wall”的存在。因为Thread模型的困难不是来自于局部实现上的疥癣之痒，而是冯诺依曼模型所带来无法根治的顽疾。在冯诺依曼机统治计算机业的长达60多年,它带来的Education Wall使得很多人特别是战斗在开发第一线的程序员们很难想象有非冯诺依曼结构的存在。其实令人更加难以想象的是，在冯诺依曼这位教皇统治现代计算机工业之前,绝大多数的电子计算机是并行计算的。有一个传说流传甚广冯诺依曼制造了第一台计算机ENIAC。其实冯诺依曼本人未曾参与ENIAC的制造,那篇奠定冯诺依曼机结构的101页报告也是在ENIAC运行了一年后才发表的，更重要的是ENIAC是一台并行计算机。冯诺依曼对计算机的兴趣,来自于曼哈顿工程中大量的数值计算。1944年冯诺依曼在火车站上偶遇了ENIAC总设计师戈尔斯坦后才参观了当时ENIAC的研制小组。当时冯诺依曼发现，引用“the machines abilities for parallel operations made programmingsignificantly more complicated. This taught him to focus onsingle-instruction code where parallel handling of operands was guaranteednot to occur”“这些机器的并行操作的能力使得程序编制极为复杂。这一事实让冯诺依曼更多的关注于顺序指令代码，企图以此来保证并行操作决不会出现。” William Aspray 1990.冯诺依曼其实不只一次地在阴沟里翻过船。相对于量子力学的可加性假设，反对Backus设计Fortran语言来说，冯诺依曼综合症还算不上是一种失误。因为即便在我们这个软硬件高度发达的年代里,并行计算仍然是一个飘荡的幽灵。可以想象,在那个电子管和打孔机的年代里,并行计算的难度恐怕是连这位能心算无穷级数的天才级数学大师都望而生畏的东西。但是无论如何，冯诺依曼的设计的确为后世的计算机工业带上了一个难以解套的紧箍咒。今日无数天才程序员为之殚精竭虑的并行计算，其实是一个非常幽默的问题如何在一台原本设计用来杜绝并行计算的机器上进行并行编程？由于冯诺依曼机在并行计算上的困难是本质性的，很难在它之上做零碎的修改来彻底治愈冯诺依曼综合症。我们迫切需要适合并行计算的计算机模型。计算机科学家们发现,运算之间的时序性其实只取决于运算之间结果依赖性。比如说这样一个计算(2+3)*(4+6)。假设我们有两个CPU,显然两个加法可以同时进行.他们的开始执行时依赖于两个参数的输入时间，乘法的开始执行时间依赖于最后一个加法的完成时间。这就是传说中的交叉引用。 Trustno1 写道转贴一个评论,牛人就是牛人. 引用本文: 转寄转贴删除修改回复作者:dragondevil人气:86 发信人: dragondevil(流星见龙在田), 信区: Algorithm 标 题: Re: 转载zz 关于两个世界体系的对话 -by Trustno1 发信站: 瀚海星云 (2008年08月23日13:26:20 星期六), 站内信件 WWWPOST 不错的文章。不超出基于Von带来的认识，就不会发现计算的本质，既不是函数也不是数据 结构，仅仅是数据流本身。Education wall，正是最令人担心的。注意到即便是CAM模型， 也不过是为Anti-Von故意反其道而行罢了，仍然有查询，并不直接的实践数据流向的交换。 当实践了一组指令模块的输出向输入的任意调度，使这些模块持续工作，程序的功能就只剩 下约定哪个时钟沿将哪个模块的输出送到