总复习

这个「总复习」是根据老师提供的总复习 PPT 整理的。

大部分内容实际上都是从原笔记复制过来的，额外包括少量一些我复习时的注记，以及原笔记不包括的内容等。

有一部分内容因为篇幅较长，我就没复制过来，而是直接给予了原笔记的链接。同时大部分标题下面都有提供原笔记链接。

计算机系统概述

计算机硬件的基本组成

硬件是具体物理装置的总称。

计算机硬件主要包括：

1. 中央处理器（CPU）：主要用于指令的执行。主要包含两种基本部件：
   • 数据通路：主要包含：
     • 算术逻辑部件（ALU）：执行算术和逻辑运算等操作；
     • 通用寄存器：暂存指令所用的操作数或执行结果。
   • 控制器：对指令进行译码，生成相应的控制信号，以控制数据通路进行正确的操作。
2. 存储器：分为：
   • 内存：包括：
     • 主存储器（主存）
     • 高速缓存（Cache）
   • 外存：包括磁盘存储器和态硬盘等直接和主存交换信息的存储器。
3. 外部设备（外设、I/O 设备）：外设通常由机械部分和电子部分组成，而且两部分通常是可以分开的，机械部分是外部设备本身，而电子部分则是控制外部设备的设备控制器。
4. I/O 控制器：外设通过设备控制器连接到主机上，各种设备控制器统称为 I/O 控制器、I/O 接口或 I/O 模块。
   • 键盘接口、打印机适配器、显示控制器（显卡）、网络控制器（网卡）等都是一种设备控制器。
5. 总线：传输信息的介质，用于在部件之间传输信息，CPU、主存和 I/O 模块通过总线互连，在 CPU 和 I/O 模块中都内含相应的存储部件，即各类寄存器或缓存器。

一个典型计算机系统的硬件组成如下图所示：

计算机软件的分类

软件包括运行在硬件上的程序和数据以及相关的文档。计算机软件就是指存储和运行在计算机硬件中的程序。

一般将软件分成：

• 应用软件：专门为数据处理、科学计算、事务管理、多媒体处理、工程设计以及过程控制等应用所编写的各类程序。
• 系统软件：为有效、安全地使用和管理计算机，以及为开发和运行应用软件而提供的各种软件。
  • 如操作系统（Windows）、语言处理系统（C 语言编译器）、数据库管理系统（Oracle）、各类实用程序（备份程序）等。

计算机系统的抽象层及其转换

抽象层

计算机系统的抽象层次为

硬件/软件	抽象层次	用户
软件	应用（问题）	最终用户
	算法	程序员
	编程（语言）
	操作系统/虚拟机
-	指令集体系结构（ISA）	架构师
硬件	微体系结构
	功能部件/RTL
	电路	电子工程师
	器件

转换

抽象层转换：

1. 算法和程序
2. 编程语言
   • 高级语言
   • 低级语言：机器语言、汇编语言
3. 语言处理系统
   • 汇编程序（assembler）：用来将汇编语言源程序翻译成机器语言目标程序
   • 解释程序（interpreter）：用来将源程序中的语句按其执行顺序逐条翻译成机器指令并立即执行。
   • 编译程序（compiler）：用来将高级语言源程序翻译成汇编语言或机器语言目标程序。
4. 操作系统
5. 指令集体系结构
6. 微体系结构

用户 CPU 时间计算

对应笔记

CPI 是执行一条指令所需的时钟周期数。对于一条指令，CPI 是确定值；对于一个程序或机器，综合 CPI 是所有指令的平均时钟周期数。

$$\boxed{ \begin{aligned} \text{用户 CPU 时间} &= \text{程序总指令条数} \times \text{CPI} \times \text{时钟周期}\\ &= \text{程序总指令条数} \times \text{CPI} \div \text{时钟频率} \end{aligned} }$$

Amdahl 定律

对应笔记

对系统中某部分（硬件或软件）进行更新所带来的系统性能改进程度，取决于该部分被使用的频率或其执行时间占总执行时间的比例。

$$\begin{aligned} \text{改进后的执行时间} &= \dfrac{\text{改进部分执行时间}}{\text{改进部分的改进倍数}} + \text{未改进部分执行时间}\\ \text{整体改进倍数} &= \dfrac{1}{\frac{\text{改进部分执行时间比例}}{\text{改进部分的改进倍数}} + \text{未改进部分执行时间比例}} \end{aligned}$$

即

$$\boxed{p = \dfrac{1}{\frac{t}{n} + 1 - t}}$$

其中

• $p$ 是整体改进倍数；
• $t$ 是改进部分执行时间比例；
• $n$ 是改进部分的改进倍数。

数据的机器级表示

大部分可参见《计算系统基础》笔记。

二进制、八进制、十六进制、十进制数之间的转换

比较简单，略。

原码、补码、移码表示法

比较简单，略。

无符号整数、带符号整数表示

比较简单，略。

浮点数的表示

$$n = (-1)^s \times 2^{E-e} \times 1.f$$

其中：

• 符号位 $s$
• 指数位 $E$
• 分数位 $f$

IEEE 754 浮点数表示

• 单精度：
  • 符号位 $s$：1 位
  • 指数位 $E$：8 位
  • 偏移量 $e$：127
  • 分数位 $f$：23 位
• 双精度：
  • 符号位 $s$：1 位
  • 指数位 $E$：11 位
  • 偏移量 $e$：1023
  • 分数位 $f$：52 位

C 语言中的整数、浮点数类型

略。

数据的存储和排列顺序

比特（bit）是计算机中最小的存储单位，只能存储 0 或 1。比特是「二进制位」（binary digit）的缩写。

8 个比特组成一个字节（byte），一个字节能表示 256 种不同的状态。

计算机中信息使用的单位除比特和字节外，还经常使用字（word）作为单位。不同的计算机，字的长度和组成不完全相同。

在考察计算机性能时，一个很重要的性能参数就是机器的字长。平时所说的「16 位」「32 位」机器中的 16、32 就是指字长。所谓字长通常是指 CPU 内部用于整数运算的数据通路的宽度。

字长等于 CPU 内部用于整数运算的运算器位数和通用寄存器宽度。

左边字节称为高字节，右边字节称为低字节。

• 大端（big endian）：高位优先
• 小端（little endian）：低位优先

如 0123 4567H 在 0800H ~ 0803H 这四个存储单元中的存储顺序：

运算方法和运算部件

常见的汇编指令

理解并能写出常见的汇编指令，尤其是算术运算、逻辑运算涉及的指令。

RTL(Register Transfer Language) 规定

• R[r]：通用寄存器 r 的内容
• M[addr]：存储单元 addr 的内容
• M[R[r]]：寄存器 r 的内容所指存储单元的内容
• PC：PC 的内容
• M[PC]：PC 所指存储单元的内容
• SEXT(imm)：对立即数 imm 进行符号扩展
• ZEXT(imm)：对立即数 imm 进行零扩展
• 传送方向用 <- 表示，即传送源在右，传送目的在左

可以看看《计算系统基础》笔记「MIPS 指令集」。

串行、并行、带标志的加法器原理

对应笔记

详细内容可见《计算系统基础》笔记——4. 运算方法和运算部件。

全加器

设输入为加数 $A$、被加数 $B$ 和低位进位 $C_{\mathrm{in}}$，输出为和 $F$ 和高位进位 $C_{\mathrm{out}}$。则有

$$\left\lbrace\begin{aligned} F &= A \oplus B \oplus C_{\mathrm{in}} \\ C_{\mathrm{out}} &= A \cdot B + A \cdot C_{\mathrm{in}} + B \cdot C_{\mathrm{in}} \end{aligned}\right.$$

详细内容见《计算系统基础》笔记中关于「全加器」的介绍。

《计算系统基础》笔记中用的是 $S$，这里是 $F$，下同。

「串行进位加法器」见《计算系统基础》笔记中关于「行波进位加法器」的介绍。

并行进位加法器

串行进位加法器采用串行逐级传递进位，电路延迟与位数成正比关系。因此，现代计算机采用一种先行进位（carry look ahead）方式。

定义辅助函数

$$\left\lbrace\begin{aligned} G_i &= X_i \cdot Y_i, &\text{进位生成函数}\\ P_i &= X_i + Y_i, &\text{进位传递函数} \end{aligned}\right.$$

全加逻辑方程

$$\left\lbrace\begin{aligned} F_i &= X_i \oplus Y_i \oplus C_{i-1} \\ C_{i+1} &= X_i \cdot Y_i + (X_i + Y_i) \cdot C_i = G_i + P_i \cdot C_i \end{aligned}\right.$$

通过计算 $G_i$ 和 $P_i$，可以直接计算出 $C_{i+1}$，而不需要等待 $C_i$ 传递过来。

详细内容见《计算系统基础》笔记中关于「先行进位加法器」的介绍，里面的式子解释更为详细，同时还有不同颜色的标注。

《计算系统基础》笔记中 $P_i$ 定义为 $X_i \oplus Y_i$，这没差，而且 $F_i$ 里也会用到。

带标志加法器

对于溢出标志 $\mathrm{OF}$ 有

$$\mathrm{OF} = C_n \oplus C_{n-1}$$

对于符号标志 $\mathrm{SF}$ 有

$$\mathrm{SF} = F_{n-1}$$

对于零标志 $\mathrm{ZF}$ 有

$$\mathrm{ZF} = 1 \iff F = 0$$

对于进位/借位标志 $\mathrm{CF}$ 有

