发表时间：2024.01.01     作者：Jingyi     来源：ShoelessCai     阅读：206

这部分工作主要是直播真题大题的时候，有些知识点一知半解，需要找到外部 Reference。这里就是总揽地整理所有的外部 Reference，如果听众或者用户对于之前的知识点有好奇的话，可以进一步学习。

彻底搞懂系列之：ARP协议 点击

数据帧转发过程中IP地址及MAC地址的变化 点击

什么是地址解析协议ARP？ 点击

三态门（三态缓冲器）的工作原理 点击

操作系统——生产消费者问题 点击

关于ARP请求报文和ARP报文的源地址和目的地址 点击

以太网帧、IP数据报，各有MAC地址

cpu可直接处理外存上的信息吗？ 点击

什么是ARP？ 点击

计算机组成原理5-预测和冒险 点击

IP-prefix 某种 IP 策略 点击

Prefix 点击

关于报文的生命周期 TTL 点击

指令控制相关内容 点击

2012 关于抖动和驻留集 点击

2024.1.4

关于多体交叉存储

所谓的多体交叉存储，即主存组织形式。N体交叉存储，就是 N 条总线并行。题目当中经常出现“主存块”是什么意思？这是主存和 Cache 交互的基本单位，也可以理解为“颗粒”。

网上定义：其基本思想是在不提高存储器效率不扩展数据通路位数的前提下，通过存储芯片的交叉组织，提高cpu单位时间内访问的数据量，从而缓解快速的cpu与慢速的主存之间的速度差异。

Cache 是怎么组织的？ Cache 从物理形态上就是镶在 CPU 内部，称为“集成在CPU内部”。抽象上理解，就是每行的长度，一共多少行，来理解到物理地址。

Cache:即高速缓冲存储器，是位于CPU与主内存间的一种容量较小但速度很高的存储器。由于CPU的速度远高于主内存，CPU直接从内存中存取数据要等待一定时间周期，Cache中保存着CPU刚用过或循环使用的一部分数据，当CPU再次使用该部分数据时可从Cache中直接调用这样就减少了CPU的等待时间提高了系统的效率。Cache又分为级Cache(L1 Cache)和二级Cache(L2 Cache)，L1 Cache集成在CPU内部，L2 Cache早期一般是 焊在主板上 现在也都集成在CPU内部，常见的容量有 256KB 或 512KB L2 Cache。

BTW，主存的物理地址，只要组织形式变一变，就可以找到其在 Cache 上的位置。因此，Jingyi 总结为，主存地址和Cache地址是一回事。只不过拥有很好的二进制算法，使得按照某种方式编址，正好可以找到其对应 Cache 的位置。

关于存储周期

这里顺带提一下，主存如果是多体交叉存储的模式，存储周期怎么算？

答曰：仍然是一个存储周期，我指的是干完一个动作的时间。

存储周期：存储周期包含存取时间和恢复时间，指两次独立访问存储器操作之间的最小间隔。

参考：

多体交叉存储

Cache

存储周期 加深理解 牛客网

关于 Cache 分组

上述介绍多体交叉存储多为主存分为 N 个体，用 N 个总线连接。

但是，也发现 Cache 似乎也能分组，如果驻留集（进程已装入内存的页面的集合）大小为 10，则

关于 x86 你应该知道

x86 一些默认设置，经常会出现在 408 当中，当你解题的时候，你必须知道这些条件，不然很多题目是无法解开的。大家可以这么认为， 考 408 都是 Suppose 你对 x86 架构非常熟悉的 。

其一，二级页表映射；
其二，页面大小，2^12，即 4KB。

资料显示，映射表自身也是需保存在物理内存中的， x86 处理器使用了两级转换：页目录和页表。即每个任务(程序)都有自己的页目录和页表，页目录表的地址被记录在任务的 TSS 段中。



参考：关于二级页表映射

关于 I/O 和 CPU 交互

有几种算出每秒钟，要传送多少次 I/O 接口寄存器的数据。首先，I/O 传输速度一定是很快的，可能是 4MB/s，其次入口寄存器约为 4B。这个时候，传输一次入口寄存器数据的时间 4B / 4MB/s ，而每秒钟传输次数为 4MB/s / 4B。还有一种理解方式是，每秒钟 I/O 传送至入口数据是 4MB，而入口寄存器容量 4B，此时，每秒传输次数为 4MB / 4B = 10^6 次。

上述是依据做题总结得出的，主要聚焦于 I/O 中断的时间计算。有几大特点。

