计算机基础知识教案

1、 HYPERLINK / 适应经验的强大惯性，源自于背景的长期稳定性。软件体系的快速变革，让我们忽视了硬件体系的长期稳定。这种稳定性使得专门多适应经验变成了不言自明的信条。 大多数的软件设计方法的革新只只是是用旧石斧打造出来新石斧。在C中我们使用getc,putc来进行IO,在Java中无非是变成了 System.in.read(),System.out.print ()。什么缘故IO必定是这种形式呢?这是因为我们长期使用着同一种计算机。我们明白PC/Mac如此的计算机中CPU与IO设备进行通信，需要通过各种总 线。下面这张图演示了CPU与IO设备之间通信的差不多过程. 以 C语言为代表的传统

2、的IO,实际上是单CPU上单任务工作模式的投影。在单台计算机上, 传统计算机体系结构决定了CPU处于操纵者和决策者的地位。换而言之,我们历来适应于以CPU的视角来考虑程序的IO逻辑.程序员是将自己假设为CPU. 程序员关怀的IO设施只是一个黑盒.我们只需要往IO发送一个请求，然后等待请求回来进行运算,完全不关怀这一来一回之间到底发生了什么过程. 然而当我们打开黑盒,观看CPU与IO的通信过程的时候, IO Monad就从幕后走向了台前。以总线的角度看,CPU和外设是等同的，都只是一个具有运算能力和输入输出端口的黑盒.总线正如 Bind/=函数一样不关怀这些黑盒子里如何运算的，它只关怀从那个黑盒

3、拿数据出来放入那个黑盒. 从整个计算机的体系结构看，传统的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,再通过|管

4、道符传送给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函

5、数能够通过操作系统的IO设施串联起来.因此随着程序语言往CPU中心化的演化,这些痕迹就逐渐消逝了. Monad仅仅是一个数学框架，并没有提供什么新的软件技术。在Monad 诞生之前，程序员们就差不多在广泛的使用类似的软件设计方法。然而这些设计方法本身却无法回答我们一系列的追 问:Exception,IO,Pipeline,什么缘故这些毫不相关的领域中都会出现相同的数学结构?什么缘故在不同的领域内呈现的Monad 特性完全不同，有的多有的少有的甚至完全消逝?这些相同的结构的背后又预示着什么?以及,我们什么缘故要问这么多什么缘故?这些问题的答案对我们的编程实践又 有什么意义? (2)关于两个世界体

6、系的对话 并行计算,是一群顽皮的孩童,充满着生机勃勃的活力，却又不失恶作剧式的顽皮。他们仿佛是一座活跃的“火山”。他们身上惊人的能量只有正确的引导 下，才能完全的绽放出来而不致埋没；他们身上顽皮的天性只有在严格的教导中，才可不能变成脱缰的野马而无法驾驭。正如儿童的教育首先需要深入他们的内心世 界，我们也必须深入并行计算的本质，去探究这些小孩内心中的陌生而又奇妙的世界。 在这群小孩们中间，并发是与我们最为的亲热也是最让我们头疼的一位。如何应付并发?目前存在两个截然对立的答案,Thread Model Vs Event Driven.对这两个模型，在编程实践的层面上我们都通过了严格的探讨，也有专门

7、多人通过各种途径去尝试调和其中的分歧。然而Which is a bad idea?是一个至今争论不休的问题。我认为这不是仅靠分析他们各自优劣就能解决的问题，而是必须解释清晰什么缘故会产生这两种截然不同的方案。知其然，必 先知其因此然。只有回到问题的源头，才能以更宽广的视野去选择道路。 在我们介绍IO Monad的部分时，曾经略带提过计算机体系结构决定了程序员以CPU为考虑中心的适应。那个计算机模型，确实是统治我们现在大多数计算机内部构造的冯诺依曼模型。 在计算机中存在两种不同的流，一种称为操纵流(Control Flow),另外一种则是数据流(Data Flow)。计算机要进行工作必须要通过其

8、中一种进行驱动。冯诺依曼机的核心工作方式是操纵流(指令流)驱动。即按照指令的执行序列，依次读取指令，然 后依照指令所含的操纵信息，调用数据进行处理。冯诺依曼机为了操纵指令序列的执行顺序，设置一个程序(指令) 计数器PC(Program Counter)，让它存放当前指令所在的存储单元的地址。假如程序现在是顺序执行的，每取出一条指令后PC内容加l，指示下一条指令该从何处取得。假如 程序将转移到某处，就将转移的目标地址送入PC，以便按新地址读取后继指令。 Program Counter是一个递增的自然数。我们明白，自然数集具有严格的顺序性,123,这种特性的集合在数学上被称为偏序集。假如我们在两个

