计算机是咋运行的：冯诺依曼结构

数组、链表这些结构限制条件的根本原因来自于 计算机硬件的体系结构。

在现今的计算机教育体系中，编程语言、数据结构（含算法）、计算机原理及体系结构几门课是计算机专业的本科生都要学习的。

实际上这几门课之间，也包括其他一些课程（例如编译原理、自动机、数电、模电、操作系统等等 ），有不少 overlap 的知识点和相互引用的地方，要从一个方向讲清楚某个知识点，就不得不涉及其他几个领域的知识。但是因为内容实在太多，不得已被分割为几门课程。

大学课程如此，我们这类入门性质的课程就要灵活得多，不必特意割裂知识间原本的联系，而是用到什么就讲什么。

今天这一章，虽然目标是说明数据结构受限的原因，但为了把它讲明白，我们先从计算机原理开始。

1. 电子计算机的前世今生

1.1 从人、算盘、到专用计算器

计算机对应的英文原词是 computer，这个词在英语里原本指从事数据计算的人——即使到了上世纪六七十年代，许多从事计算工作的人，仍然被称为 computer 。

下图是 1949 年，NASA 的人形计算机（human computers）：

由于计算任务的必要性和痛苦性，通过工具或者设备来代替人承担计算任务一直是人类的追求。从古老的算筹、算盘等简易工具，到计算尺、手摇计算机等机械工具，都是这种追求的体现。

到了 20 世纪前半叶，为了满足科学计算的需求，使用电子模拟器或液压机械的模拟计算机被发明出来。但它们都是用来进行特定问题计算的。

这类计算器，内置了固定用途的程序，形象点说，就是程序被“焊死”在了机器里，一旦机器造出来，程序就定了，既不能修改也不能删除。

现在某些特定类型的计算机依然维持这样的设计方式，通常是为了简化或教育目的。例如：便携式计算器，就内置了固定的数学计算程序。

1.2 通用计算机

20 世纪 30 至 40 年代，随着社会发展，人们对计算机性能和通用性的需求越来越强。

1936 年，英国数学家图灵提出了一种被称为图灵机（Turing machine）的抽象计算模型，用来模拟人们用纸笔进行数学运算的过程。

这一数学模型，从理论上证明了通用计算的可行，也因此成为了现代电子计算机的计算模型。

1937年，美国数学家香农发表了论文：《对继电器和开关电路中的符号分析》。

该论文标志着二进制电子电路设计和逻辑门应用的开始，为人们制造模拟图灵机的物理机器提供了基础元器件。

二十世纪 40 年代，欧美各国造出了一系列电子计算机，有 Z3，ABC，Colossus computer，Mark I 等。

电子数值积分计算机（Electronic Numerical Integrator And Computer，缩写 ENIAC）是其中的翘楚，它由美国陆军资助建造，是世界上第一台通用计算机。

ENIAC 由电路管线构成，通过编程来解决各种各样的计算问题。不过在 ENIAC 上编程可不是像现在编程这样，敲几个键盘就行了，而是要重新设计电路连接方式，并由一个人类小组进行重新配接线路才可以。

下图就是 ENIAC 的编程小组，在重构电路连接：

2. 冯·诺依曼结构

以约翰·冯·诺伊曼为代表的一批数学家、计算机科学家在使用 ENIAC 和 Mark I 等计算机时发现了存储的重要性。

1945 年 6 月 30 日，ENIAC 机密计划的安全官戈德斯坦发表了一篇由冯·诺伊曼撰写的 101 页报告，史称《EDVAC 报告书的第一份草案》。其中提出了“冯·诺伊曼结构（Von Neumann architecture）”这个术语。

冯·诺伊曼结构一种设计计算机的概念结构，具体见下图：

冯·诺依曼结构的要点主要包括：

