BUAA OS LAB2 实验报告

Thinking

Thinking 2.1

Q:

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

A:

实际程序中，访存、跳转等指令以及用于取指的PC寄存器中的访存目标地址都是虚拟地址。我们编写的C程序中中指针的值也是虚拟地址。

Thinking 2.2

Q:

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

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

A:

宏的的特性就是可重复使用。当这段代码的具体实现需要更改时，只需要改宏这一处就行。宏相比函数由于是字符串的替换，因此不必进行地址的跳转和栈的保存。

在实验环境中，只看到了单向链表、双向链表、单向队列、双向队列、循环队列，感觉循环队列在插入和删除操作方面和循环链表没太大差异，据此进一步分析。

插入操作：单向链表插入操作十分简单，两行代码，双向链表插入操作一般运行四行代码，需要额外判断是否next指向了NULL，循环链表与双向链表运行代码量基本相等，需额外判断是否next指向了头指针。特别的是，插入到头结点对三种链表而言性能相似，单向链表与双向链表插入到尾结点均要遍历完整个链表。

删除操作：单向链表的删除操作复杂度为O(n)，因为需要靠循环才能找到上一个链表节点的位置，双向链表及循环链表的删除操作与插入性能相近，也还是需要额外判断NULL或HEAD。删除头结点对三种链表而言性能相似，而单向链表与双向链表删除尾结点还是要遍历。

Thinking 2.3

Q：

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

1
2
3
4
5
6
7
8
9
10
A:
structPage_list{
struct {
struct{
structPage *le_next;
structPage *le_prev;
}pp_link;
u_shortpp_ref;
}*lh_first;
}
1
2
3
4
5
6
7
8
9
10
B:
structPage_list{
struct {
struct{
structPage *le_next;
structPage **le_prev;
}pp_link;
u_shortpp_ref;
} lh_first;
}
1
2
3
4
5
6
7
8
9
10
C:
structPage_list{
struct {
struct{
structPage *le_next;
structPage **le_prev;
}pp_link;
u_shortpp_ref;
}*lh_first;
}

A:

答案选C。Page_list中含有的是Page结构体指针头。每一个Page内存控制块都有一个pp_ref用于表示其引用次数（为0时便可remove)，还有一个结构体用于存放实现双向链表的指针。

Thinking 2.4

Q：

请思考下面两个问题：

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

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

A:

ASID的必要性：同一虚拟地址在不同地址空间中通常映射到不同物理地址，ASID可以判断是在哪个地址空间。例如有多个进程都用到了这个虚拟地址，但若该虚拟地址对应的数据不是共享的，则基本可以表明指向的是不同物理地址，这也是一种对地址空间的保护。

可容纳不同地址空间的最大数量：MIPS 4Kc处理器通过8位ASID字段，最多可支持256个不同的地址空间。

Thinking 2.5

Q：

请回答下述三个问题：

•tlb_invalidate和tlb_out的调用关系？

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

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

A:

tlb_invalidate调用tlb_out

调用tlb_invalidate可以将该地址空间的虚拟地址对应的表项清除出去，一般用于这个虚拟空间引用次数为0时释放tlb空间

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
 LEAF(tlb_out)
.set noreorder
	mfc0    t0,CP0_ENTRYHI  //保存ENTRIHI原有值
	mtc0    a0,CP0_ENTRYHI  //将传进来的参数放进ENTRYHI中
	nop
	/* Step 1: Use 'tlbp' to probe TLB entry */
	/* Exercise 2.8: Your code here. (1/2) */
	tlbp //检测ENTRYHI中的虚拟地址在tlb中是否有对应项
	nop
	/* Step 2: Fetch the probe result from CP0.Index */
	mfc0    t1, CP0_INDEX //INDEX可以用来判断是否命中
.set reorder
	bltz    t1, 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 //将清零后的两寄存器值写入到对应tlb表项中,相当于删除原有的tlb表项
.set reorder

NO_SUCH_ENTRY:
	mtc0    t0, CP0_ENTRYHI //将原来的ENTRYHI恢复
	j       ra //返回
END(tlb_out)