$$\mathrm{CF} = C_{\mathrm{in}} \oplus C_{\mathrm{out}}$$

补码加减运算

列竖式即可，略。

乘除运算

原码乘法

对应笔记

$10 \times (-6)$ 原码一位乘法过程如下：

移位采用逻辑右移。

有几位就加几次。

计算的时候，要是 P 部分溢出了一个 1，记得保留。例如 $11 \times 7$ 的过程中可能会出现 0101 + 1011，这时候会得到 1 0000，这个 1 不能舍弃，而是要等右移的时候加上去。或者就像上图那样，在 P 左边加个 C 位。

补码乘法

对应笔记

$10 \times (-6)$ 补码布斯乘法过程如下：

规则就是 01 加，10 减，其他不动。

移位采用算术右移。

有几位就加几次。

跟上面不太一样的是，这时候溢出的 1 不用保留。例如 $11 \times (-7)$ 过程中可能会出现 111010 + 001011，这时候会得到 1 000101，这个 1 应该舍弃，即右移后变成 000010，而非 100010。

原码除法

对应笔记

$10 / (-6)$ 原码不恢复余数法除法过程如下：

不恢复余数法含义就是：若中间余数为正，上商为 $1$，做减法；若中间余数为负，上商为 $0$，做加法。因此也被称为加减交替法。

比较方便书写的方式基本就是上面的改版：已经获得的商与前面用逗号分隔，同时左移空出来的位以及当前步骤得到的上商使用方框框起来，也为下一步是 $+Y$（0）还是 $-Y$（1）做准备。

有几位就加几次再加一次（例如上面的例子有 4 位，加了 5 次），这是因为 Q 多了一位。

同样的，溢出的 1 不用保留，例如上面最后的 1110 + 0110，应该是 1 0100，但是应该舍弃变成 0100，而不用算入结果中。

另外最后上商为 0 时必须恢复余数，把试商时减掉的余数加回去。这个我还没遇到例子。

补码除法

对应笔记

$10 / (-6)$ 补码不恢复余数法除法过程如下：

被除数的扩展，如果是负数的话，那 R 初始就是全 1。

中间余数与除数同号时，说明够减，上商为 1；异号时，说明不够减，上商为 0。

有几位就加几次再加一次（例如上面的例子有 5 位，加了 6 次）。

这样的得到的商多了一位，最高位是用来判断是否溢出的（像上图就通过最后单独将 Q 左移抹去了那个 1）。

若被除数与除数同号，则计算结果就是商；若异号，则计算结果为商加 1（异号说明商为负，要取反加一，取反已经完成了）。这就是商的修正。

若余数与被除数同号，则计算结果就是余数；若异号，则按下面的规则进行余数的修正：

1. 被除数符号与除数符号相同时，最后余数加上除数；
2. 被除数符号与除数符号不同时，最后余数减去除数。

乘除运算溢出判断

无符号整数乘法溢出判断

$n$ 位 $x \times y$ 乘积 $2n$ 位取低 $n$ 位，高 $n$ 位为溢出标志，即高 $n$ 位全零则未溢出，否则溢出。

有符号整数乘法溢出判断

$n$ 位 $x \times y$ 乘积 $2n$ 位取低 $n$ 位，高 $n$ 位为溢出标志，即若高 $n$ 位每一位与低 $n$ 位最高位相同则未溢出，否则溢出。

整数除法溢出判断

只有 $-2^{31} / -1$ 时会溢出。

常量乘除运算

对应笔记

变量与常量乘除运算时，往往以移位、加法、减法的组合运算实现。

对于乘法和无符号整数除法，组合得到的结果和直接相乘/除结果一样。

对于有符号整数除法，若被除数 $x$ 小于零，对于 $x / 2^{k}$，则需要先将 $x$ 加上 $2^{k} - 1$，再右移 $k$ 位校正，否则 $x$ 移位后会向 $-\infty$ 舍入。

浮点数加减运算、舍入方式

加减运算

对应笔记

主要应该就是「对阶」和「规格化」需要注意吧。

对阶操作，目的是使两数阶码相等：

1. 小阶向大阶看齐，阶小的那个数的尾数右移，右移位数等于两个阶码差的绝对值
2. IEEE 754 尾数右移时，要将隐含的 1 移到小数部分，高位补 0，移出的低位保留到特定的「附加位」上

对阶要采用下面的「舍入」方法。

规格化就是，例如两个很大的数（1.b + 1.c，可能得到 1d.e），就需要「右规」（变成 1.de）；而左规则是运算后得到了高位为 0 的结果，因为不合标准，需要进行「左规」（把小数点左移，变成 1 在小数点前）。

舍入

对应笔记

IEEE 754 规定：舍入方式为最近偶数舍入，即舍入到最接近的偶数。这种舍入方式可以减小舍入误差。

舍入方式：

• 就近舍入：舍入到最近的可表示的数。对于非中间值，0 舍 1 入，对于中间值，舍入到最接近的偶数。
  • $1.1101 \textcolor{FF0099}{11} \to 1.1110$
    • 11：向上舍入
  • $1.1101 \textcolor{FF0099}{01} \to 1.1101$
    • 01：向下舍入
  • $1.1101 \textcolor{FF0099}{10} \to 1.1110$
    • 10：中间值，舍入到最接近的偶数
  • $1.1111 \textcolor{FF0099}{10} \to 10.0000$
    • 10：中间值，舍入到最接近的偶数
• 正向舍入：朝 $+\infty$ 方向舍入。
• 负向舍入：朝 $-\infty$ 方向舍入。
• 朝零舍入：朝 $0$ 方向舍入。

指令系统

指令格式设计

对应笔记

一条指令必须显式或隐式包含的信息：

• 操作码：指定操作类型，如加、减、乘、除、传送等
• 源操作数或其地址：一个或多个源操作数所在的地址，如主（虚）存地址、寄存器编号、I/O 端口、指令给出
• 结果的地址：产生的结果存放何处（目的操作数），如存储单元地址、寄存器编号、I/O 端口
• 下条指令地址：下条指令存放何处，通常隐含在程序计数器 PC 中，当改变顺序时由指令给出

指令格式的选择应遵循的几条基本原则

• 应尽量短
• 要有足够的操作码位数
• 指令编码必须有唯一的解释，否则是不合法的序列
• 指令字长应是字节的整数倍
• 合理地选择地址字段的个数
• 指令尽量规整

操作数类型

对应笔记

操作数是指令处理的对象，基本类型有：

• 指针或地址：被看成无符号整数，用来参加运算以确定主（虚）存地址
• 数值数据：
  • 定点数（整数）：一般用二进制补码表示
  • 浮点数（实数）：大多数机器采用 IEEE 754 标准
  • 十进制数：用 NBCD 码（8421 码）表示
• 位、位串、字符和字符串：
  • 位和位串：标志、控制和状态等信息
  • 字符和字符串：表示文本等

例子如下：

寻址方式

对应笔记

寻址方式是指令或操作数地址的指定方式。即：根据地址找到指令或操作数的方法。

指令的寻址比较简单，正常情况下通过 PC 增值的方式来确定下一条指令的地址。对于跳转指令，跟操作数寻址方式相同。操作数的寻址比较复杂，通常寻址方式也特指「操作数的寻址」。

设

• A：地址字段值
• R 寄存器编号
• EA：有效地址
• (X)：X 中的内容

方式	算法	优点	缺点
立即	操作数 = A	指令执行速度快	操作数幅值有限
直接	EA = A	有效地址计算简单	地址范围有限
间接	EA = (A)	有效地址范围大	多次存储器访问
寄存器	操作数 = (R)	指令执行快，指令短	地址范围有限
寄存器间接	EA = (R)	地址范围大	额外存储器访问
偏移	EA = A + (R)	灵活	复杂
堆栈	EA = 栈顶	指令短	应用有限

偏移方式：将直接方式和寄存器间接方式结合起来，有相对/基址/变址三种。

EA = A + (R) 中，R 可以明显给出，也可以隐含给出；R 可以为 PC、基址寄存器 B 或变址寄存器 I。

• 相对寻址（EA = A + (PC)）：相对于当前指令处偏移量为 A 的单元
  • 指令地址码给出一个偏移量（带符号数），基准地址隐含由 PC 给出
  • 可用来实现程序（公共子程序）的浮动或指定转移目标地址
  • 注意：当前 PC 的值可以是正在执行指令的地址或下条指令的地址
• 基址寻址（EA = A + (B)）：相对于基址 (B) 处偏移量为 A 的单元
  • 指令地址码给出一个偏移量，基准地址明显或隐含由基址寄存器 B 给出
  • 可用来实现多道程序重定位或过程调用中参数的访问
• 变址寻址（EA = A + (I)）：相对于基址 A 处偏移量为 (I) 的单元
  • 指令地址码给出一个基准地址，而偏移量（无符号数）明显或隐含由变址寄存器 I 给出
  • 可为循环重复操作提供一种高效机制，如实现对线性表的方便操作
  • 自动变址：指令中的地址码 A 给定数组首址，变址器 I 每次加/减数组元素的长度 x
    • 一般 RISC 机器不提供自动变址寻址，并将变址和基址寻址统一成一种偏移寻址方式

操作类型

对应笔记

