OS-lab2

一、思考题

Thinking 2.1

请根据上述说明，回答问题：

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

答：

虚拟地址。自身所写的程序的指针储存地址为映射到进程地址空间的偏移地址，不同进程地址空间是相互隔离的，不同进程两个值相同的指针对应的真实内存是不同的
虚拟地址。其地址为32位而物理地址为64位

Thinking 2.2

请思考下述两个问题：

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

答：

1. 简化代码量
2. 复杂宏大量调用简单宏可重用性强，可读性强，易于维护
单向链表

对于单纯的插入和删除操作只有O(1)的时间复杂度，但是对于任意第 i 个元素的插入和删除操作来说，则需要从头遍历一遍故而时间复杂度会上升到O(n);
双向链表

对于任意第 i 个元素的插入和删除操作时间复杂度都只有O(1)；
循环链表
- 单向循环链表
  
  和单向链表一样，对于任意第 i 个元素的插入和删除操作来说，时间复杂度会为O(n);
- 双向循环链表
  
  和双向链表一样，对于任意第 i 个元素的插入和删除操作来说，时间复杂度会为O(1)。

Thinking 2.3

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

答：

首先我们可在include/pmap.h中观察到Page(与真实物理页面相区别，而Page管理一个页面)：

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

又知道Page_LIST_entry_t在宏定义typedef LIST_ENTRY(Page) Page_LIST_entry_t;中声明，查看LIST_ENTRY在queue.h中声明如下:

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

现在可以确定Page的结构：

struct Page {
    struct {                                                               
                struct type *le_next; 
                struct type **le_prev;
        } pp_link;
    u_short pp_ref;
};

在pmap.h中声明的IST_HEAD(Page_list, Page)完成了Page_list的构建如下：

struct Page_list { 
    struct Page *lh_first;                      
}

可知这个lh_first相当于链表头head，综上Page_list的结构如C选项所示。

Thinking 2.4

请思考下面两个问题：

请阅读上面有关 TLB 的描述，从虚拟内存和多进程操作系统的实现角度，阐述 ASID 的必要性。
请阅读 MIPS 4Kc 文档《MIPS32® 4K™ Processor Core Family Software User’s Manual》的 Section 3.3.1 与 Section 3.4，结合 ASID 段的位数，说明 4Kc 中可容纳不同的地址空间的最大数量。

答：

ASID的必要性：

为了提高TLB的性能，将TLB分成Global和process-specific。global 是指常驻在TLB中不会被刷出的，例如内核空间的翻译，process-specific 是指每个进程独有的地址空间，当发生进程切换的时候，这部分TLB可以被刷出，为了支持process-specific的tlb，arm提出了ASID（Adress Space ID）的硬件解决方案，这样TLB就可以识别出这个 TLB 页表项是属于哪一个进程的，这样就不用每次切换进程都要 flush 所有 TLB。
在 MIPS 中，每一个TLB表项会有一个ASID，标识这个表项是属于哪一个进程的。例如有多个进程都需要使用这个虚拟地址，但若该虚拟地址对应的数据不是共享的，此时该表项不是global项且ASID与CP0_EntryHi的ASID也不一样，表明它们指向的是不同物理地址，需要使此次访问缺失，以保护相应的地址空间。

可容纳不同地址空间的最大数量：64个，参考原文如下：

Instead, the OS assigns a 6-bit unique code to each task’s distinct address space. Since the ASID is only 6 bits long, OS software does have to lend a hand if there are ever more than 64 address spaces in concurrent use; but it probably won’t happen too often.

Thinking 2.5

请回答下述三个问题：

tlb_invalidate 和 tlb_out 的调用关系？
请用一句话概括 tlb_invalidate 的作用。
逐行解释 tlb_out 中的汇编代码。

答:

tlb_invalidate函数内部调用tlb_out函数。
tlb_invalidate函数就是用tlb_out()把虚拟地址va对应的tlb页表项清空。
tlb_out该函数根据传入的参数（TLB 的 Key）找到对应的 TLB 表项，并将其清空

在解释tlb_out 中的汇编代码之前，我们先了解一下有关TLB的相关命令

tlbr：以 Index 寄存器中的值为索引,读出 TLB 中对应的表项到 EntryHi 与 EntryLo。

tlbwi：以 Index 寄存器中的值为索引,将此时 EntryHi 与 EntryLo 的值写到索引指定的 TLB 表项中。

