计算机科学速成课

1 计算机早期历史

1.1 计算机的重要性

计算机是当今世界的命脉，如果突然关掉所有计算机，那么世界将会直接乱套。我们生活中很多产品也都是依靠计算机生产出来的。所以说，计算机改变了我们生活几乎所有方面，计算机对我们社会的重要性不言而喻。

1.2 计算机的发展

略。。。

2 电子计算机

上节提到，用于特定场景的计算设备，如制表机，大大提高了企业和政府的工作效率。但是随着社会的发展，交通运输、科学研究甚至航空航天等发展，人民需要计算能力更强的机器。这种计算能力更强的机器，往往体积巨大，耗电量巨大，这为后面的创新埋下伏笔。

2.1 传统大型计算机的缺点

传统计算机主要有两个缺点

• 运算速度慢，进行普通的加减乘除的耗时都很长；
• 齿轮等计算机机械组件磨损，导致早期计算机容易出现Bug。

最大的机电计算机是哈佛马克一号，由IBM公司完成，它由着数十万组件、上百万连接点和几百英里的导线，这台机器最早是用于给“曼哈顿计划”跑模拟。这台机器的大脑是继电器。

什么是继电器

继电器是用电控制的机械开关。继电器有根“控制线路”，控制电路是开还是关。当螺线圈通过电时，其会产生磁场，吸引上面的线闭合，达到连通的目的。这个继电器可以用于机器进行控制。

糟糕的是，继电器开关有一定质量，这会影响其闭合。其一秒能够闭合50次，导致计算机的运算非常慢（完成一次加减乘除需要几秒钟）。

除了速度慢，另一个限制是齿轮磨损。随着机器的不断运行，器件的磨损不可避免。哈佛马克一号有上千的继电器，任何一个发生故障，就会导致计算出错。

此外，黑色的温暖的环境，也会使虫子滋生。虫子，英文命Bug。虫子附着在大型计算机的组件上，会导致其运行出错。那么，机器故障（Bug）的来源也是此。

2.2 电子管

显然，未来要想继续制造出更强大的计算机，就必须用其他东西代替继电器。幸运的是，一个新的电子组件出现了——“热电子管”。这种电子管只能运行电流单向运动，当电流反向时，电子管不能发光。这种管叫“二极管”。

但是，要怎么利用电子管进行开关控制呢？答案就是——真空三极管

聪明的人民在二极管中添加了一根导线。利用这跟导线，可以控制向电子添加正电荷或者负电荷，来控制电流的流通。

三极管和继电器有着相同的功能，但是由于没有部件的物理移动，所以它的磨损很少，开闭速度可以达到上千次每秒。这种真空三极管，在电子设备中大量运用，持续了近半个世纪。

刚开始时，这种三极管造价昂贵，而且一个计算机需要上千个电气开关。不过随着时间推移，一些政府部门可以承担这种价格，这种三极管开始应用计算机。标志着计算机从机电转向电子。

2.3 电子计算机

世界上第一台电子计算机造成于英国，名叫“巨人一号”，它有1600个真空管。最初是英国政府用来破解纳粹的通信加密密码的。巨人，被认为是第一个可编程的计算机。

世界上第一个真正的通用的可编程计算机，是ENIAC。不过由于真空管很多，它几乎半天就会出现一次故障。

2.4 晶体管

为了降低成本和大小，同时提高可靠性和速度，我们需要一种新的电子开关。1947年，贝尔实验室发明了晶体管（晶体三极管）。一个全新的计算机时代来临了。

晶体管的物理性特别复杂，涉及到量子力学。简单地来说，晶体管的制造需要半导体材料，通过控制基极电荷，控于控制半导体材料的导电性，来是否允许电流的流动。

晶体管具有很好的开关速度，且其为固态的，比起易碎的玻璃电子管。其体积也远小于继电器或者真空管。这样我们就能制造出更小更便宜的计算机。

如今，晶体管小至几十纳米，运算次数达到几十上百万，并且有几十年的寿命。

3 布尔逻辑和逻辑门

3.1 什么是二进制

前文我们提到，计算机最早是机电设备，一般用十进制计数，比如用齿轮数代表十进制，再到晶体管计算机。

幸运的是，只用开关两种状态也可以代表信息。这种叫做二进制，意思是用两种状态表示。

你可能认为只用两种状态能表示的信息不多，不过这对计算机来说有很多好处。对于电子元件：电路闭合，有电流通过，代表真；电路断开，无电流通过，代表假。二进制也可以写成0和1。

3.2 为什么使用二进制？

• 二进制表示的状态相对于其他进制更容易区分。
• 二进制已经有一个专门研究的数学分支——布尔代数，在此方面已经有较大的发展了。

当初，一些早期的计算机是三进制的，甚至是五进制的。问题是状态越多，越难区分不同的状态，信号可能会发生交叠。所以，我们用信号的开和闭，尽可能地减少这种问题。

另一个使用二进制的原因，就是有一整个数学分支，专门处理“真”和“假”。它已经解决了所有法则和符号问题，这个数学分支叫“布尔代数”。

3.3 布尔代数及基本逻辑门单元

布尔代数的基本单元不是数学中的数字，而是非（NOT），与（AND）、或（OR）和异或（XOR）等。那么这几种符号的作用，学数字电路中已经接触很多了。下面简单这几种逻辑门介绍：

非（NOT）：输出与输入相反，输入真，输出假，反之亦然。
与（AND）：两个输入仅同真输出真，若有一假则为假。
或（OR）：两个输入只要有一个是真，则输入为真。
异或（XOR）：两输入相异则输出真，两输入相同则输出假。

不过，设计师在设计电路和芯片时，不需要考虑这些晶体管是如何设计或电子是怎么流过半导体的。他们需要考虑的是抽象层次的东西，很少在晶体管层次考虑，而是考虑逻辑门或者更大的组件。

4 二进制

4.1 二进制的数字表示

要想表示更多的信息，就要增加数字表示的位数，类似十进制那样。多位数字，如“263”，就能表示比10更大的数。这种逢十进一的数字表示方法，就是十进制（基于十的表示法）。

二进制也一样，它是基于2的表示法，其只有两个数字，0和1。多位二进制表示法，应该按权值展开，如下图所示：

4.2 二进制的加法

二进制的加法和十进制一样，满足条件则进一。如下图的二进制加法。

4.3 字节

二进制中，一个1或0叫做一位，即一个位(bit)有两个不同状态0和1，8位叫做一个字节。即1字节=8位。我们的32为或64位电脑，指的是一次能进行32位的或64位的同时计算。

除了字节外，还有KB、MB和TB等，转化关系如下表所示。

4.4 计算机中的正负表示

计算机中，大多用第一位表示正负，1是负，0是正。

后面，我们还会讲到，计算机会给内存中的每一个位置，做一个标记，这个标记叫位址，目的是为了方便存取数据。因为现在的数据量越来越大，内存地址也有64位。

4.5 计算机中的浮点数

我们有几种方法表示浮点数，最常用的是IEEE 754标准。它用类似科学计数法的方法，来存十进制数。对于32位浮点数，第一位表示正负，后面8位表示指数，最后23位表示有效数。

例如，$625.9 = 0.6259*10^3$，其中，$6259$为有效位数，$3$是指数，其在计算机中的表示如下图。

4.6 ASCII-计算机中的文字表示

不同于书面用符号来表示文字信息，计算机中用数字表示文字。一种方法是，用1表示A，2表示B，3表示C，以此类推。美国科学家曾用5位来表示字母，因为$2^5$为32，这对26个字母来说够了，但这不能表示标点符号、数字和大小写字母。

ASCII，美国信息交换标准代码，发明于1963年，ASCII码是7位代码，足够存储128个不同的值。扩展范围后，足够表示大小写字母、数字和标点符号等。

因为ASCII码值发明地较早，所以被广泛使用，这样，可以让不同公司制作的计算机，能够交换数据。这种交换信息的能力叫互用性。我们知道一个字节有8位，在值为128以后的数字，可以由各国自己根据情况使用。在美国，这些额外的数字主要用于编码附加符号，比如数字符号，图形元素和常用的重音字符，而在希腊，则用于表示希腊字母等。

4.7 Unicode-解决不同标准编码下的乱码问题

不过虽然ASCII码已经能很好地应用于计算机了，但是对于亚洲一些国家（如中国和日本），他们有着上千的文字，ASCII码显然不够用。此外，各个国家设置了相应的字符编码表，但是互不兼容。字码不兼容的问题经常出现，以致于出现一个专门形容这种情况的名词，“mojibake”，意为“乱码”。

所以，Unicode诞生了，统一了所有的编码标准，设计于1992年，解决了不同国家不同标准的问题，Unicode用一个统一的编码。最常见的Unicode是16位的，有超过一百万个位置，这对所有语言的字符都够用了，能很好地解决字符不兼容导致乱码的问题。

对于其他格式的信息如MP3或GIF，就像ASCII用二进制表示字母一样，我们用二进制编码声音/颜色，表示照片，电影和音乐。

最后，我们要知道，对于计算机，网页、短信、视频甚至操作系统，都是一长串01字符。

5 算术逻辑单元

5.1 什么是ALU

上一节课我们提到如何用二进制表示数据，如010表示2等。我们知道，表示和存储数据是计算机的重要功能。但真正的目标是计算处理有意义的数据，这些操作由计算机的“算术逻辑单元”处理，简称ALU。

ALU是计算机的数学大脑，理解了ALU的设计和功能后，你就理解了现代计算机的基石。ALU就是计算机中负责运算的组件，基本上其他组件都需要用到它。

最著名的ALU，就是英特尔的74181，1970年发布，是第一个封装在单个芯片内的完整ALU。

接下来，我们将利用我们之前学过的逻辑门，设计一个功能与74181相同的组件，然后甚至用此设计CPU。

5.2 ALU单元之一：算术单元

ALU有两个单元，1个算术单元，1个逻辑单元。

5.2.1 什么是算术单元

算术单元负责计算机里的所有数字操作，比如加减法，或者给某个数+1（这个叫增量运算），不过今天我们重点要理解的是加法运算。

设计时，我们不在晶体管层次出发，而是用更高层的抽象——逻辑门。我们需要用到AND，OR，NOT和XOR逻辑门。

5.2.2 半加器

对于二进制加法，1+0=1，0+1=1，0+0=0，1+1=10。如下图：

我们只看前三个和第四个的第一位，发现它和异或（XOR）操作一样。不过对于1+1，我们还需要一个进位，这里就用到了与操作（AND）。设计如下：

它只能处理一位计算，我们称为半加器。我们也可以将其封装起来，变成只有输入和输出的“黑盒操作”，如下图：

5.2.3 全加器

如果想要处理超过1+1的运算，我们需要“全加器”。半加器输出了进位，着意味着，我们处理时，还需要将进位考虑进去，才能设计全加器。

全加器要考虑三位数字的和，如下图所示。全加器有三输入（这里是ABC），两输出（进位和总和）。

我们可以用半加器进行A+B，再把C输入到第二个半加器上，然后用一个或门（OR）计算进位，最终我们得到全加器。设计如下：

我们一样可以将全加器封装起来，这样只能看到输入（ABC）和输出（SUM总和，CARRY进位），方便我们进行更高层次的设计。

5.2.4 8位加法器设计

有了全加器，我们可以进行多位加法器设计。这主要是利用半加器和全加器进行，刚开始因为没有高位的进位，我们使用半加器，接下来我们全部使用全加器，因为需要考虑进位。如下图：

因为是一个进位一个进位地往下输入的，所以叫“8位行波进位加法器”，当然，最后一位可能会发生进位，表示相加的两个数字和太大了，超过了8位，这叫做“溢出”。这会导致错误和不可预测的结果。

我们可以用更多的全加器，可以操作16位或32位数字，让溢出更难发生。不过代价是更多的逻辑门和更多的耗时。所以，现代电路用的加法器不同，叫“超前进位加法器”。

简单的ALU单元可以进行多种加减操作，如半加、全加、减法、增1等，但是没有乘除操作。这是因为，简单的ALU没有专门的电路来处理，而是把乘法用多次加法来实现。不过对于强大的手机和电脑，有专门的乘法处理电路。没有多困难，只是逻辑门更多，造价更昂贵而已。

5.3 ALU单元之二：逻辑单元

现在，我们讲ALU的另一部分，逻辑单元。逻辑单元执行逻辑操作，比如之前的AND，OR和NOT等操作。它也能做一些简单的判断，比如结果是不是0，是否为负数等。

例如下图就是检查ALU输出是不是0的电路，很简单，多个或操作，然后最后取反便可，因为只有输出位数全为0，结果才为0。

前面我们讲的英特尔公司发明的74181，不过只能处理4位输入，也就是说，我们做了一个比英特尔74181还好的ALU！！

5.4 ALU

74181用了大概70个逻辑门，但不能执行乘法操作。但它向小型化迈出了一大步，可以让计算机更强大更便宜。ALU需要大量的逻辑，我们用一个符号来代替，它看起来像一个大“V”，如下图所示。

ALU有两个8位的输入，然后用一个操作代码来控制其是加法还是减法操作，操作代码告诉ALU进行什么操作。

ALU的输出是8位的，ALU还输出一堆标志（Flag）。一些操作介绍如下：

• ZERO：若ALU输出是0，那么ZERO标志就变成1。
• NEGATIVE：我们可以用ALU做减法，然后用NEGATIVE判断其是不是小于0，从而进行比较大小。
• OVERFLOW：ALU还有溢出单元，判断有没有进位。

ALU有很多Flag，这三个是最常用的。

6 寄存器与内存

上节课，我们用逻辑门做了一个简单的ALU，它能执行算术运算（Arithmetic）和逻辑运算（Logic），ALU里的A和L因此得名。当然，算出来后将结果扔掉的话那就没什么意义了，得找个办法存起来，这就需要用到计算机的内存了。

6.1 计算机中的存储器

当我们正在使用电脑时，比如打游戏、看视频，如果突然断开电源，进度将会中断且不难复原。我们会损失数据的原因是，电脑使用的是“随机存取存储器”，简称“RAM”。它只能在有电的情况下存储东西。

另一种存储叫持久存储，关掉电脑数据也不好丢失。

本节课，我们将从简单开始，做出存储1的器件，之后再扩大，做出我们的内存模块。下次再和ALU结合，做出CPU。

6.2 存储器的原理与制作

6.2.1 存0电路与存1电路

(1) 存1电路

至今，我们所说的电路都是单向的，总是向前流动，但是我们也可以把输出连回输入。如下图所示的连法，当输出是1后，无论输入是0还是1，因为将输出连回了输入，最终的输出都是1。那么，这个电路元件就可以存储1。然而问题是，无论怎么试，都没法将1变回0。

(2) 存0电路

那么，我们来看看将这个电路里的OR门换成AND门会怎么样，如图。当输出是0后，无论再对A输入0还是1，输出都是0，就是说，这个电路了可以存储0。这里就不绘制动态分析过程了，可参照存0电路。

6.2.2 锁存器与门所

(1) 锁存器

现在，我们用了存1存储器和存0存储器了，我们将其都利用起来，如下图，这个叫做“AND-OR锁存器”。它有两个输入，“设置”输入，把输出变成1，“复位”输入把输出变成“0”。如果“设置”和“复位”都是0，电路会输出最后放入的内容。这就是说它存住了一位的信息，这叫“锁存”，因为他锁住了一个值。

