计算机基础知识讲义全Word格式文档下载.docx
《计算机基础知识讲义全Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《计算机基础知识讲义全Word格式文档下载.docx（18页珍藏版）》请在冰点文库上搜索。
catsample.txt|grep"
High"
|wc–l.cat将sample.txt的文件容包装成stdout,|管道符将stdout的容传给grep命令查询所有单词位High的行，查询的结果又被转化为stdout,再通过|管道符传送给wc命令进行行数统计。
微软最新的Shell取名为Monad,其言下之意恐怕无需赘述了.
不仅如此,IOMonad在结构化程序语言的最初演化的阶段也残留了一些踪迹.很多古老的Pascal程序，都保留了在程序首部书写InputOutpu参数的习惯.
program
fac_n（input,output）;
var
n:
integer;
functionfac（n:
integer）:
begin
ifn=1thenfac:
=1
elsefac:
=n*fac（n-1）;
end;
这就是把程序的主体看成IOMonad上的一个计算函数。
所有的Pascal函数可以通过操作系统的IO设施串联起来.当然随着程序语言往CPU中心化的演化,这些痕迹就逐渐消失了.
Monad仅仅是一个数学框架，并没有提供什么新的软件技术。
在Monad诞生之前，程序员们就已经在广泛的使用类似的软件设计方法。
但是这些设计方法本身却无法回答我们一系列的追问:
Exception,IO,Pipeline,为什么这些毫不相关的领域中都会出现相同的数学结构?
为什么在不同的领域呈现的Monad特性完全不同，有的多有的少有的甚至完全消失?
这些相同的结构的背后又预示着什么?
以及,我们为什么要问这么多为什么?
这些问题的答案对我们的编程实践又有什么意义?
（2）关于两个世界体系的对话
并行计算,是一群顽皮的孩童,充满着生机勃勃的活力，却又不失恶作剧式的顽皮。
他们仿佛是一座活跃的“火山”。
他们身上惊人的能量只有正确的引导下，才能完全的绽放出来而不致埋没；
他们身上顽皮的天性只有在严格的教导中，才不会变成脱缰的野马而无法驾驭。
正如儿童的教育首先需要深入他们的心世界，我们也必须深入并行计算的本质，去探究这些孩子心中的陌生而又神奇的世界。
在这群孩子们中间，并发是与我们最为的亲密也是最让我们头疼的一位。
如何对付并发?
目前存在两个截然对立的答案,ThreadModelVsEventDriven.对这两个模型，在编程实践的层面上我们都经过了严格的探讨，也有很多人通过各种途径去尝试调和其中的分歧。
但是Whichisabadidea?
是一个至今争论不休的问题。
我认为这不是仅靠分析他们各自优劣就能解决的问题，而是必须解释清楚为什么会产生这两种截然不同的方案。
知其然，必先知其所以然。
只有回到问题的源头，才能以更宽广的视野去选择道路。
在我们介绍IOMonad的部分时，曾经略带提过计算机体系结构决定了程序员以CPU为思考中心的习惯。
这个计算机模型，就是统治我们现在大多数计算机部构造的诺依曼模型。
在计算机中存在两种不同的流，一种称为控制流（ControlFlow）,另外一种则是数据流（DataFlow）。
计算机要进行工作必须要通过其中一种进行驱动。
•诺依曼机的核心工作方式是控制流（指令流）驱动。
即按照指令的执行序列，依次读取指令，然后根据指令所含的控制信息，调用数据进行处理。
•诺依曼机为了控制指令序列的执行顺序，设置一个程序（指令）计数器PC（ProgramCounter），让它存放当前指令所在的存储单元的地址。
如果程序现在是顺序执行的，每取出一条指令后PC容加l，指示下一条指令该从何处取得。
如果程序将转移到某处，就将转移的目标地址送入PC，以便按新地址读取后继指令。
ProgramCounter是一个递增的自然数。
我们知道，自然数集具有严格的顺序性,1<
2<
3,这种特性的集合在数学上被称为偏序集。
如果我们在两个偏序集中找到一个函数那么我们称f为保序的连续映射.
在诺依曼机中,正是通过时钟发生器与PC,PC与存地址之间的连续映射把CPU时间的顺序性映射到了代码的顺序性。
比如X86CPU大致就可以分为下面几个时钟周期.（FC为取指令周期,SC为源操作数周期,DC为目的操作数周期,EC执行周期,IC中断相应周期,DMA,DMA传送周期）
诺依曼机的数据流是由控制流驱动，比如X86Cpu中，数据是在CPU取指以后在SC周期读取的.这点在大多数人看来是不言自明无足轻重的。
但是他们却涉及到了传统编程语言中最为本质的问题。
Fortran之父JohnBackus在它图林奖领奖演说<
CanProgrammingBeLiberatedfromthevonNeumannStyle?
中,毫不讳言的道出了这一点:
引用
”VonNeumann
programminglanguagesusevariablestoimitatethecomputer'
sstoragecells;
controlstatementselaborateitsjumpandtestinstructions;
andassignmentstatementsimitateitsfetching,storing.……Theprimarystatementinthatworldistheassignmentstatementitself.Alltheotherstatementsofthelanguageexistinordertomakeitpossibletoperformacomputationthatmustbebasedonthisprimitiveconstruct:
theassignmentstatement.”
“诺依曼型的语言,使用变量来模仿计算机的存储单元;
控制语句来描述跳转和测试指令;
赋值语句模仿数据的获取，存储….这个世界最核心的语句就是赋值语句本身。
所有其它语句的存在，只是为了能使那些根植于赋值语句的计算结构可以正确地运行。
”
这回答了我们一个问题,为什么在传统语言中IO的行为是与Monad截然对立的?
赋值语句本身是一种CPU部的隐式IO操作。
因此传统IO函数与赋值语句是可复合的，它的确让我们的程序看上去自然舒适，而不像IOMonad那样别扭。
但是这种暂时的自然舒适，给我们带来了无尽的麻烦。
我们能够放心的让计算机运算1+1是因为有图林机和lambda演作为保障。
隐式的赋值语句将IO混入了计算后,会发生什么呢?
显然这是这两个模型无法回答，而又需要我们深入探究的问题。
作为结构化语言的发明人JohnBackus在同一片演说里，反复强调了对赋值语句所带来的困扰
”Moreover,theassignmentstatementsplitsprogrammingintotwoworlds.Thefirstworldcomprisestherightsidesofassignmentstatements.Thisisanorderlyworldofexpressions,aworldthathasusefulalgebraicproperties……Itistheworldinwhichmostusefulcomputationtakesplace.
Thesecondworldofconventionalprogramminglanguagesistheworldofstatements.…...Thisworldofstatementsisadisorderlyone,withfewusefulmathematicalproperties.Structuredprogrammingcanbeseenasamodestefforttointroducesomeorderintothischaoticworld,butitaccomplisheslittleinattackingthefundamentalproblemscreatedbytheword-at-a-timevonNeumannstyleofprogramming,withitsprimitiveuseofloops,subscripts,andbranchingflowofcontrol.”
更重要的是，赋值语句将程序割裂为两个世界。
第一个世界是赋值语句右边的世界。
这是一个有序的表达式世界，这个世界有许多有用的代数特性…….。
最有用的计算都发生在这里。
第二个世界是语句的世界，这是一个无序的世界，在那里找不到什么有用的数学特性。
结构化编程一定层度上为这个混乱的世界带来一些秩序，但是它那些原始的循环,子函数,分支流程技术从未击中过诺依曼型语言的本质问题---一次一条指令的控制流模式”
JohnBackus的演讲，已经过去31年了，他老人家也已经驾鹤西去。
相比于Backus的年代，我们在编程实践上已经有非常丰富的手段来应付这个混乱的世界，结构化，面向对象，面向方面,动态语言。
在这些方法看来，赋值语句与计算是等价的、同质的、混合使用是天经地义无需置疑的；
IO只是局部领域的专有问题（比如网络通信）而不是全局性的问题。
但是另一方面理论研究者们遵循JohnBackus观点,用数学理论构建IO世界的在秩序。
这些数学理论的推演告诉我们这样一个结果:
在诺依曼型语言中IO问题不是局部的而是全局性的。
IO具有并发性，而计算是非并发的，这两种操作需要分别处理。
当程序中引入越来越多的并行/并发背景的时候，JohnBackus的远见卓识就越显示出他深邃的洞察力。
并发占主流的程序里,IO的并发性意味着单台计算机面对的将不是唯一的时钟。
比如两台以TCP连接的服务器,他们时钟速度未必是等同的，即便是等同的我们也无法忽略时钟信号传递的延时。
当两个时序不一样的时钟共同驱动一份代码的时候，诺依曼机的根本性难题也随之而来。
诺依曼机的程序指令是按照CPU的时序顺序执行的，并发多任务程序也不例外。
偏序集的有一个特性叫做传递性,1<
2,2<
4,那么1<
4.这种传递性。
这使得自然数集的若干个子集的并集同样存在偏序性.在诺依曼机上,任何与顺序有关的问题，最为简易的方式就是依靠偏序的传递性,从底层自低向上地一级一级传递CPU的时钟序列。
ThreadModel模型之所以易于开发，也正是因为操作系统在底层控制了时间片的分配，使得每一个Thread的时钟序列和代码顺序保持一致。
换而言之ThreadModel是一个放大了的诺依曼机，要在这个模型中处理并发，我们必须面一个问题——时钟校准。
时钟校准恐怕是这个世界最本质的问题之一，它直接导致了上世纪最为诡异的理论——相对论的诞生。
从物理学上讲，信号传递是时钟校准的唯一办法。
在计算机中也不能例外，诺依曼机要校准不同的时钟序列，就必须解决如何获取外来信号的问题。
控制流驱动模式决定了诺依曼机不允许外界的信号直接驱动指令执行。
CPU只能通过本地时钟触发控制流，周期性发起状态查询。
CPU在某个周期向其他时钟源发送信号，在收到远端时钟的反馈信号后计算得出本地代码序列上的同步点,然后移动PC指针指向同步点。
无论是早期CPU的轮询模式还是现在广泛采用的中断方式，其基本的校准模式并没有改变,只不过查询对象由最初的IO设备演变为中断寄存器。
基于信号查询的校准方式，让诺依曼机在处理并发问题上就像是带着镣铐跳舞。
控制流驱动首先无可避免地导致了锁机制的产生。
JohnBackus告诉我们赋值语句其实是一种IO,它意味着赋值运算符两边数据的单向的数据流动。
但是诺依曼机的查询式时钟校准机制，必然意味着一次双向的数据流动。
如果以两条赋值指令来驱动一次双向数据交换，那么势必就要同步两条指令的先后执行顺序。
但是要同步指令的执行顺序，又必须先校准时序。
于是这里我们陷入了类似于相对论的逻辑困境。
两个惯性系中要校准时钟必须首先知道光速的传播速度，而要知道光速的传播速度必须首先校准时钟。
爱因斯坦为了避免这种逻辑无穷倒退，引入了速度不变的光信号。
类似地在诺依曼机下我们必须强迫一次双向的数据交换在一个指令中瞬时的完成,比如X86下的test&
set,exchange等等。
这些指令的使用就导致了Mutex,Semaphore,CriticalSection各种五花八门的锁结构。
随着锁机制的引入，锁竞争，死锁，粒度控制，各种并发性的麻烦滚滚而来。
然而我们的麻烦还远没有结束。
控制流驱动还会导致诺依曼综合症中的“MemoryWall”效应（另外两个效应是”EnergyWall“和“EducationWall“）。
因为每一次指令的执行都必须伴随着计算数据地址，状态地址，指令地址等等额外的数据流动开销。
随着指令数量的增加MemoryWall会越来越厚，最终会阻塞控制流的运行,使其而无法及时响应IO信号。
ContextSwitch就是最为著名的MemeoryWall.在外界的IO信号未到达之前，Thread必须不间断地定期执行信号查询代码。
每次查询完毕让出CPU后就要执行复杂的数据流动（比如Registersave/restore,Cacherefill等）。
为了避免这种开销,现在很多语言采用消耗更低的Greenthread的方案.这些方案可以一定程度上降低消耗但是无法完全根除。
在并发性达一定数量级后即便是Erlang这样的语言也无法忽视“MemoryWall”的存在。
因为Thread模型的困难不是来自于局部实现上的疥癣之痒，而是诺依曼模型所带来无法根治的顽疾。
在诺依曼机统治计算机业的长达60多年,它带来的EducationWall使得很多人特别是战斗在开发第一线的程序员们很难想象有非诺依曼结构的存在。
其实令人更加难以想象的是，在诺依曼这位教皇统治现代计算机工业之前,绝大多数的电子计算机是并行计算的。
有一个传说流传甚广——诺依曼制造了第一台计算机ENIAC。
其实诺依曼本人未曾参与ENIAC的制造,那篇奠定诺依曼机结构的101页报告也是在ENIAC运行了一年后才发表的，更重要的是ENIAC是一台并行计算机。
诺依曼对计算机的兴趣,来自于曼哈顿工程量的数值计算。
1944年诺依曼在火车站上偶遇了ENIAC总设计师戈尔斯坦后才参观了当时ENIAC的研制小组。
当时诺依曼发现，
“themachines'
abilitiesforparalleloperationsmadeprogrammingsignificantlymorecomplicated.Thistaughthimtofocusonsingle-instructioncodewhereparallelhandlingofoperandswasguaranteednottooccur”
“这些机器的并行操作的能力使得程序编制极为复杂。
这一事实让诺依曼更多的关注于顺序指令代码，企图以此来保证并行操作决不会出现。
”
<
JohnvonNeumannandtheOriginsofModernComputing>
WilliamAspray1990.
诺依曼其实不只一次地在阴沟里翻过船。
相对于量子力学的可加性假设，反对Backus设计Fortran语言来说，诺依曼综合症还算不上是一种失误。
因为即便在我们这个软硬件高度发达的年代里,并行计算仍然是一个飘荡的幽灵。
可以想象,在那个电子管和打孔机的年代里,并行计算的难度恐怕是连这位能心算无穷级数的天才级数学大师都望而生畏的东西。
但是无论如何，诺依曼的设计的确为后世的计算机工业带上了一个难以解套的紧箍咒。
今日无数天才程序员为之殚精竭虑的并行计算，其实是一个非常幽默的问题——如何在一台原本设计用来杜绝并行计算的机器上进行并行编程？
由于诺依曼机在并行计算上的困难是本质性的，很难在它之上做零碎的修改来彻底治愈诺依曼综合症。
我们迫切需要适合并行计算的计算机模型。
计算机科学家们发现,运算之间的时序性其实只取决于运算之间结果依赖性。
比如说这样一个计算（2+3）*（4+6）。
假设我们有两个CPU,显然两个加法可以同时进行.他们的开始执行时依赖于两个参数的输入时间，乘法的开始执行时间依赖于最后一个加法的完成时间。
这种计算机模型称为数据流机。
在这种计算机上，首先需要依靠编译器分析程序中的数据依赖性。
与诺依曼结构为每一个存单元表识一个变量名不同，编译器为每一个运算上的依赖节点标记一个唯一的Tag.比如上面这个运算,我们可以为所有的Input标记Tag（Input1….Input4）,为乘法运算所依赖的两个加法运算标记两个Tag（Add1,Add2）。
编译后的运算指令和Tag一起被合并到一种叫instructionstorage的包。
比如2+3就变成了（Input1,Input2,+,Add1）.当程序运行时这些数据包就会加载到一种叫做CAM的存中。
CAM（Content-addressablememory）与我们普通使用的线性编址随机访问的RAM（RandomAccessmemory）不同。
在RAM中我们给出一个地址，它返回这个地址的存储的dataword。
而CAM是给它一个dataword,它会搜索地址空间给出所有存储这个data-word的地址。
当一个instructionstorage的所有tag处于到达状态时比如（2,3,+,Add1），（4,6,+,Add2）,就会把运算数据和操作指令打包成instructiontoken交给运算单元进行并行运算.一旦运算完成,运算单元会将运算结果和输出Tag打成一个datatoken数据包发送给CAM.CAM就搜索所有依赖于此Tag的instructionstorage搜索出来，将对应的tag标记为到达状态比如（5,Add2,*,Output）。
在DataFlow机上整个计算过程由数据流驱动控制流。
每一个指令有一系列类似黑盒的InputOutput以及相关的运算操作组成。
程序的运算顺序依赖于数据的输入顺序，而不依赖于系统的时钟序列。
数据也不会像诺依曼机一样长久的存储于存单元当中，而变成在instructionstorage之间传递的数据消息。
这种模式在应对针对外部的并发信号时，程序无需进行毫无必要的轮询操作，而是在信号到达的即刻立即响应处理数据。
没有了控制流带来的Memorywall,也不需要引入锁机制。
那个阴魂不散的赋值运算符所带来的混乱也消失的无影无踪。
很多程序员在学习Monad模型时,对它那种抽象违反直觉的模型产生本能的反感，认为Monad只是一种纯粹为了形式化而形式化的奇技淫巧。
这种现象并不奇怪，正所谓不识庐山真面目，只缘身在此山中。
我们如果在诺依曼机的顺序执行的背景下去考察Monad,看到的势必是并发世界在顺序模型上的扭曲投影。
而在DataFlow模型下，Monad模型自然而然地回归到了并发形态。
我提到过一个IOMonad的例子
getline（）.DO
（X=>
X.ToUpper（）.IO（））.DO
putline（X））;
我们曾把Monad比作联邦快递，现在来看这个联邦快递所作的工作就是在快递数据。
每一个被Bind/>
=复合的函数都是一个可以并行计算的instructionstorage，而Bind/>
=则是描述了运算与运算之间的依赖性和数据流的走向。
IOMonad的各个部件在数据流驱动模型中一一对应必不可少的。
现在我们再回过头去关注一下UnixPipe和早期的Pascal程序,恐怕就不会对他们具有Monad结构而感到奇怪了。
Unix发明人DennisM.Ritchie在<
TheEvolutionoftheUnixTime-sharingSystem>
中说道:
“Ofcourse,thefundamentalideawasbynomeansnew;
thepipelineismerelyaspecificformofcoroutine.”
“当然，管道的基本概念没有什么新意;
它只是一种特别形式的协程”
Monad结构之所以会在PipeLine的层面上发扬光大,完全是因为pipeline所需要面对的是一群并发的进程。
在Ritchie的同一片文章里,我们还能看到早期Unix系统中地的并发性问题是依靠管道,消息队列等操作系统机制来完成的。
也就是说早期的Unix系统本身就是一个使用Monad结构来构造的并发系统。
传统程序语言只是设计用来编写这个并发系统上的非并发的顺序型代码。
随着技术的发展,当操作系统层面上的工具无法应付越来越复杂的并发问题时,我们才想起往传统编程语言中增加并发性的支持。
Monad模型在并发问题上展现出来的强大能力实非偶然。
整个DataFlow的计算过程类似一棵表达式展开树。
在更加复杂的例子中，比如引入递归的情况下,DataFlow就会形成一网或者说图。
在DataFlow诞生以来，计算机科学家们对DataFlow网结构特性进行了大量的研究。
比如ThomasHildebrandt在1998年工作，给出了一个基于tracedmonoidialcategory的模型.TarmoUustaluandVarmoVene,2005年在此基础上直接给出了一个
升级会员 