计算机基础知识

计算机基础知识

中央处理器CPU

计算机组成结构（Computer Architecture）源于冯·诺伊曼计算机结构，该结构成为现代计算机系统发展的基础。将计算机硬件划分为5个部分：处理器、存储器、总线、接口和外部设备。

CPU的功能

• 程序控制

  CPU通过执行指令来控制程序的执行顺序，这是CPU的重要功能。

• 操作控制
  一条指令功能的实现需要若干操作信号配合来完成，CPU产生每条指令的操作信号并将操作信号送往对应的部件，控制相应的部件按指令的功能要求进行操作。

• 时间控制
  CPU对各种操作进行时间上的控制，即指令执行过程中操作信号的出现时间、持续时间及出现的时间顺序都需要进行严格控制。

• 数据处理

  CPU通过对数据进行算术运算及逻辑运算等方式进行加工处理，数据加工处理的结果被人们所利用。所以，对数据的加工处理也是CPU最根本的任务。

此外，CPU还需要对系统内部和外部的中断或异常做出响应，进行相应的处理。

CPU的组成

• 运算器

  执行所有的算术运算，比如加减乘除等；

  算数逻辑单元  ALU（算数运算、逻辑运算）
  累加寄存器    AC （类型：通用寄存器）（存放，在算术的过程中累计的值存在这里）
  数据缓冲寄存器 DR （暂时存放内存的指令或数据，后面与内存打交道）
  状态条件寄存器 PSW（保存指令运行结果的条件码内容，如溢出标志等）
  

• 控制器
  控制整个CPU的工作，概括：保证指令执行、处理异常事件。

  指令寄存器 IR  暂存CPU执行指令，暂存CPU当前正在执行的指令
  程序计数器 PC  存放指令执行地址，下一条指令的地址
  地址寄存器 AR  保存当前CPU所访问的内存地址
  指令译码器 ID  分析指令操作码
  

• 寄存器组

  保存程序的中间结果，也会进行暂存指令。

• 总线

  总线（Bus）是一种传输数据和信号的通道，连接各种计算机组件。

程序员可以通过汇编语言对寄存器进行操作。

进制转换

二进制转十进制

无符号的二进制整数

110 转十进制的思路：
对应的下标：210
1*2的2次方 + 1*2的1次方 + 0*2的0次方  = 4 + 2 + 0 = 6

带符号的二进制整数

带符号，第一位，0：正数，1：负数，后面跟上面一样

小数二进制数

101.011 转十进制的思路：
对应的下标：210.-1-2-3
1*2的2次方 + 0*2的1次方 + 1*2的0次方 . 0*2的-1次方 + 1*2的-2次方 + 1*2的-3次方   = 4 + 0 + 1 . 0 + 0.25 + 0.125 = 5.375
注意：任何数的0次方都是1

十进制转二进制

转换整数的十进制数值为二进制，可以使用除2取余法。

15转换为二进制的思路：
15 ÷ 2 = 7 余 1
7  ÷ 2 = 3 余 1
3  ÷ 2 = 1 余 1
1  ÷ 2 = 0 余 1
二进制：1111

转化小数

小数部分乘以2，得到的结果的整数部分作为二进制小数的第一位，直到小数部分为0，顺序是从上到下。

11.75转换为二进制的思路：
0.75 * 2 = 1.5   整数位是1
0.5  * 2 = 1.0   整数位是1
小数部位二进制：11

数据

定点数

计算机中用来表示带符号整数的四种编码方式包括：

• 原码：最高位表示符号，0表示正数，1表示负数，其余位表示数值
• 反码：正数的反码与原码相同，负数的反码是对该数的每一位取反
• 补码：正数的补码与原码相同，负数的补码是对该数的反码加1
• 移码：移码是对其补码取反，将符号位取反的补码（不区分正负）

      1    -1
原码 0001  1001
反码 0001  1110
补码 0001  1111 (1110 + 1)
移码 1001  0111

反码是计算机系统中的一种表示方式，用于处理负数。

补码是将减法运算转换为加法运算，从而简化运算器设计。

浮点数

表示格式：
阶符 - 阶码（移码）- 数符 - 尾数（补码）

尾数：用补码表示，位数决定精度，位数越多精度越高；

阶码：用移码表示，位数决定范围，位数越多范围越高；

对阶时，小数向大数看齐；

对阶是通过较小数的尾数右移实现的；

校验码

