练习0：把实验1的代码填入本实验中代码有lab1的注释相应的部分。
用understand中的merge工具将实验1中填写代码部分复制到实验2中，如图1。
图1
练习1：实现firstfit连续物理内存分配算法。
对于lab2代码首先对其make，之后在虚拟机中运行查看其错误所在位置如图2。
可以发现其错误出现在default_check(void)这个函数之中，该函数为检查firstfit算法的函数。继续分析错误出现的原因:
struct Page *p0 = alloc_pages(5), *p1, *p2;
assert(p0 != NULL);
assert(!PageProperty(p0));
list_entry_t free_list_store = free_list;
list_init(&free_list);
assert(list_empty(&free_list));
assert(alloc_page() == NULL);
unsigned int nr_free_store = nr_free;
nr_free = 0;
free_pages(p0 + 2, 3);
assert(alloc_pages(4) == NULL);
assert(PageProperty(p0 + 2) && p0[2].property == 3);
assert((p1 = alloc_pages(3)) != NULL);
assert(alloc_page() == NULL);
assert(p0 + 2 == p1);
p2 = p0 + 1;
free_page(p0);
free_pages(p1, 3);
assert(PageProperty(p0) && p0->property == 1);
assert(PageProperty(p1) && p1->property == 3);
assert((p0 = alloc_page()) == p2 - 1); //错误出现的位置
分析源码后可知，在其对内存进行一些列分配释放操作后，再次申请一页内存后出现错误，可知其在最后一次p0 = alloc_page()申请中得到内存页的位置与算法规则不相符，回到default_alloc_pages(size_t n)、default_free_pages(struct Page *base, size_t n)函数中可以分析得到，在分配函数和释放函数中都出现错误：
list_add(&free_list, &(p->page_link));
分配函数中若分得的块大小大于申请页数，则需要将多余的页形成一个块，按照从低地址到高地址的顺序挂回free_list中，而不是直接挂到free_list的后面。
list_add(&free_list, &(base->page_link));
将释放页与空闲页合并操作之后，只是将新的空闲区域挂到了free_list的后面，并没有按照从低地址到高地址的顺序将其挂到free_list之中，导致后面check函数中出现错误。对源代码做如下修改（红色为修改部分）：
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;
while ((le = list_next(le)) != &free_list) {
//从free_list的头开始寻找符合条件的空闲块
struct Page *p = le2page(le, page_link);
if (p->property >= n) {
page = p;
break;
}
}
if (page != NULL) {
list_del(&(page->page_link));
if (page->property > n) { //若分配成功的块总页数比申请页数大
struct Page *p = page + n;
p->property = page->property - n;
list_add(list_prev(le), &(p->page_link));
}
nr_free -= n;
ClearPageProperty(page);
}
return page;
}
释放内存与申请内存思路大致相同：
default_free_pages(struct Page *base, size_t n) {
int flag = 0; //设置标志位
assert(n > 0);
struct Page *p = base;
for (; p != base + n; p ++) {
assert(!PageReserved(p) && !PageProperty(p));
p->flags = 0;
set_page_ref(p, 0);
}
base->property = n;
SetPageProperty(base);
list_entry_t *le = list_next(&free_list);
while (le != &free_list) {
p = le2page(le, page_link);
le = list_next(le);
if (base + base->property == p) {
base->property += p->property;
ClearPageProperty(p);
list_del(&(p->page_link));
}
else if (p + p->property == base) {
p->property += base->property;
ClearPageProperty(base);
base = p;
list_del(&(p->page_link));
}
}
nr_free += n;
le = list_next(&free_list);
while (le != &free_list) {
p = le2page(le, page_link);
le = list_next(le);
struct Page *q = le2page(le, page_link);
if(p>base){ //判断插入位置在头部
list_add(&free_list, &(base->page_link));
flag = 1;
break;
}
if(p<base & base<q){ //判断插入位置在中间
list_add_before(le, &(base->page_link));
flag = 1;
break;
}
}
//判断插入位置在尾部
if(flag == 0)list_add_before(&free_list, &(base->page_link));
}
修改思路：将合并后的空闲页按照从低到高的地址顺序插入到free_list之中，注意边界条件。
修改后再次运行代码如图3：
图3
可以看到check_alloc_page() succeeded,修改成功，分配函数成功运行。
Lab2中的分配代码、释放代码都是以空闲块为一个整体单位，此外在labcode_result中分配与释放都是以页为单位，将所有的空闲页按照从低地址到高地址全部挂到free_list上。
分析上述两种方式，我认为第一种方式更加合理。将所有的空闲页全部挂到free_list链表上开销过大，同时在进行分配时需要将符合条件区域内的所有页进行操作，但是在以块为单位的算法中，只需要将每一块的第一页作为该块的代表挂到free_list上即可，方便操作同时减少开销。
练习2：实现寻找虚拟地址对应的页表项
pde_t *pdep = &pgdir[PDX(la)];
if (!(*pdep & PTE_P)) { //如果不存在
struct Page *page;
if (!create || (page = alloc_page()) == NULL) { //判断是否建立
return NULL;
}
//设置参数，初始化
set_page_ref(page, 1);
uintptr_t pa = page2pa(page);
memset(KADDR(pa), 0, PGSIZE);
*pdep = pa | PTE_U | PTE_W | PTE_P;
}
return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)]; //返回入口
练习3：释放某虚拟地址所在的页并取消对应的二级页表项的映射
if (*ptep & PTE_P) { //判断是否存在
struct Page *page = pte2page(*ptep);
if (page_ref_dec(page) == 0) { //判断是否需要释放
free_page(page);
}
*ptep = 0; //初始化二级页表项
tlb_invalidate(pgdir, la); //更新tlb
}
第二篇：计算机操作系统实验报告(共享内存管理)
数学与计算机科学系实验报告
课程：计算机操作系统 地点：软件实验室二时间： 2013年 5月 17 日
