2023年408真题第41~47题汇总解析

LYmatch

122人浏览 · 2026-10-15 16:36:06

LYmatch · 2026-10-15 16:36:06 发布

第41题（数据结构·图）

题目

已知有向图G采用邻接矩阵存储，类型定义如下：

typedef struct {
    int numVertices, numEdges;      // 图的顶点数和有向边数
    char VerticesList[MAXV];        // 顶点表
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

将图中出度大于入度的顶点称为K顶点。请设计算法 int printVertices(MGraph G)：对给定任意非空有向图G，输出G中所有K顶点，并返回K顶点的个数。

要求：

给出算法的设计思想。
根据算法思想，写出C/C++描述，并注释。

答案

算法设计思想： 遍历邻接矩阵，同时统计每个顶点的出度和入度；再遍历一次顶点表，输出所有出度大于入度的顶点，并计数返回。

C/C++代码：

int printVertices(MGraph G) {
    int n = G.numVertices;
    int outDeg[MAXV] = {0};   // 出度数组
    int inDeg[MAXV]  = {0};   // 入度数组
    int count = 0;            // K顶点个数

    // ① 一次双重扫描，同时统计出度和入度
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (G.Edge[i][j] != 0) {   // 存在弧 i → j
                outDeg[i]++;           // i 的出度加1
                inDeg[j]++;            // j 的入度加1
            }
        }
    }

    // ② 遍历顶点表，输出K顶点并计数
    for (int i = 0; i < n; i++) {
        if (outDeg[i] > inDeg[i]) {
            printf("%c ", G.VerticesList[i]);
            count++;
        }
    }

    return count;
}

复杂度： 时间O(n²)，空间O(n)。

详细解析

关键理解： 邻接矩阵中，第i行非零元素的个数就是顶点i的出度，第i列非零元素的个数就是顶点i的入度。一次双重循环即可同时统计出度和入度，无需分别扫行和扫列。

示例验证： 以题目给出的图为例，弧为 a→b、a→d、b→d、b→c、c→d。

顶点	出度	入度	出 > 入？
a	2	0	✓ K顶点
b	2	1	✓ K顶点
c	1	1	✗
d	0	3	✗

输出结果：a b，返回值为2。

常见失分点： 输出时误打印下标而非顶点名；未同时统计入度和出度导致重复扫描；返回值逻辑错误。

涉及知识点详解

知识点1：图的邻接矩阵存储

邻接矩阵是用一个二维数组 Edge[i][j] 表示顶点之间相邻关系的存储结构。

有向图： Edge[i][j] = 1 表示存在弧 i→j；Edge[i][j] = 0 表示不存在。
无向图： 邻接矩阵是对称矩阵，Edge[i][j] = Edge[j][i]。
带权图： Edge[i][j] 存储权值，不存在边时用∞或0表示。

邻接矩阵的性质：

性质	说明
空间复杂度	O(n²)，适合稠密图
判断两点是否相邻	O(1)
求某顶点所有邻接点	O(n)
第i行非零元素个数	有向图中为顶点i的出度
第i列非零元素个数	有向图中为顶点i的入度
无向图第i行非零元素个数	顶点i的度

知识点2：顶点的度（出度与入度）

无向图： 顶点v的度 = 与该顶点相关联的边数，记为TD(v)。所有顶点度之和 = 2×边数。
有向图：
- 出度OD(v)： 以v为起点的弧的数目。
- 入度ID(v)： 以v为终点的弧的数目。
- 度TD(v) = OD(v) + ID(v)。所有顶点出度之和 = 所有顶点入度之和 = 弧数。

第42题（数据结构·外部排序）

题目

对含有n(n>0)个记录的文件进行外部排序，采用置换-选择排序生成初始归并段时需要使用一个工作区，工作区中能保存m个记录。

(1) 若文件中有19个记录，关键字依次为 51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100，当m=4时，可以生成几个初始归并段？各是什么？

(2) 对任意的m (n≫m>0)，生成的第一个初始归并段的长度最大值和最小值分别是多少？

答案

(1) 共生成 3个初始归并段：

归并段	关键字序列	长度
第1段	14, 37, 51, 63, 94, 99	6
第2段	15, 23, 31, 48, 56, 60, 90, 166	8
第3段	8, 17, 43, 100	4

(2) 首段长度最大值 = n，最小值 = m。

详细解析

置换-选择排序原理

置换-选择排序的核心思想是利用内存工作区（通常实现为最小堆）不断选择当前可输出的最小记录，同时从输入文件读入新记录进行"置换"，从而生成比工作区容量更长的有序归并段。

关键规则： 每次从堆顶输出最小元素后，读入一个新记录替换该位置。若新记录的关键字 ≥ 当前归并段已输出的最大关键字，则它属于当前归并段；若 < 当前归并段已输出的最大关键字，则它不能加入当前归并段，需标记为下一归并段的记录，但仍暂存在工作区中。当工作区中所有记录都被标记为"下一归并段"时，当前归并段结束。

第(1)问逐步模拟

初始工作区读入前4个记录，构建最小堆。