校验码是计算机系统中一种用于验证数据完整性的技术，常见的校验码包括奇偶校验码、循环冗余校验码（CRC）、校验和等。

奇偶校验

是一种错误检测方法，用于检测数据传输过程中的错误。它通过在数据中添加一个奇偶位来保证传输的数据的正确性，可以检查出误码，但不能纠错。

两种方式：

• 奇校验：在传输的数据中，如果数据中的1的个数为奇数，则奇校验位设置为0，否则设置为1。
• 偶校验：在传输的数据中，如果数据中的1的个数为偶数，则偶校验位设置为0，否则设置为1。

模2运算

模2运算是一个对二进制数进行运算的操作，它的原理是将两个二进制数按位进行异或运算。具体来说，对于两个二进制数a和b，模2运算可以表示为a ⊕ b，其中⊕表示异或操作。

在模2运算中，每一位的结果只有两种可能：0和1。如果两个二进制数的对应位相同，那么结果为0；如果对应位不同，结果为1。模2运算常用于校验和计算、差错检测和纠错编码等领域。

例：对于两个二进制数1010和1101，进行模2运算的结果为0111。
1010
1101
----- 结果
0111

CRC循环冗余校验

循环冗余校验是一种用于检测和纠正数据传输中可能出现的错误的技术。它利用一个固定的生成多项式来对数据进行计算，生成一个固定长度的校验码。接收方在接收到数据后，同样使用生成多项式对数据进行计算，并与发送方生成的校验码进行比较，以判断数据是否被传输过程中出现了错误。它在数据通信和存储中广泛应用，如以太网、串行通信协议、磁盘驱动器等。

CRC校验的原理是将数据看作二进制序列，并通过将每一位与生成多项式进行除法运算得到余数。发送方在发送数据时，将生成的校验码附加在数据后面一起发送；接收方在接收到数据后，同样使用生成多项式对数据进行计算，得到一个余数。如果余数为0，则说明数据没有错误；如果余数不为0，则说明数据在传输过程中出现了错误。

算法要求生成多项式必须包含最低次项（1）

例：待发送的信息101001，生产多项式：X^3 +  X^2 + 1，计算编码后的信息：
生产多项式：X^3 +  X^2 + 1 ，得到除数：1*X^3 + 1*X^2 + 0*X^1 + 1*X^0 = 1101
101001，因X^3，需要补3个0,得到：101001000
101001000 ÷ 1101 进行模2运算：
1101  | 101001000   --- 被除数是1开头，第一位是1
1101  | 1101        --- 模2运算
1101  | 0111        --- 结果：第一位是0，去掉，得到1，第二位是1
1101  |  1110       --- 去掉多余0，进行补位（开头是0就需要去掉）
1101  |  1101       --- 模2运算
1101  |  0011       --- 结果：第一位是0，去掉，得到0，第三位是0，
1101  |   0111      ---（开头是0就需要去掉，不需要模2运算）第一位是0，去掉，得到1，第四位是1，
1101  |    1110     --- 去掉多余0，进行补位（开头是0就需要去掉）
1101  |    1101     --- 模2运算
1101  |    0011     --- 结果：第一位是0，去掉，得到0，第五位是0，
1101  |     0110    ---（开头是0就需要去掉，不需要模2运算）第一位是0，去掉，得到1，第六位是1，
1101  |      1100   --- 去掉多余0，进行补位（开头是0就需要去掉）
1101  |      1101   --- 模2运算
1101  |      0001   --- 结果：第一位是0，去掉，得到0，第七位是0，
1101  |       001   ---（开头是0就需要去掉，不需要模2运算）第一位是0，去掉，得到0，第八位是0，--- 位数不足4为，结果是：101001 001

海明校验

海明校验是一种用于错误检测和纠正的校验码。它通过添加额外的校验位，可以检测和纠正比特错误。校验码的位置是2^k-1，海明码中的任何一位都是由若干个校验位来校验，被校验的海明位的下标等于所有参与校验该位的校验位的下标之和，而校验位由自身校验；海明校验可以有效地检测和纠正单个比特错误，但对于多个比特错误的检测和纠正能力有限。此外，海明码还存在一定的冗余，会增加数据的传输量。因此，在实际应用中，需要根据具体的需求和信道的特性选择合适的校验码。