Thinking 2.6

Q：

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

A:

函数调用与CPU访存的关系总结

  1. 初始化阶段：
    通过env_setup_vm、page_alloc等函数构建进程的页表框架，为后续访存提供基础设施。
  2. 主动映射阶段：
    load_icode和map_segment预先建立关键映射（如代码段），减少运行时TLB未命中次数。
  3. 动态映射阶段：
    运行时未映射的虚拟地址访问触发do_tlb_refill，依赖passive_alloc和page_insert动态分配物理页并更新页表，体现“按需分配”特性。
  4. 一致性维护：
    映射变更后（如page_insert），通过tlb_invalidate确保TLB与页表一致，避免脏数据访问。

Thinking 2.7

Q：

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

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

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

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

A:

内存管理机制对比表（X86、MIPS、RISC-V、LoongArch）

特性 X86 MIPS RISC-V LoongArch
地址转换机制 分段 + 分页混合机制 纯分页机制 纯分页机制（支持 Sv32/Sv39/Sv48） 纯分页机制（多级页表）
分段机制 支持（强制逻辑地址分段） 无 无 无
分页机制 多级页表（32位二级，64位四级/五级） 固定页表结构（TLB映射） 灵活分页模式（Sv32/Sv39等） 多级页表（类似X86，支持大页）
TLB 管理 硬件自动处理 TLB 未命中 软件处理 TLB 未命中（异常机制） 可选硬件加速或软件处理 硬件辅助 TLB 填充（部分自动化）
权限控制 分段和分页双重保护（Ring 0~3） 分页权限位 + 固定内核/用户区域 分页权限位（U/S/M模式） 分页权限位 + 特权级隔离
物理地址扩展 PAE 或 64 位扩展（48~52位） TLB 条目扩展（支持40~64位） 分页模式扩展（如Sv39支持56位） 多级页表扩展（支持大物理地址）
地址空间划分 分段划分逻辑空间 固定内核/用户区域（如 kseg0） 灵活划分（用户/内核地址空间） 固定内核映射区域 + 用户空间
兼容性设计 保留分段以兼容历史架构 无历史包袱，设计简单 模块化设计，无历史兼容负担 自主研发，兼容性设计较少
典型应用场景 通用计算（PC/服务器） 嵌入式/早期游戏主机/路由器 嵌入式/IoT/新兴处理器 国产高性能计算/服务器

lab2难点

T1

除以页大小得到页数。

1
2
3
4
5
6
7
8
9
void mips_detect_memory(u_int _memsize) {
         /* Step 1: Initialize memsize. */
          memsize = _memsize;
  
          /* Step 2: Calculate the corresponding 'npage' value. */
          /* Exercise 2.1: Your code here. */
          npage = memsize / PAGE_SIZE;
          printk("Memory size: %lu KiB, number of pages: %lu\n", memsize / 1024, npage);
 }

T2

注意顺序，先将新添加的表项链接到前后，再修改原先的链接顺序。

注意prev指针指向的是前一项的next指针，是一个二重指针。

1
2
3
4
5
6
7
8
9
#define LIST_INSERT_AFTER(listelm, elm, field)                                                   \   
do {                                                                                    		\
                 LIST_NEXT((elm),field) = LIST_NEXT((listelm),field);                            \
                 if ((LIST_NEXT((listelm), field)) != NULL) {                                       \
			LIST_NEXT((listelm), field)->field.le_prev = &(LIST_NEXT((elm), field));   			\
														}            						\
                 LIST_NEXT((listelm),field) = (elm);      									  \
    			(elm)->field.le_prev = &LIST_NEXT((listelm),field);\
} while (0)

T3

page_free_list是一个page_list类型，该类型在宏定义里用PAGE_HEAD()定义为了一个链表头部。

