HW3：从用户视角和内核视角理解内存管理¶
作业说明¶
- 本次作业内容涵盖部分往年期末考试中的典型题型，主要考察大家对课堂内存管理相关知识的理解与掌握。同时，部分题目会结合 NexOS 的具体实现，引导大家将理论知识应用到实际系统分析中。
- 实验相关的实现要求、代码路径和测试说明会在实验文档中单独介绍。
- 由于本次作业发布时，理论课可能尚未讲完第七章的全部内容，同学们可以先完成已经学习过的部分。
- 本次作业完成周期为 3 周，截止时间为 5 月 31 日 23:59 (周日)。
作业目标¶
通过完成本次作业，你需要进一步巩固以下内容：
- 虚拟内存与分页机制
- 用户态地址空间与
sbrk()堆边界变化 - 用户态堆块管理与空闲链表
- 页表查找与地址转换
- TLB 对地址转换性能的影响
- 请求分页与 page fault 的性能开销
- 页面置换算法
- 抖动（thrashing）的产生原因与影响
作业题¶
题目 1：用户态地址空间与 sbrk()¶
参考 Nexos 内核中的实现，p->sz 表示当前进程用户地址空间的大小，单位为字节，也就是当前堆顶之后的第一个地址；它不一定正好落在页边界上。sbrk 系统调用（sys_sbrk()）会先保存旧的 p->sz 作为返回值，再调用 growproc(n) 将 p->sz 调整为 p->sz + n。实际是否分配或释放用户页，不是直接由 n 对应多少字节决定，而是由新旧 p->sz 经过 PGROUNDUP() 后是否跨过页边界决定。
其中，n > 0 时通过 uvmalloc() 增加用户空间大小，n < 0 时通过 uvmdealloc() 减少用户空间大小。本题中的 6000 和 3000 均为十进制字节数，不是十六进制。
页大小为 4KB，即 PGSIZE = 0x1000。
假设不考虑执行失败和超过用户地址上限的情况。某进程当前的地址空间上界为 p->sz = 0x5000，随后用户程序依次执行：
请回答下面的问题：
- 一个用户进程的地址空间通常包含哪些主要区域？
sbrk()主要影响其中哪一部分？ - 两次
sbrk()的返回值分别是多少？每次调用后新的p->sz分别是多少？ - 两次调用分别需要新分配或释放哪些用户页？请列出相关用户虚拟页的起始地址，并简要说明计算过程。
题目 2：用户态堆块分裂与空闲链表合并¶
malloc() / free() 通常在用户态维护堆块和空闲链表。假设堆块大小只包含 header 和 payload（注意没有footer），并采用如下规则：
HEADER = 0x10，ALIGN = 0x10，MIN_FREE_BLOCK = 0x20；malloc(n)的needed = ALIGN_UP(n + HEADER, ALIGN)，采用 first-fit，剩余空间不小于MIN_FREE_BLOCK时分裂；malloc()返回block_start + HEADER，free(ptr)释放ptr - HEADER，释放后按地址顺序插入并合并相邻空闲块。
假设当前堆空间范围为：
初始堆块布局如下，其中空闲链表为 0x1080(0x60) -> 0x1170(0x70)：
| 块名 | 起始地址 | 块大小 | 状态 | 说明 |
|---|---|---|---|---|
| A | 0x1000 |
0x80 |
allocated | - |
| B | 0x1080 |
0x60 |
free | 空闲块 F1 |
| C | 0x10e0 |
0x90 |
allocated | 指针对应 p2 = 0x10f0 |
| D | 0x1170 |
0x70 |
free | 空闲块 F2 |
| E | 0x11e0 |
0x60 |
allocated | - |
随后依次执行(注意其中的数字40为十进制字节数，不是十六进制)：
请回答：
- 计算
malloc(40)的needed和返回值，并说明是否发生空闲块分裂。 - 写出
free(p2)后是否发生合并，以及最终空闲链表。
题目 3：基本概念解释¶
请解释下列内存管理相关概念：
- Segmentation fault（段错误）
- TLB（Translation Lookaside Buffer，地址转换后备缓冲）
- Page fault（缺页异常）
- Demand paging（请求调页）
- Thrashing（抖动）
题目 4：有效访问时间与缺页率分析¶
假设某系统使用 请求调页（demand paging） 技术，并采用 3 级页表。页表存放在内存中。
已知：
- TLB 命中率为 96%
- 内存访问时间为 80 ns
- TLB 访问时间为 10 ns（假设 TLB 查找与内存访问串行进行）
- 当发生 page fault 时：
- 如果存在空闲页框，或者被替换的页面没有被修改，则缺页异常处理时间为 6 ms
- 如果被替换的页面已经被修改，则缺页异常处理时间为 18 ms
- 发生 page fault 时，被替换页面有 40% 的概率是已修改页面
请回答下列问题。
-
计算一次 page fault 的平均处理时间。
-
假设 TLB 不命中时，有 0.5% 的概率发生 page fault。计算 TLB 不命中时的平均访问时间。
-
计算系统的有效访问时间 EAT。
-
如果要求系统的有效访问时间不超过 150 ns，那么 TLB 不命中时最大可接受的 page fault rate 是多少？对应的系统总 page fault rate 是多少？
说明
为简化计算，本题中，发生 page fault 时，只计算缺页异常的处理时间，忽略触发异常前查询页表所耗费的时间，以及缺页处理完成后重新执行指令所需的普通访存时间。
题目 5：页面置换算法模拟¶
考虑如下页面访问序列：
假设系统采用请求调页（demand paging），并且只有 3 个页框。请分别计算在以下页面置换算法下会发生多少次 page fault，并列出每次 page fault 时系统持有的页面状况：- LRU replacement
- FIFO replacement
- Optimal replacement
题目 6：页表查找与地址转换¶
NexOS 采用 RISC-V Sv39 分页机制，页面大小为 4KB，即 PGSIZE = 4096。在当前代码中，虚拟地址通过 PX(level, va) 拆成三级页表索引和页内偏移：
PX(2) |
PX(1) |
PX(0) |
Offset |
|---|---|---|---|
| 9 bits | 9 bits | 9 bits | 12 bits |
相关宏定义如下：
#define PGSHIFT 12 // 页内偏移位数
#define PXMASK 0x1FF // 9 bits 掩码
#define PXSHIFT(level) (PGSHIFT + (9 * (level)))
#define PX(level, va) ((((uint64)(va)) >> PXSHIFT(level)) & PXMASK)
#define PA2PTE(pa) ((((uint64)(pa)) >> 12) << 10) // PA是物理地址，PTE是页表项，物理页地址转换为 PTE 中的物理页起始地址部分
#define PTE2PA(pte) (((pte) >> 10) << 12)
#define PTE_FLAGS(pte) ((pte) & 0x3FF)
#define PTE_COW (1L << 8) // Copy-On-Write 标志位
某进程的根页表物理页起始地址为 0x0000000087000000，页表中与本题相关的 PTE 如下，其他未列出的 PTE 均为 0。表中的 PTE 数值按 NexOS 的 PA2PTE(pa) | flags 方式编码。
| 页表页 | 索引 | PTE 内容 | 说明 |
|---|---|---|---|
| root page table | 0x080 |
0x0000000021c00401 |
指向下一级页表页 0x0000000087001000，仅设置 PTE_V |
level-1 page table 0x0000000087001000 |
0x091 |
0x0000000021c00801 |
指向 level-0 页表页 0x0000000087002000，仅设置 PTE_V |
level-0 page table 0x0000000087002000 |
0x145 |
0x000000002048d017 |
叶子 PTE，映射到物理页 0x0000000081234000，权限为 PTE_V \| PTE_R \| PTE_W \| PTE_U |
level-0 page table 0x0000000087002000 |
0x146 |
0x00000000202af013 |
叶子 PTE，映射到物理页 0x0000000080abc000，权限为 PTE_V \| PTE_R \| PTE_U |
level-0 page table 0x0000000087002000 |
0x147 |
0x0000000000000000 |
无有效映射 |
请回答下列问题：
- 虚拟地址
0x0000002012345678对应的PX(2)、PX(1)、PX(0)和Offset分别是多少？ - 按
walk()的查找顺序，虚拟地址0x0000002012345678能否通过walkaddr()成功翻译？如果可以，最终物理地址是多少？注意walkaddr()返回的是物理页起始地址，页内偏移需要再加回去。 - 虚拟地址
0x0000002012346abc若在用户态执行写操作，NexOS 会如何处理？请说明原因，并指出它与 COW 写 fault 的区别。