操作系统 Lab2 物理内存管理 试验报告

课程信息所在网址： chyyuu/os_course_info

• 试验目的
• 试验内容
• 基本练习
  • 练习0：填写已有试验
  • 练习1：实现 first-fit 连续物理内存分配算法（需要编程）
  • 练习2：实现寻觅虚拟地址对应的页表项（需要编程）
  • 练习3：释放某虚地址所在的页并取消对应二级页表项的映射（需要编程）
• 参考答案分析
  • 练习1
  • 练习2
  • 练习3
• 试验中涉及的知识点列举
• 试验中未涉及的知识点列举
• 参考文献

试验目的

• 了解基于段页式内存地址的转换机制
• 了解页表的建立和使用方法
• 了解物理内存的管理方法

试验内容

• 理解如何发现系统中的物理内存；
• 理解如何建立对物理内 存的初步管理，即理解连续物理内存管理;
• 理解页表相关的操作，即如何建立页表来实现虚拟内存到物理内存之间的映射，对段页式内存管理机制有一个比较全面的理解;

基本练习

练习0：填写已有试验

将LAB1中完成的代码（不包含拓展练习）移植到了lab2的框架中，涉及到的文件为kern/debug/kdebug.c和kern/trap/trap.c，具体内容已在LAB1报告中进行说明，此处不再赘述；

练习1：实现 first-fit 连续物理内存分配算法（需要编程）

