思考题

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

虚拟地址；虚拟地址。

Thinking 2.2 请思考下述两个问题：

• 从可重用性的角度，阐述用宏来实现链表的好处。

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

Q1：通过宏定义对链表的操作进行封装，实现了代码复用，减少了代码量的同时便于代码的维护。

Q2：

/usr/include/sys/queue.h 的单向链表只能获取每一项的后一项，因此在插入与删除时都需要对链表进行遍历，时间复杂度为 O(n)；
/usr/include/sys/queue.h 的循环链表既实现了双向链表，又维护了头尾指针，插入与删除时可以根据链表项直接获取其位置进行操作，并获取其前后项，时间复杂度为 O(1)；
本实验中的双向链表在插入与删除操作时，可以根据链表项直接获取其位置，时间复杂度为 O(1)；但无法直接对链表尾部进行操作，需要遍历链表获取尾部项，时间复杂度为 O(n)。

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

le_next 是指向下一个元素的指针，因此类型为 Page *；le_prev 是指向前一个元素的链表项的 le_next 的指针，因此应为二级指针，类型为 Page **。

同时，lh_first 为 Page 链表的头指针，因此类型为结构体指针而非结构体。

综上，选择 C 结构：

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

Q1：

避免 TLB 频繁 Flush 带来的性能损耗。若不使用 ASID 来标识不同的地址空间，则在进行进程切换时，需要完全冲刷 TLB，否则残留的旧进程 TLB 表项可能导致地址翻译错误（不同地址空间中，相同的虚拟地址可能映射到不同的物理地址）。而通过 ASID 标识地址空间可以在访问 TLB 时进行 ASID 匹配，以确保访问正确的地址空间，因此仅在必要时进行特定 TLB 表项的 Flush，大大提高性能。
支持多进程并发的地址空间隔离。每个进程拥有独立的虚拟地址空间，ASID 为每个进程分配唯一的标识符，确保 TLB 表项仅对匹配 ASID 的进程可见。及时多进程使用相同的虚拟地址，也能通过 ASID 区分物理映射，避免地址空间污染。

Q2：ASID 位数为 8 位，因此最多可容纳 2⁸ = 256 个地址空间。

Thinking 2.5 请回答下述三个问题：

•tlb_invalidate 和 tlb_out 的调用关系？

•请用一句话概括 tlb_invalidate 的作用。

•逐行解释 tlb_out 中的汇编代码。

Q1：tlb_invalidate 调用 tlb_out；

Q2：删除特定虚拟地址在 TLB 中的旧表项；

Q3：

LEAF(tlb_out)	# 初始化tlb_out函数的相关信息，并标记函数的开头
.set noreorder	# 不允许对接下来的代码进行重排序
	mfc0    t0, CP0_ENTRYHI	# 保存EntryHi寄存器的旧值
    mtc0    a0, CP0_ENTRYHI	# 将参数值（旧表项的Key）通过a0寄存器写入EntryHi寄存器
	nop	# 因流水线设计架构原因，tlbp指令的前后都应各插入一个nop以解决数据冒险
    tlbp	# 根据EntryHi中的Key查找TLB中相应的表项，并将该表项的索引存入Index寄存器（若未找到匹配表项，则Index最高位置1）
    nop
    mfc0    t1, CP0_INDEX	# 获取Index寄存器的值
.set reorder	# 允许对接下来的代码进行重排序
	bltz    t1, NO_SUCH_ENTRY	# 若Index寄存器的值小于0，也即TLB未找到匹配表项，则跳转到NO_SUCH_ENTRY处
.set noreorder	# 不允许对接下来的代码进行重排序
	mtc0    zero, CP0_ENTRYHI	# 接下来三条命令将EntryHi, EntryLo0和EntryLo1寄存器置零
	mtc0    zero, CP0_ENTRYLO0
	mtc0    zero, CP0_ENTRYLO1
	nop
	tlbwi	# 以Index寄存器中的值为索引，将EntryHi, EntryLo0和EntryLo1的值写入到索引指定的TLB表项中

.set reorder	# 允许对接下来的代码进行重排序

NO_SUCH_ENTRY:	# NO_SUCH_ENTRY标签处
	mtc0    t0, CP0_ENTRYHI	# 将EntryHi寄存器的旧值写回
	j       ra	# 跳转回去
END(tlb_out)	# 标记tlb_out函数的结束，并记录其大小

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

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

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

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

• 简单了解并叙述 LoongArch 中的内存管理机制，比较 LoongArch 与 MIPS 在内存管理上的区别。

LoongArch 是龙芯自主研发的指令集架构，其内存管理机制在继承传统设计的基础上进行了多项创新，与 MIPS 架构存在显著差异。

地址空间与分段设计