初始状态： 工作区：14, 37, 51, 94；待读入：63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100

生成归并段1：

步骤	输出	max	读入	工作区状态	判断
1	14	14	63	37, 51, 94, 63	63 ≥ 14，可加入
2	37	37	15	51, 94, 63, 15	15 < 37，标记为下一段
3	51	51	99	94, 63, 15(标记), 99	99 ≥ 51，可加入
4	63	63	48	94, 99, 15(标记), 48	48 < 63，标记为下一段
5	94	94	56	99, 15, 48, 56	56 < 94，标记为下一段
6	99	99	23	15, 48, 56, 23	23 < 99，标记为下一段

工作区中所有元素均被标记，归并段1结束 = {14, 37, 51, 63, 94, 99}（长度6）。

生成归并段2： 工作区重置为 15, 23, 48, 56；待读入：60, 31, 17, 43, 8, 90, 166, 100

步骤	输出	max	读入	判断
1	15	15	60	60 ≥ 15，可加入
2	23	23	31	31 ≥ 23，可加入
3	31	31	17	17 < 31，标记为下一段
4	48	48	43	43 < 48，标记为下一段
5	56	56	8	8 < 56，标记为下一段
6	60	60	90	90 ≥ 60，可加入
7	90	90	166	166 ≥ 90，可加入
8	166	166	100	100 < 166，标记为下一段

归并段2 = {15, 23, 31, 48, 56, 60, 90, 166}（长度8）。

归并段3： 工作区剩余 8, 17, 43, 100，依次输出。归并段3 = {8, 17, 43, 100}（长度4）。

第(2)问理论边界

最大值 = n： 当输入文件的关键字序列已经有序时，每次读入的新记录都 ≥ 当前归并段的最大关键字，所有n个记录都进入同一个归并段。
最小值 = m： 当输入文件的关键字序列严格递减时，每次读入的新记录都小于当前已输出的最大关键字，初始工作区的m个记录输出完毕后立即触发归并段切换。

涉及知识点详解

知识点1：外部排序

外部排序是指待排序的记录数量很大，无法一次性全部装入内存，需要在内存和外存之间多次交换数据才能完成的排序。

外部排序的两个阶段：

生成初始归并段： 将文件分成若干段，每段装入内存排序后写回外存，形成有序的初始归并段。
多路归并： 将多个初始归并段逐步合并，最终得到全局有序文件。

优化方向：

增加归并路数k → 减少归并趟数 → 减少I/O次数（但k过大时内部归并开销增加）。
减小初始归并段数量 → 使用置换-选择排序。

知识点2：置换-选择排序

置换-选择排序是一种生成初始归并段的算法，其核心优势是生成的初始归并段长度可以超过工作区容量。

算法步骤：

从输入文件读入m个记录到工作区，建最小堆。
输出堆顶最小记录，记为MIN。
从输入文件读入下一个记录R：
- 若R ≥ MIN，则R可加入当前归并段，替换堆顶后调整堆。
- 若R < MIN，则R不能加入当前归并段，标记为"下一段"，暂存工作区。
重复步骤2~3，直到工作区中所有记录都被标记为"下一段"。
当前归并段结束，清除标记，重新建堆，开始下一段。

平均归并段长度： 约为工作区容量的2倍（当输入随机排列时）。

时间复杂度： O(n log m)，空间复杂度O(m)。

第43题（计算机组成原理·虚拟存储与Cache）

题目

计算机M字长32位，按字节编址，采用请求调页的虚拟存储管理方式，虚拟地址32位，页面大小4KB。数据Cache采用4路组相联映射，主存块大小32B，Cache数据区大小8KB。C语言程序段包含一个二维数组 int a[24][64]，数组首地址为 0042 2000H，数组按行优先存储，每个int占4B。执行前数组a不在主存中。

for (i = 0; i < 24; i++)
    for (j = 0; j < 64; j++)
        sum += a[i][j];

(1) 数组a分为几个页面存储？访问数组a会发生几次缺页异常？页故障地址各是什么？

(2) 该程序段对数组a的访问是否具有时间局部性？

(3) 虚拟地址中哪几位用作块内地址？哪几位用作Cache组号？a[1][0] 的虚拟地址是什么？对应的Cache组号是多少？

(4) 数组a占用多少个主存块？在按行、按列两种循环顺序下，数组a的Cache命中率分别是多少？

答案

问题	答案
(1) 页面数	2个页面
(1) 缺页次数	2次
(1) 页故障地址	`0042 2000H`、`0042 3000H`
(2) 时间局部性	不具备，每个元素仅访问一次
(3) 块内地址位	A₄~A₀
(3) Cache组号位	A₁₀~A₅
(3) `a[1][0]` 虚拟地址	`0042 2100H`
(3) `a[1][0]` Cache组号	8
(4) 主存块数	192块
(4) 按行命中率	87.5%
(4) 按列命中率	87.5%

详细解析

第(1)问：页面分布与缺页

数组a共 (24 \times 64 = 1536) 个元素，每个int占4B，总大小 = (1536 \times 4 = 6144\text{B} = 6\text{KB})。

