memory1.0.cpp

模拟linux操作系统的内存分配与回收

#include "stdio.h"
#include "stdlib.h"
#include <string>
#include "math.h"

//--------常量定义--------------//
#define TOTAL_SIZE 1000		//用户向系统申请内存总共的大小
#define ADDR_LENGTH 7		//地址的长度（eg: 7位）

//--------数据结构和全局变量定义--------------//
struct node					//节点定义，每个节点代表一个内存空闲区
{
	int size;				//该节点代表内存空闲区的大小
	node *prior;			//前一个节点
	node *next;				//后一个节点
	char *p;				//指针，指向该节点所代表的内存空闲区的首地址
};

char *head;					//指针，指向向系统申请的内存块的首地址
struct node *present;		//指针，指向当前操作的节点
char quit, error;			//quit用以判断用户是否要求退出，error用以判断程序中是否有出错

//------------函数定义-----------------//
void help(void);									//帮助函数，显示操作说明
int  Error(char);									//报错函数, 调用出错类型, 返回出错类型
void allocation(int);								//内存分配函数, 调用用户申请分配内存的大小
void sub_reclaim(struct node *, struct node *, char *, int);//内存回收函数的子函数, 
							//调用申请回收的内存的地址和大小, 及上一空闲区和下一空闲区的首地址
void reclaim(char *, int);							//内存回收函数, 调用申请回收的内存的地址和大小
void vacancy(void);									//内存使用情况显示函数
void init(void);									//初始化函数
void process(void);									//流程控制函数

//-----------主函数--------------//
void main()
{
	struct node *tmp;

	init();													//初始化

	while(!quit)											//主循环
	{
		error = 0;
		process();
	}

	free (head);											//释放先前向系统申请的内存

	for(tmp = present->next->next; tmp != present; tmp = tmp->next)   //释放所有节点
	{
		free(tmp->prior);
	}
	if(present->prior != present) free(present->prior);
	free(present);

	return;
};

void init()
{	
	head = (char *)malloc(TOTAL_SIZE) ;						//申请一块内存区
	if (head == NULL) { printf("memory application failed.\n"); return; }	//内存申请失败
	printf("a %d-byte memory block ranging address %d-%d is available.\n", TOTAL_SIZE, head, head + TOTAL_SIZE - 1);

	present = (struct node *) malloc(sizeof(struct node));	//产生第一个节点
	present->p = head;
	present->size = TOTAL_SIZE;
	present->next = present;
	present->prior = present;
	
	quit = 0;
	error = 0;
	help();													//显示操作说明
};

void help(void)
{
	printf("--------------------------------------------------------------------\n"); 
	printf("Type \"m size\" to ask for memory. eg: \"m 100\" .\n");
	printf("Type \"f address size\" to free used memory. eg: \"f 3279648 100\".\n");
	printf("Type \"h\" for help.\n");
	printf("Type \"v\" to show vacancy.\n");
	printf("Type \"q\" to quit.\n");
	printf("--------------------------------------------------------------------\n");
};

