此系列文章的目的就是让非科班的前端同学迅速对计算机科班同学的必修课达到速成的效果，因为前端一般情况下对很多知识点的面试要求并不高，只需要具备基础理论素养一般就够用了，所以速成是完全可行的。

  • 我这段时间换工作，看到很多工作尤其大厂要求如果非科班，需要具备基本的计算机课程知识，就顺便复习了一边

  • 我这边面试了一些成都的中厂（比如青云、火花思维、北森云计算）和大厂（比如滴滴出行，贝壳金服，腾讯动漫），技术面除了腾讯全都过了的（腾讯需要混合开发经验，我暂缺所以一面没过），基本上都是要求具备科班的基础知识的，甚至面试会问，比如问了进程、线程、协程的区别，进程的调度算法等等

  • 之前写过一篇计算机组成原理入门文章，这篇比之前的要详细很多

导航：
系列文章分为四部分，欢迎大家点赞，收藏，我们一起进步！

  • 计算机组成原理
  • 操作系统
  • 计算机网络（没有包括HTTP，因为这个对前端很重要，单独拎出来讲）
  • 数据结构和算法

  • 计算机网络 —- HTTP

  • 计算机发展

    • 第一台电子数字计算机：ENIAC(1946)，主要是为了军方的计算要求，比如弹道轨迹，所以当时人们的主要需求是单纯的计算，此时的逻辑原件是电子管，逻辑元件是什么呢？就是电子数字就是处理电信号，高低电压表示01的二进制，逻辑元件就是处理电信号的基本单位，此时计算机需要把这些逻辑元件用线路把他们连接起来，从而实现用电路来运算的功能，电子管有我们半个手掌那么大，同时也意味着这个机器的体积是很大的，同时电子管耗电，计算机的耗电量也很高，此时的计算机只能识别0101的二进制数，所以只能用机器语言来编程，此时程序员编程是在一个纸袋上的，如下图，有孔代表0，没孔代表1
  • image.png
  • 晶体管时代：我们看一下晶体管和电子管的比较
  • image.png
  • 晶体管的电气特性可以替代电子管，而且晶体管的体积比电子管小很多，这也意味着此时的计算机要小很多

  • 并且出现了面向过程的程序设计语言和操作系统的雏形，制造一台计算机大概需要几万到几十万的晶体管，需要用手工的方式把晶体管焊接到电路板上，就非常容易出错

  • 中小规模集成电路时代：

  • image.png
  • 把逻辑元件集成在基片上，这种集成电路的技术让我们计算机变得越来越小，同时功耗更低，可靠性也比手动焊接的晶体管更高，此时的计算机主要用于科学计算，一些高级语言同时产生，并出现分时操作系统
  • 随着集成电路工艺的不断提升，出现了大规模和超大规模集成电路，此时开始出现微处理和微型计算机，也就是我们现在家用的计算机，就拿苹果的A13处理器来说，每一个逻辑元件在其中不超过7纳米，一个指甲盖大小的cpu就集成了85亿个晶体管。
  • 我们看一下英特尔公司微处理器发展
  • image.png
  • 机器字长：计算机一次整数运算所能处理的二进制位数，我们常说的8086能一次处理16位字长的二进制位

计算机硬件的基本组成

  • 冯诺依曼体系
  • 因为早期的计算机比如ENIAC，每一步的计算，需要执行的指令都需要程序员手动去操作，也就是手工就浪费了大量的时间。

  • 为了解决这个问题，冯诺依曼就提出了存储成都的概念，就是指，将指令以二进制代码的形式事先输入到计算机的内存里，然后内存根据里面存储的指令从首地址也就是第一条指令开始按顺序一条一条的执行，直到程序执行结束，这种自动执行的机制比人工操作使计算机的计算效率大大提升

  • 冯诺依曼体系是以运算器为核心的，我们现代的计算机是以存储器为核心，我们这里详细了解冯诺依曼体系如何以运算器为核心的价值不大，所以就直接介绍以存储器为核心的现代计算机涉及的部件吧。

屏幕快照 2021-07-27 下午1.51.32.png

上图的实线是数据线，数据交换的通路，虚线是控制线和反馈线，是命令的通路

  • 首先我们的数据通过输入设备会被加工程计算机能够识别的0101的形式，我们直接输入的代码计算机是不认识的，在上面一小节我们知道计算机的计算功能是通过逻辑元件进行处理的，而逻辑元件是通过接受高低电压（背会解释为0101）在线路上处理这些0101的，所以计算机能识别的是0101的形式。
  • 然后经过输入设备

    1、计算机系统功能概述

计算机的功能部件（重点）

1、输入设备

比如键盘鼠标。将程序或者数据以机器能够识别和接受的形式输入计算机

2、输出设备

比如显示器，打印机。将计算机处理结果输出

3、存储器（重点）