页面大小4KB，6KB需要 (\lceil 6/4 \rceil = 2) 个页面。首地址 0042 2000H 页内偏移为0，恰好是页面起始地址。第一页存放前4KB，第二页存放剩余2KB。

执行前数组a不在主存，因此发生2次缺页异常：

第一次：访问数组起始位置，页故障地址 = 0042 2000H
第二次：跨越到第二页，页故障地址 = 0042 3000H（第一页起始地址 + 4KB）

第(2)问：时间局部性

不具备时间局部性。 时间局部性是指一个内存位置被访问后，在不久的将来可能会被再次访问。本程序段中，每个数组元素 a[i][j] 在整个循环过程中仅被访问一次，不存在重复访问同一元素的情况。

第(3)问：地址划分与组号

① 块内地址： 主存块大小32B = (2^5)B，按字节编址，块内地址需要低5位，即 A₄~A₀。

② Cache组号： Cache数据区8KB，4路组相联，主存块32B：

[
\text{组数} = \frac{8\text{KB}}{32\text{B} \times 4} = \frac{8192}{128} = 64 \text{ 组}
]

64组需要6位组号。块内地址占低5位，组号占接下来的6位，即 A₁₀~A₅。

③ a[1][0] 虚拟地址： 按行优先存储，a[1][0] 前面有 (1 \times 64 = 64) 个元素，偏移量 = (64 \times 4 = 256\text{B} = 100\text{H})。

[
\text{虚拟地址} = 0042\ 2000\text{H} + 100\text{H} = \mathbf{0042\ 2100\text{H}}
]

④ Cache组号： 将 0042 2100H 分解，组号位 A₁₀~A₅ = 01000（二进制）= 8。

第(4)问：主存块数与命中率

① 主存块数： (6144 / 32 = 192) 块。

② 按行访问命中率： 一个主存块32B可存放 (32/4 = 8) 个int元素。按行访问时元素连续存放，每访问一个主存块中的第一个元素时产生一次Cache缺失，随后该块内剩余7个元素均命中。

[
\text{命中率} = \frac{7}{8} = \mathbf{87.5%}
]

③ 按列访问命中率： Cache数据区8KB可容纳256个主存块（(8\text{KB}/32\text{B}=256)），而数组a仅占192个主存块，整个数组可以全部装入Cache。一旦数组被完全调入，按列访问时每个元素仍只访问一次，但每次访问时其所在主存块已在Cache中，因此命中率同样为87.5%。

关键点： Cache容量（8KB）大于数组总大小（6KB），不存在因容量不足导致的块替换冲突。

涉及知识点详解

知识点1：虚拟存储与请求调页

虚拟存储是将主存和辅存统一管理，为用户提供一个远大于实际主存容量的虚拟地址空间。

请求调页： 程序运行时只将当前需要的页面调入主存，访问到不在主存的页面时触发缺页异常，由操作系统将所需页面从辅存调入主存。

虚拟地址划分：

虚拟地址 = 虚页号 + 页内偏移
页内偏移位数 = (\log_2(\text{页面大小}))
虚页号位数 = 虚拟地址位数 - 页内偏移位数

缺页异常处理： CPU检测到缺页 → 保存现场 → 操作系统查找页面在辅存的位置 → 调入主存 → 更新页表 → 重新执行指令。

知识点2：Cache映射方式

映射方式	特点	地址划分	冲突情况
直接映射	每个主存块只能映射到唯一Cache行	标记+行号+块内地址	冲突最严重
全相联	主存块可映射到任意Cache行	标记+块内地址	无冲突，但比较器复杂
组相联	主存块映射到唯一组，组内任意行	标记+组号+块内地址	折中方案

组相联映射的地址划分：

[
\text{主存地址} = \text{标记} + \text{组号} + \text{块内地址}
]

块内地址位数 = (\log_2(\text{块大小}))
组号位数 = (\log_2(\text{组数}))
组数 = (\frac{\text{Cache数据区大小}}{\text{块大小} \times \text{路数}})
标记位数 = 主存地址位数 - 组号位数 - 块内地址位数

知识点3：局部性原理

时间局部性： 刚被访问过的数据很可能在不久的将来被再次访问（如循环变量）。
空间局部性： 刚被访问过的数据其相邻数据很可能在不久的将来被访问（如数组的顺序访问）。

知识点4：Cache命中率

[
\text{命中率} = \frac{\text{命中次数}}{\text{总访问次数}}
]

影响命中率的因素：

程序访问的局部性越好，命中率越高。
Cache容量越大，命中率越高。
块大小要适中：过大会减少块数，增加冲突；过小则无法充分利用空间局部性。
组相联路数越大，冲突越少，命中率越高。
替换算法（LRU、FIFO、随机）影响命中率。

第44题（计算机组成原理·指令系统）

题目

题43中C程序段在计算机M上的部分机器级代码如下：