• 若SET=1,RESET=0，则输出为1；
• 若SET=0,RESET=1，则输出为0；
• 若SET=0,RESET=0，则输出不变，也即会保存上一个状态的输出，也即它锁住了1位的信息（存储）；
• 若SET=1,RESET=1，则输出为0，个人认为这种操作没有什么太大的意义；

放入数据的操作叫“写入”，拿出数据的操作叫读取。

(2) 门锁

麻烦的是，用两条线“设置”和 “复位”来输入，有点难理解。为了更容易用，我们希望只有一条输入线，进行输入数据。然后设置另一条线，叫允许写入线，用来启用内存，启用时允许写入，没启用时就锁定。外加一些逻辑门，就可以做出这个电路。这个叫门锁，因为门可以打开和关上。

其中，DATA INPUT表示输入要保存的数据；WRITE ENABLE表示允许写入线，此线输入1时为启用(允许写入数据)，此线输入为0时为锁定(存储数据，此时不论DATA INPUT如何变输出都不变)。

但是，我们不想直接面对这个电路，我们想用一个“黑盒”将其框住，这就成为了一个组件。这个门锁只有当“允许写入线”为1时才可以写入和输出数据。

6.2.3 寄存器

虽然一个门锁只能存储一位数字，但是我们并排放8个锁存器，就可以存8位信息。

一组这样的锁存器叫“寄存器”，寄存器能存储一个数字，这个数字有多少位，叫位宽。

早期计算机用8位寄存器，后来到16位、32位和如今的64位。

写入寄存器时，我们需要先将所有的“允许写入线”设为1，这里我们可以引一条总线统一控制。然后我们将数据输入，完成输入后再将所有的“允许写入线”设为0。

6.2.4 矩阵网络优化门锁放置

如果只有很少的位(bits)，把锁存器并排放置，也勉强够用了。64 位寄存器要 64 根数据线，64 根连到输出端，幸运的是，我们只要1根线(“总线”)启用所有锁存器，但加起来也有 129 条线了。如果存 256 位要 513 条线！非常耗材。

解决方法就是矩阵，在计算机中，寄存器并不并排放，而是成矩阵网络。存256位的寄存器，就将门锁摆成16*16形式，要用某个寄存器，就打开想应的行线和列线。

要启用某个锁存器，就打开相应的行线和列线，放大看看怎么做的。

我们只想打开交叉处锁存器的”允许写入线”，所有其他锁存器，保持关闭。我们可以用 AND 门！只有行线和列线均为1，AND门才输出 1。所以可以用选择单个锁存器，这种行/列排列法，用一根“允许写入线(总线)”连所有锁存器。

为了让锁存器变成“允许写入”，行线，列线和“允许写入线”都必须是 1，每次只有行列号对应的那1个锁存器会这样。同时，有了这种电路连接结构，使得我们可以只用一根”数据线”(类似于允许写入线的总线)连所有锁存器来传数据，因为只有一个锁存器会启用，只有那个会存数据。其他锁存器会忽略数据线上的值，因为没有“允许写入”。

我们可以用类似的技巧，做“允许读取线(READ ENABLE)”来读数据。

所以对于 256 位的存储只要 35 条线，具体计算如下：

不过，我们怎么将计算机的二进制数据传给这个“矩阵”呢？因此，我们需要用到多路复用器，它能够连通所给输入对应的线，比如若输入“1010”，那么多路复用器就会将第10路连通，达到选线路的目标。

那么，更高的一层抽象来了，256位内存，如下。其分别有上文提到的8位地址线、数据线、允许写入线和允许读取线：

这样，我们就做成了一个内存了。

6.3 如何利用多个内存完成数据存取

利用这个256位的内存，我们可以存许多数据。具体的存法如下：

我们将8个256位的内存并排在一起，用同样地址线将其连接。那么，一个内存可以存一位（单独），8个并在一起就可以同时存8位（1Byte）。为了存8位的数据，我们给8个内存同样的地址，也就是一个8位数据，分给8个内存分别存储。因为是256位的内存，所以可以存256个八位，也就是256 Byte的数据。

我们将其抽象，也就是说，这8给内存，可以有256有地址，每个地址可以读写一个8位数据。

内存的一个重要特征是可以随时访问任何位置，因此叫“随机存取存储器”（RAM），RAM就像人类的短期记忆，记录计算机当时正在干嘛。

上面真实的内存条中，有8颗芯片，每个芯片有32个内存方块，每个内存方块4个矩阵，所以1个方格有8192×4=32768位，总之，总位数约为：

所以，这节课，我们做了一个SRAM（静态随机存取存储器），还有其他比如DRAM、闪存等等，他们在功能上与SRAM相似，但用不同的电路存单个位，比如用不同的逻辑门、电容器、电荷捕获或忆阻器等等。但根本上，这些技术都是矩阵层次嵌套，来存储大量信息。

就像计算机中的很多事情，底层其实都很简单。让人难以理解的是一层层精妙的抽象，像一个越来越小的俄罗斯套娃。

7 中央处理器CPU

7.1 CPU与指令

前面课程已经提到，我们已经做了一个算术逻辑单元（ALU），输入二进制，它会执行计算。我们还做了两种内存：寄存器，很小的内存，能存一个值；RAM，能在不同地址存大量数字。现在，我们是时候把他们放在一起，组建计算机的“心脏”了，这个“心脏”叫“中央处理单元”，简称CPU。

CPU负责执行程序，这些程序可能是浏览器、社交软件和音乐等等。这些程序是由一个个操作组成的，这种“操作”叫“指令”，因为它“指示”计算机要做什么。如果是计算指令如加或者减，CPU会让ALU进行数学运算。也可能是内存指令，CPU会和内存通信，然后读/写值。

当我们用一条线连接两个组件时，这条线只是所有必须线路的一个抽象，这种高层次视角叫”微体系架构“。意思就是，我们从微观部件考虑整体同类型部件，以更高抽象层次去看代问题。

7.2 CPU指令体系

我们已经知道数据是以二进制值存在内存里，程序也可以存在内存里。我们可以给CPU 支持的所有指令，分配一个 ID，下图为计算机指令表。下表中，我们看到，前四位存储指令的”操作代码“，如0010、0001等，后面四位代表数据来源于哪里（地址或者寄存器）

我们还需要两个寄存器来完成CPU指令，一个寄存器追踪程序运行到哪了，我们叫它”指令地址寄存器“，顾名思义，存当前指令的内存地址。另一个寄存器存当前指令，叫”指令寄存器“。指令体系如下：

7.3 指令的运行流程

一条指令的运行，有三个阶段，分别是取指令阶段、解码和执行。这里，我们会在RAM里放一个程序，过一遍流程。

CPU的第一个阶段叫”取指令阶段“。指令地址寄存器连接到RAM，RAM得到指令地址寄存器的内容，将对应地址的数据传到指令寄存器中，下图中显示的是”0010 1110“。

然后是解码，根据前文的指令表，知道0010是LOAD_A指令。后四位是RAM的地址（如表），1110是14，那么我们就取得RAM中地址是14的值3。这是一个LOAD_A指令，会将这个值放入A寄存器中，而其他寄存器不受影响。

最后是执行，通过检验电路和输入运行线开关，就将3写入了寄存器A中。执行完后，指令地址寄存器地址+1，进行下一个指令。

当然，每一个指令都会有对应的逻辑电路来判断其是否要进行。这些控制单元可能非常复杂，我们将其抽象一层，以一个整体部件（控制单元Control Unit）代替。

这个控制单元就行交响乐的指挥使，控制CPU的所有组件。”取指令-解码-执行“完成后，我们可以再来一次其他指令，从”取指令开始“。上面介绍的指令只涉及到寄存器的存取，其他指令如ADD，会用到ALU部件。利用ALU将值计算出来后，再传回对应的寄存器中。也就是说，寄存器加ALU，就可以做成CPU。

7.4 CPU的节奏把控者——时钟

我们刚才走的是一个人工的流程，但是计算机中没有”人工“，所以计算机中靠的是时钟来负责管理CPU的节奏。时钟以精确的时间间隔，触发电信号。控制单元会用这个信号，推进CPU的内部操作，确保一切按节奏进行。

时间间隔不能太短，因为电信号的传输也需要一定的时间。**CPU进行“取指令-解码-执行”的速度叫“时钟速度”，单位是Hz，1Hz表示一秒一个周期。

第一个单芯片CPU是“英特尔4004”，1971年发布的4位CPU，它的微架构很像我们之前所说的CPU。虽然是第一个小型CPU，但他的时钟速度达到740千赫兹——每秒740万个周期。

• 超频
  你可能听过有人会把计算机超频，意思是修改时钟速度，加快CPU的速度，就像罗马帆船要撞另一艘船时，鼓手会加快敲鼓速度。芯片制造商经常给CPU留一点余地，可以接受一点超频！但超频大多会让CPU过热或产生乱码，因为信号跟不上时钟。

• 降频
  你可能很少听说降频，但降频其实很有用，有时没必要让处理器全速运行(例如，可能用户走开了，或者在跑一个性能要求较低的程序)。把 CPU 的速度降下来，可以省很多电，省电对用电池的设备很重要，比如笔记本和手机

• 动态调频
  很多现代处理器可以按需求，加快或者减慢时钟速度，这叫“动态调整频率”，加上时钟后，CPU才完整，这样我们又提升了一层抽象。CPU和RAM独立，两者用地址线、数据线和允许读写线进行通信。

7.5 小小结

加上时钟后，CPU才是完整的，现在可以放到盒子里，抽象成一个独立组件。

8 指令和程序

8.1 更加丰富的指令系统

上节课中，我们把ALU，控制单元，RAM和时钟结合在一起，做了一个基本但可用的“中央处理单元”，简称CPU，它是计算机的核心。这次，我们给CPU一些指令来运行。

CPU之所以强大，是因为它是可编程的，如果写入不同指令，就会执行不同任务。所以，CPU是一块硬件，可以被软件控制。在上节课的指令系统中，我们只有4条语句，这节课我们会增加几条指令，如下

1. SUB：与ADD一样，操作两个寄存器相减，放在第二个寄存器上。
2. JUMP：让程序跳转到新位置，如果想改变一些指令或者跳过一下指令，这个很有用。JUMP的底层实现方式是，把需要的指令后四位代表的内存地址的值覆盖掉“指令地址寄存器”里的值。
3. JUMP_NEG：它只在ALU的“负数标志”为真时（即此时计算结果为负数），进行JUMP。
4. HALT：计算机和程序停下来。

值得一提的是，指令和数据都是存在同一个内存里面的，他们在根本上毫无区别，都是二进制数。

利用更多的指令，我们可以使CPU的程序更加丰富。

8.2 无限循环与条件指令

当指令顺序出现问题时，程序可能进入无限循环，这个程序会永远跑下去。所以，我们需要更多其它类型的JUMP以满足我们的需要，这样只在特定条件下才会发生，程序不会出现无限循环。前面提到的JUMP_NEG就是，此外还有 JUMP_IF_EQUAL（如果相等）、JUMP_IF_GREATER（如果更大）等等。这些指令，同样使我们的CPU程序更加丰富。

软件还可以让我们做到硬件做不到的事，ALU没有除法功能，是程序给了这个功能。别的程序也可以用我们的除法程序，来做其他事情。

8.3 指令长度

我们这里假设的CPU很基础，所有指令都是8位，操作码只占了前四位，即便用尽4位，也只能代表16个指令。同时，因为4位最大为16，说明我们最多可以操纵16个地址，这非常少。

因此现代计算机用两种办法来解释此，① 最直接的方法是用更多位来代表指令，比如32位或者64位，这叫做指令长度。② 第二个策略是“可变指令长度”，举例，比如某个CPU用8位长度的操作码，看到HALT指令，HALT不需要额外的数据，那么会立马执行。如何看到JUMP，它得知道位置值，这个值在JUMP后面，这叫做“立即值”。这样设计，指令可以是任意长度。

8.4 现代计算机的指令系统

上面都是假设的例子，现在讲一个真实的例子。1971年，英特尔发明的4004处理器，这是第一次把CPU做成芯片，它支持46个指令，包括JUMP、ADD等。CPU发展到现在，功能越来越强大。比如，英特尔的酷睿i7，有上千个指令和指令变种，长度从1到15字节。

9 高级CPU设计

9.1 早期CPU提速方式

随着本系列的进展，我们知道计算机进步巨大，从1秒一次运算，到现在有千hz甚至兆hz的CPU。

9.1.1 减少晶体管切换时间

早期计算机的提速方式是，减少晶体管的切换时间。晶体管组成了逻辑门，ALU以及前几集的其他组件，但这种提速方式终究会遇到困难。所以厂商和科学家们发明各种新的技术来提高性能。

9.1.2 利用复杂电路设计除法

上节课我们做了一个CPU除法法器，不断减去同一个数，直到小于等于0才停下。但这种方法需要多个时钟，很低效。所以现代CPU直接在硬件层面上设计了除法，可以直接给ALU除法指令。虽然这让CPU更大更复杂，但也让运行速度更快。

9.2 缓存——解决CPU与RAM传输问题

现代计算机几千兆的时钟速度，带来了另一个问题，如何传递数据给CPU？这时，RAM成了一大阻力，RAM是CPU之外的独立组件，意味着数据要用线来传递，叫总线(BUS)。虽然电信号可以以光速快速快速传输，但是很小的延迟也会造成问题，RAM还需要时间找地址、取数据、配置和输出数据，这样会占用太多时间。

解决延迟的方法之一是，给CPU加一点RAM，叫缓存(CACHE)。

因为处理器空间不大，所以缓存一般只有几KB或MB。缓存提高了运行速度，CPU从RAM拿数据时，RAM不用传一个，可以传一批。这很实用，因为数据常常是一个一个按顺序处理的，将要处理的数据提前传入缓存，可以大大提升CPU运行速度。因为缓存离CPU近，传输时间大大降低，这比直接反复去RAM拿数据快得多。

注意：这里的近就是指物理上的近，RAM与CPU通信的总线BUS物理长度可能1cm，但是CACHE与CPU通信的物理距离可能只有0.01cm。

如果想要的数据已经在缓存中，叫“缓存命中”，否则叫缓存未命中。缓存可以当临时空间，存一些中间值，适合长\复杂的运算。

计算完后的值要想存储，不会直接存入RAM，而是存入缓存中。因此，缓存里的数据要对RAM里的数据进行更新，缓存里每块空间，有一个特殊标记，叫“脏位”。

同步缓存与RAM的数据一般是当缓存满了，而又需要存更多的数据时发生。这时会检查缓存中的“脏位”，如果是脏的，就会把数据写回RAM中。

9.3 指令流水线

CPU在处理指令时，不一定要完全按照串行流程，可以按照并行方式进行。意思是，当此条指令正在“执行”时，可以处理下一个指令的“解码”，下下条指令的“读取”，这样可以同时利用上CPU里的所有部分。这样进行执行，吞吐量*3。如下图所示。

当然，这样也可能出现问题，首先是因为上一条指令可能会改变下一条指令的运行方式，所以CPU在运行前需要解析这些指令，必要时还需要停下来等待上一条指令完成后在继续。

高端CPU，比如笔记本和手机那种，会进一步，动态排序有依赖关系的指令，最小化流水线停工时间，这叫“乱序执行”。这种电路非常复杂，但因为高效，几乎所有现代处理器都有流水线。