存储器主要用来存储程序和数据。
常见的存储器有内存（简称主存，是CPU能够直接访问的存储器），还有就是硬盘（简称辅存，辅存中的信息必须调入主存后，才能为CPU所访问）
接下来我们主要介绍的是内存（硬盘后面的有专门章节介绍），内存主要结构如下
👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图6
其中，存储体就是存放数据的地方，MAR（地址寄存器，存储器就是暂时存储数据的地方）就是根据在存储体内的地址，去取数据，取到的数据放到MDR（数据寄存器），等待CPU去拿取到的数据。

到这里了，出个题，javascript里我们写的let a = 1;这句话属于赋值的命令，根据我们上面的描述，它在存储器里简单经历了怎样的过程呢？

  • 首先变量a其实就是一个内存地址，cpu首先告诉主存储器，我要在内存地址a上取数据
  • 然后主存储器的MAR接受到了a这个地址，接着去存储体内根据这个地址（相当于根据快递单地址取快递）
  • 找到快递，也就是数据后，放到前台（也就是MDR）
  • 然后cpu就把取到的货（数据）从MDR拿走了。

需要注意的是，虽然MAR和MDR属于主存储器的一部分，但是现代CPU中却存在于CPU中。
接着，我们看一下存储体的大致示意图

👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图7
如上图，存储体由许多存储单元组成，每个存储单元可以存放一串二进制代码，这串二进制代码称为存储字，代码的位数称为存储字长（存储单元二进制代码的位数）。

注意这里的地址，就是之前MAR存放的地址，它找寻的方式就是, 比如MAR存的1(指地址是数字1)，那么就要去存储体的1号地址上在对应的存储单元上取数据。

4、运算器

运算器的功能，字面意思当然是实现算数运算的功能了（如：加减乘除），除此之外，运算器还可以做逻辑运算，比如我们js里的与或非（&&，||），运算器简要示意图如下，我们简单介绍一下其中的一些术语：
👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图8
这里我们重点掌握ALU的功能，其它的术语我们只做了解：
ALU： 算术逻辑单元，内部通过电路来实现算术和逻辑运算
ACC：累加器，用于存放操作数，或者运算结果
MQ： 乘商寄存器，在做乘除运算的时候，存放操作数
X： 通用的操作数寄存器

5、控制器

控制器如下图的三部分都比较重要，需要记住。
👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图9
CU：控制单元，比如之前我们说的存储器，从存储器既可以取数据又可以取指令，控制单元就是用来分析指令的，给出控制信号
IR：指令寄存器，存放当前执行的指令
PC：程序计数器，存放下一条指令的地址
综合上面的计算机功能部件，我们串联起来看看他们是如何工作的

取数指令执行过程（了解）

首先，是取指令的过程如下,假如我们有一段程序a*b + c (数据装入内存如下图， 比如第一句 内存地址是0 , 指令分为了操作码和地址码，操作码是指要执行什么操作，这里000001表示取数的操作，去存储体取数据，地址码是指去存储体哪个地址去取，这里的0000000101换算成10进制就是5，所以去由下图主存地址是5的地方取数据)
👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图10
接下来我们根据下图示例，看看执行指令的过程
👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图11

  1. PC = 0,也就是说从主存地址为0开始取指令
  2. 接着PC去找MAR， 也就是说MAR = 0
  3. MAR去查存储体里主存地址0的指令，拿到000001 0000000101 放入MDR
  4. cpu把MDR的指令取出来放入IR,也就是指令寄存器
  5. 然后IR将指令放入CU(控制单元)进行分析，然后得到结论，这是一个”取数的指令”
  6. 然后CPU再去MAR，去找（MAR=5）主存地址为5的数据，放入MDR(MDR = 0000000000000011，也就是10进制的5)
  7. 内存地址5上的数据是十进制的2（代表变量a），然后拿出来放入ACC寄存器

来个插曲，我们知道数据在内存里是二进制存着，也就是0和1, 0和1怎么用表示呢？
我们拿其中一种存储0和1的方式来说明

  • 电容是否有电荷，有电荷代表1，无电荷代表0
  • 如下图

👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图12
👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图13

关于高级语言编译（重点）

高级语言一般有两种方式转换为机器语言

  • 一种是直接借助编译器，将高级语言转换为二进制代码，比如c，这样c运行起来就特别快，因为编译后是机器语言，直接就能在系统上跑，但问题是，编译的速度可能会比较慢。
  • 一种是解释性的，比如 js，是将代码翻译转换成机器语言（中间可能会先翻译为汇编代码或者字节码），解释一行，执行一行

需要注意的是，按照第一种将大量的高级代码翻译为机器语言，这其中就有很大的空间给编译器做代码优化，解释性语言就很难做这种优化，但是在v8引擎中，js还是要被优化的，在编译阶段（代码分编译和执行两个阶段）会对代码做一些优化，编译后立即执行的方式通常被称为 JIT (Just In Time) Comipler。

