lab2 实验报告 [BUAA-OS]

Lab2实验报告

Part1. 思考题

Thinking 2.1 程序代码中的地址

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

由于实际程序中访存、跳转等指令以及用于取指的PC寄存器中的访存目标地址都是虚拟地址，因此指针变量中存储的地址也是虚拟地址。而MIPS汇编程序中lw和sw指令使用的地址也是虚拟地址。

Thinking 2.2 链表宏

请思考下述两个问题：

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

1. 从可重用性的角度，使用宏能通过预处理器用复制宏代码的方式替代函数调用，实现链表，宏定义的链表操作函数可以方便地被其他程序调用，而不需要重复编写相同的代码，也省去了函数调用的压栈、返回等等操作。
   指导书里提到C++/Java等语言中存在泛型，C语言中没有泛型的语法，使用宏能够较好地实现可重用性(如只要保证链表有field字段和le_prev/le_next属性，就可很方便地实现链表操作，具有可读性和可维护性)。

2. 性能差异如下：

• 关于插入操作：单向链表和循环链表在插入操作时都只需要维护2个指针，双向链表需要维护4个指针，对于在某一个元素后插入的情况，单向链表和循环链表以及双向链表只需要O(1)的时间复杂度.而对于在某一元素前插入，单向链表和循环链表需要O(n)的时间复杂度，双向链表需要O(1)的时间复杂度。在某个位置插入时，单向链表和循环链表以及双向链表都需要O(n)的时间复杂度。
• 关于删除操作：对于删除某个元素的操作，单向链表和循环链表都需要O(n)的时间复杂度，双向链表需要O(1)的时间复杂度；如果要删除某个位置上的元素(只知道序号)，单向链表和循环链表以及双向链表都需要遍历查找，需要O(n)的时间复杂度。

链表头的删除和插入操作都只需要O(1)的时间复杂度；尾部的删除和插入操作，循环链表只需要O(1)的时间复杂度，单向链表和双向链表需要O(n)的时间复杂度。

链表类型	插入/删除操作(某个位置)	删除某个元素	插入操作(某个元素前)	插入操作(某个元素后)
单向链表	O(n)	O(n)	O(n)	O(1)
循环链表	O(n)	O(n)	O(n)	O(1)
双向链表	O(n)	O(1)	O(1)	O(1)

Thinking 2.3 Page_list 结构体

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

>A
>struct Page_list {
   struct {
       struct {
           struct Page *le_next;
           struct Page *le_prev;
           } pp_link;
           u_short pp_ref;
       }* lh_first;
>}

>B
>struct Page_list {
   struct {
      struct {
          struct Page *le_next;
          struct Page *le_prev;
      } pp_link;
      u_short pp_ref;
  } lh_first;
>}

>C
>struct Page_list{
  struct {
    struct {
	    struct Page *le_next;
	    struct Page **le_prev;
	} pp_link;
	u_short pp_ref;
}* lh_first;
>}

LIST_HEAD(Page_list, Page);
typedef LIST_ENTRY(Page) Page_LIST_entry_t;

struct Page {
        Page_LIST_entry_t pp_link; /* free list link */
        u_short pp_ref;
};

#define LIST_HEAD(name, type)     \
    struct name {                                                   \
        struct type *lh_first; /* first element */                          \
    }

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

根据以上代码，我们可以得出选择C。

struct Page_list{ // LIST_HEAD(Page_list, Page);
    struct { // struct Page
        struct { // LIST_ENTRY(Page)
            struct Page *le_next;
            struct Page **le_prev;
        } pp_link;
        u_short pp_ref;
    }* lh_first;
}

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 中可容纳
  不同的地址空间的最大数量。

1. ASID的必要性
   在多进程操作系统中，每个进程都有自己的虚拟地址空间，具有不同页表。同一虚拟地址在不同地址空间中可能对应不同的物理地址，ASID 用于区分不同进程的虚拟地址空间。TLB 事实上构建了一个映射 $<VPN,ASID> \stackrel{TLB}{\longrightarrow} <PFN,N,D,V,G >$，ASID的存在使得TLB可以标识其虚拟地址空间，实现进程间的地址隔离，保护进程的地址空间不被其他进程访问。

2. 4Kc 中可容纳不同的地址空间的最大数量

In this figure the virtual address is extended with an 8-bit address-space identifier (ASID), which reduces the frequency of TLB flushing during a context switch. This 8-bit ASID contains the number assigned to that process and is stored in the CP0 EntryHi register. —— MIPS 4Kc Page 43

ASID段为8位，因此4Kc中可容纳不同的地址空间的最大数量为 $2^8=256$。

Thinking 2.5 tlb_inalidate

请回答下述三个问题：

• tlb_invalidate和tlb_out的调用关系？
• 请用一句话概括tlb_invalidate的作用。
• 逐行解释tlb_out中的汇编代码。

1. 我们在kern/tlbx.c中看到tlb_invalidate函数的实现，其调用关系如下：

void tlb_invalidate(u_int asid, u_long va) {
    tlb_out((va & ~GENMASK(PGSHIFT, 0)) | (asid & (NASID - 1)));
}

