Lab2 实验报告

思考题

Thinking 2.1

Thinking 2.1 请根据上述说明，回答问题：

在编写的 C 程序中，指针变量中存储的地址被视为虚拟地址，还是物理地址？ MIPS 汇编程序中 lw 和 sw 指令使用的地址被视为虚拟地址，还是物理地址？

均为虚拟地址。

Thinking 2.2

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

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

对各自定义的类型都适用，在使用时只需稍微定义数据域即可，而不需从头开始定义繁琐的数据结构，具有很高的可重用性
使用起来很方便，无需关注链表的遍历、插入、删除操作的具体实现，也因此避免了由此可能带来的错误
这种用宏定义链表结构的操作可以说是既保留了C语言作为贴近底层的语言的高效性，也吸纳了一些高级语言的简便性，可以说是兼顾了开发效率和编译效率

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

本实验中使用的双向链表的插入(不论前后)与删除操作时间复杂度均为O(1)
单向链表插入在后面的时间复杂度为O(1)，但插入在前面和删除操作的时间复杂度为O(n)，因为需要修改前一个元素的指针域，只能通过遍历来实现
循环链表的时间复杂度取决于其为单向还是双向，效果与上述两种链表分别一致

Thinking 2.3

Thinking 2.3

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

结合宏定义和如下的定义可知

struct Page_list{       // LIST_HEAD(Page_list, Page)
    struct {            // 自定义的 Page 类型
        struct {        // List_ENTRY(Page), Page 的指针域
            struct Page *le_next;
            struct Page **le_prev;
            } pp_link;  // field
        u_short pp_ref; // Page 的数据域
    }* lh_first;        // Page 的指针
}
/*
有一个叫 Page_lsit 的结构体，里面存放了一个 Page 类型变量的指针
有一个叫 Page 的结构体，里面存放了 pp_ref 和 pp_link 变量
有一个匿名结构体实例化为 pp_link 变量，里面存放了一个 Page 类型变量的指针和一个 Page 类型变量的指针的指针
*/

Thinking 2.4

Thinking 2.4 请思考下面两个问题：

请阅读上面有关 TLB 的描述，从虚拟内存和多进程操作系统的实现角度，阐述 ASID的必要性。

虚拟内存的设计初衷就是为了方便不同的程序方便地使用自己的内存空间而无需关注具体内存分配的实现，而多进程操作系统则对不同程序的隔离提出了更高的要求。因此，对于不同的进程(或程序)，都拥有各自的地址空间，同一虚拟地址对应的物理地址未必相同，通过 ASID 来区分地址空间对于多进程的并发执行相当必要，否则每执行一个程序都需要清空 TLB 使得 TLB 单独为其服务。

请阅读 MIPS 4Kc 文档《MIPS32® 4K™ Processor Core Family Software User’sManual》的 Section 3.3.1 与 Section 3.4，结合 ASID 段的位数，说明 4Kc 中可容纳不同的地址空间的最大数量。

ASID 有8位，故最多可容纳 256 个不同的地址空间。

Thinking 2.5

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

tlb_invalidate 和 tlb_out 的调用关系？

tlb_invalidate 调用 tlb_out

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

使 TLB 中的某些条目失效，避免访问到与内核页表不一致的物理页号和权限信息。

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

LEAF(tlb_out)   // 定义一个叶函数 tlb_out
.set noreorder  // 设置汇编器不进行指令重排序
    mfc0    t0, CP0_ENTRYHI // 将 CP0 中的 ENTRYHI 寄存器内容(当前的 VPN 和 ASID)读取到 t0 寄存器中，便于后续恢复
    mtc0    a0, CP0_ENTRYHI // 将 a0 寄存器中的参数(调用函数时传入的 VPN 和 ASID )存储到 CP0 中的 ENTRYHI 寄存器中
    nop // 插入空泡，解决冲突
    /* Step 1: Use 'tlbp' to probe TLB entry */
    /* Exercise 2.8: Your code here. (1/2) */
    tlbp    // 根据  CP0 中的 ENTRYHI寄存器 中的内容，探测 TLB 中与之匹配的表项，并将其索引存入 CP0 中的 INDEX 寄存器中(不存在则最高位置一)
    nop // 插入空泡，解决冲突
/* Step 2: Fetch the probe result from CP0.Index */
    mfc0    t1, CP0_INDEX   // 将  CP0 中的 INDEX 寄存器中的结果读取到 t1 寄存器中进行判断
.set reorder    // 设置汇编器可以进行指令重排序
    bltz    t1, NO_SUCH_ENTRY   // 若 t1寄存器中的值 小于 0，即 TLB 中不存在对应的索引，跳转到相应位置进行处理