1  00401072  C7 45 F8 00 00 00 00   mov [ebp-8], 0
2  00401079  EB 09                  jmp 00401084h
3  0040107B  8B 55 F8               mov eax, [ebp-8]
...
7  00401088  7D 32                  jge 004010bch
8  0040108A  C7 45 FC 00 00 00 00   mov [ebp-4], 0
...
19 004010AE  C7 84 82 00 20 42 00 0A 00 00 00   mov [ecx+edx*4+00422000h], 0Ah
20 ...

(1) 第20条指令的虚拟地址是多少？

(2) 第2条jmp和第7条jge都是跳转指令，操作码分别是EBH和7DH，跳转地址分别为00401084H、004010BCH，这两条指令都采用什么寻址方式？给出第2条指令jmp的跳转目标地址计算过程。

(3) 第19条mov指令的功能是"a[i][j]←10"，其中ecx和edx为寄存器名，00422000H是数组a的首地址，指令中源操作数采用什么寻址方式？已知edx中存放的是变量j，ecx中存放的是什么？根据该指令的机器码判断计算机M采用的是大端还是小端方式。

(4) 第一次执行第19条指令时，取指令过程中是否会发生缺页异常？为什么？

答案

小问	答案
(1)	第20条指令虚拟地址 = 004010B9H
(2)	均采用相对寻址；jmp目标地址 = 00401079H + 2H + 09H = 00401084H
(3)	源操作数：立即寻址；ecx中存放 i×256；小端方式
(4)	不会发生缺页异常，因为第1条和第19条指令位于同一页面（虚页号均为00401H）

详细解析

第(1)问：第20条指令地址

第19条指令地址为004010AEH，机器指令为 C7 84 82 00 20 42 00 0A 00 00 00，共11个字节。按字节编址：

[
004010AEH + 11 = \mathbf{004010B9H}
]

第(2)问：跳转指令寻址方式

寻址方式： 两条指令都采用相对寻址。

第2条jmp目标地址计算：

指令地址：00401079H
机器指令：EB 09H，EBH是操作码，09H是偏移量
指令长度：2字节
下一条指令地址：00401079H + 2H = 0040107BH
目标地址 = 下一条指令地址 + 偏移量 = 0040107BH + 09H = 00401084H

第(3)问：寻址方式与大小端

源操作数寻址方式： 立即寻址。源操作数是立即数0Ah（十进制10），直接出现在指令中。

ecx内容： 数组 int a[24][64]，每行64个int，每行占 (64 \times 4 = 256) 字节。目的操作数地址为 ecx + edx*4 + 00422000h，edx存放j，edx*4为元素内偏移。ecx对应第i行的起始偏移，即 i × 256。

大小端判断： 第19条指令机器码中立即数0Ah的编码为 0A 00 00 00，低位字节0A存放在低地址处，符合小端序规则。

第(4)问：缺页异常判断

第19条指令地址004010AEH，第1条指令地址00401072H。32位虚拟地址、4KB页面下：

第1条指令虚页号：00401072H >> 12 = 00401H
第19条指令虚页号：004010AEH >> 12 = 00401H

两者虚页号相同，位于同一页面。程序开始执行时第1条指令已被取指执行，说明该页面已调入主存，因此第一次执行第19条指令取指时不会发生缺页异常。

涉及知识点详解

知识点1：指令格式与指令长度

机器指令通常由操作码和地址码两部分组成。指令长度可以是固定长度或可变长度。

x86指令特点： 变长指令，长度1_{15字节。操作码占1}3字节，后跟ModR/M字节、SIB字节、位移量、立即数等。

计算下一条指令地址：

[
\text{下一条指令地址} = \text{当前指令地址} + \text{当前指令长度}
]

知识点2：寻址方式

寻址方式	含义	示例
立即寻址	操作数直接出现在指令中	`mov eax, 100`
寄存器寻址	操作数在寄存器中	`mov eax, ebx`
直接寻址	指令中给出操作数的内存地址	`mov eax, [1000H]`
间接寻址	指令中给出操作数地址的地址	`mov eax, [[1000H]]`
寄存器间接寻址	寄存器中存放操作数地址	`mov eax, [ebx]`
相对寻址	目标地址 = PC + 偏移量	`jmp 09H`
基址寻址	基址寄存器 + 偏移量	`mov eax, [ebx+8]`
变址寻址	变址寄存器 + 偏移量	`mov eax, [esi*4+100H]`
基址变址寻址	基址寄存器 + 变址寄存器×比例 + 偏移量	`mov [ecx+edx*4+00422000h], 0Ah`

相对寻址的目标地址计算：

[
\text{目标地址} = \text{下一条指令地址} + \text{偏移量}
]

其中，下一条指令地址 = 当前指令地址 + 指令长度。偏移量是有符号数，可为正（向前跳转）或负（向后跳转）。

知识点3：大端与小端

方式	规则	示例：0x12345678
大端	高位字节存放在低地址	12 34 56 78
小端	低位字节存放在低地址	78 56 34 12

判断方法： 观察多字节数据在内存中的存储顺序。若低位字节在低地址，则为小端；若高位字节在低地址，则为大端。

知识点4：虚拟地址到页号的转换

32位虚拟地址、4KB页面：

