Post

BUAA-OS-lab2

Posted Updated
By Zhixin Cai
14 min read
BUAA-OS-lab2

lab2 实验报告

思考题

Thinking 2.1

C 语言中指针变量储存的地址是虚拟地址，汇编代码中 lw 和 sw 指令中使用的地址也是虚拟地址。

Thinking 2.2

使用宏来实现链表的好处主要体现在以下几个方面：

  • 代码复用：宏可以使链表的定义和操作变得通用，不受特定数据类型的影响。通过宏，可以在不同的数据结构中重用相同的链表实现代码，只需简单地将链表节点中的数据类型进行替换即可。
  • 类型无关性：宏允许链表操作与具体的存储类型无关，这意味着同一个宏定义可以用于创建存储不同类型数据的链表。
  • 性能优势：宏在编译时会被直接替换为相应的代码，没有函数调用的开销。这可以减少程序运行时的性能损耗。

通过阅读系统中 queue.h 中的宏定义，对比多种链表的实现方式及其特性，可以得出以下结论：

  • 单向链表 单向链表对于单纯的给定元素特定位置进行插入和删除操作，时间复杂度是 $O(1)$ 的；但是如果要插入到中间的第 $i$ 个位置，或是执行 insert_before 操作，需要从头部遍历一遍才能找到相应的位置，这个时间复杂度是 $O(n)$ 的，效率比较低下。

  • 双向链表

由于双向链表记录了元素的前驱和后继，它对于任意元素在任意给定位置的插入和删除操作时间复杂度都只有 $O(1)$。

  • 循环链表

本质上和单向链表是一样的，执行 insert_before 时需要从头遍历，时间复杂度是 $O(n)$。

Thinking 2.3

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

关于 Page 的声明：

1
2
3
4

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

而 typedef LIST_ENTRY(Page) Page_LIST_entry_t; 中声明了 Page_LIST_entry_t，再找到关于 LIST_ENTRY 的定义：

1
2
3
4
5

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

所以 Page_LIST_entry_t 实际上是一个结构体，其中包含两个指针，分别指向下一个元素和前一个元素。

这里，我们处理完了关于 Page 的展开。

然后，再查找 Page_list 的声明：

1
2
3

struct Page_list { 
    struct Page *lh_first;                      
}

进而可以完成展开。

Thinking 2.4

在多进程环境中，每个进程都有自己的虚拟地址空间，这些地址空间通常是独立的。ASID用于在TLB中区分不同进程的页表项，确保每个进程只能访问自己的内存地址，从而实现进程间的隔离。

ASID使得操作系统在管理内存时更加灵活和高效。它允许操作系统为每个进程分配一个唯一的标识符，而不需要关心进程的具体虚拟地址空间布局，从而简化了内存管理的工作。

当CPU进行上下文切换时，如果没有ASID，则需要将TLB中的所有条目刷新，因为新的进程可能会使用相同的虚拟地址，而这些地址在TLB中可能映射到不同的物理地址。ASID允许TLB保留多个进程的条目，只有当切换到具有相同ASID的进程时才需要刷新相关的TLB条目，减少了不必要的刷新操作。

ASID 6 位，因此可以最多容纳 64 个不同的地址空间。

Thinking 2.5

1
2
3

void tlb_invalidate(u_int asid, u_long va) {
    tlb_out((va & ~GENMASK(PGSHIFT, 0)) | (asid & (NASID - 1)));
}

tlb_invalidate函数调用 tlb_out 函数。tlb_invalidate 函数就是用 tlb_out() 把虚拟地址 va 对应的 tlb 页表项清空。

阅读 tlb_out 函数：

LEAF(tlb_out) # 标记这是一个叶子函数，即它不会调用其他函数，也不会保存其他寄存器的状态。
.set noreorder # 告诉汇编器不要对指令进行重新排序，确保指令按照写的顺序执行
    mfc0    t0, CP0_ENTRYHI # 将 CP0 寄存器中的 ENTRYHI（TLB 的键字段）内容复制到通用寄存器 t0 中，保存原始的 ENTRYHI 值
    mtc0    a0, CP0_ENTRYHI # 将传入的参数（a0 寄存器中的值）复制到 CP0 的 ENTRYHI 寄存器中，准备进行TLB操作
    nop
    /* Step 1: Use 'tlbp' to probe TLB entry */
    /* Exercise 2.8: Your code here. (1/2) */
    nop
    tlbp # 根据 EntryHi 中的 Key，查找 TLB 中与之对应的表项，并将表项的索引存入 Index 寄存器
    nop
    /* Step 2: Fetch the probe result from CP0.Index */
    mfc0    t1, CP0_INDEX # 将 CP0 的 INDEX 寄存器内容（TLB 探测的结果）复制到通用寄存器 t1 中
    .set reorder
    bltz    t1, NO_SUCH_ENTRY # 如果 TLB 中没有找到对应的条目，跳转到 NO_SUCH_ENTRY 标签
    .set noreorder
    mtc0    zero, CP0_ENTRYHI
    mtc0    zero, CP0_ENTRYLO0
    mtc0    zero, CP0_ENTRYLO1 # 把 CP0_ENTRYHI，CP0_ENTRYLO 全部设为 0，为清空 TLB 做准备
    nop
    /* Step 3: Use 'tlbwi' to write CP0.EntryHi/Lo into TLB at CP0.Index  */
    /* Exercise 2.8: Your code here. (2/2) */
    nop
    tlbwi # 将此时 EntryHi 与 EntryLo 的值，也就是 0，写到索引指定的 TLB 表项中，完成清空
    nop