• 算术和逻辑运算指令：加、减、乘、除、比较、与、或、取反等
• 移位指令：算术移位、逻辑移位、循环移位、半字交换等
• 传送指令：传送、读取、写等
• 串指令：串传送、串比较、检索、传送转换等
• 顺序控制指令：条件转移、无条件转移、跳步、调用、返回等
• CPU 控制指令：停机、开中断、关中断、系统模式切换等
• 输入输出指令：CPU 与外部设备交换数据或传输控制命令及状态信息

操作码编码

对应笔记

操作码编码方式

• 定长操作码编码
• 扩展操作码编码

编码长度

• 代码长度更重要时：采用变长指令字、变长操作码
• 性能更重要时：采用定长指令字、定长操作码

变长指令字和变长操作码使机器代码更紧凑；定长指令字、定长操作码便于快速访问和译码。

指令长度是否可变与操作码长度是否可变没有绝对关系，但通常是 ：「定长操作码不一定是定长指令字」、「变长操作码一般是变长指令字」。

• 定长操作码编码：指令的操作码部分采用固定长度的编码
  • 如：假设操作码固定为 6 位，则系统最多可表示 64 种指令
• 扩展（变长）操作码编码
  • 基本思想：将操作码的编码长度分成几种固定长的格式。被大多数指令集采用。

设某指令系统指令字是 16 位，每个地址码为 6 位。若二地址指令 15 条，一地址指令 34 条，则剩下零地址指令最多有多少条？

解答

操作码按短到长进行扩展编码。

首先是二地址指令，需要 4 位进行描述，可以设为从 (0000 ~ 1110)。

然后是一地址指令。上面已经占用了 (0000 ~ 1110)，因此一地址必须是 (1111)，再加上有 34 条，需要 6 位进行描述，可以划分为以下两种：

• 11110 (00000 ~ 11111)，共 32 条
• 11111 (00000 ~ 00001)，共 2 条

最后是零地址指令，剩下的就是 (00010 ~ 11111)，这一共有 30 种，此外这一共也才占用了 10 位，还剩下六位，因此答案就是 $30 \times 2^6 = 15 \times 2^7$ 条。

异常的中断的区别

对应笔记

• 异常（exception）：指处理器在执行某条指令时发生在 CPU 内部的事件。
  • 如整除 0、溢出、断点设置、单步跟踪、访问超时、非法操作码、栈溢出、缺页、保护错等。
• 中断（interrupt）：程序执行过程中，若外设完成任务或发生某些特殊事件，会向 CPU 发中断请求，要求 CPU 对这些情况进行处理。
  • 如打印机缺纸、定时采样计数时间到、键盘缓冲满。
  • 通常，每条指令执行完后，CPU 都会主动去查询有没有中断请求，有的话，则将下条指令地址作为返回地址（断点）保存，然后转到相应的中断服务程序执行，结束后回到断点继续执行。
  • 中断事件与执行的指令无关，由 CPU 外部的 I/O 部件发出，因此，称为 I/O 中断或外部中断，需要通过专门的中断请求线向 CPU 请求。

异常分类：

• 故障（fault）：执行某条指令时发生的异常事件，如溢出、缺页、越界、越权、越级、非法指令、除数为 0、堆/栈溢出、访问超时等。
• 自陷（trap）：执行预先设置的指令，如断点、单步、系统调用等。
• 终止（abort）：指令执行过程中出现了硬件故障，如访存校验错等。

MIPS 指令格式和寻址方式

对应笔记

MIPS 三种指令格式：

• R-Type
  • 两个操作数和结果都在寄存器的运算指令
• I-Type
  • 运算指令：一个寄存器、一个立即数
  • Load 和 Store 指令
  • 条件分支指令
• J-Type
  • 无条件跳转指令

• OP（Operation）：操作码
  • R-Type 为 0 (000 000)
  • J-Type 为 2 (000 010) 或 3 (000 011)
  • I-Type 为其他
• rs（Register Source）：第一个源操作数寄存器
• rt（Register Target）：第二个源操作数寄存器
• rd（Register Destination）：结果寄存器
• shamt（Shift Amount）：移位量
• func（Function Code）：功能码
  • R-Type 指令中 OP 字段是特定的值，具体操作由 func 字段给定。
• immediate：立即数或 Load/Store 指令和分支指令的偏移地址
• target address：无条件转移地址的低 26 位。将 PC 高 4 位拼上 26 位直接地址，最后添 2 个 0 就是 32 位目标地址

寻址方式：

• R-型指令的寻址方式只有一种，就是「寄存器寻址」。
  • 操作数 = (R)
• I-型指令的寻址方式有 4 种，就是「寄存器寻址」、「立即数寻址」、「相对寻址」、「基址或变址寻址」。
  • 寄存器：操作数 = (R)
  • 立即数：操作数 = A
  • 相对：EA = A + (PC)
  • 基址或变址：EA = A + (B)/EA = A + (I)
• J-型指令的寻址方式只有一种，就是「直接寻址」。
  • EA = A

选择结构的汇编指令表示

例子：

if (i == j) {
    f = g + h;
} else {
    f = g - h;
}

假设：

• i：$s3
• j：$s4
• g：$s5
• h：$s6
• f：$s7

      bne $s3, $s4, else
      add $s7, $s5, $s6
      j   end
else: sub $s7, $s5, $s6
end:

循环结构的汇编指令表示

例子：

for (; i != h; i + j) {
    g += A[i];
}

假设：

• A 是 int 数组（sizeof(int) = 4），首地址为 $s0
• i：$s3
• j：$s4
• h：$s5
• g：$s6

loop: sll $t0, $s3, 2    # $t0 = i * 4
      add $t0, $t0, $s0
      lw  $t1, 0($t0)
      add $s6, $s6, $t1
      add $s3, $s3, $s4
      bne $s3, $s5, loop

过程调用的指令、执行步骤、栈和栈帧的变化

对应笔记

过程调用的执行步骤（假设过程 P 调用过程 Q）：

• 调用过程 P 中完成
  1. 将参数放到 Q 能访问到的地方
  2. 将 P 中的返回地址存到特定的地方，将控制转移到过程 Q
• 被调用过程 Q 中完成
  1. 为 Q 的局部变量分配空间（局部变量临时保存在栈中）
  2. 执行过程 Q
  3. 将 Q 执行的返回结果放到 P 能访问到的地方
  4. 取出返回地址，将控制转移到 P，即返回到 P 中执行

MIPS 过程调用指令：

• jr（jump register）：无条件跳转到寄存器中的地址（对应于过程返回）
• jal（jump and link）：跳转到目标地址，并将下一条指令地址存入寄存器 ra（对应于过程或函数调用）
• j：无条件跳转到目标地址

MIPS 寄存器使用约定：

• 保存寄存器 $s0 ~ $s7 的值在从被调用过程返回后还要被用，被调用者需要保留
• 临时寄存器 $t0 ~ $t9 的值在从被调用过程返回后不需要被用（需要的话，由调用者保存） ，被调用者可以随意使用
• 参数寄存器 $a0 ~ $a3 在从被调用过程返回后不需要被用（需要的话，由调用者保存在栈帧或其他寄存器中），被调用者可以随意使用
• 全局指针寄存器 $gp 的值不变
• 帧指针寄存器 $fp 用栈指针寄存器 $sp - 4来初始化

需在被调用过程 Q 中入栈保存的寄存器（被调用者保存）

• 返回地址 $ra
• 保存寄存器 $s0 ~ $s7
• 所有局部数组和结构等复杂类型变量

若局部变量和临时变量发生了寄存器溢出（寄存器不够分配），则也要入栈。

MIPS 中栈的实现：

• 用栈指针寄存器 $sp 来指示栈顶元素
• 每个元素的长度为 32 位，即：一个字（4 个字节）
• 「入栈」和「出栈」操作用 sw/lw 指令来实现，需用 add/sub 指令调整 $sp 的值。
• 栈生长方向：从高到低地址「增长」，而取数/存数的方向是从低到高地址（大端方式）
  • 每入栈 1 字：$sp - 4 -> $sp
  • 每出栈 1 字：$sp + 4 -> $sp

x86 栈帧例子如上：

各过程有自己的栈区，称为栈帧（stack frame），即过程的帧（procedure frame）。

栈由若干栈帧组成。

• 用专门的帧指针寄存器指定起始位置
• 当前栈帧范围在帧指针和栈指针之间
• 程序执行时，栈指针可移动，帧指针不变。所以过程内对栈信息的访问可通过帧指针进行
• 复杂局部变量一定分配在栈帧中

过程调用时 MIPS 栈和栈帧的变化如下：

过程调用举例

中央处理器

CPU 执行指令过程

对应笔记

通常，CPU 执行一条指令的大致过程如下。

1. 取指令：从 PC 指出的内存单元中取出指令送到指令寄存器（IR）。
2. 对 IR 中的指令操作码译码并计算下条指令地址：不同指令的功能不同，即指令涉及的操作过程不同，因而需要不同的操作控制信号。
3. 计算源操作数地址并取源操作数：根据寻址方式确定源操作数地址计算方式，若源操作数是存储器数据，则需要一次或多次访存。
   • 例如，对于间接寻址或两个操作数都在存储器的指令，需要多次访存；若源操作数是寄存器数据，则直接从寄存器取数，无须访存。
4. 对操作数进行相应的运算：在 ALU 或加法器等运算部件中对取出的操作数进行运算。
5. 目的操作数地址计算并存结果：根据寻址方式确定目的操作数的地址计算方式，将运算结果存入存储单元中，或存入通用寄存器中。

对于上述过程的第 1 步和第 2 步，所有指令的操作都一样，都是取指令、指令译码并修改 PC。