趣味习题（拓展）

  1. 为什么我们说的32位操作系统，最大内存不超过4GB呢？（32位指的是寻址最大的范围是2的32次方，也就是MAR最多表示的范围，如果一个存储单元是8bit，也就是1k，所以共有2*32B也就是大约4G的空间）

    2、数据的表示和运算（重点）

  • 本章绝对重点为知道浮点数在计算机内如何表示，推导出为什么javascript 0.1+0.2 !=0.3
  • 次级重点是知道10进制与其它进制的相互转换方法

    2.1 进位计数

学习任意进制如何转十进制的方法。将任意进制的各位数码与它们的权值相乘，再把乘积相加，就得到了一个十进制数。这种方法叫按权展开相加法。

👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图14

2.2 二进制转其它进制

拿2进制转16进制为例，因为16进制是2的4次方，所以将2进制每4位分为一组。

👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图15

2.3 十进制转任意进制

方法为：整数部分是除基取余发，小数部分采用乘基取余法。案例如下。

👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图16

2.4 真值和机器数(此知识点为后面的定点数和浮点数打基础)

我们平常用正号和负号来表示正数和负数，比如+10，-10。这种带 “+”或者”-“符号的数称为真值。而机器表示这些真值的时候常常用”0”表示正，用”1”表示负。如0101这里的0代表负 101代表进制的5，所以表示的+5。

2.5 定点数的表示（主要理解其中原码/补码/移码的关系）

  • javascript的数字是浮点数，所以定点数我们看看就行了

定点数分为：无符号数和有符号数

无符号数：就是说没有符号位的定点数，因为有符号位的定点数比如110，其中第一个1是符号，0表示正，1表示负，而无符号数不用考虑这一层。（通常讨论无符号整数，而没有无符号小数）

有符号数：有符号定点数分为定点正数和定点小数，也就是说如果有一个数位10.2，小数和整数部分要分别存。

下图位定点整数的格式，可以到看到，小数是固定的，在最后一位，而且实际上是没有的，只是约定在最后，并且二进制的第一位是符号位，表示正负。

image.png
下图是定点小数格式，最高位也是符号位，小数点隐含在其后
image.png
注：可用原码、反码、补码三种方式来表示定点整数和定点小数。还可用移码表示定点整数。

定点数的原码

原码比较简单，就是第一位为符号为，剩余的位数才表示数值，比如2进制的-0.1，在原码里表示为1,1（注意这里的逗号实际上不存在，只是为了把符号为和数值位分隔一下）

原码有什么问题呢？（两个正数相加没有问题，我们看看一个正数和一个负数相加呢，也就是做减法）

0，101（10进制的5） + 1，001（10进制的-1） = 1，110（10进制的-6）,大家看，是不是就出问题了，此时就要就需要补码，我们后面再讲（在计算机里，加法器实现较为简单，减法器就复杂很多，所以说如果能用加法代替减法，是不是就完美了）

定点数的补码

补码是在原码的基础上，对于正数，补码和原码表示相同，如果是负数，原码符号位不变，数值部分按位取反，末位+1，比如定点小数原码为1，1100000的补码为1，0100000

定点数的移码

在补码的基础上将符号位按位取反。注意：移码只能用于表示整数。比如定点小数原码为1，1100000的补码为1，0100000 ，那么移码就是0，0100000

定点数的加减法

例如0，101 + 1，001（这是负数，因为符号位是1），转换为10进制就是 5 - 1，因为不能做减法，所以要将负数的源码转为补码，1，001的补码等于 按位取反是1，110，然后末位加1就是1，111 ，等价于0，101 + 1，111 = 10，100 ，因为首位的1计算机并不会保存，所以最终结果是0，100也就是10进制的4

定点数的溢出（作为拓展，希望大家有兴趣的自己探索一下）

兄弟们，我觉得计算机原理中对于前端非常非常重要的知识点来了，就是浮点数，希望通过接下来的学习能够解答为什么javascript中。0.1+0.2 != 0.3

2.6 浮点数

浮点数的表示

我们举一个例子来理解浮点数的表示，比如数字+302657264526，这是定点整数的表示方法，如果是科学计数法，我们表示为：+3.026 * 1011 ，而其中的10是不是固定不变的呢，所以如果要保存这个科学技术法表示的数字，我们可以不看10这个基数，只需要保存+11 和 +3.026就能推出这个数字的科学技术法，从而得到这个数字

我们可以给+11 和 +3.026取两个名字，在浮点数里分别叫阶码和尾数，如下图

截屏2020-12-28上午11.17.56.png
其中， 阶码反映数值的大小，尾数反应数值的精度，为什么这么说呢，比如之前举的例子中，+11表示小数点要右移多少位，是不是越大，移动的位数越多，数字就越大呢，对于尾数，右移小数点其实是在尾数的基础上，比如+3.026的基础上去移动的，所以尾数表示的位数越多，那么精度就越精确。比如+3.0265748是不是同样右移5位比+3.026表示的数字更精确呢

在二进制表示的计算机内，阶码常用补码或者移码表示的定点整数，尾数常用原码或者补码表示的定点小数。

