408易错冷门知识点、概念总结和补充

本文由 简悦 SimpRead 转码， 原文地址 zhuanlan.zhihu.com

前言：被去年选择题整麻了，出题老头净找些些偏门知识点，尤其是计网，错的六个选择中计网占了一半，导致我现在极其不信任考纲的范围，所以二周目准备把教材全部通读一遍。以下内容均来自参考教材以及习题解答、以及真题和模拟题：数据结构（严蔚敏）、计组（袁春风、csapp）、OS（汤小丹、现代操作系统）、计网（谢希仁）。
个人建议在成套做完真题之后来看这个文章用于补充，部分内容可能偏难怪，真题不太会考察这么过于细致的内容，建议选择性看。

408 真题一些说明

408 中断默认为外中断，内中断为异常
408 认为链接阶段就产生虚拟地址

• 2013 年计组大题
  在现代计算机体系结构中，Cache 未命中后无需再次访问 Cache。但根据官方答案，无论数据是否存放到 Cache 中，CPU 都是先访问 Cache， 只有当 Cache 中找不到数据时，才会去访问内存，并把内存中的数据读⼊到 Cache 中，CPU 再从 CPU Cache 读取数据。考试中题目未特别说明，建议可以两种都写上

• 2015 年计组大题
  答案中认为 PC 寄存器是用户可见的，这个前提是在 X86 架构下，寄存器的可见性主要看指令集的实现方式，例如 MIPS 架构（精简指令集）下是不可见的，近几年出题风格明显是袁书风格，也就是以 MIPS 架构为主，建议记成 PC 是用户不可见的

• 2023 年选择题第 7 道
  关于非空 B 树，插入的新关键字最终位于叶结点中
  如果以《数据结构（C 语言版）》为准，则该选项错误；而《算法导论》中 B 树插入操作算法采用前置分裂，B 树删除操作算法采用前置合并，该选项却是正确的。根据真题答案，以《数据结构（C 语言版）》和其参考用书《数据结构基础》1976 年版等为准。

• 2014、2022 年计网选择
  **408 中，拥塞窗口值因超时变成 1 这个过程，是立刻改变，而不需要一个 rtt 时间（谢书图中需要一个 rtt 将拥塞窗口设置为 1，所以某些模拟题在计算拥塞窗口时，会加上这个改变时间）

数据结构

概念

例如 单链表是一种逻辑结构 （×） 单链表是存储结构（物理结构）
线索二叉树是物理结构 （√）

链表

• 区分静态链表和动态链表（2024 选择）
  静态链表：使用数组来存储元素，并通过一个数组来存储每个元素的下一个元素的索引。静态链表虽然是顺序存储，但是逻辑上仍是链式，不能用于快速排序
  动态链表：是真正的链表结构，它使用节点（Node）来存储数据和指向下一个节点的指针（或引用）。动态链表可以动态地增加或减少节点，因此它的大小是不固定的。

树

• （）遍历可以保证访问到某节点时，栈中存储的永远是它的全部祖先节点（后序）
• 二叉树的前序遍历相当于入栈，中序遍历相当于出栈
• 区分 度数为 m 的树和 m 叉树
• 线索二叉树 用 0 表示结点孩子，用 1 表示结点前驱，遍历线索二叉树的时间复杂度为 O(n), 空间复杂度为 O(1), 这是因为线索二叉树的遍历不需要使用栈来实现递归操作。
• 树的存储结构（建议看书）：双亲表示法（并查集的结构）、孩子表示法、孩子兄弟表示法
• 并查集 find 操作花费的时间与当前节点到根节点的路径长有关，没有采取优化时，平均时间复杂度为树高 O(lgn)、最坏为 O(n)（考试估计不会考这么细，如果题目没说采取哪种优化方式，最好 / 最坏情况，直接说并查集时间复杂度基本上是错的）

栈与队列

• 共享栈：两个栈共享同一片存储空间，这片存储空间不单独属于任何一个栈，某个栈需要的多一点，它就可能得到更多的存储空间；两个栈的栈底在这片存储空间的两端，当元素入栈时，两个栈的栈顶指针相向而行。
  判断栈满的条件，设低位栈 S1，高位栈 S2
  （1）都指向当前元素：栈满时 S2.top-S1.top==1
  （2）指针指向当前元素下一个位置：栈满时 S1.top-S2.top==1

• 循环队列指顺序存储的队列，而不是逻辑上的循环，如循环单链表表示的队列不能称为循环队列

• 链式栈 / 队列不需要判断栈满 / 队列满，而是动态分配结点

• 带头结点的单链表实现的队列，队首指针始终指向头结点，队首元素是首元结点

串、数组和广义表

• 模式匹配算法：主要有 BF 算法和 KMP 算法。BF 算法实现简单，但存在回湖，效率低，时间复杂度为 O(mxn)。KMP 算法对 BF 算法进行改进，消除回溯，提高了效率，时间复杂度为 O(m+n)。

• 广义表：是另外一种线性表的推广形式，表中的元素可以是称为原子的单个元素，也可以是一个子表，所以线性表可以看成广义表的特例。广义表的结构相当灵活, 在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。广义表通常采用链式存储结构：头尾链表的存储结构和扩展线性链表的存储结构。

• 稀疏矩阵: 稀疏矩阵的三元组表既可以采用数组存储，又可以采用十字链表存储。当存储稀疏矩阵时，不仅要保存三元组表，而且要保存稀疏矩阵的行数、列数和非零元素的个数。

  用三元组存储的矩阵进行转置：(1) 将矩阵的行列值相互交换；(2) 将每个三元组中的 i 和 j 相互调换；(3) 重排三元组之间的次序便可实现矩阵的转置。因为三元组是以行序为主序顺序排列的。

图

• 有向图表示方法：<x,y> || 无向图表示方法：（x,y）
• 连通图的生成树: 一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的 n-1 条边，这样的连通子图称为连通图的生成树。
• 连通分量: 无向图的极大连通子图 G 称为的连通分量，任何连通图的连通分量只有一个，即是其自身
• 有向树和生成森林: 有一个顶点的入度为 0，其余顶点的入度均为 1 的有向图称为有向树。一个有向图的生成森林是由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

• 十字链表和多重邻接表：注意画法
  逆邻接表：任一表头结点下的边结点的数量是图中该结点入度的弧的数量，与邻接表相反。图的邻接表，反映的是节点的出度邻接情况，图的逆邻接表反映的是节点的入度邻接情况

• 构造最小生成树:

• 最短路径

• 判断是否有环

查找

• 哈希表
  散列函数构造方法：数字分析法、平方取中法、折叠法、除留余数法
  同义词：具有不同关键字值但具有相同哈希地址的对象

  二次聚集（或称堆积）：在处理冲突过程中发生的两个第一个散列地址不同的记录争夺同一个后继散列地址的现象称作 “二次聚集”，即在处理同义词的冲突过程中又添加了非同义词的冲突。线性探测法会产生 “二次聚集” 现象。而二次探测法和伪随机探测法以及链地址法可以避免 “二次聚集” 现象，但不能保证一定找到不发生冲突的地址。（前面是书上原话，“避免堆积但还是可能冲突”这描述有点矛盾，我觉得可以认为所有的开放定址法都无法避免 “聚集” 现象）

  **平均查找长度的因素：**查找过程中与给定值比较的个数取决于三个因素: 散列函数、处理冲突的方法和散列表的装填因子，假如所设定的散列函数是 “均匀” 的，则影响平均查找长度的因素只有两个，处理冲突的方法和装填因子α。

• AVL 树查询更高效，红黑树插入和删除更高效

• B 树和 B + 树都是外存查找。B 树查找节点操作在磁盘上进行，在节点中找关键字在内存中进行，所以查找效率取决于 B 树层数 (磁盘查找次数)。B + 树能保存更多的 key，使树更矮，能让读写磁盘次数减少，查找速度更快

排序

• 高优先级的数据要使用稳定的排序，先排低优先级，再排高优先级

• 直接插入排序与折半插入排序：
  （1）直接插入排序适用于链式存储结构，只是在单链表上无需移动记录，只需修改相应的指针；而折半插入排序（包括希尔排序）只能用于顺序结构。
  （2）折半插入排序所需要的关键字比较次数与待排序序列的初始排列无关, 仅依赖于记录的个数。所以当记录的初始排列为正序或接近正序时，直接插入排序比折半插入排序执行的关键字比较次数要少。
  （3）在平均情况下, 折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此折半插入排序的时间复杂度仍为 O( )。
  ᅟᅠ

• 链式存储和顺序存储
  可链式存储的排序
  （1）归并排序可用于链式结构，且不需要附加存储空间，但递归实现时仍需要开辟相应的递归工作栈。而用顺序表实现归并排序时，需要和待排序记录个数相等的辅助存储空间，所以空间复杂度为 O(n)。
  （2）简单选择排序、冒泡排序、基数排序可用于链式结构

  只能顺序存储：折半插入排序、希尔排序、堆排序、快速排序（很难链式结构）

• 易错点：区分插入建堆和给定初始序列建堆（2018 真题与 2021 真题）

• 冷门点：区分多路平衡归并和多路归并

• 优先级调度算法用什么数据结构组织就绪队列效率最高？堆，这样可以总是取出优先级最高的 pcb