9、偏序集中找到一个函数 那么我们称f为保序的连续映射. 在冯诺依曼机中,正是通过时钟发生器与PC,PC与内存地址之间的连续映射把CPU时刻的顺序性映射到了代码的顺序性。比如X86 CPU大致就能够分为下面几个时钟周期.(FC为取指令周期,SC为源操作数周期,DC为目的操作数周期,EC执行周期,IC中断相应周 期,DMA,DMA传送周期) 冯诺依曼机的数据流是由操纵流驱动，比如X86Cpu中，数据是在CPU取指以后在SC周期读取的.这点在大多数人看来是不言自明无足轻重的。但 是他们却涉及到了传统编程语言中最为本质的问题。Fortran之父John Backus在它图林奖领奖演讲中, 毫不讳言的道出

10、了这一点: 引用” 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

11、 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.” “冯诺依曼型的语言,使用变量来模仿计算机的存储单元;操纵语句来描述跳转和测试指令;赋值语句模仿数据的猎取，存储.那个世界最核心的语句确实是赋值语句本身。所有其它语句的存在，只是为了能使那些根植于赋值语句的计算结构能够正确地运行。”这回答了我们一个问题,什么缘故在传统语言中I

12、O的行为是与Monad截然对立的? 赋值语句本身是一种CPU内部的隐式IO操作。因此传统IO函数与赋值语句是可复合的，它的确让我们的程序看上去自然舒适，而不像IO Monad那样不扭。然而这种临时的自然舒适，给我们带来了无尽的苦恼。我们能够放心的让计算机运算1+1是因为有图林机和lambda演作为保障。隐式 的赋值语句将IO混入了计算后,会发生什么呢?显然这是这两个模型无法回答，而又需要我们深入探究的问题。作为结构化语言的发明人John Backus在同一片演讲里，反复强调了对赋值语句所带来的困扰 引用” Moreover, the assignment statement splits pr

13、ogramming 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 t

14、he 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

15、-a-time von Neumann style of programming, with its primitive use of loops, subscripts, and branching flow of control.” 更重要的是，赋值语句将程序割裂为两个世界。第一个世界是赋值语句右边的世界。这是一个有序的表达式世界，那个世界有许多有用的代数特 性.。最有用的计算都发生在那个地点。第二个世界是语句的世界，这是一个无序的世界，在那儿找不到什么有用的数学特性。结构化编程一定层度上为那个混乱的 世界带来一些秩序，然而它那些原始的循环,子函数,分支流程技术从未击中过冯诺依曼型语言的本

16、质问题-一次一条指令的操纵流模式”John Backus的演讲，差不多过去31年了，他老人家也差不多驾鹤西去。相比于Backus的年代，我们在编程实践上差不多有特不丰富的手段来应付那个混乱的世 界，结构化，面向对象，面向方面,动态语言。在这些方法看来，赋值语句与计确实是等价的、同质的、混合使用是天经地义无需置疑的；IO只是局部领域内的专有 问题(比如网络通信)而不是全局性的问题。然而另一方面理论研究者们遵循John Backus观点,用数学理论构建IO世界的内在秩序。这些数学理论的推演告诉我们如此一个结果: 在冯诺依曼型语言中IO问题不是局部的而是全局性的。IO具有并发性，而计确实是非并发的，

17、这两种操作需要分不处理。当程序中引入越来越多的并行/并发背景 的时候，John Backus的远见卓识就越显示出他深邃的洞察力。 并发占主流的程序里,IO的并发性意味着单台计算机面对的将不是唯一的时钟。比如两台以TCP连接的服务器,他们时钟速度未必是等同的，即便是等 同的我们也无法忽略时钟信号传递的延时。当两个时序不一样的时钟共同驱动一份代码的时候，冯诺依曼机的全然性难题也随之而来。冯诺依曼机的程序指令是按照 CPU的时序顺序执行的，并发多任务程序也不例外。偏序集的有一个特性叫做传递性,12,24,那么14.这种传递性。这使得自 然数集的若干个子集的并集同样存在偏序性. 在冯诺依曼机上,任何与