.set reorder

NO_SUCH_ENTRY:
    mtc0    t0, CP0_ENTRYHI # 将之前保存的原始 ENTRYHI 值写回到 CP0 的 ENTRYHI 寄存器中，恢复上下文
    j       ra # 返回
END(tlb_out)

Thinking 2.6

x86 体系结构中的内存管理机制：

x86 架构的内存管理依赖于分段和分页机制。x86 处理器使用段寄存器（CS, DS, ES, FS, GS 和 SS）来确定内存中代码和数据的地址。每个段寄存器包含一个段选择子和一个段偏移量。段选择子用于在全局描述符表（GDT）或局部描述符表（LDT）中查找段描述符，段描述符包含段的基地址、限制和其他属性。段寄存器中的段偏移量与段描述符中的基地址相加，以形成线性地址。

x86 架构还支持分页机制，允许操作系统将物理内存划分为固定大小的页，并使用页表将线性地址映射到物理地址。分页机制提供了虚拟内存和内存保护功能。操作系统可以控制每个页的访问权限，如读/写、执行等。分页机制还允许操作系统实现多任务处理和内存扩展。

MIPS 体系结构中的内存管理机制：

MIPS 架构的内存管理依赖于分页机制。MIPS 处理器使用虚拟地址和物理地址之间的映射。MIPS 架构支持多种分页模式，如直接映射、两级页表和三级页表。在分页模式下，虚拟地址被划分为页号和页内偏移量。页号用于查找页表，以获取页的物理地址。页内偏移量与页的物理地址相加，以形成最终的物理地址。

MIPS 架构的分页机制提供了虚拟内存和内存保护功能。操作系统可以控制每个页的访问权限，如读/写、执行等。与 x86 架构相比，MIPS 架构的分页机制更为简单，不依赖于分段机制。

实验难点分析

这次课下实验主要分为物理内存管理，虚拟内存管理和 TLB 重填三个板块。

物理内存管理部分内容相对比较简单，主要是完成链表宏的填充和一些函数的实现。链表宏的填充相对不难，理解了双向链表的结构便很好实现，但是在填充之前需要阅读多个文件中的相关代码，并结合已有的链表宏，理解传入参数的意义。函数实现方面，只要把握住各个变量之间的关系，理解 ROUND 函数和页控制块及其中的变量的作用，依照代码内的提示实现即可。

虚拟内存管理部分内容也不是很难，主要是要理解两级页表的机制，以及相关宏定义和函数的使用。上机的时候 exam 也考了二级页表的遍历，栽在了对二级页表项的虚拟地址的理解上面，我以为这里的虚拟地址指的是存储二级页表项的指针指向的位置，苦想了半天都没写出来，最后结合本地的测试代码才搞明白，指的是可以映射到相对应的二级页表项的虚拟地址。

TLB 重填部分要填写的代码不多，依照代码提示让做什么写什么就行。

实验体会

对于已有的大量代码，一上来就想要完成任务会有点无从下手。其实应该先通读一遍所有的代码，再开始完成填空的。不过 lab2 的课下写的比较晚，比较着急，先笼统的看了一遍就开始写，写的时候照着提示或者是上下文依葫芦画瓢也很快就写完了，但是显然对代码的理解不够深入。

在完成练习之后，我又抽了大半天的时间，结合指导书，从头到尾读了一遍 pmap.c 中的所有函数实现，并完成了对所有函数功能的注释，对函数的实现方式也有了自己的认知。在通读代码的过程中，我逐渐豁然开朗，之前稀里糊涂的东西都得到了诠释。在之后与同学交流的过程中，我对代码和内存管理的理解又更加深入了。

操作系统
操作系统 OS实验
This post is licensed under CC BY 4.0 by the author.