第二个问题是条件跳转，比如JUMP Negative这些，这些指令会改变程序的执行流。简单的流水线处理器，看到JUMP指令会停一会，等待条件值确定下来，一旦JUMP的结果出了，处理器就继续流水线。因为等待会消耗很多时间，高级的流水线处理器会提前猜测哪个条件可能性大，然后提前把指令放在流水线上，这叫“推测执行”。如果猜测正确，则立即执行，错误则会清空刚才加载的指令，重新加载。为了减少清空次数，CPU开发了高级方法来猜测哪条分支更有可能，叫“分支预测”。现代计算机的猜测正确率高达90%。

• 超标量处理器

理想情况下，流水线一个时钟周期完成1条指令，然后“超标量处理器”出现了，一个时钟周期可以完成多条指令。即便有流水线涉及，在指令执行阶段，处理器里 有些区域还是可能会空闲，例如：有一条指令是“从内存中取出某地址存放的数据”，执行这条指令期间ALU会闲置，所以一次性处理多条指令(取指令+解码)会更好（此句子也可翻译为：那么，为什么不一次获取和解码多个指令，并尽可能地执行指令呢）。也就是说，如果多条指令要 CPU 的不同部分，就多条同时执行。我们可以再进一步，加多几个相同的电路执行出现频次很高的指令——举例，很多 CPU 有4个、8个甚至更多完全相同的ALU结构，可以同时执行多个数学运算。

参考连接1：一文解析超标量处理器 - CSDN
参考连接2：计算机组成原理：超标量，让CPU的吞吐率超过1 - CSDN
参考连接3：一个时钟周期执行一条指令的过程理解（单周期CPU） - CSDN
参考连接4：计算机组成原理（6）——-指令执行过程 - CSDN

9.4 多核处理器

以上的指令流水线工作都是对于一个流水线来说的。另一个方法是同时运行多个指令流，叫多核处理器。多核意思是，CPU芯片有多个独立处理单元，就像有多个CPU。多个CPU之间可以合作运算。

你应该听过双核或四核处理器，意思是一个 CPU 芯片里，有多个独立处理单元，很像是有多个独立’CPU，但因为它们整合紧密，可以共享一些资源，比如缓存，使得多核可以合作运算

当多核不够时，可以用多个CPU，比如视频网站的服务器。

2个和4个核的计算机是最常用的（现在可能有8核了），但人们还需要更多的，所以有了超级计算机。目前世界上最快的计算机位于中国超算中心，神威·太湖之光，有40960个CPU，每个CPU有256个核心，总共超过1千万个核心，可以进行超级运算或者宇宙大模拟。

10 早期的编程方式

前几集我们把重点放在计算机的原理，怎么从内存读写数据，执行操作。还讲了指令的执行。但是，我们还没将程序如何“进入”计算机。

10.1 最早的编程——可编程纺织机

给计算机编程这个需求，早在计算机出现之前就有了，最著名的来自于纺织行业。如果想要织一件红色衣服，我们只需要将红线放入纺织机中，但是如果想要图案怎么办？开始时，工人要经常改变纺织方向以作图案，所以早期有团案的衣服较为贵。后来发明了可编程纺织机，用孔板进行控制。这个纺织机叫“雅卡尔织布机”，被认为是最早的编程。

10.2 穿孔卡片编程

近1个世纪后，穿孔纸用于1890年美国人口普查。每张纸都可以存个人信息，用孔来表示信息，比如种族、婚姻等。穿孔纸存的是数据，不是程序。

10.3 插线编程

为了用计算机正确执行不同计算，程序员需要某种控制面板。面板有很多小插孔，程序员可以插电线，控制让机器的不同部分，互相穿数据和信号，因此也叫“插线板”。不幸的是，这意味着，运行不同程序要重新接线。所以到1920年，控制面板变成了可拔插，让编程更方便，可以给计算机插入不同程序。但是插线板编程很复杂，不过它在大多机电计算机很常见，世界上第一台电子计算机也是用插线板编程。

10.4 冯诺依曼结构

插线编程非常复杂，也非常耗时，这对计算机设计程序很麻烦。后来，内存的出现与发展，出现了“存储程序计算机”，能在内存里存储程序。如果内存足够，不仅可以存程序，还可以存数据。程序和数据都存在一个地方，叫“冯诺伊曼结构”。冯诺依曼计算机的标志是：

第一台冯诺依曼结构计算机叫“宝宝”，由曼彻斯特大学于1948年建成。直到1980年代，人们还是主要用穿孔卡片进行程序写入，计算机可以吸入一张卡片，把卡片内容写进内存。卡片输入非常麻烦，要是不小心弄乱了，要花几小时甚至几天来整理。数据由计算机输出，依然是需要用到卡片，方式是打孔。

10.5 面板编程

到了1980年代，还有一种常见的编程方式，面板编程。面板编程，用一大堆开关进行控制。通过开关控制进行二进制代码的编写，然后就可以运行程序。

不管是插线、穿孔纸片还是面板，早期编程都是专家活，需要非常了解底层硬件，比如操作码和寄存器等等。所以当时编程很难。下节课，讲到编程语言，是一种更简单的编程方法。

11 编程语言发展历史

之前，我们把重点放在硬件——组成计算机的物理组件上，比如电、电路、寄存器、RAM、ALU和CPU，但是在硬件层面上编程非常麻烦。所以程序员想要一种更加通用的方法编程，一种更软的媒介。所以，这节课，我们将要讲软件和高级语言。

11.1 机器语言、汇编语言和编译器

第8节课，我们一步步讲了一个简单程序。前面我们讲到用二进制代码表示不同的操作和地址，其实这只是一种数据的表现方式。就像英语和摩斯密码，虽然二者的符号和表达不同，但是可以传达相同的信息，计算机语言也类似。

11.1.1 机器语言

计算机能处理二进制，二进制是处理器的“母语”。这叫“机器语言”或者“机器码”。在计算机早期阶段，必须用机器码写程序。具体地来讲，会先在纸上用英语写一个高层次版本，这种对程序的高层次描述，叫伪代码，然后，用“操作码表”把伪代码转成二进制机器码，翻译完成后，程序就可以喂入计算机并运行。

11.1.2 汇编语言

但这种方法太麻烦了，所以在1940-1950年代，程序员开发一种新语言，更可读更高层次。它为每个操作码分配一个简单名字，叫“助记符”，助记符后面紧跟数据，形成完整指令。程序员可以用“LOAD_A 14”写代码，而不是用01二进制写代码了。

11.1.3 汇编器

当然，计算机并不认识助记符，它只认得二进制码，所以程序员写了一个二进制程序来帮忙。它可以读懂文字指令，自动转换成二进制指令，这种程序叫“汇编器”。汇编器读取用汇编语言写的程序，然后转成“机器码”。随着时间推移，汇编器能够帮助人类完成的事情越来越多。其中一个就是自动分析JUMP地址，程序员写程序时，只需写入可跳转的标签，汇编器就会自己跳转分析。

因此，程序员可以专心编程，不用管底层细节。

汇编语言直接对应机器码，虽然已经很方便了。但是，汇编器仍然强迫程序员思考，用什么寄存器和内存地址，如果我们突然要用额外一个数，可能要改很多代码。这时候，需要更加高级的语言出现。

11.2 A-0语言

为了更加方便编程，历史上有计算机科学家发明了A-0语言。这种语言相对汇编语言更加高级(一般一条汇编指令对应一条机器指令)，一行高级编程语言，可能会转成几十条二进制指令。同时，这名科学家还做了编译器，可以专门把高级语言转成低级语言，比如汇编或者机器码（CPU可以直接执行机器码）。虽然这个想法很先进，但是在当时并没有被大众所广泛使用。

11.3 高级语言的思想

幸运的是，这种思想开始流行，很多人尝试创建新的编程语言。比如我们用高级语言Python为例，计算两个值的和，如果用汇编语言，我们得从内存取值，和寄存器打交道以及其他底层细节。但同样的程序用Python可以这样写，不用管内存和寄存器位置。

程序员只需要创建“代表内存地址的抽象”，叫变量。上图，我们把变量存在A和B中，然后相加两个数，把结果存在C中。在底层操作时，编译器可能把变量A存在寄存器A中，但这些，程序员已经不需要自己思考放在哪了。

11.4 Fortran语言

Fortran语言，名字来源于“公式翻译”，IBM发布于1957年，其主宰了早期计算机编程。平均来说，Fortran语言写的代码，比同等的手写汇编代码短20倍，然后Fortran编译器会把代码转成机器码。语言更加高级，所以运行速度会慢一点，但是代码编写速度会大大提高。Fortran语言开始时只能运行在IBM计算机上。

11.5 通用编程高级语言

50年代的大部分编程语言和编译器只能运行在一种计算机上。如果升级电脑，所有的代码都可能要重写。因此，工业界、学术界和政府计算机专家，在1959年组成一个联盟——数据系统语言委员会。开发了一种通用编程语言，可以在不同机器上通用。最后，诞生一门通用商业语言，Cobol。为了兼容不同硬件，每个计算机都需要对应的编译器，但是这些编译器可以接收相同的Cobol代码。这种叫一次编写，多处运行。

由于高级语言的出现，原来只有计算机科学家才能的编程，到后来各个专业的人们都可以学会编程。下面是不同年代出现的主要重要语言，可以以此来瞧瞧编程语言的发展。

1. 从1959年开始，编程语言的时代开始了。
2. 在1960年代，有Algol、Lisp、Basic等语言。
3. 70年代有Pascal、C和Smalltalk语言等。
4. 80年代有C++、Objective-C（扩充C的面向对象语言）等。
5. 90年代有Python、Java和Ruby等语言。
6. 在新千年，Swift、C#和Go在崛起。

新语言使用更加聪明的抽象，使得其在某些方面更容易和强大。

12 编程原理-语句和函数

上节课讲到机器码写程序需要处理底层细节，写大型程序非常麻烦。为了脱离底层细节，开发了编程语言以让程序员专心解决问题，不用管硬件细节。这节课，我们讨论大部分编程语言都有的语法和函数。

12.1 语句与语法

语法，是用来规定句子结构的一系列规则。英语有语法，所有的编程语言也都有语法。a=5是一句语言，意思是，创建一个变量a，把数字5放进去。这叫赋值语句，把一个值赋给一个变量。注意，变量名称可以随便取（不重名即可），当然取名最好有点意义，这样可以方便别人读懂。程序和做菜一样，会一步步运行到程序尾部。

为了不只是顺序执行程序，我们需要流程控制语句。最常见的流程控制语句是if语句，if语句需要判断语句，因此这些表达式又叫“条件语句”，下面是一些流行语言的if语句。if语句是指，如果if里的条件为真，那么就执行if下面的代码；否则执行else下面的代码。

if语句只执行一次，如果要执行多次，则要用while语句。当while条件为真时，就会重复执行代码。另一个常用的循环结构是for结构。for结构不判断条件，会判断次数，会循环特定次数。

12.2 函数

为了隐藏程序的复杂度，我们可以把代码打包成函数，有些编程语言也叫“方法”或“子程序”。若其他地方想用这个函数，直接写函数名即可。当然，我们可以在函数里面加其他函数，这样可以设计更加简洁的代码。所以现代软件，是由上千个函数组成的，每个负责不同的事情。

这种模块化编程，不仅可以让单个程序员独立制作APP，也可以让团队协作写更大型的程序。不同程序员写不同的函数，只需要保证自己的代码正确，把所有人的拼起来，整个程序应该就能正常运行。

现在，我们不需要写指数函数这些普遍的函数。现代编程语言，有很多预先写好的函数集合，叫“库”，由专业人员编写，不仅效率高，而且经过了仔细检查。这样可以方便我们开发程序。本节结束，下节讲函数。

13 算法入门

前面两集尝试了高级编程语言，我们讨论了几种语句，赋值语句、if语句、循环语句等，以及打包的函数。算法，是解决某种问题的具体方法，一般而言所需时间越少越好，有时我们也关注其他方面，比如所占空间等。

13.1 排序算法

最常见的算法就是排序，比如给数字排序。排序也是应用非常广泛，非常常见的算法。排序算法有很多，为的是更快地进行排序。视频讲了选择排序。选择排序是指，对于每一次范围（这个范围逐渐减少）从中选择最小的放在最首。

算法的输入大小与运行步骤之间的关系，叫算法复杂度，代表运c行速度的量级。算法复杂度叫大O表示法。选择排序的复杂度是O(n^2)。此外，更低的排序有归并排序，时间复杂度是O(n*logn)。

13.2 迪杰斯特拉算法

用于图搜索的算法，对于一个有权图，要找最短路径，如果全部穷举，那么会是O(n!)的复杂度，这是一个非常糟糕的复杂度。所以，迪杰斯特拉发明了一种求最短路的算法，叫迪杰斯特拉算法。其算法复杂度是O（n^2）。

算法无处不在，并广泛应用于生活中各个地方，算法设计，也是计算机科学中一个很重要的方向。本节完，这节内容比较少，是因为这些知识数据结构中基本都学过了，就不需要着重记笔记。

14 数据结构

本集高能，基本上一分钟一个数据结构。

上节课讲了一写算法，比如数组排序、最短路径。不过，上节没讲的是，算法处理的数据，存在内存里的格式是什么。我们希望数据是结构化的，方便读取。所以，科学家发明了数据结构。

14.1 数组

数组的值一个个连续存在内存里面，所以不像之前，一个变量里只存一个值，我们可以把多个值存在数组变量里。我们用下标[i]取值，下标一般从0开始。数组变量表示的是首元素地址，后面通过偏移得到其他元素坐标。

现在很多语言自带了数组的一些算法，比如排序算法等，不需要我们直接写。

14.2 字符串

和数组相似的就是字符串，它是由字母、数字和标点等组成的数组。写代码时，用括号括起来就可以了，j="START"。在字符串末尾，有NULL项，这一项表示字符串到此结束。

因为计算机经常处理字符串，所以会有很多字符串函数，比如连接字符串strcat（接收两个字符串，把第二个放在第一个末尾）。

14.3 矩阵

有时，我们需要处理图像或者表格，此时我们需要矩阵。我们可以把矩阵看做是数组的数组。多维数组里的元素，其实也是像一维数组那样顺序排列的，只不过提取数组方式不一样。

14.4 结构体

把多种不同类型的数据打包放在一起，就叫结构体。甚至我们可以做一个结构体数组。结构体数组和普通数组一样，创建时便有固定的空间，不能动态增加容量。

14.5 链表

我们将值和指针放在一个节点（结构体）里面，就可以实现动态添加元素。指针是一种特殊变量，指向一个内存地址。多个连成的节点，就叫链表。有多种链表，比如循环链表和单向链表等等。

不同于数组的长度固定，链表可以通过改变指针指向动态添加元素。

• 队列和栈

队列和栈都是基于链表的（好像有数组类型的不过不常用）。

队列就像排队一样，谁先来谁先上，这叫先进先出（FIFO）。有入队和出队操作，入队在队尾进行，出队在队首进行。

栈是先进后出的结构。栈元素的出入叫入栈和出栈。入栈和出栈在栈顶进行。

14.6 树

如果节点有两个指针，分别指向左树和右树。最高的叫根节点，其余都叫子节点。没有任何子节点的节点，叫叶节点。若每个节点最多两个子节点，那么就叫二叉树。

树的一个重要特性是，从根到叶是单向的。

14.7 图

不同于树，如果数据可以随意相连，包括循环，就叫图。

上面就是主要的数据结构，此外还有堆和红黑树等等。最后，利用好数据结构，可以帮助我们更加高效地完成一些任务开发。

15 阿兰·图灵