说明：tlb_invalidate函数调用tlb_out函数。
2. tlb_invalidate的作用是使TLB中对应虚拟地址的旧表项无效，保证下次访问对应虚拟地址时触发TLB miss，从而更新TLB中的表项。

3. tlb_out中的汇编代码如下：

LEAF(tlb_out) 
.set noreorder
    mfc0    t0, CP0_ENTRYHI // EntryHi寄存器值存入t0，保存原值
    mtc0    a0, CP0_ENTRYHI // 将a0的值存入EntryHi寄存器，a0为旧表项的Key
    nop
    /* Step 1: Use 'tlbp' to probe TLB entry */
    /* Exercise 2.8: Your code here. (1/2) */
    tlbp                   // 根据Key查询TLB中是否有与之匹配的旧表项，存入Index寄存器
    nop
    /* Step 2: Fetch the probe result from CP0.Index */
    mfc0    t1, CP0_INDEX // 将Index寄存器值存入t1寄存器
.set reorder
    bltz    t1, NO_SUCH_ENTRY // t1为负，说明未找到与Key匹配的旧表项，跳转到NO_SUCH_ENTRY
.set noreorder
    mtc0    zero, CP0_ENTRYHI // 将EntryHi寄存器清零
    mtc0    zero, CP0_ENTRYLO0 // 将EntryLo0寄存器清零
    mtc0    zero, CP0_ENTRYLO1 // 将EntryLo1寄存器清零
    nop
    /* Step 3: Use 'tlbwi' to write CP0.EntryHi/Lo into TLB at CP0.Index  */
    /* Exercise 2.8: Your code here. (2/2) */
    tlbwi // 将EntryHi和EntryLo0/EntryLo1写入TLB中Index寄存器对应的表项
    nop
.set reorder

NO_SUCH_ENTRY:
    mtc0    t0, CP0_ENTRYHI // 将t0的值存回EntryHi寄存器，恢复原值
    j       ra // 返回调用者
END(tlb_out)

Thinking 2.6 函数调用与 CPU 访存流程

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

在Lab2中，CPU 访存流程与函数调用的关系紧密，Lab2在 MOS 系统的作用是管理虚拟内存和页表，保证用户程序的运行。函数调用与CPU访存流程的关系紧密，函数调用涉及到内存的访问和操作，而CPU访存流程则是实现这些操作的基础。

1. 在内核初始化阶段，CPU 需要初始化内存管理模块，检测物理内存范围并建立虚拟内存系统。调用mips_detect_memory、mips_vm_init、page_init，确保系统能够正确管理物理内存并支持虚拟内存。
2. 在用户进程运行阶段，CPU通过虚拟地址访问内存。若虚拟地址在TLB中命中，则直接完成访存；若TLB miss，则触发异常处理，随即调用do_tlb_refill、page_lookup、passive_alloc、page_alloc、page_insert、tlb_invalidate等函数，缺页异常处理依赖于内存管理函数的调用，这些函数负责分配物理页并更新页表，从而解决缺页问题。

Thinking 2.7 其他体系结构的内存管理

从下述三个问题中任选其一回答：

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

1. X86体系结构中的内存管理机制
   X86体系结构中的内存管理机制主要包括以下几个关键部分：

   1. 分段机制：X86使用分段机制使用段描述符来定义内存区域，划分为多个段，每个段都有自己的基地址、限长和访问权限等。虚拟地址被分为段选择符和段内偏移。CPU通过段选择符找到对应的段描述符，再根据段描述符中的基地址和限长计算出物理地址。
   2. 分页机制：X86使用分页机制将内存划分为固定大小的页（通常为4KB），并通过多级（通常是二级或三级）页表将虚拟地址映射到物理地址。分页的主要目的是提供内存隔离和内存保护。
   3. 在X86系统中，分段和分页机制可以结合使用，也可以单独使用。结合使用时，分段提供逻辑上的内存组织，而分页提供物理上的内存映射，即使用段内偏移作为分页的虚拟地址，再通过页表进行映射得到最终物理地址。
   4. 内存保护：段描述符和页表项中包含访问权限（如读、写、执行），CPU会根据当前的特权级（CPL）检查访问是否合法。X86有四个特权级（Ring 0到Ring 3），内核通常运行在Ring 0，用户进程运行在Ring 3。

2. X86和MIPS在内存管理上的区别

   • X86采用的是段页式内存管理机制，而MMIPS采用的是页式内存管理机制。
   • X86的段描述符和页表项中包含更多的信息，如访问权限、特权级等，而MIPS的页表项中只包含页的物理地址。
   • 在TLB处理方面，TLB miss时，X86直接由硬件的 MMU 处理，使用段描述符和页表项中的信息进行地址转换，并更新TLB；而MIPS则会触发异常，将控制权交给操作系统内核，由内核中的相应程序处理异常并更新TLB。
   • X86是CISC（复杂指令集计算机）架构，支持64位逻辑地址并可以转换为32位物理地址指令集丰富；而MIPS是RISC（精简指令集计算机）架构，地址空间为32位，指令集相对简单。

Thinking A.1 三级页表

