Lab2实验报告

BUAA 2023 Operating System Lab2

(一)思考题

Thinking 2.1

请根据上述说明，回答问题：在编写的 C 程序中，指针变量中存储的地址是虚拟地址，还是物理地址？MIPS 汇编程序中 lw 和 sw 使用的是虚拟地址，还是物理地址？

编写的C程序中，指针变量中存储的地址是虚拟地址，MIPS汇编程序中的lw和sw使用的也是虚拟地址，因为这些都是对于某一个进程的逻辑地址，都是虚拟地址。

Thinking 2.2

请思考下述两个问题：

从可重用性的角度，阐述用宏来实现链表的好处。
查看实验环境中的 /usr/include/sys/queue.h，了解其中单向链表与循环链表的实现，比较它们与本实验中使用的双向链表，分析三者在插入与删除操作上的性能差异。
- 通过宏实现链表，我们可以通过宏定义的传参传入相应的类型和命名随时改变链表项的类型，不需要再重新定义新的结构体，增加了可重用性。
- 在实验环境中，循环链表在插入删除操作中和双向链表没有太大差异
  - 插入操作：单向链表的插入的效率比双向链表要高，单向链表的插入只需要两行，双向链表需要四行，循环链表也是四行，需要额外判断next是不是指向了头指针。插入到头结点对三种链表性能相似，插入到尾结点对于单向链表和双向链表需要遍历完整整个链表。
  - 删除操作：删除操作对三种表的性能类似，都需要遍历找到相应的结点。

Thinking 2.3

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

Page_list的结构如C选项所示：

struct Page_list{
	struct {
		struct {
			struct Page *le_next;
			struct Page **le_prev;
		} pp_link;
		u_short pp_ref;
	}* lh_first;
}

Thinking 2.4

请思考下面两个问题：

请阅读上面有关 R3000-TLB 的描述，从虚拟内存的实现角度，阐述 ASID 的必要性。
请阅读《IDT R30xx Family Software Reference Manual》的 Chapter 6，结合 ASID段的位数，说明 R3000 中可容纳不同的地址空间的最大数量。
- 对于每一个进程，它都有自己的虚拟空间，即他们所在的地址空间是不一样的，所以存在在不同的地址空间中，他们存在相同的VPN，但是它们对应的物理页号是不同的，因此我们需要用ASID区分不同的地址空间，保证不同地址空间VPN映射的物理地址是唯一的。并且在进程切换时，也可以根据ASID的不同选择将TLB中的非目标进程的表项清除。
- 可容纳不同地址空间的最大数目：64
  
  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. In such a system, new tasks are assigned new ASIDs until all 64 are assigned; at that time, all tasks are flushed of their ASIDs “de-assigned” and the TLB flushed; as each task is re-entered, a new ASID is given. Thus, ASID flushing is relatively infrequent.

Thinking 2.5

请回答下述三个问题：

tlb_invalidate 和 tlb_out 的调用关系？
请用一句话概括 tlb_invalidate 的作用。

逐行解释 tlb_out 中的汇编代码。

tlb_invalidate调用tlb_out

//pamp.c
void tlb_invalidate(u_int asid,u_long va){
	tlb_out(PTE_ADDR(va)|(asid<<6));
}

删除特定虚拟地址在TLB中的旧表项

LEAF(tlb_out)
   .set noreorder
          mfc0    t0, CP0_ENTRYHI
          //将EntryHi Register的内容取出，放到暂存寄存器中
          mtc0    a0, CP0_ENTRYHI
    	  //将a0寄存器存放的旧表项的Key放入EntryHi Register中
          nop
           /* Step 1: Use 'tlbp' to probe TLB entry */
           /* Exercise 2.8: Your code here. (1/2) */
      	  tlbp
    	  //根据EntryHi中的Key查找对应的旧表项，将表项的索引存入Index
          nop
          /* Step 2: Fetch the probe result from CP0.Index */
          mfc0    t1, CP0_INDEX
    	  //取出表项的索引放到t1寄存器中
  .set reorder
          bltz    t1, NO_SUCH_ENTRY
    	  //如果index小于0，说明不存在该表项，跳转到NO_SUCH_ENTRY
  .set noreorder
          mtc0    zero, CP0_ENTRYHI
    	  //清空EntryHi Register寄存器
          mtc0    zero, CP0_ENTRYLO0
          //清空EntryLo Register寄存器
    	  nop
          /* Step 3: Use 'tlbwi' to write CP0.EntryHi/Lo into TLB at CP0.Index  */
         /* Exercise 2.8: Your code here. (2/2) */
          tlbwi
    	  //将EntryHi和EntryLo中的值写入索引指定的TLB表项，就是清空之后的				内容写进去，把原来内容覆盖掉
  .set reorder
 
  NO_SUCH_ENTRY:
          mtc0    t0, CP0_ENTRYHI
          //将t0寄存器的内容重新放入EntryHi Register中
          j       ra
          //返回tlb_out被调用的地址
  END(tlb_out)