1. 计算机硬件由运算器、控制器、存储器、输入设备和输出设备五大部分组成，其中运算器和控制器组成了中心处理单元（CPU）；
2. 指令——指令是单个的 CPU 操作，一款 CPU 能够进行哪些操作是在设计时就确定了的，和数据都以二进制编码；
3. 存储器中既存储数据又存储指令。

这一结构将存储设备与处理单元（运算器、控制器）分开，依此结构设计出的计算机又称存储程序型计算机。

存储程序型计算机改变了若要改变程序，就要改变计算机线路的情况。它将运算操作转化成一串程序指令，又将程序指令当成一种特别类型的数据和其他数据一起存储在存储器中。这样，一台存储程序型计算机就可以像变更数据一样改变程序了。

3. 存储空间的地址和内容

3.1 存储空间

存储器在逻辑上是一个空间，这个空间被叫做存储空间。

存储空间被分为若干存储单元，每个存储单元又分为两个部分：

• 地址：每个存储单元对应的序号，标识内容在存储空间中位置的编码；
• 内容：存储单元中存放的信息。

无论地址还是内容均以二进制的形式表示：

换言之，存储空间线性编址，按地址访问，存储在其中的每一条指令或数据，都是空间里存放的内容，它们都拥有自己的地址。

4. 类比仓库

我们可以将存储空间类比成一个仓库，里面有许多的货架，相当于一个个的存储单元，每个货架都有自己的编号（存储单元地址），货架上还会有相应的货物（存储单元的内容），就像下面这样：

当我们想要拿到其中某一个货物的时候，我们首先要知道该货物所在的货架编号，然后根据编号找到货架，从上面把货物取下来。比如：告诉我们去拿 001号货架上的货物，我们就去把小红盒拿下来就是了。

反之放置货物，就是将货物放到对应编号的货架上去。

总结一下：

• 在这些货架上的“货物”，可能是指令，也可能是数据；
• “拿货”就是读操作，而“放置”则对应写操作；
• 指令和数据一样可以被读、被写、被修改（用新“货物”替代旧“货物”）；变更指令或者数据，都只要修改存储空间内的内容就好了，无须变更硬件设置。

5. 一条指令是怎么被执行的？

计算机运行的过程，就是一条条执行指令的过程。

由运算器和控制器组成的 CPU，是计算机的“执行机构”。可以类比于我们人脑的神经中枢，“思维”专用。CPU 负责顺序执行程序的每一条指令。

每一条指令的执行过程，大致是这样的：

1. 取指令（Instruction Fetch，IF）：根据指令地址，从存储器里取出相应指令；
2. 指令解码（Instruction Decode，ID）：分析指令的操作类型（读/写操作，输入/输出操作，或者算术逻辑运算操作等）和获取操作数的方法；
3. 执行（Execute，EX）：完成指令功能（例如控制运算器对操作数进行运算），并控制数据在 CPU、存储器和输入/输出设备之间流动；
4. 写回（Writeback，WB）：将运算结果写入 CPU 或存储器。

一个完整的指令执行过程所需要的时间，称作一个指令周期。

在一条指令被执行完毕，结果数据写回之后，若无意外事件（如结果溢出等）发生，则计算机根据程序的控制结构（顺序结构、条件结构、循环结构）确定下一步要执行的指令，开始新一轮执行指令的循环。

6. 冯诺依曼结构的直观解释

我们打个形象的比于：冯诺依曼结构的计算机就像一家餐厅——

【1】 存储器相当于仓库：

仓库（存储空间）里的货架都有编号，货架上，要么放着食谱（指令），要么放着食材（数据）。

【2】 CPU 则相当于厨师（控制器）和炊具（运算器）：

【3】 执行一条指令的过程就像做一道菜：

1. 从仓库里拿食谱——取指令；

2. 阅读食谱，搞清楚要烹调的方式和要使用的食材——指令解码；

3. 根据食谱拿食材，并烹饪制作——执行；

4. 把做好的菜放回到货架上——回写。

这道菜做完，再去做下一道菜。