[
\text{虚页号} = \text{虚拟地址} \div 4096 = \text{虚拟地址的高20位}
]

即虚页号 = 虚拟地址 >> 12。

同一页面的判断： 若两个虚拟地址的高20位相同，则它们位于同一页面，共享同一个页表项和物理页面。

第45题（操作系统·进程同步与互斥）

题目

现要求学生使用swap指令和布尔型变量lock实现临界区互斥。lock为线程间共享的变量：值为TRUE时线程不能进入临界区，值为FALSE时线程能够进入临界区。某同学编写的伪代码如下：

bool lock = FALSE;
// ── 进入区 ──
bool key = TRUE;
if (key == TRUE)
    swap key, lock;         // 原子交换 key 和 lock 的值
// ── 临界区 ──
临界区;
// ── 退出区 ──
lock = TRUE;

交换两个变量值的函数 newSwap() 代码如下：

void newSwap(bool *a, bool *b) {
    bool temp = *a;
    *a = *b;
    *b = temp;
}

(1) 伪代码中哪些语句存在错误？将其改为正确的语句（不增加语句条数）。

(2) 函数 newSwap() 是否可以用函数调用语句 newSwap(&key, &lock) 代替指令 swap key, lock 以实现临界区的互斥？为什么？

答案

第(1)问

错误一：进入区使用了if而非while。

bool key = TRUE;
while (key == TRUE)    // if 改为 while
    swap key, lock;

错误二：退出区将lock设置为TRUE（应为FALSE）。

lock = FALSE;          // TRUE 改为 FALSE

修正后的完整代码：

bool lock = FALSE;
bool key = TRUE;
while (key == TRUE)
    swap key, lock;
// ── 临界区 ──
临界区;
// ── 退出区 ──
lock = FALSE;

第(2)问

不可以。 swap指令是原子操作，由硬件保证其执行过程不可被打断。而 newSwap() 函数由多条普通C语句组成，不是原子操作。在多线程并发环境下，newSwap() 的执行过程中可能发生线程切换，导致交换操作出现竞态条件，无法保证互斥的正确性。

详细解析

第(1)问：错误分析

错误一分析：

if语句只进行一次条件判断。如果lock为TRUE（临界区已被占用），多个线程可能同时执行到此处，都通过判断并执行swap操作，导致多个线程同时进入临界区。

改为 while 后，线程会持续检查key的值。执行 swap key, lock 后，key变为FALSE，lock变为TRUE，key不再为TRUE，线程退出循环，成功进入临界区。如果lock已为TRUE，swap后key仍为TRUE，线程继续忙等待。

错误二分析：

题目规定lock值为TRUE时线程不能进入临界区，值为FALSE时能够进入。线程退出临界区后应释放锁，即让lock变为FALSE。原代码将lock设为TRUE，会导致后续所有线程都无法进入临界区，造成死锁。

第(2)问：原子性分析

newSwap(&key, &lock) 的执行包含三步：

temp = *a（读key）
*a = *b（将lock写入key）
*b = temp（将原key写入lock）

如果线程A执行到第2步后发生线程切换，线程B也可能同时进入临界区，导致两个线程都认为自己获得了锁，互斥失效。只有硬件提供的原子swap指令才能保证整个交换过程一气呵成、不被中断。

涉及知识点详解

知识点1：临界区与互斥

临界区： 进程中访问临界资源的那段代码。

互斥： 同一时刻只允许一个进程进入临界区。

临界区互斥的四条原则：

空闲让进： 临界区空闲时，应允许一个进程进入。
忙则等待： 已有进程在临界区时，其他进程必须等待。
有限等待： 进程应在有限时间内进入临界区，避免饥饿。
让权等待： 进程不能进入临界区时，应释放CPU（但swap方案不满足此条）。

知识点2：原子操作与硬件指令

原子操作： 不可被中断的一个或一系列操作。硬件提供以下原子指令：

指令	功能
TestAndSet	原子地测试并设置标志
Swap	原子地交换两个变量的值
CompareAndSwap (CAS)	原子地比较并交换

swap指令实现互斥： 每个进程维护一个局部变量key，共享变量lock。进入区不断swap key和lock，直到key变为FALSE（表示获得了锁）。退出区将lock置为FALSE。

特点： 不满足"让权等待"原则，未获得锁的进程会忙等待（自旋），浪费CPU时间。适用于多处理器系统或临界区很短的情况。

知识点3：忙等待与自旋锁

忙等待： 进程在等待进入临界区时，持续执行循环检测，不释放CPU。

自旋锁： 基于忙等待的锁机制，适用于：

多处理器系统（一个CPU自旋时，其他CPU可继续工作）
临界区执行时间很短的情况

缺点： 单处理器系统中，自旋会浪费CPU时间；长时间等待会导致优先级反转问题。

第46题（操作系统·I/O管理与系统调用）

题目

进程P通过执行系统调用从键盘接收一个字符的输入，已知此过程中与进程P相关的操作包括：

① 将进程P插入就绪队列
② 将进程P插入阻塞队列
③ 将字符从键盘控制器读入系统缓冲区
④ 启动键盘中断处理程序
⑤ 进程P从系统调用返回
⑥ 用户在键盘上输入字符

