思考题

Thinking 2.1

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

在编写的 C 程序中，指针变量中存储的地址 被视为虚拟地址。

MIPS 汇编程序中 lw 和 sw 指令使用的地址被视为虚拟地址。

Thinking 2.2

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

​ 指导书中提到：“C++ 中可以使用 std::stack 定义一个类型为 T 的栈，Java 中可以使用 HashMap 定义一个键类型为 K 且值类型为 V 的哈希表。这种模式称为泛型，C 语言并没有泛型的语法，因 此需要通过宏另辟蹊径来实现泛型。”

​ 我认为用宏来实现链表的好处主要是：实现泛型。宏定义实现链表，用参数type来表示结构体类型，这样就可以针对不同的数据结构使用同样的链表代码，可重用性更高。

​ 除此之外，field的设计也十分巧妙，利用==字符串字面量的替换==，使得其能代表所有结构结构体的所有成员变量，提高了宏的可重用性

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

循环列表的各种插入和删除操作都是O（1），时间性能最好；但是空间开销大

单项列表空间性能好，但是在前插、尾插、非头部节点删除等操作上的时间复杂度都是O（n），时间性能最差

而双向链表只有在进行尾部插入删除时时间复杂度较高，综合起来考虑：

时间性能：循环列表 > 双向链表 > 单项链表

空间性能：单项链表 > 双向链表 > 循环链表

Thinking 2.3

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

image-20240410230238608

C是正确的展开结构

  • Page_list是链表头部结构体HEAD，其中包含了一个指向链表第一个元素的指针lh_first，在这里类型为Page*
  • lh_first指向链表第一个元素结构体Page，内部包含一个数据pp_ref和一个结构体pp_link
    • pp_ref用于记录该Page的被引用次数
    • pp_link的类型是Page_LIST_entry_t，根据宏定义” typedef LIST_ENTRY(Page) Page_LIST_entry_t “ 可知，pp_link实际上是由宏LIST_ENTRY(Page)生成的一个特殊结构体，内部包含两个指针struct Page *le_next和struct Page **le_prev

Thinking 2.4

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

​ 不同进程之间，共享相同的物理地址空间，但是不共享虚拟地址空间。每个进程都存在独立的 虚拟地址空间->物理地址空间 的映射。也就是说，在不同进程之间，一个虚拟地址可能对应不同的物理地址。

​ 如果不采用ASID，在多进程的情况下，每次进程发生切换都需要查找与旧进程地址空间相关的所有TLB转换并使其无效，这样会导致切换的效率变低。为了解决这个问题，引入了ASID，用于标识地址空间的ID。

​ 设置了进程的ASID之后，MMU在查找TLB时，只会查找对应ASID的TLB行；切换进程时，设置了ASID的TLB行不会被清理掉，TLB中就可以缓存不同进程的页表，在减少TLB清理的同时，保证了权限的隔离。

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

![image-20240411120810643](C:\Users\86199\Documents\A blog\myblog\source_posts\image-20240411120810643.png)

每个ASID唯一标识一个进程，从图中可知ASID共有8位，则4Kc中可容纳不同地址空间的最大数量是 $2^8 = 256$ 个

Thinking 2.5

tlb_invalidate 和 tlb_out 的调用关系？

tlb_inbalidate里面调用了tlb_out，实际上，tlb_invalidate的主要功能就是利用tlb_out实现的

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

让特定进程对应页表中指定虚拟地址va对应的tlb表项失效，删除该虚拟地址映射

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

tlb_out函数存在于tlb_asm.S文件中，这个文件include的头文件是asm.h，我们通过查看相关的头文件，可以知道tlb_out里面使用的宏的定义

在cp0regdef.h中：

1
2
3
4
5
#define CP0_INDEX $0
#define CP0_ENTRYLO0 $2
#define CP0_ENTRYLO1 $3
#define CP0_CONTEXT $4
#define CP0_ENTRYHI $10

在asm.h中：

1
2
3
4
5
6
7
8
9
10
11
#define LEAF(symbol)             \
	.globl symbol;               \
	.align 2;                    \
	.type symbol, @function;     \
	.ent symbol;                 \
	symbol:                      \
	.frame sp, 0, ra
	