【4】 程序更新类似于换菜单：

假设，今天这顿饭总共做了两道菜：炒萝卜和烤鱼。

明天客人不想吃烤鱼了，想吃蒸鱼，那只要把仓库中“第1格“的食谱换成”蒸“就可以了，餐厅的所有硬件，包括厨师，都不会受影响，其他位置的食谱和食材也不会受影响。

这就是冯诺依曼结构的直观解释。

7. 冯诺依曼结构的应用

现代计算机，大部分都基于冯诺依曼结构。

下图是一台普通 PC 的硬件结构图，我们可以来看一下其中不同部件和冯诺伊曼结构的对应：

• 红框里的 CPU——运算器、控制器；
• 黄框里的内存条——存储器；
• 绿框里的键盘接口和显卡——输入设备和输出设备。

这是一个典型的冯诺依曼结构。

8. 冯·诺依曼结构的瓶颈

8.1 导致瓶颈的原因

冯·诺依曼结构在运行中会导致一个瓶颈，叫做冯·诺伊曼瓶颈（von Neumann bottleneck），其产生原因是现实当中不同计算机部件的客观性能：

• CPU 的处理速度特别快
• CPU 与存储器之间的数据传输速率与存储器的容量相比起来相当小

这个瓶颈的表现就是：CPU 的高效工作与低速的数据传输之间不平衡，CPU不得不在数据输入输出的时候闲置，因而严重影响了整体效率。

8.2 通过直观例子理解瓶颈

还用餐厅的例子来说明：

我们的 Hello Kitty 厨师是个超级快手，她的平底锅也是厨界神奇，任何食材无论煎炒烹炸全都能一秒钟完成：

偏偏负责给她拿食谱和食材的助手是个慢吞吞：

每次往返一趟厨房和仓库得半个小时，而且能拿的东西还特别少，每次只能拿 50g 以下的东西，食谱还可以一次拿完，要是拿食材，得往返个百八十回的。

这种情况下，Hello Kitty 只能整天闲着，慢吞吞先生却累得要死。这个问题会越来越严重，而餐厅的整体运行效率则受限于慢吞吞先生的工作效率。

8.3 缓解瓶颈的办法

针对冯诺依曼瓶颈，人们想了很多办法来缓解它，这些法子包括：

• 在 CPU 与存储器之间加入高速缓存;
• 采用分支预测（branch prediction）算法;
• 通过编程方式的改变（现代的函数式编程以及面向对象编程），在宏观上减少将大量数值从存储器搬入搬出的操作；
• 等等

这些方法的确大幅缓解了瓶颈问题。

9. 哈佛结构

上面我们提到了一台和 ENIAC 同时期的电子计算机 Mark I，它虽然不如 ENIAC 那样通用，却是美国第一部大尺度自动数位电脑，由 IBM 制造出来之后被哈佛大学接管。

它将指令和数据区别对待，将它们分开存储，这种结构被称为 “哈佛结构（Harvard architecture）”。

因为指令和数据分别放在不同的存储器中，可以在同时读取两者，因此哈佛结构相对冯·诺依曼结构，效率会更高。

但是这种高效的代价很大：

• 哈佛结构比冯诺依曼结构要复杂得多；
• 在动态加载程序时，哈佛结构需要先将静态程序代码作为数据读入数据存储器，再将其传输到指令存储器中去——这样既增加了存储负担又增加了传输负担，还使得过程非常复杂。

过高的复杂度限制了哈佛结构的推广。

现在，我们日常使用的计算机，在整体体系结构上基本上都采用冯诺依曼结构。不过许多 CPU 内核，会采取类哈佛结构的设计，在 CPU 内的缓存中区分指令缓存和数据缓存。这也可以说是在现实应用中冯诺依曼结构和哈佛结构的一种折中。

欢迎关注我公众号：AI悦创，有更多更好玩的等你发现！

公众号：AI悦创【二维码】