Thinking 2.6

任选下述二者之一回答：

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

简单了解并叙述 RISC-V 中的内存管理机制，比较 RISC-V 与 MIPS 在内存管理上的区别。

X86架构使用分页机制来管理内存。MIPS架构也使用分页机制来管理内存。但是，与X86不同，MIPS使用TLB来缓存页面表项以实现更快的访问。

Thinking A.1

在现代的 64 位系统中，提供了 64 位的字长，但实际上不是 64 位页式存储系统。假设在 64 位系统中采用三级页表机制，页面大小 4KB。由于 64 位系统中字长为8B，且页目录也占用一页，因此页目录中有 512 个页目录项，因此每级页表都需要 9 位。因此在 64 位系统下，总共需要 3 × 9 + 12 = 39 位就可以实现三级页表机制，并不需要 64位。

现考虑上述 39 位的三级页式存储系统，虚拟地址空间为 512 GB，若三级页表的基地址为 PTbase，请计算：

三级页表页目录的基地址。
映射到页目录自身的页目录项（自映射）。

页表基地址(page table) 为PT_base

页中间目录基地址(page middle directory) PMDbase：

(PT_base >> 12) * 8 + PT_base

页全局目录(page global directory) PGDbase：

((PT_base >> 12) * 8 + PT_base)>>12*8+PT_base（三级页表页目录的基地址）

即PT_base+PT_base>>9+PT_base>>18

页全局目录项（page global directory entry）PGDE：

(PT_base+PT_base>>9+PT_base>>18)>>12 *8（映射到页目录自身的页目录项）

即PT_base+PT_base>>9+PT_base>>18+PT_base>>27

(二)难点分析

exercise2.2

难点在于对于这里面链表和我们平常所理解的链表不同，我们平常见到双向链表的pre指针是指向前一个表项，而这里的链表的pre指针指向的是前一个链表的next指针，这里需要注意。同时对于宏的应用也是一个难点。

exercise2.4

在程序中对于地址的处理一定要将物理地址转化为虚拟地址才能被操作，这是2.4的一个难点。

exercise2.6

根据教程的图例指导，我们应该能很快的明白要做什么，但是我们很容易忘记我们在页表总取出的物理地址要转化为虚拟地址才能加上偏移量进行操作，正如上面所说的，在程序中所见的地址都是虚拟地址，如果将物理地址直接用来操作，会导致错误，因为程序不会认为这是物理地址。

除了具体的练习，整个实验要注意的是在进行alloc等操作的时候，我们一定要检查返回值，即是否还有足够的空间去申请，在不满足条件时及时退出，不对后面的步骤造成影响。

另外，我们要对多级页表的映射形成一个清晰的映像，这样才能去指导实验的正确进行，要分清什么时候是虚拟地址，什么时候是物理地址。

(三)实验体会

只有在对理论有着较深体会之后才能对实验得心应手，在学习实验的过程中，由于一开始对于理论的掌握不是很牢靠，导致实验碰壁，在重新梳理思路后开始实验，在清晰的知识下指导下实验完成就很顺利，所以实验的基础是牢靠的理论。
要学会使用Gxemul的debug功能，有时候bug单看代码是难以发现的，我们应该学习debug功能，运用单步调试，设置断点等方法进行bug的de。
在实验中，我们要抛弃局部性的理念，不能只在实验需要完成代码附近寻找答案，我们应该查阅各种文件宏定义，这样才能去真正理解这一个空的目的。