北航OS Lab2 上机

exam

参考往年题总是有帮助的。

21级

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


u_int page_perm_stat(Pde *pgdir, struct Page *pp, u_int perm_mask) {
	u_int count = 0;
	for (u_int i = 0; i < (1u << 10); i++) {
		Pde *pgdir_entryp = pgdir + i;
		if (*pgdir_entryp & PTE_V) {
			Pte *pte = (Pte *) KADDR(PTE_ADDR(*pgdir_entryp));
			for (u_int j = 0; j < (1u << 10); j++) {
				Pte *pte_entryp = pte + j;
				if ((*pte_entryp & PTE_V) && (*pte_entryp & perm_mask) == perm_mask) {
					if (pa2page(PTE_ADDR(*pte_entryp)) == pp)
						count++;
				}
			}
		}
	}
	return count;
}

你需要掌握：

如何对页表进行遍历
一些判断条件的写法（有效性判断、权限位判断、物理页判断）

22级

未找到题面，但内容相对简单，不难看懂。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


u_int page_filter(Pde *pgdir, u_int va_lower_limit, u_int va_upper_limit, u_int num) {
 	u_int begin = va_lower_limit;
 	u_int end = va_upper_limit;
 	struct Page *cur_page;
 	u_int count = 0;
 	for (u_int addr = begin; addr < end; addr += PAGE_SIZE) {
 		cur_page = page_lookup(pgdir, addr, NULL);
 		if (cur_page != NULL && cur_page->pp_ref >= num) {
 			++count;
 		}
 	}
 	return count;
}

你可以先试着读一读。

你需要掌握：

如何遍历某虚拟地址范围内的物理页
注意到page_lookup(pgdir, addr, NULL)中的NULL，思考一下为什么可以用NULL

23级

先来看题面，试着自己想一想！

实现u_int page_conditional_remove(Pde *pgdir, u_int asid, u_int perm_mask, u_long begin_va, u_long end_va)

操作：在从begin_va到end_va的虚拟地址对应的所有页表项中，删除 权限位与perm_mask交集非空的表项 的映射。

返回值：删除的映射数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


u_int page_conditional_remove(Pde *pgdir, u_int asid, u_int perm_mask, u_long begin_va, u_long end_va) {
	struct Page *cur_page;
	Pte *pte_entryp;
	u_int count = 0;
	for (u_long addr = begin_va; addr < end_va; addr += PAGE_SIZE) {
		cur_page = page_lookup(pgdir, addr, &pte_entryp);
		if (cur_page != NULL && (*pte_entryp & perm_mask) != 0) {
			page_decref(cur_page);
			tlb_invalidate(asid, addr);
			*pte_entryp = 0;
			count++;
		}
	}
	return count;
}

你问我怎么知道要page_decref(cur_page);,tlb_invalidate(asid, addr);和*pte_entryp = 0;？

考场是有HINT的！提示你模仿page_remove()函数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


void page_remove(Pde *pgdir, u_int asid, u_long va) {
	Pte *pte;

	/* Step 1: Get the page table entry, and check if the page table entry is valid. */
	struct Page *pp = page_lookup(pgdir, va, &pte);
	if (pp == NULL) {
		return;
	}

	/* Step 2: Decrease reference count on 'pp'. */
	page_decref(pp);

	/* Step 3: Flush TLB. */
	*pte = 0;
	tlb_invalidate(asid, va);
	return;
}

笔者第一次提交就是没有认真参考这个函数，导致漏写*pte_entryp = 0;

那么你应当知道： cur_page = page_lookup(pgdir, addr, &pte_entryp); 这时候为什么不是NULL？因为你需要用到这个页表项的信息了，仅仅拿到cur_page是不够的。

经过简单的练习，相信你应该没有那么畏惧lab2_exam了！

extra

还是老样子，我直接给出题面和我的代码。

由于我曾经没能正视lab2上机，认为通过exam就很难了，因此刚开始看到extra这么全新背景且高度系统化的题面，只是抱着尽力做一做，而不是一定要拿下的态度。等到发现它并没有那么难时，时间也流逝得差不多了。

这次extra相较于往年，更多地考查了对宏定义的运用，函数操作过程完全依据题意。而往年改写函数的套路则直接用在了exam上。

往年题extra就像笔者的lab1_extra一样，例如page_alloc改写为buddy_alloc、swap_alloc

题面

见：

1

https://demiurge-zby.github.io/p/%E5%8C%97%E8%88%AAos-lab2-%E4%B8%8A%E6%9C%BA/lab2_extra.pdf

解答

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53


void *malloc(size_t size) {
	/* Your Code Here (1/2) */
	size_t true_size = ROUND(size, 8);
	struct MBlock *cur;
	LIST_FOREACH(cur, &mblock_list, mb_link) {
		if (cur->size >= true_size && cur->free == 1) {
			if (cur->size - true_size < 32) {	
				cur->free = 0;
				return cur->ptr;
			}
			size_t leave = cur->size - true_size - 24;
			cur->size = true_size;
			struct MBlock* newMBlock = (struct MBlock*)(cur->ptr + true_size);
			newMBlock->size = leave;
			newMBlock->free = 1;
			newMBlock->ptr = (void*) newMBlock->data;
			LIST_INSERT_AFTER(cur, newMBlock, mb_link);
			cur->free = 0;
			return cur->ptr;
		}
	}
	return NULL;
}

void free(void *p) {
	/* Your Code Here (2/2) */
	if (p < HEAP_BEGIN + MBLOCK_SIZE || p > HEAP_BEGIN + HEAP_SIZE) {
		return;
	}
	void *nowp = p - MBLOCK_SIZE;
	struct MBlock* now = (struct MBlock*)nowp;
	if (now->ptr != now->data || now->free == 1) {
		return;
	}
	struct MBlock* next = LIST_NEXT(now, mb_link);
	if (next != NULL && next->free == 1) {
		now->size += 24 + next->size;
		now->ptr = now->data;
		now->free = 1;
		LIST_REMOVE(next, mb_link);
	}
	if(now != LIST_FIRST(&mblock_list)) {
		struct MBlock* prev = MBLOCK_PREV(now, mb_link);
		if (prev->free == 1) {
			LIST_REMOVE(now, mb_link);
			prev->size += 24 + now->size;
			prev->ptr = prev->data;
			return;
		}
	}
	now->free = 1;
	return;
}