第一章——计算机系统基础

前言：
计算机第一章节主要知识点。

1 知识点介绍

数值转换；
数的表示；
计算机的组成；
流水线；
多级存储结构；
I/O控制方式；
可靠性、校验码；

2 数值转换

进位计数制系统基本概念：数制、基数、数码、数位、位权。

特点/数制	十进制	二进制	八进制	十六进制
基本数码	0-9	0, 1	0-7	0-9, A-F
基数	10	2	8	16
位权	$10^n$	$2^n$	$8^n$	$16^n$

2.1 BCD码

是一种二进制的数字编码形式，用4位二进制数来表示1位十进制数。

2.2 8421码

8421码是BCD码的一种，它表达的意思是每一个二进制位上的数据对应一个固定的值，只需要把对应的1位置的数据值相加，即可得到该二进制对应的十进制值。

$$
0b1010100 = 64 + 16 + 4 = 84
$$

$$
100 = 0b1100100
$$

2.3 N进制转十进制

使用按权展开法，将N进制的每一位数用 $N^k$ 形式表示，N为底数/基数，k为指数。

二进制转十进制

$$
0b10100.01 = 1 \times 2^4 + 1 \times 2^2 + 1 \times 2^{-2}
$$

八进制转十进制

$$
604.01 = 6 \times 8^2 + 4 \times 8^0 + 1 \times 8^{-2}
$$

2.4 十进制转N进制

使用短除法。以下是示范从十进制转二进制。

          余
2 |_94_ ---0
2 |_47_ ---1
2 |_23_ ---1
2 |_11_ ---1
2 |__5_ ---1
2 |__2_ ---0
     1  ---1

从下往上写余数，因此 94 = 0b1011110

2.5 二进制和八进制互转

每3位二进制表示一个八进制数。

二进制：010 001 110
八进制： 2 1 6

2.6 二进制和十六进制互转

每4位二进制表示一个十六进制。

二进制： 1000 1110
十六进制： 8 E

2.7 数据的存储单位

在计算机中，数据的最小存储单位为bit（位，简写为b），1bit为一个二进制数。字节Byte（简写为B）有8个bit。为8个二进制数。

1Byte = 8bit
1kB = 1024B
1MB = 1024kB
1GB = 1024MB
1TB = 1024GB

$1024 = 2^{10}$

2.8 二进制算术运算

算术运算：加减乘除，逻辑运算：与或非异或同或。

2.8.1 例题

内存按字节编址从A5000H到DCFFFH的区域其存储容量为（D）。

A. 123kB
B. 180kB
C. 223kB
D. 224kB

内存按字节编址，地址从90000H到CFFFFH，若用存储容量为16k × 8bit的存储器西片构成该内存，至少需要（D）片。

A. 2
B. 4
C. 8
D. 16

内存按字节编址，从A1000H到B13FFH的区域的存储容量为（C）kB。

A. 32
B. 34
C. 65
D. 67

地址编号从80000H到BFFFFH且按字节编址的内存容量为（B）kB，若用16k × 4bit的存储芯片构成该内存，共需（C）。

A. 128
B. 256
C. 512
D. 1024

A. 8
B. 16
C. 32
D. 64

移位指令中的（A）指令的操作结果相当于对操作数进行乘2操作。

A. 算术左移
B. 逻辑右移
C. 算术右移
D. 带进位循环左移

3 数的表示

数在计算机中都是以二进制存储的，数在计算机中的表示就是 机器数 。
机器数的真值：符号位 + 相应进制的数值。比如正1的二进制真值为+0001，十进制真值为+1。

3.1 码制

码制包含原码、反码、补码、移码。

码制	数值+1	数值-1	1+(-1)
原码	0000 0001	1000 0001	1000 0010
反码	0000 0001	1111 1110	1111 1111
补码	0000 0001	1111 1111	0000 0000
移码	1000 0001	0111 1111	1000 0000

计算机中常用补码进行加减法运算，而移码常用于浮点数的阶码。

码制	整数数值范围
原码	$-(2^{n - 1} - 1)$ ~ $2^{n - 1} - 1$
反码	$-(2^{n - 1} - 1)$ ~ $2^{n - 1} - 1$
补码	$-2^{n - 1}$ ~ $2^{n - 1} - 1$
移码	$-2^{n - 1}$ ~ $2^{n - 1} - 1$