一是 I/O 输入时候一定涉及中断；
二是从 I/O 传至 CPU 每秒钟产生非常多的次数，取决于什么？取决于 I/O 设备传送至入口寄存器的速度。

参考：2009， 2010 408联考真题

关于比较器，什么是比较器？

比较器用于将请求的数据块地址与Cache中已存储的数据块地址进行比较，以判断所请求的数据是否已经在Cache中。这是关于比较器的作用，就是校验这件事，即“对应的组（列）找对了吗？”。

这里要注意，因为组内的行号，甚至是某个主存块内部的 Offset 都是可以一样的，就以组区分，每个组配置一个比较器，校验组是否找对。因此，只针对非唯一的部分，设置比较器校验。

那么，怎么通过示意图的比较器来推断“映射模式”呢？

机械地说，关于 Cache-主存映射，主存-外存映射，这类组织形式，有三种：

全相联映射，直接映射，组相联映射。其中，直接映射可以理解为“单路组相联”；全相联我们记一个口诀“全相联 不相交” —— 用图像的形式记住全相联模式。因此，上述三种映射模式，分别对应的比较器组 织：全相联映射是一行一个比较器；直接映射是只有一个比较器（待验证）；组相联映射，N组相联映射，则有N 个比较器。这里的组，也可以理解为“列”，有时候理解为“列”会更加容易一些。

关于比较器，还留有一些疑问

比较器有几位？

答曰：和 TAG 的位数是一致的。

为什么全相联是一行一个比较器？

答曰：全相联直接把主存内容复制进 cache ，相邻内容，cache 内部编号也是连续的，因此按行验证 tag。全相联针对主存内容比较大的情况，直接将主存里的内容，复制进 cache 。

直接映射模式下，映射到 Cache 的是同一个程序的内容吗？

答曰：取决于程序大小。这里涉及“为什么有几种映射方式？每次按照主存地址找到 Cache 的行号和块号，Cache 一定是空着的吗？”

主存中的每一块只能装入Cache 中的唯一位置。 若这个位置已有内容，则产生块冲突，原来的块将无条件地被替换出去（无须使用替换算法)。来源： 知乎

直接相联和组相联，主要功能是干嘛的？

答曰：主要功能即更多地更好地利用cache，因此，物理状态，不同的内容，放到 cache同一行。

是否存在“大内容用全相联，小内容用直接相联”？

答曰：？？？

针对不同映射模式，是一根总线一个比较器吗？

答曰：从线上公开资料看，比较器的比特应该无法同时传输。

关于捎带确认

捎带确认，piggybacking。当主机收到远程主机的TCP数据包之后，通常不马上发送ACK数据包，而是等上一个短暂的时间，如果这段时间里面主机还有发送到远程主机的TCP数据包，那么就把这个ACK数据包“捎带”着发送出去，把本来两个TCP数据包整合成一个发送。

信道利用率

1.发送周期 = RTT + 发送时延 + 确认帧发送时延

2.传输数据时间

3.信道利用率 = 传输数据时间 / 发送周期

针对遇到的题目，记得这种信道利用率求法。

已知发送帧的发送时延 t1

发送周期 T。 发送时延 = RT + 帧发送时延 + 确认帧发送时延

信道利用率 = t1 / T ，即 发送帧的发送时延 / 发送周期

参考： 操作系统-第5章习题解析

关于路由前缀、路由前缀表

首先，路由前缀，路由前缀 = IP地址 / 掩码。

再者，至于路由前缀表，这是再次汇总，直接配置前缀表给到路由器。

以下是从必应找到的答案：

前缀列表将若干CIDR地址块组成一个逻辑操作对象。 您可以为一些常用的IP地址创建前缀列表，并将其作为路由表的目标地址配置路由，而不需要为每个IP地址配置路由。 如果您需要扩展访问范围并要访问另外一个地址段（CIDR），则可以直接更新相关的前缀列表，引用该前缀列表的所有路由表都会自动更新。

个人理解，有比较器之后，就是按照聚合之后的前缀路由表分配路由器。

关于程序计数器

在x86体系里是这样。x86 系统中自增的是IP，用CS:IP 组合表示正在执行的指令地址Q，此时 PC只是一个概念上的说法。所以 【PC】 的内容未必是当前指令在内存中的绝对位置。

+1 是指增加一个概念中的单位。为了方便教学往往说 +1，实际上是增加 (一条指令的长度寻址粒度)，在MIPS中就是4，因为 MIPS一条指令长度4字节，寻址粒度Q是 1字节。而x86 体系的指令长度不定，所以每次增加的量会变化。