.set noreorder  // 设置汇编器不进行指令重排序
    mtc0    zero, CP0_ENTRYHI   // 将 CP0 中的 ENTRYHI 寄存器设置为零，便于接下来清空 TLB
    mtc0    zero, CP0_ENTRYLO0  // 将 CP0 中的 ENTRYLO0 寄存器设置为零，便于接下来清空 TLB
    mtc0    zero, CP0_ENTRYLO1  // 将 CP0 中的 ENTRYLO1 寄存器设置为零，便于接下来清空 TLB
    nop // 插入空泡，解决冲突
    /* Step 3: Use 'tlbwi' to write CP0.EntryHi/Lo into TLB at CP0.Index  */
    /* Exercise 2.8: Your code here. (2/2) */
    tlbwi   // 将 CP0 中的 ENTRYHI 和 ENTRYLO0/1的内容写入到由INDEX寄存器指定的TLB条目中，清空 TLB 表项。
.set reorder    // 设置汇编器可以进行指令重排序

NO_SUCH_ENTRY:
    mtc0    t0, CP0_ENTRYHI // 将之前保存在 t0 寄存器中的原始 ENTRYHI 值写回到 CP0 的 ENTRYHI 寄存器。
    j       ra  // 函数结束，返回调用处
END(tlb_out)    // 函数结束

Thinking 2.6

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

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

X86体系结构中的内存管理机制相对复杂且灵活，它主要采用了分段式内存管理和物理地址扩展技术。分段式内存管理允许将内存划分为多个段，每个段都有一个基地址和长度。程序中的逻辑地址由段选择器和偏移量组成，通过段描述符表（GDT或LDT）和段选择子来转换为线性地址。这种机制提供了更大的内存空间，但也增加了内存管理的复杂性和访问延迟。

物理地址扩展技术是X86体系结构为了满足不同应用场景下的内存需求而发展出来的。最初的X86体系结构使用16位地址总线，只能寻址64KB的内存空间。然而，随着技术的发展和应用需求的增长，物理地址扩展技术被引入到X86体系结构中，使得地址总线扩展到32位和64位，可以寻址更大范围的内存空间，如4GB和16EB。

MIPS体系结构则采用了不同的内存管理机制。MIPS是一种精简指令集计算机（RISC）架构，其内存管理相对简单和直接。MIPS使用基于Load/Store的内存访问方式，即只有加载和存储指令能够直接访问内存，其他指令只能操作寄存器中的数据。MIPS没有显式的分段机制，而是通过虚拟内存和缓存机制来实现内存管理。它使用TLB（Translation Lookaside Buffer）来进行虚拟地址到物理地址的转换，以提高地址转换的速度。

在内存管理的区别上，X86和MIPS主要体现在以下几个方面：

地址空间与分段：X86通过分段式内存管理提供了更大的地址空间，而MIPS则没有显式的分段机制。X86的地址转换涉及段选择子和偏移量的计算，而MIPS则直接通过TLB进行虚拟地址到物理地址的映射。

复杂性与灵活性：X86的内存管理机制相对复杂，提供了更多的灵活性和配置选项，但也增加了实现的难度和成本。MIPS则追求简单和高效，其内存管理机制相对直接和简洁。

性能影响：X86的分段式内存管理可能会引入额外的内存访问延迟，尤其是在涉及跨段访问时。而MIPS的基于Load/Store的内存访问方式以及TLB的使用则有助于提高内存访问的速度和效率。

综上所述，X86和MIPS在内存管理上有着不同的设计和实现方式。X86通过分段式内存管理和物理地址扩展技术提供了更大的地址空间和灵活性，但也可能带来一定的性能开销。而MIPS则追求简单、高效的内存管理机制，通过基于Load/Store的访问方式和TLB的使用来优化内存访问性能。

Thinking A.1

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

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

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

(((PTbase >> 12) << 3 + PTbase) >> 12) << 3 + (PTbase >> 12) << 3 + PTbase

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

设三级页表页目录的基地址为 PDbase,即(((PTbase >> 12) << 3 + PTbase) >> 12) << 3 + (PTbase >> 12) << 3 + PTbase

(PDbase >> 12) << 3 + PTbase

难点分析

Exercise 2.1

Exercise 2.1 请参考代码注释，补全 mips_detect_memory 函数。

Step1: memsize 只需要忠实地使用 _memsize 进行赋值即可
Step2: (~~比较阴间的是~~)页大小 PAGE_SIZE 在 include/mmu.h 中定义，也可以使用 PGSHIFT 宏直接通过位运算来获取页数。