void process()
{
	char temp, input[100];
	int i, m_length, free_m_addr;

	printf(">");
	gets(input);											//读取用户输入的字符
	i = strlen(input)-1;
	switch (input[0])										//判断格式规范性, 数据预处理
	{
		case 'm':											//内存分配命令
			if (input[1] != ' ' || i < 2) { error = Error(1); break; }

			m_length = 0;

			for (; i >= 2; i--) 
			{
				if ( !isdigit(input[i]) ) { error = Error(1); break; }
				temp = input[i] - 48;						//将ASCII码转换成整数
				m_length += temp * pow( 10,  strlen(input)-1-i ); 
				if (m_length > TOTAL_SIZE) break;
			}
			if (m_length > TOTAL_SIZE) { error = Error(2); break; }
			else if (!m_length) { error = Error(2); break; }

			if (!error)	{ allocation(m_length);	vacancy(); }		//执行内存分配
			break;

		case 'f':											//内存回收命令
			if (input[1] != ' ' || i < 10 )	{ error = Error(1); break; }
			else if (input[9] != ' ') { error = Error(3); break; }	

			free_m_addr = 0;

			for (i = ADDR_LENGTH+1; i >= 2; i--)
			{
				if ( !isdigit(input[i]) ) { error = Error(1); break; }	
				temp = input[i] - 48;						//将ASCII码转换成整数
				free_m_addr += temp * pow(10, 8-i);
				if(free_m_addr > (int)head+TOTAL_SIZE - 1) break;
			}

			if(free_m_addr < (int)head || free_m_addr > (int)head+TOTAL_SIZE - 1) 
			{ error = Error(3); break; }

			m_length = 0;

			for (i = strlen(input)-1; i >= 10; i--) 
			{
				if ( !isdigit(input[i]) ) { error = Error(1); break; }	
				temp = input[i] - 48;						//将ASCII码转换成整数
				m_length += temp * pow( 10, strlen(input)-i-1 ); 
				if (m_length > TOTAL_SIZE) break;
			}

			if (m_length > TOTAL_SIZE || (int)free_m_addr + m_length > (int)head + TOTAL_SIZE ) 
			{ error = Error(2); break; }
			else if (!m_length) { error = Error(2); break; }

			if (!error)										//符合规范，进入内存回收函数
			{
				reclaim((char *)free_m_addr, m_length); 
				vacancy(); 
			}
			break;

		case 'h': 
			if (strlen(input) == 1) { help(); break; }		//显示操作说明
			error = Error(1);  break;

		case 'v':
			if (strlen(input) == 1) { vacancy(); break; }	//显示内存使用情况
			error = Error(1);  break;

		case 'q': 
			if (strlen(input) == 1) { quit = 1; return; }	//退出
			else { error = Error(1); break; }

		default: error = Error(1); break;
	}
}

int Error(char error)
{
	switch (error)
	{
		case 1: printf(" bad command!\n"); break;
		case 2: printf(" bad memory assignment!\n"); break;
		case 3: printf(" invalid address!\n"); break;
		default: break;
	}
	return (error);
};

void allocation(int m_size)
{
	char *temp;
	struct node *tmp;
	temp = present->p;
	do
	{
		if (present->size >= m_size)							//找到合适的空闲去
		{
			present->p += m_size;
			present->size-= m_size;
			if(present->size == 0)
			{
				if(present->next == present)					//分配后，内存无空闲区
				{
					printf(" All memory allocated.\n");
					present->p = head;
				}
				else											//空闲区大小 = 分配大小
				{
					present->prior->next = present->next;
					present->next->prior = present->prior;
					tmp = present;
					present = present->next;
					free(tmp);
				}
			}
			return;
		}
		else present = present->next;							//至下一空闲区
	} while ( temp != present->p );						//对内存块中空闲区的搜寻至多一个循环
	printf(" not enough memory!\n");
};

