思考题

Thinking 2.1

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

A:

  • 在编写的C程序中，指针变量中存储的地址是虚拟地址；
  • MIPS汇编程序中lw和sw使用的也是虚拟地址。

Thinking 2.2

Q1:从可重用性的角度，阐述用宏来实现链表的好处。
Q2:查看实验环境中的 /usr/include/sys/queue.h，了解其中单向链表与循环链表的实现，比较它们与本实验中使用的双向链表，分析三者在插入与删除操作上的性能差异

A1:

用宏实现链表的好处可以通过将其与通过函数实现进行对比来体现。就我们实验中Page组成的链表为例：

1
2
3
4
5
6
7
8
9
10
struct Page{
    Page_LIST_entry_t pp_link;
    /*
        pp_link{
            struct Page *le_next;
            struct Page **le_prev;
        }
    */
    u_short pp_ref;
};

假设我们有一个链表头struct Page* head指向的链表，若我们要编写一个在该链表元素listelm后插入元素elm的函数，我们应当做如下定义：

1
void insert_after(struct Page* listelm, struct Page* elm);

而若我们定义另一种链表单元如下：

1
2
3
4
5
6
7
8
9
10
11
struct my_Page{
    Page_LIST_entry_t pp_link;
    /*
        pp_link{
            struct Page *le_next;
            struct Page **le_prev;
        }
    */
    u_short pp_ref;
    u_long some_data;
};

这个插入代码就无法在该类型上复用了。而考虑宏函数：

1
2
3
4
5
6
7
#define LIST_INSERT_BEFORE(listelm, elm, field)                                                    \
        do {                                                                                       \
                (elm)->field.le_prev = (listelm)->field.le_prev;                                   \
                LIST_NEXT((elm), field) = (listelm);                                               \
                *(listelm)->field.le_prev = (elm);                                                 \
                (listelm)->field.le_prev = &LIST_NEXT((elm), field);                               \
        } while (0)

首先无需考虑链表的类型命名，也无需考虑链表的指针域命名(传入替换即可)，更无需考虑和插入操作无关的除指针域结构体之外的数据域组成，复用性大大提高。

A2:

插入操作：

单向链表在进行给定节点前插的操作时，由于无法通过给定结点访问到前序节点的指针域，因此需要对链表从头进行一个事件复杂度为O(n)的遍历，找到前序节点，才能完成前插操作；
而循环链表和双向链表因为指针域中多了指向前序节点后向指针的二级指针，因此只通过给定节点就可以访问到前序节点的后续指针，因此可以以O(1)的效率完成前插。

而循环链表的头节点指针域是由一对分别指向链表头部和尾部的指针组成的，因此在执行尾插时无需像双向链表和单向链表一样进行复杂度为O(n)的遍历。

删除操作：

依然来看单向链表。如果希望删除单向链表中的任意给定节点，需要的操作是将前序节点的后向指针指向给定节点的后续节点，这依然牵扯到前序节点指针域的访问，因此删除操作也需要O(n)的遍历，而双向链表和循环链表则具有O(1)的复杂度。

Thinking 2.3

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//A:
struct Page_list{
    struct {
        struct {
            struct Page *le_next;
            struct Page **le_prev;
        }* pp_link;
    u_short pp_ref;
    }* lh_first;
}
//B:
struct Page_list{
    struct {
        struct {
            struct Page *le_next;
            struct Page **le_prev;
        } pp_link;
    u_short pp_ref;
    } lh_first;
}
//C:
struct Page_list{
    struct {
        struct {
            struct Page *le_next;
            struct Page **le_prev;
        } pp_link;
    u_short pp_ref;
    }* lh_first;
}

A:
答案是C选项。Page_list结构体中只存了一个指向链表第一个元素的lh_first指针，而阅读代码我们可以知道，Page_list指向的Page链表单元的结构是:名为pp_link的指针域和标记页面引用次数的数据域pp_ref，其中pp_link内包含后向一级指针le_next和前向二级指针le_prev。

Thinking 2.4

Q1:请阅读上面有关 R3000-TLB 的描述，从虚拟内存的实现角度，阐述 ASID 的必要性。
Q2:请阅读《IDT R30xx Family Software Reference Manual》的 Chapter 6，结合 ASID段的位数，说明 R3000 中可容纳不同的地址空间的最大数量。

A1:
引入虚拟内存的核心目的在于：为每个进程提供一个独立的内存视图。也就是说，每个进程都有自己独立的地址空间，仅凭借虚拟地址无法完成到物理地址的索引，通过ASID来判断该va属于哪个地址空间就十分必要了。

A2:

ASID段的位数为6，也就是说理论上R3000可以容纳不同的地址空间的最大数量为2^6=64个。

而若当前同时存在的地址空间超过64时，会由操作系统进行ASID flushing。具体地讲，就是：所有任务的ASID被取消分配(de-assigned)，TLB被刷新；当每个任务被重新输入(re-entered)时，会被赋予新的ASID。这一过程是不常发生的。

Thinking 2.5

Q1:tlb_invalidate 和 tlb_out 的调用关系？
Q2:请用一句话概括 tlb_invalidate 的作用。
Q3:逐行解释 tlb_out 中的汇编代码。

A1:
tlb_out是被tlb_invalidate调用的。

A2:

1
tlb_invalidate(u_int asid, u_long va);

用于删除TLB中asid指定的地址空间下，va所对应虚拟页面的表项。