而对于第 3 ~ 5 步，不同指令的操作可能不同，它们完全由第 2 步译码得到的控制信号控制，即每条指令的功能由第 2 步译码得到的控制信号决定。

RTL(Register Transfer Language) 规定

• R[r]：通用寄存器 r 的内容
• M[addr]：存储单元 addr 的内容
• M[R[r]]：寄存器 r 的内容所指存储单元的内容
• PC：PC 的内容
• M[PC]：PC 所指存储单元的内容
• SEXT(imm)：对立即数 imm 进行符号扩展
• ZEXT(imm)：对立即数 imm 进行零扩展
• 传送方向用 <- 表示，即传送源在右，传送目的在左

CPU 的基本组成

对应笔记

CPU 的基本组成包括：

• 数据通路：指令执行过程中，数据所经过的路径，包括路径中的部件。它是指令的执行部件。
  • 数据通路中专门进行数据运算的部件称为执行部件。
  • 数据通路就是由「操作元件」和「状态元件」通过总线或分散方式连接而成的进行数据存储、处理和传送的路径。
• 控制器：对指令进行译码，生成指令对应的控制信号，控制数据通路的动作。能对执行部件发出控制信号，是指令的控制部件。

操作元件和状态元件的区别

数据通路中专门进行数据运算的部件称为执行部件：

• 组合逻辑元件（操作元件）：
  • 输出只取决于当前的输入
  • 定时：所有输入到达后，经过一定的逻辑门延时，输出端改变，并保持到下次改变，不需要时钟信号来定时
• 时序逻辑元件（状态元件、存储元件）：
  • 具有存储功能，在时钟控制下输入被写到电路中，直到下个时钟到达
  • 输入端状态由时钟决定何时被写入，输出端状态随时可以读出

指令周期、时钟周期

对应笔记

指令周期是取并执行一条指令的时间。每条指令的指令周期未必一样。

整个数据通路中的定时信号就是时钟信号，一个时钟周期就是一个节拍。

MIPS 指令格式

MIPS 指令格式，典型的 MIPS 指令以及功能描述（书本 134-135 页）。

典型的 MIPS 指令数据通路

能够理解单周期数据通路设计，画出局部数据通路，明确控制信号取值。

这个部分还是去看原笔记「单周期数据通路」（或 PPT）比较合适。

多周期数据通路设计

能够理解多周期数据通路设计，明确控制信号取值、指令执行状态转换图。

对应笔记

取指周期开始时：

取指周期结束时：

取指周期（第一个周期）：

寄存器取/指令译码周期（第二个周期）：

Branch

指令译码输出为 beq：

Branch 指令执行并完成周期（第三个周期）：

R-Type

指令译码输出为 R-Type：

R-type 指令执行周期（第三个周期）：

R-type 完成周期（第四个周期）：

I-Type

指令译码输出为 ori：

ori 指令执行周期（第三个周期）：

ori 完成周期（第四个周期）：

访存指令

指令译码输出为访存指令（lw/sw）：

lw/sw 内存地址计算周期（第三个周期）：

sw 指令存数周期（第四个周期）：

lw 指令取数周期（第四个周期）：

lw 指令回写周期（第五个周期）：

完成前述 6 条指令的完整多周期数据通路：

状态转换图：

微程序控制器的基本思想、基本结构、执行、编码方式

对应笔记

微程序控制器的基本思想：

• 仿照程序设计的方法，编制每个指令对应的微程序
• 每个微程序由若干条微指令构成，各微指令包含若干条微命令
  • 一条微指令相当于一个状态，一个微命令就是状态中的控制信号
• 所有指令对应的微程序放在只读存储器中，执行某条指令时，取出对应微程序中的各条微指令，对微指令译码产生对应的微命令，这个微命令就是控制信号。这个只读存储器称为控制存储器（Control Storage），简称控存 CS 。

微程序控制器的基本结构：

• 输入：指令、条件码
• 输出：控制信号（微命令）
• 核心：控存 CS
• $\mu$PC：指出将要执行的微命令在 CS 中的位置
• $\mu$IR：正在执行的微命令

每个时钟执行一条微指令。微程序第一条微指令地址由起始地址发生器产生。

顺序执行时，$\mu$PC 每次加 1；转移执行时，由转移控制字段指出对哪些条件码进行测试，转移地址发生器根据条件码修改 $\mu$PC 的值。

微指令格式：

编码方式：

• 不译法（直接控制法）：一位对应一个微命令（控制信号），不需译码。
• 字段直接编码（译）法：
  • 将微指令分成若干字段，每个字段对包含的若干微命令编码
  • 把互斥微命令组合在同一字段，相容微命令组合在不同字段
    • 相容微操作：能同时进行的微操作，称为相容的。
    • 互斥微操作：不能同时进行的微操作，称为互斥的。
      • 如 ALU 运算、存储器操作等。
  • 一条微指令中最多可同时发出的微命令个数就是字段数
• 字段间接编码（译）法
• 最小编码（译）法

其中前三个适用于「水平型」微指令风格（相容微命令尽量多地安排在一条微指令中），最后一个适用于「垂直型」微指令风格（一条微指令只控制一、二个微命令）。

带异常处理的数据通路、有限状态机

对应笔记

异常和中断处理大致过程如下：

1. 当 CPU 在执行当前程序或任务（即用户进程）的第 $i$ 条指令时，若检测到一个异常事件，或在执行第 $i$ 条指令后发现有一个中断请求信号，则 CPU 会中断当前程序的执行，跳转到操作系统中相应的异常/中断处理程序去执行。
2. 若异常/中断处理程序能够解决相应问题，则在异常/中断处理程序的最后，CPU 通过执行「异常/中断返回指令」回到被打断的用户进程的第 $i$ 条指令或第 $i+1$ 条指令继续执行；
3. 若异常/中断处理程序发现是不可恢复的致命错误，则终止用户进程。通常情况下，对于异常和中断事件的具体处理过程全部由操作系统软件来完成。

一旦 CPU 检测到有异常事件或中断请求，就会进入异常/中断响应过程。在此过程中，CPU 完成以下两个任务：

1. 保护断点和程序状态；
2. 识别异常/中断类型并转相应处理程序执行。

数据通路中需增加以下两个寄存器：

• EPC：32 位，用于存放断点（异常处理后返回到的指令的地址）。
  • 写入 EPC 的断点可能是正在执行的指令的地址（故障时），需要把 PC 的值减 4 后送到 EPC
  • 写入 EPC 的断点也可能是下条指令的地址（自陷和中断时），直接送 PC 到 EPC
• Cause：32 位（有些位还没有用到），记录异常原因。
  • 假定处理的异常类型有以下两种：
    • 未定义指令：Cause=0
    • 溢出：Cause=1

需要加入两个寄存器的「写使能」控制信号：

• EPCWr：在保存断点时该信号有效，使断点 PC 写入 EPC。
• CauseWr：在处理器发现异常（如：非法指令、溢出）时，该信号有效，使异常类型被写到 Cause 寄存器。

需要一个控制信号 IntCause 来选择正确的值写入到 Cause 中。

需要将异常查询程序的入口地址（MIPS 为 0x8000 0180）写入 PC，可以在原来 PCSource 控制的多路复用器中再增加一路，其输入为 0x8000 0180。

带异常处理的有限状态机：

指令流水线

指令流水线流水段组成及各流水段的功能

对应笔记

一条指令流水线由如下 5 个流水段组成：

• 取指令（IF）：从存储器取指令；
• 指令译码（ID）：产生指令执行所需的控制信号；
• 取操作数（OF）：读取操作数；
• 执行（EX）：对操作数完成指定操作；
• 写回（WB）：将结果写回。

注意，上面的流水段按书上的说法只是一个例子，跟后面实际出现的「取指」（IF）、「取数/译码」（Reg/Dec, ID）、「执行」（EX）、「访存」（MEM）、「写回」（WB）并不一样。

但由于这部分内容我已经完成了，而且「功能」部分比较简短容易记忆，加上我问了老师写哪个都行，这部分依旧原样保留。但需要注意的是后面部分用的流水段并不是上面这个。

每个流水段寄存器中保存的信息包括两类：

1. 后面阶段需要用到的所有数据信息，它们是前面阶段在数据通路中执行的结果；
   • 包括 PC + 4、指令、立即数、目的寄存器、转移目标地址、ALU 运算结果、标志信息等。
2. 前面传递过来的后面各阶段要用到的所有控制信号。

典型 MIPS 指令的功能段划分、流水线数据通路的设计、控制信号的取值

能够理解流水段寄存器，理解流水线数据通路，但不要求自己画出数据通路。

这个部分看原笔记「指令功能段划分」比较合适。

结构冒险现象及其解决方法

对应笔记

结构冒险（Structural Hazards）：硬件资源冲突

• 现象：同一个部件同时被不同指令所使用。
• 解决方法：
  1. 一个部件每条指令只能使用 1 次，且只能在特定周期使用
  2. 设置多个部件，以避免冲突。如指令存储器 IM 和数据存储器 DM 分开

为了避免结构冒险，规定流水线数据通路中功能部件的设置原则为：

• 每个部件在特定的阶段被用（如：ALU 总在第三阶段被用）
• 将指令存储器（Im）和数据存储器（Dm）分开
• 将寄存器读口和写口独立开来

数据冒险现象及其解决方法

需要深入理解转发技术、load-use 数据冒险的检测和处理方法。

对应笔记

数据冒险（Data hazards）：数据冲突