void reclaim(char *addr, int size)
{
	struct node *tmp_node;
	char *temp, up, down;
	up = 0;
	down = 0;
	temp = present->p;
	tmp_node = present;
	
	if(tmp_node->next == tmp_node && tmp_node->size == 0)			//内存使用已满
	{
		tmp_node->p = addr;
		tmp_node->size = size;
		present = tmp_node;
		return;
	}
	else
	{
		do
		{
			if (   (addr >= tmp_node->p && addr < tmp_node->p + tmp_node->size)
				|| (addr + size - 1 >= tmp_node->p && addr + size - 1 <= tmp_node->p + tmp_node->size - 1)
				|| (addr < tmp_node->p && addr + size - 1 > tmp_node->p + tmp_node->size - 1) )
			{												//申请回收的内存块与空闲区有交叠
				printf("Unable to free memory that's not used.\n");
				return;
			}
			else if (addr >= tmp_node->p + tmp_node->size)	//需回收的内存块在此空闲区后面
			{
				if (up) { sub_reclaim(tmp_node, tmp_node->next, addr, size); return; }
				if (tmp_node->next->p > tmp_node->p )
				{
					tmp_node = tmp_node->next;				//寻找下一空闲区
					down = 1;
					continue;
				}
				else { sub_reclaim(tmp_node, NULL, addr, size); return; }
			}
			else if (addr + size <= tmp_node->p)			//需回收的内存块在此空闲区前面
			{
				if (down) { sub_reclaim(tmp_node->prior, tmp_node, addr, size); return; }
				if (tmp_node->prior->p < tmp_node->p)
				{
					tmp_node = tmp_node->prior;
					up = 1;									//寻找上一空闲区
					continue;
				}
				else { sub_reclaim(NULL, tmp_node, addr, size); return; }
			}
			else { Error(2); printf(" Unknow error.\n"); return; }
		} while(temp != tmp_node->p);
	}
};

void sub_reclaim(struct node *above, struct node *after, char *addr, int size)
{
	struct node *newnode;
	newnode = (struct node *)malloc(sizeof(struct node));

	if(above == NULL)									//申请回收的内存地址之前没有空闲区
	{
		if(after->p == addr + size)						//与后一空闲区合并
		{ 
			after->size += size;
			after->p -= size;
			present = after;
			return;
		}
		else if(after->p > addr + size)					//插入新节点
		{
			newnode->p = addr;
			newnode->size = size;
			newnode->prior = after->prior;
			newnode->next = after;
			after->prior->next = newnode;
			after->prior = newnode;
			present = newnode;
		}
		else { Error(2); }
	}
	else if (after == NULL)								//申请回收的内存地址之后没有空闲区
	{					
		if(above->p + above->size == addr) { above->size += size; return; }	//与前一空闲区合并
		else if(above->p + above->size < addr)			//插入新节点
		{
			newnode->p = addr;
			newnode->size = size;
			newnode->next = above->next;
			newnode->prior = above;
			above->next->prior = newnode;
			above->next = newnode;
			present = newnode;
		}
		else { Error(2); return; }
	}
	else												//申请回收的内存块处在两个空闲区之间
	{
		if(addr == above->p + above->size)				//与前一空闲区合并
		{
			above->size += size;
			if(addr + size == after->p)					//与后一空闲区合并
			{
				above->size += after->size;
				above->next = after->next;
				after->next->prior = above;
				present = above;
				free(after);
			}
		}
		else											//与前一空闲区不相连
		{
			if(addr + size == after->p)					//与后一空闲区合并
			{
				after->p = addr;
				after->size += size;
				present = after;
			}
			else										//插入新节点
			{
				newnode->p = addr;
				newnode->size = size;
				newnode->next = after;
				newnode->prior = above;
				above->next = newnode;
				after->prior = newnode;
				present = newnode;
			}
		}
	}
};

void vacancy()
{
	struct node *temp, *temp2;
	int count = 0;
	temp = present;

	while(1) { if (temp->prior->p >= temp->p) break; temp = temp->prior; }	//寻找第一个空闲区

	temp2 = temp;

	printf(" -------------------------------------\n");
	printf("      free\n");

	if (temp2->p == head && temp2->size == 0)				//内存无空闲区
	{
		printf("      none  \n");
		printf(" -------------------------------------\n");
		return;
	}

	do
	{
		if(temp2->size == 1)
		{ printf(" %d-%d\t%dbyte\n", temp2->p, temp2->p + temp2->size - 1, temp2->size); }
		else
		{ printf(" %d-%d\t%dbytes\n", temp2->p, temp2->p + temp2->size - 1, temp2->size); }

		temp2 = temp2->next;
		count++;
	} while (temp2->p > temp2->prior->p && count <= (TOTAL_SIZE / 2));

	printf(" -------------------------------------\n");
};