18、顺序有关的问题，最为简易的方式确实是依靠偏序的传递性,从底层自低向上地一级一级传递CPU的时钟序列。Thread Model模型之因此易于开发，也正是因为操作系统在底层操纵了时刻片的分配，使得每一个Thread的时钟序列和代码顺序保持一致。换而言之 Thread Model是一个放大了的冯诺依曼机，要在那个模型中处理并发，我们必须面一个问题时钟校准。 时钟校准可能是那个世界最本质的问题之一，它直接导致了上世纪最为诡异的理论相对论的诞生。从物理学上讲，信号传递是时钟校准的唯一方法。 在计算机中也不能例外，冯诺依曼机要校准不同的时钟序列，就必须解决如何猎取外来信号的问题。操纵流驱动模式决定了冯诺依

19、曼机不同意外界的信号直接驱动指 令执行。CPU只能通过本地时钟触发操纵流，周期性发起状态查询。CPU在某个周期向其他时钟源发送信号，在收到远端时钟的反馈信号后计算得出本地代码序 列上的同步点,然后移动PC指针指向同步点。不管是早期CPU的轮询模式依旧现在广泛采纳的中断方式，其差不多的校准模式并没有改变,只只是查询对象由最初 的IO设备演变为中断寄存器。 基于信号查询的校准方式，让冯诺依曼机在处理并发问题上就像是带着镣铐跳舞。操纵流驱动首先无可幸免地导致了锁机制的产生。John Backus 告诉我们赋值语句事实上是一种IO,它意味着赋值运算符两边数据的单向的数据流淌。然而冯诺依曼机的查询式时钟

20、校准机制，必定意味着一次双向的数据流淌。如 果以两条赋值指令来驱动一次双向数据交换，那么势必就要同步两条指令的先后执行顺序。然而要同步指令的执行顺序，又必须先校准时序。因此那个地点我们陷入了类 似于相对论的逻辑困境。两个惯性系中要校准时钟必须首先明白光速的传播速度，而要明白光速的传播速度必须首先校准时钟。爱因斯坦为了幸免这种逻辑无穷倒 退，引入了速度不变的光信号。类似地在冯诺依曼机下我们必须强迫一次双向的数据交换在一个指令中瞬时的完成,比如X86下的test&set, exchange等等。这些指令的使用就导致了Mutex, Semaphore, Critical Section各种五花八门的

21、锁结构。随着锁机制的引入，锁竞争，死锁，粒度操纵，各种并发性的苦恼滚滚而来。然而我们的苦恼还远没有结束。 操纵流驱动还会导致冯诺依曼综合症中的 “Memory Wall”效应(另外两个效应是”Energy Wall“和“Education Wall“)。因为每一次指令的执行都必须伴随着计算数据地址，状态地址，指令地址等等额外的数据流淌开销。随着指令数量的增加Memory Wall会越来越厚，最终会堵塞操纵流的运行,使其而无法及时响应IO信号。Context Switch确实是最为闻名的Memeory Wall.在外界的IO信号未到达之前，Thread必须不间断地定期执行信号查询代码。每次查询完

22、毕让出CPU后就要执行复杂的数据流淌(比如 Register save/restore,Cache refill等)。为了幸免这种开销,现在专门多语言采纳消耗更低的Green thread的方案. 这些方案能够一定程度上降低消耗然而无法完全根除。在并发性达一定数量级后即便是Erlang如此的语言也无法忽视“Memory Wall”的存在。因为Thread 模型的困难不是来自于局部实现上的疥癣之痒，而是冯诺依曼模型所带来无法根治的顽疾。 在冯诺依曼机统治计算机业的长达60多年,它带来的Education Wall使得专门多人特不是战斗在开发第一线的程序员们专门难想象有非冯诺依曼结构的存在。事实上

23、令人更加难以想象的是，在冯诺依曼这位教皇统治现代计算机工业 之前,绝大多数的电子计算机是并行计算的。有一个传讲流传甚广冯诺依曼制造了第一台计算机ENIAC。事实上冯诺依曼本人未曾参与ENIAC的制造,那 篇奠定冯诺依曼机结构的101页报告也是在ENIAC运行了一年后才发表的，更重要的是ENIAC是一台并行计算机。冯诺依曼对计算机的兴趣,来自于曼哈 顿工程中大量的数值计算。1944年冯诺依曼在火车站上偶遇了ENIAC总设计师戈尔斯坦后才参观了当时ENIAC的研制小组。当时冯诺依曼发觉， 引用“the machines abilities for parallel operations made