15.1 图灵机

前几集我们讲了基础，比如函数、算法和数据结构。今天，我们来看一个对计算机理论贡献巨大的人，计算机科学之父——阿兰·图灵。

图灵于1912年出生在伦敦。当时一个很著名的问题是“可判定性问题”：是否存在一种算法，输入正确逻辑语句，输出准确的“是”或“否”。美国数学家阿隆佐·丘奇于1913年首先提出解决办法，他开发了一个叫“lambda算子”的系统，证明了这样的算法不存在。

但是lambda算子系统过于复杂，大洋彼岸的图灵提出一种假想计算机——后来被称为图灵计算机。图灵机的原理更加简单，更容易被人接受。图灵是一台理论计算设备。

图灵机有无限长的纸带，纸带可以存储符号。图灵机可以读入和写入纸带上的符号，还有一个状态变量，保存当前状态，还有规则。图灵证明只要有足够多的规则、状态和纸带，可以创造任何东西。没有计算机能比图灵机更强大。现在的计算机、手表和手机啥的，都是图灵完备的。

• 停机问题

图灵利用图灵机完成了可判定性问题的证明。

有没有办法在不执行的情况，弄清会不会停机？

图灵通过一个巧妙逻辑矛盾证明了停机问题是无法解决的，我们来看看他的推理。想象有一个假想图灵机，输入:问题的描述+纸带的数据，输出 Yes 代表会”停机”，输出 No 代表不会停机。不用担心它具体怎么工作，假设这样的机器存在就好，毕竟重点是推论。

图灵推理说：如果有个程序，此图灵机无法判断是否会”停机”，意味着”停机问题”无法解决。为了找到这样的程序，图灵用这台图灵机设计了另一个图灵机。如果一开始的图灵机说程序会”停机”(YES)，那么新设计机器会永远运行(即不会停机)；如果一开始的图灵机的结果为 No，代表不会停机，那么让新机器输出 No，然后”停机”。也就是说新设计的图灵机和一开始的图灵机的输出正好相反。如果程序不停机，就停机，如果程序停机，就永远运行下去。

…………剩下的内容看视频吧。

总之，长话短说，丘奇和图灵证明了计算机的能力有极限，无论有多少时间或内存，有些问题是计算机无法解决的。

16 软件工程

大型软件，代码往往很多。开发软件需要很强的科学性，由此，一个关于软件的学问出现了，软件工程。

16.1 面向对象

前文我们提到了，把大项目分解成小函数，可以让很多人同时工作。每个人不需要关心整个工程，只需要关心自己的部分即可。

但是仅仅把打包成函数还不够，就像office有上千万行代码，就算打包成函数也有几十万个。解决办法是：把函数打包成层级，把相关代码都放在一起，打包成对象。这就是面向对象的由来。

一个对象可以包含其他对象、函数和变量。我们要访问某个函数时，要通过对象不断向内索引。这样通过封装组件，可以隐藏复杂度。

16.2 开发文档

开发完成项目后，团队需要完成解释文档，帮助理解代码都在做什么，以及定义好”程序编程接口”，简称API。

API帮助不同程序员合作，不用知道具体细节，只知道怎么使用就行了。API还控制哪些函数和数据让外部访问，哪些仅供内部访问。“面向对象”的编程语言，可以指定函数是public或private来设置权限。

“面向对象”的核心是，隐藏复杂度和选择性的公布功能。现在大部分软件或者游戏都是面向对象编程语言写的，比如C++，C#等。

16.3 IDE

现代软件的开发，一般需要借助开发器。开发器集成了编译、调试、整理代码等功能，因为集成了所有的东西，因此叫集成开发环境，简称IDE。

IDE还可以直接编译和运行代码。如果代码错误，IDE会定位到错误代码并给出提示来解决问题，这叫调试debug。

程序员工作的另一个重要部分是给代码写文档，这个文档写在readme里面。文档也可以直接注释在程序里面。注释很重要。

16.4 源代码管理

IDE还有另一个功能，叫源代码管理，也叫版本控制。大型程序有源代码管理，他们还会将代码放到一个中心服务器上，叫代码仓库。

要修改代码时，就从代码仓库里取出来，修改完成后再放入。

当代码出现错误时，源代码管理也可以帮助程序员恢复到未修改的版本，并定位是谁修改了代码。

16.5 测试

测试代码和写代码一样重要，测试一般有个人或者小团队完成。测试统称为“质量保存测试”，简称QA。它严格测试软件的方方面面，模拟各种情况，看看软件会不会出错，就是找Bug。

16.6 alpha版本和beta版本

beta版本是接近完成的版本，此版本可以向大众开放，进行免费测试。alpha版本的粗糙的版本。

17 集成电路与摩尔定律

过去几集我们学了软件、编程语言等，软件科学有着巨大的发展，但是如果没有硬件的大幅度进步，软件是不可能做到这些的。

17.1 集成电路IC的出现

电子计算机时代，计算机有独立部件组成，叫”分立元件“，然后不同组件再用线连在一起。这时候计算机非常大而且很昂贵。在1950年中期，晶体管开始商业化，开始用于计算机。晶体管比真空管更小，但是元件依然是分立的。

晶体管的到来，标志着”计算2.0时代“的到来。但是晶体管的出现并没有完全解决电脑元件多线路复杂的问题。解决办法就是，讲计算机所有元件集成。简单地来说，把多个组件包在一起，变成一个新的独立组件，这就是集成电路。

1959年的仙童半导体，让集成电路变成现实。仙童半导体用硅作为材料，其更稳定更可靠，价格也更低。Noyce因为发明了仙童半导体，被公认为现代集成电路之父。电子时代出现。

IC 就像电脑工程师的乐高积木，可以组合出无数种设计，但最终还是需要连起来，创造更大更复杂的电路，比如整个计算机。所以，PCB被创造出来了。

17.2 印刷电路板——PCB

集成电路可以把多个电路元件集成在一块芯片上，但是依然要将电路连接起来以制造计算机。所以工程师再度创新：印刷电路板，简称PCB。PCB可以大规模生产，无需焊接或用一大堆线。它通过蚀刻金属线的方式，把零件连接到一起。PCB和IC结合使用，可以大幅度减少独立组件和线路，但做到同样的功能。而且更小、更便宜更可靠。

17.3 光刻

早期的元件，无法集成大量晶体管。所以需要全新的制造工艺——光刻。简单来说，就是用光把复杂图案印到材料上，比如半导体。它只有几个基础操作，但可以制作出复杂电路。

光刻机光刻电路的流程是，对于一块硅（晶圆），上面加氧化层，光刻胶，和光掩膜，然后用强光照射，强光能照射的地方光刻胶消失，然后把露出部分的氧化层清洗掉，最后再清洗掉光刻胶，就可以进行材料掺杂了。

我们想修改硅露出来的区域让它导电性更好，所以用一种化学过程来改变它，称为“掺杂”。

由于光刻机和集成电路的出现，一片IC由原来的5个晶体管增加到1960年中期的上百个。

17.4 摩尔定律

1965年，摩尔看到了趋势：每两年左右，得益于材料和制造技术的发展，同样大小的空间，能塞进两倍数量的晶体管。这叫摩尔定律。芯片的价格也不断下降。

芯片集成地小，可以减少电的损耗，信号延迟更低，时钟速度加快。仅仅1950年左右，用分立元件会占满整个屋子，到集成电路出现，元件越来越小。尤其是集成电路用于微处理器，开启了计算3.0时代。到2010年，10亿个晶体管集成在一片芯片。光刻机分辨率也从几毫米到15纳米。

如今的处理器，比如iPhone7的A10CPU，有33亿个晶体管。

集成芯片的设计当然不是手工的，从1970年开始，超大规模集成（VLSI）软件来自动生产芯片设计。

17.5 未来集成电路面临的挑战

不幸的是，摩尔定律受到越来越多的挑战，现在已经达到极限。进一步做小，会面临两个问题。

1. 用光掩膜把图案加到晶圆上，因为光的波长，精度已经达到极限。
2. 当晶体管非常小，电极之间可能只距离几个原子，电子会跳过间隙，叫量子隧道贯穿效应。

18 操作系统

18.1 操作系统简介

1940、1950年代的电脑，每次只能运行一个程序，程序员通过在打孔纸板上写程序来进行。打好孔后，再放入计算机中运行程序。但是，这种方法较慢。我们需要一种方法，让计算机自动运行程序，”操作系统“因此而生。

操作系统，也叫OS，其实也是一种程序。但是它有操作硬件和特殊权限，可以运行和管理其他程序。操作系统一般是开机第一个启动的程序。其他程序，都由操作系统启动。

18.2 操作系统的作用

早期的操作系统，一次只能运行一个程序，现在可以运行多个。系统运行完一个程序后，会自动运行下一个程序，不会浪费时间在更换程序上，这叫”批处理“。

当时，不同的CPU甚至相同的，可能配备着不同的打印机。程序员不仅需要考虑如何写程序，还有考虑如何和打印机和键盘等”外部设备“的交互。程序员需要考虑外部设备如何使用，以进行写代码。如今，操作系统充当软件和硬件之间的媒介。更具体地说，操作系统提供API来抽象硬件，叫”设备驱动程序”。程序员可以用标准化机制和输入输出硬件(I/O)交互。比如，程序员只需要调用print(highscore)，然后操作系统会处理输出到纸上的具体细节。

18.2 多任务处理

如果一个系统只能运行一个程序的话，那么很多设备将会闲置，只能等待其他I/O设备完成后，才用。所以，后来开发了能在单个CPU上同时运行几个程序的操作系统。这种能力叫做操作系统的”多任务处理“。

18.3 操作系统的内存管理

不同的程序数据，在计算机中存放于不同的位置，甚至可能同一个程序的数据分别处于计算机中的不同位置。这种存法导致程序员要追踪这些地址很麻烦。为了隐藏这种复杂性，操作系统会把内存地址进行”虚拟化“，这叫虚拟内存。程序可以假定内存总是从地址0开始的。而内存实际的物理地址，被操作系统隐藏和抽象了。

操作系统会自动地讲程序的物理地址与虚拟地址进行映射（有一个映射表，存储了虚拟内存和真实内存的映射关系）。一个在不同物理地址的程序，可能映射为统一顺序。这种机制可以使程序的内存大小可以灵活增减，叫”动态内存分配“。

我们会给一个程序一定的内存范围，如果程序出错开始乱写数据，那么这些错误的数据不会到其他内存下，这叫“内存保护”。这对防止恶意软件(如病毒)也很有用，例如，我们不希望其他程序有能力读或改邮件程序的内存，如果有这种权限，恶意软件可能以你的名义发邮件，甚至窃取个人信息。

18.4 分时操作系统

在1970年代，计算机开始变得越来越便宜。这时，计算机不仅可以多个程序运行，而且可以多个用户访问。用户通过“终端”访问电脑，终端只是键盘和屏幕，本身没有处理能力。冰箱大小的计算机可能有50个终端，能让50个用户使用，这时操作系统不但要处理多个程序，还要处理多个用户。

为了能够让多用户使用计算机而不会使一个用户占满计算机，开发了分时操作系统。意思是每个用户只能用一小部分处理器、内存等，因为电脑很快，即使拿到1/50的资源也足以完成许多任务。

早期分时操作系统中，最有影响力的是Multics（多任务信息与计算系统），它是第一个从设计时就考虑到安全的操作系统。开发人员不希望恶意用户访问不该服务的数据。不过由于其系统过度设计了（功能太多），导致其所占内存过多，不能流行起来。

18.5 Unix操作系统

所以为了简化操作系统的复杂度，设计者开发了Unix，Unix把操作系统分成两个部分：

1. 首先是操作系统的核心功能，如内存管理、多任务处理和输入/输出处理，这叫“内核”；
2. 第二部分是一堆有用的工具，如程序和运行库，但他们不是内核的一部分。紧凑的内核，意味着功能没有那么全面。

Unix的简单使得它可以用于很多计算机，越来越多的开发人员用Unix写程序和运行程序。Unix系统也在贝尔实验室大受欢迎。甚至在1970年代，有人还写了在Unix下的不同编程语言的编译器，这些使得Unix成为了1970-80年代最受欢迎的计算机操作系统。

18.6 个人电脑和现代操作系统

随着计算机水平的发展，出现了个人电脑和家庭电脑。这些电脑的操作系统比较简单，缺乏“多任务“、”内存保护“等功能，若遇到程序错误，就会发生崩溃（蓝屏）。幸运的是，1980年代开发的windows系统，有更好的保护，不会经常崩溃。

19 内存和储存介质

本节重点，存储技术的发展。

19.1 内存和存储器区别

本系列中，我们多次谈到内存，甚至设计了一个简单内存（锁存器）。一般来说，电脑内存是”非永久性“，如果电源线不小心拔掉了，内存里所有数据都会丢失，所以内存叫”易失性“存储器。

不过，存储器和内存有所不同。任何写入存储器的数据，比如电脑硬盘，数据会一直存着，直到被覆盖删除，断电也不会丢失。存储是”非易失的“。比如一个小小的U盘，能够低成本+可靠+长时间地存储上GB的数据。

19.2 早期的存储器——延迟线存储器

最早的存储介质是打孔纸片和打孔纸带。纸片用了十几年，因为不用电而且便宜耐用。坏处就是读取慢，只能写入一次，打的孔无法修复，若要存储临时值，纸卡不好用。

由于纸片的缺陷，人们发明了延迟线存储器。原理是，拿一个管子装满液体，管子一端放扬声器，另一端放麦克风，扬声器发出的声波，发送到麦克风需要一定时间，麦克风将压力波转换回电信号，我们可以用压力波的传播延迟来存储数据。若有压力则表示1，无则表示0，麦克风受到这些压力波后，把其转换为1010之类的二进制数据。若用线路+放大器将其接回，那么就可以存储这段信号了。

但是，延长线存储器的缺点是，每个时刻只能读一位数据。如果你想访问第100位数据，你只能等待第100位数据出现，这种叫做”顺序存储器“或”循环存储器“，而我们想要的是”随机存取存储器“，可以随时访问任何位置。

19.3 磁芯存储器

后面还出现了如”磁致伸缩延迟存储器“，但是延迟线存储器在1950年代中期就基本过时了，因为出现了性能、可靠性和成本都更好的”磁芯存储器“。当磁圈加正电，就可以磁化，加反向电，就可以反向磁化，可以用这个来表示01存储信息。当然，用1位不行，需要用到磁圈网络。

下图是一个实际的磁芯存储器，每个黄色方格有32行x32列的磁芯，每个磁芯存1位数据，所以能存1024 位(bit)(32x32=1024)。

最重要的是，磁芯存储器不像延迟线存储器，磁芯存储器能随时访问任何一位，这时非常有用的。磁芯存储器于1950开始，流行了20多年。

19.4 磁带

即使如此，磁芯存储器能存储的数据还是太少了。1951年，还发明了一直存储器，叫”磁带“。磁带是纤薄柔软的一长条磁性带子，卷在轴上。磁带可以在”磁带驱动器“内前后移动。磁带的存储空间相比之前的几kb大小，大了很多，可达几mb。因为磁带驱动器很贵，但是磁带很便宜，所以磁带一般用于数据存储。磁带的主要缺点是访问速度。

19.5 现代存储器——硬盘、软盘、光盘

