[C++知识库]C语言_单连续分区存储管理—-可变分区存储管理实现

在学习操作系统时，讲到CPU对内存的寻址，会涉及到内存的管理方式，内存管理方式有如下四种：
1.单连续分区存储管理
2.页式存储管理
3.段式存储管理
4.段页式存储管理
其中，单连续分区存储管理可以分为1.固定分区存储管理和2.可变分区存储管理。
其中最复杂的是可变分区存储管理，内存管理效果最好，但是实际应用最多的是段页式存储管理。段页式存储管理实现考虑情况较少，实现起来相对简单，但是效率也很高。但是如果明白了可变分区存储管理，应该其他内存管理方式也明白了。

单连续分区存储管理

思想

维护两个数据结构：
1.用于存放空闲分区的双向链表
2.是用于存放内存中作业信息的线性表
将内存看成是一个大的块，当有作业申请内存时，就找第一个足够大小的空闲分区，将作业放入该分区，同时更新线性表和链表。如果没有足够大小的空间，就启动主存紧凑（将所有的主存外零头汇聚到高地址处），得到一个大的空闲分区块，然后判断是否满足分配条件。

算法实现

分配内存

只考虑三种情况
|1.作业C不能放入空闲分区。
|2.作业C可以放入空闲分区
___|2.1剩下的内存大小不足以形成内存碎片，直接分配给该作业。
___|2.2.作业C可以放入空闲分区，剩下的内存大小也足以形成内存碎片

void addTable(int name, int size,int addr) {
	//往任务分配表中添加新任务
	for (int i = 0; i < 100; i++) {
		if (tab[i].flag == false) {
			tab[i].name = name;
			tab[i].addr = addr;
			tab[i].length = size;
			tab[i].flag = true;								//该内存块被占用
			return;
		}
	}
}

void alterTable() {
	//修改任务分配表
	std::sort(tab, tab + 100, cmp);									//将任务分配表按从大到小的顺序排序
	tab[0].addr = 0;
	for (int i = 1; i < 100; i++) {
		if (!tab[i].flag) break;
		tab[i].addr = tab[i - 1].addr + tab[i - 1].length;		//更改任务起始地址
	}
}

void compactMem(pFreePartition p) {
	//递归将p空闲分区合并到p.next中
	if (p == NULL) {
		return;
	}
	if (p->next == NULL) {
		head = p;
		p->back = NULL;
		return;
	}
	p->next->size += p->size;										//更改空闲分区的大小
	p->next->address -= p->size;									//更改空闲分区的地址
	compactMem(p->next);
	free(p);
}

void ffcolection() {
	//模拟分配内存模块
	int size;
	int name;
	bool flag = false;												//用于标识分配了一个完整的分区
	printf("\n----------模拟分配作业内存模块----------\n\n");
	printf("\n请输入需要分配的作业名：\n");
	scanf("%d", &name);
	printf("\n请输入需要分配的内存大小(单位 B)：\n");
	scanf("%d", &size);

	pFreePartition p = head;										//设置指针遍历空闲分区链表

	while (p != NULL) {
		if (p->size > size) {
			//当前内存区满足分配条件
			if (p->size - size > MIN) {
				//分配内存以后的空间满足内存碎片
				addTable(name, size, p->address);					//修改作业分配表
				p->size = p->size - size;							//修改空闲区链表
				p->address += size;
			}
			else {
				//分配内存以后的空间不满足内存碎片的条件，直接分配给原进程
				addTable(name, p->size, p->address);
				flag = true;
				if (p == head) {
					//头结点为分区
					head = p->next;									//空闲区链表为空
					free(p);
					p = NULL;
				}
				else {
					//非头结点为分区
					p->back->next = p->next;
					free(p);
					p = NULL;
				}
			}
			break;
		}
		//当前内存区不满足内存分配条件
		p = p->next;
	}

	if (p == NULL && flag == false) {
		//p==NULL有可能分配了一个完整的分区，有可能没有找到一个分区,flag==fasle标识没有找到一个完整的分区
		//尝试主存紧凑
		//printf("test1:%d\n", head->address);
		compactMem(head);
		//printf("test2:%d\n", head->address);
		//更改任务分配表
		alterTable();
		if (head==NULL||head->size < size) {
			printf("无法为任务提供足够内存!!\n");
		}
		else {
			addTable(name, size, head->address);
			head->size -= size;
			head->address += size;
			if (head->size == 0) {
				free(head);
				head = NULL;
			}
		}
	}
}

