计算机组成原理
2022年考试题型分布：选择（10）、填空（18）、简答（22）、计算（15）、解答类大题（35）
各章分数大致分布：概论-5、RISC-V-10、数的表示和运算-25、存储器-25、数据通路-10、流水线-7、IO-10、总线-8
简答5道，4-3 + 5-2
- 对比中断方式
计算2道：7+8
- booth算法
- 加减交替相除
解答5道：7+7+7+7+7
- 分析数据通路与控制信号
- 手撸riscv
- 芯片组合
- cache设计
- 总线
概论
计算机发展历史
8个伟大思想
计算机层次结构
计算机硬件的主要指标
非时间指标：
- 机器字长：一次能处理的数据的位数，一般与内部寄存器的位数相等。常见的有32b和64b
- 总线宽度：数据总线一次能并行传送的最大信息位数
- 主存容量、带宽
- CPU内核数
时间指标：
- 主频、时钟周期：CPU工作的频率与周期(aka Cycle)
- CPI：Cycle Per Instruction. 某一程序CPU执行的时间 = 指令数 * CPI
- MIPS、MFLOPS：Million Instructions per Second, Million Floating-point Operations per Second
- CPU执行时间: 某一程序CPU执行的时间 = 指令数 * CPI
数的表示
无符号数和有符号数
无符号数：编码的全部二进制位都是数值位，没有符号位。
- 无符号数默认是正的
- n位的无符号整数的范围是：$0\sim 2^n-1$
- n位的无符号小数的范围是：$0\sim 1-2^{-n}$。注意，给定位数的情况下，小数是离散的，表示的是$m2^{-n}, m=0,1,…,2^n-1$。
有符号数：编码的最高位是符号位，0正1负。剩下的n-1位是数值位。
- 有符号数的范围问题比较复杂，原码和补码的情况并不相同。在下一节定点数的表示会详细讲到。
定点数
有符号机器数的定点表示：
原码表示法
用机器数的最高位表示符号，其余表示数值（数的绝对值）- 小数的原码举例：$+0.1101\to 0.1101\quad -0.1101\to 1.11001$
- 整数的原码举例：$+1100\to0,1100\quad -1100\to 1,1100$
- 原码对应的函数定义很显然，就不写了。
原码表示法的范围问题：（n+1位字长，其中有n位数值位）
- 小数的范围：$-(1-2^{-n})\sim 1-2^{-n}$
- 整数的范围：$-(2^n-1)\sim 2^n-1$
- 无符号数的表示实际上是原码表示。与之对比可以发现，有符号数的范围是可以用无符号数范围对称得到的。
原码表示法的优缺点：
- 优点：与真值的对应简单、直观，转换也简单
- 缺点：0的表示不唯一（+0和-0），并且原码加减运算比较复杂
反码表示法（了解）
反码和原码是完全类似的。在实际操作当中很少遇到。
反码的产生：
- 正数反码：等于原码
- 负数反码：原码符号位不变，数值位取反。
- 举例：$+1101\to 0,1101\quad -1101\to 1,0010$
补码表示法（重点）
计算机当中的数字运算是以补码的形式完成的。补码解决了原码的两个缺点。
补码的产生：
- 正数补码：同原码
- 负数补码：原码符号位不变，数值位取反，再+1
- 举例：$+1101\to0,1101\quad -1101\to1,0010+1\to1,0011$
补码的函数表示：
- 负小数：$[x]_b = 2-x$
- 负整数：$[x]_b=2^{n+1}-x$（其中，n+1为字长，包括符号位和数值位）
补码的范围：（n+1位字长，其中有n位数值位）
- 小数：$-1\sim 1-2^{-n}$
- 整数：$-2^n\sim 2^n-1$
- 在补码当中，0的表示是唯一的：0, 0
- 相比与原码，多出了$-1, -2^n$，他们由原来的-0（1, 0000）表示
补码转化原码：一样的数值取反+1。
移码表示法
在真值上加一个偏移常数（通常$2^n$，n+1为字长，n位数值位），得到移码。
移码只用来表示整数。
移码的函数表示：$[x]_y=2^n+x$，n+1为字长。
移码与补码的联系：补码符号位取反就是移码。
浮点数
浮点数的表示：$N = S\times r^j$
- S是尾数，本质上是一个小数，可+|-
- r是基数，在计算机中常用2，4，8，16
- j是阶码，表示基数的阶
- 类比：科学计数法$51522\to 0.51522\times 10^6$
数值存储：$j_f|j_1\sim j_m|S_f|S_1\sim S_n$
- $S_f$代表浮点数的符号
- n反应浮点数的精度
- m反应浮点数的表示范围
- $j_f， m$表示小数点的实际位置（决定了阶码）
浮点数的范围：
- 先看S的范围：$S\in [-(1-2^{-n}),-2^{-n}]\cup[2^{-n}, 1-2^{-n}]$（不考虑0先）
- 再看j的范围：$j\in [-(2^m-1), 2^m-1]$
- 结合 $N = S\times r^j$可以得到浮点数的范围：
- 最大正数：$(1-2^{-n})2^{2^m-1}$, 最小正数：$2^{-n}2^{-(2^m-1)}$
- 最大负数：$-2^{-n}2^{-(2^m-1)}$, 最小负数：$-(1-2^{-n})2^{2^m-1}$
- 可以看出，范围是对称的。
浮点溢出：
- 上溢：大于最大正数|最小负数。阶码大于最大阶码
- 下溢：小于最小正数大于最大负数，按0处理。阶码小于最小阶码
浮点数的规格化：
- 定义：$r=2, \quad \frac{1}{2}\le |S|<1.$
- 判断：
- 原码的判断简单，看第一数位为1即可。
- 补码的判断：符号位与第一数位不同。
- 举例：$x=-1/2,\quad [x]_y = 1.1000\to yes!\quad [x]_b=1.1000\to no!$
- 范围：尾数规格化后的范围会发生变化，发生在小正和大负。这是因为规格化为尾数S添加了最小限制：$|S|\ge \frac{1}{2}$。（原来是$|S|\ge 2^{-n}$）
在浮点机当中的书写：$[x]_y=[j]_y; [S]_y.$
当阶码用移码，尾数用补码时，机器0为0, 000; 0.0000。有利于电路实现。
IEEE754
IEEE 754 标准格式：：$S_f|j_f|j_1\sim j_m|S_1\sim S_n$
IEEE 754当中的尾数规格化格式是1.1—，如1100 = $1.1\times 2^{100}$。1被隐含了。
IEEE 754当中的指数是通过移码表示的。
规格化数
(float) $=(-1)^{S_f}\times(1+S)2^{j-127}$
(double) 类似，偏移为1023。
非规格化数
此时j = 0， S != 0。
(float) $= (-1)^{S_f}\times S\times2^{0-126}$
数的运算
算数与逻辑移位
算术移位：右移的时候添加符号位
逻辑移位：右移添加0、
算术左移和逻辑左移是一样的。
定点运算
定点运算是考察的重点。
难点在于乘除法：原码一位乘、Booth乘法、加减相除法。
定点加减法
定点数的加减法在计算机中以补码的形式进行。
- 加法：$[A+B]_b=[A]_b+[B]_b$
- 减法：$[A-B]_b=[A]_b+[-B]_b$
判断溢出：只有符号相同的数，同正或者同负，相加，才会发生溢出。
- 采用一位符号位：
- $C_s$是符号位的进位
- $C_1$是第一数位（最高位）的进位
- Let $V = C_s\oplus C_1.$ If V = 1, 溢出
- 采用两位符号位：
- 运算数符号位重复书写，再相加。如11, 1100 +11, 1010
- 若结果的双符号位不同，溢出。
- 最高符号位代表运算结果的真正符号
定点乘法
原码一位乘
原码乘法的时候，被乘数和乘数都以绝对值的形式进行。最后得到结果再添加符号位。
原码乘法引入了“部分积”作为中介。
原码乘法实际上就是不断地“加、移”，乘数有n数值位就重复n次。
加法规则：
- 末位为1，加被乘数
- 末位为0，加0
例如：计算 -0.1101*0.1011。首先先取绝对值，计算-0.1101*0.1011
| 部分积 | 乘数 | 说明 |
|---|---|---|
| 0.0000 0.1101 | 1011 + | 初态。 末位为1，+0.1101 |
| 0.1101 0.0110 0.1101 | 1011 1101 + | / >> 1 1, +0.1101 |
| 1.0011 0.1001 0.0000 | 1101 1110 + | / >> 1 0, +0.0000 |
| 0.1001 0.0100 0.1101 | 1110 1111 + | / >> 1 1, +0.1101 |
| 1.0001 0.1000 | 1111 1111 | / >> 1得到结果 |
结果是负的。所以结果就是-0.10001111
从上面的过程可以看到，四数值位乘数，加了四次移位四次。
补码一位乘（Booth算法）
Booth算法改善了原码一位数要单独计算符号的问题。正负数可以直接通过补码参与乘法运算。
Booth算法与原码一位乘类似，也引入了部分积。同样是重复进行了“加、移”的运算。
不同的地方在于：
- Booth算法的被乘数有两个符号位，并且乘数也有一个符号位。
- Booth算法的加法规则不同：
- 在乘数后添加了一个辅助位0。
- 检验$y_{n+1}-y_{n}$，若为$1\to +[x]_b, \quad 0\to +0,\quad -1\to +[-x]_b.$
- 移位：注意是算术右移。
- Booth算法的计算次数不同：
- 对于n+1位乘数（含一位符号），加法做n+1次
- 移位做n次
定点除法
原码恢复余数法
符号位单独处理，然后在绝对值下进行除法运算。令$y^*=|y|$。
步骤：
- 初态，直接加上$[-y^*]_b$
- 看新的部分余数：
- 如果余数为正，则末位上商1。左移一位，再加上$[-y^*]_b$
- 如果余数为负，则末位上商0。然后将此余数加上$[y^*]_b$，得到原先的余数（也可以直接还原）。左移一位，再加上$[-y^*]_b$
- 重复操作。对于n+1位的余数（1位符号），需要做n+1次上商，n次左移。
- 商可以直接读出，余数还需要逻辑右移n位。
例如，计算 $x=0.1011, y=0.1101, x/y.$
$[y*]_b=0.1101, \quad [-y*]_b=1.0011$
| 被除数（余数） | 商 | 说明 |
|---|---|---|
| 0.1011 1.0011 | _ _ _ _ _ + | / +[-y*]b |
| 1.1110 0.1101 | _ _ _ _ 0 + | 余数为-，上0 恢复余数，+[y*]b |
| 0.1011 1.0110 1.0011 | _ _ _ _ 0 _ _ _ 0 + | 恢复后 << 1 +[-y*]b |
| 0.1001 1.0010 1.0011 | _ _ _ 01 _ _ 01 + | +, up 1 << 1 +[-y*]b |
| 0.0101 0.1010 1.0011 | _ _ 011 _ 011 + | +, up 1 << 1 +[-y*]b |
| 1.1101 0.1101 | _ 0110 + | -, up 0 恢复余数，+[y*]b |
| 0.1010 1.0100 1.0011 | _ 0110 0110 + | 恢复后 << 1 +[-y*]b |
| 0.0111 | 01101 | +, up1 |
可以看到，商为0.1101，余数为0.0111*2^{-4}。
原码不恢复余数法（加减交替法）
比恢复余数法更简单一点，步骤如下：
- 先加[-y*]b
- 若余数为正，上1，左移，加[-y*]b
- 若余数为负，上0，左移，加[y*]b
- 同样，0.0000上商5次，移位4次
浮点运算
浮点加减法
对于两个浮点数$x= S_x2^{j_x}, y=S_y2^{j_y}$
- 对阶
- 对阶的原则：小阶向大阶看齐。
- 阶变大，尾数右移一位
- 阶变小，尾数左移一位
- 对齐之后，对尾数进行一个定点的加减运算。
- 尾数求和
- 规格化
- 左规(如0.0100)
- 右规(如S>1)
- 舍入：对阶和右规的时候，可能会出现尾数末位丢失。需要考虑舍入。
- 0舍1入法：类似四舍五入，0则直接舍去，1则末位加1。
- 恒置1法：只要舍去的位数当中有1，就把末位置1。
- 判断溢出：通过由指数上溢来判断。（下溢会直接当作机器0处理）。
RISC-V
没啥好说的。。
处理器
数据通路
目标是看懂下面的图
几个信号：
- PCSel: 对应MUX，1选择跳转0选择PC+4
- ImmSel：对应Imm Gen，*表示不生成立即数，B表示生成B型立即数，S、I、J、U等。注意，ld是I型，jalr也是I型
- RegWEn：寄存器写使能信号，为1表示允许写寄存器
- BrEq：表示等于信号
- BrLt：表示less than信号
- BrUn：表示符号信号，1表示无符号u比较，当BrLt有效时，BrUn有效
- BSel：图中下面的MUX，控制发出data2或者imm
- ASel：data1或者PC
- ALUSel：表示选择alu的功能，实际上有四位
- MemRW：选择读或者写主存
- WBSel：*表示不写回，有值的话，可以写回alu、dm、pc+4的数据
- Br信号、WB、Imm可以有*，其他必须有值
流水线：
存储器
存储器的内容很抽象，除了上课之外，推荐购买额外的课外辅导《王道考研 计算机组成原理》。
最好是购买最新正版，配套的视频资源讲的很好，一定要看看。
存储器概述
存储器的分类
- 按作用（层次）
- 主存（aka 内存）
- 高速缓冲存储器（aka Cache）
- 辅存（aka 外存）
- 按存储介质
- 磁表面存储器：磁盘、磁带
- 磁芯存储器
- 半导体存储器：MOS型存储器、双极型存储器
- 光存储器：光盘
- 按存取方式
- 随机存储器（RAM）：可以随机存取，且与存储单元的物理位置无关。主要用于主存/Cache。
- 只读存储器（ROM）：只能读不能写。但是信息的存储十分稳固。用来存放固定不变的程度、常数、字库等。现在的ROM有些已经可以重写了，但是依然保留了断电内容保留、随机读取的特性。
- 串行访问存储器：读写操作要按照物理顺序进行，无法随机。如磁带光盘磁盘。
存储器的性能指标
存储容量
单位成本
存储速度：
- 存取时间$T_a$。启动一次存取操作到完成的时间
- 存取周期$T_m$。两次存取操作的间隔时间
- 主存带宽aka 数据传输率。B/s 或 b/s 或 w/s
存储器的层次结构
存储器的层次结构如下图所示。
结构主要体现在
- Cache-主存层：解决了CPU与主存速度不匹配的问题
- 主存-辅存层：解决了存储系统的容量问题
在存储体系当中，Cache、主存可以与CPU直接交换信息。而辅存需要通过主存才能与CPU交换信息。
注意，上层内容是下层内容的一部分。
主存
主存的基本组成
- 基本元件：存储元，每个存储元存储一个bit的信息。其中包含了
- MOS管：半导体作为通电开关，给出一个高电压时，MOS管接通，低电压断开
- 电容：有无存储电荷来对应1/0。可以通过充电放电来控制其中的电荷
- MOS管和电容联动，可以实现存储元的读写
- 几个（通常8个）存储元用一根线连接，可以形成一个存储单元（通常1B）
- DRAM芯片结构：
- 译码驱动电路：MAR传入地址译码器，对应到某一根地址线以及对应的存储单元。
- 存储矩阵（aka 存储体）：由多个存储单元构成，每个存储单元由多个存储元构成。现代计算机一般按照字节编址，即一根地址输出对应一个字节。支持字节、字、双字、半字等多方法寻址。
- 读写电路：控制读写
- 线路：地址线、数据线、片选线、读写控制线（可2根可1根）
- 芯片描述：存储单元数量X存储字长
SRAM & DRAM 芯片
SRAM用于Cache， DRAM用于主存。
高频考点是两者的对比。
特性差异
- DRAM使用栅极电容，SRAM使用双稳态触发器（6个MOS管集合）
- DRAM中读取是破坏性的，电容放电后就没电了。所以我们需要重写再生，补充电荷
- SRAM不用。
- SRAM速度更快，省去了重写的步骤
- SRAM更贵（用了6个MOS）
- SRAM集成度低，因为用了6个MOS体积更大
- SRAM功耗更大（还是因为6MOS）
- DRAM需要刷新，SRAM不用
- 由于电荷在电容中只能保持1~2ms，因此刷新周期一般是2ms
- 每次刷新一行存储单元
- 由于在地址线位数多的情况下，地址输出线会好多（如20位对应1M输出）。因此我们考虑二维存储，将地址的前半段和后半段，分别给行、列地址译码器，这样只需要2*1k条线。
- 当一个存储单元的行、列线同时供电，才会进行选中读写。
- 一次刷新占用一个读写周期。
- 刷新是由存储器独立完成的，不需要CPU的控制。
- DRAM行列地址不同时送出
- 这是因为DRAM通常容量更大，地址线更多，为了节省地址线、减少芯片引脚，先后输出。可以使引脚减少一半。（地址线利用技术）
比较幽默的是现在DRAM已经过时了，现在主存一般用SDRAM 😓😓
DRAM的刷新
- 分散刷新：在一次读取之后马上刷新，显然这样将原来的存取周期延长了一倍。同一行可能在2ms内刷新多次，效率很低。
- 集中刷新：每隔2ms进行一次集中的刷新
- 异步刷新：为了保证每一行在2ms内都刷新一次，将2ms分成若干段，每隔一定时间发送一次刷新请求，刷新其中的一行。
ROM
只读存储器（Read Only Memory）。
ROM和RAM的根本区别在于断电之后是否丢失。
ROM的类型
- MROM（Mask ROM）厂家提前写好，写入后无法改变内容。灵活性差，但是成本低、可靠、集成高
- PROM（Programmable ROM） 允许用户写入一次，写完不可更改
- EPROM（Erasable PROM）可以多次改写，但是次数有限，且时间比较长
- Flash存储器 EPROM 超级升级版
- SSD （Solid State Drives） Flash超级升级版
主存与CPU
连接
- 位扩展：利用空余的数据线
- 字扩展：利用空余的地址线和译码器
- 同时扩展：构图的时候，位扩展用层叠，字扩展用展开，先位后字
其他的也说不清楚，还是看看远处的ppt和书吧家人们。
必考。
提高访存速度
采用高速器件
采用Cache-主存层次结构
调整主存结构
回顾一个知识点：存取周期T = 存取时间r + 恢复时间
- 以读为例，存取周期是两次读操作的间隔
- 存取时间是一次读完成需要的时间
- 读1——恢复——读2——恢复。。。
多模块存储器：
- 单体多字存储器：每次并行读出m个连续的字。但是如果数据在两行内（如xxDD|DDxx），则需要读两行。
- 高位交叉编址：
- 地址：体号|体内地址
- 这样的方法下，连续的两个地址大概率是存储在同一个存储体当中，这意味着我们仍然需要等待很多的恢复时间。
- 因此虽然理论上是并行的，在实际效果上，相当于单纯的扩容
- 低位交叉编址：
- 地址：体内地址|体号
- 显然，连续的两个地址是存储在两个不同的存储体当中的。如100|00和100|01分别存储在00号和01号存储体里面。
- 如此在访问100|00之后，00号开始冷却，cpu可以在00冷却的同时直接访问100|01。实现了流水线访存
- 为了实现不间断的流水线，应当使得$m\ge T/r。$如果综合考虑成本、集成等，m = T/r 最佳。
- 如此一来，读取n个字花费的时间为t = T + (n-1)r。当$n\to\infty, \quad \bar{t}\to r$.
汉明码
汉明码有数值位n和检测位k构成，n与k之间的关系满足：$2^k\ge n+k+1$。
以4位数值位为例，那么需要3位检测位。也就是说，总共有7位Hamming code.
编号如下：
| H1 | H2 | H3 | H4 | H5 | H6 | H7 |
|---|---|---|---|---|---|---|
| T1 | T2 | C3 | T4 | C5 | C6 | C7 |
可以看出来，检测位的位置在$2^i(i=0,1,2…)$。其余位是数值位。
接下来分组，对于三个检测位$T_4T_2T_1$，分组要使得Tn组的数，对应的Tn位为1。如T1组的数为3(011), 5(101), 7(111)。可以列出以下矩阵得到。
| T4 | T2 | T1 | |
|---|---|---|---|
| C3 | 0 | 1 | 1 |
| C5 | 1 | 0 | 1 |
| C6 | 1 | 1 | 0 |
| C7 | 1 | 1 | 1 |
观察每列，得到：T4: 5,6,7|T2: 3,6,7|T1: 3,5,7
接下来有两种检测方法：
- 配偶检验规则：要使得T1, C3, C5, C7四位当中1的个数为偶数。则$P_1 = T1\oplus C3\oplus C5\oplus C7 = 0, \to\ T_1=C3\oplus C5\oplus C7$
- 配奇检验规则：要使得T1, C3, C5, C7四位当中1的个数为奇数。则$P_1 = T1\oplus C3\oplus C5\oplus C7 = 1, \to\ T_1=C3\oplus C5\oplus C7 \oplus 1$
纠错的过程：
- 偶检验：先求出$P_1, P_2, P_4$。正确的code会使得Pn为0，错误的code会使得Pn为1。若Pn为1，说明Pn组（对应位为1）的数中有问题，否则没有。因此，令$x=P_4P_2P_1$，则Cx位出错。
- 奇检验：同理，正确code使Pn为1，错误code使Pn为0。则$x=\overline{P_4P_2P_1}$。
Cache
概述
块
为了方便数据交换，主存与Cache都划分出了相同大小的块（如1KB），进行数据交换。主存的块aka 页，Cache的块aka 行。
地址可以拆分为（块号|块内地址）的形式
工作原理
Cache的速度通常来说会比主存快几十倍，所以我们可以将某些主存块复制到Cache当中，供cpu快速调用，缓和cpu和主存之间的速度矛盾。
介绍局部性原理：
- 空间局部性：现在访问的地址，其附近的地址也可能在将来被访问（如指令、数组）
- 时间局部性：现在访问的地址，将来可能被再次访问（如循环结构）
性能分析
- 命中率H：要调用的内容恰好在Cache中的概率
- 缺失率M：1 - H
- 平均访存时间：令t_c表示Cache的访存时间，t_m表示主存的。
- 先访问cache，未命中再访问主存：$T = Ht_c+(1-H)(t_c+t_m)$
- 同时访问cache和主存，cache命中就终止访问主存：$T = Ht_c+(1-H)t_m$
- 效率：$e = \frac{t_c}{T}$
Cache-主存地址映射
本节探讨一个问题：如何将主存上的块对应到cache上？
- 全相联映射
- 全相联映射将主存上的块对应到cache的任意一行。
- 此方法下，地址结构为标记|块内地址
- 由于主存的块可以对应到cache的任意一行，在寻址的时候需要遍历cache的每一行，逐个比对tag，判断是否命中。
- 显然，优点是充分利用了cache内的空间，命中率高
- 缺点是查找tag缓慢
- 直接映射
- 直接映射则是将主存上的块固定地对应到某一行。
- 对应行号 = 主存块号 % 总行数
- cache总有8行，主存1号、9号、17号都会映射到cache的1行。
- 此方法下，地址结构是标记|cache行号|块内地址
- 在查找的时候，只需根据行号找到对应的cache行，比对此行数据的tag即可。
- 显然，优点是查找速度快
- 缺点是浪费了很多空间，命中率低
- 直接映射与全相联映射是两个极端。
- 组相联映射
- 组相联映射可以看成是全相联映射和直接映射的结合。
- 将cache的所有行分成若干组，主存的块可以映射到组内的任意一行。
- 对应组号 = 主存块号 % 总组数
- 优点：折中，综合效果更好
- 术语：n路组相联映射：n个cache行为一组
cache中存储的信息：有效位+标记+整块数据
缓存替换
解决这样一个问题：缓存满了之后，新来的主存替换到哪里？
对于直接相联，主存块能填的坑是固定唯一的，因此不需要考虑这个问题。
对于全相联，主存块可以填到任意一个cache行
对于组相联，可以填到固定的某组内的任意一个cache行
就替换而言，可以有四种不同的算法：
- 随机算法RAND：随便选一个cache行替换
- 显然，效果很差，命中率低
- 先进先出（FIFO）：先填入的cache行先被替换
- 没有考虑到局部性，命中率低
- 容易发生抖动（同个主存块频繁进出）
- 近期最少使用（Least Recently Used）：统计最近最少被命中的cache行，将其替换
- 为2^n个cache行添加一个n bit的计数器，统计cache行寂寞了多少个回合
- 每次读cache就修改每一行的计数器
- 要替换时，选择最大的那个cache行（近期最少被命中的）
- 基于局部性原理，效果好，命中率高
- 最不经常使用（Least Frequently Used）：统计全局最少被命中的cache行
- 需要准备一个很大的计数器，统计访问次数
- 命中了就加1，需要替换时，选取最小的cache行
- 在这种情况下，不同行的计数器可能会相等，可以考虑使用行增序、FIFO等原则
- 没有很好地遵循局部性原理，因为曾经常用的现在并不一定常用。实际效果不如LRU，而且需要一个很大的计数器。
Cache写方法
我们讨论写命中时的写策略。有以下两种方法：
- 写回法
- 写命中时，只修改cache当中的内容，不立即写入主存。
- 当cache行被替换时，写回主存
- 需要添加一个脏位，标记一个cache行是否被修改过
- 优点是节省了访存次数，更快
- 缺点是有数据不一致的隐患
- 写直达法
- 写命中是，修改cache的同时，修改主存对应的块
- 优缺点与写回法相反
- 可以作用写缓冲来改进，写缓冲由SRAM制成，由专门的电路负责写主存
虚拟存储器
感觉不是重点。
虚拟存储器对应用程序员是透明的，对系统程序员不是。
虚存具有主存的速度和辅存的容量。
虚存体系下，主存-辅存结构有点类似于cache-主存。
呃呃，你的女神也可能是别人的天勾。
辅助存储器
看图吧
RAID 0/1/3/5/10
3和5的区别在于校验信息的位置不同。
总线系统
基本概念
总线：总线是一级能够为多个部件分时共享的公共信息传送线路。
- 分时是指同一时刻只允许有一个部件向总线发送信息
- 共享是指总线上可以挂接多个部件，接受同个信息。
总线上的信息发送，有串行、并行两种。
- 串行：一次是传输一个bit
- 并行：有多条传输线，可以传输多个bit
- 串行的成本更低，更稳定
- 并行虽然可以传输多个bit，但是会容易发生干扰，要注意控制同步传输
分类
计算机系统当中的总线，按照功能可以分成以下三类。
- 片内总线：指CPU芯片内部的总线，是CPU内部寄存器之间、寄存器与ALU之间的公共连接线
- 系统总线：是计算机系统内各个功能部件（CPU、主存、I/O接口）之间相互连接的总线。按照 传输信息内容不同，可以分成3类：
- 数据总线：双向，与机器字长、存储字长有关
- 地址总线：单向，由cpu传出。与存储地址、I/O地址有关
- 控制总线：有出（CPU控制读写存储器、总线确认、中断确认），有入（中断请求、总线请求）
- 通信总线：计算机系统之间，或者计算机系统与其他系统之间的通信。传输方式有两种：
- 串行通信总线
- 并行通信总线
特性与性能指标
总线特性
- 机械特性：尺寸、形状、管脚数、排列
- 电气特性：传输方向、有效的电平范围（如0~0.4V为低电平）
- 功能特性：每根传输线的功能，如地址、数据、控制
- 时间特性：信号的时序关系
- 总线带宽：总线工作频率 * 总线宽度
性能指标
- 总线宽度：数据线有多少根
- 标准传输率：每秒传输的最大字节数
- 时间同步/异步
- 总线复用：地址线与数据线的复用
- 信号线数：地址线、数据线与控制线的总和
- 总线控制方式：突发、自动、仲裁、逻辑、计数
- 其他指标：负载能力
总线结构
根据总线数目的不同，可以分成单总线、双总线、三总线、四总线的结构。
单总线结构
单总线结构只包含了一套系统总线，连接了所有的系统内部件。CPU、主存、I/O接口可以通过单总线传输信息。如下图所示。
- 优点：结构简单，成本低，便于接入新的设备
- 缺点：带宽低、负载重（只有一条），并且多个部件争夺一条线，不支持并发传送的操作
双总线系统
双总线系统是对单总线系统的改进版本，原来的系统总线上，分成了主存总线和I/O总线。IO总线用于管理IO设备。主存总线和IO总线通过硬件设备通道进行连接。
- 优点：将低速的IO设备从单总线上分离出来，实现总线的分离
- 缺点：需要增加通道等硬件设备
三总线结构
进一步地改进了双总线结构。cpu依然和主存通过主存总线连接，而对于IO接口，低速IO设备通过IO总线与CPU连接（速率慢），高速的IO设备则通过DMA总线与主存连接，通过主存作为中介，和CPU交换信息。
- 优点：提高了IO设备的性能，使其更快地响应命令，提高系统吞吐量
- 缺点：系统工作效率比较低
此外，还有另一种形式的三总线结构。主存和cpu不直接相连了，而是使用cpu—局部总线—cache—系统总线—主存。IO则接在局部总线上。剩下的接扩展总线，扩展总线与系统总线连接。
四总线结构
现代计算机常用的总线结构，但是在考试中不是重点。有四条总线：局部总线、系统总线、扩展总线、高速总线。
主存和cpu不直接相连了，而是使用cpu—局部总线—cache—系统总线—主存局部总线—cache—系统总线。
总线控制
总线的精华😓😓😓
总线通信控制的目的：解决通信双方的协调配合问题。
两个概念：
- 主设备（aka 主模块）：对总线有控制权
- 从设备（模块）：响应从主设备发来的总线命令
总线传输周期
- 申请分配阶段：需要使用总线的主设备提出申请，经总线仲裁机构决定将下一传输周期的总线使用权授予申请者。可以细分为请求阶段和仲裁阶段。
- 寻址阶段：主模块向从模块给出地址和命令。
- 传输阶段：主模块和从模块交换数据
- 结束阶段：主模块撤消有关的信息。
总线定时
总线定时是指总线在双方交换数据的过程当中需要时间上的配合关系的控制，这种控制称为总线定时。实质上是一种协议或者规则，主要有同步和异步两种基本定时方式，另外还有半同步通信、分离通信两种方式也会介绍到。
同步通信：由一个统一的时钟控制数据传送的节奏。
以写为例，如下图所示。
- 在T1，主设备给出地址，并准备数据
- 在T2，主设备给出写命令，并提供数据
- 在T3，从设备开始写入
- 在T4，结束后主设备撤消有关的信息
可以看出，同步的优点在于传输速度快、总线控制逻辑简单。缺点在于主从设备是强制性同步，从设备有可能速度跟不上时钟的节奏。并且没有校验的时间，可靠性比较差。
异步通信：取消了公共时钟，主从设备采用应答的方式，类似于“握手”。有三种方式：
不互锁方式：主设备发出请求后，过一段时间自动撤回，无需回应。从设备的回答也是如此。
半互锁方式：主设备发出请求后，需要接受到回答，才撤消。而从设备的回答过一段时间自动撤消。
全互锁方式：主设备发出请求后，需要接受到回答，才撤消。而从设备要到主设备撤消之后才会撤消回答。
可以看出，优点是总线周期长度可变，可以保证速度相差很大的两个设备也能够进行通信，并且可靠。缺点是控制方式比较复杂，而且速度更慢。
半同步通信：对同步通信的另一个修正方法。
我们注意到，在T2之后，是从设备响应的时间。如果此时从设备还没准备好提供数据，那么就提供一个$\overline{WAIT}$信号，暂时停滞，留出新周期Tw给从设备进行准备和响应。
以上的三种通信都有一个共同点，就是在从模块准备数据的时候，总线是空闲的。只有在主模块发地址、命令，以及从模块向主模块发数据的时候，是占用总线的。基于此，为了更好地利用总线空闲，我们提出分离式通信。
分离式通信：充分挖掘系统总线每个瞬间的潜力。对于一个总线传输周期，分离成两个子周期：
- 主模块申请占用总线，发完地址和命令之后，放弃总线的使用权
- 从模块申请占用总线，将各种信息送到总线
这时，准备数据时不占用总线，允许在总线空闲的时间内，有其他的主从设备使用总线。利用了中间的总线空闲时间。
注意，采用同步方式通信。否则无法释放中间的空闲时间。
输入/输出系统
概述
真的感觉不是重点，随便写写。
外部设备：
- 输入设备
- 输出设备
- 外部存储器（需要通过IO接口）
- 其他
IO控制方式：
- 程序查询方式：由cpu通过程序不断查询IO设备是否已经准备好，从面控制io设备与主机交换信息。cpu和io串行工作。
- 程序中断方式：只在io设备准备就绪并向cpu发出中断请求时，主机停下手头的工作，予以响应。cpu和io并行工作。
- DMA方式：主存和io设备之间有一条直接数据通路，当主存和io设备交换信息时，无需调用中断服务程序。cpu和io并行工作。
前两个主要用于数据传输率低的外部设备。
IO接口
接口的功能和组成与连接
| 功能 | 组成 | 连接 |
|---|---|---|
| 选址、选设备 | 设备选择电路 | 设备选择线 |
| 传送命令 | 命令寄存器、命令译码器 | 命令线 |
| 传送数据 | 数据缓冲寄存器 | 数据线 |
| 反映设备状态 | 设备状态标记 | 状态线 |
与总线的连接：
cpu-io接口-外部设备的连接：
程序查询方式
“好了没好了没好了没？”
- 优点：接口设计简单，设备量、操作量少
- 缺点：cpu花费大量时间在查询和等待，且一段时间内只能交换信息，效率很低
程序中断方式
“好了叫我”
中断系统：
PC在每次执行完指令都会检验，外部设备是否有传过来中断信号。如果有中断信号，那么PC需要跳转到中断服务程序，去处理传过来的中断。
如何向cpu发送中断请求？
一个中断请求源，对应一个INTR（中断请求标记触发器）
多个INTR组成了中断请求标记寄存器
INTR分散在各个中断源的接口电路中
或者集中在cpu的中断系统内
各个中断源同时提出请求怎么办？
- 需要按照处理优先级，如输入中断大于输出中断，高速中断大于低速中断。
- 在硬件上通过中断排队器实现。（即逻辑门的组合）集中在各个中断源接口，或者在cpu内。
- 在软件上可以通过查询程序实现。
cpu如何响应中断？
cpu在执行完一条指令后会检验是否满足响应条件。- 中断触发器中有中断请求信号
- cpu开中断（即处于可以接受中断请求的状态）。异常和不可屏蔽中断不受此限制。
- 一条指令执行完毕。异常不受此限制。
如果有中断的话，cpu执行中断隐指令。
- 中断隐指令不是某个指令，是一系列硬件自动操作的统称。包括：
- 关中断
- 保存断点，到栈或者寄存器当中
- 引出中断服务程序
即PC跳向中断服务程序入口。
如何确定入口的地址？- 硬件上可以使用硬件向量法，由排队器输出产生向量地址，该地址储存了入口地址。思考：为什么不直接排队器输出入口地址？
- 在软件上可以使用软件查询法
中断服务程序做了什么？
- 保护现场：除了保护程序断点（由中断隐指令完成，硬件实现），还需要保护寄存器的内容（由进栈指令完成，软件实现）。
- （置屏蔽字）如果有
- （开中断）如果多重
- 中断服务：对不同的io设备具有不同内容的设备服务
- （关中断）如果多重
- 恢复现场：由出栈指令实现
- （恢复屏蔽字）如果有
- 开中断
- 中断返回：由中断服务程序的最后一条中断返回指令完成。
单重中断和多重中断
单重中断：在执行中断服务程序的过程中，又出现了新的更高优先级的中断请求。如果不理会，就是单重中断
多重中断：如果选择暂停当前的中断服务，转去处理更高级的请求，则是多重中断，aka 中断嵌套。
屏蔽字：
- 响应优先级是固定规则的
- 但是处理优先级是可以使用中断屏蔽技术动态调整的。每个中断源有一个屏蔽字寄存器，内有若干位屏蔽触发器，对应不同的中断源。1表示屏蔽，0表示可以正常申请。
DMA方式
DMA控制器
主要功能：
- 传送前：接受外设的dma请求，向cpu发出总线请求；接管总线控制权
- 传送时：管理总线，控制数据传送；确定主存单元地址与长度，能自动修改去就参数
- 传送后：向cpu报告dma操作结束。
组成：
- 主存地址寄存器AR：存放要交换数据的主存地址
- 传送长度计数器WC：记录传送数据的长度
- 数据缓冲突破器DR：暂存每次传送的数据
- DMA请求触发器：设备准备好数据后将其置位，启动一次读写操作
- 控制／状态逻辑：由控制和时序电路及状态标志组成
- 中断机构：数据传送完成后提出中断请求
传送过程
- 预处理（由cpu完成）
- 主存起始地址–>AR
- IO设备地址—>DAR
- 传送数据个数—>WC
- 启动IO设备
- 数据传送
- 设备将数据写入DR
- 写完后DMA控制器向总线发起请求，获得总线控制权
- DMA控制器接管总线后，通过数据线将DR的数据传送给主存
- 完成传送后，AR和WC+1
- 重复设备数据写入DR
- 后处理
- 当传送完成，WC溢出。溢出信号给中断机构
- 中断机构发出中断信号，给cpu处理。
特点
- 使得主存与cpu脱钩，主存可以被cpu或者外设访问
- 数据传送时，主存地址的确定、传送数据的计数等由硬件实现
- 主存当中要开辟专用的缓冲区，及时供给和接受外设的数据
- dma传送速度很快，cpu和外设并行工作，提高了效率
- dma在传送前要通过程序进行预处理，结束后通过中断进行后处理
传送方式
由于主存可以被cpu和外设访问，这里就有一个问题，他们想同时访问主存的时候，如何解决冲突？
停止cpu访存：dma工作的时候，停止cpu访存，总线控制权交给dma
交替访存：平分时间，dma与cpu交替访问
周期窃取：由于dma并不是一直占用总线的，只在部分的时间内占用总线访问主存。考虑三种情况：
- cpu此时不访存：dma直接拿下
- cpu正在访存：等待cpu这个存取周期结束
- cpu和dma同时访存：dma先上
可以看出来，这样的思想和分离式通信是类似的。
中断方式与DMA方式对比
| 中断 | DMA | |
|---|---|---|
| 数据传送 | 程序控制 | 硬件控制 |
| 中断请求 | 传送数据的时候 | 后处理的时候 |
| 响应中断 | cpu执行指令后 | 总线空闲的时候即可 |
| 控制 | cpu控制 | DMA控制器 |
| 场景 | 低速设备 | 高速设备 |
| 优先级 | low | high |
| 异常处理 | 可以处理异常 | 不能处理异常 |