Lab2_实验报告

一、思考题

Thinking 2.1

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

Thinking 2.2

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

​ C 语言并没有泛型的语法，用宏来实现含有不同类型结构体的链表，可以提高代码的可重用性，可读性更高

  • 查看实验环境中的 /usr/include/sys/queue.h，了解其中单向链表与循环链表的实现，比较它们与本实验中使用的双向链表，分析三者在插入与删除操作上的性能差异
    图片
单向链表 循环链表 双向链表
Add before first node O(1) O(1) O(1)
Add before given node O(n) O(n) O(1)
Add after given node O(1) O(1) O(1)
Add after last node O(n) O(1) O(1)
delet first node O(1) O(1) O(1)
delet given node O(n) O(n) O(1)
delet last node O(n) O(n) O(1)

Thinking 2.3

通过下面的宏展开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//include/pmap.h
LIST_HEAD(Page_list, Page);
typedef LIST_ENTRY(Page) Page_LIST_entry_t;

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

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

可知正确答案为C：

1
2
3
4
5
6
7
8
9
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 的必要性。

​ ASID是用于标识此 TLB 条目与哪个进程相关。系统中并发执行多个拥有不同虚拟地址空间的进程，具有不同的页表。而 CPU 的 MMU 使用 TLB 缓存虚拟地址映射关系，不同页表拥有不同虚拟地址映射，不同进程的虚拟地址可以对应相同的虚拟页号。同时并发执行的多个进程具有不同 ASID 以方便 TLB 标识其虚拟地址空间。

(源自Lab3指导书^_^)

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

The purpose of the TLB is to translate virtual addresses and their corresponding Address Space Identifier (ASID) into a physical memory address. The translation is performed by comparing the upper bits of the virtual address**(along with the ASID bits) **against each of the entries in the tag portion of the JTLB structure.

In this figure the virtual address is extended with an 8-bit address-space identifier (ASID), which reduces the frequency of TLB flushing during a context switch. This 8-bit ASID contains the number assigned to that process and is stored in the CP0 EntryHi register.

ASID段共有8位，可以被设置为256个不同的值，因此4Kc中可最多容纳256个不同的地址空间。

Thinking 2.5

  • tlb_invalidate 和 tlb_out 的调用关系

​ tlb_invalidate 调用tlb_out

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

    tlb_invalidate 函数可以实现删除特定虚拟地址的映射，每当页表被修改，就需要调用该函数以保证下次访问相应虚拟地址时一定触发 TLB 重填，进而保证访存的正确性

  • 逐行解释 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
LEAF(tlb_out)
.set noreorder
        mfc0    t0, CP0_ENTRYHI  #ENTRYHI寄存器值存入t0寄存器
        mtc0    a0, CP0_ENTRYHI  #a0寄存器值存入ENTRYHI寄存器
        nop
        tlbp  #：根据EntryHi中的Key查找TLB中与之对应的表项，并将表项的索引存入 Index 寄存器
        nop
        mfc0    t1, CP0_INDEX  #INDEX寄存器值存入t1寄存器
.set reorder
        bltz    t1, NO_SUCH_ENTRY  #t1寄存器值(INDEX寄存器值)小于0，未找到匹配项，跳转到NO_SUCH_ENTRY
		nop
.set noreorder
        mtc0    zero, CP0_ENTRYHI  #EntryHi寄存器赋值为0
        mtc0    zero, CP0_ENTRYLO0  #EntryLo0寄存器赋值为0
        mtc0    zero, CP0_ENTRYLO1  #EntryLo1寄存器赋值为0
        nop
        tlbwi  #以Index寄存器中的值为索引，将EntryHi、EntryLo0、EntryLo1的值写到索引指定的 TLB 表项中
.set reorder

NO_SUCH_ENTRY:
        mtc0    t0, CP0_ENTRYHI  #t0寄存器值存入ENTRYHI寄存器
        j       ra  #函数返回
END(tlb_out)