• 现象：后面指令用到前面指令结果数据时，前面指令的结果还没产生。
• 解决方法：
  1. 采用转发（Forwarding/Bypassing）技术
  2. Load-use 冒险需要一次阻塞（stall）
  3. 编译程序优化指令顺序

仅考虑 RAW（写后读）数据冒险。

上面的解决方法忽略掉了原笔记中几条不太好的解决方法，下面是全部：

1. 硬件阻塞（stall）
2. 软件插入 NOP 指令
3. 合理实现寄存器堆的读/写操作（但不能解决所有的数据冒险）
   • 前半时钟周期写，后半时钟周期读，若同一个时钟内前面指令写入的数据正好是后面指令所读数据，则不会发生数据冒险。
4. 转发（Forwarding 或 Bypassing 旁路）技术
   • 若相关数据是 ALU 结果，可通过转发解决
   • 若相关数据是上条指令 DM 读出内容，不能通过转发解决，随后指令需被阻塞一个时钟或加 NOP 指令 （称为 Load-use 数据冒险）
5. 编译优化：调整指令顺序（不能解决所有数据冒险）

详细内容可以看原笔记「数据冒险」部分。

转发技术

详细内容可以看原笔记「转发技术」部分或 PPT。

load-use 数据冒险的检测和处理方法

详细内容可以看原笔记「转发技术」部分或 PPT。

控制冒险现象及其解决方法

对应笔记

控制冒险（Control hazards）：指令执行顺序改变

• 现象：转移或异常改变执行流程，后继指令在目标地址产生前已被取出。
• 解决方法：
  1. 采用静态或动态分支预测
  2. 编译程序优化指令顺序（分支延迟）

静态预测

对应笔记

总是预测条件不满足，即：继续执行分支指令的后续指令。可加启发式规则：在特定情况下总是预测满足，其他情况总是预测不满足。

可以将 「转移地址计算」和「分支条件判断」操作调整到 ID 阶段来缩短延迟。

预测错误的检测和处理（称为「冲刷、冲洗」Flush）

• 当 Branch=1 并且 Zero=1 时
• 增加控制信号：IF.Flush=Branch and Zero，取值为 1 时，说明预测失败
• 预测失败（条件满足）时，完成以下两件事（延迟损失时间片 C=1 时）：
  • 将转移目标地址 -> PC
  • 清除 IF 段中取出的指令，即：将 IF/ID 中的指令字清 0，转变为 NOP 指令

动态预测

对应笔记

一位预测状态图：

二位预测状态图：

基本思想：只有两次预测错误才改变预测状态。

延迟分支

基本思想：把分支指令前面的与分支指令无关的指令调到分支指令后面执行，以填充延迟时间片，不够时用 NOP 填充。

异常和中断引起的控制冒险、处理方法

对应笔记

异常和中断会改变程序的执行流程：

• 某条指令发现异常时，后面多条指令已被取到流水线中正在执行
  • 例如 ALU 指令发现「溢出」时，已经到 EX 阶段结束了，此时，它后面已有两条指令进入流水线了。

流水线数据通路处理异常思路：假设指令 add r1, r2, r3 产生了溢出，MIPS 异常处理程序首地址为 0x8000 0180。

• 清除 add 指令以及后面的所有已在流水线中的指令
• 关中断（将中断允许触发器清 0）
• 保存 PC 或 PC - 4（断点） 到 EPC
• 0x8000 0180 送 PC

根据异常发生的流水段可确定是哪条指令，因为各类异常发生的流水段不同

• 「溢出」在 EXE 段检出
• 「无效指令」在 ID 段检出
• 「除数为 0」在 ID 段检出
• 「无效指令地址」在 IF 段检出
• 「无效数据地址」在 load/store 指令的 EXE 段检出

存储器层次结构

存储器的分类

对应笔记

按工作性质/存取方式分类：

• 随机存取存储器 Random Access Memory (RAM)
  • 按地址访问，每个单元读写时间一样，且与各单元所在位置无关。如：内存。
  • 原意主要强调地址译码时间相同。现在的 DRAM 芯片采用行缓冲，因而可能因为位置不同而使访问时间有所差别。
• 顺序存取存储器 Sequential Access Memory (SAM)
  • 数据按顺序从存储载体的始端读出或写入，因而存取时间的长短与信息所在位置有关。例如：磁带。
• 直接存取存储器 Direct Access Memory (DAM)
  • 直接定位到读写数据块，在读写数据块时按顺序进行。如磁盘。
• 相联存储器 Associate Memory (AM)，Content Addressed Memory (CAM)
  • 按内容检索到存储位置进行读写。例如：快表。

按存储介质分类：

• 半导体存储器：双极型，静态 MOS 型，动态 MOS 型
• 磁表面存储器：磁盘（Disk）、磁带 （Tape）
• 光存储器：CD，CD-ROM，DVD

按信息的可更改性分类：

• 读写存储器（Read/Write Memory)：可读可写
• 只读存储器（Read Only Memory)：只能读不能写

按断电后信息的可保存性分类：

• 非易失（不挥发）性存储器（Nonvolatile Memory）
  • 信息可一直保留， 不需电源维持。
  • 如 ：ROM、磁表面存储器、光存储器等
• 易失（挥发）性存储器（Volatile Memory）
  • 电源关闭时信息自动丢失。（如：RAM、Cache 等）

按功能/容量/速度/所在位置分类：

• 寄存器（Register）
  • 封装在 CPU 内，用于存放当前正在执行的指令和使用的数据
  • 用触发器实现，速度快，容量小（几 ~ 几十个）
• 高速缓存（Cache）
  • 位于 CPU 内部或附近，用来存放当前要执行的局部程序段和数据
  • 用 SRAM 实现，速度可与 CPU 匹配，容量小（几 MB）
• 主存储器 MM（Main (Primary) Memory）
  • 位于 CPU 之外，用来存放已被启动的程序及所用的数据
  • 用 DRAM 实现，速度较快，容量较大（几 GB）
• 外存储器 AM （辅助存储器 Auxiliary/Secondary Storage）
  • 位于主机之外，用来存放暂不运行的程序、数据或存档文件
  • 用磁表面或光存储器实现，容量大而速度慢

主存储器的组成和基本操作

• 记忆单元/存储基元/存储元/位元（Cell）
  • 具有两种稳态的能够表示二进制数码 0 和 1 的物理器件
• 存储单元/编址单位（Addressing Unit）
  • 具有相同地址的位构成一个存储单元，也称为一个编址单位
• 存储体/存储矩阵/存储阵列（Bank）
  • 所有存储单元构成一个存储阵列
• 编址方式（Addressing Mode）
  • 按字节编址、按字编址
• 存储器地址寄存器（Memory Address Register, MAR）
  • 用于存放主存单元地址的寄存器
• 存储器数据寄存器（Memory Data Register, MDR/MBR）
  • 用于存放主存单元中的数据的寄存器

指令执行过程中需要访问主存时，CPU 首先把被访问单元的地址送到主存地址寄存器（MAR）中，然后通过地址线将主存地址送到主存中的地址寄存器，以便地址译码器进行译码，选中相应单元，同时，CPU 将读/写信号通过控制线送到主存的读写控制电路。

1. 如果是写操作，CPU 同时将要写的信息送主存数据寄存器（MDR）中，在读写控制电路的控制下，经数据线将信息写入选中的单元；
2. 如果是读操作，则主存读出选中单元的内容送数据线，然后被送到 MDR 中。

数据线的宽度与 MDR 的宽度相同，地址线的宽度与 MAR 的宽度相同

存储器的层次化结构

为了缩小存储器和处理器两者之间在性能方面的差距，通常在计算机内部采用层次化的存储器体系结构：

• 速度越快，容量越小，越靠近 CPU。
• CPU 可以直接访问内部存储器；而外部存储器信息要先被取到主存，再被 CPU 访问。
• 数据一般只在相邻层之间复制传输，而且总是从慢速存储器复制到快速存储器。

SRAM 和 DRAM 的区别

对应笔记

• 静态存储元件（SRAM）：
  • MOS 管多，功耗大，集成度低；
  • 可保持记忆状态，无须刷新；
  • 读写速度快；
  • 价格昂贵。
• 动态存储元件（DRAM）：
  • MOS 管少，功耗小，集成度高；
  • 必须定时刷新；
  • 读写速度慢；
  • 价格较低。

存储器芯片的扩展

对应笔记

扩展方式：

• 字扩展（位数不变、扩充容量）
  • 用 16K $\times$ 8 位芯片扩成 64K $\times$ 8 位存储器需几个芯片？地址范围各为什么？
    • 字方向扩展 4 倍，即 4 个芯片。0000-3FFFH, 4000-7FFFH, 8000-BFFFH, C000-FFFFH，地址共 16 位，高两位由外部译码器译码生成 4 个输出，分别连到 4 个片选信号，片内地址有 14 位
  • 地址线、读/写控制线等对应相接，片选信号连译码输出
• 位扩展（字数不变，位数扩展）
  • 用 4096 $\times$ 1 位芯片构成 4K $\times$ 8 位存储器需几个芯片？地址范围各是多少？
    • 位方向扩展 8 倍，字方向无需扩展。即 8 个芯片，地址范围都一样：000-FFFH，地址共 12 位，全部作为片内地址
  • 芯片的地址线及读/写控制线对应相接，而数据线单独引出
