BUAA-OS Lab2 上机 - 北航操作系统 | Test Blog = FlyingLandlord's Blog

# Lab 2-1 Exam

给出页面保护的概念，如果一个页面处于空闲状态，那么可以利用 page_protect(pp) 函数使得页面 pp 被保护，被保护的页面永远不能再次被 page_alloc 分配出去

同时实现 page_status_query(pp) 函数，支持查询页面 pp 是否处于保护状态

考察要点

struct Page 结构体的内容
空闲页面的链式管理方法
如何遍历 page_free_list （ LIST_FOREACH 的用法）
page_alloc 分配空闲页面的工作原理

解答

首先我们考虑给 struct Page 结构体增加一个字段，表示该页面是否被保护

	struct Page {
	Page_LIST_entry_t pp_link; /* free list link */

	// Ref is the count of pointers (usually in page table entries)
	// to this page. This only holds for pages allocated using
	// page_alloc. Pages allocated at boot time using pmap.c's "alloc"
	// do not have valid reference count fields.
	u_short pp_protect; // Lab 2-1 Exam
	u_short pp_ref;
	};

然后考虑在 page_alloc 分配页面的时候，避免分配 pp_protect 值为 1 的页面

	int page_alloc(struct Page **pp)
	{
	struct Page *ppage_temp;
	if (LIST_EMPTY(&page_free_list)) return -E_NO_MEM;
	while (1) {
	ppage_temp = LIST_FIRST(&page_free_list);
	LIST_REMOVE(ppage_temp, pp_link);
	if (ppage_temp->pp_protect == 1) continue;
	bzero(page2kva(ppage_temp), BY2PG);
	*pp = ppage_temp;
	break;
	}
	return 0;
	}

注意到这里我们的处理方式是遇到一个 pp_protect 的页面就把他从空闲链表中移除，因为按照题意，这个页面永远不会再使用
然后就是加保护和判断，这部分就不难了

	// Lab 2-1 Exam
	int page_protect(struct Page *pp) {
	struct Page *page_i;
	int is_free = 0;
	int is_protect = 0;
	if (!LIST_EMPTY(&page_free_list)) {
	LIST_FOREACH(page_i, &page_free_list, pp_link) {
	if (page_i == pp) {
	is_free = 1;
	break;
	}
	}
	}
	if (pp->pp_protect == 1) is_protect = 1;
	if (is_protect == 1) return -2;
	else if(is_protect == 0 && is_free == 0) return -1;
	else if(is_protect == 0 && is_free == 1) {
	pp->pp_protect = 1;
	return 0;
	}
	}

	int page_status_query(struct Page *pp) {
	struct Page *page_i;
	int is_free = 0;
	int is_protect = 0;
	if (!LIST_EMPTY(&page_free_list)) {
	LIST_FOREACH(page_i, &page_free_list, pp_link) {
	if (page_i == pp) {
	is_free = 1;
	break;
	}
	}
	}
	if (pp->pp_protect == 1) is_protect = 1;
	if (is_protect == 1) return 3;
	else if(is_protect == 0 && is_free == 1) return 2;
	else return 1;
	}

# Lab 2-1 Extra

给出伙伴系统的概念，为 64 MB 物理内存的高 32 MB 建立伙伴系统，功能描述如下：

# 内存区间的初始化
伙伴系统将高地址 32 MB 划分为数个内存区间，每个内存区间有两种状态：已分配和未分配。每个内存区间的大小只可能是4\cross2^i\mathrm{KB}，其中 $i$ 是整数且 $0\le i\le10$ 。初始，共有 8 个 4 MB 大小的内存区间，状态均为未分配。
# 内存区间的分配
每次通过伙伴系统分配 $\space x\space\mathrm{B}$ 的空间时，找到满足如下三个条件的内存区间：
该内存区间的状态为未分配。
其大小不小于 $\space x\space\mathrm{B}$ 。
满足上面两个条件的前提下，该内存区间的起始地址最小。
如果不存在这样的内存区间，则本次分配失败；
否则，执行如下步骤：
设该内存区间的大小为 $\space y\space\mathrm{B}$ ，若 $\frac{y}{2} < x$ 或 $y = 4\mathrm{KB}$ ，则将该内存区间的状态设为已分配，将该内存区间分配并结束此次分配过程。
否则，将该内存区间分裂成两个大小相等的内存区间，状态均为未分配。
继续选择起始地址更小的那个内存区间，并返回步骤 1。
# 内存区间的释放
当一个内存区间使用完毕，通过伙伴系统释放时，将其状态设为未分配。
我们称两个内存区间和是可合并的，当且仅当它们满足如下四个条件：
$x$ 和 $y$ 的状态均为未分配。
$x$ 和 $y$ 是由同一个内存区间一次分裂所产生的两个内存区间。若存在两个可合并的内存区间，则将两个内存区间合并，若合并后仍存在两个可合并的内存区间，则继续合并，直到不存在两个可合并的内存区间为止。

完整题面见链接

本题较难，考察的知识点有：

内存分配的过程 alloc ， init ， free 的基本操作
简单的树形数据结构的建立
二叉树的遍历，节点的插入与删除

其中难点在于第三条，但是更加困难的是需要想到用二叉树来储存管理伙伴系统

在考场上首先没有搞清楚什么叫做模拟内存分配，误以为需要真的去操作内存，然后就修改了 alloc 函数和 Page 结构体，导致 Other Error 出现
同时考试时尝试使用链表去做，发现有很大的问题，而且不容易模拟节点的分裂与合并
有用数组的究极简单做法，但是我不会
需要一定的数据结构知识和调试技巧

下面简单解释放出的代码：