• 下文中将对实现first-fit连续物理内存分配算法的实现过程进行简要说明：

  • 在ucore中采用面向对象编程的思想，将物理内存管理的内容笼统成若干个特定的函数，并且使用结构体pmm_manager来将这些函数的指针封装起来，使得具体使用到物理内存管理所提供的服务的时候，只要要调用已经初始化完成的pmm_manager的实例中的函数指针就可，这样就实现了将物理内存管理的具体实现与ucore其余部分隔离开来的效果。其中，上述若干个封装在pmm_manager中的提供物理内存管理服务的函数分别如下：
    • init：对物理内存管理器的初始化；
    • init_memmap：对管理的空闲页的数据进行初始化；
    • alloc_pages：申请分配指定数量的物理页；
    • free_pages: 申请释放若干指定物理页；
    • nr_free_pages：查询当前的空闲页总数；
    • check: 对物理内存管理器进行测试；
  • 查看default_pmm.c文件可以发现，最终ucore中所使用的物理内存管理器中的函数指针分别指向了default_init, default_init_memmap等若干函数，在本试验中，为了方便起见，通过对这些函数的实现进行修改来实现first-fit 连续内存分配算法，当然，另外一个一个更加符合面向对象编程思想的思路是重新实现若干ff_init, ff_init_memmap等专门为FF（first-fit）算法实现的函数，而后另外实例化一个使用了这些函数的内存管理器，而后将全局的默认内存管理器换成FF内存管理器就可；
  • 下文中对具体对于每一个设计物理内存管理的函数中的修改内容进行说明：
    • 首先查看default_init中的内容，发现仅有对空闲内存块链表的初始化以及将总空闲数目置零的操作，这是与具体物理内存分配算法无关的，因而直接使用默认的函数实现就可；

      list_init(&free_list);     nr_free = 0;

    • 接下来查看default_init_memmap函数，该函数的具体作用为对最初的一整块未被占用的物理内存空间中的每一页所对应的Page结构（用于形容这些页的状态）进行初始化，考虑到相邻的物理页对应的Page结构在内存上也是同样相邻的，因而可以直接通过第一个空闲物理页对应的Page结构加上一个偏移量的方式来访问所有的空闲的物理页的Page结构，具体初始化方式为：
      • 遍历所有空闲物理页的Page结构，将Page结构的形容空闲块的数目的成员变量置零（因而该成员变量只有在整个空闲块的第一个Page中才有意义），而后清空这些物理页的引用计数，而后通过设置flags的位的方式将其标记为空闲，具体的实现代码如下所示：

        struct Page *p = base;for (; p != base + n; p ++) {    assert(PageReserved(p));    p->flags = p->property = 0;    set_page_ref(p, 0);    SetPageProperty(p);}

      • 接下来对空闲块的第一个页的Page结构进行初始化，具体实现为将其表示空闲块大小的成员变量设置为作为参数传入的空闲块大小（单位为页），而后升级存储所有空闲页数量的全局变量，而后将这个空闲块插入到空闲内存块链表中（只要要将第一个Page的page_link插入就可）；具体的代码实现如下所示：

        base->property = n;nr_free += n;list_add(&free_list, &(base->page_link));

      • 至此初始化空闲页信息完成；
    • 接下来考虑实现分配空闲页函数default_alloc_pages：该函数的具体功能为分配指定页数的连续空闲物理空间，并且将第一页的Page结构的指针作为结果返回；该函数的具体实现方式如下：
      • 对参数进行合法性检查，并且查询总的空闲物理页数目能否足够进行分配，假如不足够进行分配，直接返回NULL，表示分配失败；
      • 从头开始遍历保存空闲物理内存块的链表(按照物理地址的从小到大顺序)，假如找到某一个连续内存块的大小不小于当前需要的连续内存块大小，则说明可以进行成功分配（选择第一个遇到的满足条件的空闲内存块来完成内存分配）；具体代码实现如下所示：

        struct Page *page = NULL;list_entry_t *le = &free_list;while ((le = list_next(le)) != &free_list) {    struct Page *p = le2page(le, page_link);    if (p->property >= n) {        page = p;        break;    }}

      • 接下来考虑对取得的满足条件的空闲内存块进行解决，假如该内存块的大小大于需要的内存大小，则将空闲内存块分裂成两块，物理地址较小的一块分配出来进行使用（大小刚好为需要的物理内存的大小），而物理地址较大的那一块重新进行初始化（包括对第一个Page中表示空闲块大小的成员变量进行设置，其应当设置为原价的空闲块大小减掉分配掉的大小，以及将这个分裂出来的空闲块插入到空闲块链表中（该链表中的空闲块按照物理地址从小到大排序））；假如原价的空闲块大小恰好等于需要的内存大小，则没有比较进行分裂；于此同时，对分配出去的物理内存的每一个的形容信息（即对应的Page结构）进行初始化，具体为修改flags成员变量来将这些Page标记为非空闲，最后将原始空闲块在空闲块链表中删除掉，并且升级表示总空闲页数量的全局变量；最后用于表示分配到的物理内存的Page结构指针返回。具体实现的代码如下所示：

        if (page != NULL) { // 假如寻觅到了满足条件的空闲内存块    for (struct Page *p = page; p != (page + n); ++p) {        ClearPageProperty(p); // 将分配出去的内存页标记为非空闲    }    if (page->property > n) { // 假如原价找到的空闲块大小大于需要的分配内存大小，进行分裂        struct Page *p = page + n; // 取得分裂出来的新的小空闲块的第一个页的形容信息        p->property = page->property - n; // 升级新的空闲块的大小信息        list_add(&(page->page_link), &(p->page_link)); // 将新空闲块插入空闲块列表中    }    list_del(&(page->page_link)); // 删除空闲链表中的原价的空闲块    nr_free -= n; // 升级总空闲物理页的数量}

      • 至此完成了内存页分配的实现
    • 接下来考虑释放占用的内存块的函数default_free_pages，该函数的具体功能为释放指定的某一物理页开始的若干个连续物理页，并且完成first-fit算法中需要的若干信息的维护，具体的实现如下所示：

      • 首先考虑遍历需要释放的物理页的形容信息（即对应的Page结构），对其进行升级，具体内容为：

        • 判断原价这些物理页能否真的被占用了，假如释放未被占用的物理页，这说明出现了异常情况；
        • 设置flags来将这些物理页标记为空闲；
        • 清空这些物理页的引用计数；
          具体的代码实现如下所示：

        struct Page *p = base;for (; p != (base + n); p ++) {    assert(!PageReserved(p) && !PageProperty(p)); // 进行检查    SetPageProperty(p); // 标记为空闲    set_page_ref(p, 0); // 清空引用计数}

      • 接下来将这一新的空闲块插入到空闲块链表中，具体代码实现如下：

        base->property = n; // 设置空闲块大小list_entry_t *le = list_next(&free_list); for (; le != (&free_list) && le < (&(base->page_link)); le = list_next(le)); // 寻觅新的空闲块在空闲块链表中应当处于的位置list_add_before(le, &(base->page_link)); // 将空闲块插入到链表中nr_free += n; // 升级空闲物理页总量

      • 接下来需要对空闲块跟其相邻的空闲块（假如存在的话）进行合并，为此专门实现了一个函数merge_backward，用于尝试将指定的某一个空闲块与其链表后的空闲块进行合并，假如合并失败则返回0，否则返回1，使用该函数可以简洁的完成所有合并操作，具体代码实现如下：

        while (merge_backward(base)); // 将新插入的空闲块和其物理地址大的一端的所有相邻的物理空闲块进行合并for (list_entry_t *i = list_prev(&(base->page_link)); i!= &free_list; i = list_prev(i)) { // 将新插入的空闲块和其物理地址小的一段的所有相邻的物理空闲块进行合并    if (!merge_backward(le2page(i, page_link))) break;}

        接下来通过具体实现代码对merge_backward函数进行说明：

        static boolmerge_backward(struct Page *base) {    list_entry_t *le = list_next(&(base->page_link)); // 获取链表中下一块（物理地址大的一端）的相邻空闲块    if (le == &free_list) return 0; // 假如此空闲块是物理地址最大的空闲块，则无法进行向后合并，返回合并失败    struct Page *p = le2page(le, page_link);    if (PageProperty(p) == 0) return 0;    if (base + base->property != p) return 0; // 假如这两空闲块不是相邻的，无法进行合并    base->property += p->property; // 进行空闲块合并    p->property = 0;    list_del(le); // 将合并前的物理地址较大的空闲块从链表中删去    return 1; // 返回合并成功}

  • 至此完成了整个first-fit算法的实现；

• 答复问题：你的first fit算法能否有进一步的改进空间？
  • 在本试验中所实现的first fit算法依然有着相当的改进空间，其中最主要的不足我认为就在于时间效率上，每次查询第一块符合条件的空闲内存块时，最坏情况需要找遍整个链表，这样的话时间复杂度是O（N），N表示当前的链表大小，考虑针对时间效率的优化方式如下：
    • 采用splay等平衡二叉树结构来取代简单的链表结构来维护空闲块，其中按照中序遍历得到的空闲块序列的物理地址刚好按照从小到大排序；
    • 每个二叉树节点上维护该节点为根的子树上的最大的空闲块的大小；
    • 在每次进行查询的时候，不妨从根节点开始，查询左子树的最大空闲块能否符合要求，假如是的话进入左子树进行进一步查询，否则进入右子树；（二分查找）
    • 按照上述方法，最终可以查找到物理地址最小的能够满足条件的空闲地址块，将其splay到平衡树的根（假如使用splay树的话），而后进行删除以及新的分裂出来的空闲块的插入等操作；
    • 按照上述方法的话，每次查询符合条件的第一块物理空闲块的时间复杂度为O(log N)，比照原价的O（N）有了较大的改进；

练习2：实现寻觅虚拟地址对应的页表项（需要编程）

• 本练习的要求为补全pmm.c中的get_pte函数，好像函数名形容的一般，该函数的主要功能为根据给定的page directory以及线性地址，查询出该linear address对应的page table entry，并且根据输入参数要求判断能否创立不存在的页表，接下来将根据该函数的具体实现代码分析具体实现的过程：

pde_t *pdep = pgdir + PDX(la); // 获取到页目录表中给定线性地址对应到的页目录项pte_t *ptep = ((pte_t *) (KADDR(*pdep & ~0XFFF)) + PTX(la)); // 从找到的页目录项中查询到线性地址对应到的页表中的页表项，即页表基址加上线性地址的中的offset（第12...21位，从0开始）if (*pdep & PTE_P) return ptep; // 检查查找到的页目录项能否存在，假如存在直接放回找到的页表项就可if (!create) return NULL; // 假如该页目录项是不存在的，并且参数要求不创立新的页表，则直接返回struct Page* pt = alloc_page(); // 假如需要按需创立新的页表，则请求一个物理页来存储新创立的页表if (pt == NULL) return NULL; // 假如物理空间不足，直接返回set_page_ref(pt, 1); // 升级该物理页的引用计数ptep = KADDR(page2pa(pt)); // 获取到该物理页的虚拟地址（此时已经启动了page机制，内核地址空间），这是由于CPU执行的指令中使用的已经是虚拟地址了memset(ptep, 0, PGSIZE); // 新创立的页表进行初始化*pdep = (page2pa(pt) & ~0XFFF) | PTE_U | PTE_W | PTE_P; // 对原价的页目录项进行设置，包括设置其对应的页表的物理地址，以及包括存在位在内的标志位return ptep + PTX(la); // 返回线性地址对应的页目录项

• 答复以下问题：
  • 请形容页目录项（Pag Director Entry）和页表（Page Table Entry）中每个组成部分的含义和以及对ucore而言的潜在用处。

    • 接下来形容页目录项的每个组成部分，PDE（页目录项）的具体组成如下图所示；形容每一个组成部分的含义如下[1]：

      • 前20位表示4K对齐的该PDE对应的页表起始位置（物理地址，该物理地址的高20位即PDE中的高20位，低12位为0）；
      • 第9-11位未被CPU使用，可保留给OS使用；
      • 接下来的第8位可忽略；
      • 第7位用于设置Page大小，0表示4KB；
      • 第6位恒为0；
      • 第5位用于表示该页能否被使用过；
      • 第4位设置为1则表示不对该页进行缓存；
      • 第3位设置能否使用write through缓存写策略；
      • 第2位表示该页的访问需要的特权级；
      • 第1位表示能否允许读写；

      • 第0位为该PDE的存在位；

        pde.png

    • 接下来形容页表项（PTE）中的每个组成部分的含义，具体组成如下图所示[2]：

      • 高20位与PDE类似的，用于表示该PTE指向的物理页的物理地址；
      • 9-11位保留给OS使用；
      • 7-8位恒为0；
      • 第6位表示该页能否为dirty，即能否需要在swap out的时候写回外存；
      • 第5位表示能否被访问；
      • 3-4位恒为0；
      • 0-2位分别表示存在位、能否允许读写、访问该页需要的特权级；

    • 可以发现无论是PTE还是TDE，都具备着少量保留的位供操作系统使用，也就是说ucore可以利用这些位来完成少量其余的内存管理相关的算法，比方可以在这些位里保存最近一段时间内该页的被访问的次数（仅能表示0-7次），用于辅助近似地实现虚拟内存管理中的换出策略的LRU之类的算法；也就是说这些保留位有利于OS进行功能的拓展；

pte.png

- 假如ucore执行过程中访问内存，出现了页访问异常，请问硬件要做哪些事情？    - 当ucore执行过程中出现了页访问异常，硬件需要完成的事情分别如下：        - 将发生错误的线性地址保存在cr2寄存器中;        - 在中断栈中依次压入EFLAGS，CS, EIP，以及页访问异常码error code，假如page fault是发生在客户态，则还需要先压入ss和esp，并且切换到内核栈；        - 根据中断形容符表查询到对应page fault的ISR，跳转到对应的ISR处执行，接下来将由软件进行page fault解决；

练习3：释放某虚地址所在的页并取消对应二级页表项的映射（需要编程）

• 接下来具体代码实现来说明释放某虚地址所在的页并且取消PTE表项的映射的具体实现：

assert(*ptep & PTE_P); // 确保传入的二级页表项是存在的struct Page *page = pte2page(*ptep); // 获取该页表项对应的物理页对应的Page结构page->ref --; // 减少该物理页的引用计数if (!page->ref) free_page(page); // 假如该物理页的引用计数变成0，即不存在任何虚拟页指向该物理页，释放该物理页*ptep &= (~PTE_P); // 将PTE的存在位设置为0，表示该映射关系无效tlb_invalidate(pgdir, la); // 刷新TLB，保证TLB中的缓存不会有错误的映射关系

• 答复如下问题：

  • 数据结构Page的全局变量（其实是一个数组）的每一项与页表中的页目录项和页表项有无对应关系？假如有，其对应关系是啥？
    • 存在对应关系：因为页表项中存放着对应的物理页的物理地址，因而可以通过这个物理地址来获取到对应到的Page数组的对应项，具体做法为将物理地址除以一个页的大小，而后乘上一个Page结构的大小取得偏移量，使用偏移量加上Page数组的基地址皆可以或者得到对应Page项的地址；
  • 假如希望虚拟地址与物理地址相等，则需要如何修改lab2，完成此事？ 鼓励通过编程来具体完成这个问题。
    • 因为在完全启动了ucore之后，虚拟地址和线性地址相等，都等于物理地址加上0xc0000000，假如需要虚拟地址和物理地址相等，可以考虑升级gdt，升级段映射，使得virtual address = linear address – 0xc0000000，这样的话即可以实现virtual address = physical address；

• 最终完成所有练习之后，可以通过make grade的所有测试，最终试验结果如下所示：

result.png

参考答案分析

接下来对所给出的参考答案进行分析，与本试验中的实现进行比照：

练习1

• 因为代码实现本身比较简单，本试验的在default_init, default_memmap的实现上与参考答案的思路基本一致，因而不进行赘述；
• 关于default_alloca_pages函数的实现，本试验与参考答案的试验的区别如下所示：
  • 在实现遍历空闲块链表部分，本试验中的实现时先找到符合条件的块，而后退出遍历过程，对空闲块进行解决，而参考答案是直接在遍历过程中进行解决，而后再直接退出函数；
  • 答案的实现中，空闲块链表上保存了所有的空闲的物理页对应的Page，而本试验的实现中，空闲块链表上仅存了所有连续空闲块的第一个物理页对应的Page，本人的实现减小了该链表的长度，有利于提高时间效率；
• 接下来探讨default_free_pages函数的实现区别：
  • 同样，因为上述提及到的存储在空闲块链表上的内容的不同，本人的实现在删除只要要将某个物理空闲块的第一页从链表上摘下来就可，而参考答案的实现需要将整个空闲块的所有页都从链表上删除掉；
  • 在完成空闲块的合并方便，本试验中的实现将合并操作抽出来形成单独的函数，使得代码思路更加清晰；

练习2

• 因为练习2中的代码思路较为简单，本试验中的实现与参考答案的区别仅仅表现在少量具体的代码形容上，比方说在获取页目录表的某一项的时候，参考答案使用pgdir[PDX(la)]进行获取，而本试验中的实现使用呢了pgdir + PDX(la)进行获取；两者形容没有具体的优劣之分；

练习3

• 因为练习3的代码实现较为简单，本试验中的实现与参考答案基本没有区别，因而不再赘述；

试验中涉及的知识点列举

列举本次试验中涉及到的知识点如下：

• 80386 CPU的段页式内存管理机制，以及进入页机制的方法；
• 对物理内存的探测的方法；
• 具体的连续物理内存分配算法，包括first-fit，best-fit等一系列策略；
• ucore中链表的实现方法；
• 在C语言中使用面向对象思想实现物理内存管理器；
• 链接地址、虚拟地址、线性地址、物理地址以及ELF二进制可执行文件中各个段的含义；

对应到的OS中的知识点如下：

• 内存页管理机制；
• 连续物理内存管理；

两者之间的对应关系为：

• 前者为后者提供了具体完成某一个平台上的操作系统对应的内存管理功能的底层支持；
• 同时在试验中设计到的其余少量知识点，比方面向对象思想、链表的使用等，方便了具体的操作系统的实现编码；

试验中未涉及的知识点列举

试验中未涉及的知识点包括：

• 虚拟内存管理，包括在物理内存不足的情况下将暂时使用不到的物理页换出到外存中，从而实现大于物理内存空间的虚拟内存空间；
• PageFault的解决；
• OS中的进程、线程的创立、管理、调渡过程，以及进程间的同步互斥；
• OS中用于访问外存的文件系统；
• OS对IO设施的管理；
• 从内核态跳转到客户态的方式；

试验代码

AmadeusChan/ucore_os_lab/tree/master/lab2

参考文献

• [1] https://wiki.osdev.org/Paging
• [2] INTEL 80386 PROGRAMMER’S REFERENCE MANUAL 1986