os-lab2

本文最后更新于 2024年9月6日 下午

1.思考题

2.1

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

2.2

使用宏来实现链表具有以下好处：
用宏实现链表，可以避免重复劳动，因为宏没有规定返回值的类型。
2.
单向链表的插入操作的时间复杂度为O(1)，删除操作的时间复杂度为O(n)；
循环链表的插入操作的时间复杂度为O(1)，删除操作的时间复杂度为O(n)；
双向链表的插入操作的时间复杂度为O(1)，删除操作的时间复杂度为O(1)；

2.3

正确的结构选C

2.4

  • ASID可以唯一标识每个进程，可以为该进程提供地址空间保护，当TLB尝试解析虚拟页码时，它确保当前正在运行的进程的ASID与与虚拟页面关联的ASID匹配。
  • 同时也使得不同的虚拟地址空间可以映射到同一块物理地址，有利于提高CPU的利用率。

4kc中ASID的位数为8位，说明可容纳不同地址的空间的最大数量位为$2^8$

2.5

tlb_invalidate 调用了tlb_out
tlb_invalidate 函数实现删除特定虚拟地址在TLB
中的旧表项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
LEAF(tlb_out)
.set noreorder
 mfc0    t0, CP0_ENTRYHI //将 EntryHi中key加载到寄存器t0中
 mtc0    a0, CP0_ENTRYHI//将旧表项Key写入EntryHi
 nop//空指令
 tlbp //根据EntryHi中的Key查找对应的旧表项，将表项的索引存入Index
 nop//空指令
 mfc0    t1, CP0_INDEX //将旧表项的索引存入t1寄存器
.set reorder
 bltz    t1, NO_SUCH_ENTRY //如果t1的值为负，则跳转到标签NO_SUCH_ENTRY处
.set noreorder
 mtc0    zero, CP0_ENTRYHI //否则，向EntryHi寄存器写入0
 mtc0    zero, CP0_ENTRYLO0//向EntryLo0寄存器写入0
 mtc0    zero, CP0_ENTRYLO1//向EntryLo1寄存器写入0
 nop   //空指令
 tlbwi //将EntryHi和EntryLo0、EntryLo1中的值写入索引指定的表项
.set reorder

2.6

  • MIPS主要采用的是页式管理系统，X86主要采用的是段页式。

  • MIPS 会触发TLB Refill 异常，内核的 tlb_refill_handler 会以 pgd_current 为当前进程的 PGD 基址，索引获得转换失败的虚址对应的 PTE，并将其填入 TLB，完了CPU 把刚刚转换失败的虚地址再走一下 TLB 就OK了。而 X86 在 TLB 不命中时，是由硬件 MMU 以 CR3 为当前进程的 PGD 基址，索引获得 PFN 后，直接输出 PA。同时 MMU 会填充 TLB 以加快下次转换的速度。

  • 另外转换失败的虚址，MIPS 使用 BadVAddr 寄存器存放，X86 使用 CR2 存放。

2.7

三级页表页目录的基地址为：
$PT_{base}|PT_{base}>>9|PT_{base}>>18$

映射到页目录自身的页目录项:
$PT_{base}|PT_{base}>>9|PT_{base}>>18|PT_{base}>>27$

难点分析

  1. 对于双向链表的理解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define LIST_HEAD(name, type)                                                                      \
 struct name {                                                                              \
  struct type *lh_first; /* first element */                                         \
 }
#define LIST_ENTRY(type)                                                                           \
 struct {                                                                                   \
  struct type *le_next;  /* next element */                                          \
  struct type **le_prev; /* address of previous next element */                      \
 }

LIST_HEAD(Page_list, Page);
typedef LIST_ENTRY(Page) Page_LIST_entry_t;

struct Page {
 Page_LIST_entry_t pp_link; /* free list link */

 // Ref is the count of pointers (usually in page table entries)
 // to this page.  This only holds for pages allocated using
 // page_alloc.  Pages allocated at boot time using pmap.c's "alloc"
 // do not have valid reference count fields.

 u_short pp_ref;
};

根据上述定义代码可以很好的理解页中双向链表的结构。

  1. 难点在于二级页表的查询机制和相关函数的理解：

    重点在于对pgdir_walk函数的理解，该函数构建了虚拟地址对应的一级页目录项和二级页表的对应关系。其中对于指针所指向的地址理解也十分重要

    参考上图
    pgdir代表的是一级页表基地址
    pgdir_entryp则是代表查询的页目录项地址
    *pgdir_entryp存的则是对应二级页表的物理页号和权限位
    *ppte存的则是该页对应的二级页表项的地址。

实验体会

lab2实验的整体难度较高，涉及了mips的内存管理。尤其是其中的二级页表和快表机制在实际写代码时比较绕，自映射也很难理解，花费了大量时间和精力理解。同时需要完成的内容较多，主要涉及了c语言的指针，容易搞混。