24、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语言

25、来讲，冯诺依曼综合症还算不上是一 种失误。因为即便在我们那个软硬件高度发达的年代里,并行计算仍然是一个漂移的幽灵。能够想象,在那个电子管和打孔机的年代里,并行计算的难度可能是连这 位能心算无穷级数的天才级数学大师都望而生畏的东西。然而不管如何，冯诺依曼的设计的确为后世的计算机工业带上了一个难以解套的紧箍咒。今日许多天才程序 员为之殚精竭虑的并行计算，事实上是一个特不幽默的问题如何在一台原本设计用来杜绝并行计算的机器上进行并行编程？ 由于冯诺依曼机在并行计算上的困难是本质性的，专门难在它之上做零碎的修改来完全治愈冯诺依曼综合症。我们迫切需要适合并行计算的计算机模型。计算 机科学家们发觉,运算之间

26、的时序性事实上只取决于运算之间结果依靠性。比如讲如此一个计算(2+3)*(4+6)。假设我们有两个CPU,显然两个加法能够 同时进行.他们的开始执行时依靠于两个参数的输入时刻，乘法的开始执行时刻依靠于最后一个加法的完成时刻。 这种计算机模型称为数据流机。在这种计算机上，首先需要依靠编译器分析程序中的数据依靠性。与冯诺依曼结构为每一个内存单元表识一个变量名不同， 编译器为每一个运算上的依靠节点标记一个唯一的Tag.比如上面那个运算,我们能够为所有的Input标记Tag(Input1.Input4),为乘 法运算所依靠的两个加法运算标记两个Tag(Add1,Add2)。编译后的运算指令和Tag一起

27、被合并到一种叫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)，(

28、4,6,+,Add2),就会把运算数据和操作指令打包成 instruction token交给运算单元进行并行运算.一旦运算完成,运算单元会将运算结果和输出Tag打成一个data token数据包发送给CAM.CAM就搜索所有依靠于此Tag的instruction storage搜索出来，将对应的tag标记为到达状态比如(5,Add2,*,Output)。 在DataFlow机上整个计算过程由数据流驱动操纵流。每一个指令有一系列类似黑盒的Input Output以及相关的运算操作组成。程序的运算顺序依靠于数据的输入顺序，而不依靠于系统的时钟序列。数据也可不能像冯诺依曼机一样长久的存储于内存单元

29、 当中，而变成在instruction storage之间传递的数据消息。这种模式在应对针对外部的并发信号时，程序无需进行毫无必要的轮询操作，而是在信号到达的即刻立即响应处理数据。没有 了操纵流带来的Memory wall,也不需要引入锁机制。那个阴魂不散的赋值运算符所带来的混乱也消逝的无影无踪。 专门多程序员在学习Monad模型时,对它那种抽象违反直觉的模型产生本能的反感，认为Monad只是一种纯粹为了形式化而形式化的奇技淫巧。这 种现象并不惊奇，正所谓不识庐山真面目，只缘身在此山中。我们假如在冯诺依曼机的顺序执行的背景下去考察Monad,看到的势必是并发世界在顺序模型上的 扭曲投影。而在D