3.2 定点数和浮点数

3.2.1 定点数（定点表示法）

小数点的位置固定不变的数，小数点不需要占用一位二进位。包括 定点整数 和 定点小数 。
定点小数小数点隐含在二进制符号位和数值位中间。

$$
x_0 x_1 x_2 x_3 … x_n(.)
$$

$x_0$ 为符号位。

3.2.2 浮点数（浮点表示法）

就是科学计数法。
$N = R^e \times M$ R是基数，由于计算机用二进制存储数据，因此R固定为2，指数e为阶码，M为尾数。浮点数的表示有点类似科学计数法，如： $0.985 \times 10^2$ 。浮点数在计算机中存储格式如下。

$$
N = M \times R^e
$$

如。

$$
0.985 \times 10^2
$$

M: 为尾数；
e: 为指数（阶码），带符号；
R: 为基数（阶码的底）；

1	对阶 -> 尾数计算 -> 结果格式化

阶符	阶码	数符	尾数
阶码的符号	决定数值表示的范围	N的符号	决定数值表示的精度

阶符：阶码e的符号；
阶码：用移码表示，表示数值的范围；
数符：N的符号。
尾数：决定数值表示的精度，位数越多精度越高；

尾数的小数点左移n位阶码加n，右移n位阶码减n。
浮点数的计算需要进过3个过程：对阶 -> 尾数计算 -> 结果格式化 。
浮点数相加，第一步先使阶码相等即对阶，然后将尾数相加，最后格式化为科学计数法（小数点后十分位为非0）。

对阶：使阶码相等；
尾数计算：对尾数进行算术计算；
结果格式化：整数部分为0，小数点后第一位为非0；

3.2.2.1 例题

机器字长为n位的二进制数可以用补码来表示（A）个不同的有符号定点小数。

A. $2^n$
B. $2^{n - 1}$
C. $2^n - 1$
D. $2^{n - 1} + 1$

如果“2X”的补码是“90H”，那么X的真值是（B）。

A. 72
B. -56
C. 56
D. 111

某机器字长为n，最高位是符号位，其定点整数的最大值为（B）。

A. $2^n - 1$
B. $2^{n - 1} - 1$
C. $2^n$
D. $2^{n - 1}$

4 计算机的组成

计算机（硬件）组成（冯诺依曼）：输入设备、输出设备、存储器、运算器、控制器。控制器就像大脑，发出指令控制计算机各个部分协调工作。（计算机系统包括软件和硬件两大部分。）

输入设备

功能：把相关的程序和数据输入到存储器中进行保存。如：键盘、鼠标等。

输出设备

功能：输出存储器中的相关数据数据。如：打印机、显示器等。

运算器

功能：进行逻辑和算术运算。如：加减乘除、与或非等。

控制器

功能：控制协调其他设备工作，发送相关的控制命令，去命令相关的设备执行操作。

存储器

功能：存储数据。如：硬盘、内存等。包括主存储器（内容（ROM和RAM））和辅助存储器（硬盘）。

运算器 + 控制器就是中央控制单元CPU；

存储器包括辅助存储器（比如硬盘）、主存储器（内存（RAM、ROM））；

输入设备 + 输出设备 + 辅助存储器就是外部设备；

主存储器 + CPU就是主机；

工作流程简述：控制器发送控制命令给输入设备，输入设备将数据传入存储器中，在控制器指令的作用下，把程序的指令一条条送到控制器中，控制器对指令进行译码，根据指令的操作要求向存储器和运算器发送指令，向运算器发运算命令，想存储器发取数命令，经过运算器的运算将结果保存到存储器中，又在控制器的命令下将结果输出到输出设备中。

4.1 重要寄存器

4.1.1 运算器

算术逻辑单元ALU：数据的算术运算和逻辑运算；
累加寄存器AC：通用寄存器，为ALU提供了一个工作区，用于暂存数据；
数据缓冲寄存器DR：写内存时，暂存指令或数据；
状态条件寄存器PSW：存状态标志与控制标志（争议：也有将其归类为控制器的）；

4.1.2 控制器