例：待发送的信息1010，通过海明校验，奇校验规则下的海明码是？
数据位是n位，校验位数k位，则需要满足公式：2^k-1 = n + k
n=4，计算k值， 2^k-1 = 4 + k --- 2^k = 5 + k 得出 k = 3
公式：2^k-1 ，计算校验位的下标，k=1 下标是1 ， k=2 下标是2 ， k=3 下标是4
数据位是4位，校验位是3位，总共是7位
下标：1  2  3  4  5  6  7k1 k2 d1 k3 d2 d3 d41     0  1  0      填充数据位
----------------------------
通过分组得出:
1 k1  d1 d2     d4  --- 1+2=3(d1) 1+4=5(d2) 1+2+4=7(d4) --- 1 0 0 
2 k2  d1    d3  d4  --- 1+2=3(d1) 2+4=5(d3) 1+2+4=7(d4) --- 1 1 0
4 k3     d2 d3  d4  --- 1+4=5(d2) 2+4=5(d3) 1+2+4=7(d4) --- 0 1 0
因奇校验，数据中的1的个数为奇数，则奇校验位设置为0，否则设置为1
k1 --- 1 0 0  ---  0
k2 --- 1 1 0  ---  1
k3 --- 0 1 0  ---  0
下标：1  2  3  4  5  6  7k1 k2 d1 k3 d2 d3 d40  1  1  0   0  1  0   
得出海明码是：0110010 

存储系统

计算机系统中的存储系统指的是用于存储和访问数据的硬件和软件组件。

存储系统主要包括：

• 主存储器（主存）：也称为内存，是计算机中用于存储程序指令和数据的临时存储器。

• 辅助存储器（外存）：也称为二级存储器，用于长期存储数据和程序。常见的辅助存储器包括硬盘驱动器、光盘和闪存驱动器等。

• 高速缓存（Cache）：是位于主存储器和处理器之间的存储器层次结构中的一级缓存。高速缓存用于存储最近使用的数据和指令。

• 虚拟存储器：是一种将辅助存储器扩展到主存储器的技术。虚拟存储器使用页面置换算法将主存储器中的数据和指令分成固定大小的页面，当某个页面不再被频繁使用时，可以将其置换到辅助存储器中，以释放主存储器空间。

• 存储器控制器：是连接计算机系统的存储器和处理器的关键组件。存储器控制器负责管理数据在各个存储层次之间的传输和调度。

多级存储结构

• CPU寄存器：位于CPU内部的最快速度的存储器，用于存放指令和数据。寄存器的容量有限，但其访问速度非常快。

• 缓存存储器：位于CPU和主存之间的存储器，用于缓存主存中经常访问的数据和指令。缓存存储器的容量较小，但其访问速度比主存快很多。

• 主存（内存）：用于存放程序和数据的主要存储设备。主存的容量较大，但其访问速度相对较慢。

• 辅助存储器：包括硬盘、磁带等外部存储设备，用于长期存储大量的程序和数据。辅助存储器的容量很大，但其访问速度相对主存较慢。

高速缓存（Cache）与主存的地址映射是由硬件完成的，主存和外存之间是通过软件和硬件结合实现的。

Cache

计算机系统中的缓存（Cache）是一种高速存储器，用于暂时存储来自主存（RAM）的数据，以提高CPU访问数据的速度。缓存采用了快速的SRAM（静态随机访问存储器）技术，与主存相比，它具有更低的访问延迟和更高的带宽。程序员无法对Cache进行操作，

计算机系统中通常存在多级缓存，其中L1缓存是最接近CPU的一级缓存，通常包括数据缓存和指令缓存。L2缓存位于L1缓存之外，其容量较大，但速度稍慢。还可以有更多级的缓存，如L3缓存和L4缓存。缓存的层次结构主要是为了平衡容量和速度两个因素。

使用Cache改善系统性能的依据是程序的局部性原理：

• 时间局部性：被引用过一次的存储器位置在未来会被多次引用，主要体现是主要是循环。
• 空间局部性：如果一个存储器的位置被引用，那么将来他附近的位置也会被引用，主要体现是顺序执行的过程。

int[] arr = {1,2,3,4};
int sum = 0;
for(int i=0;i<arr.length;i++){sum = sum + arr[i];
}
// arr就是空间局部性 / sum是时间局部性

Cache的地址映像方法

• 直接映射：主存的块与 Cache块的对应关系是固定的；优点：硬件电路设计比较简单；缺点：冲突率较高，灵活性差；
• 全相联映射：主存与 Cache均分成大小相同的块，允许主存的任一块可以调入存储器的任何一个块的空间中；优点：冲突率较低、灵活性好；缺点：电路难于设计和实现，适用于小容量，无法从主存块号中直接获得 Cache的块号，变换比较复杂，速度比较慢；
• 组相联映射：将 Cache中的块再分成组，组采用直接映像方式而块采用全相联映像方式，直接相联与全相联的折中