首先用一个结构体 struct buddy_allocator 来存储伙伴系统中的内存块，这里为了简单省事，直接使用静态数组模拟链表， cnt 表示当前使用到的数组下标编号， st_addr 表示该块起始地址， size 表示该块大小，实际大小由宏 BLOCKSIZE 定义
初始化无需多说，直接分配 8 个块，初始大小 4 MB，初始化相应地址即可
分配采用递归方式进行，对于 8 个初始块尝试调用 _buddy_alloc 函数，进行分配，如果块的大小不满足上述条件，那么就对块进行分裂（也就是插入二叉树节点），如果块被使用过那么就直接返回 - 1，先尝试分配左边，再尝试分配右边，这样可以保证得到最小的地址
回收保证地址一定合法，因此找到 pa 相符的叶子节点，然后直接把 used 置为 0，然后在回溯过程中判断是否两个儿子未被使用并且是叶子节点，如果是，那么就直接删去儿子节点，表示合并两个块

	// Lab 2-1 Extra
	struct buddy_allocator {
	int size;
	int used;
	int st_addr;
	int lson, rson;
	}buddy[700005];
	static int cnt = 1;

	#define BLOCKSIZE(i) ((4*(1<<i)) << 10)

	void buddy_initialize(int index, int size, int addr) {
	buddy[index].size = size;
	buddy[index].st_addr = addr;
	buddy[index].used = 0;
	buddy[index].lson = 0;
	buddy[index].rson = 0;
	}

	void buddy_init(void) {
	int i = 0;
	cnt = 1;
	for (i = 0; i < 8; i++) {
	buddy_initialize(cnt++, 10, 32 * (1 << 20) + i * 4 * (1 << 20));
	}
	}

	int _buddy_alloc(u_int size, int p, int fa) {
	if (BLOCKSIZE(buddy[p].size) / 2 < size \|\| buddy[p].size == 0) { if (!buddy[p].used && BLOCKSIZE(buddy[p].size) >= size && !buddy[p].lson && !buddy[p].rson) {
	buddy[p].used = 1;
	return p;
	} else return -1;
	}
	if (buddy[p].used) return -1;
	if (buddy[p].lson == 0 && buddy[p].rson == 0) {
	buddy[p].lson = cnt++;
	buddy[p].rson = cnt++;
	buddy_initialize(buddy[p].lson, buddy[p].size-1, buddy[p].st_addr);
	buddy_initialize(buddy[p].rson, buddy[p].size-1, buddy[p].st_addr + BLOCKSIZE(buddy[p].size)/2);
	}
	int r;
	r = _buddy_alloc(size, buddy[p].lson, p);
	if (r == -1) r = _buddy_alloc(size, buddy[p].rson, p);
	return r;
	}

	int buddy_alloc(u_int size, u_int pa, u_char pi) {
	int i = 1;
	for (i = 1; i <= 8; i++) {
	int p = i;
	if (buddy[p].used && !buddy[p].lson && !buddy[p].rson) continue;
	int r = _buddy_alloc(size, p, 0);
	if (r != -1) {
	*pa = buddy[r].st_addr;
	*pi = buddy[r].size;
	return 0;
	}
	}
	return -1;
	}

	void _buddy_free(u_int pa, int i, int fa) {
	if (i == 0) return;
	if (pa == buddy[i].st_addr && !buddy[i].lson && !buddy[i].rson) {
	buddy[i].used = 0;
	return;
	}
	if (pa < buddy[buddy[i].rson].st_addr) _buddy_free(pa, buddy[i].lson, i);
	else _buddy_free(pa, buddy[i].rson, i);
	if (!buddy[buddy[i].lson].used && !buddy[buddy[i].rson].used &&
	!buddy[buddy[i].lson].lson && !buddy[buddy[i].lson].rson &&
	!buddy[buddy[i].rson].lson && !buddy[buddy[i].rson].rson) {
	buddy[i].used = 0;
	buddy[i].lson = 0;
	buddy[i].rson = 0;
	}
	}

	void buddy_free(u_int pa) {
	int i;
	for (i = 1; i <= 8; i++) {
	if (pa < (i-1) * 4 * (1 << 20) + 32 * (1 << 20)) continue;
	if (pa >= i * 4 * (1 << 20) + 32 * (1 << 20)) continue;
	_buddy_free(pa, i, 0);
	}
	}

# Lab 2-2 Exam

倒查页表，根据给出的物理页查找有多少虚拟页被映射到了该物理页

考察知识点有：

如何根据页表查找页面物理地址
KADDR ， PTE_ADDR ， page2pa 等函数的英勇

几个注意点：

需要根据 *pgtable_entry | PTE_V 页表页是否有效
根据页表自映射相关知识，页表自身所在页面已经包含在了页目录中，因此无需特殊判断
判断时语句是唯一难点， page2pa(pp) == PTE_ADDR(*pgtable_entry)

	// Lab 2-2 Exam
	int inverted_page_lookup(Pde pgdir, struct Page pp, int vpn_buffer[]) {
	int i, j;
	int tot = 0;
	for (i = 0; i < 1024; i++) {
	Pde *pgdir_entry = pgdir + i;
	if ((*pgdir_entry) & PTE_V) {
	Pte pgtable = KADDR(PTE_ADDR(pgdir_entry));
	for (j = 0; j < 1024; j++) {
	Pte *pgtable_entry = pgtable + j;
	if ((*pgtable_entry) & PTE_V) {
	if (page2pa(pp) == PTE_ADDR(*pgtable_entry)) vpn_buffer[tot++] = (i << 10) \| j;
	}
	}
	}
	}
	return tot;
	}

# Lab 2-1 Exam

# Lab 2-1 Extra

# 内存区间的初始化

# 内存区间的分配

# 内存区间的释放

# Lab 2-2 Exam

BUAA-OS Lab3上机

BUAA-OS Lab5实验总结