BUAA-OS实验

lab2-1-extra

Posted by cjj on 2022-05-23
Words 986 and Reading Time 4 Minutes
Viewed Times

lab2-1-Extra——一个可能的解决思路

题目要求对物理空间的高32MB地址空间建立伙伴关系，我在这里简单梳理一下我基于数组的实现，由于课上构思比较紧张，代码有些写的不妥的地方请海涵。

首先建立用于存储区间信息的结构体：

1
2
3
4
5
6
7
8
9
10
11
typedef struct Buddy{
	u_int start;
	u_int size;
	u_int time;
	u_int mode;
	u_int f;
}Buddy;

Buddy buddy[100000];
int tot;
int time;

其中，$start$代表该区间的起始位置；

$size$代表区间大小；

$time$是一个比较特殊的量，记录该区间是第几次分裂而来，初始化为0；

$mode$代表区间状态，1代表已分配，0代表未分配，还有-1会表示一个比较特殊的状态（已分裂），后续会详细解释；

$f$也是一个比较特殊的量，记录着该区间是由数组中那个元素分裂而来，初始化为-1；

$tot$记录目前$boddy$的个数，初始化为0。

这里buddy数组我预留了100000，比较保守。

buddy_init的思路：

只需要从 $0x2000000$以起始位置实现8个buddy并存入数组中即可。

1
2
3
4
5
6
7
8
9
10
11
void buddy_init(void) {
	u_int start = 0x2000000;
	u_int size = 0x400000;
	int i;
	tot = 8;
	time = 0;
	for (i = 0; i < 8; i++) {
		//一些初始化操作
	}
	//printf("buddy init finish");
}

buddy_alloc的思路：

大体分为3步：

  1. 寻找符合要求的地址最低的区间
  2. 针对该区间进行分裂操作
  3. 获取各种需要的信息并返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int buddy_alloc(u_int size, u_int *pa, u_char *pi) {
	u_int min = 0x4000010;
	int index = 0;
	int i;
	for (i = 0; i < tot; i++) {
		//(1)寻找符合要求的地址最低的区间
	}
	if (min == 0x4000010) {
        //没找到
		return -1;
	}
	int pos = findMin(index, size);//(2)进行分裂操作

    
	//(3)获取输出信息


	return 0;
}

可以看到，上述比较关键的是进行分裂操作的函数，此处我写的是一个findMin递归函数，核心就是将区间分裂，但不删除旧的区间，仅在数组最后添加新的子区间，并标记旧区间的状态为-1，新子区间的$f$记为旧区间的下标，更新time并标记到新增子区间。

1
2
3
4
5
6
7
8
9
int findMin(int i, u_int size) {
	if (buddy[i].size / 2 < size || buddy[i].size == 0x1000) {
		buddy[i].mode = 1; //(1)找到了合适的区间
		return i; 
	}
	time++;
	//(2)新增两个子区间
	return findMin(tot-2, size);//递归分裂
}

buddy_free的思路：

分两步：

1.寻找满足起始地址为pa的区间并改变其状态为未分配

2.合并可能合并的区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void buddy_free(u_int pa) {
	int i;
    //(1)寻找满足条件的区间，采用倒序，效率高一些
	for (i = tot - 1; i >= 0; i--) {
		if (buddy[i].mode == 1 && buddy[i].start == pa) {
			break;
		}
	}
	buddy[i].mode = 0;
    //(2)合并可能的区间
	if (buddy[i].time != 0) {
		merge(buddy[i].time);
	}
}

上述的关键也是merge函数，本处我是递归实现的：

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
void merge(u_int time) {
	int a = -1, b = -1, i;
	int flag = 0;
    //获取两个可能可以合并的区间
	for (i = tot - 1; i >= 0; i--) {
		if (buddy[i].mode == 0 && buddy[i].time == time) {
			if (a == -1) {
				a = i;
			} else {
				b = i;
				flag = 1;
				break;
			}
		}
	}
	if (flag) {
		buddy[a].mode = -1;
		buddy[b].mode = -1;
        //唤醒他们的父区间，并让两个子区间进入异常态实现舍去。
		buddy[buddy[a].f].mode = 0;
		if ( buddy[buddy[a].f].time != 0) {
			merge(buddy[buddy[a].f].time);
            //递归合并可能的区间
		}
	}
}

总结：

对于本题，我采用了数组实现的方法，为了避免TLE，想到了分裂时并不删除区间的方法，其实是以空间换时间，或许可以尝试链表实现的方法，可能更优雅和高效。

This is copyright.

FEATURED TAGS
BUAA-OS实验
FRIENDS