(1) 按照正确的操作顺序，操作①的前一个和后一个操作分别是哪个？操作⑥的后一个操作是哪个？

(2) 在哪个操作之后CPU一定从进程P切换到其他进程？在哪个操作之后CPU调度程序才能选择进程P执行？

(3) 完成哪个操作的代码属于键盘驱动程序？

(4) 键盘中断处理程序执行时，进程P处于什么状态？CPU处于内核态还是用户态？

答案

第(1)问

操作①的前一个操作是 ③（将字符从键盘控制器读入系统缓冲区）
操作①的后一个操作是 ⑤（进程P从系统调用返回）
操作⑥的后一个操作是 ④（启动键盘中断处理程序）

完整正确顺序：② → ⑥ → ④ → ③ → ① → ⑤

第(2)问

CPU一定从进程P切换到其他进程：操作②（将进程P插入阻塞队列）之后
CPU调度程序才能选择进程P执行：操作①（将进程P插入就绪队列）之后

第(3)问

操作③（将字符从键盘控制器读入系统缓冲区） 的代码属于键盘驱动程序。

第(4)问

进程P处于 阻塞态
CPU处于 内核态

详细解析

第(1)问：操作顺序

② 将进程P插入阻塞队列： 进程P发起系统调用请求从键盘输入字符，但键盘尚无数据可读，操作系统将P设为阻塞态，插入阻塞队列，等待I/O完成。
⑥ 用户在键盘上输入字符： 用户在物理键盘上按键，产生输入事件。
④ 启动键盘中断处理程序： 键盘控制器检测到按键，向CPU发送中断信号，CPU响应中断，启动键盘中断处理程序。
③ 将字符从键盘控制器读入系统缓冲区： 键盘中断处理程序执行期间，将字符从硬件控制器读入系统缓冲区。
① 将进程P插入就绪队列： 字符读取完成后，操作系统唤醒等待该I/O的进程P，将其从阻塞队列移至就绪队列。
⑤ 进程P从系统调用返回： 进程P被调度执行后，从系统调用返回用户态，继续执行后续指令。

第(2)问：CPU切换与调度时机

操作②之后CPU一定切换： 进程P因等待键盘输入而被插入阻塞队列后，P无法继续执行，CPU必然进行上下文切换，转去执行就绪队列中的其他进程。

操作①之后调度程序才能选择P： 只有当进程P被移入就绪队列后，它才具备被CPU调度程序选中的条件。操作③时P仍处于阻塞态，调度程序无法选择它。

第(3)问：驱动程序的职责

设备驱动程序是操作系统内核中直接与硬件设备交互的模块。将字符从键盘控制器读入系统缓冲区，正是驱动程序的核心职责——完成硬件到内核缓冲区的数据传输。操作⑥是用户在物理键盘上的按键动作，属于硬件事件，不是驱动代码。

第(4)问：进程状态与CPU模式

键盘中断处理程序是内核代码，执行时CPU自然处于内核态。此时进程P正在等待I/O完成，已被插入阻塞队列，因此处于阻塞态。

涉及知识点详解

知识点1：系统调用

系统调用是操作系统提供给应用程序的接口，使应用程序能够请求操作系统内核的服务。

系统调用的执行过程：

用户程序执行系统调用指令（如 int 0x80 或 syscall），CPU从用户态切换到内核态。
内核根据系统调用号执行相应的服务例程。
服务完成后，CPU从内核态返回用户态，用户程序继续执行。

常见系统调用类型： 进程控制、文件操作、设备管理、信息维护、通信。

知识点2：进程状态转换

状态	含义
就绪态	进程已获得除CPU外的所有资源，等待调度
运行态	进程正在CPU上执行
阻塞态	进程等待某个事件（如I/O完成），即使CPU空闲也无法执行
创建态	进程正在被创建
终止态	进程正在被终止

状态转换：

就绪 → 运行：被调度程序选中
运行 → 就绪：时间片用完或被更高优先级进程抢占
运行 → 阻塞：请求I/O或等待事件
阻塞 → 就绪：等待的事件发生（如I/O完成）
运行 → 终止：进程结束

知识点3：中断与中断处理

中断： CPU在执行程序过程中，遇到某些紧急事件需要暂停当前程序，转去执行处理该事件的程序，处理完毕后再返回原程序继续执行。

中断处理过程：

中断请求：设备向CPU发送中断信号。
中断响应：CPU在当前指令执行完毕后，检查中断信号。
保护现场：保存当前程序的PC、寄存器等。
中断处理：执行中断服务程序。
恢复现场：恢复被中断程序的上下文。
中断返回：返回原程序继续执行。

中断处理程序运行在内核态。

知识点4：设备驱动程序

设备驱动程序是操作系统内核中负责控制硬件设备的模块，是硬件与操作系统之间的接口。

主要功能：

初始化设备
向设备发送命令
从设备读取数据
处理设备中断
管理设备缓冲区

