北航操作系统Lab2实验报告

2025-04-17

本次实验主要实现了MOS操作系统的内存管理

Thinking 2.1

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

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

Thinking 2.2

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

  • 宏将一段代码封装成一条语句，一方面，增强了代码的可重用性，同一个宏定义可以用于创建存储不同类型数据的链表；另一方面，使代码更加简洁，避免了长段重复代码的出现。除此之外，宏是基于字符串替换实现的，相比函数更加简单易用，不必进行地址的跳转和栈的保存，减少程序运行时的性能损耗。

  • 单向链表对给定位置的元素进行后向的插入和删除操作，时间复杂度是 O(1) ；但对于前向的插入，以及插入到某个索引位，需要从头部遍历一遍才能找到相应的位置，时间复杂度是 O(n)

  • 双向链表记录了元素的前驱和后继，对于任意给定位置的元素的双向插入和删除操作时间复杂度是 O(1)；插入到某个索引位，仍需要从头部遍历一遍，时间复杂度是 O(n)

  • 循环链表对给定位置的元素进行后向的插入和删除操作，时间复杂度是 O(1) ，特别的，对于尾部的插入，时间复杂度也是 O(1)；但对于前向的插入，以及插入到中间的某个索引位，时间复杂度仍是 O(n)

Thinking 2.3

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

// Page_list 定义
LIST_HEAD(Page_list, Page);
// LIST_HEAD 定义
#define LIST_HEAD(name, type)  \
	struct name {              \
		struct type *lh_first; \
	}
// 展开为
struct Page_list {
    struct Page *lh_first;
}
// Page 定义
struct Page {
	Page_LIST_entry_t pp_link;
	u_short pp_ref;
};
// 展开为
struct Page_list {
    struct Page {
		Page_LIST_entry_t pp_link;
		u_short pp_ref;
	} *lh_first;
}
// Page_LIST_entry_t 定义
typedef LIST_ENTRY(Page) Page_LIST_entry_t;
// 展开为
struct Page_list {
    struct Page {
		LIST_ENTRY(Page) pp_link;
		u_short pp_ref;
	} *lh_first;
}
// LIST_ENTRY 定义
#define LIST_ENTRY(type)       \
	struct {                   \
		struct type *le_next;  \
		struct type **le_prev; \
	}
// 最终展开为
struct Page_list {
    struct Page {
		struct {
			struct Page *le_next;
			struct Page **le_prev;
		} pp_link;
		u_short pp_ref;
	} *lh_first;
}
  • 答案选 C

Thinking 2.4

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

  • ASID 为每个进程分配了一个唯一的标识符。在进行地址转换时，TLB 可以根据 ASID 和虚拟地址来准确地查找对应的物理地址映射，确保每个进程的地址空间相互隔离，防止进程之间的地址冲突和数据泄露；同时，ASID 也使得操作系统在进行进程切换时，无需频繁地清空 TLB，提高了系统的性能和效率，因为可以通过 ASID 快速区分不同进程的地址转换信息，而不必担心不同进程之间的 TLB 内容相互干扰

  • ASID在 HntryHi 寄存器中占6位，最多容纳$2^6=64$个不同的地址空间

Thinking 2.5

请回答下述三个问题： （1）tlb_invalidate 和 tlb_out 的调用关系？ （2）请用一句话概括 tlb_invalidate 的作用。 （3）逐行解释tlb_out中的汇编代码。

  • tlb_invalidate 方法中调用了 tlb_out 方法
  • tlb_invalidate 函数就是用 tlb_out 把虚拟地址对应的 tlb 页表项清空
LEAF(tlb_out)                   # 标记这是一个叶子函数，即它不会调用其他函数，也不会保存其他寄存器的状态
.set noreorder                  # 汇编器不对指令进行重新排序，确保指令按照写的顺序执行
nop
	mfc0	k1,CP0_ENTRYHI      # 将 EntryHi 寄存器的值存入 k1 寄存器
	mtc0	a0,CP0_ENTRYHI      # 将 a0 寄存器的值存入 EntryHi 寄存器
	nop
	tlbp                        # 根据 EntryHi 在 TLB 中查找与之对应的表项，并把表项的索引存入 Index 寄存器
	nop
	nop
	nop
	nop
	mfc0	k0,CP0_INDEX        # 将 Index 寄存器的值存入 k0 寄存器    
	bltz	k0,NOFOUND          # 如果 Index 小于零，证明 TLB 中没找到 EntryHi 对应的表项，跳转到 NOFOUND 标签
	nop
	mtc0	zero,CP0_ENTRYHI    # 将 EntryHi 寄存器设为 0
	mtc0	zero,CP0_ENTRYLO0   # 将 EntryLo0 寄存器设为 0
	nop
	tlbwi                       # 将 Index 对应的 TLB 表项中设置为 0
NOFOUND:
	mtc0	k1,CP0_ENTRYHI      # 将之前保存的 EntryHi 寄存器值中的值存入 EntryHi 寄存器，恢复上下文
	j	ra                      # 函数返回
	nop