PADDR()将虚拟地址转换为物理地址，

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
void page_init(void) {
	/* Step 1: Initialize page_free_list. */
	/* Hint: Use macro `LIST_INIT` defined in include/queue.h. */
	/* Exercise 2.3: Your code here. (1/4) */

	LIST_INIT(&page_free_list);

	/* Step 2: Align `freemem` up to multiple of PAGE_SIZE. */
	/* Exercise 2.3: Your code here. (2/4) */

	freemem = ROUND(freemem, PAGE_SIZE);

	/* Step 3: Mark all memory below `freemem` as used (set `pp_ref` to 1) */
	/* Exercise 2.3: Your code here. (3/4) */
	int size = PADDR(freemem) / PAGE_SIZE;
	int i;
	for (i = 0; i < size; ++i) {
		pages[i].pp_ref = 1;
	}

	/* Step 4: Mark the other memory as free. */
	/* Exercise 2.3: Your code here. (4/4) */
	for (i = size; i < npage; ++i) {
		pages[i].pp_ref = 0;
		LIST_INSERT_HEAD(&page_free_list, &pages[i], pp_link);
	}
}

T4

memset()需要的是虚拟地址，需要page2kva()将页转换为虚拟地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int page_alloc(struct Page **new) {
	/* Step 1: Get a page from free memory. If fails, return the error code.*/
	struct Page *pp;
	/* Exercise 2.4: Your code here. (1/2) */

	pp = LIST_FIRST(&page_free_list);
	if (pp == NULL) {
		return -E_NO_MEM;
	}

	LIST_REMOVE(pp, pp_link);

	/* Step 2: Initialize this page with zero.
	 * Hint: use `memset`. */
	/* Exercise 2.4: Your code here. (2/2) */

	memset(page2kva(pp), 0, PAGE_SIZE); // memset requests virtual address!!!!

	*new = pp;
	return 0;
}

T5

1
2
3
4
5
6
void page_free(struct Page *pp) {
	assert(pp->pp_ref == 0);
	/* Just insert it into 'page_free_list'. */
	/* Exercise 2.5: Your code here. */
	LIST_INSERT_HEAD(&page_free_list, pp, pp_link);
}

T6

如图，顺序已经十分清楚了。

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
32
33
34
35
36
static int pgdir_walk(Pde *pgdir, u_long va, int create, Pte **ppte) {
	Pde *pgdir_entryp;
	struct Page *pp;

	/* Step 1: Get the corresponding page directory entry. */
	/* Exercise 2.6: Your code here. (1/3) */

	pgdir_entryp = pgdir + PDX(va);

	/* Step 2: If the corresponding page table is not existent (valid) then:
	 *   * If parameter `create` is set, create one. Set the permission bits 'PTE_C_CACHEABLE |
	 *     PTE_V' for this new page in the page directory. If failed to allocate a new page (out
	 *     of memory), return the error.
	 *   * Otherwise, assign NULL to '*ppte' and return 0.
	 */
	/* Exercise 2.6: Your code here. (2/3) */

	if (!((*pgdir_entryp) & PTE_V)) {
		if (create) {
			try(page_alloc(&pp));
			*pgdir_entryp = page2pa(pp);
			*pgdir_entryp = (*pgdir_entryp) | PTE_C_CACHEABLE | PTE_V;
			pp->pp_ref++;
		} else {
			*ppte = 0;
			return 0;
		}
	}

	/* Step 3: Assign the kernel virtual address of the page table entry to '*ppte'. */
	/* Exercise 2.6: Your code here. (3/3) */
	*ppte = (Pte *)KADDR(PTE_ADDR(*pgdir_entryp)) + PTX(va);

	return 0;
}

T7

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
32
33
34
int page_insert(Pde *pgdir, u_int asid, struct Page *pp, u_long va, u_int perm) {
	Pte *pte;

	/* Step 1: Get corresponding page table entry. */
	pgdir_walk(pgdir, va, 0, &pte);

	if (pte && (*pte & PTE_V)) {
		if (pa2page(*pte) != pp) {
			page_remove(pgdir, asid, va);
		} else {
			tlb_invalidate(asid, va);
			*pte = page2pa(pp) | perm | PTE_C_CACHEABLE | PTE_V;
			return 0;
		}
	}

	/* Step 2: Flush TLB with 'tlb_invalidate'. */
	/* Exercise 2.7: Your code here. (1/3) */

	tlb_invalidate(asid, va);

	/* Step 3: Re-get or create the page table entry. */
	/* If failed to create, return the error. */
	/* Exercise 2.7: Your code here. (2/3) */
	try(pgdir_walk(pgdir, va, 1, &pte));

	/* Step 4: Insert the page to the page table entry with 'perm | PTE_C_CACHEABLE | PTE_V'
	 * and increase its 'pp_ref'. */
	/* Exercise 2.7: Your code here. (3/3) */
	*pte = page2pa(pp) | perm | PTE_C_CACHEABLE | PTE_V;
	pp->pp_ref++;

	return 0;
}

