BUAA-OS

「BUAA OS Lab2-1-Extra」数组模拟伙伴系统

Posted by saltyfishyjk on 2022-04-15
Words 2.1k and Reading Time 8 Minutes
Viewed Times

「BUAA OS Lab2-1-Extra」数组模拟伙伴系统

Part 0 前言

本篇博客记录模拟伙伴系统的数组实现方法，Part 1为题目描述，Part 2为设计分析，Part 3为课上源码（已AC并开源）参考，读者可自取所需。

同时，本博客系统已支持评论区，欢迎您参考 Gitment评论区配置与使用中Part2开通您在本博客的权限，留下您的想法。

Part 1 题目描述

请你对现有的物理内存管理机制进行修改，对 MOS 中$ 64 MB $物理内存的高地址 $ 32 MB $建立伙伴
系统。下面对本题中所需要实现的伙伴系统进行描述：

内存区间的初始化

伙伴系统将高地址$ 32 MB $划分为数个内存区间，每个内存区间有两种状态：已分配和未分配。

每个内存区间的大小只可能是$ 4 \times 2^i KB $，其中$ i $是整数且$ 0 \le i \le 10 $。

初始，共有$ 8 $个$ 4 MB $大小的内存区间，状态均为未分配。

内存区间的分配

每次通过伙伴系统分配 $ x B $的空间时，找到满足如下三个条件的内存区间：

  • 该内存区间的状态为未分配。
  • 其大小不小于 $x B $。
  • 满足上面两个条件的前提下，该内存区间的起始地址最小。

如果不存在这样的内存区间，则本次分配失败；否则，执行如下步骤：

  1. 设该内存区间的大小为 $ y B $，若$ \frac{y}{2} < x $或$ y = 4 K$，则将该内存区间的状态设为已分配，将该内存区间分配并结束此次分配过程。
  2. 否则，将该内存区间分裂成两个大小相等的内存区间，状态均为未分配。
  3. 继续选择起始地址更小的那个内存区间，并返回步骤 1。

内存区间的释放

当一个内存区间使用完毕，通过伙伴系统释放时，将其状态设为未分配。
我们称两个内存区间$ x $和$ y $是可合并的，当且仅当它们满足如下四个条件：

  1. $ x $和$ y $的状态均为未分配。
  2. $ x $和$ y $是由同一个内存区间一次分裂所产生的两个内存区间。
    若存在两个可合并的内存区间，则将两个内存区间合并，若合并后仍存在两个可合并的内存区间，则继续合并，直到不存在两个可合并的内存区间为止。

请你实现如下的三个函数：

初始化函数 buddy_init

  • 函数原型为： void buddy_init(void)
  • 调用此函数后，为 MOS 中 $ 64 MB $物理内存的高地址$ 32 MB $初始化伙伴系统。初始化结束后，伙伴系统中仅有只有$ 8 $个$ 4 MB $的待分配内存区间。

分配函数 buddy_alloc

  • 函数原型为：int buddy_alloc(u_int size, u_int *pa, u_char *pi)
  • 调用此函数后，通过伙伴系统分配大小不小于size字节的空间，分配逻辑见上述描述。
    如果分配失败，返回$ −1$。否则，将pa指向所分配内存区间的起始地址，设所分配内存区间的大小为$ 4 \times 2^i KB $，令*pi = i，并返回$ 0 $。
    ，令*pi = i，并返回$ 0 $。

释放函数 buddy_free

  • 函数原型为：void buddy_free(u_int pa)
  • 调用此函数后，通过伙伴系统释放一个状态为已分配的内存区间，其起始地址为pa 。释放后的合并逻辑见上述描述。

注意事项

你需要先在include/pmap.h中加入如下三个函数定义： 

1
2
3
void buddy_init(void);
int buddy_alloc(u_int size, u_int *pa, u_char *pi); 
void buddy_free(u_int pa);

之后再在mm/pmap.c中实现这三个函数。

评测逻辑

评测过程中，我们会将所有的Makefile文件、include.mk以及 init/init.c替换为 lab2 初始配置，接着将init/init.c中的mips_init函数改为如下形式：

1
2
3
4
5
6
7
8
void mips_init(){
mips_detect_memory(); 
mips_vm_init();
page_init(); 
buddy_init(); 
buddy_test();
*((volatile char*)(0xB0000010)) = 0; 
}

最后的*((volatile char*)(0xB0000010)) = 0;会终止 Gxemul 模拟器的运行，避免占用评测资源。

buddy_test在评测过程中新添加到init/init.c的函数，其中仅包含以下两种操作：

  • 调用buddy_alloc函数，我们保证size不为$ 0 $。
  • 调用buddy_free函数，我们保证pa是之前某次调用buddy_alloc所得到的。

每调用一个函数算一次操作，我们保证总操作数不超过$ 1000 $。