A3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
LEAF(tlb_out)
 .set noreorder
        mfc0    t0, CP0_ENTRYHI // 保存现场
        mtc0    a0, CP0_ENTRYHI // 将`Key`写入`ENTRYHI`
        nop
        nop
        tlbp // 在TLB中查找Key对应的表项
        nop
        nop
        mfc0    t1, CP0_INDEX // 将查找结果写入t1寄存器
.set reorder
        bltz    t1, NO_SUCH_ENTRY // 若未查找到(index < 0), 则直接返回，若找到，进行下述流程
.set noreorder
        mtc0    zero, CP0_ENTRYHI  // 向`ENTRYHI`写入0
        mtc0    zero, CP0_ENTRYLO0 // 向`ENTRYLO`写入0
        nop
        tlbwi // 将`INDEX`指定的表项的`KEY`和`VALUE`全置0
.set reorder

NO_SUCH_ENTRY:
        mtc0    t0, CP0_ENTRYHI // 恢复现场
        j       ra // 函数返回
END(tlb_out)

解答如上。

Thinking 2.6

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

A1:
地址空间大小: x86 的地址空间是 32 位或 64 位，而 MIPS 的地址空间通常是 32 位。这意味着 x86 可以支持更大的内存容量。
缓存一致性协议：x86 使用缓存一致性协议（如MESI协议），用于维护多个CPU之间的缓存一致性。而 MIPS 通常不包括这样的协议，这意味着在多CPU系统中，需要使用额外的硬件或软件来实现缓存一致性。

A2:
地址空间大小：RISC-V 的地址空间可以是 32 位或 64 位，而 MIPS 的地址空间通常是 32 位。这意味着 RISC-V 可以支持更大的内存容量。
页面大小：RISC-V 支持多种页面大小，包括 4KB、8KB、16KB、32KB、64KB、128KB、256KB 和 512KB。而 MIPS 可能只支持某些特定的页面大小，比如 4KB 和 16KB。

Thinking A.1

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

A1:

单个页面大小为4KB，则二级页表区域所占的空间大小为4KB * 512 * 512 = 1GB，一级页表区域所占空间大小为4KB * 512 = 2MB。我们不妨进行改写，二级页表基地址为PT2base = PTbase，一级页表基地址为 PT1base，而页目录基地址为PDbase。则可知PT2base = PT1base + 2M * (PT1base / 512G)，而PDbase = PT2base + 4K * ((PT2base - PT1base) / 1G)。

A2:
设该页目录项的地址为PDitem，则有PDitem = PT2base + 8 * ((PDbase - PT2base) / 2M)。

实验难点

本次实验的难点主要可以概括为以下几点：

虚拟地址vs物理地址

在完成本次实验的过程中，尽管实验代码已经在pmap.h和mmu.h为我们配备好了如下各种在本次实验的kseg0段上，虚拟地址与物理地址互相转化的内联函数：

1
2
3
4
5
6
static inline u_long page2ppn(struct Page *pp);
static inline u_long page2pa(struct Page *pp);
static inline struct Page *pa2page(u_long pa);
static inline u_long page2kva(struct Page *pp);
static inline u_long va2pa(Pde *pgdir, u_long va);

无需在实验过程中为各种转化的具体实现抓耳挠腮，只需调用就好。但难点就在于我在完成实验的过程中需要对虚拟地址和物理地址斤斤计较。我在实验中总结的经验是：编写代码的我们在使用指针时是站在程序员视角的，也就是说我们操纵的一切指针都存储着将来这段程序对应进程下的虚拟地址，而物理地址则是一个我们需要通过特殊手段转化得到的数据。

本次实验中需要注意页目录项中存储的页表基地址和页表项中存储的页基地址均为物理地址。

理解整个内存管理体系的结构

页控制块和空闲链表

页控制块是pages指针指向的一片连续的Page结构体，每一个Page结构体映射着一个物理页框。

空闲链表是以page_free_list为表头的一个双向链表，主要作用是将pages数组中所有空闲页面控制块串联起来，方便空闲页面的分配。

页表项PTE和页目录项PDE

首先grep一下可以发现在mmu.h里面有typedef u_long Pde;以及typedef u_long Pte;，可知这二者本质上是32位无符号整数。

而其结构也值得注意。指导书中给出的PDE结构图如下：

PDE

其实这张图还挺有迷惑性的，让人第一眼以为要取出这里的页表基地址需要：address = pde >> 12，然而当我看到mmu.h如下的宏我明白了：

1
#define PTE_ADDR(pte) ((u_long)(pte) & ~0xFFF)

原来只需要低12位清零就好了，也就是说PDE和PTE中存储的物理地址要取得，是需要将低十二位清理，而并不是右移12位。

心得体会

  • 在照着指导书进行实验代码编写受阻时，不妨向前翻一两页，很有可能会找到漏读的关键信息。
  • 指导书不能只囫囵吞枣读一遍！指导书不能只囫囵吞枣读一遍！指导书不能只囫囵吞枣读一遍！
  • 学习新概念时，不仅要记住这个概念长什么样，还要理解这个概念为什么长这样。就拿这次实验举个例子，我在写物理内存管理这一部分的时候就有很多疑惑：为什么同时有pages和page_free_list两个变量在管理页面控制块？而且为什么明明是一片连续的结构体数组，结构体里面还套了个链表的指针域，这玩意怎么一会儿数组一会儿链表的？这些问题在后面写虚拟内存管理的那部分的时候得到了解答，原来链表和数组的形式并不冲突，在pages数组上穿起链表是为了更高效地检索和获取空闲的物理页面，便于后续的页面分配工作。