摘自：知乎

从做题的认知来说，Jingyi 通常把（PC）认为是指令长度。具体看移动到下一条指令的目标地址，与本指令的目标地址（注意，都是地址）的位移，除以指令机器数所含的 Offset，即 （PC）+ n。也就是上文的，位移除以颗粒度。

取址和间址一样吗？为什么可以重叠？

取址和间址，针对的区域不一样。取址是去指令地址，只针对指令所在存储区域，而间址是找数据段的内容，因此区域不会产生冲突。 点击获取参考

散列表，位置冲突，不命中两次，怎么计算比对次数？

题目：序列 = {7， 14， 8， 11， 30， 18， 9}

Hash(key) = (3*key) % 7



5号位置，11元素放入，计数=2；18元素比对，计数=3；18元素放入 7号位置，共计数 = 2+3 = 5

6号位置：30元素放入，计数=2；9元素比对， 计数=3；9元素放入 8号位置（8>7），共计数 = 2+3-1 = 4

参考：计算散列表查找成功和查找不成功的平均查找长度（利用线性探测 法处理冲突）

2024年2月15日更新

2024.1.6

2023年结束的时候有两件事情，一是和家里人聚了聚，算是才明白他们获取信息的方式。怎么说呢？如果是我的话，就问问，小姑娘，老大不小了老是一个人行动，不会被人说闲话吗？

有时候，挺简单的一件事情，遇到恻隐，就复杂了！

有人问，你还会像小时候那样灵敏吗？

Jingyi 会回答，会的。但是，随着学习的内容越来越复杂，很多人是无法想象其他人付出的努力的，如果你什么都不懂，那么，保持安静是个很稳妥的 —— 至少不能贬低懂行的，对吧？

闲话聊完，现在除了和猫、和狗说话，还有就是自我碎碎念，录课，以及不期回复的对话。我为自己的 2024 定一个目标，就是“顾及别人的感受”。如果别人不回复，那咱们就看看书，干点别的事情吧！

以下是本人整理 2009 - 2020年 408 考研真题，关乎大题目，我提出了一些疑问，我将其作为专题记录下来。部分知识点可能与之前会重复。

虚页号 = Tag + Index

在虚拟存储器中，逻辑地址/虚拟地址 = 页目录号 + 页号 + 页内偏移（Offset）。那么问题来了！

页目录号、页号都是拿来干嘛的呢？

答曰：页目录号、页号都是某种【位移】，用来计算【物理地址】的。

其中，页目录起始地址 + 页目录号 = 页号的页框号的物理地址；

这句话的含义是，【页目录起始地址 + 页目录号】是一个物理地址，该物理地址放置的是页框号，但是，这是页面的页框号吗？不是！这是页号的页框号。

然后，页号的页框号是某种起始地址，因此 页号的页框号 + 页号 = 页面的页框号的物理地址；

再一次，【页号的页框号 + 页号】是一个物理地址，该物理地址的内容，是页框号，并且是页面的页框号。

最后，页面的页框号，同样也是起始地址。页面的页框号 + 页面偏移 = 页面内容的物理地址；

这里的含义非常显然，这是个物理地址，其内容放的是页面内容。

进程 A 被 kill 之后再 start，页目录号、页表号的地址会变吗？

答曰：我的理解是这样的。

第一，进程的 Alive Proccess Set，变更一个进程，所有的起始地址就会变一次；

第二，如果 kill 一个进程，再启动一个进程，因此页目录起始地址、页表起始地址都会改变；

第三，但是，进程内线程切换的时候是不变的，起始地址都是不变的。

再一次提示自己，这属于虚拟内存的范畴，必然是内存和外存交互。

虚页号 = Tag + Index

页面数量 / 存储体个数 = 单元个数，该单元个数需要多少个 bit 覆盖？

需要多少 bit，则 Index 则为多少 bit。

如何理解“地址空间”？

答曰：即所在物理区域的长度。例如，主存地址空间40，则 主存大小 = 2^40 bit

报文出内网的时候，是怎样的？

第一，主机广播 ARP Request，以太网帧对方MAC全1，内部 ARP Request 目的MAC全0；

第二，网关路由器发现自己直接交付来的 Request，回复其自身的MAC；

第三，主机收到网关路由器的 MAC 地址，目的IP为目标主机的IP，目的MAC写得网关路由器 MAC，源IP写的自己内网IP，源MAC地址写的发出端口的 MAC。

