操作系统实验：Lab2 物理内存管理
2018-03-29 本文已影响0人
wenj1997
清华大学操作系统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中的段表页表。