tlbwr：将 EntryHi 与 EntryLo 的数据随机写到一个 TLB 表项中（此处使用 Random 寄存器来“随机”指定表项，Random 寄存器本质上是一个不停运行的循环计数器）。

tlbp：根据 EntryHi 中的 Key（包含 VPN 与 ASID），查找 TLB 中与之对应的表项，并将表项的索引存入 Index 寄存器（若未找到匹配项，则 Index 最高位被置 1）。

现在我们仔细研究一下tlb_out函数：

#include <asm/regdef.h>
#include <asm/cp0regdef.h>
#include <asm/asm.h>
LEAF(tlb_out)
    nop
    //首先将CP0_ENTRYHI中原有的值写入k1寄存器
    mfc0    k1,CP0_ENTRYHI
    //将传入的参数（待清空表项的key）写到CP0_ENTRYHI中
    mtc0    a0,CP0_ENTRYHI
    nop
    //根据 EntryHi 中的 Key，查找 TLB 中与之对应的表项，并将表项的索引存入 Index 寄存器，（若未找到匹配项，则 Index 最高位被置 1）。
    tlbp
    //防止冲突
    nop
    nop
    nop
    nop
    //取出CP0_INDEX的值
    mfc0    k0,CP0_INDEX
    //如果是Index 最高位被置 1，表明没找到，跳到 NOFOUND 标签处，(因为此时相当于已经完成了清空工作)
    //如果找到了，Index 最高位为0，继续执行
    bltz    k0,NOFOUND
    nop
    //为清空做准备，CP0_ENTRYHI，CP0_ENTRYLO全部填入0
    mtc0    zero,CP0_ENTRYHI
    mtc0    zero,CP0_ENTRYLO
    nop
    //根据找到的Index将此时 EntryHi 与 EntryLo 的值写到索引指定的 TLB 表项中，即完成清空
    tlbwi
NOFOUND:
		 //复原现场（将原来的key写会CP0_ENTRYHI）
    mtc0    k1,CP0_ENTRYHI
    //跳回被调用的地方
    j   ra
    nop
END(tlb_out)

Thinking 2.6

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

简单了解并叙述 X86 体系结构中的内存管理机制，比较 X86 和 MIPS 在内存管理上的区别。
简单了解并叙述 RISC-V 中的内存管理机制，比较 RISC-V 与 MIPS 在内存管理上的区别。
简单了解并叙述 LoongArch 中的内存管理机制，比较 LoongArch 与 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架构的保护模式下的内存管理中，分段是强制的，并不能关闭，而分页是可选的；

二、实验难点

lab2比前两次lab的难度都提高了很多，从理解和补全代码时都遇到了不小的困难，下面依然按照八个Exercise的顺序逐个分析难点

Exercise 2.1 mips_detect_memory ()

mips_detect_memory()函数用于探测硬件可用内存。本函数其实很简单，首先传进来的参数代表总物理内存字节数，只需要除以每个页面的大小就可以得到总物理页数npage，每个物理页面的大小PAGE_SIZE我们可以再mmu.h中找到。

Exercise 2.2 LIST_INSERT_AFTER

在2.2之前，介绍了一些对链表操作的宏，包括创建，插入，删除等操作。在这里，我们要补全LIST_INSERT_AFTER，它的作用是将 elm 插到已有元素 listelm 之后。

首先，我们先了解一下这个链表的类型，如下：

链表包括指向下一个元素的指针 le_next，以及指向前一个元素链表项 le_next 的指针 le_prev。le_prev 是一个指针的指针，它的作用是当删除一个元素时，更改前一个元素链表项的 le_next。

之后的补全代码部分其实就是大一数据结构学习的链表内容，将需要改动的三个元素的le_next和le_prev进行相应修改即可

注意的是由于是#define块，除了最后一行外每一行的后面都需要加上/

Exercise 2.3 page_init

该函数的作用是来初始化物理页面管理，执行一下操作：

使用链表初始化宏 LIST_INIT。
将 freemem 按照 PAGE_SIZE 进行对齐（使用 ROUND 宏为 freemem 赋值）。
将 freemem 以下页面对应的页控制块中的 pp_ref 标为 1。
将其它页面对应的页控制块中的 pp_ref 标为 0 并使用 LIST_INSERT_HEAD 将其插入空闲链表。

该部分的代码填写只需按照操作要求一步步补全，从而实现了将freemem前地址( KSEG0 到 freemem )对应所有的页的pp_ref 标为 1，freemem之后地址的pp_ref 标为 0，同时插入空闲链表，便于后续取出空闲页。

