思考题

Thinking 2.1

请根据上述说明，回答问题：在编写的 C 程序中，指针变量中存储的地址被视为虚拟地址，还是物理地址？MIPS 汇编程序中 lw 和 sw 指令使用的地址被视为虚拟地址，还是物理地址？

C 语言中指针变量储存的地址是虚拟地址，汇编代码中 lw 和 sw 指令中使用的地址也是虚拟地址。

Thinking 2.2

  • 从可重用性的角度，阐述用宏来实现链表的好处。
  • 查看实验环境中的 /usr/include/sys/queue.h，了解其中单向链表与循环链表的实现，比较它们与本实验中使用的双向链表，分析三者在插入与删除操作上的性能差异。

  1. 使用宏来实现链表的好处有以下几个方面：

    • 代码复用：宏可以使链表的定义和操作变得通用，不受特定数据类型的影响。通过宏，可以在不同的数据结构中重用相同的链表实现代码，只需简单地将链表节点中的数据类型进行替换即可。
    • 类型无关性：宏允许链表操作与具体的存储类型无关，这意味着同一个宏定义可以用于创建存储不同类型数据的链表。
    • 性能优势：宏在编译时会被直接替换为相应的代码，没有函数调用的开销。这可以减少程序运行时的性能损耗。

  2. 阅读了系统中queue.h可以得到以下结论

    • 单项链表如果要插入到链表中间的某个位置，需要从头部遍历一遍才能找到相应的位置，这个事件复杂的是 O(n)；
    • 而双向链表记录了元素的前驱和后继，它对于任意元素在任意给定位置的插入和删除操作时间复杂度都只有 O(1)；
    • 循环列表本质和单向链表差不多

Thinking 2.3

请阅读 include/queue.h 以及 include/pmap.h, 将 Page_list 的结构梳理清楚，选择正确的展开结构。

1
2
3
4
5
6
7
8
9
10
A:
struct Page_list{
struct {
	struct {
		struct Page *le_next;
		struct Page *le_prev;
	} pp_link;
	u_short pp_ref;
}* lh_first;
}
1
2
3
4
5
6
7
8
9
10
B:
struct Page_list{
	struct {
		struct {
			struct Page *le_next;
			struct Page **le_prev;
		} pp_link;
		u_short pp_ref;
	} lh_first;
}
1
2
3
4
5
6
7
8
9
10
C:
struct Page_list{
	struct {
		struct {
			struct Page *le_next;
			struct Page **le_prev;
		} pp_link;
		u_short pp_ref;
	}* lh_first;
}

应当选择C。
关于Page：

1
2
3
4
struct Page {
    Page_LIST_entry_t pp_link;  /* free list link */
    u_short pp_ref;
};

而关于Page_LIST_entry_t：

1
2
3
4
5
#define LIST_ENTRY(type)                                                    \
        struct {                                                                \
                struct type *le_next;   /* next element */                      \
                struct type **le_prev;  /* address of previous next element */  \
        }

Thinking 2.4

  • 请阅读上面有关 TLB 的描述，从虚拟内存和多进程操作系统的实现角度，阐述 ASID的必要性。
  • 请阅读 MIPS 4Kc 文档《MIPS32® 4K™ Processor Core Family Software User’s Manual》的 Section 3.3.1 与 Section 3.4，结合 ASID 段的位数，说明 4Kc 中可容纳不同的地址空间的最大数量。

在多进程环境中，每个进程都有自己的虚拟地址空间，这些地址空间通常是独立的。ASID用于在TLB中区分不同进程的页表项，确保每个进程只能访问自己的内存地址，从而实现进程间的隔离。

ASID使得操作系统在管理内存时更加灵活和高效。它允许操作系统为每个进程分配一个唯一的标识符，而不需要关心进程的具体虚拟地址空间布局，从而简化了内存管理的工作。

当CPU进行上下文切换时，如果没有ASID，则需要将TLB中的所有条目刷新，因为新的进程可能会使用相同的虚拟地址，而这些地址在TLB中可能映射到不同的物理地址。ASID允许TLB保留多个进程的条目，只有当切换到具有相同ASID的进程时才需要刷新相关的TLB条目，减少了不必要的刷新操作。