浮点数的表示为 N = rE * M ， r相当于底数，是2（跟10进制科学计数法是10意思是一样的），E代表阶码，M代表尾数。

IEEE 754标准的双精度浮点数

常见的IEEE 754标准分为单精度浮点数float和双精度浮点数double，我们可以看一下它的区别（阶码也可以称为指数）
image.png

因为javascript的数字就是双精度浮点数，所以我们只介绍这一种。在双精度浮点数的尾数是52位，其实是可以表示53位，为什么呢，我们知道科学计数法，但二进制只能表示0和1，0不符合科学计数法，所以52位最前面有一个省略的数字是1，默认存在，但是不显示在52位中。

并且尾数用原码表示。

现在我们讲一下阶码需要注意的点。阶码是用的无符号定点整数表示，为[0，2047]（2的11次方减一）但这就有一个问题了，不能表示负数，为了表示负数一般可以引入符号位，但是符号位定点数减法运算又要引入补码，就很麻烦，所以采取一种取巧的方式，将阶码部分统一减去1023，就变成[-1023, 1024]

又因为阶码的全0和全1有特殊用途，所以-1023和1024的移码就是全1和全0，所以阶码的范围变为[-1022， 1023]。那如果阶码是0和1有什么特殊用途呢？

当阶码E全为0，尾数M不全为0时，此时尾数隐藏的首位1.xxx的1变为0
当阶码E全为0，尾数M全为0时，表示真值正负0

当阶码E全为1，尾数M全为0时，表示无穷大
当阶码E全为1，尾数M不全为0时，表示NaN

好了，根据上面我们学到的知识，来简单解决下0.1 + 0.2 为什么不等于0.3

将 0.1 转换为二进制表示

回顾一下一个数的小数部分如何转换为二进制。一个数的小数部分，乘以 2，然后取整数部分的结果，再用计算后的小数部分重复计算，直到小数部分为 0 ，这就是我们之前讲的乘基取余法。

因此 0.1 转换为二进制表示的过程如下：

小数 x2 的结果 整数部分
0.1 0.2 0
0.2 0.4 0
0.4 0.8 0
0.8 1.6 1
0.6 1.2 1
0.2 0.4 0
0.4 0.8 0
0.8 1.6 1
0.6 1.2 1
… … …

得到 0.1 的二进制表示为 0.00011…(无限重复 0011)

通过科学计数法表示

0.00011…(无限重复 0011) 通过科学计数法表示则是 👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图21，其中小数位中无限重复 1001。

转换为 IEEE 754 标准表示

当经过科学计数法表示之后，就可以求得 阶码 和 尾数 了。

阶码的移码 = 阶码的真值 + 偏移量，因此 0.1 的 阶码 等于 👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图22 的11位二进制表示，即 011 1111 1011。

再来获取 0.1 的 尾数，尾数 就是 1.10011001…(无限重复 1001) 中的小数位，由于 尾数 占 52位所以抽取 52 位小数，1001…(中间有 11 个 1001)…1010 (请注意最后四位，是 1010 而不是 1001，因为四舍五入有进位，这个进位就是造成 0.1 + 0.2 不等于 0.3 的原因)。

到此，终于可以将 0.1 转换为 IEEE 754 表示了。

  1.     0       011 1111 1011   1001...( 11 x 1001)...1010
  2. (符号位)     (阶码)          (尾数)

此时如果将这个数转换为十进制，可以发现值已经变为 0.100000000000000005551115123126 而不是 0.1 了。

回归到 0.1 + 0.2 != 0.3 这个问题

通过上面的过程，我们知道了 JS 因为遵循了 IEEE 754 产生浮点误差的原因。因此不仅 0.1 会产生误差，0.2 及 0.3 也是如此，因此最后造成了 0.1 + 0.2 不等于 0.3 的结果。

3、存储系统

  • 本章绝对重点就是cache的基本原理（为什么需要cache, 局部性原理是什么），cache的替换算法和cache

多级存储系统（了解）

为什么需要多级存储的结构呢？如下图所示，可以了解到为什么要引入cache
image.png
主存的执行速度相比cpu要慢很多，这会造成主存在运行的时候，cpu会等待的问题，比如cpu1秒就处理10条指，但从内存里取10条指令就需要1分钟，就很浪费cpu资源，所以为了解决这个问题，采用了cache-主存的方式，cache是高速缓冲储存器，它的速度接近于cpu。

存储器的分类 —- 按存取方式（了解）

  • 随机存取存储器：读写任何一个存储单元所需要的时间都相同，与存储单元所在的物理位置无关。比如内存条。
  • 顺序存取存储器：读写一个存储单元所需时间取决于存储单元所在的位置。比如磁带，你如果已经放完了磁带，想从头开始听，需要倒带到开始的位置。
  • 直接存取存储器：既有随机存取特性，也有顺序存取特性。先直接选取信息所在的区域，然后按顺序方式存取。

RAM和ROM的特点（重点）

RAM