驱动程序与中断处理程序的关系： 中断处理程序通常属于驱动程序的一部分，负责响应设备的中断请求，完成数据的读取或写入。

第47题（计算机网络·TCP与FTP）

题目

主机H登录FTP服务器后，向服务器上传一个大小为18000 B的文件F。假设H为传输F建立数据连接时，选择的初始序号为100，MSS = 1000 B，拥塞控制初始阈值 ssthresh = 4 MSS，RTT = 10 ms，忽略TCP段的传输时延。在F的传输过程中，H以MSS段向服务器发送数据，且始终没有错误、丢包和乱序。

(1) FTP的控制连接是持久的还是非持久的？FTP的数据连接是持久的还是非持久的？H登录FTP服务器时，建立的TCP连接是控制连接还是数据连接？

(2) H通过数据连接发送F时，F的第一个字节序号是多少？在断开数据连接的过程中，FTP服务器发送的第二次挥手的ACK序号是多少？

(3) F发送过程中，当H收到确认序号为2101的确认段时，H的拥塞窗口调整为多少？收到确认序号为7101的确认段时，H的拥塞窗口调整为多少？

(4) H从请求建立数据连接开始，到确认F已被服务器全部接收为止，至少需要多长时间？期间应用层数据的平均发送速率是多少？

答案

小问	答案
(1)	控制连接持久；数据连接非持久；登录时建立控制连接
(2)	F第一个字节序号 = 101；第二次挥手ACK序号 = 18102
(3)	确认序号2101时 cwnd = 3 MSS；确认序号7101时 cwnd = 5 MSS
(4)	至少 6 RTT = 60 ms；平均发送速率 ≈ 2.4 Mbps

详细解析

第(1)问：FTP连接性质

FTP协议使用两条独立的TCP连接：

连接类型	端口	建立时机	持久性
控制连接	21	客户端登录时建立	持久（整个会话期间保持）
数据连接	20（主动模式）	每次文件传输时临时新建	非持久（传完即关）

H登录服务器时，首先建立的是控制连接，用于发送用户名、密码等身份验证命令。控制连接在整个FTP会话期间一直保持，即使数据连接被大文件占满，用户仍能在控制连接上发送ABOR等紧急命令。

第(2)问：序号计算

① F的第一个字节序号： H选择的初始序号为100。三次握手中，SYN段消耗1个序号。因此数据连接建立后，第一个数据字节的序号 = 100 + 1 = 101。

② 第二次挥手的ACK序号：

H发送的最后一个数据字节序号 = 101 + 18000 - 1 = 18100
FIN段消耗1个序号，H的FIN段序号 = 18100 + 1 = 18101
FTP服务器第二次挥手的ACK序号 = 18101 + 1 = 18102

挥手次序	方向	报文	序号/确认号
第1次	H → S	FIN	seq = 18101
第2次	S → H	ACK	ack = 18102
第3次	S → H	FIN	seq = Y
第4次	H → S	ACK	ack = Y + 1

第(3)问：拥塞窗口调整

确认序号N的含义： N表示"对方已收到字节[101, N-1]"，期望下一个收到字节N。已收到字节数 = N - 101。

① 收到确认序号2101时： 已收到 (2101 - 101 = 2000) B = 2 MSS，即已收到2个ACK。

初始cwnd = 1 MSS
第1个ACK：cwnd = 1 + 1 = 2 MSS（慢启动）
第2个ACK：cwnd = 2 + 1 = 3 MSS（慢启动）

② 收到确认序号7101时： 已收到 (7101 - 101 = 7000) B = 7 MSS，即累计收到7个ACK。

收到第几个ACK	cwnd变化	阶段
第3个ACK	3 → 4 MSS	慢启动（达到ssthresh = 4 MSS）
第4个ACK	4 → 4.25 MSS	拥塞避免
第5个ACK	4.25 → 4.5 MSS	拥塞避免
第6个ACK	4.5 → 4.75 MSS	拥塞避免
第7个ACK	4.75 → 5 MSS	拥塞避免

第(4)问：总时间与平均速率

① 总时间计算：

RTT轮次	本轮cwnd	本轮发送段数	累计已发段数	状态
1	1 MSS	1	1	慢启动
2	2 MSS	2	3	慢启动
3	4 MSS	4	7	慢启动→拥塞避免
4	5 MSS	5	12	拥塞避免
5	6 MSS	6	18 ✓	拥塞避免，文件刚好发完

文件共18000 B ÷ 1000 B/MSS = 18个MSS段，在第5个RTT轮次刚好全部发出。

[
\text{总时间} = \text{建立连接（1 RTT）} + \text{数据传输（5 RTT）} = 6 \text{ RTT} = 6 \times 10 = \mathbf{60 \text{ ms}}
]

② 平均发送速率：

[
\text{平均速率} = \frac{18000 \times 8 \text{ b}}{0.06 \text{ s}} = 2.4 \times 10^6 \text{ b/s} = \mathbf{2.4 \text{ Mbps}}
]

涉及知识点详解

知识点1：FTP协议

FTP（文件传输协议） 是应用层协议，使用两条TCP连接：