Exercise 2.4 page_alloc

该函数的作用就是从空闲页链表中取出一页交给传进的参数

具体操作就是：

如果空闲页表没有空闲页，就返回异常返回值-E_NO_MEM
有空闲页就取出一页，清空该页后赋给*new，同时将该页在空闲链表中删去

Exercise 2.5 page_free

非常简单的一个函数，就是将要free页的pp_ref 标为 0，再插入到空闲链表中

Exercise 2.6 pgdir_walk

这个Exercise用于虚拟内存管理，首先我们先来了解一下位于 kuseg 的虚拟地址的两级页表结构如下：（一级页表指代 Page Directory，二级页表指代 Page Table)

那么pgdir_walk函数的作用是将一级页表基地址 pgdir 对应的两级页表结构中 va 虚拟地址所在的二级页表项的指针存储在 ppte 指向的空间上。如果 create 不为 0 且对应的二级页表不存在，则会使用 page_alloc 函数分配一页物理内存用于存放二级页表，如果分配失败则返回错误码，具体流程如下图：

我们先用一级页表基地址加上偏移量，得到指向一级页表项的指针，取值得到该页表项。如果该页表项无效（存在对应的二级页表），那么如果create为1就调用page_alloc给他分配一页，如果为0就给*ppte赋值NULL。

如果存在对应的二级页表，那么就将页表项转换为虚拟地址返回，具体转化过程为：

*ppte = (Pte *)KADDR(PTE_ADDR(*pgdir_entryp) + PTX(va) * 4);

其中*pgdir_entryp即为对应页表项

Exercise 2.7 page_insert

该函数的作用是将一级页表基地址 pgdir 对应的两级页表结构中虚拟地址 va 映射到页控制块 pp 对应的物理页面，并将页表项权限为设置为 perm，如上图黄色部分所示。

简单来说就是进行地址的映射，分两种情况，一种是二级页表对应的页和pp相同，一种是不同。

相同的情况比较简单，就更新一下映射的权限位同时删除TLB中缓存的页表项

如果不同，就需要先移除之前的映射，然后再分配新的一页映射到pp上，同时删除TLB中缓存的页表项，并接上数据perm和权限位

Exercise 2.8 tlb_out

接下来我们来进行对TLB的相应操作，首先我们先来了解一下TLB的结构：

正如指导书中所说：

TLB 事实上构建了一个映射 < VPN, ASID > —TLB →< PFN, N, D, V, G >。

其中ASID表示一虚拟地址在不同的地址空间中通常映射到不同的物理地址。

对TLB操作时我们有四个可以使用的指令：

tlbr：以 Index 寄存器中的值为索引，读出 TLB 中对应的表项到 EntryHi 与 EntryLo0、 EntryLo1。
tlbwi：以 Index 寄存器中的值为索引，将此时 EntryHi 与 EntryLo0、EntryLo1 的值写到索引指定的 TLB 表项中。
tlbwr：将 EntryHi 与 EntryLo0、EntryLo1 的数据随机写到一个 TLB 表项中（此处使用 Random 寄存器来“随机”指定表项，Random 寄存器本质上是一个不停运行的循环计数器）。
tlbp：根据 EntryHi 中的 Key（包含 VPN 与 ASID），查找 TLB 中与之对应的表项，并将表项的索引存入 Index 寄存器（若未找到匹配项，则 Index 最高位被置 1）。

后续我们补全代码时会频繁用到这四个指令。

首先我们先来补全刚才使用过的tlb_invalidate 函数中调用的tlb_out 函数，按照题目要求插入tlbp和tlbwi即可

Exercise 2.9 _do_tlb_refill

然后我们进行TLB的重填，操作为：

尝试在循环中调用’page_lookup’以查找虚拟地址 va 在当前进程页表中对应的页表项’ppte’
如果’page_lookup’返回’NULL’，表明’*ppte’找不到用’passive_alloc’ 9 为 va 所在的虚拟页面分配物理页面，直至’page_lookup’返回不为’NULL’则退出循环。

Exercise 2.10 do_tlb_refill

很简单，只需要使用tlbwr将CP0.EntryHi/Lo 随机写入到TLB中即可。

三、实验体会

本次实验难度较大，首先要理解虚拟地址，物理地址和页表项之间的关系，然后还要清楚诸多函数之间的调用关系并理解每个函数的实现逻辑和作用，确实是任务量不小。

同时在后面对TLB的操作我还是不是很透彻，日后也还要加深理解，继续深入学习。