• 冷门点：败者树和不用败者树时的比较次数
  不用败者树时，k - 路归并，令 u 个记录平均分布在 k 个归并段上，归并后的第一个记录应是 k 个归并段中关键字最小的记录，这需要进行 k-1 次比较。同理，每得到归并后的有序段中的一个记录，都要进行 k-1 次比较。显然，为得到含 u 个记录的归并段需进行 (u-1)(k-1) 次比较。
  使用败者树时，对于 k 个归并段，首次构建败者树需要 k-1 次比较，而后续每次获取最小的记录最多需要 次
  例如：对于 5 路归并，每个归并段有 20 个记录，则不适用败者树需要 (5-1)(20x5-1)=396 次 比较，而使用败者树时，首次构建败者树需要 4 次比较，后续每次最多比较 3 次。

• 最佳归并树的 io 次数、哈夫曼树带权路径长度、加权平均长度
  最佳归并树的 io 次数：

假设由置换-选择得到9个初始归并段，其长度（即记录数）依次为9, 30, 12, 18, 3, 17, 2, 6, 24。现作3-路平衡归并，其归并树（表示归并过程的图）如图8.21所示，图中每个圆圈表示一个初始归并段，圆圈中数字表示归并段的长度。假设每个记录占一个物理块，则两趟归并所需对外存进行读写次数为 (9+30+12+18+3+17+2+6+24) × 2 × 2 = 484

哈夫曼树带权路径长度：

哈夫曼树加权平均长度：
（2023 真题 4）在由 6 个字符组成的字符集 S 中，各字符出现的频次分别为 3, 4, 5, 6, 8, 10，为 S 构造的哈夫曼编码的加权平均长度为（ 2.5） (3x4 +3x5 +3x6 +2x8 +2x10) / (3+4+5+6+8+10)= 2.5

计算机组成原理

1.1 概念

• Amdahl 定律：对计算机系统的某一部分加速时，该加速部分对系统整体性能的影响取决于该部分的重要性和加速程度

• 冷门点：ISA 是对指令系统的一种规定或结构规范, 而具体实现的组织 (organization) 称为微体系结构 (microarchitecture), 简称微架构, ISA 和微体系结构是两个不同层面上的概念, 微体系结构是软件不可感知的部分，相同的 ISA 可能有不同的微体系结构。
  ISA 规定的内容包括数据类型及格式、指令格式, 寻址方式和可访问地址空间大小, 程序可访问的寄存器个数、位数和编号、控制寄存器的定义、I/0 空间的编址方式、中断结构、机器工作状态的定义和切换、输入输出结构和数据传送方式、存储保护方式等。
  例如, 加法器采用串行进位方式还是并行进位方式实现属于微体系结构范畴。（具体实现是微架构实现）

• 寄存器可见问题

1.2 时间复杂度与空间复杂度

对于按行优先存放在内存的多维数组, 如果按列优先访问数组元素, 则空间局部性就差
如果在一个循环体中某个数组元素只被访问一次, 则时间局部性就差。

2.1 数值转换

• 数值表示范围
  例如 123456789==(int)(float)123456789 （×）
  123456==(int)(float)123456 （√）
  123456789==(int)(double)123456789（√）
  (d+f)-d==f （×）
  i==(int)(double)i （√）

（补充，对于 float 有效位数这个概念，不能单纯理解为 8 位十进制就不能存放，例如 16777215 就可以存放。有效位数主要是指规格数的精度，其最差精度出现在尾数由 1.00…000（首位 1 是隐含的，后面 23 个 0）变成 1.00…001，相对变化比例为 2^-23，转化为十进制有效位数 23lg2 约为 6.92 位；最好精度出现在 1.11…111 末位变化 1，十进制有效位数为 24lg2 约为 7.22 位。所以综合下来，我们常说 “IEEE754 的精度是 7 位十进制数字”）

• 冷门点：C 语言中，一个运算中同时有无符号整数和带符号整数，会将带符号整数强制类型转换为无符号整数。（C 语言标准不同，相同的表达式可能会有不同结果。例如 在 C99 中为带符号整型，而在 C90 中为无符号整型）

2.2 数据的存储

• 冷门点：音频，图片等文件格式或处理程序也涉及字节顺序问题，例如 GIF、Microsoft RTF 采用小端方式；PS、JPEG 等采用大端方式。
• **易错点：**边界对齐存储，起始地址大小必须是自身大小整数倍，例如 double 类型起始地址必须是 8 倍；结构体的总大小必须是最宽基本类型成员大小的整数倍

3.1 数值运算

• 易错点：算数移位的溢出判断，注意移位时符号位并非保持不变，而是整体移动 (王道说的符号位不变，有个前提是不发生溢出) 还可以转回十进制数，乘以 2 看是否在范围中

• 易错点：加法器的两个输入端信息和输入的低位进位信息

• 乘法运算分类

• 除法运算分类

• 桶型移位器：移位指令有时要求一次移动若干位，对于**这种移动多位的操作，可采取桶型移位器，**它利用大量多路选择器来实现数据的快速移位

• 冷门点：在门电路延迟一定的情况下, 加法器的速度主要取决于进位方式, 先行进位方式比串行进位方式的速度快。
  ᅟᅠ

• 易错点：
  串行乘法运算是通过多次累加和左移完成的，而串行除法运算是通过多次累加和右移完成的 （x）
  串行乘法移位时, 将进位位、部分积和乘积部分一起进行算术右移 （x）
  区分算数移位和乘除法运算中的移位，算数左移相当于乘法，右移相当于除法，但是串行乘法运算是多次累加和逻辑右移，而串行除法运算是通过多次累加和左移实现的

3.2 浮点数

• 0 的表示: 用 0000 0000H 表示 + 0, 用 8000 0000H 表示 - 0。当运算结果出现阶码过小时, 计算机将该数近似表示为 0, 称为 “机器 0”

• 冷门点：判断浮点数是否溢出，取决于阶码（指数）是否上溢出

• 易错点：规格化尾数的表示形式。尾数范围：设尾数是 W，且基数为 R，则当 1/R≤|W|＜1 时，浮点数为规格化数

• 冷门点：IEEE 754 的四种舍入方式：就近舍入 (四舍五入)、朝 0 舍入、朝 +∞舍入、朝−∞舍入

• 冷门点：**浮点数的区间间隔的计算，**舍入误差会随着数值增大而增大，也就是相邻可表示数的间隔越大。
  例如，规格化数最小间隔区间： ，其中浮点数最小数值区间为 ， ，数值位为 23 位，所以能表示 个尾数。
  规格化数最大间隔区间：

• 冷门点：浮点数阶码之差过大直接忽略，若 |E| 等于 25, 则保留的附加位中, 最左边第 1 位一定是 0, 采用就近舍入时, 这些附加位完全被丢弃。因此， |E | 大于等于 25 时, 可以使运算结果直接取阶大的那个数。

4.1 指令

• 易错点 访存指令不能访问栈中信息, 必须提供专门的入栈和出栈指令（×）
  栈是一个动态存储区, 每次过程调用都会生成一个新的栈帧, 栈顶的地址存放在一个特定的栈指针寄存器中, 可以使用专门的入栈和出栈指令来访问栈顶数据, 也可以通过普通的访存指令来读写栈帧中某个位置的内容

• 冷门点：变长指令字格式是一种不规整型指令集格式，因此，在取当前指令时，可以每次按最长的指令长度来取。例如，如果最长指令长度为 6，则每次取 6 个字节。

• 基准地址和偏移量：
  变址寻址时，指令中提供的形式地址是基准地址，位移量由变址寄存器给出（例如存放数组下标值）
  基址寻址时，指令中给出的形式地址为位移量，而基准地址由基址寄存器提供
  相对寻址时，指令中给出的形式地址为位移量，而基准地址由程序计数器 PC 提供

5 中央处理器

组合逻辑电路：简称组合电路, 用来构成 “操作元件”。组合逻辑电路在逻辑功能上的特点是, 任意时刻的输出仅仅取决于该时刻的输人, 与电路原来的状态无关。因此，它没有存储功能。

时序逻辑电路：简称时序电路, 用来构成 “状态元件”。时序逻辑电路在逻辑功能上的特点是, 任意时刻的输出不仅取决于当时的输入信号, 而且还取决于电路原来的状态, 或者说, 还与以前的输人有关。时序逻辑电路具有存储功能，能保存所存储的状态。

微程序层次：微程序（ 微指令（ 微命令 ）），一条指令的功能通过执行一条微程序实现

• 易错点：不同异常事件，返回地址（断点）不同，例如 故障的断点是发生故障的当前指令的地址；自陷的断点是自陷指令后面一条。
  比如执行 lw/sw 指令发生缺页异常，则缺页处理结束后的返回地址应该是当前 PC-4（和指令长度有关），才能保证缺页异常处理后重新执行 lw/sw 指令。

• 易错点：内部异常的识别大多采用软件识别，外部中断源可以采用软件识别和硬件识别方式

• 冷门点：单周期和多周期的时钟周期

单周期处理器的时钟周期：数据通路的时钟周期的长度应该以最复杂的指令所需的执行时间为准来确定, 以保证所有指令都能在一个时钟周期内完成。取数 load 指令一般是最复杂指令，因此单周期处理器的时钟周期至少为 200+50+100+200+50=600ps

