Crash Course Computer Science(1-10)

在 B站 发现了一门好课《Crash Course Computer Science》(计算机科学速成课),虽然讲“速成”有点急功近利的意思,但这门课从计算机的历史开始讲起,几乎涵盖了从布尔逻辑到二进制、从硬件到软件、从编译原理到操作系统、从计算机网络到信息安全等等计算机科学的知识,作为一种科普,扩充知识面还是相当不错的。


P1 计算机的早期历史

计算机起源于人们计算的需求,最早被发明的是算盘,用来计算大数字,后来又出现了很多变种应用于各行各业,比如星盘让船可以在海上计算纬度,计算尺帮助计算乘除法,各种时钟用于计算日出、潮汐、天体位置等。而 Computer 一词,最初是指以计算为职业的人,后来才慢慢代指机器,其中以 1694 年发明的“步进计算器”最出名,它通过转动齿轮,带动数字加减过程的进位。1822年,Charles Babbage 提出了一种“差分机”,用于解决同一个公式下不同参数的计算,但这个项目最终失败了。在研究差分机期间,Charles Babbage 还构想了一种“分析机”可以做不同的运算,由于这个思想太超前,所以同样没有建成。但是分析机的思想奠定了 计算机可以自动完成一系列操作 这个基础。英国数学家 Ada 根据分析机的理念,设计了假想的程序,所以 Ada 被认为是世界上第一个程序员。

1880年,美国人口快速增长,人口普查局找到 Herman Hollerith 制造一款打孔卡片制表机,用传统机械来计数,用电动结构连接其他组件,大大提升了统计的数据。企业开始意识到计算的价值,之后 Hollerith 成立了制表机器公司,在1924年跟其他机械公司合并后,成为 国际商业机器公司(International Business Machines),即 IBM

步进计算器发明者 Gottfried Leibniz:

让优秀的人浪费时间算数简直是侮辱尊严,农民用机器能算得一样准。


P2 电子计算机

IBM 在 1944年 建造了哈佛马克一号机电计算机,它的基本组件是 继电器(一种用电控制的机械开关)。但继电器是机械结构,本身有重量,而且频繁开闭容易坏,所以效果不是很理想。早在 1904年,英国物理学家就发明了真空管(二级管),1906年美国发明家往真空管加入了控制电路,变成 三极管,达到了跟继电器一样的效果,从此计算机从机械走向了电子。世界上第一台通用,可编程的电子计算机是ENIAC,每秒能进行5000次加法运算。

三极管是其他电子器件的基础,但也不是完美的,经常烧坏,1947年,贝尔实验室发明了 晶体管,晶体管涉及的原理十分复杂,简单地说,就是两个电极之间有一种材料隔开,这种材料有时导电,有时不导电,这叫做 半导体晶体管通过改变导电性让电荷流动或不流动,达到跟继电器和三极管一样的效果。自那以后,IBM 建造了很多纯晶体管的计算机,计算机的体积也越来越小,最终让计算机从实验室走向办公室,再走向普通家庭。

有趣的是,晶体管的主要材料是硅,而彼时晶体管和半导体的开发集中在美国的加州,所以那个地方被称为硅谷。连晶体管发明者之一 William Shockley 都搬了过去,成立了肖克利半导体,里面的员工后来成立了仙童半导体,里面的员工后来又成立了英特尔。

从继电器到三极管再到晶体管,我们只做了一件事,那就是让开关开闭得更快,而且更不容易损坏,仅此而已。


P3 布尔逻辑和逻辑门

用两种状态表示信息叫做「二进制」,二进制可以用 true 和 false ,或者 1 和 0 来表示。计算机二进制的理论来自于布尔代数,在布尔代数中,变量的值只有 true 和 false 两种,运算法则有与、或、非、异或(AND、OR、NOT、XOR) 等。晶体管的控制信号表示输入,结果表示输出。用不同的晶体管组合来实现不同的布尔逻辑运算,这就是逻辑门。

  • 与(AND):两个值都为true,结果才为true
  • 或(OR):两个值只要有一个为true,结果才为true
  • 非(NOT):取反
  • 异或(XOR):两个值相同时,结果为 false ,否则为 true

P4 二进制

在十进制中,只有 0-9 十个数字,想表示更大的数字,加位数就行了,比如51,5在十位表示5个10。在二进制中只有 0 和 1 两个数,想表示更大的数字,也是加位数,这样一个位,我们称之为 比特(bit),比如 101,表示 1个1 + 0个2 + 1个4 = 5。二进制逢二进一,需要比十进制更多的进位,在计算机里,大部分操作都是八位八位这样子计算的,比如 11011010,所以我们把八个位称为一个 字节(byte),8位能表示256种不同的状态,在8位的游戏里,只有256种颜色,而16位是65536种。