Thinking 2.6

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

  • X86 体系结构中的内存管理机制：

    X86采用分段式分页式内存管理机制，将内存地址空间划分为多个段，每个段都有自己的基地址和界限，再将每个段进一步分割成固定大小的页面，通常为 4KB。分段和分页结合起来实现了更加灵活和高效的内存管理。

    X86 的内存管理由以下寄存器控制：

    段寄存器（DS、ES、SS、CS、FS、GS）：存储段的基地址

    页表寄存器（CR3）：存储页表的基地址

    页目录表寄存器（CR4）：存储页目录表的基地址

  • 比较 X86 和 MIPS 在内存管理上的区别：

    • X86主要采用的是段页式内存管理，MIPS主要采用的是页式内存管理
    • X86 的 TLB 是两级结构，而 MIPS 的 TLB 是一级结构
    • TLB未命中处理x86 使用硬件 MMU 直接访问页表并填充 TLB，MIPS 使用异常和内核的处理函数来填充 TLB
    • 转换失败的虚址，X86使用CR2存放，MIPS使用BadVAddr寄存器存放

Thinking A.1

在现代的64位系统中，提供了64位的字长，但实际上不是64位页式存储系统。假设在64位系统中采用三级页表机制，页面大小4KB。由于64位系统中字长为8B，且页目录也占用一页，因此页目录中有512个页目录项，因此每级页表都需要9位。因此在64位系统下，总共需要3 × 9 + 12 = 39位就可以实现三级页表机制，并不需要64位。现考虑上述39位的三级页式存储系统，虚拟地址空间为512GB，若记三级页表的基地址为PT_base，请你计算：

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

    页面目录(PDG) 中间目录(PMD) 页表(PT)

$$
第一个中间目录项对应第(PT_{base}>>12)页表项\
第一个中间目录项对应PT_{base}的偏移量(PT_{base}>>12)<<3 = (PT_{base}>>9)\
PMD_{base} = PT_{base}+(PT_{base}>>9)\
\
第一个页面目录项对应第(((PT_{base}>>9))>>12)中间目录项\
第一个页面目录项对应对应PMD_{base}的偏移量(PT_{base}>>12)<<3 = (PT_{base}>>9)\
PGD_{base} = PT_{base}+(PT_{base}>>9) + (PT_{base}>> 18)
$$

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

$$
第一个页面目录项对于PGD_{base}的偏移(PT_{base}>> 27)\
PGD_{self_mapping} = PT_{base}+(PT_{base}>>9) + (PT_{base}>> 18)+ (PT_{base}>> 27)
$$

二、实验难点

1.overview

实验总体流程调用函数的依赖关系如下图：

图片

2.链表宏和page结构体的对应关系

page_free_list 是struct Page_list

head 是struct Page_list * 故使用时应该 &page_free_list

var,listelm,elm 是struct Page *

field 是 pp_link

遍历链表如下操作

1
2
3
4
struct Page *tmp;
LIST_FOREACH(tmp, &page_free_list, pp_link) {
	//dosomething
}

3.二级页表地址变换机制

图片

虚拟地址是由MIPS 4Kc发出的“三段式”

而页表项内保存的是与物理地址有关的“两段式”

（差点混淆了T_T

三、实验体会

我曾经5次认为自己学会了二级页表！！！但每次再打开指导书对着代码细细品阅时，总是”别有一番收获“

所以Lab2教会我，要想真正学明白，要做到以下三点

  • 整体把握

    复习Lab2的时候，我在不同文件中苦苦穿梭，捋不清头绪。看完一篇学长博客之后，我惊叹于他对整体实验流程的把握，有感而发画下了实验难点中的overview图。在做Lab3的时候，我将会从更宏观的角度整体把握实验的运行逻辑与函数调度关系。

  • 面面俱到

    眼光只局限与实验代码给出的Your code here(x/x)填空，只是水过地皮草不湿，永远无法理解实验究竟在干什么。仔细品阅实验代码，精妙的TAILQ宏函数实现，passive_alloc为虚拟地址申请物理页时严谨的assert，都能带给我们美的享受和思维的提升。

  • 多多交流
    和舍友交流对于自映射和二级页表机制的理解时，我惊讶地发现，自己自成一套严谨逻辑的理解，原来是离题万里的谬误。闭门造车只会带来思路的闭塞，交流互鉴方能辩（and 辨）出真理