• 字位同时扩展（字和位同时扩展）
  • 用 16K $\times$ 4 位芯片构成 64K $\times$ 8 位存储器需几个芯片，地址范围各是多少？
    • 字向 4 倍、位向 2 倍，8 个芯片。0000-3FFFH, 4000-7FFFH, 8000-BFFFH, C000-FFFFH
  • 地址线、读/写控制线等对应相接，片选信号则分别与外部译码器各个译码输出端相连

连续编址方式、交叉编址方式

对应笔记

连续编址方式：

在连续编址的多模块主存储器中，主存地址的高位表示模块号（体号），低位表示模块内地址（体内地址），地址在模块内连续。

对于连续编址的多模块主存储器，当访问一个连续主存块时，总是先在一个模块内访问，等到该模块全部单元访问完才转到下一个模块访问，因而这种情况下不能提高存储器的吞吐率。

交叉编址方式：

在交叉编址的多模块存储器中，主存地址的低位表示模块号，高位表示模块内地址。

交叉编址方式下，总是把高位的体内地址送到由低位体号所确定的模块内进行译码。

磁盘读写的三个步骤

对应笔记

1. 寻道：磁盘控制器把磁盘地址送到磁盘驱动器的磁盘地址寄存器后，便产生寻道命令，以启动磁头定位伺服系统根据柱面号移动磁头到指定的柱面（磁道），并选择指定的磁头准备进行读写。此操作完成后，发出寻道结束信号给磁盘控制器，并转入旋转等待操作。
2. 旋转等待：盘片旋转开始时，首先将扇区计数器清零，以后每来一个扇区标志脉冲，扇区计数器加 1，把计数内容与磁盘地址寄存器中的扇区号进行比较，如果一致，则输出扇区符合信号，说明要读写的信息已经转到磁头下方。
3. 读写：扇区符合信号送给磁盘控制器后，磁盘控制器的读写控制电路开始动作。如果是写操作，就将数据送到写入电路，写入电路根据记录方式生成相应的写电流脉冲；如果是读操作，则由读出放大电路读出内容送磁盘控制器。

磁盘存储器的性能指标

对应笔记

记录密度

提高盘片上的信息记录密度：

• 增加磁道数目：提高磁道密度
• 增加扇区数目：提高位密度，并采用可变扇区数

存储容量

存储容量指整个存储器所能存放的二进制信息量，它与磁表面大小和记录密度密切相关。

磁盘的未格式化容量是指按道密度和位密度计算出来的容量，它包括了可利用的所有磁化单元的总数，未格式化容量（或非格式化容量）比格式化后的实际容量要大。格式化后的实际容量只包含数据区。

低密度存储方式，容量：

• 未格式化：$\text{磁盘总容量} = \text{记录面数} \times \text{理论柱面数} \times \text{内圆周长} \times \text{最内道位密度}$
• 格式化（记录面数约为盘片数的两倍）：$\text{磁盘实际数据容量} = 2 \times \text{盘片数} \times \text{磁道数/面} \times \text{扇区数/磁道} \times 512 \text{B/扇区}$。
  • 早期扇区大小为 512 字节，现在为 4096 字节，即 4K 扇区。

数据传输速率

数据传输速率：单位时间内从存储介质上读出或写入的二进制信息量。

平均存取时间

平均存取时间为 $T = \text{平均寻道时间} + \text{平均旋转等待时间} + \text{数据传输时间}$：

• 平均寻道时间：磁头寻找到指定磁道所需平均时间（大约 5ms）
• 平均旋转等待时间：指定扇区旋转到磁头下方所需平均时间，取磁盘旋转一周所需时间的一半（大约 4~6ms）（转速：4200/5400/7200/10000rpm）
• 数据传输时间：（大约 0.01ms/扇区）

数据校验的基本原理

对应笔记

大多采用「冗余校验」思想，即除原数据信息外，还增加若干位编码，这些新增的代码被称为校验位。

比较结果：

1. 没有检测到错误，得到的数据位直接传送出去。
2. 检测到差错，并可以纠错。数据位和比较结果一起送入纠错器，将正确数据位传送出去。
3. 检测到错误，但无法确认哪位出错，因而不能进行纠错处理，此时，报告出错情况。

由若干位代码组成的一个字叫码字。 两个码字中具有不同代码的位的个数叫这两个码字间的「距离」。码制中各码字间最小距离为码距，它就是这个码制的距离。

码距与检错、纠错能力的关系：

• 若能检测 $e$ 位错误，则码距 $d$ 至少为 $e+1$；
• 若能纠正 $t$ 位错误，则码距 $d$ 至少为 $2t+1$。
• 若能同时检测 $e$ 位错误和纠正 $t$ 位错误，则码距 $d$ 至少为 $e+t+1$。

奇偶校验码

对应笔记

基本思想：增加一位奇（偶）校验位并一起存储或传送，根据终部件得到的相应数据和校验位，再求出新校验位，最后根据新校验位确定是否发生了错误。

实现原理（假设数据 $B = b_{n-1}\dots b_0$ 从源部件传送至终部件，在终部件接受到的数据为 $B' = b_{n-1}'\dots b_0'$）：

1. 在源部件求出奇（偶）校验位 $P$
   • 奇校验：$P = b_{n-1} \oplus \dots \oplus b_0 \oplus 1$
   • 偶校验：$P = b_{n-1} \oplus \dots \oplus b_0$
2. 在终部件求出奇（偶）校验位 $P'$
   • 奇校验：$P' = b_{n-1}' \oplus \dots \oplus b_0' \oplus 1$
   • 偶校验：$P' = b_{n-1}' \oplus \dots \oplus b_0'$
3. 计算最终校验位 $P^{*} = P \oplus P'$
   • 若 $P^{*} = 1$，则终部件接受的数据有奇数位错；
   • 若 $P^{*} = 0$，则终部件接受的数据正确或有偶数位错。

奇偶校验码的码距为 2，只能检测 1 位错误，不能纠正错误。

开销小，适用于校验一字节长的代码，故常被用于存储器读写检查或按字节传输过程中的数据校验。因为一字节长的代码发生错误时，1 位出错的概率较大，两位以上出错则很少，所以可用奇偶校验。

循环冗余校验码

对应笔记

循环冗余校验码（CRC, Cyclic Redundancy Check）具有很强的检错、纠错能力，用于大批量数据存储和传送中的数据校验。

基本思想：

• 数据信息 $M(x)$ 是一个 $n$ 位的二进制数据。将其左移 $k$ 位后，用一个约定的「生成多项式」$G(x)$ 相除，$G(x)$ 是一个 $k+1$ 位的二进制数，相除后得到的 $k$ 位余数就是校验位。校验位拼接到 $M(x)$ 后，形成一个 $n+k$ 位的代码，称该代码为 CRC 码，也称为 $(n+k, n)$ 码。
• 一个 CRC 码一定能被生成多项式整除，当数据和校验位一起送到接受端后，只要将接受到的数据和校验位用同样的生成多项式相除，如果正好除尽，表明没有发生错误；若除不尽，则表明某些数据位发生了错误。通常要求重传一次。

假设要传输的数据信息为 6 位 100011，报文多项式为 $M(x) = x^5 + x + 1$。若约定生成多项式为 $G(x) = x^3 + 1$，则校验位位数为 3，除数为 1001。

生成校验位时，用 $x^3 \cdot M(x)$ 除以 $G(x)$，即 $100011000 \div 1001$。相除时采用「模 2」运算，即异或运算。

程序访问的局部性

对应笔记

在较短时间间隔内，程序产生的地址往往集中在一个很小范围内。这种现象称为「程序访问的局部性」：

• 时间局部性：指被访问的某个存储单元在一个较短的时间间隔内很可能又被访问；
• 空间局部性：指被访问的某个存储单元的邻近单元在一个较短的时间间隔内很可能也被访问。

Cache 的基本工作原理

对应笔记

在 CPU 和主存之间设置一个快速小容量的存储器，其中总是存放最活跃（被频繁访问）的程序和数据，由于程序访问的局部性特征，大多数情况下，CPU 能直接从这个高速缓存中取得指令和数据，而不必访问主存。

这个高速缓存就是位于主存和 CPU 之间的 Cache。

主存被分成若干大小相同的块，称为主存块（Block），Cache 也被分成相同大小的块，称为 Cache 行（line）或槽（Slot）。

在系统启动或复位时，每个 cache 行都为空，其中的信息无效，只有装入了主存块后信息才有效。为了说明 cache 行中的信息是否有效，每个 cache 行需要一个有效位（valid bit）。

有了有效位，就可通过将有效位清零来淘汰某 cache 行中的主存块，称为冲刷（flush），装入一个新主存块时，再使有效位置 1。

如下图所示，V 为「有效位」，1 表示信息有效，0 表示信息无效。

• 开机或复位时，所有行的有效位为 0
• 某行被替换后使其有效位为 1
• 某行装入新块时，使其有效位为 1
• 使有效位为 0 来冲刷 Cache（如进程切换，DMA 传送时等）
• 为操作系统设置 Cache 冲刷指令

CPU 执行程序过程中，需要从主存中取指令或读数据时，先检查 cache 中有没有要访问的信息：

• 若有，就直接从 cache 中读取，而不用访问主存；
• 若没有，再从主存中把当前访问信息所在的一个主存块复制到 cache 中。

因此，cache 中的内容是主存中部分内容的副本。

命中情况：

• 命中 Hit：要访问的信息在 Cache 中
  • Hit Rate(命中率)：在 Cache 中的概率
  • Hit Time(命中时间)：在 Cache 中的访问时间（判断时间 + Cache 访问）