#define END(function)            \
	.end function;               \
	.size function, .- function

regdef.h中则定义了常见的寄存器名称，在此列举tlb_out中用到的部分：

1
2
3
4
5
#define zero $0 /* wired zero */
#define a0 $4 /* argument registers */
#define t0 $8 /* caller saved */
#define t1 $9
#define ra $31 /* return address */

使用到的TLB相关指令（摘自指导书）：

  • tlbp：根据 EntryHi 中的 Key（包含 VPN 与 ASID），查找 TLB 中与之对应的表项，并将 表项的索引存入 Index 寄存器（若未找到匹配项，则 Index 最高位被置 1）。
  • tlbwi：以 Index 寄存器中的值为索引，将此时 EntryHi 与 EntryLo0、EntryLo1 的值写 到索引指定的 TLB 表项中。

tlb_out的主要作用是：接受一个参数，保存在a0（也就是$4）寄存器中，将这个参数对应的tlb表项置0

下面逐行解释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
31
LEAF(tlb_out)
.set noreorder
	mfc0    t0, CP0_ENTRYHI //把CP0_ENTRYHI寄存器的值保存在t0中
	mtc0    a0, CP0_ENTRYHI //把接受的参数从a0存入CP0_ENTRYHI中
	nop
	/* Step 1: Use 'tlbp' to probe TLB entry */
	/* Exercise 2.8: Your code here. (1/2) */
	tlbp //查询CP0_ENTRYHI中参数在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 //将Index中的结果与 0 ⽐较，判断有没有查到，如果没查到Index最⾼位被置1，就会⼩于0
.set noreorder
	// 如果查到了，将ENTRYHI、ENTRYLO0、ENTRYLO1清零
	mtc0    zero, CP0_ENTRYHI
	mtc0    zero, CP0_ENTRYLO0
	mtc0    zero, CP0_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 和 EntryLo 的内容写入index 对应的 tlb条⽬

.set reorder

NO_SUCH_ENTRY: // 如果没有查到
	mtc0    t0, CP0_ENTRYHI //将原来的ENTRYHI恢复
	j       ra //返回
END(tlb_out)

Thinking 2.6

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

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架构的保护模式下的内存管理中，分段是强制的，并不能关闭，而分页是可选的；

难点分析

难点太多一时不知从何说起）就把我最困惑的几个点稍微总结一下叭

双向链表的理解

​ 第一个卡住我的点就是实现LIST_INSERT_AFTER，一开始看指导书没太看明白节点和指针之间的指向关系，（最主要的是没理解那个指向自己的指针），后来看了讨论区里面发布的往年精品帖才搞懂指针之间的关系。

  • prev是struct Page**,保存next的地址；next是struct Page *,保存结构体的地址；作用是remove节点时避免遍历双向链表

field的理解

​ 由于对宏的理解不深刻，一直没搞明白field到底是个什么东西（x），直到后来问了助教才知道这个地方是字符串字面量的替换。就是调用的时候填入的是什么，field就会被替换成填入的结构体成员变量名称（例如pp_link）。

地址和页号等的转换不熟练

​ 一开始没理清楚pde pte pgdir pa va等等之间的关系，所以看代码的时候非常痛苦，每次遇到都要去看一遍头文件，后来在学长博客里面看到一张画的很好的图！感谢学长的馈赠（图片放在这里再膜拜一遍）

![地址转换图](C:\Users\86199\Documents\A blog\myblog\source_posts\地址转换图.png)

实验体会

​ 代码在实现逻辑上并没有很难理解的部分，主要是陌生概念太多，需要对各种概念理解比较透彻，才能看懂这部分想要干什么。

​ 对于我这种记忆力不够强的菜菜是比较大的挑战（x）经常看了后面忘记前面 QAQ 不过有学长博客、讨论区和讲解的帮助还是挺过来了！！！

​ 特别是看指导书的过程中，经常会感觉东西比较零碎，需要人为去梳理一遍逻辑，加深对知识的理解。不过搞明白之后还是很有成就感的说

函数整理

page_alloc

  • 声明： page_alloc(struct Page **pp)
  • 作用：从page_free_list中获取一个物理页分配给pp
  • 调用：panic_on(page_alloc(&p));