第四，网关路由器接收到主机发来的报文，先修改源 MAC 和 目的 MAC，这两个指标，每经过一段物理链路都会变，因为物理传输的地址依据，是 MAC。再修改 源 IP 地址，称为 NAT 服务，具体操作就是维护一张表，内网 IP + 端口，对应 外网 IP + 端口。

第五，路由器和路由器之间传播的时候，只更改 MAC 地址（依据链路的端口），IP 地址都是不变的。

第六，报文传送到对方网络的网关路由器，路由器发现是自己直接交付的 目的IP，进行 NAT 服务。修改源 MAC 和目的 MAC，修正目的 IP，写的是目的主机内网的 IP 地址 + 端口。

第七，报文传送到目的主机。

CPU 性能衡量指标

以下 Jingyi 给出相应解题步骤，其实也可以称为如何理解题目的步骤。

计算 CPU 效率的步骤：

1.I/O 与主存之间每秒工作次数；
2.工作一次需要 N 条指令；
3.CPI （CPU 性能决定）
4.CPU 效率 = 事件 #CLOCK / CPU #CLOCK

每秒工作次数 = 1/（Q/v）= v/Q —— 可分开算或者套公式

三种映射方式

关于映射方式：全相联映射、直接映射（单路组）、组相联映射；

这些映射方式干嘛用的？

依据主存确定 Cache 地址的时候，未必你要找的块未被占用，如果被占用的话，直接替换。原因的话，主要是由于主存地址是无法更改的，因此，对应 Cache 就是唯一的地址映射。

关于比较器

这里映射，指的是 Cache - 主存之间的映射。如果是全相联模式，多少 Cache 行，连接多少个比较器；直接映射模式，只连接一个比较器；组相联映射，多少组，连接多少个比较器。

比较器的位数和 Tag 是一致的，一端接着电压，0-1 比特按照一定顺序，序贯地进入比较器并输出。

主存地址 v.s. Cache 地址

其实，大多数时候，主存地址和 Cache 地址是一致的，并且是先有主存地址，再有按照主存表示的比特，将信息输入 Cache 。

那么，万一按照主存地址，发现对应的块号已经被占用了怎么办？

直接换出，写命中还分【直写法】和【写回法】。408 对考生的要求是，针对 Cache 主存块的内容换出 Cache，写入主存的时候，要掌握四种算法。

随机算法，【FIFO，LRU，LFU（最近最少频率使用）】。其中，使用 LRU 的时候，最左边的 Tag 还要留一个脏位。

说到 Tag 再说一句，anyway 都会有一个有效位。

注意，数据或者指令的主存地址，由主存格局决定。

Cache 行号 = ( 1/Cache 行大小 ) * [ start_pos + i * 列数 * 4B + j * 4B ] % Cache 行数

这里涉及位置冲突问题，因此，如果冲突，则无条件换出原来的 Cache 内容。

IP 数据报分片

IP数据报分片，属于数据链路层。

以太网信道 MTU = 1500B，Maximum Transmission Unit。

在处理这类问题的时候，要注意 IP数据报【分片长度】必须是 8B 整数倍。

这一点在做题的时候很容易忘记，切记！

IEEE 802.11

这个知识点考得不多，但是考过。

IEEE 802.11 一共有 4 个地址 Slots，其中地址4 大多数时候是空着的。



Address 1 代表接收端， Address 2 代表传送端， Address 3 位被接收端拿来过虑地址。 点击获取信 息

Source Address（SA）：顾名思义，源地址，也就是帧的发送源
Destination Address（DA）：目的地址，也就是帧最终要发往的地方
Transmitter Address（TA）：传输地址，传输此帧的地址
Receiver Address（RA）：接收此帧的地址，不一定是最后的地址哦
Basic Service Set Identifier（BSSID）：AP的基础服务集ID，也就是vap的mac地址

从王道的习题来看，地址1 是网关路由器地址，地址2 是发送报文的主机的地址，地址3 是网关路由之后的链路地址，或者接收端端口所在的 IP地址。

关于 IEEE 802.11 更多信息 。

主存中的【程序段】是如何起作用的？

一条指令，对应一个主存地址，机器数显示的是指令的长度。

PC 的内容是指令长度，如果指令长度 16 位，按字节编址，则跳转下一跳地址的时候，(PC) = (PC)+2

回忆这样一道题目。

告诉你某条指令 A，内部有 Offset，此时你计算出 Offset = -6；