• 缺失 Miss：要找到信息不在 Cache 中
  • Miss Rate(缺失率)：不在 Cache 中的概率
  • Miss Penalty(缺失损失)：访问一个主存块所花时间
  • 命中时间远小于缺失损失

设 $t_{\text{avg}}$ 为平均访问时间，命中率为 $\alpha$，$t_c$ 为 Cache 访问时间，$t_m$ 为主存访问时间，则

$$t_{\text{avg}} = \alpha t_c + (1 - \alpha)(t_c + t_m) = t_c + (1 - \alpha)t_m$$

直接映射、全相联映射、组相联映射

直接映射

对应笔记

映射关系为

$$\text{Cache 行号} = \text{主存块号} \bmod \text{Cache 行数}$$

块（行）都从 0 开始编号。

假定 Cache 有 $2^c$ 行，主存有 $2^m$ 块，即以 $m$ 位主存块号中低 $c$ 位作为对应的 Cache 行号来进行 Cache 映射。即主存块号的低 $c$ 位正好是它要装入的 Cache 行号。

在 Cache 中，给每一行设置一个 $t$ 位长的标记（tag），此处 $t = m - c$，主存某块调入 Cache 后，就将其块号的高 $t$ 位设置在对应的 Cache 行的标记中。

根据上面的分析，主存地址被分为以下三个字段：

其中高 $t$ 位为标记，中间 $c$ 位为 Cache 行号（行索引），剩下的地位地址为块内地址。

特点：

• 容易实现，命中时间短
• 无需考虑淘汰（替换）问题
• 不够灵活，Cache 存储空间得不到充分利用，命中率低

计算 Cache 容量：

全相连映射

对应笔记

全相联映射的基本思想是一个主存块可装入 Cache 任意一行中。

在全相联映射 Cache 中，每行的标记用于指出该行取自主存的哪个块。

因为一个主存块可能在任意一个 Cache 行中，所以，需要比较所有 Cache 行的标记，因此，主存地址中无须 Cache 行索引，只有标记和块内地址两个字段。

全相联映射方式下，只要有空闲 Cache 行，就不会发生冲突，因而块冲突概率低。

全相联映射方式的时间开销和所用元件开销都较大，实现起来比较困难，不适合容量较大的 cache。

全相联映射的组织示意图：

组相连映射

对应笔记

将 Cache 所有行分组，把主存块映射到 Cache 固定组的任一行中，映射关系如下

$$\text{Cache 组号} = \text{主存块号} \bmod \text{Cache 组数}$$

特点：

• 结合直接映射和全相联映射的优点
• 每组 2 或 4 行（称为 2-路或 4-路组相联）较常用

组相联映射的组织示意图：

映射方法的比较

关联度：一个主存块映射到 Cache 中，可能存档的位置个数

• 直接映射：1，关联度最低
• 全相联映射：Cache 行数，关联度最高
• N-路组相联映射：N，关联度居中

Cache 大小和块大小一定时，缺失率直接映射最高，全相联映射最低；命中时间直接映射最小，全相联映射最大。

关联度越高，总的标记位数越多，额外空间开销越大：

先进先出算法、最近最少用算法

先进先出算法

对应笔记

最近最少用算法

对应笔记

最近最少用算法 LRU 是一种栈算法，命中率随组的增大而提高。

LRU 具体实现时，并不是通过移动块来实现的，而是通过给每个 cache 行设定一个计数器，通过计数值来记录这些主存块的使用情况，称为 LRU 位。

计数器变化规则：

• 每组 4 行时，计数器有 2 行，计数值越小说明越被常使用。
• 命中时，被访问行的计数器置 0，比其低的计数器加 1，其余不变。
• 未命中且该组未满时，新行计数器置为 0，其余全加 1。
• 未命中且该组已满时，计数值为 3 的那一行中的主存块被淘汰，新行计数器置为 0，其余加 1。

即计数值为 0 的行中的主存块最常被访问，计数值为 3 的行中的主存块最不常被访问，先被淘汰。

全写法、回写法的区别

对应笔记

写命中（Write Hit）：要写的单元已经在 Cache 中

• 全写法：
  • 同时写 Cache 和主存单元
  • 使用写缓存
• 回写法：
  • 只写 Cache，不写主存
  • 缺失时一次写回，每行有个修改位（脏位 dirty bit），表示该行是否被修改过
  • 大大降低主存带宽需求，控制可能很复杂

虚拟存储器的基本概念

对应笔记

虚拟存储技术实质：

• 程序员在比实际主存空间大得多的逻辑地址空间中编写程序
• 程序执行时，把当前需要的程序段和相应的数据块调入主存，其他暂不用的部分存放在磁盘上
• 指令执行时，通过硬件将逻辑地址（也称虚拟地址或虚地址）转化为物理地址（也称主存地址或实地址）
• 在发生程序或数据访问失效（缺页）时，由操作系统进行主存和磁盘之间的信息交换

CPU 通过存储器管理部件（MMU）将指令中的逻辑地址（VA）转换为主存的物理地址（PA）。

进程的虚拟地址空间划分

对应笔记

Linux 在 x86 上的虚拟地址空间

• 内核空间（Kernel）
  • 与进程相关的数据结构
  • 物理存储区
  • 内核代码和数据
• 用户空间
  • 用户栈（User Stack）
  • 共享库（Shared Libraries）
  • 堆（heap）
  • 可读写数据（Read/Write Data）
  • 只读数据（Read-only Data）
  • 代码（Code）

分页式虚拟存储器的工作原理

对应笔记

页表、地址转换、快表、CPU 访存过程

在分页式虚拟存储系统中，虚拟地址空间被划分成大小相等的页面，外存和主存之间按页面（page）为单位交换信息。

虚拟地址空间中的页称为虚拟页、逻辑页或虚页（VP）；主存空间也被划分成同样大小的页框（页帧），有时把页框也称为物理页或实页（PF/PP）。

虚拟存储管理采用「请求分页」的思想，每次访问指令或数据仅将当前需要的页面从硬盘等外存调入主存某页框中，而进程中其他不活跃的页面保留在硬盘上。

当访问某个信息所在页不在主存时发生缺页异常，此时，从外存将缺失页面装入主存。

页分类：

• 未分配页：没有和任何内容相关联的页称为「未分配页」。
  • 虚拟地址空间中有一些「空洞」的没有内容的页面。如上面的图片所示，堆区和栈区都是动态生长的，因而在栈和共享库映射区之间、堆和共享库映射区之间都可能没有内容存在。
• 已分配页：代码和数据等有内容的区域所关联的页面。
  • 缓存页：已调入主存而被缓存在 DRAM 中的页面；
  • 未缓存页：未调入主存而存在外存上的页。

因为缺页处理代价较大，所以提高命中率是关键，因此，在主存页框和虚拟页之间采用全相联映射方式。此外，当进行写操作时，由于外存访问速度很慢，所以，不能每次写操作都同时写 DRAM 和外存，因而，在处理一致性问题时，采用回写方式。

页表：建立各个「虚拟页」和所存放的「主存页框号」或磁盘上存储位置之间的关系。

进程中的每个虚拟页在页表中都有一个对应的表项，称为页表项。页表项内容包括

• 该虚拟页的存放位置：建立虚拟页和物理页框之间的映射，用于进行虚拟地址到物理地址的转换。
• 装入位（valid）：有效位。
  • 若为 1，表示该虚拟页已从外存调入主存，是一个「缓存页」。此时，存放位置字段指向主存物理页号（即页框号或实页号）。
  • 若为 0，则表示没有被调入主存，此时：
    • 若存放位置字段为 null，则说明是一个「未分配页」；
    • 否则是一个「未缓存页」，其存放位置字段给出该虚拟页在磁盘上的起始地址。
• 修改位（dirty）：说明页面是否被修改过。
• 使用位：说明页面的使用情况，配合替换策略来设置，因此也称替换控制位。
• 存取权限位：说明页面是可读可写、只读还是只可执行等，用于存储保护。
• 禁止缓存位：说明页面是否可以装入 cache，通过正确设置该位，可以保证磁盘、主存和 cache 数据的一致性。

虚拟地址分为两个字段：

• 高位字段：虚拟页号
• 低位字段：页内地址

主存物理地址也分为两个字段：

• 高位字段：物理页号
• 低位字段：页内地址

由于虚拟页和物理页（页框）大小一样，所以二者页内地址相等。

逻辑地址转换为物理地址的过程：

地址变换过程：

1. 首先根据页表基址寄存器的内容，找到主存中对应的页表起始位置（即页表基地址）；
2. 然后将虚拟地址高位字段中的虚页号作为索引，找到对应的页表项：
   • 若装入位为 1，则取出物理页号，和虚拟地址中的页内地址拼接，形成访问主存时实际的物理地址；
   • 若装入位为 0，则说明缺页，需要操作系统进行缺页处理。

把经常要查的页表项放到 Cache 中，这种在 Cache 中的页表项组成的页表称为「后备转换缓冲器」（Translation Lookaside Buffer, TLB），通常称为快表，相应地称主存中的页表为慢表。

每个表项的内容由页表项内容加上一个 TLB 标记字段组成：TLB 标记字段用来表示该表项取自页表中哪个虚拟页对应的页表项。

因此，TLB 标记字段的内容：

• 在全相联方式下就是该页表项对应的虚拟页号；
• 组相联方式下则是对应虚拟页号中的高位部分，而虚拟页号的低位部分作为 TLB 组索引用于选择 TLB 组。

