一、实习内容
主存储器空间的分配和回收。

二、实习目的
通过本实习帮助理解在不同的存储管理方式下应怎样进行存储空间的分配和回收。

三、实习题目
在分页管理方式下采用位示图来表示主存分配情况，实现主存分配和回收

四、设计思想
1.设计思路
（1）假定系统的主存被分成大小相等的64个块，用0/1对应空闲/占用。
（2）当要装入一个作业时，根据作业对主存的需求量，先查空闲块数是否能满足作业要求，若能满足，则查位示图，修改位示图和空闲块数。位置与块号的对应关系为：
块号=j*8+i，其中i表示位，j表示字节。
根据分配的块号建立页表。页表包括两项：页号和块号。
（3）回收时，修改位示图和空闲块数。


2.主要数据结构

struct bitGraph
{
	int a[8][8];//位示图
	int freebit;//空闲块数
}BG;

//进程的数据结构
struct proc
{
	char name[10];//进程名
	int *PT;//页表
	int size;//进程所需要的空间
	struct proc *next;
	struct proc *front;
};

3.主要代码结构及代码段分析

//分配内存
int getMalloc()
{
	int i = 0,j = 0,p = 0,k = 0,flag = 0;
	struct proc *process;
	process = (struct proc *)malloc(sizeof(struct proc));
	printf("请输入进程名：\n");
	scanf("%10s",process->name);
	process->next = head->next;
	if(head->next != NULL)
		head->next->front = process;
	head->next = process;
	process->front = head;
	printf("请输入进程所需内存大小：\n");
	scanf("%d",&process->size);
	if(process->size > BG.freebit)
	{
		printf("对不起，空闲空间不足以分配如此多内存给该进程。\n");
		return 0;
	}
	else
	{
		process->PT = new int [process->size];
		for(i=0;i<8 && flag==0;i++)
			for(j=0;j<8 && flag==0;j++)
			{
				if(!BG.a[i][j])
				{
					BG.a[i][j] = 1;
					BG.freebit--;
					process->PT[k] = 8*i + j;
					k++;
					if(k == process->size)
						flag = 1;
				}
			}
	}
	printf("\n位示图：\n");
	for(i=0;i<8;i++)
	{
		for(j=0;j<8;j++)
			printf("%d",BG.a[i][j]);
		printf("\n");
	}
}

//回收内存
int setFree()
{
	char name[10];
	int flag = 0,i = 0,j = 0;
	struct proc *p = head;
	printf("请输入需要回收的进程名：");
	scanf("%10s",&name);
	for(p = head;p != NULL;p = p->next)
	{
		if(strcmp(p->name , name)==0)//找到该进程，将其从进程链表中删除，并改写位示图
		{
			flag = 1;
			for(i=0;i < p->size;i++)
			{
				int m = p->PT[i]/8;
				int n = p->PT[i]%8;
				BG.a[m][n]= 0;
				BG.freebit++;
			}
			if(p->front != NULL)
			{
				if(p->next != NULL)
				{
					p->front->next = p->next;
					p->next->front = p->front;
					free(p);
				}
				else
				{
					p->front->next = p->next;
					free(p);
				}
			}
			else
			{
				p->next->front = p->front;
				free(p);
			}
		}
	}
	if(flag == 0)
		printf("没有该进程！\n");
	else
		printf("回收成功！\n");
	printf("\n位示图：\n");
	for(i=0;i<8;i++)
	{
		for(j=0;j<8;j++)
			printf("%d",BG.a[i][j]);
		printf("\n");
	}
}

//显示进程页表
int showMemo()
{
	char name[10];
	int flag = 0,i = 0;
	struct proc *p = head;

	printf("请输入进程名：");
	scanf("%10s",&name);
	for(p = head;p != NULL;p = p->next)
	{
		if(strcmp(p->name , name)==0)
		{
			printf("	进程名  页号    块号\n");
			for(i=0;isize;i++)
			{
				printf("%10s	%d	%d\n",p->name,i,p->PT[i]);
				flag = 1;
			}
		}
	}
	if(flag == 0)
		printf("没有该进程！\n");
}

int main()
{
	char choose;
	BG.a[8][8] = 0;
	BG.freebit = 64;

	head = (struct proc *)malloc(sizeof(struct proc));
	if(head==NULL)
	{
		printf("error in allocating...\n");
	}
	else
		printf("successed\n");
	head->next = head->front = NULL;//建立进程的头结点
        char buf[128];
	do
	{
	system("clear");
	printf("---------------------------\n");
	printf("1.新进程请求内存空间\n");
	printf("2.回收空间\n");
	printf("3.显示进程页表\n");
	printf("4.退出\n");
	printf("---------------------------\n");
		printf("请选择：");
		scanf("%c",&choose);
		switch(choose)
		{
			case '1':
				getMalloc();
				gets(buf);break;
			case '2':
				setFree();
				gets(buf);break;
			case '3':
				showMemo();
				gets(buf);break;
			case '4':
				exit(1);gets(buf);break;
			default:
				gets(buf);
				printf("输入错误！请重新输入。\n");break;
		}
		printf("\n");
		getchar();
	}while(choose != '4');
}

五、上机实习所用平台及相关软件
本程序在Linux平台（Ubuntu8.04.1）下，使用vi编辑器编写，g++编译通过。

六、调试过程
测试数据：
进程名    请求内存大小
aaa    3
bbb    10
ccc    30
ddd    1000
测试结果：
截图（略）

七、总结
（1）我使用了一个二维数组作为位示图的数据结构，这样简单明了。而进程页表使用一个一维数组，用数组下标即可表示页号，节省了存储空间。
（2）在程序中充分考虑到出错处理。比如在功能选择菜单中，若用户输入非法字符则提示“输入错误！请重新输入”；在用户申请内存时，若要求的空间大小大于空闲空间大小，则提示“空闲空间不足”；在回收内存空间和显示进程页表时，若用户输入的进程名不存在，则提示“没有该进程”。这样提高了程序的健壮性。
（3）通过本实验，我进一步加深了对使用位示图方式表示和实现主存分配回收的理解，同时也得到了将系统理论实践的机会，熟练了编程能力。