RAM又被称作“随机存储器”，是与CPU直接交换数据的内部存储器，也叫主存（内存）。它可以随时读写，而且速度很快，通常作为操作系统或其他正在运行中的程序的临时数据存储媒介。当电源关闭时RAM不能保留数据（掉电数据消失哦）如果需要保存数据，就必须把它们写入一个长期的存储设备中（例如硬盘）。

ROM

ROM又被称为“只读存储器”，ROM所存数据，一般是装入整机前事先写好的，整机工作过程中只能读出，而不像随机存储器那样能快速地、方便地加以改写。ROM所存数据稳定，断电后所存数据也不会改变

局部性原理（重点）

先看下图

👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图24

（说明一下，MDR和MAR虽然逻辑上属于主存，但是在电路实现的时候，MDR和MAR离CPU比较近）

上图是在执行一串代码,可以理解为js的for循环

  1. const n = 1000;
  2. const a = [1, 2, 3, 4, 5, 6, 7]
  3. for(let i =0; i < n; i++) {
  4.     a[i] = a[i] + 2
  5. }
  6. 复制代码

我们可以发现

  • 数组的数据有时候在内存是连续存储的（代码里但数组a，对应图中主存里但a[0]-a[7]的数据块）
  • 如果我们要取数据，比如从内存取出a[0]的数据需要1000ns(ns是纳秒的意思),那么取出a[0]到a[7]就需要1000 * 8 = 8000 ns
  • 如果我们cpu发现这是取数组数据，那么我就把就近的数据块a[0]到a[7]全部存到缓存上多好，这样只需要取一次数据，消耗1000ns

cahce就是局部性原理的一个应用

  • 空间局部性：在最近的未来要用到的信息（指令和数据），很可能与现在正在使用的信息在存储空间上是邻近的（比如for循环用到数据在主存都是相邻存储的）
  • 时间局部性：在最近的未来要用到的信息，很可能是现在正在使用的信息

`

`
下图注意的是，cpu拿数据是先从cache里拿，如果没有才从主存里面取

👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图25

可以看到cache一次性取了a[0]到a[9]存储体上的数据，只需要1000ns，因为Cache是高速存储器，跟cpu交互速度就比cpu跟主存交互速度快很多。

cahce替换算法（重点）

在理解替换算法之前，我们简单的了解一下，cache-主存的映射方式
首先这里的映射是什么意思呢，比如主存的数据一块1kb（所有数据按块存储），那cache上也要按一块1kb来存，这样主存有数据放到cache的话，就直接以块形式放入，操作简单，就是说cache上的一块数据是跟主存上的一块数据是有映射关系的。

未标题-1_wps图片.jpg

  • 全相联映射：很好理解，就是主存上任意一块数据，比如一块数据是1kb，可以放在cache任意位置（cache的一块大小也是1kb），如上图主存第9块数据是可以放在cache的任意位置的

  • 直接映射：每个主存块只能放到一个特定的位置：cache块号 = 主存块号 % cache总块数，比如上图b，主存的9号内存块 9 % 8（8是cache的块数） = 1， 也就是会放到cache的1号块

  • 组相联映射：cache块分为若干组， 每个主存块可放到特定分组中的任意一个位置组号 = 主存块号 % 分组数，例如上图c，主存块号9，cache分为了4组，所以9 % 4 = 1，会放到第一组，第一组有两个空位，看谁有空放谁

现在我们来看替换算法，替换算法我们是以全相联映射为基准的（直接映射根本就不需要替换算法，留给您想一下是为啥呢？）(最需要注意的是LRU算法，你要能写出javascript的实现，我在面试的时候也遇到过)：

下面是主要这次讲解的替换算法：

  • 随机算法（RAND）
  • 先进先出（FIFO）
  • 近期最少使用（LRU）

  • 最近不经常使用（LFU）

  • 随机算法很简单，就是cache满了，随机选择cache的一块替换掉，拿我们之前讲的假如cache有8个块，那么就是每次从8个块随机选择一个替换掉（前提是cache每个块都已经装了数据）

  • 先进先出: 若cache已满，则替换掉最先被调入cache的块，说白了就是队列这样的数据结构，去维护cache块的更新

  • 近期最少使用，LRU算法：为每一个cache块设置一个“计数器”，用于记录每个cache块已经有多久没有被访问。当cache满后替换“计数器”最大的。（是不是听起来很懵逼，简单来说就是让你设计一个算法，当你的cache块都有数据了，新来的数据要替换掉最近最少使用的数据，这也是一道leetcode题，一般采用双向链表 + 哈希表的方式解决，大家可以看leetcode官方视频解析：https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/）