T8

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
LEAF(tlb_out)
.set noreorder
	mfc0    t0, CP0_ENTRYHI
	mtc0    a0, CP0_ENTRYHI
	nop
	/* Step 1: Use 'tlbp' to probe TLB entry */
	/* Exercise 2.8: Your code here. (1/2) */
	tlbp
	nop
	/* Step 2: Fetch the probe result from CP0.Index */
	mfc0    t1, CP0_INDEX
.set reorder
	bltz    t1, NO_SUCH_ENTRY
.set noreorder
	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
.set reorder

NO_SUCH_ENTRY:
	mtc0    t0, CP0_ENTRYHI
	j       ra
END(tlb_out)

T9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void _do_tlb_refill(u_long *pentrylo, u_int va, u_int asid) {
	tlb_invalidate(asid, va);
	Pte *ppte;
	/* Hints:
	 *  Invoke 'page_lookup' repeatedly in a loop to find the page table entry '*ppte'
	 * associated with the virtual address 'va' in the current address space 'cur_pgdir'.
	 *
	 *  **While** 'page_lookup' returns 'NULL', indicating that the '*ppte' could not be found,
	 *  allocate a new page using 'passive_alloc' until 'page_lookup' succeeds.
	 */

	/* Exercise 2.9: Your code here. */
	while (page_lookup(cur_pgdir, va, &ppte) == NULL) {
		passive_alloc(va, cur_pgdir, asid);
	}

	ppte = (Pte *)((u_long)ppte & ~0x7);
	pentrylo[0] = ppte[0] >> 6;
	pentrylo[1] = ppte[1] >> 6;
}

T10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
NESTED(do_tlb_refill, 24, zero)
	mfc0    a1, CP0_BADVADDR
	mfc0    a2, CP0_ENTRYHI
	andi    a2, a2, 0xff /* ASID is stored in the lower 8 bits of CP0_ENTRYHI */
.globl do_tlb_refill_call;
do_tlb_refill_call:
	addi    sp, sp, -24 /* Allocate stack for arguments(3), return value(2), and return address(1) */
	sw      ra, 20(sp) /* [sp + 20] - [sp + 23] store the return address */
	addi    a0, sp, 12 /* [sp + 12] - [sp + 19] store the return value */
	jal     _do_tlb_refill /* (Pte *, u_int, u_int) [sp + 0] - [sp + 11] reserved for 3 args */
	lw      a0, 12(sp) /* Return value 0 - Even page table entry */
	lw      a1, 16(sp) /* Return value 1 - Odd page table entry */
	lw      ra, 20(sp) /* Return address */
	addi    sp, sp, 24 /* Deallocate stack */
	mtc0    a0, CP0_ENTRYLO0 /* Even page table entry */
	mtc0    a1, CP0_ENTRYLO1 /* Odd page table entry */
	nop
	/* Hint: use 'tlbwr' to write CP0.EntryHi/Lo into a random tlb entry. */
	/* Exercise 2.10: Your code here. */
	tlbwr
	jr      ra
END(do_tlb_refill)

实验体会总结

这次实验最麻烦的一点是信息量巨大，需要看懂许多的结构体和定义函数的使用方法，而且还有物理地址、虚拟地址、二级页表页号等的转换，TLB也是涉及大量地址转换。

体会：

  • 需要多看课程组的Hint，好几个不知道值的参数都是宏定义
  • 一般情况下用的都是虚拟地址，只有填入内容才会使用物理地址
  • 对于c语言结构体和指针的使用需要熟悉