操作系统实验：Lab2 物理内存管理

清华大学操作系统Lab2实验报告
课程主页：http://os.cs.tsinghua.edu.cn/oscourse/OS2018spring
实验指导书：https://chyyuu.gitbooks.io/ucore_os_docs/content/
github：https://github.com/chyyuu/ucore_os_lab

实验目的

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

练习0：填写已有实验

Eclipse的compare with工具

在Project Explorer中选取lab1和lab2目录，右键选择Compare With -> Each Other，得到如图界面。随后，按照需要将lab1中的代码搬入lab2目录。

练习1：实现 first-fit 连续物理内存分配算法

在kern/mm/default_pmm.c中，主要改动了default_alloc_pages和default_free_pages两个函数。注释中说明了我的做法：

static struct Page *
default_alloc_pages(size_t n) {
    assert(n > 0);
    if (n > nr_free) {
        return NULL;
    }
    struct Page *page = NULL;
    list_entry_t *le = &free_list;

// Step1：找到第一个长度大于等于n的块
    while ((le = list_next(le)) != &free_list) {
        struct Page *p = le2page(le, page_link);
        if (p->property >= n) {
            page = p;
            break;
        }
    }

// Step2：如果可以找到长度大于等于n的块，则
// (1) 如果长度大于n，在从这个块中取走长度为n的存储空间，并将剩下的存储空间插入到列表中
// (2) 删除原来的块
    if (page != NULL) {
        if (page->property > n) {
            struct Page *p = page + n;
            p->property = page->property - n;
            SetPageProperty(p);
            list_add_after(&(page->page_link), &(p->page_link));
        }
        list_del(&(page->page_link));
        nr_free -= n;
        ClearPageProperty(page);
    }
    return page;
}

static void
default_free_pages(struct Page *base, size_t n) {
    assert(n > 0);
    struct Page *p = base;

// 原来的代码，检查每个block中的各个page property是否合法
    for (; p != base + n; p ++) {
        assert(!PageReserved(p) && !PageProperty(p));
        p->flags = 0;
        set_page_ref(p, 0);
    }

// 原来的代码，设置好释放空间的长度和page property
    base->property = n;
    SetPageProperty(base);

// Step1：找到插入链表的位置（链表已按照地址从大到小排序）
    list_entry_t *le = list_next(&free_list);
    list_entry_t *prev = &free_list;
    while (le != &free_list) {
        p = le2page(le, page_link);
        if (base < p) {
            break;
        }
        prev = le;
        le = list_next(le);
    }

// Step2：检查是否可以和链表的前一项中的空间合并
    p = le2page(prev, page_link);
    if (prev != &free_list && p + p -> property == base) {
        p -> property += base -> property;
        ClearPageProperty(base);
    } else {
        list_add_after(prev, &(base -> page_link));
        p = base;
    }

// Step3：检查是否可以和链表的后一项中的空间合并
    struct Page *nextp = le2page(le, page_link);
    if (le != &free_list && p + p -> property == nextp) {
        p -> property += nextp -> property;
        ClearPageProperty(nextp);
        list_del(le);
    }

    nr_free += n;
}

你的first fit算法是否有进一步的改进空间

分析以上first fit算法的代码，可以看到无论是alloc过程还是free过程都需要O(n)的复杂度。如果使用first fit算法，我认为以上代码效率低的主要原因在于使用双向链表组织所有的block，这导致访问必须耗费线性时间。
如果使用树状结构组织，如下图所示，alloc过程将变成DFS，复杂度依旧是O(n)，但是free过程在查找插入位置时可以二分查找，从而达到O(logn)的复杂度。

(xi,leni)表示(起始地址，块大小)。其中x0<x1<...<x6，且块地址不相互重叠
此外，first-fit算法还可以改成best-fit算法（适用于大部分分配的尺寸较小时）或worst-fit算法（适用于大部分分配的尺度适中时）。

练习2：实现寻找虚拟地址对应的页表项

//(1) find page directory entry
    pde_t *pdep = pgdir + PDX(la); 
