操作系统实验报告（lab2）

操作系统实验

Lab2

---

目录

1.思考题解答
2.难点分析
3.思考体会

---

思考题解答

Thinking 2.1

由于而在实际程序中，访存、跳转等指令以及用于取指的 PC 寄存器中的访存目标地址都是虚拟地址，所以 C 程序和 MIPS 程序中使用的都是虚拟地址。

Thinking 2.2

（1）
用宏实现链表的相关操作有以下优点：

• 重用性和可移植性好，代码简洁；宏定义的使用避免了重复冗余代码在程序中的出现。
• 代码执行效率高；预处理器用复制宏代码的方式代替函数调用，省去了参数压栈、生成汇编语言的CALL调用、 返回参数、执行return等过程，从而提高了速度。

（2）
实验环境中定义了单向链表、双向链表、单向队列、双向队列、循环队列。

• 插入操作：
  单向链表和循环链表的插入只需维护两个指针，双向链表的插入需要维护四个指针；对于在头节点插入，三种实现方式的开销相似；对于在尾节点插入，单向链表和双向链表均需要遍历整个链表，二循环链表可直接定位插入。
• 删除操作：
  单向链表和循环链表的删除性能接近（均需遍历以找到删除节点的上一个节点），双向链表删除性能较好；对于在头结点进行删除，三种实现方式的开销相似。

Thinking 2.3

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

#define LIST_HEAD(name, type)   \
    struct name {               \
        struct type *lh_first; /* first 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;
};

联系以上三段代码，显然选择 C。
Page_list 是 Page类型的头指针，是查询各页信息的入口，Page类型内含有双向指针和此页引用次数的数据。

Thinking 2.4

由于操作系统将进程作为处理任务的单元，故不同进程可能使用相同的虚拟地址，但若此地址不是共享的（Global = 0）则映射到的物理地址是不同的，这里使用 ASID 来标注引导取不同的物理地址，防止混淆。
结合原文和 ASID 6位的事实， R3000 中可容纳不同的地址空间的最大数量为 64。

Thinking 2.5

• tlb_invalidate 调用 tlb_out。
• tlb_invalidate将释放快表中地址空间为 ASID，虚拟地址为 va的项。

LEAF(tlb_out)
.set noreorder
    mfc0    t0, CP0_ENTRYHI //保存原本EntryHi中具有的值
    mtc0    a0, CP0_ENTRYHI //将待查询信息（ASID 和 虚页号组合）写入EntryHi
    nop
    /* Step 1: Use 'tlbp' to probe TLB entry */
    /* Exercise 2.8: Your code here. (1/2) */
    nop
    tlbp    //根据探查信息获取页表项索引
    nop
    nop
    nop //等待cpu执行完毕tlbp
    nop
    /* Step 2: Fetch the probe result from CP0.Index */
    mfc0    t1, CP0_INDEX  //取页表项索引 Index
.set reorder
    bltz    t1, NO_SUCH_ENTRY  //索引小于0，则没有对应页表项
.set noreorder
    mtc0    zero, CP0_ENTRYHI   //清空 EntryHi
    mtc0    zero, CP0_ENTRYLO0  //清空 EntryLo
    nop
    /* Step 3: Use 'tlbwi' to write CP0.EntryHi/Lo into TLB at CP0.Index  */
    /* Exercise 2.8: Your code here. (2/2) */
    tlbwi   //将清零后的Hi/Lo写入TLB的项
.set reorder

NO_SUCH_ENTRY:
    mtc0    t0, CP0_ENTRYHI //恢复EntryHi中原来的值
    j       ra  //返回
END(tlb_out)

Thinking 2.6

X86 和 MIPS 在内存管理上的区别主要有：

• MIPS 采用的是页式管理系统，X86 采用的是页式段式内存管理结构；
• TLB 不命中时：MIPS 会触发TLB Refill 异常，内核的 tlb_refill_handler 会以 pgd_current 为当前进程的 PGD 基址，索引获得转换失败的虚址对应的 PTE，并将其填入 TLB；X86 是由硬件 MMU 以 CR3 为当前进程的 PGD 基址，索引获得 PFN 后，直接输出 PA。同时 MMU 会填充 TLB 以加快下次转换的速度。
• 转换失败的虚拟地址：MIPS 使用 BadVAddr 寄存器存放，X86 使用 CR2 存放。

Thinking A.1

(1)
PTbase + PTbase << 9 + PTbase << 18
(2)
PTbase + PTbase << 9 + PTbase << 18 + PTbase << 27

---

难点分析

个人感觉这次实验的难度上了一个台阶，主要有以下几点：

• 搞清楚 Page_list 的指针结构，其中定义struct type **le_prev;为指向前一个结点的指针让我很迷惑，后来自习阅读示例才发现此指针指向的是上一个结点指向下一个结点的指针。
• 弄清楚 虚拟地址(va)，物理地址（pa），页控制块地址(pp) 的关系和转化函数；在pamap.c中，我们需要时刻记清楚现在操作的是什么类型的地址，必要时灵活使用转化函数。
• 对于两级页表的处理，考验对页表结构的熟悉程度，由于给了结构图，这里只需理清地址之间的关系即可。
• TLB部分任务虽然简单，但是封装好的函数内部较为复杂，需要仔细体会。

---

思考体会

本次实验为初步构建操作系统内存管理体系，可分为两个部分，即内核对内存相关的地址空间的初始化和用户访存过程中页面控制、页表和快表的行为处理。
个人感觉本次作业子刚上手的时候较为困难，常常记不住一些函数和宏的作用，不知道自己写的函数功能是什么，混淆三种地址导致bug。但对内存管理相关的文件（pmap.c pmap.h mmu.h queue.h tlbex.c tlb_asm.S）熟悉后再结合教程的图文，绝大部分的问题还是不难解决的。
总的来说，这次作业使我在理论课中学到的内存管理知识得以应用，让我从更加具象的层面观察操作系统的内存管理机制。