释放内存

四种情况：
情况一：
情况2：

情况3：
情况4：

实际上四种情况可以当成两种情况处理，先将空闲内存块插入，最后再进行空闲块整合。

void recolection() {
	//模拟释放内存模块
	int name;														//记录删除的进程名
	int address = -1;													//记录删除的进程地址
	int length;														//记录删除的进程长度
	printf("\n----------模拟释放内存模块----------\n\n");
	printf("\n请输入要释放的作业名:\n\n");
	scanf("%d", &name);

	for (int i = 0; i < 100; i++) {									//任务分配表中删除任务name
		if (name == tab[i].name) {
			address = tab[i].addr;
			length = tab[i].length;
			tab[i].flag = false;
			tab[i].addr = INF;
		}
	}
	if (address == -1) {
		printf("任务名不存在！！\n");
		return;
	}

	pFreePartition p = head;
	pFreePartition pre = head;

	while (p != NULL) {
		if (p->address > address) {
			//p空闲分区在address之后
			break;
		}
		pre = p;
		p = p->next;
	}

	if (p == NULL) {
		//释放的任务后无空闲区
		p = (pFreePartition)malloc(sizeof(freePartition));
		p->address = address;
		p->next = NULL;
		p->back = pre;
		p->size = length;
		if (p->back != NULL) {
			//p不是头结点
			p->back->next = p;
		}
		else {
			//p是头结点
			head = p;
		}
	}
	else {
		//释放的任务后有空闲区
		pFreePartition temp = (pFreePartition)malloc(sizeof(freePartition));
		//检测一下p->back是否是空
		temp->next = p;
		temp->back = p->back;
		p->back = temp;
		if (temp->back != NULL) {
			//p不是头结点
			temp->back->next = temp;
		}
		else {
			//p是头结点
			head = temp;
		}
		
		temp->address = address;
		temp->size = length;
	}

/*任务内存恢复测试
	p = head;
	while (p != NULL) {
		printf("test:   address:%d   size:%d\n", p->address, p->size);
		p = p->next;
	}
*/
	p = head->next;
	while (p!=NULL&&p->back!=NULL) {
		//将多个连续的分区合并为一个分区
		if (p->back->address + p->back->size == p->address) {
			//printf("p->address:%d p->size:%d p->next->addreee:%d\n", p->address, p->size, p->next->address);
			pFreePartition temp = p->back;
			p->size += p->back->size;
			p->address = p->back->address;
			head = p;
			free(temp);
		}
		p = p->next;
	}
	printf("内存释放完成\n");
}

查看内存使用情况和作业管理表使用情况

void seeSimulateMemory() {
	//查看当前模拟内存使用情况
	printf("\n空闲分区使用情况:\n\n");
	pFreePartition p = head;
	while (p != NULL) {
		printf("address:%d   size:%d\n", p->address,p->size);
		p = p->next;
	}
	printf("\n-----------任务分配情况----------\n\n");
	for (int i = 0; i < 100; i++) {
		if (tab[i].flag==true) {
			printf("name:%d   address:%d   length:%d\n", tab[i].name, tab[i].addr, tab[i].length);
		}
	}
	printf("空闲分区查看完成");
}

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<algorithm>

#define debug(x) printf("debug:%s",x);
#define freep NULL;

const int INF = 0x3f3f3f3f;
const int MIN = 5;						//定义碎片最小容量

typedef unsigned int Uint;

//空闲区链表
typedef struct node {
	Uint size;							//空区大小（以字节计），包括区头所占空间
	struct node* next;					//后一分区地址
	struct node* back;					//前一分区地址
	Uint address;						//本分区首地址
}freePartition,*pFreePartition;