//(2) check if entry is not present
    if (!(*pdep & PTE_P)) { 
//(3) check if creating is needed, then alloc page for page table
        if (create) { 
            struct Page *page = alloc_page(); 
            if (page != NULL) {
//(4) set page reference
                set_page_ref(page, 1); 
//(5) get linear address of page
                pte_t page_la = KADDR(page2pa(page)); 
//(6) clear page content using memset
                memset(page_la, 0, PGSIZE); 
//(7) set page directory entry's permission
                *pdep = page2pa(page) | PTE_P | PTE_W | PTE_U; 
//(8) return page table entry
                return ((pte_t *)(KADDR(PDE_ADDR(*pdep)))) + PTX(la); 
            } else {
                return NULL;
            }
        } else {
            return NULL;
        }
    }
//(8) return page table entry
    return ((pte_t *)(KADDR(PDE_ADDR(*pdep)))) + PTX(la); 

请描述页目录项（ Page Director Entry） 和页表（ Page Table Entry） 中每个组成部分的含义和以及对ucore而言的潜在用处。

页目录项包括一些几部分：

名称	地址	ucore中的对应
Page Table 4KB Aligned Address	31 downto 12	对应的页表地址
Avail	11 downto 9	PTE_AVAIL
Ignored	8
Page Size	7	PTE_PS
0	6	PTE_MBZ
Accessed	5	PTE_A
Cache Disabled	4	PTE_PCD
Write Through	3	PTE_PWT
User/Supervisor	2	PTE_U
Read/Write	1	PTE_W
Present	0	PTE_P

页表项包括一些几部分：

名称	地址	ucore中的对应
Physical Page Address	31 downto 12	对应的物理地址高20位
Avail	11 downto 9	PTE_AVAIL
Global	8
0	7	PTE_MBZ
Dirty	6	PTE_D
Accessed	5	PTE_A
Cache Disabled	4	PTE_PCD
Write Through	3	PTE_PWT
User/Supervisor	2	PTE_U
Read/Write	1	PTE_W
Present	0	PTE_P

如果ucore执行过程中访问内存，出现了页访问异常，请问硬件要做哪些事情？

• 将引发页访问异常的地址将被保存在cr2寄存器中
• 设置错误代码
• 引发Page Fault

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

//(1) check if this page table entry is present
    if (*ptep & PTE_P) { 
//(2) find corresponding page to pte
        struct Page *page = pte2page(*ptep); 
//(3) decrease page reference
        page_ref_dec(page);
//(4) and free this page when page reference reachs 0
        if (page -> ref == 0) {
            free_page(page);
        }
//(5) clear second page table entry
        *ptep = 0;
//(6) flush tlb
        tlb_invalidate(pgdir, la);
    }

数据结构Page的全局变量（ 其实是一个数组） 的每一项与页表中的页目录项和页表项有无对应关系？如果有，其对应关系是啥？

有关系。页目录项保存的物理页面地址（即某个页表）以及页表项保存的物理页面地址都对应于Page数组中的某一页。

如果希望虚拟地址与物理地址相等，则需要如何修改lab2，完成此事？ 鼓励通过编程来具体完成这个问题

由于在lab1中是对等映射关系，即

virtual address = linear address = physical address

可以考虑将lab2中的和段页式映射有关的代码恢复到lab1状态。
参考实验指导书中“系统执行中地址映射的四个阶段”一节，逐阶段修改。

• 更改链接脚本tools/kernel.ld，将虚拟地址改为0x100000：

  SECTIONS {
    /* Load the kernel at this address: "." means the current address */
    . = 0x0100000;
  

• 把kernel基地址改回0：

  /* All physical memory mapped at this address */
  #define KERNBASE            0x00000000
  

• 注释掉取消0~4M区域内存页映射的代码

  //disable the map of virtual_addr 0~4M
  // boot_pgdir[0] = 0;
  

实验结果(make qemu)

覆盖的知识点

• 内存分配
• 二级页表的创建

未覆盖的知识点

• 段表的相关内容

与参考答案的区别

• 练习1：自己完成。
• 练习2：写完后未能自己调出bug，后参考了答案中的实现。
• 练习3：自己完成。

总结

在完成本实验代码部分时，由于各个练习需要填写的代码处有完整的指导，因此实现的时候并不困难。但是在回答思考题的时候，发现对OS的理解还远远不够。
最大的困难在于理解练习2中给页中内容清0时，memset的参数填写的是线性地址而非物理地址。之后查看同学讨论后，有同学表示是因为此处已经开启了页表，因此这里硬件会完成线性地址到物理地址的转换。不过目前来看，虽然完成了相应的实验内容，但是对于OS启动时页表相关操作的理解还不够。在实验解释后，我还需要阅读Intel Manual等资料进一步了解x86中的段表页表。