1950，60年代，有个类似的“磁鼓存储器”，磁鼓持续旋转，可以读取数据。但到1970年代，磁鼓存储器不再生产。然而磁鼓导致了硬盘的发展，因为硬盘和磁鼓很像。磁盘有磁性，其优点就算薄，可以进行堆叠。1970年代，磁盘大幅度改进并变得普遍，如今硬盘可以轻易容纳1TB的数据。

软盘，除了磁盘是软的，其他基本一样。软盘是为了便携。你可能对光盘（CD）产品更熟悉，功能和硬盘一样，都是存储数据，不过原理不同，光盘主要用的是光学技术。如今，存储器朝固态前进，如硬盘和U盘，里面都是集成电路。如果机械硬盘被固态硬盘代替，简称SSD。

20 文件系统

上集我们讲了数据存储，磁带和硬盘这样的技术。他们可以在断电的情况下存储上万亿个位，非常适合存储一整块相关的文件。我们见过很多文件，比如音乐文件，视频文件。这节课我们要讲，什么是文件，计算机如何管理文件。

20.1 计算机中的文件格式

20.1.1 数据格式与TXT文本文件

数据可以随意摆放，但是按照一定规律和格式会更好，这叫数据格式。你可以发明自己的格式，但是最好按照已有的格式更好，比如JPG。

最简单的是文本文件，简称TXT，其本质也是二进制。我们可以把二进制转换为十进制，再由ASCII值转换为字符。

20.1.2 波形文件WAV

更复杂的文件，比如波形文件（wave），简称wav，它存音频文件。在正确读取数据前，需要知道一些信息，如码率，单声道还是立体声。数据的数据，叫元数据。元数据在文件开头，在实际数据前面，因此也叫文件头。音频数据紧跟在元数据后面，是一长串数字，数字代表每秒捕获多次的声音幅度。

比如，对于一段声音，我们可以得到其波形如下。通过电脑或者手机，每秒可以对声音进行上千次采样，每次采样可以用一个数字表示，声压越高数字越大，也叫“振幅”，wave文件里存的就是这些数据。在播放声音文件时，扬声器会产生相同的波形，播出声音。

20.1.3 位图文件BMP

位图（Bitmap），后缀.bmp，它存图片，计算机上，图片由很多个叫”像素“的方块组成，每个像素有三种颜色组成：红，绿，蓝，叫”加色三原色“，混在一起可以创造其他颜色。如图wav文件一样，bmp文件开头也是元数据，有图像宽度，图像高等，颜色深度信息。BMP文件是一串二进制代码，每三位分别表示红绿蓝的深度。

不管是文本文件，WAV文件，BMP，或者其他文件，其在底层都是一长串二进制。要想知道文件是什么样的，就得先知道文件格式是什么样的。

20.2 计算机如何存储文件

20.2.1 目录文件

虽然硬件可能是磁盘、磁带或者硬盘等，不过通过抽象后，都可以看成一排能存数据的桶。早期计算机只能存一个文件，它会顺序放置，从头存到尾。但随着计算能力和存储容量的提高，存多个文件变得非常有用。最简单的是，多个文件连续存储。这时，知道不同文件的开头和结尾在哪就变得很重要。需要记录文件的位置，这里叫”目录文件“。这个文件通常存储在开头。

目录文件中，存所有文件的名称，还有创建时间、能否都写等等，最重要的是，目录文件中写明了文件起始位置和文件大小信息。如果更改了文件信息，就必须更新目录文件。这个例子叫”平面文件系统“，因为文件都在同一个层次。

20.2.2 文件分块——碎片化存储

现代文件系统可能会出现问题，比如因为文件连续存储，那么前一个文件存储信息过多，可能会覆盖后一个文件。所以出现了两者解决方案：

1. 把空间划分成一块块，导致有一些”预留空间“，可以方便移动和管理；
2. 拆分文件在多个块里面，目录文件中会记录拆分后文件所在的块。这听起来很像前面讲的虚拟内存。

若要删除某个文件，计算机会将”目录文件“里的对应文件的信息删除，注意这里实际的文件并没有被删除，只是可以被其他新文件覆盖。所以计算机取证团队可以利用这点”恢复数据“。

不过，文件因为这种存储方式会变成多个块，我们称他为碎片。碎片化的文件不利于读取，就出现了”碎片化管理“技术。碎片化整理就是将原来的分散在多个块里的数据，按顺序整理好，方便整理。

20.2.3 分层文件系统

平面层的数据不利于文件查看，所以出现了”分层文件系统“，所以出现一个根目录。根目录可以索引下面的文件夹，这样就可以做一个无限深度的文件夹。如果想把数据移动，我们只需要把一个目录文件的信息删除，然后添加在另一个目录文件下即可。

文件系统使我们不必关心文件在磁带或磁盘的具体位置，整理和访问文件更加方便。

21 压缩

上集我们讨论了文件格式，如何编码文字、声音和图片，还举例了txt、wav、bmp，这些格式虽然有用，但是其效率并不高。我们希望文件能小一点，这样能存大量文件，传输也会更快。解决办法就是压缩，把数据变小。

21.1 无损压缩技术

我们以图像为例，每个像素的颜色是三种原色：红绿蓝的组合。每个颜色用一个字节存，数字范围是0到255。如果红绿蓝都是255会得到白色。

21.1.1 游程编码压缩

为了减少所占内存，一种方法是减少重复信息。最简单的方法是游程编码，适合经常出现相同值的文件。比如，若有连续多个统一颜色，我们可以在最开始的颜色前加一个数字表示重复次数。为了区分哪个是数字，哪个是颜色，我们将所有颜色前面加数字表示重复次数。

我们在没有损失的情况下，完成了压缩，这叫无损压缩。解压后，数据和没有压缩一模一样。

21.1.2 字典编码压缩

另一种无损压缩，它用更紧凑的方式表示数据块，叫“字典编码”。我们需要一个字典，存储”代码“和”数据“间的对应关系。

比如，我们有四种不同的色组如下，我们需要为这四对色组，生产紧凑代码。

1950年，霍夫曼发明了一种高效的编码方式，叫霍夫曼树。方法是这样，列出所有块和出现频率，每轮选两个最低频率，然后将其组成一个树，总频率是2，然后不断重复这个过程。最后得到如下结果，它有一个属性，按频率排列，然后将每个数分支用01表示，就得到了二进制与颜色块的字典。厉害的是，它们决定不会冲突，因为每条路径是唯一的。这意味在代码是”无前缀的”，没有代码是以另一个代码开头的。然后，就可以将原来的颜色二进制码压缩。

“消除冗余法”和“用更紧凑的表示方法”，这两种方法通常会组合使用。几乎所有的无损格式都用了它们，比如GIF、PNG、PDF、ZIP。游程编码和字典编码，都是无损压缩，压缩不会丢失位信息，解压可以完全恢复。

21.2 有损压缩技术

但有时候，丢失一些数据也可以，因为人们可能看不出。大多数有损压缩技术，都用到了这点。

21.2.1 感知编码

以声音为例，我们的耳朵有一些频率的声音不能听到，比如超声波，那么录音乐的时候，超声波数据都可以扔掉，因为人类听不到超声波。另一方面，人们对人声很敏感，所以应该尽可能保持。有损音频编码就是如此，用不同精度编码不同频段。这种删掉人类无法感知的数据的方法，叫“感知编码”。

21.2.2 图像与视频压缩编码

• 图片压缩

最著名的有损压缩图像格式是JPEG，人的视觉也与听觉一样不完美，我们善于发现尖锐对比，比如物体边缘，然后看不出不大的颜色变化。JPEG就是利用这点，将负责的8*8像素块，变成简单的像素块，如下所示…………

（这里就不详细说了，有兴趣直接去搜JPEG图像压缩原理即可）。

• 视频压缩

视频也是如此，视频就是一长串的连续图片，所以很多方面，图片的技术也使用于视频。因为视频之间帧与帧之间有时变化很小，比如背景(基本会保持一段时间背景不变或变化很小)，这叫“时间冗余”，视频不用每一帧都存这些像素，可以只存变化的部分。还有的通过帧分析，用多个补丁代表物体，然后帧之间直接移动这些补丁。MP4就是一种很流行的视频压缩格式。

不过当压缩太严重时就会出错，没有足够空间更新补丁内的像素。

总而言之，压缩对大部分的数据有用，学习压缩也非常重要，因为可以高效存储图片、音乐、视频，这也帮助一些娱乐的兴起，不然宽带可能太贵。

22 命令行界面

我们之前讨论过输入输出，但是都是计算机组件相互输入输出，比如RAM输出数据、或输指令进CPU，这节课讲用户如何输入和获得数据。我们有设备用于显示信息，如今有个专门的学科叫“人机交互”。

22.1 早期的输入方式——齿轮旋钮开关、纸带

早期机械计算设备，用齿轮、旋钮和开关等机械结构来输入输出。这些就是交互界面，甚至一些早期电子计算机，也是用一大堆机械面板和线来操作。其输出是打印在纸上。

然而，到1950年代，机械输入完全消失，因为出现了打孔纸卡和磁带，但输出依然是打印在纸上。当时的计算机输入，是以计算机为照顾对象输入的（尽可能迁就机器，对人类好不好用是其次），因为纸带方便计算机读取信息，但是不适合人类了解纸带里的信息。人类输入程序和信息，但是计算机不会交互式地回应。程序开始运行后会一直进行，直到结束。

22.2 输入设备——键盘

这种情况一直持续到1950年代末，一方面小型计算机变得足够便宜，另一方面计算机变得更快，能同时支持多个程序和用户，这叫“多任务”和“分时系统”。计算机需要人类的数据输入，这时有了键盘。由于“QWERTY”型打字机已经流行于市面上了，所以键盘也是“QWERTY”型的。

打字机的流行过程也比较曲折。打字机的发明者刚开始没想到会流行于市场，只不过由于十指打字的出现，才使得打字机开始流行。这种打字方式比一个手指快很多，之后还有人学会了盲打。

不过计算机如何使用打字机呢？早期的计算机使用了一种特殊打字机，是专门用于发电报的，叫电传打字机。利用电传打字机，一方的人打的字，可以在另一方显示，使得两个人可以长距离通信。

因为电传打字机有电子接口，稍作修改就能用于计算机。电传交互界面在 1960~1970 很常见。

用起来很简单，利用键盘，输入一个命令，然后按回车，计算机就会输出回来，用户和计算机来回“对话”这叫“命令行界面”。比如，输入ls，计算机就会列出所有文件到打印机上。这就是早期的交互界面。

它是最主要的人机交互方式，一直到 1980 年代。

22.3 显示设备——屏幕

随着电视剧开始量产，同时处理器和内存也在发展，到1970年代屏幕代替电传打字机进行交互变得可行。但与其为屏幕专门做全新的标准，工程师直接用现有的电传打字机协议，这样屏幕就像无限长的纸，除了输入输出文字，没有其他东西，协议是一样的，所以计算机分不出是纸张还是电子屏幕（也就相当于用电子屏幕虚拟实际的电传打字机纸张）；而输入数据依然使用的是键盘。这些包括了屏幕的“虚拟电传打字机”，叫“终端(Terminal)”。

到1970年代末，屏幕成了计算机的标配。那时候，还发明了文字交互游戏，如“zork”。

现在，我们计算机中还有命令行交互界面，比如windows系统中的CMD命令行界面就是如此，可见早期计算机对我们现在的计算机运行方式影响巨大。

命令行界面虽然简单但十分强大，由于编程大部分是打字活，所以程序员们使用命令行也比较自然，因此，即使是现在大多数程序员工作中依然用命令行界面。而且用命令行访问远程计算机，是最常见的方式，比如服务器在另一个国家。

23 屏幕和2D图形显示

23.1 早期的图形屏幕

早期文本任务与图形任务是分开的，早期的屏幕无法清晰地显示图像，还不如将其打印的纸上。早期屏幕的典型用途，是跟踪程序的运行情况，比如寄存器的值。因为屏幕更新很快，这对临时值显示简直完美。但是屏幕很少用于显示结果，结果值还是主要用纸打印出来。

这台 1960 年的 PDP-1是一个早期图形计算机的好例子。

图中三个组件是分开的，因为当时文本任务和图像任务是相互分离的。事实上，早期的屏幕性能太差无法清晰地显示文字，而打印到纸上有更高地对比度和分辨率。早期屏幕的典型用途是跟踪程序的运行情况，例如：寄存器的值。

23.2 CRT显示技术

最早最有影响力的显示技术是阴极射线管（CRT），原理是把电子发射到有磷光体涂层的屏幕上，当电子撞击涂层时，会发光几分之一秒，由于电子是带电粒子，路径可以用磁场控制，屏幕内用板子或线圈，把电子引导到想要的位置上。

这样，就有两种方法绘制图形：

• 1.引导电子束描绘出形状，这叫矢量扫描，如果重复地够快就可以显示出现图形；
• 2.按照固定路径，一行行来，从上到下，从左到右，不断重复，只在特定路径扫描，叫“光栅扫描”。

23.3 像素

随着技术发展，我们终于可以在屏幕上显示清晰的点，叫“像素”。

液晶显示技术（LCD）和以前的技术相当不同，但LCD也用光栅扫描，每秒更新多次像素里红绿蓝的颜色。

23.4 符号显示

不过，早期计算机显示不用像素，因为就算二值400×400的显示，也有16万bits，这已经超过了电脑当时最大存储空间。所以早期电脑是存符号，80×25个符号最典型，每个符号用8位ASCII码表示，也才16000bits，这样才合理。

这样计算机需要额外的硬件从内存读取符号，转换成光栅图像，才能显示图像。这个硬件叫“符号生成器”，基本上算是第一代显卡。它内部只要一小块只读存储器(ROM)，存着每个字符的图形，叫“点阵图案”。如果图形卡看到一个 8位二进制，发现是字母 K，那么会把字母 K 的点阵图案光栅扫描显示到屏幕的适当位置。为了显示，“字符生成器”会访问内存中的一块特殊区域，这块区域专为图形保留，叫屏幕缓冲区。程序想显示文字时，修改这快区域的值就行。

但是字符集实在太小了，不能显示很多东西。因此对ASCII进行了各种扩展，加新字符。此外，还可以改变背景颜色。

23.5 矢量扫描法

但是，上面这种方法不能绘制任意图案。科学家想到了“矢量扫描法”，若要显示文字，就用线条画出来，而不是存一个像素矩阵那样占用大量内存。这个方法用命令来画线段，因为可以不断改变命令，所以这图案甚至可以是动态的。

23.6 Sketchpad

1962是一个大里程碑，Sketchpad诞生，一个交互式图形界面，用途是计算机辅助设计（CAD）。用户可以用光笔，进行画图，程序里面还自带了许多元件，帮助进行设计图案。这个发明有巨大意义，它们代表了人机交互的关键转折点。

23.7 像素与位图显示

1960年代末，计算机存储技术的发展，可以利用像素矩阵来表示图形。计算机把像素数据存在一个特殊区域，叫“帧缓冲区”

位图显示（BMP）的灵活性，为交互式开启了全新可能，但它的高昂成本持续了十几年。所幸的是，Sketchpad等的诞生为图形化交互界面的发展做出了巨大贡献。

24 冷战和消费主义

之前讲了很多计算机的知识，比如编译器、语言、操作系统、算法和存储等等，这些全部在1940-70年代出现。本节课注意讲一下这个时代的历史，更好地帮我我们理解计算机和计算机的发展。

24.1 二战后的科技发展

二战之后，两个超级大国关系越来越紧张，美国和苏联出现了冷战。这时期，国家花了大量资金在科学与工程学上，计算机技术发展迅速。