就跟 1000克 = 1千克 一样,1000 byte = 1 kilobyte(千字节) = 1KB = 8000 bits ,以此类推, MB是百万字节(Mega), GB是十亿字节(Giga)。可是在计算机中,还有另外一种计算方式,那就是1千字节 = 2^10 byte = 1024 byte ,在 Linux 系统中为了加以区分,常用 1 KiB 这样的写法跟 1KB 区分开来,前者是 1024 byte,后者是 1000 byte。

为了表示负数,我们把第一位作为符号位,1表示负,0表示正。类似于科学计数法,在32位系统中,为了表示小数(浮点数),我们会取第2-9位作为指数,剩下23位作为有效位数。

除了数字,我们也要在计算机中表示文字。最简单的方法就是编码,ASCII(美国信息交换标准代码)发明于1963年,采用7位编码,可以表示128个不同的值,我们的每一个英文字母、数字和常用符号都对应一个值,比如 a 的编码是 97,当计算机遇到二进制97的编码时,就在显示器上显示 a 。随着计算机在全世界的流行,各个国家都推出了自己的字符编码,比如中国的 GBK,后来由于实在是太混乱了,Unicode 就诞生了——统一了所有编码的标准。Unicode是16位的,足以解决所有国家的编码问题。

就像用二进制编码来表示不同的字符一样,其他格式的二进制编码,如 .mp3 / .jpg / .avi 等等都是特定的二进制编码,用来编码音乐、图片和视频。所以,在计算机中,归根结底都是一长串的 0 和 1 罢了。


P5 算术逻辑单元(ALU)

我们用二进制表示数字,但真正重要的是有意义地处理数字。 算术逻辑单元(ALU) 是计算机负责运算的组件,ALU包含一个算术单元(Arithmetic)和一个逻辑单元(Logic)。算术单元我们可以用一个 XOR 和 一个 AND 组装成一个半加器,两个半加器组装一个全加器,再由全加器组装8位加法器。在8位加法器中,如果两个数相加超过了11111111,那么我们就称 溢出(overflow) 了。逻辑单元是负责逻辑运算的组件,比如 AND、OR、NOT、XOR,以及一些简单的数值测试(如一个数是否负数)。

在8位的ALU中,我们有两个8位的输入 A 和 B,以及一个4位的操作码告诉ALU应该执行什么操作,例如用操作码1000表示做加法,用1100表示做减法。ALU有一个8位的输出,以及一些标志输出,例如是否溢出标志,是否为零标志。


P6 寄存器和内存

算术逻辑单元可以对数字进行运算,而 寄存器和内存负责对结果进行保存。断电后丢失的存储称为随机存储(RAM),而断电后永久保存的称为持续存储(ROM)。用一个 AND 门,一个 OR 门,一个 NOT 门能制作一个 AND-OR 锁存器,可以存储一位。锁存器加一些额外的逻辑门,可以实现允许写入和允许读取,用这个来控制该位是否允许被读写。将8个一位锁存器并排,就可以存储8位的二进制数了,一组这样的锁存器称为 8位寄存器,当然,也有16位、32位或64位的寄存器。

在64位的寄存器中,每个锁存器都要有线来控制读写显得很麻烦,可以用矩阵来级联,矩阵一横一竖的交叉点即是特定位置的锁存器。这样,对于256位的寄存器,只需要35条线(1条数据线、1条允许写入线、1条允许修改线、16行+16列矩阵线用于选择锁存器)。例如,要选择第12行第8列的锁存器,可以启用对应的矩阵线,其交点就是目标,对应的矩阵线用二进制标记就是 1100 1000,这就是内存地址概念的由来。内存的一个重要特性是,可以随时访问任何位置,因此叫 随机访问存储器(RAM)

如今,无论是 SRAM,DRAM 或其他 RAM,从根本上都是矩阵层层嵌套,来存储大量信息罢了。


P7 中央处理器(CPU)

CPU负责执行程序。程序由一个个操作组成,这些操作称为 指令(instruction),如果是计算指令,CPU 会与 ALU 通信进行计算操作,如果是内存指令,CPU 会与内存通信,然后读写值。

程序可以放在内存里,指令也一样可以放在内存里。在内存里放一系列8位二进制数,前4位表示 操作码,即 CPU 应该执行的指令,后4位表示数据来自哪里(内存地址或某个寄存器ID),此外,我们还需要两个寄存器来组建我们的 CPU,一个负责追踪程序运行到哪里了,称为 指令地址寄存器,存储着当前指令的内存地址,另一个负责存当前指令,称为 指令寄存器

CPU 启动时,第一个步骤是 取地址,CPU会往指令地址寄存器上的地址去取需要的指令,例如在0地址取到00101110,这个数会被存入指令寄存器中。第二个步骤是 解码(decode),取到的00101110指令表示什么意思?需要由 控制单元 进行解码,控制单元本质上也是一些逻辑门的组合,它可以解释例如前4位0010是存储操作,后4位1110是应该存入的地方。知道该做什么操作和往哪里存储后,第三个步骤就可以 执行 了。CPU会有一些线连接到内存,打开内存对应地址的允许写入线,然后往里面写值。