javascript我这边提供一种实现思路：

  1. // 链表的数据结构
  2. class ListNode {
  3.   constructor(key, value) {
  4.     this.key = key
  5.     this.value = value
  6.     this.next = null
  7.     this.prev = null
  8.   }
  9. }
  11. // LRU 缓存类 
  12. // 参数是缓存上限 比如new LRU(2)，表示最大缓存数量为2
  13. class LRUCache {
  14.   constructor(capacity) {
  15.     // 记录最大上限缓存的数量
  16.     this.capacity = capacity
  17.     // 哈希表让查询时间复杂度变为了O(1)
  18.     this.hashTable = {}
  19.     // 记录当前缓存数量
  20.     this.count = 0
  21.     // 双向链表的头尾节点先建立好，目的是快速在尾节点删除使用最少的元素和插入最新元素到头结点
  22.     this.dummyHead = new ListNode()
  23.     this.dummyTail = new ListNode()
  24.     this.dummyHead.next = this.dummyTail
  25.     this.dummyTail.prev = this.dummyHead
  26.   }
  28.   get(key) {
  29.     // 获取元素需要处理两步
  30.     // 1是看哈希表是否有元素，有的话就返回，这就是使用哈希表的好处，链表遍历就慢
  31.     // 2因为你获取的元素，这个元素的新鲜度就要提升，所以要把元素放到链表首部
  32.     let node = this.hashTable[key]
  33.     if (node == null) return -1
  34.     this.moveToHead(node)
  35.     return node.value
  36.   }
  38.   put(key, value) {
  39.     // 放置元素也分两种处理
  40.     // 1是如果已经有的元素，直接更改其
  41.     let node = this.hashTable[key]
  42.     if (node == null) {
  43.       let newNode = new ListNode(key, value)
  44.       this.hashTable[key] = newNode
  45.       this.addToHead(newNode)
  46.       this.count++
  47.       if (this.count > this.capacity) {
  48.         this.removeLRUItem()
  49.       }
  50.     } else {
  51.       node.value = value
  52.       this.moveToHead(node)
  53.     }
  54.   }
  56.   moveToHead(node) {
  57.     this.removeFromList(node)
  58.     this.addToHead(node)
  59.   }
  61.   removeFromList(node) {
  62.     let tempForPrev = node.prev
  63.     let tempForNext = node.next
  64.     tempForPrev.next = tempForNext
  65.     tempForNext.prev = tempForPrev
  66.   }
  68.   addToHead(node) {
  69.     node.prev = this.dummyHead
  70.     node.next = this.dummyHead.next
  71.     this.dummyHead.next.prev = node
  72.     this.dummyHead.next = node
  73.   }
  75.   removeLRUItem() {
  76.     let tail = this.popTail()
  77.     delete this.hashTable[tail.key]
  78.     this.count--
  79.   }
  81.   popTail() {
  82.     let tailItem = this.dummyTail.prev
  83.     this.removeFromList(tailItem)
  84.     return tailItem
  85.   }
  86. }

4、指令系统(了解)

指令的格式

首先什么是指令呢？是指计算机执行某种操作的命令，是计算机运行的最小功能单位。一台计算机的所有指令的集合构成该机的指令系统，也称为指令集。比如著名的x86架构（intel的pc）和ARM架构（手机）的指令集是不同的

一条指令就是机器语言的一个语句，它是一组有意义的二进制代码。一条指令通常包括操作码（OP） + 地址码（A）

根据指令中操作数地址码的数目不同，可将指令分成以下几种格式。我们举几个例子（没有覆盖全部）让大家感受一下，尤其注意三地址指令，就能理解指令的大致格式了
1、零地址指令
image.png
只给出操作码OP，没有显式地址。这种指令有两种可能：

  • 不需要操作数的指令，如空操作指令、停机指令等

2、三地址指令
image.png
指令的含义：（A1）OP（A2）->A3
它表示从A1和A2地址上取出数据，然后进行OP操作，最后存放到A3地址上。

寻址方式

寻址寻什么呢？我们计算机里无非保存的是指令和数据，就是寻这个家伙了。

指令寻址方式有两种：一种是顺序寻址方式，另一种是跳跃寻址方式。
1、顺序寻址可通过程序计数器PC加1，自动形成吓一跳指令
2、跳跃寻址通过转移类指令实现，跳跃，就是不按照程序计数器自动加一的方式给出下调指令地址，而是由本条指令给出的下条指令格式

数据寻址：确定本条指令的地址码指明的真实地址。大致有10种寻址方式，我们只介绍其中一种，因为这部分内容都是以了解为主。

相对寻址：相对寻址是把程序计数器(PC)的内容加上指令格式种的形式地址A而形成操作数的有效地址。如下图：
（不理解没关系，这章不重要）
image.png

CISC和RISC

  • CISC （复杂指令系统计算机）：一条指令完成一个复杂的基本功能。比如x86架构的计算机，主要用于笔记本和台式电脑。计算机的指令系统比较丰富，有专用指令来完成特定的功能。因此，处理特殊任务效率较高。

  • RISC （精简指令系统计算机）：一条指令完成一个基本”动作”；多条指令组合完成一个复杂的基本功能。比ARM架构，主要用于手机，平板等。设计者把主要精力放在那些经常使用的指令上，尽量使它们具有简单高效的特色。对不常用的功能，常通过组合指令来完成。因此，在RISC 机器上实现特殊功能时，效率可能较低。