又由于是循环，跳转指令是向前跳转，位移 -24；

增加的步长 = -24 / -6 = 4，于是，(PC) = (PC)+4 ；

信道利用率

首先确定，信道利用的是数据链路层的指标。

信道利用率，通俗地说，是发送窗口（Slots）与最多能够承受的 Slots 个数之比。

对于 GBN 协议，发送窗口最多 2^n - 1，为啥要减 1 ？因为，要留一个窗口接受确认帧，不然的话，就会搞错。

最多能承受的 Slots 怎么计算？

首先，信道传输速度是有限的。

因此，一个帧来回一次的时间，即

发送周期 = 发送Delay + 接受确认帧Delay + RTT。

最多能承受的 Slots = 发送周期 / 发送Delay ；

故，信道利用率 = 发送窗口 / 最多能承受的 Slots ；

BTW，SR 协议 发送窗口最多 2^(n-1)。

RIP 协议

首先，RIP 协议、BGP 协议，是应用层的协议；OSPF 协议，是传输层的协议。

可以这样来记忆，即 OSPF 协议适用于大网络，所以是传输层的协议，Layer 更低级，能够铺的面更大。

其次，RIP 协议有【坏消息传得慢】特点。

例题，如果网络Internet，到路由器 1 断开，到路由器 2 还存在连接，路由器 3 和上述两个路由器均有连接。并且，路由器 2 的路由表如下：

目的网络 | 下一跳 | 接口
Internet | 2 | Internet接口

路由器 1 断开之后，路由器 2 是不知道的，路由器 2 会将上述记录更新给到路由器 3 。此时，路由器 3 记录如下：

目的网络 | 下一跳 | 接口
Internet | 3 | Internet接口

如果题目是这么问的，此时，路由器 3 中的路由表显示到 Internet 距离，回答为 3 —— 此时，和路由器 3 连接着的路由器 1 是断开的。

注意，这里的下一跳路由，指的是链路接收端端口所在的 IP 地址。

TTL

TTL: Time To Live

每经过一个路由器，TTL自动减少1。

路由器 Prefix

学习过程中，发现【Prefix】这个提法。首先，关于 Prefix 这个概念，指的就是 CIDR/MASK，关键在于 Prefix Table，分配路由器的时候，按照 Prefix Table，效率会高很多。

CPU 读突发传送总线事务

读突发传送总线事务时间 = 总线获取地址时间 + 主存工作时间 + 总线传输时间

读突发传送总线事务，是 CPU 获取 Cache 缺失的时候，触发的事件。

I/O 与主存交互

CPU 和 DMA 交互的时候，存储器总线宽度 32 位，平均每秒产生的缺页中断 1.5 次，页面大小 4KB。

因此，每秒钟与 DMA 交互的次数 = 1.5 * 4KB / 4B = 1.5 * 1024 = 1536 次数

如果给出速度，怎么理解题目？

例题：假设某外设的数据传输率 0.5MB/s，以中断方式与主存进行交互，以 32 位为传输单位，每次传输数据产生的时钟周期 100。

解：外设每秒申请的中断次数 = 0.5MB / 4B = 125000 次

每秒经过的时钟周期 = 100 * 125000 = 12.5M 个时钟周期

握手协议

1.SYN 是建立新连接时候产生的，seq 与 SYN 对应；

2.ACK 确认，ack 与 ACK 对应，ack=seq+1，seq 为前一次 seq 。

单总线 v.s. 双总线

单总线，在 ALU 两端输入的时候，一端要加一个暂存器，以便于两个数据同时输入；

双总线，无需增加暂存器，两条总线可以同时输入 ALU。

五段式指令 四体交叉存储

每个时钟周期都会有一条指令运行完毕，因此至少需要 5 + (4-1)*1 = 8个时钟周期。



关于 【取址 v.s. 间址】

取址：由 （PC）= (PC)+1；

范围是指令所在的区域，即程序段；

间址：由 CPU 依据地址获取相应内容；

范围是是数据段。

以太网

数据区域，最小长度为 46B；数据段不满这些字节，则填充；

最短帧长 = 64B

使用曼切斯特编码

MTU = 1500B

IP Header 一行 4 字节

IP Header 长度范围，20B - 60B

bit rate = MTU / 发送周期

散列表

设计表格：散列地址（位置） | 关键字（元素） | 比较次数

一定要将这三个要素放在一起比对！

长按/扫码，有您的支持，我们会更加努力！