LoongArch 采用单一平面地址空间，摒弃了 MIPS 的固定分段模式（如 kseg0、kseg1 等），支持更大的物理寻址范围（如分支跳转偏移从 MIPS 的 64KB 扩展到 1MB），减少了编译结果的指令条数和访存次数，提升内存访问效率。
TLB 与分页机制

LoongArch 的 TLB 支持动态扩展，通过多级页表实现虚拟地址到物理地址的映射，并优化了 TLB 的填充策略，减少因 TLB 未命中导致的异常处理开销。同时引入更复杂的页表格式（如 10 种指令格式），支持更大的立即数（最大 24 位）和灵活的寻址方式，适应高性能计算需求。

MIPS 的 TLB 条目包含 ASID（地址空间标识符），支持多进程隔离，但条目数量有限（如 4Kc 处理器仅有 16 个 JTLB 条目），易因频繁异常降低性能。且 MIPS 采用二级页表结构，页目录和页表均为固定大小（如 4KB），物理内存分配依赖伙伴算法和 Slab 分配器。

Thinking A.1 在现代的 64 位系统中，提供了 64 位的字长，但实际上不是 64 位页式存储系统。假设在 64 位系统中采用三级页表机制，页面大小 4KB。由于 64 位系统中字长为 8B，且页目录也占用一页，因此页目录中有 512 个页目录项，因此每级页表都需要 9 位。因此在 64 位系统下，总共需要 3×9+12=39 位就可以实现三级页表机制，并不需要 64 位。

现考虑上述 39 位的三级页式存储系统，虚拟地址空间为 512 GB，若三级页表的基地址为 PT_base。请计算：

•三级页表页目录的基地址。

•映射到页目录自身的页目录项（自映射）

三级页表中一个页目录项映射空间大小为 2¹⁸个3级页表项 × 4KB = 2³⁰B，页表空间大小为 2²⁷ * 8B = 2³⁰B。页表空间所在位置对应到页目录的第 PT_base >> 30 项，也即页表空间中第（PT_base >> 30）_ 2¹⁸ 即 PT_base >> 12 项，因此页目录基地址为 PT_base + （PT_base >> 12）_ 8B 即 PT_base + PT_base >> 9。
第 PT_base >> 30 项。

难点分析

ROUND(a,n)、ROUNDDOWN(a,n)

kern/pmap.c 中的 alloc 函数有一条语句 freemem = ROUND(freemem, align)，这行代码的含义即找到 freemem 之上最小的、按 align 对齐的初始虚拟地址，中间未用到的地址空间全部放弃。实际上是找到了一段空闲的、起始地址与 align 对齐的内存空间。

ROUND(a,n) 和 ROUNDDOWN(a,n) 都是定义在 include/types.h 的宏，前者返回 $\lceil\frac{a}{n}\rceil n$，后者返回 $\lfloor \frac{a}{n}\rfloor n$，分别表示将 a 按 n 向上对齐和向下对齐，要求 n 必须是 2 的非负整数次幂。

页控制块（Page 结构体）与空闲链表

// include/pmap.h
typedef LIST_ENTRY(Page) Page_LIST_entry_t;

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

LIST_ENTRY(type) 作为一个特殊的类型出现，其本质是一个链表项，包括指向下一个元素的指针 le_next，以及指向前一个元素链表项中的 le_next 的指针 le_prev。

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

pp_ref 对应这一页物理内存被引用的次数，它等于有多少虚拟页映射到该物理页。

上图中的 le_next 与 le_prev 组成的结构体即为链表项（field 域，页控制块中为 pp_link），链表项与 data 域（页控制块中为 u_short pp_ref）组成的 Page 结构体即为页控制块。

虚拟地址与物理地址的转换

在实际程序中，访存、跳转等指令以及用于取指的 PC 寄存器中的访存目标地址都是==虚拟地址==。C 程序中经常通过对指针解引用来进行访存，其中指针的值也会被视为==虚拟地址==，经过编译后生成相应的访存指令（在 C 程序中，一定要使用虚拟地址进行内存操作！如 memset）。

include/pmap.h 中关于 VA 与 PA 转换的相关函数：

page2ppn 用于返回给定页控制块在 pages 数组中的索引。

1
2
3

static inline u_long page2ppn(struct Page *pp) {
    return pp - pages;
}

page2pa 用于返回给定页控制块对应（控制）的物理页面的起始地址（物理地址）。

1
2
3

static inline u_long page2pa(struct Page *pp) {
    return page2ppn(pp) << PGSHIFT;	// PGSHIFT = 12，定义在include/mmu.h中
}

pa2page 用于返回给定物理地址所在页对应的页控制块。