运行make指令的最大时间为$ 10 $秒，运行Gxemul模拟器的最大时间为$ 4 $秒。

设伙伴系统管理的物理页数为$ n $，标程中buddy_alloc和buddy_free两个函数的时间复杂度均为$ O(n) $，请你尽量以此复杂度设计算法。

Part 2 设计分析

基于树的实现

通过题目的描述，我们可以自然地得到树的设计思路：设计TreeNode结构体为树节点，储存左右儿子（不一定存在）和父亲的指针信息，储存分配信息以及储存空间大小。

受限于上机时间、实现难度和buddy_free函数时间复杂度的考虑，笔者最终并没有采取这种办法，以下着重介绍第二种思路：基于数组的实现。

基于数组的实现

题目给出，对于给定size，若其可能被分配，其分配大小只能为$ 4 \times 2^i KB $，因此，我们以一页（$ 4 KB $）为单位，将内存分为$ 8 \times 1024 $个页面，利用数组buddyPage[8 * 1024]表示。

对于页数$2 ^ i $，我们按照如下公式计算得到：

得到页数$2 ^ i $后，由于伙伴系统的特点，我们从下标$ 0 $开始，以$2 ^ i $为步长，从低至高遍历buddyPage，若某一步内buddyPage全部未分配，则将其标记为该次分配并返回；若遍历结束仍未找到满足条件的块，标记为未找到。

对于buddy_free函数，我们需要释放以给定地址开始的内存，因此，我们在分配时需要区分不同的分配。举例来说，两个相邻的$ 4KB $在两次分配中分别被分配，那么当给定第一个$ 4KB $的地址时，只能释放第一个$ 4KB $。

基于数组的实现保证了我们时间复杂度为$ O(n) $，同时正确性可以逻辑证明，兼顾了实现难度和实际性能。

Part 3 课上源码

全局变量与辅助函数

1
2
3
4
5
6
7
8
9
10
11
int buddyPage[9999] = {0};
int flagWhole = 1;
int pow2(int n)
{
	int i = 0;
	int ans = 1;
	while(n--) {
		ans *= 2;
	}
	return ans;
}

buddy_init

1
2
3
4
5
6
7
void buddy_init(void)
{
	int i;
	for (i = 0;i <= 9000;i++) {
		buddyPage[i] = 0; // signals not alloced
	}
}

buddy_alloc

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
54
55
56
57
58
59
int buddy_alloc(u_int size, u_int *pa, u_char *pi)
{
	int MAX = 4 * 1024 * 1024; // MAX = 4MB
	if (size > MAX) {
		return -1;
	}
	int cnt = 0;
	int pageSize = 4 * 1024; // pageSize = 4KB
	if (size <= pageSize) {
		cnt = 1;
	} else {
		if (size % pageSize == 0) {
			cnt = size / pageSize;
		} else {
			cnt = size / pageSize + 1;
		}
	}
	int i = 0;
	int tempPi = 0;
	for (i = 0;i <= 10;i++) {
		if (pow2(i) >= cnt) {
			cnt = pow2(i);
			tempPi = i;
			break;
		}
	}
	int j;
	int nPage = 8 * 1024; // total 8K pages
	int ava = 1; // signal whether has area to alloc
	for (i = 0;i < nPage;i += cnt) {
		ava = 1;
		int l = i;
		int r = i + cnt;
		//int ava = 1; // signal whether this area can be alloced
		for (j = l;j < r;j++) {
			if (buddyPage[j] != 0) {
				//printf("buddyPage[%d] = %d\n", j, buddyPage[j]);
				ava = 0;
				break;
			}
		}
		if (ava == 1) {
			*pa = 0x2000000 + (i) * pageSize;
			*pi = tempPi;
			for (j = l;j < r;j++) {
				buddyPage[j] = flagWhole;
			}
			flagWhole++;
			break;
		}
		//printf("Need %d pages\n", cnt);
		//printf("Not Find ava betwen Page %d and %d\n", l, r);
	}
	if (ava == 1) {
		return 0;
	} else {
		return -1;
	}
}

buddy_free

1
2
3
4
5
6
7
8
9
10
11
void buddy_free(u_int pa) 
{
	int id = pa - 0x2000000;
	id = id / (4 * 1024);
	int key = buddyPage[id];
	int i = id;
	while(buddyPage[i] == key) {
		buddyPage[i] = 0;
		i++;
	}
}

Part 4 后记

Part2中提到了树的实现，笔者不会写树了（菜qwq），并且分析时感觉可能需要递归释放空间，可能会超过$ O(n) $的限制，因此没有继续深究，若读者通过此方法实现或有想法，欢迎和我取得联系一起探讨。

Part3中的代码为上机时最后一次提交，注释掉了一些调试用代码，并且很多地方的细节处理的不够漂亮（可能还有英文单词拼写错误），欢迎批评指正。

This is copyright.

FEATURED TAGS
BUAA-OS
FRIENDS