C语言拾遗(前面的教程根本没提到过)

#define PADDR(kva)\
({\
    u_long_a = (u_long)(kva);\
    if(_a<ULIM)\
        panic("PADDR called with invalid kva %08lx", _a);\
    _a - ULIM;\
})
#define KADDR(pa)\
({\
    u_long_ppn = PPN(pa);\
    if(_ppn >= npage){\
        panic("KADDR called with invalid pa %08lx", (u_long)pa);\
    }\
    (pa) + ULIM;\
})

在阅读这段物理地址和虚拟地址相互转换的代码时，我相当困惑，这个宏有返回值吗？在向无所不能的 AI 请教后，我才知道这个叫语句表达式，是 GNU C 对 C 语言标准做的扩展。允许在一个表达式里内嵌语句，允许在表达式内部使用局部变量、 for 循环和 goto 表达式，其格式为

({ 
    表达式1;
    表达式2;
    表达式3;
})

一对圆括号在外边，一对大括号在里面。
复合语句可以有函数调用、变量赋值甚至是控制流代码块。
最后一条语句必须以分号结尾。
最后一条语句的值，将作为整个表达式的值
如果大括号里的最后一句用的是没有返回值的语句，则整个表达式的返回类型为 void，即没有合法的返回值

Exercise 2.2

Exercise 2.2 完成 include/queue.h 中空缺的函数 LIST_INSERT_AFTER。

首先需要对 include/queue.h 中~~极其抽象~~的链表宏进行初步的理解。

LIST_HEAD(name, type):

定义了一个名为 name 的头部结构体，这个结构体有一个成员变量，lh_first是 type 类型变量的指针，用于指向链表中第一个 type 类型的变量。

1	LIST_HEAD(Page_list, Page);

LIST_HEAD_INITIALIZER(head):

初始化链表头(设置为空)。其实宏本身就是返回了 NULL ，并没有使用 head 变量。这个看似多余的变量实际上为未来扩展留下了余地。

1	Struct Page_list page_list = LIST_HEAD_INITIALIZER(page_list);

LIST_ENTRY(type):

使用了一个匿名结构体作为链表项。这个结构体含有两个成员变量， le_next 是 type 类型变量的指针，用于指向链表中下一个 type 类型变量； le_prev 是 type 类型变量的指针的指针，用于修改链表中前一个 type 类型变量的 le_next。

1	LIST_ENTRY(Page) a;

LIST_EMPTY(head):

判断指针 head 指向的头部结构体的链表头是否为空，其实就是判断 lh_first 是否为空。

1	if (LIST_EMPTY(&(page_free_list)))

LIST_FIRST(head):

返回指针 head 指向的头部结构体的链表第一个元素的指针。

1	pp = LIST_FIRST(&(page_free_list));

LIST_INIT(head):

初始化指针 head 指向的头部结构体的链表头为空。

1	LIST_INIT(&(page_free_list));

LIST_NEXT(elm, field):

返回指针 elm 指向的元素在对应链表中的下一个元素的指针，field 字段是在定义 elm 元素类型时，使用 LIST_ENTRY(type) 创建的链表项结构体的成员变量名。

1	p = LIST_NEXT(p, pp_link);

LIST_REMOVE(elm, field):

删除指针 elm 指向的元素再对应链表中的下一个元素，field 字段是在定义 elm 元素类型时，使用 LIST_ENTRY(type) 创建的链表项结构体的成员变量名。

1	LIST_REMOVE(pp, pp_link);

LIST_INSERT_HEAD(head, elm, field):

将指针 elm 指向的元素插入到指针 head 指向的头部结构体对应的链表的头部，field 字段是在定义 elm 元素类型时，使用 LIST_ENTRY(type) 创建的链表项结构体的成员变量名。

1	LIST_INSERT_HEAD(&(page_free_list), pp, pp_link);

LIST_INSERT_BEFORE(listelm, elm, field):

将指针 elm 指向的元素插入到指针 listelm 指向的元素所在的链表中，其中 elm 指向的元素是 listelm 指向的元素的前一个元素。field 字段是在定义 elm 元素类型时，使用 LIST_ENTRY(type) 创建的链表项结构体的成员变量名。

LIST_INSERT_AFTER(listelm, elm, field):

将指针 elm 指向的元素插入到指针 listelm 指向的元素所在的链表中，其中 elm 指向的元素是 listelm 指向的元素的后一个元素。field 字段是在定义 elm 元素类型时，使用 LIST_ENTRY(type) 创建的链表项结构体的成员变量名。