//作业分配表
typedef struct table {
	int name;							//用户作业名
	Uint length;						//作业区大小
	int addr;							//作业区首地址
	bool flag;							//标记内存的状态，flag=true为占用
}memTable;

pFreePartition head;					//空闲区表头
memTable tab[100];						//作业分配表，最多支持100个作业

void init() {
	//初始化空闲分区表
	int size;
	head = (pFreePartition)malloc(sizeof(freePartition));
	printf("请输入总分区大小：");
	scanf("%d", &size);

	assert(size > 5);											//判断总分区的合理性

	head->next = freep;											
	head->address = 0;
	head->back = freep;
	head->size = size;

	for (int i = 0; i < 100; i++) {
		tab[i].addr = INF;
		tab[i].flag = false;
	}
	return ;
}

void addTable(int name, int size,int addr) {
	//往任务分配表中添加新任务
	for (int i = 0; i < 100; i++) {
		if (tab[i].flag == false) {
			tab[i].name = name;
			tab[i].addr = addr;
			tab[i].length = size;
			tab[i].flag = true;								//该内存块被占用
			return;
		}
	}
}

bool cmp(memTable a, memTable b) {
	return a.addr < b.addr;
}

void alterTable() {
	//修改任务分配表
	std::sort(tab, tab + 100, cmp);									//将任务分配表按从大到小的顺序排序
	tab[0].addr = 0;
	for (int i = 1; i < 100; i++) {
		if (!tab[i].flag) break;
		tab[i].addr = tab[i - 1].addr + tab[i - 1].length;		//更改任务起始地址
	}
}

void compactMem(pFreePartition p) {
	//递归将p空闲分区合并到p.next中
	if (p == NULL) {
		return;
	}
	if (p->next == NULL) {
		head = p;
		p->back = NULL;
		return;
	}
	p->next->size += p->size;										//更改空闲分区的大小
	p->next->address -= p->size;									//更改空闲分区的地址
	compactMem(p->next);
	free(p);
}

void ffcolection() {
	//模拟分配内存模块
	int size;
	int name;
	bool flag = false;												//用于标识分配了一个完整的分区
	printf("\n----------模拟分配作业内存模块----------\n\n");
	printf("\n请输入需要分配的作业名：\n");
	scanf("%d", &name);
	printf("\n请输入需要分配的内存大小(单位 B)：\n");
	scanf("%d", &size);

	pFreePartition p = head;										//设置指针遍历空闲分区链表

	while (p != NULL) {
		if (p->size > size) {
			//当前内存区满足分配条件
			if (p->size - size > MIN) {
				//分配内存以后的空间满足内存碎片
				addTable(name, size, p->address);					//修改作业分配表
				p->size = p->size - size;							//修改空闲区链表
				p->address += size;
			}
			else {
				//分配内存以后的空间不满足内存碎片的条件，直接分配给原进程
				addTable(name, p->size, p->address);
				flag = true;
				if (p == head) {
					//头结点为分区
					head = p->next;									//空闲区链表为空
					free(p);
					p = NULL;
				}
				else {
					//非头结点为分区
					p->back->next = p->next;
					free(p);
					p = NULL;
				}
			}
			break;
		}
		//当前内存区不满足内存分配条件
		p = p->next;
	}

	if (p == NULL && flag == false) {
		//p==NULL有可能分配了一个完整的分区，有可能没有找到一个分区,flag==fasle标识没有找到一个完整的分区
		//尝试主存紧凑
		//printf("test1:%d\n", head->address);
		compactMem(head);
		//printf("test2:%d\n", head->address);
		//更改任务分配表
		alterTable();
		if (head==NULL||head->size < size) {
			printf("无法为任务提供足够内存!!\n");
		}
		else {
			addTable(name, size, head->address);
			head->size -= size;
			head->address += size;
			if (head->size == 0) {
				free(head);
				head = NULL;
			}
		}
	}
}

