OS-Lab2

Lab2实验报告

一、思考题

Thinking 2.1

答：虚拟地址。

Thinking 2.2

答：

使用宏来实现列表，增加了代码的可复用性和可读性。

单向链表：如果是删除项或者在某一项前插入项，则需要从头遍历链表。而如果是在某一项后插入项则可以直接插入。

循环链表：同样是单向的，因此删除和插入与单向链表相同。但由于其首尾相连，因此直接可以在链表尾部插入。

双向链表：元素可以获得其前后两项。因此删除和前后插入时间复杂度为O(1)。

Thinking 2.3

答:C是正确展开结构。pp_link是List_Entry链表项，而lh_first应当指向结构体的地址，所以是指针。

Thinking 2.4

答：

1.同一虚拟地址在不同的地址空间中通常映射到不同的物理地址。如果没有ASID加以区分地址空间，则一般情况下虚拟地址都会被映射到错误的物理地址。

2.ASID占6位，可有2^6 = 64个值，因此R3000中可容纳最多64个不同地址空间。

Thinking 2.5

答：

1.tlb_invalidate调用了tlb_out.

2.在页表更新时如果存在对应旧页表项则将其删除。

3.首先将查找的虚拟地址存入EntryHi寄存器，之后调用tlbp进行查找。查找过后将索引写入CP0的Index中。

如果索引值小于0（即没有找到），则直接跳转至最后。如果索引值大于等于0，则将索引对应的TLB清空（即向 EntryHi 和EntryLo 中写入 0, 随后使用 tlbwi 指令，将 EntryHi 和 EntryLo 中的值写入索引指定的表项）。在函数最后需要将EntryHi寄存器中的值恢复为原值。

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
	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)

Thinking 2.6

MIPS主要采用页式管理系统，而X86采用段页式管理系统。

TLB不命中时，X86由硬件MMU以CR3为当前进程的PGD基址，索引获得PFN后，直接输出PA。于此同时MMU会填充TLB以加快下次转换的速度。而MIPS 会触发TLB Refill 异常，内核的 tlb_refill_handler 会以 pgd_current 为当前进程的 PGD 基址，索引获得转换失败的虚址对应的 PTE，并将其填入TLB，然后CPU再用刚刚转换失败的虚拟地址重新访问以下TLB。

Thinking A.1

答：

总虚拟地址空间为512G = 0x8000000000

页面大小为4KB,字长为8B，因此每级页目录中也页表项个数为4KB/8B = 512项

因此3级页表项总数为2^27 项，每项对应大小为0x8000000000 / 2^27 = 0x1000

第三级页表项对应第二级页表项为 PTbase / 0x1000 个页表项

第三级页表占用空间为 2^27 * （64 / 8） = 0x40000000

第三级页表对应第二级页表目录项为（64 / 8）* PTbase / 0x1000

第二级页表项基地址（三级页表页目录的基地址）为PMDbase = PTbase + （64 / 8）* PTbase / 0x1000

第二级页表总页表项个数： 5122 = 218 (项)

每个页表项对应地址空间大小： 0x400000000 / 218 = 0x1000

第二级页表对应一级页表项： 第 (PMDbase - PTbase) / 0x1000 个页表项

第二级页表占用空间： (64 / 8) * 218 = 0x200000

第二级页表对应地址空间： (PMDbase) ~ (PMDbase + 0x200000)

第二级页表对应第一级页表页目录项： (64 / 8) * ((PMDbase - PTbase) / 0x1000)

因此第一级页表项基地址： PGDbase = (PMDbase + (64 / 8) * ((PMDbase - PTbase) / 0x1000))

第一级页表总页表项个数： 512 = 29 (项)

每个页表项对应地址空间大小： 0x200000 / 29 = 0x1000

第一级页表对应根页表项： 第 (PGDbase - PMDbase) / 0x1000 个页表项

第一级页表占用空间： (64 / 8) * 29 = 0x1000

第一级页表对应地址空间： (PGDbase) ~ (PGDbase + 0x1000)

因此，映射到页目录自身的页目录项的地址为 PGDbase + (64 / 8) * ((PGDbase - PMDbase) / 0x1000)

二、实验难点

1.针对MOS中实现的链表的理解

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

以上是针对链表的定义。

可以看出这个链表是双向的链表。但是其与普通双向链表有所不同。一般双向链表的元素可以直接访问其前后的元素，而这个链表的元素智能直接访问其后的元素，但不能直接访问其前面的元素。但le_prev的加入使得此链表可在O(1)的开销下进行链表的增删操作。

2.针对页表查询机制的理解

在实验中，我们使用二级页表查询机制实现内存管理。其原理就是使用页表的页表进行索引，通过减少页表数量减少页表对内存的占用。

如图所示，虚拟地址为32位，其被分为3个部分，分别为：

1.一级页表偏移量（31-22位），通过此表项号取得一级页表基地址，其中一级页表存放二级页表的首地址。

2.二级页表偏移量（21-12位），通过此表项号取得二级页表基地址，其中二级页表存放虚拟地址对应物理页框的首地址。

3.页内偏移量（11-0位），通过此表项号取得物理页框内偏移量，将物理页框首地址与偏移量相加得到所求物理地址。

三、心得体会

本次实验代码阅读量较大，理解定义函数与宏之后进行操作更加轻松。

本次实验主要学习操作系统启动时内存调用管理，并且了解虚拟内存以及TLB管理机制。

实验消耗时间较上次增加很多，但深入理解了指针与操作系统内存管理等内容，总体来讲获益很多。