Cache替换算法

也是页面淘汰算法，当我们主存的页面调入到Cache中经常会出现冲突，冲突就需要把一些页面淘汰出去，替换我们想要的页面；

• RAND：随机选择一个页面进行淘汰；优点：实现简单，对所有数据公平；缺点：不会有特定数据被频繁淘汰的问题，缺乏策略性；
• FIFO：淘汰最早被缓存的页面；优点：实现简单；缺点：对长时间驻留在缓存中的数据不友好；
• LRU：淘汰最久未使用的页面；优点：适用于热点数据，能够保留经常访问的数据；缺点：实现较复杂，需要维护访问时间的记录；
• LFU：淘汰访问频次最低的页面；优点：适用于长时间内不变的数据，能够保留经常被访问的数据；缺点：对频繁变化的数据不友好，需要计数器实现；
• LRU-K：基于最近一段时间内的访问情况进行淘汰；优点：能够平衡最近访问和长期访问的数据；缺点：实现较复杂，需要维护最近访问的记录；
• LRU-2：维护两个队列，淘汰最久未使用的页面；优点：简化了LRU的实现，提高了淘汰效率；缺点：不适用于有循环访问模式的数据；

Cache的读写过程

如果Cache里的页面被修改，Cache里的数据与主存中的数据会出现不一致的情况，这时候需要下面的方式进行解决：

• 写直达：同时写Cache与内存，这种效率慢，Cache更改，主存中的数据也进行更改；

• 写 回：只写Cache，淘汰页面时，写回内存，这样只写Cache，获取最新从Cache里获取，如果该页被淘汰，会把此时的数据，更新到内存中；

• 标记法：只写入内存，并将标志位清零，若用到此数据，只需要再次调取；这种效率会高，只写内存，在Cache里进行标记，如果后面在用该数据，看到此标记，会从主存中再次获取最新的数据，更新到Cache里使用；

磁盘管理

磁盘的盘面被划分一个个磁道，每个圈就是磁道；一个个磁道又被划分一个个扇区，每个扇区就是磁盘块；

机械磁盘存在两组运动，（旋转运动、线性运动）

• 旋转运动：机械磁盘内部有一个可旋转的磁盘盘片，通过电机驱动，磁盘盘片以高速旋转。数据的读写头会随着盘片的旋转，移动到指定的磁道上进行数据读写操作。

• 线性运动：机械磁盘的读写头不仅可以随着盘片的旋转运动，还可以在磁盘的半径方向上进行线性移动。通过线性运动，读写头可以准确地定位到指定的磁道上进行数据读写操作。

机械磁盘存取时间：

• 寻道时间（Seek Time）：即机械臂从当前位置移动到所需磁道的时间。机械臂的移动速度决定了寻道时间的长短。（移动不同磁道）

• 延迟时间（Latency Time）：即盘片旋转到所需扇区的时间。盘片的转速越高，延迟时间越短。（旋转不同扇区）

• 数据传输时间（Transfer Time）：即数据从磁盘读取或写入的时间。传输时间取决于数据的大小和磁盘的传输速度。

存取时间 = 寻道时间 + 延迟时间 + 数据传输时间

输入输出技术

在计算机系统中，CPU控制主存与外设直接的数据交换的过程。因内存速度快，外设速度慢，有了以下的传输的方式：

直接程序控制

在直接程序控制中，输入输出设备的操作是由计算机系统的程序直接控制的。这种方式CPU经常询问外设是否有数据进行传输，导致缺点：降低了CPU 的效率、对外部的突发事件无法做出实时响应；

程序中断方式

程序中断是指在执行程序的过程中，当需要进行输入输出操作时，会发生中断，将控制权转移到相应的I/O处理程序上，等待I/O操作完成后再将控制权还给原程序。这种方式IO设备准备好，会向CPU发送中断请求信号，CPU会保存正在执行程序的现场，去执行IO设备，处理完再回到被打断的程序，继续执行。使用场景有鼠标、键盘。

DMA