void recolection() {
	//模拟释放内存模块
	int name;														//记录删除的进程名
	int address = -1;													//记录删除的进程地址
	int length;														//记录删除的进程长度
	printf("\n----------模拟释放内存模块----------\n\n");
	printf("\n请输入要释放的作业名:\n\n");
	scanf("%d", &name);

	for (int i = 0; i < 100; i++) {									//任务分配表中删除任务name
		if (name == tab[i].name) {
			address = tab[i].addr;
			length = tab[i].length;
			tab[i].flag = false;
			tab[i].addr = INF;
		}
	}
	if (address == -1) {
		printf("任务名不存在！！\n");
		return;
	}

	pFreePartition p = head;
	pFreePartition pre = head;

	while (p != NULL) {
		if (p->address > address) {
			//p空闲分区在address之后
			break;
		}
		pre = p;
		p = p->next;
	}

	if (p == NULL) {
		//释放的任务后无空闲区
		p = (pFreePartition)malloc(sizeof(freePartition));
		p->address = address;
		p->next = NULL;
		p->back = pre;
		p->size = length;
		if (p->back != NULL) {
			//p不是头结点
			p->back->next = p;
		}
		else {
			//p是头结点
			head = p;
		}
	}
	else {
		//释放的任务后有空闲区
		pFreePartition temp = (pFreePartition)malloc(sizeof(freePartition));
		//检测一下p->back是否是空
		temp->next = p;
		temp->back = p->back;
		p->back = temp;
		if (temp->back != NULL) {
			//p不是头结点
			temp->back->next = temp;
		}
		else {
			//p是头结点
			head = temp;
		}
		
		temp->address = address;
		temp->size = length;
	}

/*任务内存恢复测试
	p = head;
	while (p != NULL) {
		printf("test:   address:%d   size:%d\n", p->address, p->size);
		p = p->next;
	}
*/
	p = head->next;
	while (p!=NULL&&p->back!=NULL) {
		//将多个连续的分区合并为一个分区
		if (p->back->address + p->back->size == p->address) {
			//printf("p->address:%d p->size:%d p->next->addreee:%d\n", p->address, p->size, p->next->address);
			pFreePartition temp = p->back;
			p->size += p->back->size;
			p->address = p->back->address;
			head = p;
			free(temp);
		}
		p = p->next;
	}
	printf("内存释放完成\n");
}

void recolectionALL() {
	//释放链表的的所有进程
	int size = 0;
	printf("\n释放链表的的所有内存\n\n");
	pFreePartition p = head;
	while (p != NULL) {
		//收集空闲分区内存
		pFreePartition temp = p;
		p = p->next;
		size += p->size;
		free(temp);
	}
	for (int i = 0; i < 100; i++) {
		//收集所有任务表的内存
		if (tab[i].flag) {
			size += tab[i].length;
		}
	}

	p = (pFreePartition)malloc(sizeof(freePartition));
	p->back = NULL;
	p->next = NULL;
	p->address = 0;
	p->size = size;
	printf("内存释放完成");
}

void seeSimulateMemory() {
	//查看当前模拟内存使用情况
	printf("\n空闲分区使用情况:\n\n");
	pFreePartition p = head;
	while (p != NULL) {
		printf("address:%d   size:%d\n", p->address,p->size);
		p = p->next;
	}
	printf("\n-----------任务分配情况----------\n\n");
	for (int i = 0; i < 100; i++) {
		if (tab[i].flag==true) {
			printf("name:%d   address:%d   length:%d\n", tab[i].name, tab[i].addr, tab[i].length);
		}
	}
	printf("空闲分区查看完成");
}

void menu() {
	int key;																//接受命令信息
	init();
	while (1) {
		printf("------------------模拟命令菜单------------------\n\n");
		printf("---------------模拟分配内存  键入1--------------\n\n");
		printf("---------------模拟释放内存  键入2--------------\n\n");
		printf("-------------模拟释放所有内存  键入3--------------\n\n");
		printf("----------------退出系统   键入0----------------\n\n");

		printf("目前内存使用情况如下：\n");
		seeSimulateMemory();

		printf("请输入命令：");
		scanf("%d", &key);
		switch (key) {
		case 1:
			ffcolection();
			break;
		case 2:
			recolection();
			break;
		case 3:
			recolectionALL();
			break;
		case 0:
			recolectionALL();
			exit(0);
		default:
			printf("\n命令不存在，请重新输入\n\n");
		}
	}
}