ASID 6 位，因此可以最多容纳 64 个不同的地址空间。

Thinking 2.5

  • tlb_invalidate 和 tlb_out 的调用关系？
  • 请用一句话概括 tlb_invalidate 的作用。
  • 逐行解释 tlb_out 中的汇编代码。
1
2
3
void tlb_invalidate(u_int asid, u_long va) {
    tlb_out((va & ~GENMASK(PGSHIFT, 0)) | (asid & (NASID - 1)));
}

可以看到是tlb_invalidate调用tlb_out

逐行解释如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
LEAF(tlb_out) # 标记这是一个叶子函数，即它不会调用其他函数，也不会保存其他寄存器的状态。
.set noreorder # 告诉汇编器不要对指令进行重新排序，确保指令按照写的顺序执行
    mfc0    t0, CP0_ENTRYHI # 将 CP0 寄存器中的 ENTRYHI（TLB 的键字段）内容复制到通用寄存器 t0 中，保存原始的 ENTRYHI 值
    mtc0    a0, CP0_ENTRYHI # 将传入的参数（a0 寄存器中的值）复制到 CP0 的 ENTRYHI 寄存器中，准备进行TLB操作
    nop
    /* Step 1: Use 'tlbp' to probe TLB entry */
    /* Exercise 2.8: Your code here. (1/2) */
    nop
    tlbp # 根据 EntryHi 中的 Key，查找 TLB 中与之对应的表项，并将表项的索引存入 Index 寄存器
    nop
    /* Step 2: Fetch the probe result from CP0.Index */
    mfc0    t1, CP0_INDEX # 将 CP0 的 INDEX 寄存器内容（TLB 探测的结果）复制到通用寄存器 t1 中
    .set reorder
    bltz    t1, NO_SUCH_ENTRY # 如果 TLB 中没有找到对应的条目，跳转到 NO_SUCH_ENTRY 标签
    .set noreorder
    mtc0    zero, CP0_ENTRYHI
    mtc0    zero, CP0_ENTRYLO0
    mtc0    zero, CP0_ENTRYLO1 # 把 CP0_ENTRYHI，CP0_ENTRYLO 全部设为 0，为清空 TLB 做准备
    nop
    /* Step 3: Use 'tlbwi' to write CP0.EntryHi/Lo into TLB at CP0.Index  */
    /* Exercise 2.8: Your code here. (2/2) */
    nop
    tlbwi # 将此时 EntryHi 与 EntryLo 的值，也就是 0，写到索引指定的 TLB 表项中，完成清空
    nop
.set reorder

NO_SUCH_ENTRY:
    mtc0    t0, CP0_ENTRYHI # 将之前保存的原始 ENTRYHI 值写回到 CP0 的 ENTRYHI 寄存器中，恢复上下文
    j       ra # 返回
END(tlb_out)

Thinking A.1