控制连接（端口21）： 持久连接，传输命令和响应（USER、PASS、RETR、STOR、ABOR等）。
数据连接（端口20）： 非持久连接，每次文件传输时临时建立，传完即关。

FTP工作模式：

主动模式（PORT）： 服务器主动连接客户端的数据端口。
被动模式（PASV）： 客户端主动连接服务器的数据端口。

知识点2：TCP序号与确认号

序号（seq）： 本报文段所发送数据的第一个字节的序号。

确认号（ack）： 期望收到的下一个报文段的第一个字节的序号。

关键规则：

SYN段和FIN段各消耗1个序号（虽然不携带数据）。
普通数据段消耗的序号数 = 数据字节数。
确认号 = 已收到的最后一个字节序号 + 1。

三次握手序号变化：

客户端：SYN（seq = x）→ 服务器：SYN+ACK（seq = y, ack = x+1）→ 客户端：ACK（seq = x+1, ack = y+1）

四次挥手序号变化：

主动方：FIN（seq = u）→ 被动方：ACK（ack = u+1）→ 被动方：FIN（seq = v）→ 主动方：ACK（ack = v+1）

知识点3：TCP拥塞控制

TCP拥塞控制包含四个算法：

① 慢启动：

初始cwnd = 1 MSS。
每收到一个ACK，cwnd加1 MSS（指数增长）。
当cwnd ≥ ssthresh时，转入拥塞避免。

② 拥塞避免：

每经过一个RTT，cwnd加1 MSS（线性增长）。
具体实现：每收到一个ACK，cwnd加 (1/\text{cwnd}) MSS。

③ 快重传：

收到3个重复ACK时，立即重传丢失的报文段，不等超时。

④ 快恢复：

快重传后，ssthresh = cwnd/2，cwnd = ssthresh，进入拥塞避免。

cwnd变化曲线：

cwnd
 ^
 |        /|
 |      /  |
 |    /    |___________
 |  /                  |
 |/                    |
 +-------------------> 时间
   慢启动  拥塞避免

知识点4：RTT与传输时间

RTT（往返时间）： 从发送方发送数据到收到确认的时间。

总传输时间的组成：

建立连接时间（1 RTT）
数据传输时间（取决于cwnd增长和文件大小）
断开连接时间（通常忽略或额外计算）

计算要点： 逐轮追踪cwnd变化，确定文件在哪一轮发完，并加上最后一段的ACK返回时间。

总结

七道题知识点分布

题号	科目	核心知识点
41	数据结构	图的邻接矩阵存储、顶点度计算、算法设计
42	数据结构	外部排序、置换-选择排序、初始归并段生成
43	计算机组成原理	虚拟存储、请求调页、Cache组相联映射、命中率
44	计算机组成原理	指令格式、寻址方式、大小端、虚拟地址转换
45	操作系统	临界区互斥、swap原子指令、忙等待
46	操作系统	系统调用、进程状态转换、中断处理、设备驱动
47	计算机网络	FTP双连接、TCP序号、拥塞控制、传输时间计算

重点知识关联

虚拟存储与Cache的联合分析（第43题）： 虚拟地址 → 虚页号 + 页内偏移 → 物理地址 → 标记 + 组号 + 块内地址。需要同时理解页式管理和Cache映射两个层次的地址划分。

TCP序号与拥塞控制的联合计算（第47题）： 序号计算涉及SYN/FIN消耗序号；拥塞窗口增长涉及慢启动和拥塞避免的切换。两者结合，需要逐步追踪每个ACK对cwnd的影响。

原子操作与并发的本质（第45题）： swap指令的原子性由硬件保证，普通函数调用无法保证。这是理解自旋锁、互斥锁等同步机制的基础。

系统调用与中断处理的层次（第46题）： 用户程序 → 系统调用 → 内核 → 阻塞进程 → 硬件中断 → 驱动处理 → 唤醒进程 → 返回用户态。需要清晰区分硬件动作、驱动代码、内核调度三个层次。

openEuler 社区

openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构

更多推荐

深入探究C／C++中互斥量(锁)的实现原理

互斥量（mutex，mutual exclusion）看起来只是一个"能加锁、能解锁"的对象，很多教材也只讲到"锁住临界区就不会有竞争"。但真正理解它，需要回答三个层次的问题：语言标准给了什么契约，标准库在平台上调用了什么，操作系统又依赖哪些硬件能力。这三个层次混在一起，就会出现"锁就是一个布尔变量""加锁一定要进内核""自旋锁比互斥量快"之类的片面结论。标题里的 C/C++ 需要先澄清：C 语言

openEuler 社区

【操作系统-61】非连续管理方式-基本分页存储管理

基本分页存储管理是一种高效的内存管理方式，它通过将内存划分为固定大小的页面和页框，避免了传统内存分配方式中连续性要求带来的外部碎片问题。分页管理的优势在于灵活性和高效性，但它也面临内部碎片、页表管理和页面置换开销等问题。分页存储管理通常用于需要支持虚拟内存的操作系统中，并在多进程、内存需求变化较大的环境中表现优越。