在现代的 64 位系统中，提供了 64 位的字长，但实际上不是 64 位页式存储系统。假设在64位系统中采用三级页表机制，页面大小4KB。由于64位系统中字长为8B，且页目录也占用一页，因此页目录中有512 个页目录项，因此每级页表都需要9位。因此在64位系统下，总共需要3×9+12=39位就可以实现三级页表机制，并不需要64位。
现考虑上述39位的三级页式存储系统，虚拟地址空间为512GB，若三级页表的基地址为PTbase，请计算：

• 三级页表页目录的基地址。
• 映射到页目录自身的页目录项（自映射）。

1. 39位的三级页式存储系统中，虚拟地址空间为512GB，页面大小为4KB，因此共有$2^{39-12}=2^{27}$个页。则根据三级页表的基地址$PT_{base}$可得页号PN为$PT_{base}>>12$，即由第PN个页表项映射得到该三级页表。根据三级页表的基地址是由二级页表的第一个页表项映射得到，因此二级页表的基地址$PMD_{base}=PT_{base} + PN×8=PT_{base} + PT_{base}>>9$。根据二级页表的基地址是由一级页表的第一个页表项映射得到，因此一级页表的基地址$PGD_{base}=PT_{base} + PMD_{base}>>9 = PT_{base} + PT_{base}>>9 + PT_{base}>>18$，也就是三级页表页目录的基地址$PGD_{base}$。
2. 求映射到页目录自身的页目录项（自映射）的页目录项，页号为$PGD_{base}>>12$, 即由第$PGD_{base}>>12$个页表项映射得到，因此该页目录项的地址为$PT_{base} + PGD_{base}>>12×8=PGD_{base}=PT_{base} + PMD_{base}>>9 = PT_{base} + PT_{base}>>9 + PT_{base}>>18 + PT_{base}>>27$。

Part2. 难点分析

链表宏与 Page_list 结构体

Thinking 2.3 Page_list 结构体 中涉及到了链表宏定义，主要的难点在于其中的le_prev，注释中描述其为 address of previous next element，即元素 A 的le_prev指向前一个元素 B 的le_next指针的地址，这是一个指针的指针！ 而且更为有意思的是，上一个元素 B 的 le_next 指针指向的是这个元素 A。换言之，是指向自己的指针的指针！
可为什么要使用这个指针的指针呢？仔细思考一下，链表中的每个元素都有一个le_next指针，指向下一个元素的地址，而le_prev指针指向的是上一个元素的le_next指针的地址，这样做的目的是为了方便删除链表中的元素(比如当前元素)，即通过修改前一个元素的le_next指针和下一个元素的le_prev指针，即可删除当前元素。对于插入来说就更明显了，因为要插入一个元素，需要修改前一个元素的le_next指针和下一个元素的le_prev指针（当然还有它自己的le_prev和le_next），使用le_prev可以很方便地修改上一个元素的le_next指针，而不用费时费力去遍历整个链表，LIST_INSERT_BEFORE和LIST_INSERT_AFTER这两个宏就很直观地体现了这一点。

#define LIST_INSERT_BEFORE(listelm, elm, field) \
    do { \
        (elm)->field.le_prev = (listelm)->field.le_prev; \
        LIST_NEXT((elm), field) = (listelm); \
        *(listelm)->field.le_prev = (elm); \
        (listelm)->field.le_prev = &LIST_NEXT((elm), field); \
    } while (0)

理解了le_prev的作用，那么Page_list结构体就很好理解了，它是一个能够访问前一个元素的next字段、方便插入删除的链表。

TLB的原理和实现&地址转换

实验环境中的TLB是一个二级页表（页目录和页表），它将虚拟地址转换成物理地址，具体组成可以参考下图

一级页表项(页目录)偏移量 = 虚拟地址的[31:22]，可以根据它和一级页表基地址找到对应的二级页表项(页表)的基地址，再根据虚拟地址中的二级页表(页表)偏移量[21:12]和基地址找到对应的物理页框号(页框)，最后根据虚拟地址中的页内偏移量[11:0]找到对应的物理地址。所以为了得到物理地址，我们需要以下几个参数：

• 虚拟地址
• 一级页表基地址(页目录基地址)
• 二级页表基地址(一级页表项，虚拟地址的[31:22])
• 物理页框号(二级页表项，虚拟地址的[21:12])
• 页内偏移量(虚拟地址的[11:0])

因此Lab2关于TLB的实验就围绕这几个参数展开。我们需要时刻清楚自己所使用的参数是什么，尤其是虚拟地址va和物理地址pa等等，这里再放一张指导书中图帮助理解(体现了具体代码实现)

建议多多查阅指导书中关于TLB的描述，理解其原理，再结合代码实现，这样会事半功倍。

实验体会

通过本次实验，我更深刻理解了虚拟地址和物理地址的转换过程，以及我们的MOS设计中的两级页表实现机制。同时，我对于指针的使用有了更深的理解，尤其是链表指针的使用。配合OS理论课中的内存管理相关内容食用更佳！

参考资料

• wokron 学长的博客
• Hugo 学长的博客
• Argithun 学长的博客
• ChatGPT老师
• DeepSeek老师