30、ataFlow模型下，Monad模型自然而然地回归到了并发形态。我提到过一个IO Monad 的例子 getline().DO (X=X.ToUpper().IO().DO (X=putline(X); 我们曾把Monad比作联邦快递，现在来看那个联邦快递所作的工作确实是在快递数据。每一个被Bind/=复合的函数差不多上一个能够 并行计算的instruction storage，而Bind/=则是描述了运算与运算之间的依靠性和数据流的走向。IO Monad的各个部件在数据流驱动模型中一一对应必不可少的。现在我们再回过头去关注一下Unix Pipe和早期的Pascal程序,可能就可不能对他们具有

31、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系统中地的并发性问题是依靠管道,消息队列等操作系统机制来

32、完成的。也确实是讲早期的Unix系统本身确实是一个使用 Monad结构来构造的并发系统。传统程序语言只是设计用来编写那个并发系统上的非并发的顺序型代码。随着技术的进展,当操作系统层面上的工具无法应付越 来越复杂的并发问题时,我们才想起往传统编程语言中增加并发性的支持。 Monad模型在并发问题上展现出来的强大能力实非偶然。整个DataFlow的计算过程类似一棵表达式展开树。在更加复杂的例子中，比如引入递 归的情况下,DataFlow就会形成一张网或者讲图。在DataFlow诞生以来，计算机科学家们对DataFlow网结构特性进行了大量的研究。比如 Thomas Hildebrandt在1998

33、年工作，给出了一个基于traced monoidial category的模型.Tarmo Uustalu and Varmo Vene,2005年在此基础上直接给出了一个基于Co-Monad的DataFlow interpreter. 随着研究的接着深入，人们甚至发觉并发机制可能更多的与代数几何的拓扑性质有关。比如并发实体之间的状态组合会随并发数量的增加而导致状态爆炸 (state space explosion problem).状态爆炸意味着我们无法通过机械的手段来操纵和检验并发状态的变换和转移，只能依靠人力来检查。现在学者普遍认为现状态空间之间极有可 能存在代数几何中的同伦变换，假如我

34、们能够找到各个状态空间之间的同伦变换，那么我们就无需遍历所有的状态。（ HYPERLINK http:/www.di.ens.fr/%7Egoubault/index1.html t _blank 现在大多数研究者相信, 顺序型问题与并发并行是两个完全不同的领域。前者可能具有更多的代数性质，而后者则是一个完全几何化的问题。这些前沿的研究方向，不是本文的重点。只是我 们值得注意的是Monad./Co-Monad是代数几何基础理论-Topos的核心方法。我们能够如此推测，Monad之因此与DataFlow模 型兼容，极有可能是因为它具有与并发系统相一致的几何性质。我们还能够更进一步地推测， Eug

35、enio Moggi论文中用Monad所描述的6种计算可能差不多上具有并发性的。比如Exception确实是一个并发性的问题。这一点在Erlang中体现的最为自 然，Erlang中Exception演变为进程与进程之间的通信消息，Erlang不在需要一层层的try_catch防卫代码。一个进程中的代码出现 异常自己死亡，在死亡之前给link进程发送一个消息由link进程决定如何处理异常。 假如这些数学理论的推测都能得到证实的话，我们可能面临的是一个编程观念上的极为重要的转折点。在顺序型领域种种软件结构的代数性质问题，在未 来都需要在并行/并发的几何结构上进行重新探讨。这一点也与代数几何的种种结

36、果不谋而合，在代数几何下几乎全部交换代数定理都有明显的几何意义。因此这些 问题是我们无法深究的依旧需要留给数学家们去头疼，只是这些前沿理论给我们的编程实践点亮前进的灯塔“The world is parallel “。Joe Armstrong的这句箴言应该成为以后软件设计的首要准则。 DataFlow尽管在并行/并发中有着巨大的优势,然而至今没有什么成功的商业型的应用。那个地点有着众多缘故，首先是硬件设备的制造，与现在动不 动几个G的RAM来相比，大容量的CAM特不难以制造。因此CAM现在只是用在一些专门的设备上，比如网络交换机和路由器差不多依靠CAM来实现地址查找。 其次是软件设计如何去兼

37、顾硬件的限制，指令与数据的依靠性分析需要对程序进行切分，然而切分到什么样的颗粒度则完全依靠于硬件的限制。假如切分的太细那么 硬件之间的通信网络就无法承受大量的数据流。最后是如何能够充分的兼容冯诺依曼机上的软件。这些差不多上DataFlow模型在工程实践方面尚不成熟的领域。 然而DataFlow模型上有相当多的成熟技术差不多广泛应用于我们日常的软硬件里。在指令级层面，比如X86CPU处理器从Cache预取了一 批指令后，通过数据流分析(data flow analysis)分析找出没有互相依靠的并发执行的指令，送到几个独立的执行单元进行乱序执行(Out-of-order execution),最

38、后依靠Cache恢复指令序列。这确实是一个缩减化的DataFlow模型。在高级语言层面,许多编译器都能对源代码做数据依靠分 析从而进行代码重排优化，将可并行的指令尽量靠近排列，以便CPU一次能够尽量取到更多的并行指令。 在软件结构的层面上,最直接的案例确实是Event Driven。原始的同步/异步IO仍然是一种轮询信号的做法,唯一的不同在于同步IO是Thread内部轮询，异步IO是程序员手工编写轮询编码。为了 进一步提高并发性能,现在主流的操作系统都提供了触发式的IO,比如windows下的完成端口,Linux下的EPOLL/KQueue.这些 Event Driven的模型是一个放大了的D

39、ataFlow模型。它将多个台机器上的独立的运算过程，看成是一个DataFlow整体计算。程序员将事件对应的代 码片断，注册在内存中的一张Hash表或者线性表里。只有当外部IO的信号到达的那一刻程序才会查询事件注册表找到对应的程序片断开始执行。Event Driven相比于Thread的优势是显而易见的，没有Context Switch，外部IO事件几乎能够得到实时地响应，没有锁机制和内存共享，程序的鲁棒性和可扩展性大大提到。然而它的缺点也是难以回避的。我们怎么讲依旧 在冯诺依曼机器上编写代码,我们的编码仍然要受到Program Counter的限制。与Thread自底向上同步时钟序列的模式不

40、同。Event Driven无法依靠偏序集的传递性自动地将外部IO时序与代码之间的顺序映射起来。这也就意味着它必须以一种自顶向下地点式手工维护两者时序的映射关 系。Event Driven难以编写和维护。原本按照本地时钟顺序自然编写的代码，需要程序员手工切分成若干块，以及手工维护复杂的状态机来驱动代码块切换时所产生的数 据流淌。 鱼与熊掌如何兼得，就成为了程序员们在处理并发问题上最为头痛的问题.融合Thread和Event Driven，历来有两种不同方向的解决方案。第一种比较主流的方案，是以冯诺依曼机的角度动身，以Thread设施兼容Event Driven，比如Fiber, co-rout

41、ine, cooperative-thread等等。这一方案的好处在于，实施简单无需在原先的Thread代码上做太多的更动。缺点在于，第一无法消除冯诺依曼 机的Memory Wall, 是一个用空间复杂度换取时刻复杂度的方案。 像Fiber如此的解决方案以Stack switch替代Context Switch. 为每一个Fiber保留Stack受到了内存的限制，在C/C+如此大量使用Stack 变量的语言里需要为每一个Fiber预留1M左右的Stack.第二，我们将在后文看到这种方案尽管能够解决并发问题，然而无法解决并行问题。在多核系统 上，多个Event Loop之间的任务调度是一个巨大的

42、难题。 第二种方案是以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 Mo

43、nad那样不扭。然而这种临时的自然舒适，给我们带来了无尽的苦恼。我们能够放心的让计算机运算1+1是因为有图林机和lambda演作为保障。隐式的赋值语句将IO混入了计算后,会发生什么呢?显然这是这两个模型无法回答，而又需要我们深入探究的问题。作为结构化语言的发明人John Backus在同一片演讲里，反复强调了对赋值语句所带来的困扰引用” Moreover, the assignment statement splits programming into two worlds.Thefirst world comprises the right sides of assignment state

44、ments. 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 usefulmathema

45、tical 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 branc

46、hing flow of control.”更重要的是，赋值语句将程序割裂为两个世界。第一个世界是赋值语句右边的世界。这是一个有序的表达式世界，那个世界有许多有用的代数特性.。最有用的计算都发生在那个地点。第二个世界是语句的世界，这是一个无序的世界，在那儿找不到什么有用的数学特性。结构化编程一定层度上为那个混乱的世界带来一些秩序，然而它那些原始的循环,子函数,分支流程技术从未击中过冯诺依曼型语言的本质问题-一次一条指令的操纵流模式”John Backus的演讲，差不多过去31年了，他老人家也差不多驾鹤西去。相比于Backus的年代，我们在编程实践上差不多有特不丰富的手段来应付那个混乱的世界，结

47、构化，面向对象，面向方面,动态语言。在这些方法看来，赋值语句与计确实是等价的、同质的、混合使用是天经地义无需置疑的；IO只是局部领域内的专有问题(比如网络通信)而不是全局性的问题。然而另一方面理论研究者们遵循John Backus观点,用数学理论构建IO世界的内在秩序。这些数学理论的推演告诉我们如此一个结果: 在冯诺依曼型语言中IO问题不是局部的而是全局性的。IO具有并发性，而计确实是非并发的，这两种操作需要分不处理。当程序中引入越来越多的并行/并发背景的时候，John Backus的远见卓识就越显示出他深邃的洞察力。并发占主流的程序里,IO的并发性意味着单台计算机面对的将不是唯一的时钟。比如

48、两台以TCP连接的服务器,他们时钟速度未必是等同的，即便是等同的我们也无法忽略时钟信号传递的延时。当两个时序不一样的时钟共同驱动一份代码的时候，冯诺依曼机的全然性难题也随之而来。冯诺依曼机的程序指令是按照 CPU的时序顺序执行的，并发多任务程序也不例外。偏序集的有一个特性叫做传递性,12,24,那么14.这种传递性。这使得自然数集的若干个子集的并集同样存在偏序性. 在冯诺依曼机上,任何与顺序有关的问题，最为简易的方式确实是依靠偏序的传递性,从底层自低向上地一级一级传递CPU的时钟序列。Thread Model模型之因此易于开发，也正是因为操作系统在底层操纵了时刻片的分配，使得每一个Thread

49、的时钟序列和代码顺序保持一致。换而言之 Thread Model是一个放大了的冯诺依曼机，要在那个模型中处理并发，我们必须面一个问题时钟校准。时钟校准可能是那个世界最本质的问题之一，它直接导致了上世纪最为诡异的理论相对论的诞生。从物理学上讲，信号传递是时钟校准的唯一方法。在计算机中也不能例外，冯诺依曼机要校准不同的时钟序列，就必须解决如何猎取外来信号的问题。操纵流驱动模式决定了冯诺依曼机不同意外界的信号直接驱动指令执行。CPU只能通过本地时钟触发操纵流，周期性发起状态查询。CPU在某个周期向其他时钟源发送信号，在收到远端时钟的反馈信号后计算得出本地代码序列上的同步点,然后移动PC指针指向同步点

50、。不管是早期CPU的轮询模式依旧现在广泛采纳的中断方式，其差不多的校准模式并没有改变,只只是查询对象由最初的IO设备演变为中断寄存器。基于信号查询的校准方式，让冯诺依曼机在处理并发问题上就像是带着镣铐跳舞。操纵流驱动首先无可幸免地导致了锁机制的产生。John Backus 告诉我们赋值语句事实上是一种IO,它意味着赋值运算符两边数据的单向的数据流淌。然而冯诺依曼机的查询式时钟校准机制，必定意味着一次双向的数据流淌。假如以两条赋值指令来驱动一次双向数据交换，那么势必就要同步两条指令的先后执行顺序。然而要同步指令的执行顺序，又必须先校准时序。因此那个地点我们陷入了类似于相对论的逻辑困境。两个惯性系

51、中要校准时钟必须首先明白光速的传播速度，而要明白光速的传播速度必须首先校准时钟。爱因斯坦为了幸免这种逻辑无穷倒退，引入了速度不变的光信号。类似地在冯诺依曼机下我们必须强迫一次双向的数据交换在一个指令中瞬时的完成,比如X86下的test&set, exchange等等。这些指令的使用就导致了Mutex, Semaphore, Critical Section各种五花八门的锁结构。随着锁机制的引入，锁竞争，死锁，粒度操纵，各种并发性的苦恼滚滚而来。然而我们的苦恼还远没有结束。操纵流驱动还会导致冯诺依曼综合症中的 “Memory Wall”效应(另外两个效应是”EnergyWall“和“Educat

52、ion Wall“)。因为每一次指令的执行都必须伴随着计算数据地址，状态地址，指令地址等等额外的数据流淌开销。随着指令数量的增加Memory Wall会越来越厚，最终会堵塞操纵流的运行,使其而无法及时响应IO信号。Context Switch确实是最为著名的Memeory Wall.在外界的IO信号未到达之前，Thread必须不间断地定期执行信号查询代码。每次查询完毕让出CPU后就要执行复杂的数据流淌(比如 Registersave/restore,Cache refill等)。为了幸免这种开销,现在专门多语言采纳消耗更低的Green thread的方案. 这些方案能够一定程度上降低消耗然而无

53、法完全根除。在并发性达一定数量级后即便是Erlang如此的语言也无法忽视“Memory Wall”的存在。因为Thread模型的困难不是来自于局部实现上的疥癣之痒，而是冯诺依曼模型所带来无法根治的顽疾。在冯诺依曼机统治计算机业的长达60多年,它带来的Education Wall使得专门多人特不是战斗在开发第一线的程序员们专门难想象有非冯诺依曼结构的存在。事实上令人更加难以想象的是，在冯诺依曼这位教皇统治现代计算机工业之前,绝大多数的电子计算机是并行计算的。有一个传讲流传甚广冯诺依曼制造了第一台计算机ENIAC。事实上冯诺依曼本人未曾参与ENIAC的制造,那篇奠定冯诺依曼机结构的101页报告也是

54、在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 op

55、erands was guaranteednot to occur”“这些机器的并行操作的能力使得程序编制极为复杂。这一事实让冯诺依曼更多的关注于顺序指令代码，企图以此来保证并行操作决可不能出现。” William Aspray 1990.冯诺依曼事实上不只一次地在阴沟里翻过船。相关于量子力学的可加性假设，反对Backus设计Fortran语言来讲，冯诺依曼综合症还算不上是一种失误。因为即便在我们那个软硬件高度发达的年代里,并行计算仍然是一个漂移的幽灵。能够想象,在那个电子管和打孔机的年代里,并行计算的难度可能是连这位能心算无穷级数的天才级数学大师都望而生畏的东西。然而不管如何，冯诺依曼的设计

56、的确为后世的计算机工业带上了一个难以解套的紧箍咒。今日许多天才程序员为之殚精竭虑的并行计算，事实上是一个特不幽默的问题如何在一台原本设计用来杜绝并行计算的机器上进行并行编程？由于冯诺依曼机在并行计算上的困难是本质性的，专门难在它之上做零碎的修改来完全治愈冯诺依曼综合症。我们迫切需要适合并行计算的计算机模型。计算机科学家们发觉,运算之间的时序性事实上只取决于运算之间结果依靠性。比如讲如此一个计算(2+3)*(4+6)。假设我们有两个CPU,显然两个加法能够同时进行.他们的开始执行时依靠于两个参数的输入时刻，乘法的开始执行时刻依靠于最后一个加法的完成时刻。这确实是传讲中的交叉引用。 Trustno

57、1 写道转贴一个评论,牛人确实是牛人. 引用本文: 转寄转贴删除修改回复作者:dragondevil人气:86 发信人: dragondevil(流星见龙在田), 信区: Algorithm 标 题: Re: 转载zz 关于两个世界体系的对话 -by Trustno1 发信站: 瀚海星云 (2008年08月23日13:26:20 星期六), 站内信件 WWWPOST 不错的文章。不超出基于Von带来的认识，就可不能发觉计算的本质，既不是函数也不是数据 结构，仅仅是数据流本身。Education wall，正是最令人担心的。注意到即便是CAM模型， 也只是是为Anti-Von有意反其道而行罢了，

58、仍然有查询，并不直接的实践数据流向的交换。 当实践了一组指令模块的输出向输入的任意调度，使这些模块持续工作，程序的功能就只剩 下约定哪个时钟沿将哪个模块的输出送到哪个模块的输入。这种方法要求严格精确的时刻约 定，必须在编译时进行指明，而不大可能实时产生（也不排除这种可能，只是我怀疑其功耗 和运算量），这就导致处理器外部导致的时刻不确定性无法解决，而使那个方法成为空谈。 相比设计一个能包容一定的时刻不确定性的以数据流调度为核心的指令阵列并行体系，专用 计算器ASIC的设计方式可称为入门级的训练（不幸的是哪怕那个入门级的训练也是目前人类 所掌握知识中较为匮乏的一种），因为其屏蔽了来自外部的任何不确

59、定性，并以固化接线实 现了数据流的转接。 数据流本身确实是计算。远离那些在一个操纵为核心的硬件体系上“虚拟”出的高级语言吧， 那只让你完全不记得什么是计算compute，什么是计算机computer。5个局长4个副局长1个办事 员的情况差不多够令人厌烦，更可恼的是实际上有20个办事员但因为局长们治理能力有限，总 是只有一两个正在工作而其他的统统休息却不停止消费他们的面包（不可能为了几个周期的 空闲而关闭功耗）。 让所有的办事员埋头工作，使传递员来提供输入、适时的取走输出并交给下一个办事员。这 确实是我所希望的体系。恩，对高性能计算而言，Von目前差不多只是个笑话。我明白那个家伙讲的确实是FPG

60、A,FGPA,FPGA 哈哈,全世界所有的语言都灵活，唯一不灵活的确实是硬件. reconfiguration computation,各个大学的大夫们差不多叫了N年了,惋惜确实是PC那个领域针插不进水泼不进.然而我相信,I记A记每年加内核的活计干不了多青年. PC那个地点,庙小妖风大,池浅王八多.Education wall让专门多人上了贼船就一辈子下不来了,怎么讲 terranhao 写道.冯.落衣慢是我们差不多的理论前提.是我们现在计算机工业的全然.看起来计算机工业只有PC一样. 引用数据流本身确实是计算。远离那些在一个操纵为核心的硬件体系上“虚拟”出的高级语言吧，这句话深得吾心,只只是