思考题

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

   C 程序的指针变量存储的是虚拟地址。MIPS汇编中的也是虚拟地址。

2. 请思考下述两个问题：

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

  实现泛型，可存储不同类型的数据，对于不同类型数据无需重新声明定义增删等相关函数。

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

  双向链表的在指定元素前插入元素的时间复杂度为o(1)， 而单向链表和循环链表需要遍历从head遍历整个链表，复杂度为o(n)。 三者在指定元素之后插入的复杂度为o(1)。

  双向链表删除为o(1)，其余两者为o(n)。

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

   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;
    }
   

2. 请思考下面两个问题：

• 请阅读上面有关 R3000-TLB 的描述，从虚拟内存的实现角度，阐述 ASID 的必要性。

  操作系统为每个进程都分配一个页表，不同的进程中，可能有相同虚拟地址。 为了确定该虚拟地址所属进程，可以使用 ASID 为进程标识码，区分不同进程。 如果不使用ASID，TLB就需要在进程切换时清空(或为每一个进程都设立一个TLB，占用大量内存)，效率低。

• 请阅读《IDT R30xx Family Software Reference Manual》的 Chapter 6，结合 ASID 段的位数，说明 R3000 中可容纳不同的地址空间的最大数量。

  6 bit，R3000可容纳至多64个不同的地址空间(但是进程可以超过64个，只需要为替换旧ASID即可)。

  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.

1. 请回答下述三个问题：
   • tlb_invalidate 和 tlb_out 的调用关系？

   tlb_invalidate 调用 tlb_out。

   1
   2
   3
   void tlb_invalidate(u_int asid, u_long va) {
       tlb_out(PTE_ADDR(va) | (asid << 6));
   }
   

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

  将指定 asid 和 va 的 tlb 页表项清空。

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

  注释形式给出解释。

    LEAF(tlb_out)
    .set noreorder /*不要让汇编器重新排序指令*/
        mfc0    t0, CP0_ENTRYHI /* 保存原有的虚拟页号 */
        mtc0    a0, CP0_ENTRYHI /*将key值写入reg hi*/
        nop /*因流水线设计架构原因，tlbp 指令的前后都应各插入一个 nop 以解决数据冒险*/
        tlbp /*根据 EntryHi 中的 Key 查找对应的旧表项，将表项的索引存入 Index*/
        nop /*数据冒险*/
        mfc0    t1, CP0_INDEX /*取出找到的索引值*/
    .set reorder
        bltz    t1, NO_SUCH_ENTRY
    .set noreorder
        mtc0    zero, CP0_ENTRYHI
        mtc0    zero, CP0_ENTRYLO0
        nop   /*数据冒险*/
        tlbwi /*将TLB对应index的表项写为0*/
    .set reorder
  
    NO_SUCH_ENTRY:
        mtc0    t0, CP0_ENTRYHI /* 找不到TLB表项则恢复虚拟页号的值，并退出函数。如果找到了对应表项，则该条会被tlbwi冒险忽略，直接退出函数*/
        j       ra
    END(tlb_out)
  

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

   X86 架构中的内存管理机制是通过分段和分页两种方式实现的。
   相比之下，MIPS 架构中的内存管理机制则只采用了分页机制。
   X86和MIPS都采用了TLB和Cache提高访存效率。

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

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

  即求 第一级页表的基地址x。

  PTbase + PTbase » 9 + PTbase » 18

  一级页表页号 9bit	二级页表页号 9bit	三级页表页号 9bit	页内偏移量 12bit
  38-30	29-21	20-12	11-0

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

  PTbase + PTbase » 9 + PTbase » 18 + PTbase » 27

难点分析

课下实验

空闲链表管理

这里的双向链表与通常意义上的双向链表不同，le_prev指向的是前一个结点的*le_next，属实奇怪，结合了图才明白这么做的含义。
(这样不能反向遍历链表，称之为双向链表本人认为不妥)

个人认为可以将这样的设定作为一道思考题考察学生理解。

1
2
3
4
struct {
    struct Page *le_next;
    struct Page **le_prev; /*通常的双向链表应该是 struct Page *le_prev;*/
} pp_link;

课上实验

exam需要遍历二级页表项，查找符合条件的页表项。
难点在于如何查找二级页表项。
但是这部分已经在 pgdir_walk 课下实验中涉及到了，如果认真完成了课下实验，此部分应当不难完成。

extra则涉及到了页面的交换，很遗憾时间不足没有完成。

实验体会

实验一届更比一届难，总有后浪推前浪，希望北航OO课程建设越来越好。

在实验指导书中，应当指出tlbwi前后也有数据冒险，否则易造成tlb_out最后退出阶段的困惑。

1
2
3
Exercise 2.8 完成 kern/tlb_asm.S 中的 tlb_out 函数。该函数根据传入的参数（TLB 的Key）找到对应的 TLB 表项，并将其清空。
具体来说，需要在两个位置插入两条指令，其中一个位置为 tlbp，另一个位置为 tlbwi。
因流水线设计架构原因，tlbp 指令的前后都应各插入一个 nop 以解决数据冒险。

• Previous
  OS lab1
• Next
  OO Unit1