程序计算器PC：存储下一条要执行指令的地址；
指令寄存器IR：存储即将执行的指令；
指令译码器ID：对指令中的操作码字段进行分析解释；
时序部件：提供时序控制信号；

计算机执行的过程：PC - > AR -> ROM -> DR -> IR -> ID 。

4.1.2.1 例题

在CPU中，常用来为ALU执行算术逻辑运算提供数据并暂存运算结果的寄存器是（D）。

A. 程序计数器
B. 状态寄存器
C. 通用寄存器
D. 累加寄存器

计算机指令一般包括操作码和地址码两部分，为分析执行一条指令，则其（C）。

A. 操作码应存入指令寄存器（IR），地址码应存入程序计数器（PC）。
B. 操作码应存入程序计数器（PC），地址码应存入指令寄存器（IR）。
C. 操作码和地址码都应存入指令寄存器（IR）。
D. 操作码和地址码都应存入程序计数器（PC）。

4.2 基本概念

CPU的性能指标：主频、字长、CPU缓存、核心数量；
- 主频：CPU内核的时钟频率，即CPU运算时的工作频率，单位是Hz；
- 字长：单位时间内能同时处理的二进制位数；
- CPU缓存：一般CPU缓存的运行速度和CPU速度相当，缓存越大命中率越高，但成本高；
- 核心数量：多个CPU并行处理；
总线的分类：数据总线、地址总线、控制总线；
总线的性能指标：带宽、位宽、工作频率；
BIOS/CMOS；
- BIOS：基本输入输出的程序，存储在ROM中是一段程序。BIOS通过硬盘引导程序MBR加载操作系统的内核到内存中；
- CMOS：是一块RAM芯片，设置参数保存在该芯片中，该芯片有一块单独的电池供电；
系统性能评测方法：时钟频率、指令执行、等效指令速度法、数据处理速率（PDR）、核心程序法、基准测试程序；
- 时钟频率：时钟频率越高性能越好；
- 指令执行：单位时间内执行的指令越多性能越好，单位是kIPS（每秒多少指令）、MIPS。有精简指令集、复杂指令集；
- 等效指令：把不同种类的指令按比例来分，计算出需要多少时间；
- 核心程序法：编写程序测试运行时间；
- 基准测试程序：针对不同领域编写专门的测试程序；

4.3 总线系统

一条总线同一时刻仅允许一个设备发送，但允许多个设备接收。分为系统总线和外部总线。

4.3.1 总线的分类

数据总线（Data Bus）：在CPU与RAM之间来回传送需要处理或是需要储存的数据。为双向传输总线（CPU读写）；
地址总线（Address Bus）：用来指定在RAM（Random Access Memory）之中存储的数据的地址。单向传输（CPU到外部设备）；
控制总线（Control Bus）：将微处理器控制单元（Control Unit）的信号，传送到周边设备，一般常见的为USB Bus和1394 Bus。双向传输（CPU与外部设备）；

4.3.2 总线的性能指标

带宽、位宽、工作频率。

带宽：总线在单位时间能传输的数据总量，单位是字节每秒（B/s）；
位宽（宽度）：数据的宽度，如：32位、64位，单位是位（bit）；
工作频率：总线的工作频率，单位时间内能传输多少次，单位是Hz（1/s）；

1	带宽 = 位宽 * 工作频率

4.3.3 例题

处理机主要由处理器、存储器和总线组成，总线包括（A）。

A. 数据总线、地址总线、控制总线；
B. 并行总线、串行总线、外部总线；
C. 单工总线、双工总线、外部总线；
D. 逻辑总线、物理总线、内部总线；

总线宽度为32bit，时钟频率为200MHz，若总线每5个时钟周期传送一个32bit的字，则该总线的带宽为（C）MB/s。

A. 40
B. 80
C. 160
D. 200

4.4 指令

4.4.1 基本概念

一条指令就是机器语言的一个语句，是一组有意义的二进制代码。


操作码字段OP	地址码字段A
指出了计算机要执行什么性质的操作（如：加减乘除与或非等）	包含各操作数的地址及操作结果的存放地址等

例如。