END(tlb_out)

Thinking 2.6

请结合 Lab2 开始的 CPU 访存流程与下图中的 Lab2 用户函数部分，尝试将函数调用与CPU访存流程对应起来，思考函数调用与CPU访存流程的关系。

  • CPU访存流程：
    • CPU发出访存指令后，查询目标页面是否在TLB中
    • 如果不在TLB中（TLB Miss），则根据页目录和虚拟地址寻找页表项
    • 如果页表项不存在（无效），则分配新页面并写入页表项
  • 用户函数部分：
    • CPU发出访存指令后，查询目标页面是否在TLB中
    • 如果不在TLB中（TLB Miss），调用处理TLB重填方法do_tlb_refill，而后调用page_lookup来查找页表项
    • 如果页表项不存在（无效），调用page_alloc来分配新页面，并通过page_insert将新页面插入页表，同时调用tlb_invalidate来使TLB无效
  • 对应关系：
    • 当CPU访存发生TLB miss时，对应到用户函数中的do_tlb_refill函数被调用
    • page_lookup函数对应于CPU访存流程中的“从页表中查找页表项”步骤
    • 如果页表项无效，page_alloc和page_insert函数对应于CPU访存流程中的“分配新页面，写入到页表项”步骤，而tlb_invalidate函数则确保TLB中的相关项被更新

Thinking 2.7

简单了解并叙述 X86 体系结构中的内存管理机制，比较 X86 和 MIPS 在内存管理上的区别。

  • 地址空间布局
    • X86：通常具有较为复杂的地址空间布局，支持多种不同类型的段和多种特权级别的内存访问，以适应不同的操作系统和应用程序需求
    • MIPS：地址空间布局相对简洁，通常采用较为统一的方式来组织内存，例如将内存分为不同的区域用于存放代码、数据、堆栈等，但不像X86那样有多种复杂的段类型和特权级别划分
  • 内存管理单元（MMU）
    • X86：MMU功能强大且复杂，支持多种内存管理特性，如分段与分页的组合使用、多种页面大小、内存保护机制等。它能够处理复杂的内存访问场景，适用于大型通用操作系统和各种不同类型的应用程序
    • MIPS：MMU设计相对简单一些，更注重于提供高效的地址转换和基本的内存保护功能。MIPS的MMU可能在页面大小选择等方面相对不如X86灵活

实验难点

  • 内存管理

    • 数据结构构建：面对多个文件中的代码，需要精准定位并理解与链表宏及函数实现相关的部分，通过阅读复杂的宏，理解双向链表结构，明确每个方法的实现，以及在链表操作中的作用，如果对链表基础操作掌握不扎实，是举步维艰的

    • 两级页表机制：两级页表作为虚拟内存管理核心，其原理较为抽象，涉及到页表项的虚实地址的理解和转换更是一大难点，需要搞清楚代码中，每一个地址时虚拟地址还是物理地址，这样在编程时才不会频繁出错

  • C 语言指针与宏知识
    • 指针运用：整个实验全程贯穿 C 语言指针操作，无论是链表构建、页表项关联还是内存数据访问，都用到了指针。尤其是空闲链表中 le_prev 这种指针的指针，在链表插入删除操作时，相比常规双向链表指针运用复杂了许多，若对指针层级等理解不到位，极易引发内存错误等问题
    • 宏运用：众多宏定义在代码中频繁出现，用于代码简化、逻辑封装。需要牢记课程组给出的各个宏的功能，像用于链表操作宏的精准使用场景、页表相关宏的参数要求等，否则代码编写时会因宏误用导致编译错误或逻辑混乱

实验感想

  • 在面对大量已有代码时，直接上手填空往往适得其反，应先沉下心通读所有代码，梳理整体架构与逻辑流程；刚开始，我仅粗略浏览便仓促开工，对代码理解浮于表面，后续遇到复杂问题，已经不知道自己在做什么了……最后，我沉下心重新精读 pmap.c 函数实现，并结合大模型添加注释后，才在脑中对本次实验有了清晰的框架

  • 内存管理：对虚拟内存、物理内存、TLB 等核心概念理解不够深入全面，对用汇编书写的 TLB 机制一知半解。对课程组给出的大量操作函数，不能够完全熟练运用，遇到复杂场景，不能及时想出使用什么函数
  • 编程技能：C 语言指针和宏运用不熟练成为实验推进最大阻碍。本次实验中，指针频繁穿梭于内存各个区域，构建起复杂数据结构时，我对指针运算、指向变换的掌握欠佳，频频出错；而且对大量宏的使用，我感觉无所适从，凸显编程基础巩固的紧迫性

综上所述，本次实验是挑战与成长并存之旅，虽困难重重，但通过攻克难点、反思体会，为后续深入学习操作系统知识、提升编程实践能力积累了宝贵经验，打下牢固基础