1	LIST_INSERT_AFTER(&test_pages[4], q, pp_link);

LIST_FOREACH(var, head, field):

遍历指针 head 指向的头部结构体对应的链表，其中 var 是一个已经声明好的链表元素结构体的指针变量，field 字段是在定义 elm 元素类型时，使用 LIST_ENTRY(type) 创建的链表项结构体的成员变量名。

这道题让我们自己实现 LIST_ISNERT_AFTER，因为这是个双向链表，我们就要对插入元素前后元素的链表项结构体中的 le_next 和 le_prev 进行修改。插在前面的话，就修改前面元素的 le_next 和后面元素(注意判断是否存在)的 le_prev，并对新插入元素的链表项进行赋值。

Exercise 2.3

Exercise 2.3 完成 page_init 函数。

初始化空闲页链表 page_free_list
将 freemem 按照页大小 PAGE_SIZE 进行对齐
把已使用的页(内核代码占用)引用次数标记为1。这里首先根据 freemem 计算已使用的页的个数，然后利用 Pages (已在 mips_vm_init 中申请空间)加偏移量，依次将这些页面的引用次数标记为1。
接着遍历 npage 页中剩下的页，将这些页面的引用次数标记为零，同时利用 LIST_INSERT_HEAD 将其插入到空闲页面链表中。

Exercise 2.4

Exercise 2.4 完成 page_alloc 函数。

page2ppn(struct Page *pp) :由页面指针获取物理页号
page2pa(struct Page *pp) :由页面指针获取物理地址
pa2page(u_long pa) :由物理地址获取页面指针
page2kva(struct Page *pp) :由页面指针获取内核虚拟地址
利用 LIST_EMPTY 判断 page_free_list 是否为空，为空则返回 -E_NO_MEM (定义在 include/error.h 中)，不为空则从 page_free_list 中获取第一个页面的指针，并将其从中删除。
利用 memset 将该页面对应的物理地址处的内容清空，并通过指针解引用赋值到调用者需要的地方

Exercise 2.5

Exercise 2.5 完成 page_free 函数。

利用 LIST_INSERT_HEAD 将该页面插入到空闲页面链表中即可。

Exercise 2.6

完成 pgdir_walk 函数。

利用 PDX 通过虚拟地址获得一级页表偏移量，与一级页表基地址相加获得一级页表项地址 pgdir_entryp
将一级页表项和 PTE_V 进行与运算，判断该页表项是否有效。若无效，则进一步判断 create 参数，若成立，则申请一块页面，申请成功则将该页面的引用次数加一，同时利用 page2pa获取该页面的物理地址，连通有效位、缓存位设置到一级页表项中，申请失败或者不成立则将 *ppte设置为 NULL。
若有效，则通过 PTE_ADDR 获得该一级页表项指向的页面的物理地址，也即对应的二级页表的物理地址，通过 KADDR 将物理地址转化为虚拟地址，将该虚拟地址加上 PTX 获得的二级页表内偏移量，即可获得对应的页表项的地址。注意 PTX 和 PDX 获得的偏移量均是以页表项的大小为单位，进行指针计算应注意指针指向类型的大小与之一致。

Exercise 2.7

Exercise 2.7 完成 page_insert 函数（补全 TODO 部分）。

因为要插入新的地址映射，所以先清空缓存(产生缺页中断后会重新载入)
通过 pgdir_walk(Pde *pgdir, u_long va, int create, Pte **ppte) 获得该虚拟地址指向的二级页表项，失败则返回异常值。(记得将 create 设置为1，当一级页表项无效时可以申请新的物理页面)
通过 page2pa 获取页面的物理地址，连同有效位、缓存位、权限位一同写入二级页表项中，同时将该页面的引用次数加一。

实验体会

最开始，实验代码相当令人困惑。不论是那些(~~感觉有点过度封装的~~)宏定义还是(~~奇奇怪怪的~~)函数调用，都很容易把人绕晕，不知道那些链表、指针、数组都有什么实际意义。尽管填写代码不是很难，但填完后对内存管理从哪里来、到哪里去仍然是一头雾水。因此，本次实验应该跳出代码层面去想一想，弄清楚每一步都要干什么，紧接着前面什么操作而来，为后面什么操作做了准备，理解每个数据结构、全局变量的意义，对内存管理顶层函数的调用熟稔于心。这样课上实验的时候才能灵活运用，不至于手忙脚乱(~~课上 exam 写了30分钟才发现写的不是题目要求的东西~~)。

人月神话

OS-Lab2