static inline struct Page *pa2page(u_long pa) {
    if (PPN(pa) >= npage) {		// PPN(pa)定义在include/mmu.h中，值为(((u_long)(pa)) >> PGSHIFT)，
        						// 用于返回物理地址pa所在的物理页面的页号
        panic("pa2page called with invalid pa: %x", pa);
    }
    return &pages[PPN(pa)];
}

page2kva 用于返回给定页控制块对应（控制）的物理页面的起始地址对应的虚拟地址（kseg0 中）。

1
2
3

static inline u_long page2kva(struct Page *pp) {
    return KADDR(page2pa(pp));	// KADDR定义在include/mmu.h中，用于返回物理地址pa在kseg0中对应的虚拟地址
}

va2pa 用于返回在给定的二级页表结构中虚拟地址映射的物理地址（若找不到映射返回~0）。

static inline u_long va2pa(Pde *pgdir, u_long va) {
    Pte *p;

    pgdir = &pgdir[PDX(va)];
    if (!(*pgdir & PTE_V)) {
        return ~0;
    }
    p = (Pte *)KADDR(PTE_ADDR(*pgdir));
    if (!(p[PTX(va)] & PTE_V)) {
        return ~0;
    }
    return PTE_ADDR(p[PTX(va)]);
}

此外在 include/mmu.h 中也定义了一些宏用于地址转换：PPN(pa)、VPN(va)、PADDR(kva)、KADDR(pa)，以及 PDX(va) 和 PTX(va) 分别用于获取虚拟地址 va 的页目录（一级页表）索引和页表（二级页表）索引，PTE_ADDR(pte) 用于获取页表项中的物理页号。

在实际编程中，需要根据情况将物理（虚拟）地址转换为对应的虚拟（物理）地址才能使用。

对二级页表结构进行处理的有关函数
- 二级页表检索函数 int pgdir_walk(Pde *pgdir, u_long va, int create, Pte **ppte)：该函数将一级页表基地址 pgdir 对应的两级页表结构中 va 虚拟地址所在的二级页表项的指针存储在 ppte 指向的空间上。如果 create 不为 0 且对应的二级页表不存在，则会使用 page_alloc 函数分配一页物理内存用于存放二级页表，如果分配失败则返回错误码。
- 增加地址映射函数 int page_insert(Pde *pgdir, u_int asid, struct Page *pp, u_long va, u_int perm)：作用是将一级页表基地址 pgdir 对应的两级页表结构中虚拟地址 va 映射到页控制块 pp 对应的物理页面，并将页表项权限为设置为perm。
- 寻找映射的物理地址函数 struct Page *page_lookup(Pde *pgdir, u_long va, Pte **ppte)：作用是返回一级页表基地址 pgdir 对应的两级页表结构中虚拟地址 va 映射的物理页面的页控制块，同时将 ppte 指向的空间设为对应的二级页表项地址。
- 取消地址映射函数 void page_remove(Pde *pgdir, u_int asid, u_long va)：作用是删除一级页表基地址 pgdir 对应的两级页表结构中虚拟地址 va 对物理地址的映射。如果存在这样的映射，那么对应物理页面的引用次数会减少一次。
页表项、TLB 和 EntryHi、EntryLo 寄存器的关系

每个页表项由 32 位组成，包括 20 位物理页号以及 12 位标志位。其中，12 位标志位包含高 6 位硬件标志位与低 6 位软件标志位。高 6 位硬件标志位用于存入 EntryLo 寄存器中，供硬件使用。低 6 位软件标志位不会被存入 TLB 中，仅供软件使用。

当页表项需要借助 EntryLo 寄存器填入 TLB 时，页表项会被右移 6 位，移出所有软件标志位，仅将高 20 位物理页号以及 6 位硬件标志位填入 TLB 使用。

EntryHi、EntryLo0、EntryLo1 都是 CP0 中的寄存器，他们只是分别对应到 TLB 的 Key 与两组 Data，并不是 TLB 本身。其中 EntryLo0、EntryLo1 拥有完全相同的位结构，EntryLo0 存储 Key 对应的偶页而 EntryLo1 存储 Key 对应的奇页。
TLB Miss 时重填过程（见思考题 2.6）

实验体会

需要掌握物理内存管理的方法，即通过页控制块来管理对应的物理页面。需要掌握页控制块的结构以及空闲页面链表创建。
熟记虚拟地址与物理地址转换的各种宏。在编程时，一定要正确地使用虚拟/物理地址。例如在 C 程序中，对内存空间操作时务必使用虚拟地址。
掌握虚拟内存管理的方法，熟悉页表相关函数的功能与使用方法。熟记页目录与二级页表的结构、页表项的构成。
掌握用户访存流程，熟悉访存过程中 TLB 重填的步骤，理清其中各个函数的作用。熟记 TLB 的结构以及 CP0 中相关寄存器的作用，尤其是 EntryHi 和 EntryLo 寄存器，理清它们与 TLB、页表之间的关系。