当时发明的计算机，大部分应用于政府和国家，因为只有国家能够承担巨额经费用于计算。计算机和以前的机器不同，以前的机器如蒸汽机和纺织机等等，他们增强了人民的物理能力，而计算机增强的是人类智力。

24.2 Memax假想计算机

Memex是一台假想的计算机设备，由范内瓦·布什发表。Memax可以存储数据，帮助人信息交流。他还预测未来会出现一种新的百科全书，信息之间相互连接（维基百科）。Memax的出现，促进了人民对计算机的未来的思考。

在范内瓦·布什建议下，美国建立了国家科学基金会，负责给科学研究提供政府资金，美国的科技领先全球，主要原因就是这个机构。

24.3 日本的收音机崭露头角

1950年代，消费者开始买晶体管设备，其中值得注意的是收音机。他小而便携，受到大家欢迎。

日本也想从二战后恢复，他们从贝尔实验室获得了晶体管的授权，帮助振兴日本的半导体和电子行业。1955年，索尼的收音机问世，他们把重心放在质量和价格上。因此，短短5年内，日本公司就占领了美国收音机市场的一半。

苏联此时在计算机方面的计算落后西方几年，但是苏联的太空技术远超他国。

24.4 太空计划促进集成电路发展

苏联在1957年把第一个卫星送上轨道，1961年把人类送上了太空。所以，美国为了追赶苏联，开始了登月计划。美国花了大量的资金用于资助太空计划。

太空计划一个重要的问题是，如何给太空船导航，这需要电脑计算复杂度轨道。太空电脑需要小、快、可靠，所以NASA采用全新工艺，集成电路。太空计划的阿波罗导航计算机，首先使用了集成电路。太空计划，促进了世界计算机工艺发展。

24.5 消费级电子发展

其实，对集成电路发展更促进的是军事，特别是洲际导弹和核弹。超级计算机，就是用于服务美国的政府机构。

最初，美国的半导体行业靠着高利润和政府合作起步，消费市场被忽略了。日本此时抓住机会，大力发展消费级电子设备，提升质量和工作效率。1970年代，太空竞赛和军事渐渐减少，美国半导体企业发现无法在消费领域竞争过日本，因为日本的产品更便宜和质量更高。这时很多美国公司倒闭，英特尔和仙童半导体都面临巨大危机。

美国公司的无力，造就了日本如卡西欧、索尼等快速发展，比如手持计算机等。很快，日本产品开始大量占领市场，计算器、手表等等。这些促进了微处理器的发展。同时，街机游戏也因此发展。70年代，家用计算机和游戏机出现。

24.6 结语

从大到人类可以随意行走，到手持电子设备，这种巨大的变化由两种力量推动，政府和消费者。政府资金促进了早期发展，消费者促进了行业持续发展。政府和消费者对科技的促进，这种关系直到现在依然存在。

25 个人计算机革命

25.1 为什么个人计算机时代能到来

随着集成技术和CPU的发展，把整台计算机做到一张电路板上成为可能，大大降低了制造成本。并且，那时有便宜可靠的存储介质，比如磁带和软盘。还有低成本的显示器，通常是电视剧稍作改装而成。这时候做成的计算机叫“微型处理器”，并且计算机的成本也不断降低，这使得一个人的计算机成为可能。个人计算机时代到来。

综上，计算机成本下降+性能提升，让个人计算机成为可能。

25.2 商业计算机与Basic语言

1975年出现了第一台可以说是商业计算机。这台计算机需要自己购买配备组件，所以组件买卖在这时候兴起。

更困难的是，计算机的编程语言依然是机器语言，这对大部分人来说都是非常困难的。比尔盖茨和他的同伴，开发了能运行basic语言，为此，他们需要一个机器，把Basic语言转换为机器语言，这叫“解释器”。

“解释器”和”编译器”类似，区别是”解释器”在程序运行的同时转换编码，而””编译器”提前转换好整个程序文件的编码，然后一次性整体运行。

这时，乔布斯开始出售原型机，用户需要自己加键盘、电源和机箱，这叫Apple1，苹果计算机公司的第一个产品。

25.3 整体机的出现

不过此时的电脑是要自己组配各个组件的，不过后来出现了整体机，如Apple2。这种集成了电脑、键盘和屏幕的全套整体计算机，吸引了大量的人购买。

Apple2以及当时出现的其他整体计算机，配备了basic语言，用户可以利用此编写自己的程序。同时，各种各样的软件开始发展。这次计算机革命，最重要的是他们是面向普通消费者的，而不是政府和企业。

25.4 IBM兼容框架

IBM公司为了抓住市场，也开发了自己的计算机，这台计算机最与众不同的是，它可以添加其他外设设备，比如显卡、声卡和游戏控制杆等等。这种开发架构叫“IBM兼容”。大量公司开始使用IBM兼容，IBM兼容体系的计算机越来越多。不使用IBM兼容的计算机大部分都失败了，除了苹果公司。

25.5 苹果公司——封闭框架

苹果公司最终选择了相反方式，“封闭架构”，用户无法加新设备到计算机中。苹果的封闭框架可以使他们做出来的产品更加照顾用户的体验感。

为了和IBM兼容体系的计算机对抗，苹果公司需要非常具有体验感的产品出现。他们的答案是Macintosh，于1984年发布，一台突破性且价格适中的一体式计算机，用的不是命令行界面，而是图形界面。

26 图形用户界面GUI

26.1 图形用户界面GUI

上集我们说，苹果在1984年发布的Macintosh，是普通人可以买到的第一台图形用户界面的计算机，还带一个鼠标。那时的计算机全是命令行的，图形界面是个革命性的进展。

我们不需要记住指令，只需要在屏幕上点击即可完成想要的功能，计算机突然变直观了，不仅仅是计算机科学家，普通人也能用计算机。这就是图形用户界面GUI。

人们认为是Macintosh把图形用户界面（GUI）变成主流，但实际上图形界面是几十年努力的结果。

26.2 恩格尔巴特

恩格尔巴特设计了一个现代化的计算机，包括图形界面、鼠标等等。1968年，恩格尔巴特演示了这台计算机，它可以进行视频通话、多人文档操作和多窗口等等。

不过由于这种设计太过超前了，最终还是失败了。但是他对于计算机科学家思维上的启发却是实在的，恩格尔巴特因此于1997年获得图灵奖。

26.3 施乐奥托与WIMP桌面

第一台真正带GUI的计算机是施乐奥托，于1973年完成。施乐计算机将2D屏幕当作“桌面”，用户可以打开多个程序，每个程序都在一个框里，叫“窗口”。窗口可以重叠，挡住后面的东西。还有桌面组件，比如计算器和时钟。这台计算机的发明者用窗口、图标、菜单和指针来设计界面，因此叫WIMP桌面。

施乐奥托团队大约制造了2000台，有的在施乐公司内部使用，有的给大学实验室，从来没有商业出售过。施乐卖的是印刷机，但在文本和图形制造工具领域也有领先。例如，他们首先使用了“剪切”“复制”“粘贴”这样的术语。施乐公司后来开发的“施乐之星系统”，不过依然过于超前并且价格昂贵，而没有流行。

26.4 苹果和微软

苹果公司的乔布斯看到了施乐团队作品的闪光之处，于是和施乐团队合作。苹果公司先后发布了Apple Lisa和Macintosh（1980年代），前者由于太贵没有太多人购买，后者在市场上火爆，可以说是第一台商业图形用户界面的计算机。

不幸的是，苹果公司的产品虽然大受欢迎，但是因为没有人在苹果电脑上制作软件，所以销量逐渐下来了。乔布斯与苹果公司股东关系愈发紧张，不久被苹果公司赶了出来。

在这期间，微软公司的Windows1.0出现了，并且站稳了市场，十年内，95%的个人计算机都有微软的Windows。刚开始的Windows系统还不像苹果一样有GUI，不过后来微软开发了面向消费者的GUI操作系统——Windows95，Windows95系统有许多至今还在用的设计，比如开始菜单、任务栏和Windows文件管理器。

现在的系统，无论是Windows、Linux还是Mac，都是施乐奥托WIMP的变化版本。未来，计算机科学家和界面设计师会设计更强大的GUI。

27 3D图形

之前讲的图形界面都是二维的，但我们生活的世界是3维的，本节课我们讲三维图形。

27.1 图像投影

三维空间用到的是三维坐标，但是计算机无法表示三维坐标，所以要将三维图形投影到二维上来。三维投影有很多，比如正交投影、透视投射。

PS：透视投影可以类比现实生活中看马路会交于一点的情景。

如果想画立方体这种简单的几何图形，直线就够了；但更复杂的图形，三角形更好，如下图所示。在3D图形学中
我们称三角形为“多边形”(Polygons)，一堆多边形的集合叫 网格。网格越密，表面越光滑，细节越多，但意味着更多计算量。

PS：为什么使用三角形：是因为空间3个点可以确定唯一一个平面，具体请参考本节视频内容。

设计三维图形时，设计师要考虑细节的程度，如果过于复杂的细节的图形（三角形过多），就会导致帧率下降，画面卡顿。

27.2 图像填充

填充图形的经典算法叫扫描线渲染，就是通过一条线的交点来进行图形填充，当然这样可能导致边缘不精细，边缘出现锯齿形状。一种减轻锯齿的方法叫抗锯齿。也就是如果在三角形内部的方块，直接填充，在交线处，虚化填充。抗锯齿在计算机文字和图标中大量使用。

图像里面不同的物体有的会遮挡，这很常见。要渲染图片时，类似排序算法，计算机根据由远到近一次渲染覆盖，这叫“画家算法”，因为画家也是先画背景，然后再画更贴近的东西。

此外，还有深度缓存算法，就是根据距离一步步地加载最小的数字到对应的格子中。最后得到的图形，既有哪里需要填充图块，也有哪种颜色是最终需要填充的。

3D游戏里面有个优化叫背景剔除，也就是三角形的两面，游戏只加载玩家能看到的那一面，另一面不加载，这样若穿到另一面，容易产生透视BUG。比如穿越火线里面的卡BUG进行透视就是这样的。

27.3 明暗处理

我们讲灯光，也叫明暗处理。我们将图像，经过平面着色，也就是根据光源，给不同的部分设置不同程度的阴影，达到三维的目的。

此外，还有高洛德着色和冯氏着色法，帮助形成更好的三维图像。

27.4 纹理与图像处理单元

此外，图像的纹理也有多种算法，最简单的是纹理映射。以上这些图像算法，我们可以通过硬件加速得到更快的运算。此外，可以将图像分块，然后多块并行渲染。CPU不是为此设计的，因此图形运算不快，所以计算机工程师为图形做了专门的处理器——GPU“图形处理单元”，就是专门用于图形渲染和处理的。GPU在显卡上，周围有专用的RAM(显存)，所有网格和纹理都在里面，让 GPU 的多个核心可以高速访问。现代显卡，如 GeForce GTX 1080 TI有3584个处理核心，提供大规模并行处理，每秒处理上亿个多边形！

28 计算机网络

早期的计算机和网络是分开的，不过随着时间发展，第一个计算机网络出现了。计算机网络的发展，帮助人们有了更快的信息交互方式，极大地改变了人们的生活，这节课我们就来讲计算机网络的发展。

第一个计算机网络出现在1950-60年代，通常在公司或研究室内部使用，为了方便信息交互，这叫“球鞋网络”。第二个好处是能共享物理资源，比如与其用多台打印机，不如用一台联网的打印机。计算机近距离构成的小型网络，叫局域网，简称LAN。局域网能小到是同一个房间里的两台机器或大到校园里的上千台机器。

尽管开发和部署了很多不同 LAN 技术，其中最著名的局域网是“以太网”，开发于1970年代，至今仍被使用。以太网是这样设计的，将要组成网络的计算机用电缆相互连接，如果一台计算机想要发送数据时，就将数据以电信号形式传到电缆，以太网链路上任何一台计算机都可以看见数据。

为了解决定向问题，以太网需要为每台计算机设置唯一的媒体访问控制地址，简称MAC地址。这个数据放在数据头部作为数据的前缀发送到网络中，所以，计算机只需要监听以太网电缆只有看到自己的 MAC 地址，才处理数据。这运作得很好，现在制造的每合计算机都自带唯一的MAC地址用于以太网和无线网。

多台电脑共享一个传输媒介，这种方法叫“载波侦听多路访问”，简称CSMA。载体指运输数据的共享媒介，以太网数据传输的载体是铜线，WiFi的载体是无线空间。很多计算机同时侦听载体，所以叫“侦听”和“多路访问”。载体传输数据的速度叫“带宽”。

不过问题是，在同一链路上传输，可能会出现同时发送的情况，造成数据冲突。最明显的解决办法是停止传输，然后等待后再传输。但是这个有一个问题，就是如果冲突过多的话，就会产生麻烦。以太网有个简单有效的解决办法，就是在同一个等待时间下加一个随机时间。此外，还有指数退避法，就是当再次检测到冲突的话，就等待原来的双倍的时间。以太网和WiFi都用这种方法，很多其他传输协议也用。

此外，用同一根网线链接整个区域的计算机还是不可能的，我们需要减少同一载体中设备的数量，载体和其中的设备总称“冲突域”。为了减少冲突 我们可以用交换机(Switch)把它拆成两个冲突域：

交换机位于两个更小的网络之间，必要时才在两个网络间传数据。交换机会记录一个列表写着哪个 MAC 地址在哪边网络。大型网络(包括最大的互联网)的底层也是类似的原理。

这些大型网络有趣之处是：从一个地点到另一个地点通常有多条路线。这就带出了另一个话题——路由。连接两合相隔遥远的计算机或网路，最简单的办法是分配一条专用的通信线路（早期电话系统就是这样运作的），这叫”电路交换”，因为是把电路连接到正确目的地，能用倒是能用，但不灵活而且价格昂贵，因为总有闲置的线路，好处是如果有一条专属于自己的线路你可以最大限度地随意使用，无需共享。因此军队，银行和其他一些机构，依然会购买专用线路来连接数据中心。

交换机是连接若干个主机的机器，用来解决冲突域问题。

路由器是连接主机、路由器或交换机的机器，用来构建数据传输的线路。

传输数据的另一个方法是“报文交换”。“报文交换”就像邮政系统一样，不像之前A和B有一条专有线路，消息会经过好几个站点，如下图所示：

每个站点都知道下一站发哪里因为站点有表格，记录到各个目的地，信件该怎么传。报文交换的好处是：可以用不同路由使通信更可靠更能容错，对于上面的例子，若HOP2站点被破坏了，由图容易知道还有很多其他路线可走。在这个例子中，各个城市HOP就像路由器一样，消息沿着路由跳转的次数叫做“跳数”。记录跳数很有用，因为可以分辨出路由问题，如果看到某条消息的跳数很高就知道路由肯定哪里错——这被称为“跳数限制”。

报文交换的缺点之一是有时候报文比较大会堵塞网络，因为要把整个报文从一站传到下一站后才能继续传递其他报文。传输一个大文件时，整条路都阻塞了，导致即便你只有一个1KB的电子邮件要传输，也只能等大文件传完，或是选另一条效率稍低的路线。解决方法是 将大报文分成很多小块，叫”数据包“。就像报文交换，每个数据包都有目标地址，因此路由器知道发到哪里。报文具体格式由”互联网协议”定义，简称IP，这个标准创建于 1970 年代。每台联网的计算机都需要一个IP地址。数百万台计算机在网络上不断交换数据，瓶颈的出现和消失是毫秒级的，路由器会平衡与其他路由器之间的负载，以确保传输可以快速可靠，这叫”阻塞控制“。