三级页表页目录的基地址
{PTbase[38:30], PTbase[38:30], PTbase[38:30], 12'h0}

映射到页目录自身的页目录项（自映射）
{PTbase[38:30], PTbase[38:30], PTbase[38:30], PTbase[38:30], 3'h0}

Thinking 2.6

  1. CPU 发出访问指令: 用户进程执行内存访问。
  2. 查询 TLB: 硬件自动执行。
  3. 触发 TLB Miss (No 分支): 硬件检测到 TLB 未命中，跳转到内核 TLB Miss 处理程序。
  4. 根据页目录表和虚拟地址寻找页表项 / 从页表中查找页表项: 主要由 page_lookup 函数实现。它遍历页目录和页表，查找对应的页表项 (PTE)。
  5. 页目录项/页表项是否有效:
    • 否 (No 分支 - 页面/页表不存在或无效):
      • 分配新页面/页表: 可能涉及 page_alloc (分配物理页) 和 page_insert (建立映射，填写 PTE)。（流程图简化了分配页表本身，Lab2 主要处理页面的分配和插入）
    • 是 (Yes 分支 - 找到有效 PTE): page_lookup 成功返回有效的 PTE。
  6. 取出物理页号 PPN … 写入 TLB: 由 _do_tlb_refill 函数在 page_lookup 成功后，读取 PTE 信息，并使用特定 CPU 指令将映射关系写入硬件 TLB。
  7. 重新访问 / 读取到 PPN 结合 offset 完成访问 (Yes 分支): TLB refill 完成后，指令重新执行，此时 TLB Hit，硬件使用 TLB 中的 PPN 完成地址翻译和访问。

核心关系: Lab2 中的 do_tlb_refill、page_lookup、page_alloc、page_insert 等函数共同构成了 CPU 访问流程图中 TLB Miss 发生后由软件执行的页表查找、页面分配（如果需要）、页表更新以及最终填充 TLB 的处理逻辑。

Thinking 2.7

  • X86 体系结构中的内存管理机制
    • 通过分段将逻辑地址转换为线性地址，通过分页将线性地址转换为物理地址。
    • 逻辑地址由两部分构成，一部分是段选择器，一部分是偏移。
    • 段选择符存放在段寄存器中，如CS（存放代码段选择符）、SS（存放堆栈段选择符）、DS（存放数据段选择符）和ES、FS、GS（一般也用来存放数据段选择符）等；
    • 偏移与对应段描述符中的基地址相加就是线性地址。
    • 操作系统创建全局描述符表和提供逻辑地址，之后的分段操作x86的CPU会自动完成，并找到对应的线性地址。
    • 从线性地址到物理地址的转换是CPU自动完成的，转化时使用的Page Directory和Page Table等需要操作系统提供。
  • X86 和 MIPS 在内存管理上的区别
    • TLB不命中：
      • MIPS触发TLB缺失和充填，然后CPU重新访问TLB
      • x86硬件MMU索引获得页框号，直接输出物理地址，MMU充填TLB加快下次访问速度
    • 分页方式不同：
      • 一种MIPS系统内部只有一种分页方式
      • x86的CPU支持三种分页模式
    • 逻辑地址不同：
      • MIPS地址空间32位
      • x86支持64位逻辑地址，同时提供转换为32位定址选项
    • 段页式的不同：
      • MIPS同时包含了段和段页式两种地址使用方式
      • 在x86架构的保护模式下的内存管理中，分段是强制的，并不能关闭，而分页是可选的；

实验难点

  • 物理内存管理部分，我感觉难度相对适中。主要任务是填充链表宏定义和实现几个关键函数。

    • 链表宏：这部分的关键在于理解双向链表的原理。虽然填充本身不难，但在动手前需要仔细阅读多个相关文件中的代码，并结合已有的宏定义，才能准确把握传入参数的含义。
    • 函数实现：这部分则要求对各个变量间的逻辑关系有清晰的认识，特别是要理解 ROUND 函数的作用以及页控制块（Page Control Block）及其内部变量的意义。只要理解了这些，依照代码注释中的提示来完成实现还是比较顺利的。

  • 虚拟内存管理部分，整体难度也感觉不算太高。

    • 核心在于掌握二级页表的工作机制，并熟悉相关的宏定义和函数调用方法。

  • TLB 重填部分，需要编写的代码量不大。基本上是根据代码注释的要求，按部就班地完成指定的操作即可。

总的来说，这次实验加深了我对操作系统内存管理机制的理解，尤其是在二级页表和地址转换的概念上有了更清晰的认识，尽管中间也遇到了一些理解上的挑战。

实验体会

面对庞大的现有代码库，我最初感到有些不知所措，直接上手完成任务确实困难。由于 Lab 2 的课下作业开始得比较晚，时间紧迫，我采取了先快速浏览一遍，然后就参照提示或模仿上下文代码来填充空白的策略。这种“依样画葫芦”的方式虽然让我较快地完成了任务，但明显感觉到自己对代码的理解并不深入。
意识到这一点后，在完成练习之后，我特意投入了大半天的时间。我结合指导书，从头到尾仔细研读了 pmap.c 文件中的每一个函数实现。同时，我也更细致地查看了相关的头文件，这不仅加深了我对 C 语言宏定义的理解，也让我对每个函数的功能和实现逻辑有了更清晰的认识，并为它们添加了自己的注释。在这个深入阅读和思考的过程中，许多之前模糊不清的地方豁然开朗，得到了合理的解释。后来通过与同学们的交流讨论，我对代码细节和内存管理机制的理解又得到了进一步的巩固和深化。