**多周期处理器的时钟周期：**多周期数据通路通过把指令的执行分成多个阶段来实现, 即 CPI>1。规定每个阶段在一个时钟周期内完成, 时钟周期以最复杂的阶段所花时间为准, 阶段的划分原则是: 将一条指令的执行过程尽量分成大致相等的若干阶段。所以上述题目中多周期时钟周期至少为 200ps

6.1 流水线

注意区分多周期和流水线，流水线没有中断周期，而是在不同流水段中加入响应检测逻辑去判断异常或中断

• 易错点：流水线深度 / 流水线段数越多，处理器时钟频率越高（√）
  因为处理器的架构设计，包括流水线深度。在一定范围内，增加流水段个数, 使得每个流水段内的操作变得非常简单, 因而, 每个阶段的延时就很小, 也就缩短了时钟周期, 提高了时钟频率。

• 易错点：取指令和指令译码两个阶段不需要控制信号对其进行控制（√）
  对所有指令来说, 取指令和指令译码两个阶段的动作都是一致的, 只要让这两个阶段的功能部件完成特定的功能就行了, 而无须区分是哪条指令对应的功能, 因而也就不需要控制信号对其进行控制。

• 造成流水线阻塞的原因

• 结构冒险的解决办法

• 数据冒险的解决办法

• 插入空指令和插入气泡解决数据冒险的区别。

• 易错点：load-use 数据冒险不能只通过转发（数据旁路）技术解决
  当一条加载（Load）指令正在从内存中读取数据，而后续的一条或多条指令需要使用这条加载指令读取的数据作为操作数时，如果这些后续指令在加载指令完成之前就开始执行，就会引发 Load-use 数据冒险。解决方法：1、load 指令之后插入 nop 指令 2、 程序编译时进行优化，调整指令顺序避免出现 load-use
  （补充：强烈建议做下教材后面的题，有个很细的点就是 采用转发和不采用转发、读写口是否采用前半周期读和后半周期写，这几个前提不同，则插入的 nop 条数也不同）ᅟ        ‌‍

• 控制冒险 , 注意无条件转移指令也会引起控制冒险

6.2 高级流水线

• 冷门点：**写后写 (WAW) 相关，**若前一条指令和后一条指令都需要对同一个寄存器进行写人, 则称这两条指令是写后写相关的。这种相关性, 在无序发射或乱序执行时可能会发生数据冒险, 而在按序发射和完成时, 不会发生数据冒险。（所以一般考的指令流水线形式，不用去考虑写后写这种情况）

_7._1 存储器层次结构

• 按存取方式分类

• **存取时间和存储周期，**通常存储周期 大于存取时间

• 冷门点：Flash 存储器的读取速度与半导体 RAM 芯片相当、写数据的速度比 RAM 芯片慢很多

• 冷门点：DRAM 和 SRAM 的中文全称
  SRAM: 半导体静态随机访问存储器, 使用 **MOS 管，**可用作 cache
  DRAM: 半导体动态随机访问存储器, 采用电容，可用作主存

• DRAM：
  （1）SDRAM，也称同步 DRAM（synchronous DRAM），传统 DRAM 与 CPU 之间采用异步方式交换数据，SDRAM 采用同步方式交换数据。
  （2）**刷新计数器：**用于跟踪和记录存储器的刷新操作。大小与行数有关，和位数无关，例如 4096 行，刷新计数器大小 12bit；16K×4 位有 128 行，刷新计数器大小 7bit，刷新需要 128 次
  （3）dram 芯片的行缓冲采用 SRAM 元件实现
  （4）DDR SDRAM 是对标准 SDRAM 的改进设计（也就是 ddr4、5 内存条等）芯片内部缓冲可以进行 2 位预取（ddr2 为 4 位、ddr3 为 8 位），一个时钟内传送两次数据。

• 冷门点：**双端口 RAM，**支持两个 CPU 同时读、读写不同存储单元，但不能同时写或一读一写同一个单元

7.2 磁盘

• 题目：磁盘容量的计算
  例：假定有一个磁盘存储器, 磁盘片外径为 355.6mm, 有 20 个记录面, 每面有 51mm 区域用于记录信息, 道密度为 3.92tpm(道 / 毫米), 位密度为 90bpm(位 / 毫米) 求磁盘容量大小

• 冷门点：**扇区是磁盘的最小编址单位，磁盘与主机交换数据最小单位是一个扇区。**每个扇区存放一个记录块, 每个记录块有相应的地址标识字段、数据字段和校验字段等。到磁盘上寻找数据时, 只要定位到数据在哪个磁头的哪个磁道的哪个扇区。所以扇区是磁盘的最小编址单位。

• 易错点：磁盘驱动器是磁盘本身，而磁盘控制器才是 IO接口
  

• 易错点：磁道满后，信息放在同一柱面的下一个盘面

• 易错点：RAID 可靠性不一定与数字挂钩，例如系统 A 使用 RAID1 技术, 系统 B 使用 RAID 5 技术，系统 A 更可靠, 因为系统对整个磁盘都进行了备份, 所以即使所有的数据都损坏了也可以恢复。而系统 B 只是记录了部分冗余信息, 如果两个磁盘的相同位都损坏了就恢复不出来。RAID1：镜像磁盘阵列，RAID5：无独立校验的奇偶校验的磁盘阵列

• 易错点：条带化，将数据分散存储在多个磁盘上，以**提高数据访问的速度，不能增加可靠性，**并没有提供数据冗余的功能

以下为概念补充

低密度存储方式：所有磁道扇区数相同，每个磁道上的位数相同，所以内道上的位密度比外道位密度高
**高密度存储方式：每个磁道上的位密度相同，所以外道上的扇区数比内道多，**整个磁盘容量比低密度存储方式高

磁道黏着：在 SSTF、SCAN 及 CSCAN 种调度算法中, 都可能出现磁臂停留在某处不动的情况。例如，有一个或几个进程对某一磁道有较高的访问频率，即这个 (些) 进程反复请求对某一磁道的 I/O 操作，从而垄断了整个磁盘设备。我们把这一现象称为 “磁臂粘着”(Armstickiness), 在高密度磁盘上容易出现此情况。可用 NstepSCAN 算法解决

7.3 固态硬盘

7.5 cache

• 结论 cache 缺失对总体性能的影响
  （1）CPI 越小，cache 缺失引起的阻塞对系统总体性能的影响越大
  （2）CPU 时钟频率越高，cache 缺失损失就越大
  （3）处理器性能越高，cache 缺失对总体性能影响越大

• 主存块大小的影响：
  （1）主存块变大, 使得缺失损失也变大, 因为需要花费更多时间从主存读一个较大的块
  （2）主存块变大, 则 cache 行数变少, 因而需要替换的可能性增加, 从而导致命中的可能性变小

• 冷门点：对于一级 cache（L1）指令和数据一般分开存放；而对于二级以上的 cache，其指令和数据是放在一起的

• 冷门点：写分配方式充分利用了空间局部性，而非写分配法没有很好地利用空间局部性（写分配：在写缺失的情况下, 同时将数据写入到 cache 跟内存中）

• 易错点：cache 缺失不是内部异常, 更不是外部中断，同时 cache 对于程序员来说是透明的。

• LRU 算法替换位
  直接映射：一个给定的主存块只能映射到一个固定的 cache 槽中, 所以, 在对应 cache 槽已有一个主存块的情况下, 新的主存块毫无选择地把原先已有的那个主存块替换掉, 因而无须考虑替换算法。
  全相联映射：与行数有关，例如 8 行需要 3bit 的替换位
  组相连：**与路数有关，**例如 4 路组相连需要 2bit，同时需要也 4 个比较器（n 路组相连需要 n 个比较器）

• 易错点：区分 CPU 访问地址单元 / 主存块 / 数组（推荐看书）

7.6 虚拟存储器

未分配页_：_该页在物理内存中不存在对应的物理页，也没有加载到内存中。比如栈区与共享库之间、堆区与共享库之间
缓存页：已调入主存而被缓存在 DRAM 中的页面
未缓存页：未调入主存而存在外存中的页面

进程中的所有页面都可以被划分为 3 个不相交的页面结合：未分配页集合、缓存页集合、未缓存页结合
所以有效位为 0，可能有两种情况：未分配和已分配但未缓存，如果页面是未分配页，则内核将分配一个新的物理页面（页框），再更新页表项，将虚拟地址与物理地址相关联；已分配但未缓存就和平时学的过程那样

	cache - 主存层次	主存 - 辅存层次
映射方式	直接 / 全相联 / 组相联	全相联
映射关系实现	硬件	操作系统的页表
写策略	直写和回写	回写
缺失处理	硬件	软件（操作系统）

cache 缺失	TLB 缺失	页面缺失
硬件处理	软件或硬件	软件处理（缺页异常）

8.1 基于总线的互连结构

• **概念：总线事务，通常把在总线上一对设备之间的一次信息交换过程称为一个总线事务。**例如, 存储器读事务是指将数据从主存取出到处理器, 存储器写事务是指将数据写到主存。典型的总线事务类型有存储器读、存储器写、I/O 读、I/O 写、中断响应等