执行完毕后,指令地址寄存器的值自动加一,一个CPU操作就完成了。像这样,CPU 取指令 → 解码 → 执行 → +1 这样一个周期称为 时钟周期。现代PC或手机一秒能达到10亿次时钟周期。所谓 超频降频,就是让 CPU 周期更快或更慢的技术。


P8 指令和程序

CPU的强大之处在于可编程,写入不同的指令就会执行不同的任务。

假设在内存地址0的地方,存放着00101100,前四位是操作码表示 LOAD_A ,后四位表示内存地址14,写成人类容易理解的内容是 LOAD_A 14,意思是,从内存地址14的位置取数放到寄存器A,内存地址14假设存放着数字3,那么数字3就会被放到寄存器A。同样的,内存地址1的地方,存放着 LOAD_B 15,CPU就会从内存地址15的地方取数放到寄存器B,最后,当 CPU 遇到 ADD B A,表示把寄存器B的值加到寄存器A上,遇到 STORE_A 13,表示把当前寄存器A的值存入内存地址13。这样就完成了一次加法。

除了 LOAD、ADD 和 STORE,CPU还有其他一些指令,SUB减法、JUMP跳转(用于实现循环和分支)、JUMP_NEGATIVE条件跳转、HALT停止(没有这个指令程序会一直执行下去),


P9 高级CPU设计

1.特殊指令

早期CPU是没有除法指令的,除法用减法来实现,例如16÷4,相当于16-4-4-4-4,这要花费很多个时钟周期。现代CPU设计中,从硬件层面上加了除法的指令,这样只要一个时钟周期就能搞定。此外,现代处理器有一些专门的电路来处理图像操作,解码压缩视频,加密等复杂运算,这些用标准操作要很多时钟周期,但一旦在硬件层面搞定,速度便大大提升。

2.Cache缓存

CPU的设计越来越巧妙和强大,以至于RAM读写的速度跟不上,RAM读写的这段时间,CPU白白空等完全就是浪费。于是人们在CPU和RAM之间加了个中间层——Cache缓存,CPU 从 RAM 拿数据时,不用一个个拿,而是一批批拿,即将用到的指令直接存在Cache缓存里,这样大大提高了读写效率。但这样带来了Cache和RAM数据不一致的问题,于是Cache会专门设计一个脏位,Cache存满后会检查脏位,把内容写回RAM后再清空缓存。

3.指令流水线

CPU有一种提升性能的方式,并行处理。我们知道,CPU一次完整的操作包含 取指 → 解码 → 执行。我们可以在执行一条指令的时候,先解码下一条待执行的指令,以及做取下下条指令的操作。这种方式叫 指令流水线。但这种方式会带来两个问题:

第一,依赖性的问题,比如你在读某个数据,而正在执行的指令会修改这个数据,因此,我们要弄清楚指令之间的依赖关系,必要时暂停指令流水线,避免出错。现代CPU会动态排序有依赖关系的指令,在学习Java volatile时,你可能听说过”重排序”的问题,就来源于CPU的指令依赖关系。
第二,JUMP跳转问题。一般的CPU会再JUMP前等待观察,一旦JUMP的结果出来,便往正确的分支塞指令。更高级的CPU会猜测JUMP到哪个分支的概率更大,叫 分支预测,提前用流水线塞指令,如果猜对了直接按流水线执行,否则就要先清空流水线,再重新塞正确的指令了。现代CPU分支预测的正确率能达到90%,所以效率棒棒哒。

4.多核处理器

现代CPU往往有多个核心,可以同时处理多个指令流。多核可以同时共同参与运算,提升效率也是很明显的。当多核也不够时,为啥不考虑下多CPU呢?中国国家超算中心的超威·太湖之光超级计算机就有 40960 个 CPU,每个 CPU 有 256 个核心,是世界上最快的计算机。


P10 早期的编程方式

程序需要加载进内存。可能你已经知道,早期的编程都是通过纸带打孔的方式,这种方式其实最早来源于纺织业。后来在19世纪美国人口普查中穿孔纸卡被用于记录汇总数据。但这只是数据,还不是程序。为了达到可编程的目的,程序员需要某种控制面板用于输入数据,最早被发明的控制面板是“插线板”,世界上第一台计算机ENIAC就用到了大量的插线板,其缺点是连线复杂,换程序十分不方便。还有一种是用大量的开关代替插线,叫做面板编程(panel programming)。

1940-1950年代,内存开始出现,使用了内存的计算机称为“存储程序计算机”,如果内存足够,不仅仅可以存程序,还可以存需要的数据,包括程序运行时产生的新数据。程序和数据存储在同一个地方,这种结构称为 冯诺依曼结构。冯诺依曼计算机的标志是:算术逻辑单元 + 数据寄存器 + 指令寄存器 + 指令地址寄存器 + 内存。

早期的编程方式都是专家活,我们亟需一种简单的方式告诉计算机我们要做什么,于是,编程语言诞生了!请看下篇。