指令						含义
4字节指令	OP	$A_1$	$A_2$	$A_3$	$A_4$	表示 $A_1$ OP操作 $A_2$，结果存入 $A_3$，将 $A_4$ 指向下一条即将执行的地址。
3字节指令	OP	$A_1$	$A_2$	$A_3$		省略 $A_4$ 使用PC代替 $A_4$ ，依次执行即PC加1。
2字节指令	OP	$A_1$	$A_2$			省略 $A_3$ ，将结果放在累加器ACC中。
1字节指令	OP	$A_1$				$A_2$ 操作数在ACC中。
0字节指令	OP					入栈（PUSH）和出栈（POP）就是0地址指令。

SISC: 精简指令集；
CISC: 复杂指令集；

4.5 寻址方式

运址是找操作数的地址或者下一条将要执行的指令地址。数据和指令存储在存储单元中的，需要进行编号，在存储单元中寻找数据和指令就是寻址。寻址有多种方式（为了扩大寻址范围和增加寻址灵活性）。

立即寻址方式：操作数直接在指令中，速度快，灵活性差；
直接寻址方式：指令中存放的是操作数的地址；
间接寻址方式：指令中存放了一个地址，这个地址对应的内容是操作数的地址；
寄存器寻址方式：寄存器存放操作数；
寄存器间接寻址方式：寄存器内存放的是操作数的地址；

4.5.1 例题

若CPU要执行的指令为：MOV R1，#45（即将数值45传送到寄存器R1中），则该指令中采用的寻址方式为（B）。

A. 直接寻址和立即寻址
B. 寄存器寻址和立即寻址
C. 相对寻址和间接寻址
D. 寄存器间接寻址和直接寻址

指令系统中采用不同寻址方式的目的是（D）。

A. 提高从内存获取数据的速度
B. 提高从外存获取数据的速度
C. 降低操作码的译码难度
D. 扩大寻址空间并提高编程灵活性

4.6 流水线

多条指令重叠进行操作的一种准并行处理实现技术。通过流水线可以提高指令执行的速度。

取指 -> 分析 -> 执行 ->

4.6.1 流水线计算公式。

4.6.1.1 流水线周期

执行时间最长的一段（ $\Delta t$ ）。
如流水线把一条指令分为三部分，及k = 3，个部分对应的执行时间为：取指 $t_1$ 、分析 $t_2$、执行 $t_3$ ，则流水线周期为 $t_1$ 、 $t_2$ 、 $t_3$ 。

4.6.1.2 流水线执行时间（ $T_k$ ）

1条指令执行时间 + （指令条数 - 1） * 流水线周期

理论公式： $(t_1 + t_2 + … + t_k) + (n - 1) \times \Delta t$
实践公式： $k \times \Delta t + (n - 1) \times \Delta t$

4.6.1.3 流水线吞吐率（TP）

计算的最基本的公式为： $TP = \frac{n}{T_k}$
流水线最大吞吐率：流水线周期的倒数（ $\frac{1}{\Delta t}$ ）。

4.6.2 例题

若指令流水线把一条指令分为取指、分析和执行三部分，且三部分的时间分别是取指2ns，分析2ns，执行1ns。那么流水线周期是？100条指令全部执行完毕需要的时间就是？

答：三部分的执行时间最长一段是 $\Delta t = 2$ ，那么100条指令执行完的执行时间为 $(2 + 2 + 1) + (100 - 1) \times 2 = 203$ 。

若指令流水线由5段组成，第1、3、5段所需时间为 $\Delta t$ ，第2、4段所需时间分别为 $3 \Delta t$ 、 $2 \Delta t$ ，如下图所示，那么连续输入n条指令时的吞吐率（单位时间内执行的指令个数）TP为（B）。

-> $\Delta t$ -> $3 \Delta t$ -> $\Delta t$ -> $2 \Delta t$ -> $\Delta t$ ->

A. $\frac{n}{5 \times (3 + 2) \Delta t}$
B. $\frac{n}{(3 + 3 + 2) \Delta t + 3(n - 1) \Delta t}$
C. $\frac{n}{(3 + 2) \Delta t + (n - 3) \Delta t}$
D. $\frac{n}{(3 + 2) \Delta t + 5 \times 3 \Delta t}$

4.7 多级存储器结构