一个 TLB 和 Cache 都采用组相联映射的过程：

1. CPU 给出的是一个 32 位的虚拟地址，首先，由 CPU 中的 MMU 进行虚拟地址到物理地址的转换；
2. 然后由处理 cache 的硬件根据物理地址进行存储访问.
3. MMU 对 TLB 查表时，20 位的虚拟页号被分成标记（tag）和组索引两部分：
   1. 首先由组索引确定在 TLB 的哪一组进行查找。
   2. 查找时将虚拟页号的标记部分与 TLB 中该组每个标记字段同时进行比较：
      • 若有某个相等且对应有效位 V 为 1，则 TLB 命中，此时，可直接通过 TLB 进行地址转换；
      • 否则 TLB 缺失，此时，需要访问主存去查慢表。
4. 该例是两级页表方式，虚拟页号被分成页目录索引和页表索引两部分，根据这两部分可得到对应的页表项，从而进行地址转换；
5. 并将对应页表项的内容送入 TLB 形成一个新的 TLB 表项，同时，将虚拟页号的高位部分作为 TLB 标记填入新的 TLB 表项中。
6. 若 TLB 已满，还要进行 TLB 替换（为降低替换算法开销，TLB 常采用随机替换策略）。
7. 在 MMU 完成地址转换后，cache 硬件根据映射方式将转换得到的主存物理地址划分成多个字段：
   1. 然后根据 cache 索引，找到对应的 cache 行或 cache 组；
   2. 将对应各 cache 行中的标记与物理地址中的高位地址进行比较：
      • 若相等且对应有效位为 1，则 cache 命中，此时，根据块内地址取出对应的字。需要的话，再根据字节偏移量从字中取出相应字节送 CPU。

系统互连及输入输出组织

外设的分类

对应笔记

• 按信息的传输方向来分：
  • 输入设备：键盘、鼠标、扫描仪等
  • 输出设备：打印机、显示器等
  • 输入/输出设备：磁盘驱动器、光盘驱动器、CRT 终端、网卡之类的通信设备等
• 按功能来分：
  • 人机交互设备：用于用户和计算机之间交互通信的设备。
    • 如：键盘、鼠标、扫描仪、打印机、显示器等
  • 存储设备：用于存储大容量数据，作为计算机的外存储器使用。
    • 如：磁盘驱动器、光盘驱动器等
  • 机-机通信设备：用于计算机及和计算机之间的通信。
    • 如：网卡、调制解调器、数/模和模/数转化设备等

总线、系统总线、数据线、地址线、控制线

对应笔记

总线是计算机内数据传输的公共路径，用于实现两个或两个以上部件之间的信息交换。

系统总线指连接处理器芯片、存储器芯片和各种 I/O 模块等主要部件的总线。

系统总线通常由一组控制线、一组数据线和一组地址线构成：

• 数据线（Data Bus）：承载在源和目部件之间传输的信息。数据线的宽度反映一次能传送的数据的位数。
• 地址线（Address Bus） ：给出源数据或目的数据所在的主存单元或 I/O 端口的地址。地址线的宽度反映最大的寻址空间。
• 控制线（Control Bus） ：控制对数据线和地址线的访问和使用。用来传输定时信号和命令信息。

基于总线的互连结构

主要模块以及连接的总线

在上面这个互连结构中，除了 CPU、主存储器以及各种接插在主板扩展槽上的 I/O 控制卡外，还有北桥芯片和南桥芯片组成一个「芯片组」，是计算机中各个组成部分相互连接和通信的枢纽。主板上所有的存储器控制功能和 I/O 控制功能几乎都集成在该芯片组内，它既实现了总线的功能，又提供了各种 I/O 接口及相关的控制功能：

• 北桥是一个主存控制器集线器（MCH）芯片，本质上是一个 DMA 控制器，因此，可通过 MCH 芯片直接访问主存和显卡中的显存。
• 南桥是一个 I/O 控制器集线器（ICH）芯片，其中可以集成 USB 控制器、磁盘控制器、以太网络控制器等各种外设控制器，也可以通过南桥芯片引出若干主板扩展槽，用以接插一些 I/O 控制卡。

I/O 接口的职能

对应笔记

• 数据缓冲：提供数据缓冲寄存器，以达到主机和外设工作速度的匹配。
• 错误或状态检测：提供状态寄存器，以保存各种错误或状态信息供CPU查用。
• 控制和定时：提供控制和定时逻辑，以接受从系统总线来的控制定时信号。
• 数据格式转换：提供数据格式转换部件使通过外部接口得到的数据转换为内部接口需要的格式，或在相反的方向进行数据格式转换。
• 与主机和设备通信：上述功能通过 I/O 接口与主机之间、I/O 接口与设备之间的通信来完成。

I/O 接口的通用结构

• 通过发送命令字到 I/O 控制寄存器来向设备发送命令
• 通过从状态寄存器读取状态字来获取外设或 I/O 控制器的状态信息
• 通过向 I/O 控制器发送或读取数据来和外设进行数据交换

I/O 端口的独立编址方式、统一编址方式

1. 统一编址方式（内存映射方式）：与主存空间统一编址，将主存空间分出一部分地址给 I/O 端口进行编号。
   • 该方法是将 I/O 端口映射到某主存区域，故也称为「存储器映射方式」。
2. 独立编址方式（特殊 I/O 指令方式）：不和主存单元一起编号，而是单独编号，使成为一个独立的 I/O 地址空间。
   • 因需专门 I/O 指令，故也称为「特殊 I/O 指令方式」。

程序直接控制 I/O 方式、中断控制 I/O 方式、DMA 方式的工作原理、区别

对应笔记

• 程序直接控制方式（最简单的 I/O 方式）
  • 无条件传送：对简单外设定时（同步）进行数据传送
  • 条件传送：Polling（轮询，查询）：OS 主动查询，也称为程序查询方式
    • I/O 设备（包括 I/O 接口）将自己的状态放到一个状态寄存器中
    • OS 阶段性地查询状态寄存器中的特定状态，以决定下一步动作
• I/O Interrupt（中断 I/O 方式）：几乎所有系统都支持的中断 I/O 方式
  • 若一个 I/O 设备需要 CPU 干预，它就通过中断请求通知 CPU
  • CPU 中止当前程序的执行，调出 OS（中断处理程序）来执行
  • 处理结束后，再返回到被中止的程序继续执行
  • OS 是被动调出的，也称为中断驱动 I/O 方式
• 直接存储器存取（DMA 方式）：磁盘等高速外设特有的 I/O 方式
  • 磁盘等高速外设成批地直接和主存进行数据交换
  • 需要专门的 DMA 控制器控制总线，完成数据传送
  • 当外设准备好数据后，向 DMA 控制器发 DMA 请求信号，DMA 控制器再向 CPU 发总线请求，
    CPU 让出总线后，由 DMA 控制器控制总线进行传输，无需 CPU 干涉

中断响应、中断处理

对应笔记

中断过程：中断响应 + 中断处理

• 中断响应：调出相应的中断服务程序（处在「禁止中断」状态）
• 中断处理：执行相应中断服务程序的过程
  • 不同的中断源其对应的中断服务程序不同

典型的多重中断处理（中断服务程序）分为三个阶段：

• 先行段（准备阶段）
  • 保护现场及旧屏蔽字
  • 查明原因（软件识别中断时）
  • 设置新屏蔽字
  • 开中断
  • 注：前三个步骤处于「禁止中断」状态，不允许被打断
• 本体段（具体的中断处理阶段）
  • 注：处于「允许中断」状态，可被新的处理优先级更高的中断打断
• 结束段（恢复阶段）
  • 关中断
  • 恢复现场及旧屏蔽字
  • 清「中断请求」
  • 开中断
  • 中断返回
  • 注：处在「禁止中断」状态，不允许被打断

中断优先权的动态分配

对应笔记

• 中断响应优先级：由查询程序或硬联排队线路决定的优先权，反映多个中断同时请求时选择哪个响应。
• 中断处理优先级：由各自的中断屏蔽字来动态设定，反映本中断与其它中断间的关系。

解答

中断屏蔽位：

程序运行过程示意图：

DMA 方式

对应笔记

CPU 停止法

对应笔记

CPU 停止法（成组传送）：DMA 传输时，CPU 脱离总线，停止访问主存，直到 DMA 传送一块数据结束。

周期挪用法

对应笔记

周期挪用（窃取）法（单字传送）：DMA 传输时，CPU 让出一个总线事务周期，由 DMA 控制总线来访问主存，传送完一个数据后立即释放总线。

交替分时访问法

交替分时访问法：每个存储周期分成两个时间片，一个给 CPU，一个给 DMA，这样在每个存储周期内，CPU 和 DMA 都可访问存储器。

I/O 子系统层次结构及每层基本功能

对应笔记

1. 用户空间 I/O 软件：提出 I/O 请求
2. 内核空间 I/O 软件：在底层操作系统中对 I/O 进行具体管理和控制
3. I/O 硬件：在操作系统内核空间 I/O 软件的控制下完成具体的 I/O 操作

用户程序、C 语言库、内核之间的关系

用户程序总是通过某种 I/O 函数或 I/O 操作符请求 I/O 操作。

不管是 C 库函数、API 函数还是系统调用封装函数，最终都通过操作系统内核提供的系统调用来实现 I/O。

Linux 系统中 printf 函数调用过程：