有时，同一个报文的多个数据包会经过不同线路，到达顺序可能会不一样，这对一些软件是个问题。幸运的是，在IP 之上还有其他协议，例如：TCP/IP可以解决乱序问题。

将数据拆分成多个小数据包，然后通过灵活的路由传递，非常高效且可容错，如今互联网就是这么运行的，这叫”分组交换“。有个好处是：它是去中心化的，没有中心杈威机构，没有单点失败问题。

如今，全球的路由器协同工作，找出最高效的线路，用各种标准协议运输数据，比如“因特网控制消息协议(ICMP)”和”边界网关协议(BGP)“。世界上第一个分组交换网络以及现代互联网的祖先是ARPANET。

29 互联网

任意计算机都和一个巨大的分布式网络连接在一起，称为互联网（Internet）。

29.1 数据在互联网上的传输过程

当你在家中通过计算机观看网上视频时，你的计算机首先需要连接到局域网LAN，这个局域网是由家里WiFi路由器连接的所有设备组成的。然后家里的局域网再通过路由器连接到广域网（Wide Area Network，WAN），广域网的路由器一般属于你的互联网服务提供商（Internet Service Provider，ISP）。在广域网里，首先会有一个区域性路由器，比如覆盖你所在街区的一个路由器，然后该路由器会连接到一个更大的广域网中，比如覆盖你所在的城市，可能再跳跃几次，最终会到达互联网主干，一般由一群超大型、带宽超高的路由器组成。

即首先会连接到你家里的WiFi路由器构建的局域网，然后该路由器再连接到ISP提供的广域网中，该广域网是由很多层层递进的路由器构成的。

比如要从YouTube中获得视频，数据包首先会到达互联网主干，沿着主干到达对应保存该视频文件的YouTube服务器，可能这里会跳4次到达互联网主干，然后跳两次穿过互联网主干，最终再跳4次到达YouTube服务器，所以总共会跳跃10次。

我们可以通过traceroute来看跳跃了几次：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Windows上的Traceroute
1.按开始按钮
2.输入“ CMD”，然后按“ Enter”
3.在命令提示符下，键入“ tracert dftba.com”

在Mac上的Traceroute
1.点击“转到”下拉菜单
2.点击“实用程序”
3.打开终端
4.键入“ traceroute dftba.com”

Linux上的Traceroute
1.通过键入CTRL + Alt + T打开终端
2.输入：“ traceroute dftba.com”

但是数据包到底是怎么传递过去的呢？如果传输时数据包丢失了，会发生什么？当我们在浏览器中输入网址时，浏览器怎么知道服务器的地址是什么呢？

就像上节介绍的，互联网是一个巨大分布式网络，如果要发送的数据较大，分组传输就会将数据拆成一个个较小的数据包进行传输。其中数据包要想在互联网上进行传输，就要符合互联网协议（Internet Protocol，IP）。

类似于邮寄手写信一般，每封信都需要一个地址，并且地址必须是唯一的，并且信的大小和重量也是有限制的，否则信件就无法送达。

29.2 用户数据报协议UDP

IP数据包也是如此，因为IP是一个非常底层的协议，数据包的头部只包含目标地址（IP地址），意味着当数据包到达对方电脑时，计算机不知道要把数据包交给哪个程序（比如QQ或微信或者浏览器），因此需要在IP之上，开发更高级的协议。

最简单常见的协议称为用户数据报协议（User Datagram Protocol，UDP）。UDP也有头部，位于data payload里面，在data之前。UDP头部里面包含了很多有用的信息，其中之一就是端口号（Port Number），每个想访问网络的程序都要向操作系统申请一个端口号。所以当数据包到达时，接收方的操作系统会读取UDP头部里的端口号，来确定该数据包是要交给哪个软件的。

示例：每个想访问网络的程序，都要向操作系统申请一个端口，例如QQ会申请端口3478，当一个数据包到达时，接收方的操作系统会读 UDP 头部，读里面的端口号，如果看到端口号为3478，就把数据包交给QQ。

简单来说，IP协议通过IP地址把数据包送到正确的计算机内；UDP通过数据包里的端口号送到正确的程序。

同时UDP的头部中还有校验和（Checksum），通过对数据求和来检查数据是否正确。假设UDP数据包里原始数据是89 111 33 32 58 41， 最简单的计算校验和的方式就是，在发送数据包之前，计算机会把所有数据加在一起，计算出校验和364。在UDP中，校验和是以16位形式存储的，如果计算出来的和超过16位能表示的最大值，则高位数会被丢弃，只保留低位。当接收方计算机接收到这个数据包时，也会重复以上过程，如果计算出来的校验和和UDP中保存的校验和相同，代表数据是正常的，否则数据是出错的。

29.3 传输控制协议（Transmission Control Protocol，TCP）

但是，UDP不提供数据修复或数据重发机制，当接收方知道数据损坏后，一般只是丢弃这个数据包。并且当发送方使用UDP协议发送数据包时，是无法得知数据包是否到达目的地的。

有些程序并不在意以上问题，因为UDP十分简单且快速。比如视频通常使用UDP协议，当数据包丢失时，也就造成视频卡顿。

但是有些数据不能接受数据包丢失的问题，比如发送电子邮件时，所有数据必须到达，所以就需要传输控制协议（Transmission Control Protocol，TCP）。和UDP一样，它的头部也保存在数据之前，人们通常将IP协议和TCP协议统称为TCP/IP协议。TCP的头部中也包含端口号和校验和，并且TCP协议还提供更高级的功能(这里只简单介绍几个重要的)：

1. TCP的数据包是有序号的
   使得接收方可以通过这个序号将数据包排成正确顺序，即使到达时间不同。
2. TCP要求接收方收到数据包并校验和检查无误后，要给发送方发送一个确认码（Acknowledgement，ACK），代表数据包已经正确接收。
   当发送方接收到确认码后，就知道上一个数据包成功抵达了，发送方就会发送下一个数据包，如果这次发送方过了一段时间没有接收到确认码，则会重新发送一次。即使这里只是由于确认码延迟了，使得接收方那里有重复的数据包，但是通过序列号，可以直接删除重复的数据包。

并且数据包并不会一个个数据包进行传输，而是同时发送多个数据包，同时接收多个确认码，这将大大提高效率，不用浪费时间等待确认码。并且通过确认码的成功率和来回时间，我们可以推测网络的拥塞程度，TCP通过这个信息，来调整同时发包数量来解决拥塞问题。

简而言之，TCP可以处理乱序和丢包问题，并且可以根据拥塞情况自动调整传输率。但是由于确认码数据包的存在，使得TCP需要传输的数据包数量翻了一倍，并且并没有传输更多信息，这对时间要求很高的程序代价太高，所以这类程序就会使用UDP协议。

29.4 域名DNS

当计算机访问一个网站时，需要两个东西：① IP地址（目标网站的地址）和 ② 端口号（对应于你使用的计算机浏览器）。

但是通过IP地址访问网站十分不方便，所以互联网提供一个特殊服务，来将域名（Domain Name）和IP地址一一对应，称为域名系统（Dimain Name System，DNS），一般DNS服务器都是由ISP提供的。当你在浏览器中输入网站域名时，浏览器就会去访问DNS服务器，DNS就会去查表，如果域名存在，则会返回浏览器对应IP地址，然后浏览器就会给这个IP地址发送TCP请求。

因为当前域名特别多，所以DNS不会将其保存成列表形式，而是将其保存成树状结构。最顶层是顶级域名（Top Level Domain，TLD），比如.com和.gov；下一层是二级域名（Second Level Domain）， 比如google.com和dftba.com；再下一层是子域名（Sub-domain），比如images.google.com等等。由于这个树结构特别大，因此这些数据分布在很多DNS服务器上，不同服务器负责树的不同部分。

• 物理层：过去两集里，我们讲了线路里的电信号，以及无线网络里的无线信号，这被称为“物理层”。
• 数据链路层：负责操控“物理层”，数据链路层有：媒体访问控制地址(MAG)、碰撞检测、指数退避以及其他一些底层协议。
• 网络层：负责各种报文交换和路由。
• 传输层：负责在计算机之间进行点到点的传输，而且还会检测和修复错误；本小节的UDP和TCP协议都属于本层。
• 会话层：会使用TCP和UDP来创建连接，传递信息，然后关掉连接。

以上是开放式系统互联通信参考模型（Open System Interconnection model，OSI）下的5层，这个框架将网络通信划分成了很多层，每一层处理各自的问题。这种抽象可以使得分工改进多个层，而无需考虑整体复杂性。并且OSI还有额外两层：表示层（Presentation Layer）和应用层（Application Layer），在下一节中进行介绍。

30 万维网

前两节深入讨论了电线 信号 交换机 数据包路由器以及协议，它们共同组成了互联网。这一节将向上抽象一层，来讨论万维网（World Wide Web）。万维网和互联网的概念完全不同，万维网是运行于互联网之上的，还有其他比如Skype、Instagram等也是运行在互联网之上的。互联网是用来传输数据的管道，各种程序都会使用到，其中传输最多数据的程序就是万维网，我们可以使用特殊的程序——浏览器（Web Browser）来访问万维网。

30.1 超链接

万维网的最基本单位是单个页面，页面里面包含内容，也有访问其他页面的链接，这些链接称为超链接（Hyperlink）。这些超链接形成巨大的互联网络，这也是万维网名字的由来。

现在说起来觉得很简单，但在超链接做出来之前，计算机上每次想看另一个信息时，你需要在文件系统中找到它或是把地址输入搜索框，有了超链接，你可以在相关主题间轻松切换。

并且由于文字超链接的强大，它有一个特殊的名字——超文本（Hypertext）。如今超文本最常指向的是另一个页面，这些页面会被获取并由浏览器进行渲染。

为了使网页能够互相连接，每个网页需要一个唯一的地址，这个地址称为统一资源定位器（Uniform Resource Locator，URL），比如thecrashcourse.com/courses就是一个页面URL。

当你访问thecrashcourse.com网址时，计算机首先会进行DNS查询，这里输入一个域名，然后DNS就会返回给浏览器对应的计算机IP地址。然后浏览器就会打开一个TCP连接到这个IP地址对应的计算机上，而这个计算机运行着一个特殊的软件——网络服务器（Web Server），网络服务器的标准端口是80。此时，你的计算机就连接到了thecrashcourse.com对应的服务器了，下一步是向服务器请求courses 页面，这里就会用到超文本传输协议（Hypertext Transfer Protocol，HTTP）。

30.2 超文本传输协议 HTTP

HTTP的第一个标准是1991年创建的HTTP 0.9，只有一个指令GET 。因为这里我们想要获取courses页面， 我们可以直接向服务器发送指令GET/courses， 该指令以ASCII编码发送到服务器，服务器会返回该网址对应的页面，然后浏览器就会将其渲染到屏幕上。如果用户点击了另一个链接，计算机就会重新发送一个GET请求。

在之后的版本中，HTTP添加了新的状态码，会将其放在请求页面的前面，比如状态码200表示网页被正确找到了，状态码400-499代表客户端出错。

因为超文本的存储和发送都是以普通文本形式进行的，编码可能是ASCII或者UTF-8，这样就无法表明什么是链接，什么只是普通的文本了，所以必须开发一种标记方法，因此出现了超文本标记语言（Hypertext Markup Language，HTML），第一代HTML创建于1990年的0.8版本，有18种指令。

如果把这些文字存入记事本或文本编辑器，然后文件取名test.html，就可以拖入浏览器打开。当然，如今的网页更复杂一些，最新版的：HTML，HTML5，有100多种标签（图片标签，表格标签，表单标签，按钮标签，等等），还有其他相关技术（比如 层叠样式表CSS、JavaScript）这里就不展开讲了。

综上，网络浏览器可以和网络服务器沟通，不仅获取网页和媒体，并且还负责显示。

随着后期万维网日益繁荣，人们越来越需要搜索。起初人们会维护一个目录，来链接到其他网站，但是随着网络越来越大，人工编辑目录变得很不方便，所以开发了搜索引擎。

最早的搜索引擎是JumpStation，它有3个部分：

1. 通过爬虫来将新链接添加进自己的列表中。
2. 不断扩张的索引，用来记录访问过的网页上出现了哪些词。
3. 查询索引的搜索算法，比如输入了某个关键字，则包含这个关键字的网页就会显示出来。

早期的搜索引擎的排名方式直接取决于搜索词在页面上的出现次数，但是有的网页会通过在页面中重复该关键字来提高排名。Google成名的很大原因就是提出了一种算法来解决这个问题，与其信任页面上的内容，搜索引擎会看其他网页有没有连接到这个网页。

最后提一个概念——网络中立性（Network Neutrality），它指的是要对所有数据包都平等对待，速度和优先级都应该一样。

31 计算机安全

31.1 保密性、完整性和可用性

计算机安全的范围和计算能力的发展速度一样快，我们可以把计算机安全，看成是保护系统和数据的保密性、完整性和可用性。

• 保密性（Secrecy）：只有有权限的人才能读取计算机系统和数据，比如黑客泄露别人的信用卡信息，就是攻击保密性。
• 完整性（Integrity）：只有有权限的人才能使用和修改系统和数据，比如黑客假冒你发送邮件，就是攻击完整性。
• 可用性（Availability）：有权限的人应该随时可以访问系统和数据，拒绝服务攻击（DDOS）就是黑客发送大量的假请求到服务器上，使得网站很慢或者直接挂掉，这就是攻击可用性。

为了实现这三个目标，安全专家会从抽象层面想想敌人可能是谁，这个称为威胁模型分析（Threat Model）。模型会对攻击者有个大致的描述：能力如何、目标是什么、可能使用什么手段。攻击手段又称为攻击矢量（Attack Vector）。威胁模型分析能够让你为特定情境做好准备，不被可能的攻击手段所淹没。换句话说，要怎么保护，具体看要对抗谁。

假设你想确保笔记本计算机的“物理安全”，你的威胁模型是”好管闲事的室友”。

通常威胁模型分析中，会以能力水平进行区分。在给定的威胁模型下，安全架构师要提供解决方案，来保持系统安全。

31.2 安全保护机制

有很多保护计算机系统、网络和数据的方法。很多安全问题可以总结成两个问题：

1. 你是谁？
2. 你能访问什么？

权限应该给适合的人而拒绝错误的人，所以为了区分谁是谁，我们使用身份认证（Authentication）来让计算机得知使用者是谁。通常身份认证有三种，各有利弊：

1. 你知道什么：这个是基于某种只有用户和计算机知道的秘密，比如用户名和密码。这是如今使用最广最容易实现的方法。但是如果黑客知道了你的密码就惨了，或者可以通过暴力攻击试了密码的所有可能来获取你的密码，有些系统会在你尝试若干次错误后阻止你继续尝试。即使增长密码也很容易破解，所以现在很多网站都要求大小写字母加特殊字符，来增加可能的密码。
2. 你有什么：这是基于用户特定的物体，比如钥匙和锁。这种方法可以避免被人猜中密码的问题，而且通常需要人在现场，所以远程攻击就更加困难了。
3. 你是什么：这是基于你，通过你自己的特征展示给计算机来进行验证，比如指纹识别器和红膜扫描仪，这些方法特别的安全，但是最好的识别技术十分昂贵。“你知道什么”和“你有什么”是确定性的，但是来自传感器的数据每次都不相同，所以“你是什么”是概率性的，系统可能认不出你，或者将其他人认成了你。并且这种方法另一个问题就是无法重设，你无法修改自己的指纹或者虹膜。