• 易错点：同一个总线不能既采用同步方式又采用异步方式通信（×）
  **半同步通信总线就可以这样。**这类总线既保留了同步通信的特点, 又能采用异步应答方式连接速度相差较大的设备。通过在异步总线中引人时钟信号, 其就绪和应容等信号都在时钟的上升沿或下降沿有效, 而不受其他时间信号的干扰。通常 I/O 总线采用半同步总线。例如, PCI 总线是一种半同步总线, 它的所有事件在时钟下降沿同步, 总线设备在时钟开始的上升沿采样总线信号（存疑，PCI 是同步总线，但是袁书课后问答这里说是半同步）。

• 冷门点**：QPI 总线用在 CPU 内部，PCI 总线用于 IO 连接** QPI 总线带宽 = 每秒传输次数 × 每次传输的有效数据 ×2 PCI1.0 规范总线带宽 = 2.5Gb/s×2× 通路数 / 10

• 易错点：点对点连接方式, 无须考虑总线裁决。只有在多个主控设备共享总线的情况下, 才需要进行总线裁决, 有集中式裁决和分布式裁决两类。

• 易错点：总线标准 ISA、EISA、PCI、APG 等都是并行传输的同步总线, 现在主要采用串行总线标准 PCI-Express。（注意 PCI 和 PCI-Express）

• 冷门点：主机和外设之间的正确连接通路：CPU 和主存 - IO 总线 - IO 接口 (外设控制器)- 通信总线 (电缆)- 外设
  通常 **I/0 总线和通信总线的数据宽度不同，**因此，在主机侧和外设侧的数据宽度不一样。因而在 IO 接口中需要有进行数据格式转换的逻辑电路。此外，还需在主机侧和外设侧分别有相应的总线接口逻辑，以支持与 I/O 总线和通信总线的连接。

8.2 IO 编址

• 统一编址方式，也称存储器映射方式。因为可以用访存指令进行 IO 访问，所以保护机制可由分段或分页存储管理来实现，大多数 RISC 架构都采用统一编址方式，例如 MIPS、RISC-V。

• 易错点：统一编址方式下无需通过专门的 IO 指令访问 IO 端口 （√）
  因为主存单元和 I/0 端口在同一个地址空间。所以，主存单元号和 I/O 端口号肯定不会相同，它们分属两个不同的地址范围。因此, 通过指令给出的地址范围就可以确定访问的是主存单元还是 10 端口，因而指令系统无须提供专门的 I/O 指令。

• 易错点： I/O 设备和 I/O 接口两部分结合起来就是输入输出系统（×）
  不是。I/O 设备和 I/0 接口只是 I/0 硬件部分, 输人输出系统应该包括 I/O 硬件和 I/O 软件两个部分。

• 易错点：一个 I/O 接口只能有一个地址 （×）
  每个 I/O 端口对应唯一的一个地址, 但一个 I/O 接口中可能有多个程序可访问的寄存器, 也就是有多个 I/O 端口, 所以应该有多个地址。

8.3 IO 中断

• 易错点：最坑的一题，中断响应优先级和中断处理优先级的细节理解
  响应优先级：2>4 处理优先级: 4>2
  2 在保存完自身状态信息后开中断，即在中断服务程序前。一旦开中断，则马上响应 4 号中断源，因为第 2 号的中断屏蔽字中对第 4 号中断源的屏蔽位是 0，也即对第 4 号中断源是开放的。而 1、3、5 中断请求需要在 2 执行对应中断服务程序时才会发生。

• 冷门点 中断响应时间的相关因素：断点和状态信息保存时间、中断源识别和判优速度、获得中断服务程序首地址和初始状态的时间
  例如：软件查询速度就比较慢；MIPS 将断点直接保存到特殊寄存器 EPC 中，不需要访问内存，因此 MIPS 处理器的中断响应时间很短。

• 易错点：中断源的识别和中断判优方法可分为软件查询和硬件判优，其中软件查询方法可以通过改变中断查询顺序来改变中断响应优先级，而硬**件判优（向量中断）无法改变中断响应优先级。**所以视题目而定，现代多采用向量中断方式，而且题目中没有特别强调是软件查询方式的情况下，中断响应优先级不可改变的说法可以认为是正确的

• 冷门点：DMA 可以采用虚拟地址和物理地址**，但主要采用物理地址**，因为 DMA 控制器不经过 CPU 的虚拟内存系统，它直接访问物理内存。

• 冷门点：解决 DMA 请求的主存值和 cache 中副本不同的方法（io 一致性问题）
  1、让所有 IO 活动都通过 cache 进行，缺点是会影响 cache 命中率
  **2、cache 刷新，**即让操作系统在 IO 读时有选择地使某些 cache 块无效，而在 IO 写时让 cache 进行一次写回操作 **3、硬件机制选择被刷新或使无效的 cache 项，**多用在多处理器系统中

• 冷门点：CPU 对 DMA 请求和中断请求的响应时间不一样
  CPU 总是在一次总线事务完成后响应, 因此,DMA 响应时间应该少于一个总线周期
  CPU 总是要等到一条指令执行结束后, 才去查询有无中断请求, 所以中断请求响应时间少于一个指令周期的时间。

• 易错点：异常不属于不可屏蔽中断，外中断才分屏蔽和不可屏蔽，内中断全是不可以被屏蔽的中断，不是 “不可屏蔽中断”。外部设备都是通过 intr 接口向 cpu 发出中断，均属于可屏蔽中断

9.1 并行处理系统

• Flynn 分类

SISD（单指令单数据流）	SIMD（单指令多数据流）	MISD（多指令单数据流）	MIMD（多指令多数据流

• 按地址空间的访问方式分类：多计算机系统（消息传递系统）、多处理器系统（共享存储系统）

区别：其中多计算机系统采用分布式存储器访问方式，某一计算节点无法通过 load/store 指令访问另一个节点的存储器，而是通过消息传递方式进行数据传送。多处理器系统共享单一地址空间的并行处理系统，每个处理器都可以通过 load/store 指令访问存储器。

• 按存储访问时间是否一致划分：UMA（一致性内存访问结构）、NUMA（非一致性内存访问结构）

区别：UMA 每个处理器访问存储单元的时间相同，NUMA 访问不同存储单元的访问时间可能不一致

一些题目（个人复习用）

• 乘除法运算相关题目

• 浮点数相关题目

非 IEEE 754 格式的浮点数计算

多模块能高速读写的原因

DDR

cache 求访问地址序列

求单周期的时钟周期

操作系统（内容、排版未做完）

操作系统参考书算是最杂的，就单纯 CPU 调度算法这块，唯一完全符合 408 考纲的是《操作系统概念》这本书，其他书或多或少概念分类有所出入（王道估计也是抄的这块，排版这块基本一致）；又比如多处理机这块新增的考点，汤书和黑书的侧重点又完全不一样，所以总结起来十分难受。

场景总结

• 输入型设备访问流程

• 存储型设备访问流程

2.1 进程概念

• 四种主要事件会导致进程的创建

• 进程的终止

• 易错点：区分程序和进程的特性。封闭性、可再现性是针对程序顺序执行而言，而程序并发执行具有失去封闭性、不可再现性的特点 ，而为了解决程序并发执行时的缺点，因此引入了进程，所以进程具有异步性。
  **异步性：**进程可按各自独立的、不可预知的速度向前推进。虽然进程具有异步性，但操作系统必须保证进程并发执行的结果是可再现的。
  **失去封闭性：**程序在执行时与其他并发执行的程序共享系统的资源，因此，资源状态的改变还与其他程序有关，即程序本身的执行环境要受到外界程序的影响。

• 冷门点：内核态也称管态、系统态；用户态也称目态

• 冷门点：静止就绪和活动就绪，静止阻塞和活动阻塞，主要区分静止在外存、活动在内存，也就是挂起。 例如，正在执行的进程由于其时间片用完被暂停执行，此时进程应从执行状态变为 (活动就绪) 状态; 处于静止阻塞状态的进程，在进程等待的事件出现后，应变为 (静止就绪) 状态; 若进程正处于执行状态时，因终端的请求而暂停下来以便研究其运行情况，这时进程应转变为 (静止就绪) 状态，若进程已处于阻塞状态，则此时应转变为 (静止阻塞) 状态。

• 易错点**：进程切换、模式切换和中断响应**
  模式切换：同一进程在用户态到内核态的相互切换。用户态→内核态，只需要保存用户态的上下文到内核堆栈中；内核态→用户态，只需要从内核堆栈中恢复用户态的断点和上下文，因此不需要保存和恢复内核态的上下文。（补充：中断响应不一定导致特权级切换，例如内核态下的中断）
  进程切换 (时间片轮转调度为例)：进程 P0(用户态)→进程 P0(内核态)→进程 P1(内核态)→进程 P1(用户态)，其中 P0 切换到内核态后，时钟中断检查 P0 的时间片，时间片用完时，将 P0 变更为就绪态，再从就绪读队列中选择出可以切换的进程 P1 的 PCB。将 P0 的上下文保存在 PCB0 中，再从 PCB1 取出 P1 的上下文放入各个寄存器中，处理完各种中断异常后从 P1 的内核堆栈取出 P1 的用户态上下文，中断返回到 P1 的用户态。
  其中进程切换和调度均发生在内核态下，内核态上下文保存在 PCB 中；进程从运行态到就绪态的转换也主要发生在内核态下