存储器被组织成金字塔层次结构。存储器自上而下，组成6个层次结构，依次变得更慢，访问频率低、容量更大、每字节的造价更便宜。

4.7.1 Cache

4.7.1.1 高速缓存Cache

功能：提高CPU数据输入输出的速率，突破所谓的“冯诺伊曼瓶颈”；
速度：在计算机的存储系统中，Cache是访问速度较快的层次；
原理：使用Cache改善系统性能的依据是程序的局部性原理；
组成：Cache由两部分组成：控制部分和Cache存储器部分；

平均系统周期时间（以读操作为例：使用“Cache + 主存储器”）

$$ t_3 = h \times t_1 + (1 - h) \times t_2$$

h代表对Cache的访问命中率， $t_1$ 表示Cache的周期时间， $t_2$ 表示主存储器的周期时间，系统的平均周期时间为 $t_3$ ，(1 - h)又称为失败率（未命中率）。

4.7.2 地址映像

通常由SRAM（Static Random Access Memory静态存储器）组成。其访问速度远高于主存，接近CPU；
其功能是提高CPU数据输入输出速率。其理论依据是程序的局部性原理。实现基础是将主存和Cache划分成大小相同的块/页；
装入缓存时将主存块与Cache块的映射关系存入相联存储表（硬件实现）中；
CPU通过主存地址访存时先访问Cache（命中可提升速度，所以其关键性能指标是命中率），依据主存地址关联相联存储表转换为Cache地址。如果在Cache没有，才需要访问主存（Cache页置换，置换算法会影响命中率）。

4.7.3 直接映像和变换

主存储器中一块只能映像到cache的一个特定的块中；
主存与缓存分成相同大小的数据块；
主存空间按缓存容量分成区，每一区的块数与缓存的总块数相等；
主存中某区的一块存入缓存时只能存入缓存中块号相同的位置；

特点：

地址变换电路简单，访问速度快；
空间利用率低，冲突概率高；
对页面置换算法依赖度较高，且Cache空间利用率较低，命中率较低；

4.7.4 全相联地址映射和变换

主存的任意一块可以映像到cache中的任意一块的位置上；
主存与缓存分成相同大小的数据块；
主存的某一数据块可以装入缓存的任意一块空间中；

特点：

空间利用率高，命中率较高；
冲突概率低；
实现复杂，速度慢，适合小容量cache；

4.7.5 组相联地址映像和变换

主存和cache按同样大小分块；cache分为若干组，如两块一组，主存按cache组数分区；
每个组采用直接映射地址方式；
组内的块则采用全相联映射方式；

特点：

是以上两种方式的折中；
实现难度和造假要比直接映射方式高；

4.8 输入输出设备管理

直接程序控制：无条件传输方式、程序查询方式（CPU会阻塞）；
中断方式（CPU不阻塞）；
直接存储器存取方式（DMA）：在传送数据块的过程中不需要CPU干涉；
输入输出处理机（IOP）；

4.9 中断的概念

中断是指计算机在执行期间，系统内发生任何非寻常的或非预期的急需处理事件，使得CPU暂时中断当前正在处理的程序而转去执行相应的时间处理程序，待处理完毕后又返回原来被中断处继续执行的过程。
根据中断源产生的条件，可以把中断分为外部中断和内部中断；

外中断：是指来自处理机和内存外部的中断，包括I/O设备发出的I/O中断，外部信号中断、各种定时器引起的时钟中断，以及程序调试中设置的断点等引起的调试中断等。外部中断在狭义上一般称为中断；
内中断：主要是指在处理机和内存内部产生的中断。内中断一般称为陷入或异常，包括程序运算引起的各种错误，如算术操作溢出、数据格式非法、除数为零等。

4.10 可靠性

用 $R_n$ 表示第n个部件的可靠度，则失效率为 $1 - R_n$ ，则可靠性计算公式如下。

4.11 校验码

奇偶校验、CRC、海明校验码。

什么是检错和纠错？
什么是码距？

字母	合法码字	非法码字	码距	检错纠错能力
A = 1, B = 0	1, 0	-	1	不能检错和纠错
A = 11, B = 00	11, 00	10, 01	2	能检错不能纠错
A = 111, B = 000	111, 000	001, 010, 011, 100, 101, 110	3	能检错和纠1位错