每种方法都有优缺点，一般建议使用两种或两种以上的认证方式。

32.3 访问控制

当系统知道了你是谁，接下来就需要知道你能访问什么，这个称为访问控制（Access Control），因此需要一个规范，来说明谁能访问什么、修改什么和使用什么。这个可以通过权限（Permission）或访问控制列表（Access Control List，ACL）来实现，其中描述了用户对每个文件、文件夹和程序的访问权限。

1. 读权限：允许用户查看文件内容。
2. 写权限：允许用户修改文件内容。
3. 执行权限：运行用户运行文件，比如程序。

有些阻止需要不同层次的权限，则ACL的正确配置就十分重要。假设我们有三个访问级别：公开、机密和绝密。有个经典模型称为Bell-LaPadula模型，其中包含两条规则：

1. 用户不能read up，即不能读等级更高的信息。
2. 用户不能write down，即用户不能写更低权限的信息，这样能避免高级别的信息不会泄漏到低级别的文件中。

通过身份认证和权限控制，可以让计算机知道你是谁和你能访问什么，但是必须先保证做这些事的软硬件必须是可信的。但是仍然无法保证程序或计算机系统的安全，因为安全软件在理论上可能是安全的，但是实现时可能会不小心留下漏洞。但是我们有办法减少漏洞出现的可能性，比如一发现漏洞就马上修补。

大部分漏洞都是具体实现时出错了，所以为了减少执行错误，就要减少执行。系统级安全的圣杯之一是“安全内核”或“可信计算基础”：一组尽可能少的操作系统软件，这个安全性是接近可验证的。

构建安全内核的挑战在于，要决定内核应该有什么（代码越少越好）。当最小化代码数量后，要是能保证代码是安全的，那就很好了。现在最好的验证代码安全性的手段是独立安全监察和质量验证（Independent Verification and Validation），让一群安全行业内的软件开发者来审计代码，这也是为什么安全型代码几乎都是开源的。

但是即使这样，还是有可能被黑客攻破，因此程序开发者需要控制损失的最大程度，这个称为隔离（Ioslation）。要实现隔离，可以“沙盒”（sandbox）程序，操作系统通过给每个程序独立的内存块，使得别的程序是无法触及的，这样就能把程序放到沙盒中，即使沙盒被破坏了，也不会影响别的程序执行。并且一台计算机可以运行多个虚拟机（Virtual Machine），使得每个虚拟机都在自己的沙盒中。

32 黑客与攻击

这里只介绍一些入侵原理，提供一个大概的概念。

32.1 社会工程学

黑客入侵最常见的方式不是通过技术，而是欺骗别人，这个称为社会工程学（Social Engineering），通过欺骗别人来让人泄露秘密，或让人配置电脑系统来变得易于攻击。最常见的攻击是网络钓鱼（Phishing），其次还有假托（Pretexting），攻击者给某个公司打电话，假装是IT部门的人，攻击者的第一通电话一般会叫人转接，这样另一个接的时候，电话看起来就像内部的，然后让别人把电脑配置得易于入侵，或者让他们泄露机密信息，比如密码或网络配置。

邮件里带木马（trojan horse）也是常见手段，木马通常会伪装成无害的东西，比如照片或发票，但实际上是恶意软件，有的会偷数据，有的会加密文件。

32.2 暴力破解、NAND镜像、缓冲区溢出

如果攻击者无法用木马或电话欺骗，攻击者只能被迫使用其他手段，方法之一就是暴力破解，尝试所有可能的密码，直到进入系统，大多数现代系统会加长等待时间来抵御这种攻击。现在出现了一种攻破方法称为NAND镜像，如果能物理接触到电脑，可以往内存上接几根线，复制整个内存，然后暴力尝试密码，知道设备让你等待，这时只要把复制的内容覆盖掉内存，就无需等待，继续尝试密码。

32.2.1 缓冲区溢出漏洞

如果无法物理接触到设备，就需要远程攻击，比如通过互联网，这一般需要攻击者利用系统漏洞，来获得某些能力或访问权限，称为漏洞利用（Exploit）。一种常见的漏洞利用叫缓冲区溢出（Buffer Overflow），这里的缓冲区是指预留的一块内存空间，比如我们在系统登录界面输入用户名和密码，而系统是用缓冲区来存储输入值的，假设缓冲区大小为10，并且缓冲区前后肯定还有其他数据，当用户输入用户名和密码时，这些值就会被复制到缓冲区中来进行验证，而该方法会溢出缓冲区，比如输入超过10个字符的密码，会覆盖掉相邻的数据，有时会让程序或系统崩溃，因为重要值被垃圾数据覆盖掉了。这里只是让系统崩溃，但是攻击者可以输入有意义的新值到程序的内存中，比如把is_admin标志位的值改为true，有了任意修改内存的能力，黑客就可以绕过登录这类东西，甚至使用那个程序劫持整个系统。

32.2.2 缓冲区溢出的组织方法

有许多方法阻止缓冲区溢出，最简单的方法就是复制到内存之前先检查长度，称为边界检查（Bounds checking），许多现代编程语言都自带边界检查，程序也会随机存放变量在内存中的位置，这样黑客就不知道应该覆盖内存的哪部分，使得更容易让程序崩溃，而不是获得访问权限。程序也可以在缓冲区后，预留一些不用的空间，然后跟踪里面的值，看是否发生变化，来判断是否有攻击，这些不用的内存空间称为金丝雀（Canaries）。

32.3 代码注入

另一种经典手段是代码注入（Code Injection），最常用于攻击用数据库的网站。下面是一个很简单的示例，我们会用“结构化查询语言”，也叫SQL（一种流行的数据库API）。

假设网页上有登录提示，当用户点击“登录”，输入文本就会发送服务器，服务器就会运行代码，检查用户名是否存在，如果存在就看密码是否匹配。为此服务器会执行一段sql查询代码，比如

1

SELECT password FROM users WHERE username='___';

这里语句就是要从users表中查找username为___的密码password。 这里的___就是用户输入的用户名。由此攻击者就能把sql命令输入到用户名中，比如whatever';DROP TABLE users;'，这时上面的查询语句就会变成

1

SELECT password FROM users WHERE username='whatever';DROP TABLE users;';

如果服务器存在用户名wharever，数据库就会返回密码， 当然我们无法得知密码是什么，所以服务器会拒绝我们；如果不存在用户名wharever，服务器会返回空密码或者直接错误，服务器也会拒绝我们。 但是我们关心的是后面的代码DROP TABLE users;，这个是我们注入的命令，这个命令是删掉users这张表。如今几乎所有服务器都会防御这种手段。

程序员需要认识到从外界输入的信息都是危险的，必须要好好检查，很多用户名和密码表单，不会让你直接输入特殊符号，比如分号或括号，来作为第一道防御。好的服务器也会清理输入，比如修改或删除特殊字符，然后才放到数据库查询语句中。

当软件制造者不知道的新漏洞被发现时，称为0day漏洞（Zero Day Vulnerability），黑客就会抢在白帽程序员做出补丁之前尽可能利用漏洞。

如果有足够多的电脑有漏洞，让恶意程序可以自动地在电脑之间互相传播，称为蠕虫（Worm）。如果黑客拿下大量电脑，这些电脑可以组成僵尸网络（Botnet），可以用于很多目的，比如发大量垃圾邮件等，用别人电脑的计算能力来挖比特币，或发起DDOS来攻击服务器。DDOS就是僵尸网络里的所有电脑发一大堆垃圾信息到服务器上，造成服务器的阻塞。

33 加密

这节将介绍计算机安全中最常见的防御形式——密码学。

33.1 加密算法

为了加密信息，要用加密算法（Cipher）将明文转换为密文，除非知道如何解密，否则密文看起来就是一堆乱码，这种将明文专为密文的过程叫做加密（Encryption），而相反过程称为解密（Decryption）。

加密算法早在计算机出现之前就存在了，凯撒使用我们如今称为凯撒加密（Caesar Cipher）的方法来加密私人信件，他会将信件中的字母向前移动3个位置，所以a变成d，brutus变成euxwxv。为了解密，接受者要知道使用了什么算法，以及偏移的字母位数作为钥匙。

33.1.1 替换加密

有一大类算法称为替换加密（Substitution Cipher），凯撒密码就是其中一种，算法把每个字母替换成其他字母。但是有一个巨大的缺点是，字母出现的频率是不一样的，比如英语中字母E出现的频率最高，如果将E替换成了X，则密文中X的出现频率就会很高，通过统计字母频率，就有可能破译密码。

33.1.2 移位加密

另一类加密算法叫移位加密（Permutation Cipher），比如列移位加密（Columnar Transposition Cipher），我们这里将明文填入网格，比如选择5x5大小的网格。为了加密信息，我们换一个顺序来读取，比如从左边开始，从下往上一次读一列，就会变成图2的形式，这样加密后的字母排列是不同的，，但是字母出现的频率没有变化。这里解密的关键是要知道读取方向和网格大小。

33.2 硬件加密

到了1900年代，人们用密码学做了加密机器，比如德国的Enigma用来加密通讯信息。Enigma是一台类似打字机的机器，包含键盘和灯板，这两个都有完整的字母表，而且它还有一系列转子，这些是加密的关键。首先我们看一个转子，它一面有26个接触点，代表26个字母，然后线会连接到另一面来替换字母，其实这个就是替换加密。但是Enigma更加复杂，它有更多的转子，一个转子的输出作为下一个转子的输入，并且转子还有26个起始位置，还可以按不同顺序加入转子，来提供更多字母替换映射。转子之后是一个叫反射器的特殊电路，它每个引脚会连接另一个引脚，并把信号发回转子，最后机器前方有一个插板，可以把输入键盘的字母预先进行替换来增加一层复杂度。图中显示的是输入H后，经过加密会输出L，因为线路是双向的，所以输入L也会被加密成H，所以加密和解密步骤是一样的，直接将密文输入机器就能得到对应的明文。

但是这个机器有个缺点，就是字母加密后，一定会变成另一个字母。

最后，为了让Enigma不只是简单的替换加密，每输入一个字母，转子就会转一格，这样比如你输入AAA，可能会输出BDK，映射会随着每次按键发生改变。

33.3 软件加密

随着计算机出现，加密从硬件转向了软件。

早期应用最广的加密算法是IBM和NSA于1977年开发的数据加密标准（Data Encryption Standard，DES），DES最初用56位二进制密钥，但到了1999年，计算机能将DES所有可能密钥都试一遍，所以DES不再安全。所以在2001年出现了高级加密标准（Advanced Encryption Standard，AES），AES使用128/192/256位密钥，使得暴力破解更加困难。

AES将数据切成一块一块，每块16个字节，然后用密钥进行一系列替换加密和移位加密，再加上一些其他操作，进一步加密信息，并且每块数据会重复这个过程10次以上。因为加密是需要时间的，如果使用过长的密钥或者加密次数过多，虽然更加安全，但是加密时间过长。目前AES被广泛应用，比如iPhone上加密文件，用WPA2协议在WiFi中访问HTTPS网站。

33.4 密钥交换

上面讨论的加密技术，都依赖于发送方和接收方都知道密钥，发送方用密钥进行加密，而接收方使用相同密钥来解密。现在我们需要某种方法，在公开的互联网上传递密钥给对方，但是这种方法不是很安全，密钥可能会被黑客拦截。解决方案就是密钥交换（Key Exchange），这是一种不发送密钥，但依然让两台计算机在密钥上达到共识的算法。我们可以使用单向函数（One-way Function）来实现，这是一种数学操作，很容易计算出结果，但是想从结果逆向推算出输入非常困难。

以颜料为例，我们可以很容易地将多个颜料混合得到最终的颜色，但是想要从最终颜色推算出用了哪些颜料进行混合是非常困难的。在这个例子中，我们的密钥就是一种独特的颜色。首先有一个公开的颜色，所有人都可以看到，然后对方和我自己各自选择一个秘密颜色，为了交换密钥，我先将我的颜色和公开颜色进行混合，然后发送给对方，并且对方也将他的颜色和公开颜色混合后发送给我，当我收到对方发来的颜色后，也将自己的颜色混入，并且对方也这么操作，这样我们就都得到了由3中颜色混合的一样的最终颜色，我们就可以将这个最终颜色当做密钥。

计算机中，我们可以用Diffie-Hellman密钥交换，在Diffie-Hellman中，单向函数是模幂运算，首先将一个数作为基数（Base），再拿另一个数作为指数（Exponent），然后将其结果除以第三个数就得到我们想要的余数：

这样，如果只给$B$、$M$和余数，很难知道指数$x$是多少，并且如果将数字变得很长，比如几百位，想要找到秘密指数几乎是不可能的。

在Diffie-Hellman中，我们有公开的数——基数$B$和模数$M$。为了安全地给对方发送信息，可按下面的步骤进行：

1. 我们选择一个秘密指数$X$，然后将计算结果$B^X \text{ mod } M$发送给对方，对方同样也选择一个秘密指数$Y$，然后也将计算结果$B^Y \text{ mod } M$发送给我。
2. 为了算出双方共用的密钥，我将对方的结果作为新的基数$B_Y$，再取$X$指数并求余，即$(B_Y)^X \text{ mod } M = (B^Y \text{ mod } M)^X \text{ mod } M = B^{XY} \text{ mod } M$，而对方也用相同方法进行计算，得到的也是相同结果，也即最终都是$ B^{XY} \text{ mod } M$。
3. 这样就可以将这个计算结果当做密钥，使用AES之类的加密技术进行加密通信。

33.5 对称加密和非对称加密

Diffie-Hellman密钥交换是建立共享密钥的一种方法，双方使用一样的密钥加密和解密信息，称为对称加密（Symmetric Encryption），因为加密和解密使用的密钥是一样的，前面的凯撒加密、Enigma和AES都是对称加密。

同样还存在非对称加密（Asymmetric Encryption），这里有两个不同的密钥，一个是公开的，一个是私有的，人们可以用公钥加密消息，而只有有私钥的人才能解密，所以知道公钥只能进行加密不能进行解密，而通过公钥加密后，也只能用私钥进行解密，所以它是不对称的。

非对称加密的形象化理解：

比如有一个带锁的箱子，我们可以将锁和箱子给别人，他将信息放入箱子并上锁后还给我，我就可以通过自己的钥匙将其打开。

过程反过来也是可以的，可以用私钥加密再用公钥解密，这个通常用于签名。服务器可以用私钥进行加密，任何人都可以用服务器的公钥进行解密来获得信息，这使得私钥相当于一个签名，只有有私钥的人才能进行加密，只有当公钥能正确解密，才能证明数据来自正确的服务器或个人(差不多是数字签名的原理)。

总之，① 公钥加密只能私钥解密；② 私钥加密只能公钥解密。

目前最流行的非对称加密技术是RSA。现在我们简单了解了现代密码学的所有”关键”部分：对称加密，密钥交换，公钥密码学。

当你访问一个安全的网站，比如银行官网：

图中绿色锁图标代表使用了公钥密码学，验证服务器的密钥，然后建立临时密钥，然后用对称加密保证通信安全。

【原文链接】
计算机科学速成课笔记 - 问夏的文章 - 知乎
读书笔记_计算机科学速成课——计算机网络（28、29、30） - 深度人工dazed的文章 - 知乎