• 冷门点：利用两组寄存器减少上下文切换的时间，其中的一组寄存器供 CPU 在系统态时使用，而另一组寄存器供应用程序使用。在这样条件下的上下文切换，只需改变指针，使其指向当前寄存器组即可。

• 易错点**：**块设备缓存位于用户地址空间 （×）
  **操作系统为 IO 设备提供缓存，位于内核空间；而共享内存位于用户地址空间，**进程可以在用户态下直接访问共享内存

概念补充
**守护进程：**停留在后台处理诸如电子邮件、web 页面这类活动的进程称为守护进程。例如 Windows 中的，可使用任务管理器。

2.2 进程同步

• **自旋锁：适用于多处理机系统，**用于忙等待的锁。当一个线程尝试获取一个已被另一个线程持有的自旋锁时，该线程不会立即被阻塞，而是会进入一个循环，反复检查锁是否已被释放。如果锁已被释放，该线程就可以成功获取锁并进入临界区。因为在不断地循环检查锁状态，会浪费大量的 CPU 时间

  （1）自旋锁无法实现 “让权等待”，而阻塞锁可以实现 “让权等待”
  （2）自旋锁和信号量均可用来实现进程互斥，单处理机系统中不适合用（自旋锁）; 在多处理机系统中，当临界资源被占用时间非常短暂时比较适合用（自旋锁），否则更适合用 （信号量）。

1. 自旋锁与信号量：主要差别在于，自旋锁可避免调用进程阻塞。由于自旋锁使用者一般保持锁时间非常短，调用进程用 “旋转” 来取代进程切换。而我们知道进程切换需要花费一定开销，并且会使高速缓存失效，直接影响系统的性能，因此将自旋锁应用于对总线资源的竞争，其效率远高于信号量机制，且在多处理器环境中非常方便。

   管程中的条件变量与信号量：
   相似点: 条件变量的 wait()signal() 操作类似于信号量的 P/ V 操作，可以实现进程的阻塞 / 唤醒。
   不同点: 条件变量是 “没有值” 的，仅实现了 “排队等待” 功能；而信号量是 “有值” 的，信号量的值反映了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。
   关于管程的题目
   ① (整型信号量) 是一种只能由 wait 和 signal 操作所改变的整型变量
   ② wait、signal 操作可以解决一切互斥问题 （√）
   ③ wait 一定会阻塞进程，而 signl 不一定会唤醒（队列中没有进程时）

• 冷门点：处于临界区的进程也能被中断（内核程序临界区在某些情况下也会发生中断）
  即使进程 A 正在临界区内执行，如果发生了中断，它的执行也会被暂停，并且 CPU 有可能被调度给另一个就绪的进程（如进程 B）

以下为概念补充

AND 型信号量：用于解决记录型信号量只针对的多个并发进程仅共享一个临界资源的情况

2.3 进程通信

• 易错点：共享文件进行通信的方式属于共享存储器通信 （x）
  共享文件进行通信的方式属于管道通信，管道是一种特殊的共享文件

• 冷门点：共享存储器系统中，基于共享数据结构的通信方式属于低级通信方式，同时生产者和消费者问题中的有界缓冲区就属于基于共享数据结构的通信方式

在共享存储器系统中，相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信。据此，又可把它们分成以下两种类型：

(1) 基于共享数据结构的通信方式。在这种通信方式中，要求诸进程公用某些数据结构，借以实现诸进程间的信息交换，如在生产者-消费者问题中的有界缓冲区。操作系统仅提供共享存储器，由程序员负责对公用数据结构的设置及对进程间同步的处理。这种方式仅适于传递相对少量的数据，通信效率低下，属于低级通信。

• 易错点: 共享存储区的申请和撤销由操作系统控制，而访问控制是由进程负责

基于共享存储区的通信方式。为了传输大量数据，在内存中划出了一块共享存储区域，各个进程可通过对该共享区的读或写交换信息，实现通信。数据的形式和位置甚至访问控制都是由进程负责，而不是OS。这种通信方式属于高级通信。需要通信的进程在通信前，先向系统申请获得共享存储区中的一个分区，并将其附加到自己的地址空间中，便可对其中的数据进行正常读写。读写完成或不再需要时，将其归还给共享存储区。

2.4 线程

• 易错点：线程是由线程创建的

• 冷门点：部分线程可以不被终止

• 易错点：用户级线程与内核级线程调度的区别

• 冷门点：用户级线程和内核级线程执行系统调用时的区别

• 冷门点：多对一模型和一对一模型对于线程运行在多处理机上的区别

• 冷门点：区分用户级线程、内核线程和轻量级线程（LWP）

以下为概念补充

用户级线程：用户级线程具有相同的结构，都运行在一个中间系统上。有两种方法实现中间系统，运行时系统和内核控制线程

• 运行时系统：介于应用程序和操作系统之间的软件系统，实质上是用于管理和控制线程的函数 (过程) 的集合。在传统的 OS 中，进程是利用 OS 提供的系统调用来请求系统资源的，系统调用通过软中断机制进入 OS 内核，由内核来完成相应资源的分配。用户级线程是不能利用系统调用的，当线程需要系统资源时，是将该要求传送给运行时系统，由后者通过相应的系统调用来获得系统资源。常见的运行时系统包括 Java 虚拟机（JVM）Python 解释器等
• **内核控制线程：**也称轻量级线程 (LWP)，是一种由内核支持的用户线程. 它是基于内核线程的高级抽象，因此只有先支持内核线程，才能有 LWPS，每一个进程有一个或多个 LWPS。

2.5 调度算法

为什么王道书中说里面调度会有仅适用于进程，仅适用于作业，是因为高级调度（作业调度）基本只存在批处理操作系统，而中级调度（内存）和低级调度（进程）在这三种操作系统中均存在。

例题：

• 调度算法的选择
  【先来先服务算法】有利于 CPU 繁忙型的作业（长作业），而不利于 IO 繁忙型的作业（短作业）
  实时系统的进程调度，通常采用【抢占式的优先级高者优先】算法
  【短进程优先】算法的平均等待时间和平均周转时间是最短的。
  系统开销小的调度算法是【先来先服务算法】（高响应算法需计算响应比，时间片轮转有上下文切换）

• 易错点：当有更高优先级进程进入就绪队列时，会通过中断方式通知操作系统须进行进程调度 （x）
  优先级更高的进程抢占 CPU 并不通过中断方式，而是在操作系统将某个优先级更高的进程置为就绪态 (创建进程或唤醒进程) 时，检查新就绪的进程是否有更高的优先级，若新就绪进程优先级更高，则发起进程调度抢占 CPU

2.6 死锁

• 冷门点：可抢占性资源和不可抢占性资源的区别
  可抢占性资源：是指某进程在获得这类资源后，该资源可以再被其它进程或系统抢占。例如优先级高的进程可以抢占优先级低的进程的处理机。CPU 和主存均属于可抢占性资源，对于这类资源是不会引起死锁的（重点）。

  不可抢占性资源：系统把某资源分配给该进程后，只能在进程用完后自行释放。磁带机、打印机等也都属于不可抢占性资源。

• 死锁的起因 (与必要条件区别)：1. 竞争资源 2. 进程推进顺序不当引起死锁

• 死锁四个必要条件中，“互斥使用资源”一般无法破坏，“一次性分配策略”破坏了 “请求和保持” 条件、“资源有序分配”破坏了“循环等待条件”

• 易错点：限制进程申请资源顺序的方案属于死锁避免（x）
  属于死锁预防，死锁避免不限制进程申请资源顺序，只会在进程申请资源请求时决定是否满足其要求

3.1 连续分配存储管理方式

• 易错点：重定位需要对指令和数据的地址都进行修改，静态重定位不允许程序运行时在内存移动位置
• 冷门点：首次适应、最佳适应等均属于基于顺序搜索的动态分区分配算法，而大中型系统中往往采用基于索引搜索的动态分区分配算法，目前常用的有快速适应算法、伙伴算法和哈希算法（2024 考研中涉及）

关于伙伴系统的题目

• 冷门点：最坏适应算法产生碎片的可能性最小，查找效率高

提高内存利用率的方式

以下为概念补充

反置页表：反置页表则通过让所有进程共享一张页表来减少内存占用，这张页表中的条目数量与物理内存中的页框数量相等。通常被用于具有大量进程和需要高效内存管理的系统中。例如，在一些高端服务器、数据库系统或云计算平台中，反置页表可以显著提高系统的整体性能和稳定性。

3.2 分段存储管理方式

• 冷门点：分段存储管理的优点

• 冷门点：可重入代码的细节

5.1 虚拟存储器

5.2 请求分页存储管理方式

• 冷门点：CLOCK 算法也称 NRU 算法 / 最近未用算法
• 冷门点：队列实现的算法可能会出现 belady 异常，例如 fifo，clock(某年 912 证明题)
• 冷门点：在为进程分配内存时，为保证进程能正常运行，所需要的最小物理块数的确定

• 冷门点：实现 LRU 算法的需要有栈或寄存器的支持，注意如何通过寄存器判断该换出哪个

以下为概念补充

