Lab2实验报告

一、思考题

Thinking 2.1

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

Thinking 2.2

1)从可重用性的角度，阐述用宏来实现链表的好处。
在实验中定义的有关链表的宏是一些十分常用的对于链表的操作，而在实验中多次使用到定义的链表结构，因此相应的链表操作也是十分频繁的，通过宏来实现链表，可以让进行相关操作时不必在编写代码实现逻辑，直接使用宏即可，这省去了不必要的代码，同时提高了代码的可读性
2)查看实验环境中的/usr/include/sys/queue.h，了解其中单向链表与循环链表的实现，比较它们与本实验中使用的双向链表，分析三者在插入与删除操作上的性能差异
在这个文件中，有单向链表、双向链表和循环链表的定义，其中双向链表的定义与我们实验中使用的双向链表类似，我们可以看不同类型链表链表项的定义：
单向链表：

双向链表：

循环链表：

实现上，单向链表和循环链表类似，都有指向下一个元素的指针，其中循环链表最后一个元素相应指针指向第一个元素，同时其维护了一个指向尾项的指针，而双向链表不仅有指向下一个元素的指针，还有一个指向前一个元素的指向下一个元素的指针的指针。
操作性能：

单向链表：在某一项前插入，需要遍历链表，在某一项后插入，可以直接插入，删除也需要遍历链表
循环链表：在某一项前插入，需要遍历链表，在某一项后插入，可以直接插入，同时可以直接在尾部插入，删除需要遍历链表
双向链表：插入可以直接插入，但在尾部插入需要遍历链表，删除也可以直接删除

Thinking 2.3

选择Page_list正确的展开结构
阅读代码可以知道Page_list其实包含的就是一个指向Page的指针，而Page的定义如下：

即一个链表项，一个被引用次数，所以相应的Page_list的结构应该是选项C所展示：

Thinking 2.4

1)从虚拟内存和多进程操作系统的实现角度，阐述ASID的必要性
操作系统为每一个进程维护一个独立的虚拟地址空间，并维护相应的页表，所以很可能同一虚拟地址在不同进程中映射到不同的物理地址，如果没有ASID，那操作系统无法知道当前虚拟地址是在哪个地址空间，也就无法给出正确的映射，导致无法正确访问相应的物理内存
2)说明 4Kc 中可容纳不同的地址空间的最大数量
官方文档描述如下：

ASID占8位，所以4Kc中最多可容纳256个不同的地址空间

Thinking 2.5

1)tlb_invalidate和tlb_out的调用关系
tlb_invalidate调用tlb_out
2)请用一句话概括tlb_invalidate的作用
删除特定虚拟地址在TLB中的旧表项
3)逐行解释tlb_out中的汇编代码

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

tlb_out汇编代码如上，首先将ENTRYHI寄存器的值放入t0寄存器，同时将a0寄存器里面保存的参数即KEY存入ENTRYHI，再通过 tlbp 指令寻找TLB中对应的旧表项，将表项的索引放入t1寄存器，如果索引大于等于0，向ENTRYHI、ENTRYLO0、ENTRYLO1寄存器中写入0，并使用tlbwi指令将这三个寄存器的值写入相应索引的表项

Thinking 2.6

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

函数调用：

函数调用需要将参数压入栈，这个操作需要对内存进行写，由于地址是虚拟地址，于是触发CPU访存。执行函数体时，CPU会跳转到函数入口地址，逐条开始执行指令，这时若遇到局部变量或者访存指令，又需要进行CPU的访存流程

Thinking 2.7

简单了解并叙述X86体系结构中的内存管理机制，比较X86和MIPS在内存管理上的区别
X86体系结构的内存管理是通过分段和分页协同工作实现的。
其主要思想是将内存划分为逻辑段，每个段通过段描述符定义其基址、长度和权限，当有逻辑地址时，首先将通过分段将逻辑地址转化为线性地址，针对线性地址，采用分页机制，进一步将线性地址映射到物理地址，这和MIPS体系结构相似，而分页和分段既是协同的，又是独立的，两个机制共同实现了X86体系的内存管理。
在分页机制上，两种体系的实现也不同，MIPS体系结构是通过软件来管理页表和TLB的，而X86体系结构完全是通过硬件来管理二者的。

二、难点分析

Exercise 2.1:对相关宏定义的查找与了解
Exercise 2.2:对双向链表的理解，尤其是对其中le_prev这个指针的理解，思考如何实现双向链表的插入、删除等操作，清楚要修改哪些值
Exercise 2.3 - Exercise 2.5：对页结构体和页表结构体的理解，理解相应的地址变换操作，清楚该由什么地址变换到什么地址，同时熟悉链表相应宏的使用
Exercise 2.6 - Exercise 2.7：对二级页表机制的理解，清楚相应的地址变换，熟练链表宏的使用
Exercise 2.8 - Exercise 2.10：对TLB的组成及替换机制的理解

三、实验体会

在Lab2中，我学会了操作系统是如何去管理内存的，包括怎么实现分页机制，怎么实现TLB机制，以及如何将逻辑地址转换到物理地址。说实话，我认为本单元的难度较大，机制本身并不难以理解，甚至如果在纸面上，应该是较为简单的，但是到要真正用软件去实现这些机制的时候，我才意识到这件事到底有多么的复杂，其中有数不清的结构体的定义，有数不清的宏定义，有难以理解的链表实现，有分不清楚的指针……最关键的是，一个文件里要用到的函数、宏定义等很可能来自其他文件，一方面，可能根本不知道有哪些函数和宏可以使用，另一方面，想用某个函数和宏的时候，如果突然不太记得其功能，可这时又不知道其定义在哪个文件。总的来说，完成本单元的代码对我来说是极具挑战性的，但是最终看到测试通过的时候我也有一种成就感，为自己付出的时间感到值得。

P.Y.T

BUAA操作系统lab2