实现高速数据传输。它允许外部设备直接访问计算机的主内存，而不需要经过CPU的介入，从而提高数据传输的速度和效率。这种方式DMA进行负责管理数据的传输和存储，IO设置会发送一个DMA请求给DMA控制器，DMA控制器会占用CPU的总线，直接和内存进行数据传输，而不需要CPU的介入。一旦数据传输完成，DMA控制器会发送一个中断信号给CPU，通知数据传输的完成。使用场景有硬盘、显卡、声卡、视频播放、大规模数据处理。

DMA传输数据时占用系统总线，此时，CPU不能使用总线。

输入/输出处理机（IPO）

也称通道，对外围设备进行统一管理，用于处理与外部设备之间的数据输入和输出；IO不会走CPU和内存，在数据传输中走通道，大大提高CPU工作效率，这种效率是以更多的硬件为代价。

计算机体系结构

计算机体系结构，是指计算机硬件和软件之间的结构和组织方式。

Flynn分类法

是计算机体系结构的分类方法之一，分为单指令流单数据流(SISD)、单指令流多数据流(SIMD)、多指令流单数据流(MISD)和多指令流多数据流(MIMD)四种类型。

• SISD：指令流中只包含一条指令，只能处理一个操作数。它是传统的冯·诺依曼计算机体系结构，串行执行指令，早期计算机。

• SIMD：指令流中包含多个相同的指令，可以同时处理多个数据。这种体系结构适用于数据并行计算，如图形处理器(GPU - 显卡)。

• MISD：指令流中包含多条指令，这种体系结构并不常见，主要用于特定领域的应用，如冗余计算和错误检测。

• MIMD：指令流中包含多条指令，每个时钟周期可以同时处理多个数据。这种体系结构适用于任务并行计算，如分布式系统。

CISC与RISC

CISC（复杂）：它使用复杂的指令集，每个指令可以执行多种操作，数据量，使用频率差别大，可变长格式；寻址方式支持多种；实现方式是微程序控制技术（微码，研制周期长，代表：X86。

RISC（精简）：它使用简单的指令集，每个指令只执行一种操作，数量少，使用频率接近，定长格式；寻址方式支持方式少；实现方式是增加了通用寄存器，以硬布线逻辑控制为主，更适合采用流水线；优化编译，有效支持高级语言，代表：RISC-V、ARM。

流水线技术

流水线是指程序执行多条指令重叠进行操作的一种准并行处理实现技术。

如：执行一条指令的过程中，需要经历取指、分析和执行三个步骤。在串行情况下，执行指令取指、分析、执行操作各需要1ms，那么执行3条指令总需要9ms，我们使用流水线进行准并行执行，执行3条指令总需要5ms，可以大大提高时间的利用率。

流水线计算公式：

流水线周期 = 执行时间最长的一段

理论公式：(t1+t2+…+tk) + (n-1) * Δt ---- (单个执行时间) + 执行条数 - 1 * 流水线周期

实际公式：(k+n-1) * Δt ---- (几个 + 执行条数 - 1) * 流水线周期

流水线的吞吐率：指令总数 / 执行完毕所需的时间（流水线）

最大吞吐率：1 / 最慢阶段的处理时间

加速比：串行执行时间 / 并行执行时间

串行执行时间是指在没有使用流水线时，执行同样任务所需的时间；并行执行时间是指使用流水线后，执行同样任务所需的时间。

例：每个执行分解为取指、分析和执行三步，已知取指5Δt，分析2Δt，执行3Δt，求500条指令全部执行完需要时间？
公式: (t1+t2+…+tk) + (n-1) * Δt  
(5 + 2 + 3) + (500-1) * 5 = 10 + 499 * 5 = 2505

冯诺依曼结构和哈弗结构

冯诺依曼结构：

也称普林斯顿结构，是一种将程序指令存储器和数据存储器合并在一起的存储器结构。一般用于PC处理器，i3、i5、i7处理器，指令与数据存储器合并在一起；指令和数据都通过相同的数据总线传输。

运算器（ALU）负责进行数学和逻辑运算； 控制器（Control Unit）负责指挥和协调各个部件的工作； 存储器（Memory）用于存储程序和数据； 输入设备（Input Device）用于将数据输入计算机； 输出设备（Output Device）用于将计算结果输出。

哈佛结构:

是一种将程序指令存储和数据存储分开的存储器结构；主要特点是将程序和数据存储在不同的存储空间中，都是独立的存储器，每个存储器独立编址、独立访问；一般使用于嵌入式系统处理器（DSP）数字信号处理；指令和数据分开存储，可以并行读取，有较高的吞吐量；四条总线：指令和数据的数据总线与地址总线。