页面缓冲算法

5.5 请求分段存储管理方式

• 易错点：页表表项和段表表项

以下为概念补充

环保护机构：是分段保护机制中的一种，分段保护机制包括越界检查等

6.1 设备驱动程序

以下为概念补充

设备处理方式，例如**如果没有设备驱动程序，**如何与设备交互

6.2 设备独立性软件

• 易错点：设备出现故障后，主要由设备驱动程序处理，而设备独立性软件只处理那些设备驱动程序无法处理的错误

• 冷门点：设备分配时按物理设备和逻辑设备分配的区别
  按物理设备分配的缺陷：（1）用户编程时必须使用 “物理设备名 “，底层细节对用户不透明，不方便编程。(2) 如果换了一个物理设备，即使是同类型的设备 (如都是打印机，但是打印机品牌不同，则程序将无法运行。(3) 如果进程请求的物理设备正在忙碌，即使系统中还有同类型的设备，进程也必须阻塞等待。
  按逻辑设备分配：根据进程请求的逻辑设备名查找 SDT(系统设备表)，在 SDT 中就有一个字段记录了设备类型，因此操作系统可以根据用户提供的逻辑设备名依次查找 SDT，找到一个用户指定类型并且空闲的设备分配给进程，只有所有该类型的进程都忙碌时才需要将进程阻塞。

6.3 用户层的 I/O 软件

• 易错点：IO 软件并不都放在操作系统内部。一般而言，大部分的 IO 软件都放在操作系统内部，但仍有一小部分在用户层，其中包括与用户程序链接在一起的库函数，以及完全运行于内核之外的假脱机系统等。

6.4 SPOOLING

（1）缓冲区技术主要用于解决数据传输速度不匹配的问题，而 S**POOLing 技术主要用于解决独占设备利用率低的问题，**即多用户、多任务并发执行时的问题，通过将数据先存储到磁盘或其他外部设备中 (例如对打印机写，变成对磁盘这种快速设备的写操作)，然后再进行后续处理。
（2）spooling 输出输入进程只存在内核态

6.5 缓冲区

7.1 文件存储

• 系统中运行的大量的源程序、可执行文件、库函数采用无结构的文件形式，即流式文件，而信息管理系统、数据库系统这类采用有结构的文件形式

7.4 文件共享

文件共享可分为基于有向无循环图实现文件共享和利用符号链接实现文件共享, 也就是硬链接和软链接

• 软连接（符号链接）

优点：**跨越磁盘甚至远程命名文件，**只要简单地提供一个机器的网络地址以及文件在该机器上驻留的路径，就可以链接全球任何地方的机器上的文件。

缺点：（1）需要额外的开销，必须读取包含路径的文件，然后要一个部分一个部分地扫描路径，直到找到 i 节点。这些操作也许需要很多次额外的磁盘访问。（2）每个符号链接都需要额外的 i 节点，以及额外的磁盘块用于存储路径。

• 两种链接的共同问题

8 多处理机

童话：2025 年 408 新增考点 - 多处理机调度总结与相关题目

计算机网络

1 概念

冷门点：在 OSI/RM 的七层模型中，数据传输过程中的加密和解密工作则主要是由 ( ) 完成的。 （表示层）
表示层: 向应用进程提供信息表示方式、对不同系统的表示法进行转换，使在采用不同表示方式的应用实体之间能进行通信，并提供标准的应用接口和公用通信服务，如数据加密、正文压缩等。

冷门点：PDU 和 SD
对等层次之间传送的数据单位称为该层的协议数据单元 PDU；层与层之间交换的数据的单位称为服务数据单元 SDU。多个 SDU 合成为一个 PDU, 也可以是一个 SDU 划分为几个 PDU。

2 物理层

易错点：指明某条线上出现的某一电平的电压的意义是功能特性，而不是电气特性，电气特性是指明在接口电缆的各条线上出现的电压的范围

易错点：bps 比特 / 秒 baud 码元 / 秒（波特率）

冷门点：（谢希仁 p54）
（1）对于给定的调制方式和数据率，信噪比越大，误码率就越低。
（2）对于同样的信噪比，具有更高数据率的调制技术的误码率也更高。

**冷门点：格雷码，**任意两个相邻码元只有一个比特不同

冷门点：奇偶校验码

冷门点：海明校验码

3 数据链路层

共享信道概念

易错点：“无比特差错”与 “无传输差错” 不是同样的概念，采用 CRC 检验后，数据链路层的传输并非变成了可靠的传输。例如，在数据链路层使用 CRC 检验，能够实现无比特差错的传输，但这还不是可靠传输，因为只保证收到的帧并没有出现比特差错，但可能出现帧丢失、帧重复或帧失序等情况。

冷门点：适配器（网卡），计算机与外界局域网的连接是通过适配器 (adapter)，其重要功能是进行数据串行传输和并行传输的转换，适配器和局域网之间的通信是通过电缆或双绞线以串行传输方式进行的，而适配器和计算机之间的通信则是通过计算机主板上的 IO 总线以并行传输方式进行的。
（1）适配器在接收和发送各种帧时，不使用计算机的 CPU，这时计算机中的 CPU 可以处理其他任务。
（2）适配器收到有差错的帧时，就把这个帧直接丢弃而不必通知计算机。
（3）适配器收到正确的帧时，它就使用中断来通知该计算机，并交付协议栈中的网络层
（4）当计算机要发送 IP 数据报时，就由协议栈把 IP 数据报向下交给适配器，组装成帧后发送到局域网。

冷门点：计算机的硬件地址（mac）在适配器的 ROM 中，IP 地址在计算机的存储器中。

• CSMA/CD
  （1）使用 CSMA/CD 协议的以太网不可能进行全双工通信，只能进行半双工通信。例如！！使用集线器的以太网在逻辑上仍是一个总线网，各站共享逻辑上的总线，使用的还是 CSMA/CD 协议；而使用交换机的以太网可以不需要碰撞检测。因为以太网交换机具有并行性，即能同时连通多对端口，使多对主机能同时通信，相互通信的主机都独占传输媒体，无碰撞地传输数据。

  （2）接上面例子，既然连以太网的重要协议 CSMA/CD 都不使用 (相关的“争用期” 也没有了)，为什么还叫作以太网? 因为它的帧结构未改变，仍然采用以太网的帧结构。

  （3）强化碰撞，当发送数据的站一旦发现发生了碰撞时，除立即停止发送数据外，还要再继续发送 32 比特或 48 比特的人为干扰信号，以便让所有用户都知道现在已经发生了碰撞。在计算时，整个信道被占用的时间还要增加一个单程端到端的传播时延。

  （4）**以太网还规定了帧间最小间隔为 9.6us，**相当于 96 比特时间。这样做是为了使刚刚收到数据帧的站的接收缓存来得及清理，做好接收下一的准备。

  （5）集线器工作在物理层，只进行简单地比特转发，不进行碰撞检测

• 802.11 无线局域网
  （1）802.11 的 MAC 层包括两个子层，分布协调功能 DCF 和点协调功能 PCF
  分布协调功能 DCF：DCF 不采用任何中心控制，而是在每一个节点使用 CSMA 机制的分布式接入算法，让各个站通过争用信道来获取发送权。802.11 标准规定，所有的实现都必须有 DCF 功能。为此定义了两个非常重要的时间间隔，即短帧间间隔 SIFS 和分布协调功能帧间间隔 DIFS

  点协调功能 PCF：PCF 是选项，是用接入点 AP 集中空制整个 BSS 内的活动，因此自组网络就没有 PCF 子层。PCF 使用集中控制的接入算法，日类似于探询的方法把发送数据权轮流交给各个站，从而避免了碰撞的产生。对于时间敏感内业务，如分组话音，就应使用提供无争用服务的点协调功能 PCF。

（2）为了方便记忆，将 Wi-Fi 4 /5 /6 作为 802.11n/ac/ax 的别名，而下一代是 802.11be

（3）802.11 有三种帧格式：数据帧、控制帧（例如 ACK、RTS）、管理帧（例如信标帧、关联请求帧）

（4）数据帧地址记忆口诀 地址 1: 此次传送给谁？ 地址 2: 此次是谁发出来的？ 地址 3: 剩下那个 mac 地址

• CSMA/CA
  （1）CSMA/CA 不需要返回确认帧，如果知道是否发送失败？通过电压信号检测
  同上，无线局域网的 Mac 帧不需要帧定界符，是因为以太网使用的曼彻斯特编码，中间会有电压跳变，如果没有电压变化就说明帧结束了，不需要帧定界符。

  （2）CSMA/CA 虽然叫碰撞避免，但是实际上是减少碰撞

  （3）为了减少碰撞，802.11 标准规定了每个站必须同时使用以下的两个方法
  用软件实现的虚拟载波监听 (VirtualCarrier Sense) 的机制：这就是让源站 A 把要占用信道的时间 (即 DATA+SIFS+ACK)，以微秒为单位，写在数据帧 DATA 的首部中持续期字段。所有处在站点 A 的广播范围内的各站都能够收到这一信息，并创建自己的网络分配向量 NAV(Network Allocation Vector)。NAV 指出了信道忙的持续时间，意思是:“A 和 B 以外的站点都不能在这段时间发送数据”。
  若进行信道预约，因为 RTS 帧和 CTS 帧也携带占用信道的时间，也属于虚拟载波监听机制，站点只要监听到数据帧、RTS 帧或 CTS 帧中的任何一个，就能知道信道将被占用的持续时间，而不需要真正监听到信道上的信号，因此虚拟载波监听机制能减少隐蔽站带来的碰撞问题。

在物理层用硬件实现载波监听：每个站检查收到的信号强度是否超过一定的门限数值，用此判断是否有其他移动站在信道上发送数据。任何站要发送数据之前，必须监听信道。只要监听到信道忙，就不能发送数据。
（4）协议 CSMA/CA 规定，所有推迟接入的站，都必须在争用期执行统一的退避算法开始公平地争用信道。

**争用期，**也叫作争用窗口组成。例如，争用窗口 CW = 15 表示窗口大小是 15 个时隙。时隙长度是这样确定的: 在下一个时隙开始时，每个站点都能检测出在前一个时隙开始时信道是否忙。时隙的长短在不同 802.11 标准中可以有不同数值。（退避算法与 CSMA/CD 略微不同，**第五次及以上重传后，争用窗口不在增加；**退避算法的公式也没有统一公式）

在以下几种情况下，发送数据必须经过争用期的公平竞争:
(1) 要发送数据时检测到信道忙 。 (2) 已发出的数据帧未收到确认，重传数据帧。(3) 接着发送后续的数据帧。

• 交换机：
  （1）一个 10Mbit/s 以太网若工作在全双工（交换机）状态，那么其数据率是发送和接收各为 10Mbit/s，而在半双工模式下，设备的发送速率和接收速率并不是固定的 5Mbit/s，而是根据网络上的实际数据传输情况动态变化的。
  （2）为了解决交换机在自学习过程中兜圈子问题，IEEE 的 802.1D 标准制定了一个生成树协议 STP。其要点就是不改变网络的实际拓扑，但在逻辑上则切断某些链路，使得从一台主机到所有其他主机的路径是无环路的树状结构，从而消除了兜圈子现象。
  （3）直通式交换机只检查 mac 地址，与存储转发交换机区别
  （4）VLAN 标签的使用
  ①A→B：假定 A 向 B 发送帧，由于交换机 能够根据帧首部的目的 MAC 地址，识别 B 属于本交换机管理的 VLAN-10，因此就像在普通以太网中那样直接进行帧的转发，不需要使用 VLAN 标签。
  ②A→E，交换机 查到 E 并没有连接到本交换机，因此必须从汇聚链路把帧转发到交换机，但在转发之前，要插入 VLAN 标签。不插入 VLAN 标签，交换机 就不知道应把帧转发给哪一个 VLAN。因此在汇聚链路传送的帧是 802.1Q 帧。交换机 在向 E 转发帧之前，要拿走已插入的 VLAN 标签，因此 E 收到的帧就是 A 发送的标准以太网帧，而不是 802.1Q 帧
  ③A→C，A 和 C 都连接到同一个交换机，但它们已经处在不同的网络中，由属于上面的网络层中的路由器来解决

（5）交换机的自学习
转发机制为：检查目的 MAC 地址，然后到地址表中查找，如果有匹配项，则按照表项中的端口号进行转发；如果没有，则转发到除进口之外的其他所有端口。而收到的端口，如果目的地址不匹配将丢弃此帧。
（例如 A 先向 B 发送一帧，从端口 1 进入到交换机。交换机收到帧后，先查找交换表，假设表中没有 B 的地址。于是，交换机把此帧的源地址 A 和端口 1 写入交换表中，并向除端口 1 以外的**所有端口广播这个帧。**广播发送可以保证让 B 收到这个帧，而 C 和 D 在收到帧后，因目的地址不匹配将丢弃此帧。）

冷门点：10BASE-T 中的 “10” 代表这种以太网具有 10Mbits 的数据率，BASE 表示连接线上的信号是基带信号，T 代表双绞线 (Twisted-pair)。同理 100BASE-FX 中 FX 代表光纤
冷门点：吉比特以太网允许在 1Gbit/s 下以全双工和半双工两种方式工作。工作在全双工方式时, 不使用载波延伸和分组突发。

冷门点：CIDR 的三个特殊地址块，其中 n=31 可用于点对点链路，如两个路由器相连，但现在也不常常分配 IP 地址，这类特殊网络也叫无编号网络或匿名网络

• PPP 协议
  （1）同步传输：采用零比特填充；异步传输：字节填充
  （2）使用字节填充时，当信息字段中出现和标志字段一样的比特 (0x7E) 组合时，就必须采取一些措施，使这种形式上和标志字段一样的比特组合不出现在信息字段中。当 PPP 使用异步传输时，它把转义符定义为 0x7D(即 01111101）

填充方法:**0x7D 后面的字节与 0x20 异或，**0x20 因为是 ASCll 码的空格，异或后不会跟控制字符冲突。
界定符 0x7E⇒0x7D +0x5E
转义符 0x7D⇒0x7D+ 0x5D
ASCII 码控制符（数值小于 0x20 的字符）⇒0x7D + 字符加上 0x20（也就是异或 0x20）
例如 0x86 无需处理，0x03，需要转为 0x7D 0x23

一些 QA：

4 IP 协议

MAC 地址是数据链路层使用的地址，而 IP 地址是网络层和以上各层使用的地址，是一种逻辑地址 (称 IP 地址为逻辑地址是因为 IP 地址是用软件实现的)

为什么不直接使用 MAC 地址进行通信? 由于全世界存在着各式各样的网络，它们使用不同的 MAC 地址。要使这些异构网络能够互相通信就必须进行非常复杂的 MAC 地址转换工作，因此由用户或用户主机来完成 这项工作几乎是不可能的事。即使是对分布在全世界的以太网 MAC 地址进行寻址，也是极其困难的。然而 IP 编址把这个复杂问题解决了

• ICMP 报文

• DHCP
  注意点：
  （1）每个报文的源 IP 地址和目的 IP 地址

  （2）除了基本的 DHCP 发现、提供、请求、确认报文，还有 DHCP 释放报文、DHCP 谢绝报文
  **DHCP 谢绝（DECLINE）报文：由客户端发送。**在使用租用到的 IP 之前（DHCP ACK 之后），客户端使用 ARP 检测所分配到的 IP 地址是否已被网络中其他主机占用。若被占用，给 DHCP 服务器发送 “DHCPDECLINE” 报文撤销 IP 地址租约，并重新发送 “DHCP DISCOVER” 报文。
  **DHCP 否认（NACK）报文：由服务器发送。**服务器不同意客户机延长租用期，则发出 DHCP 否认报文（见图）
  **DHCP 释放（RELEASE）报文：由客户端发送。**提前结束 DHCP 服务器提供的租用期。（见图）

  （3）DHCP 服务器未响应时，在 0.875 倍租用期客户必须重新发送。（见图）

  （4）路由器未配置 DHCP 中继代理时，会直接丢弃请求报文（路由器隔离广播域）；给路由器配置 DHCP 服务器 IP 地址后，使之成为 DHCP 中继代理，收到发现报文后会以单播形式发给服务器
  （5）IPv6 支持即插即用 (即自动配置)。因此 IPv6 不需要使用 DHCP。

• 路由选择协议

冷门点：最短路径优先（OSPF）协议是基于 Dijkstra 算法来计算网络中数据包的最优传输路径。

易错点：BGP 只能力求寻找一条能够到达目的网络且比较好的路由，而并非要寻找一条最佳路由。

冷门点：不同协议选择不同方式的原因，注意 RIP 和 BGP 属于应用层协议

冷门点：eBGP 和 iBGP 的概念。eBGP 是在不同 AS 的两个对等端之间的 BGP 连接，而 iBGP 是同一 AS 的两个对等端之间的 BGP 连接。可以理解为一个自治系统里面的路由器通过 iBGP 获取信息，而不同自治系统的路由器需要通过 eBGP 获取信息。

• IP 多播
  （1）多播数据报和一般的 IP 数据报的区别就是它使用 D 类 IP 地址作为目的地址，并且首部中的协议字段值是 2，表明使用网际组管理协议 IGMP
  （2）多播地址只能用于目的地址，而不能用于源地址
  （3）对多播数据报不产生 ICMP 差错报文。因此，若在 PING 命令后面键入多播地址，将永远不会收到响应 （4）以太网 MAC 地址字段中的第 1 字节的最低位为 1 时即为多播地址，但 IANA 只拿出 22 个地址，即 01-00-5E-00-00-00 到 01-00-5E-7F-FF-FF 的地址作为以太网多播地址
  （5）仅有 IGMP 协议是不能完成多播任务，还需要使用多播路由选择协议，和互联网上的其他多播路由器协同工作，以便把多播数据报用最小代价传送给所有的组成员。

  冷门点：IP 多播地址与多播 MAC 地址的**映射关系并不是唯一的，**因此收到多播数据报的主机，还要在 IP 层利用 IP 数据报首部的 IP 地址进行过滤，把不是本主机要接收的数据报丢弃。

易错点：多播转发必须动态地适应多播组成员的变化 (这时网络拓扑并未发生变化)，而单播路由选择通常在网络拓扑发生变化时才需要更新路由。 同时，多播数据报所经过的许多网络，也不一定非要有多播组成员，数据报可以由没有加入多播组的主机发出，也可以通过没有组成员接入的网络。

• IPV6

（1）IPV6 不使用 ARP 和 DHCP ，ARP 被新协议 ND 代替，DHCP 因为即插即用而不需要
（2）IPV6 删除了大部分 IPV4 的首部字段（具体部分见谢书 P150）
（3）IPv6 只允许在源点进行分片
（4）IPV6 地址的零压缩，（1）允许把数字前面的 0 省略，即一连串连续的零可以为一对冒号所取代（2）规定在任一地址中只能使用一次零压缩（也就是 “: :”）

一些 QA：

5.1 UDP

冷门点：ip 校验和 UDP 校验
IP 校验只检查 ip 数据报的首部；udp 需要加上伪首部，再与首部和数据部分一起校验（见末尾列举的题目）
（1）注意反码运算规则：按二进制加法进行，但是最高位产生进位加到结果的最低位
（2）伪首部的格式，其中协议字段的值
（3）ip 数据报每经过一个路由器，路由器都要重新计算一下首部检验和

5.2 TCP

易错点：tcp 三次握手的细节
（1）SYN=1 的报文段不能携带数据，但要消耗掉一个序号
（2）TCP 的标准规定，ACK 报文段可以携带数据，但如果不携带数据则不消耗序号。（也就是第三次握手可以分为携带数据和不携带数据，例如 TCP 连接建立过程中，若 A 发送第一个报文段序号为 x ，A 发送的第二个 TCP 报文段携带了 100B 的数据，则 TCP 连接建立成功后，A 发送的第一个 TCP 报文段序号应该为 x+101）
（3）服务器 B 发送给客户机 A 的报文段，也可拆成两个报文段。先发送一个确认报文 (ACK=1,ack=x+1)，然后再发送一个同步报文段 (SYN=1,seq=y)。这样的过程就变成了四报文握手，但效果是一样的。

冷门点：紧急指针在紧急 URG=1 时才有意义，它指出了紧急数据的末尾在报文段中的位置。值得注意的是，即使窗口为零时也可发送紧急数据。

冷门点：TCP 保活计时器，用于防止两端的 TCP 连接在长时间处于空闲状态时出现问题。TCP 包活计时器超时，服务器会向客户端发送一个探测报文段，这个报文段用于检测客户端是否仍然存活，如果服务器在发送了多个（通常是 10 个）探测报文段后仍然没有收到客户端的响应，服务器会认为客户端已经出现故障，并终止这个 TCP 连接。（补充：P174 BGP 协议那部分还有个保持时间计时器 (Hold Timer)。路由器每收到一个 BGP 报文，这个计时器就重置一次，继续从 0 开始计时。如果在商定的保持时间内没有收到对等端发来的任何一种 BGP 报文，就认为对方已经不能工作了）

冷门点：TCP 超时重传时间 RTO 的选择。网络是动态的，RTT 的大小也会动态变化，不能直接使用略大于某次测量得到的往返时间 RTT 样本的值作为超时重传时间 RTO，可以利用每次测量得到的 RTT 样本计算加权平均往返时间 RTTs，这样可以得到比较平滑的往返时间。为了解决超时重传会导致 RTT 的计算出现偏差，报文段每重传一次，就把 RTO 增大一些，典型的做法是将新 RTO 的值取为旧 RTO 的 2 倍 。

冷门点：拥塞控制算法分类，TCP 采用隐式反馈算法

以下为概念补充:

TCP 状态有限机

随着互联网的发展，TCP 首部又陆续增加了几个选项，如窗口扩大选项、时间戳选项、有关选择确认 (SACK) 选项等。这些选项的位置图中的选项字段中。例如窗口扩大选项，TCP 首部中窗口字段长度是 16 位，因此最大的窗口大小为 64KB， 窗口扩大选项占 3 字节，其中有一个字节表示移位值 S。新的窗口值等于 TCP 首部中的窗口位数从 16 增大到 (16+S)。移位值允许使用的最大值是 14，相当于窗口最大值增大到

6 应用层

冷门点：DNS 服务器的管辖范围不是以 “域” 为单位，而是以 “区” 为单位的。区是 DNS 服务器实际管辖的范围。区可能等于或小于域，但一定不能大于域。

冷门点：根域名服务器采用了任播 (anycast) 技术（任播的 IP 数据报的终点是一组在不同地点的主机，但具有相同的 IP 地址，IP 数据报交付离源点最近的一台主机）因此当 DNS 客户向某个根域名服务器的 IP 地址发出查询报文时，互联网上的路由器就能找到离这个 DNS 客户最近的一个根域名服务器。这样做不仅加快了 DNS 的查询过程，也更加合理地利用了互联网的资源

易错点：基于 TCP 的 FTP 和基于 **UDP 的简单文件传送协议 TFTP，**它们都属于文件共享协议中的一大类，即复制整个文件，其特点是: 若要存取一个文件，就必须先获得一个本地的文件副本。如果要修改文件，只能对文件的副本进行修改，然后再将修改后的文件副本传回到原节点。

冷门点：TELNET 是一个简单的远程终端协议。用户用 TELNET 就可在其所在地通过 TCP 连接注册 (即登录) 到远地的另一台主机上(使用主机名或 IP 地址)。TELNET 能将用户的击键传到远地主机，同时也能将远地主机的输出通过 TCP 连接返回到用户屏幕。这种服务是透明的，因为用户感觉到好像键盘和显示器是直接连在远地主机上的。因此，TELNET 又称为终端仿真协议

易错点：**协议 HTTP 本身是无连接的。**这就是说虽然 HTTP 使用了 TCP 连接，但通信的双方在交换 HTTP 报文之前不需要先建立 HTTP 连接。**协议 HTTP 是无状态的，**也就是说，同一个客户第二次访问同一个服务器上的页面时，服务器的响应与第一次被访问时的相同 (假定现在服务器还没有把该页面更新) 因为服务器并不记得曾经访问过的这个客户，也不记得为该客户曾经服务过多少次。HTTP 的无状态特性简化了服务器的设计，使服务器更容易支持大量并发的 HTTP 请求。

冷门点：SMTP 不使用中间的邮件服务器。不管发送方和接收方的邮件服务器相隔有多远，不管在邮件传送过程中要经过多少个路由器，TCP 连接总是在发送方和接收方这两个邮件服务器之间直接建立。当接收方邮件服务器出故障而不能工作时，发送方邮件服务器只能等待一段时间后再尝试和该邮件服务器建立 TCP 连接，而不能先找一个中间的邮件服务器建立 TCP 连接。

易错点：在浏览器和互联网上的邮件服务器之间传送邮件时，仍然使用 HTTP 协议。但是在各邮件服务器之间传送邮件时，则仍然使用 SMTP 协议。

以下为概念补充

ESMTP：扩展简单邮件传输协议，它是在 SMTP 的基础上进行扩展的一种邮件传输协议。因为 SMTP 存在着一些缺点。例如，发送电子邮件不需要经过鉴别，方便了垃圾邮件的作者；又如，SMTP 本来就是为传送 ASCII 码而不是传送二进制数据设计的。虽然后来有了 MIME 可以传送二进制数据，但在传送非 ASCII 码的长报文时，在网络上的传输效率不高。而 ESMTP 增加了 SMTP 所没有的一些功能，使邮件的发送和接收过程更加灵活、安全和高效。

POP 和 IMAP 的应用场景：

• POP：（1）单一设备用户：对于那些主要或仅在一台设备上查看和管理电子邮件的用户，POP 是一个合适的选择。因为它将邮件下载到本地客户端，用户可以在没有网络连接的情况下阅读邮件，适合需要离线访问邮件的场景。（2）本地存储需求：当用户需要长期保存邮件，并希望将邮件存储在本地设备上以便于随时访问时，POP 协议也是一个不错的选择。特别是对于那些担心邮件服务器数据安全性或希望减少服务器存储压力的用户 （3）对同步要求不高：如果用户对在不同设备之间同步邮件状态（如已读 / 未读标记）的需求不高，POP 协议可以满足基本需求。然而，这意味着用户需要在每个设备上分别管理邮件，无法享受多设备同步的便利。
• IMAP：（1）多设备用户：对于那些需要在多个设备（如手机、平板电脑、电脑）上同步邮件状态的用户，IMAP 是首选协议。它支持多设备同步，确保用户无论在哪个设备上查看或处理邮件，都能保持一致的邮件状态。（2）实时邮件访问：IMAP 协议与服务器保持实时连接，使用户能够实时接收新邮件通知。这对于需要快速响应邮件的用户来说非常重要，特别是在商务或工作环境中。（3）团队协作：在团队协作环境中，IMAP 协议允许成员在不同设备上访问共享邮箱或文件夹，实现实时协作和沟通。团队成员可以互相看到已读和未读邮件，回复和转发消息，从而提高工作效率。（4）高级邮件管理：IMAP 提供了丰富的邮件管理功能，如文件夹创建、删除、重命名，以及邮件的移动、搜索等。这些功能使得用户能够更高效地组织和管理他们的邮件。

总结

一些题目

• udp 校验和的计算

• TCP 超时重传时间 RTO 的计算