5、中央处理器 + GPU (了解)

  • 因为我们在第一章已经了解过cpu和内存在执行指令的大致过程，其实学好第一章，就已经差不多了，所以大家可以回看一下第一节。
  • 这里我们主要补充一下GPU的内容。

GPU(Graphics Processing Unit) 图形处理单元，又称图形处理器，是我们所周知的显卡的核心部件，是显卡的“心脏”。GPU是专为复杂数学运算和几何运算而设计的芯片，它的用途我们平常所周知的就是用于图形图像处理（显卡）。

CPU与GPU

我们可以看一下CPU和GPU的对比图

👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图30

  • 上图的一段总结非常好，CPU相当于1名老教授，奥数题和小学算术题都会，GPU相当于1000名小学生，只会小学算术题。

  • 从上图我们可以知道GPU将更多的空间（晶体管）用作执行单元，而不是像CPU那样用作复杂的控制单元和缓存（CPU需要同时很好的支持并行和串行操作，需要很强的通用性来处理各种不同的数据类型，同时又要支持复杂通用的逻辑判断，这样会引入大量的分支跳转和中断的处理。

  • 这些都使得CPU的内部结构异常复杂，计算单元的比重被降低了），实际来看CPU的芯片控件25%是ALU，而GPU则高达90%（GPU面对的则是类型高度统一的、相互无依赖的大规模数据和不需要被打断的纯净的计算环境。因此GPU的芯片比CPU芯片简单很多），这也就是为啥GPU运算能力超强的原因。

GPU加速在前端的应用

首先我们要知道为什么要用（开启）GPU加速（硬件加速）， 然后我们才能去探讨如何以及怎么样去应用GPU加速。

  1. 3D 或透视变换(perspective，transform) CSS 属性
  2. 使用加速视频解码的video元素
  3. 拥有 3D (WebGL) 上下文或加速的 2D 上下文的 canvas 元素
  4. 混合插件(如 Flash)
  5. 对自己的 opacity 做 CSS 动画或使用一个动画 webkit 变换的元素
  6. 拥有加速 CSS 过滤器的元素
  7. 元素A有一个 z-index 比自己小的元素B，且元素B是一个合成层（换句话说就是该元素在复合层上面渲染），则元素A会提升为合成层

这里里面最常用的是1和7。1很好理解，就是transfrom3d属性。第七点我解释一下，你怎么来判断自己的页面是否使用了3d加速。请看下图：

首先：
image.png

然后观察这两个图层：

image.png

那如何让2d也能单独的图层渲染启用GPU加速呢，只需要给2d的css上加一个index之后，然后点击动画，就会出现黄色边框，大家可以用这个网址做测试：https://www.w3school.com.cn/css3/css3_3dtransform.asp

image.png

6、总线（了解即可）

  • 总线这部分不是重点，主要了解总线的大致工作工作流程即可

    总线的定义

总线是一组能为多个部件分时共享的公共信息传送线路

系统总线的结构（扫一眼即可）

我们主要理解总线工作的逻辑

  • 单总线结构：
    • 单总线结构将CPU、主存、I/O设备（通过I/O接口）都挂在一组总线上，允许I/O设备之间、I/O设备与主存之间直接交换信息，如下图。

image.png
缺点是支持并发传送操作，优点是结构简单，成本低

  • 双总线结构
    • 双总线结构有两条总线：一条是主存总线，用于CPU、主存和通道之间传送数据；另一条是I/O总线，用于在多个外部设备与通道之间传送数据。注意，这里通道的概念比较重要，详情可移步到本文的”输入输出系统”章节

image.png
优点是将低速I/O设备从单总线上分离出来，缺点是要增加通道等硬件设备。

  • 三总线结构
    • 三总线结构是计算机系统的各部件用3条独立的总线来构成信息通路。（如下图的三条总线分别为：主存总线、I/O总线和直接内存访问总线）

image.png

总线的分类(了解)

按功能主要分为以下三种：

  • 片内总线：

    • 片内总线是芯片内部的总线，它是CPU芯片内部寄存器与寄存器之间、寄存器与ALU之间的公共连接线

  • 系统总线：分为三类：数据总线、地址总线和控制总线

    • 数据总线用来传输各功能部件之间的数据信息，它是双向传输总线。
    • 地址总线用来指出数据总线上的源数据或目的数据所在主存单元或I/O端口的地址，单向传输。
    • 控制总线传输控制信息。比如是读信号，还是写信号。

7、输入/输出系统

  • I/O这部分重中之中的知识点是I/O方式，即理解马上就要讲到的I/O设备的演进过程，其它知识点作为了解就好

I/O是什么呢？

输入/输出（Input /Output ,简称I/O），指的是一切操作、程序或设备与计算机之间发生的数据传输过程。

比如文件读写操作，就是典型的I/O操作。接下来我们看一下I/O设备的演进过程

I/O设备的演进过程

关键：I/O设备的演进过程其实就是解放cpu的过程，为什么这么说呢，看完下面的介绍就知道了！

👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图37

  • 早期计算机主要功能就是计算，所以就以cpu为核心
  • 外设连接cpu需要一套专用的线路，外设的增删就很麻烦
  • cpu和外设串行工作模式

在早期的计算机里，因为cpu启动外设后，外设准备数据是需要时间的，比如读取外部传来的数据，此时cpu如何知道I/O设备已经完成任务呢?比如说怎么知道I/O设备已经读取完一个文件的数据呢?CPU会不断查询I/O设备是否已经准备好。这时，cpu就处于等待状态。也就是cpu工作的时候，I/O系统是不工作的，I/O系统工作，cpu是不工作。而且主存和外设也需要借助cpu来通信，所以留给CPU的时间又少了。

所以我来看此阶段比较明显的问题：

  • 外设设备分散连接，外设的增删就很麻烦 ，我们引入了总线结构
  • 高速外设跟cpu交流频繁

接着看第二阶段

  • cpu启动好外设之后，就返回继续自己的工作了，外设准备好数据后，通过中断请求的方式通知cpu，cpu只需要暂停手上的工作，处理一下具体数据传输的过程，减少不断查询的时间

👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图38

  • 为了解决第一阶段CPU要等待I/O设备，串行的工作方式，所有I/O设备通过I/O总线来跟CPU打交道，一旦某个I/O设备完成任务，就会以中断请求的方式，通过I/O总线，告诉CPU，我已经准备好了。

  • 但是对于高速外设，它们完成任务的速度很快，所以会频繁中断CPU,（举一个例子，每输入一个字符就中断CPU,是不是很影响cpu的执行呢） 为了解决这个问题，高速外设跟主存之间用一条直接数据通路，DMA总线连接，DMA控制方式只需要CPU安排最开始高速外设最初的任务，接下来的数据交换就是靠DMA控制器控制了，这样就可以防止频繁中断CPU，让CPU得到了解放

问题：

  • DMA控制器的传送任务是cpu来安排的，还有dma连接外设的类型和数量是不灵活的，所以我们设置了一些专门管理外设的处理器

最后来看一下第三阶段

👍前端计算机基础理论速成系列 --- 计算机组成原理 - 图39

第三阶段，CPU通过通道控制部件来管理I/O设备，CPU不需要帮它安排任务，只需要简单的发出启动和停止类似的命令，通道部件就会自动的安排相应的I/O设备工作。为什么这种方式比DMA更好呢，因为商用的中型机、大型机可能会接上超多的I/O设备，如果都让CPU来管理，那么CPU就非常累。

通道可以理解为一种“弱鸡版的CPU”。可以识别通道指令，你可以理解为CPU告诉通道，取多少数据，数据存放到内存哪里，通道就自己去处理，不用cpu来管理这么多事情，注意看下图
image.png
如上图，通道是跟CPU并列的，所以通道能帮CPU分担任务，此时的通道有自己的一套指令集，可以执行通道指令。

后面进一步增强了通道的功能，这里出现了跟cpu处理能力差不多的I/O处理机
image.png

补充：中断是什么（重点，操作系统课也会涉及这个概念）

之前我们讲到一个名词叫中断，这个概念非常重要，我们作为补充概念学习一下

中断的概念

程序中断是指在计算机执行现行程序的过程中，出现某些急需处理的异常情况或特殊请求，CPU暂时中止现行程序，而转去对这些异常情况或特殊请求进行处理，在处理完毕后CPU又自动返回到现行的断点处，继续执行程序。我们来举个例子就明白了。

webwxgetmsgimg.jpg

当程序执行到K的时候，键盘的敲击产生了中断（I/O中断），此时CPU会终止执行当前的指令，转而去处理中断，等中断服务程序执行完毕，继续执行k+1。

中断处理流程（了解即可，看不懂没关系）

  1. 关中断。CPU关闭中断，即不再接受其他外部中断请求。
  2. 保存断点。将发生中断处的指令地址压入堆栈，以使中断处理完后能正确的返回。
  3. 识别中断源。CPU识别中断的来源，确定中断类型号，从而找到相应的中断处理程序的入口地址
  4. （以上三步一般由处理中断的硬件电路完成）保存现场。将发生中断处的有关寄存器（中断服务程序要使用的寄存器）以及标志寄存器的内容压入堆栈。
  5. 执行中断服务程序。转到中断服务程序入口开始执行，可在适时时刻重新开放中断，以便允许响应较高优先级的外部中断。
  6. （后三步一般软件，即中断处理程序完成）恢复现场并返回。把“保护现场”时压入堆栈的信息弹回寄存器，然后执行中断返回指令，从而返回主程序继续运行。（IRET指令，无操作数，从栈顶弹出3个字，分别送入IP、CS和FLAGS寄存器）

image.png

本文完结。感谢您能看到最后。

本文主要参考资料：

唐朔飞：计算机组成原理
袁春风： 计算机组成原理
王道考研：计算机组成原理
极客时间：深入浅出计算机组成原理