memsys.cpp

本程序用于模拟内存连续分配与分页式分配的管理

// MemSys.cpp : Defines the entry point for the console application.
// 本程序用于模拟内存连续分配与分页式分配的管理

#include "stdafx.h"
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <conio.h> 
#include <time.h>

#define getpch(type) (type*)malloc(sizeof(type)) 
#define NIL 999999 
#define re printf("\n")

//----------------系统内部函数------------------------
void _sleep( int n )		//停顿n秒,该函数为VC函数，在不同环境下可能会不同
{	clock_t goal;
	goal = (clock_t)n * CLOCKS_PER_SEC + clock();
	while( goal > clock() );
}

char _keygo()		//停顿，按任意键继续
{	char c;
	printf("按任意键继续......\n");
	c=getch();
  return c;
}


//----------实验参数设置------------
struct memblock  {	//定义内存块结构
	int head;				//起址
	int length;			//长度
	char name[10];	//如果已分配，设置对应的作业名
	struct memblock * link; //指向下一个
} * p; //p为临时指针
typedef struct memblock MEM; 

const totalmem = 320;		//内存总量，单位为K
const usr_head = 5;		//用户区起址，我们假设作业只能载入用户区，从usr_head开始往后分配
const max = 100;

MEM *allocate = NULL; //记录每个作业分配内存的起址\长度\内容
MEM *jobs = NULL;	//作业队列
MEM *empty = NULL;	//空闲表,用name数组没用

//int empty[max][3];	//空闲表, 一部分记录空闲区，一部分为空表目
//第二维三个数据项分别：起址，长度，状态（0为空表目，1为空闲区未分配）
//int lastempty = 0;			//empty表已使用表目数
//lastempty是空闲区域空表目的分界，用于空闲表输出时，只显示空闲区，不显示空表目。
//注意在内存回收时，会在表中将空闲区设置成空表目，导致空闲区与空表目混杂。
//const jobnum = 3;
//int jobs[jobnum] = {130, 60, 100};	//作业队列, 记录每个作业的大小
//int jobs[100];	//作业队列, 记录每个作业的大小
//int jobnum = 0;	//作业总数

//----------自定义函数-------------------

//void empty_clear(int n)	//将空闲表中一个空闲区设成空表目，用于内存回收
//{	empty[n][1] = NIL;
//	empty[n][2] = NIL;
//	empty[n][3] = 1;	
//}
//void alloc_addnew(int n, int newhead, int newlength, char newname[10])
//{	alloc[n].head = newhead;
//	alloc[n].length = newlength;
//	strcpy(alloc[n].name, newname);
//}
//--------已分配队列操作-----------
void alloc_disp()	//显示当前内存状态
{	p = allocate;
	printf("****当前内存分配状态:\n"); 
	while(p!=NULL) 
	{ printf("[%dK]--[%dK]: %s.\n",p->head, (p->head) + (p->length), p->name); 
		p=p->link; 
	} 
}

void alloc_copy(MEM *p1, MEM *p2)	//复制,注意link不能复制，可能会出错
{	p1->head = p2->head;
	p1->length = p2->length;
	strcpy(p1->name, p2->name);
}

void alloc_insert(MEM *pjob)
{ MEM * pr;
	p=getpch(MEM);	
	alloc_copy(p, pjob);
	pr = allocate;
	while ((pr->link) != NULL)	//将指针移动到最后
		pr = pr->link;
	pr->link = p;
	p->link = NULL;
	//可以考虑重新排序,使输出好看 ........
}


void alloc_remove(MEM *pjob)
{	MEM * pr, * prev;
	if (allocate == pjob)
	{	allocate = allocate->link;
		free(pjob);
		return;
	}
	prev = allocate;	//获取前一个指针
	pr = allocate->link;
	while (pr!=NULL) 
	{	if (pr == pjob) break;
		else
		{	prev = pr;
			pr=pr->link;
		}
	}
	if (pr ==NULL) 
	{	printf("!!!%s不在内存中，卸载作业出错!!!\n", pjob->name);
		return;
	}
	prev->link = pr->link; //把pjob删除，他的前后指针要连接起来
	free(pjob);
}
//--------空闲区队列操作-----------
void empty_disp()	//显示当前内存状态
{	p = empty;
	printf("****当前空闲区:\n"); 
	while(p!=NULL) 
	{ printf("[%dK]--[%dK]--|%dK|-%s.\n",p->head,p->head+p->length, p->length, "未分配"); 
		p=p->link; 
	} 
}

void empty_insert(MEM *pe)
{
}

void empty_remove(MEM *pe)
{	MEM * pr, * prev;
	if (empty == pe)
	{	empty = empty->link;
		free(pe);
		return;
	}
	prev = empty;	//获取前一个指针
	pr = empty->link;
	while (pr!=NULL) 
	{	if (pr == pe) break;
		else
		{	prev = pr;
			pr=pr->link;
		}
	}
	if (pr ==NULL) 
	{	printf("!!!没有这个空闲块，修改空闲表失败!!!\n");
		return;
	}
	prev->link = pr->link; //把当前空闲块删除，他的前后指针要连接起来
	free(pe);
}



//void destroy(MEM *pr)//释放一个数据块MEM
//{	free(pr); }

void init()	//初始化
{// int i;
	MEM * prev;
//	for (i=0; i<max; i++)
//		empty_clear(i);
	//初始化内存已分配状态
	p=getpch(MEM);	//创建已分配内存块
	p->head = 0;
	p->length = usr_head;
	strcpy(p->name, "SYSTEM");	
	p->link = NULL;
	allocate = p;	//第一个块是系统区
	prev = p;
	//用户区初始化
	p=getpch(MEM);	//创建已分配内存块
	p->head = usr_head;
	p->length = 5;
	strcpy(p->name, "JOB[1991]");	//作业1991
	p->link = NULL;
	prev->link = p;
	prev =p;
	p=getpch(MEM);	//创建已分配内存块
	p->head = 77;
	p->length = 23;
	strcpy(p->name, "BUFFER");	//缓冲区
	p->link = NULL;
	prev->link = p;
	prev =p;
	p=getpch(MEM);	//创建已分配内存块
	p->head = 123;
	p->length = 46;
	strcpy(p->name, "MIRROR");		//镜像区
	p->link = NULL;
	prev->link = p;
	alloc_disp();
	//根据上面的数据，初始化空闲表
	p=getpch(MEM);	//创建空闲区
	p->head = 10;
	p->length = 67;
	strcpy(p->name, "FFF");	
	p->link = NULL;
	empty = p;	//第一个空闲块
	prev = p;
	p=getpch(MEM);	//创建空闲区
	p->head = 100;
	p->length = 23;
	strcpy(p->name, "FFF");	
	p->link = NULL;
	prev->link = p;
	prev =p;
	p=getpch(MEM);	//最后一个空闲区
	p->head = 169;
	p->length = totalmem - p->head;
	strcpy(p->name, "FFF");	
	p->link = NULL;
	prev->link = p;
	prev =p;
	empty_disp();
}


int input() // 输入作业参数
{ int i, tmp, jobnum;
	char str[2];
	MEM * pr;
	printf("\n 作业总数为:"); 
	scanf("%d",&jobnum); 
	pr = jobs;
	for(i=0;i<jobnum;i++) 
	{ printf("\n 输入第[%d]号作业的大小:", i); 
		scanf("%d",&tmp); 
		p=getpch(MEM);	
		p->head = NIL;	//作业起址等于999999表示该作业没有分配内存
		p->length = tmp;
		strcpy(p->name, "作业");
		itoa(i, str, 10);
		strcat(p->name, str);
		p->link = NULL;
		if (i == 0)	jobs =p;
		else 	pr->link = p;
		pr = p;
	} 
	printf("作业队列为:\n"); 
	p = jobs;
	while(p!=NULL) 
	{ printf("[%dK]--|%dK|: %s.\n",p->head, p->length, p->name); 
		p=p->link; 
	} 
	return jobnum;
} 
void mem_alloc(MEM *pjob)
{	MEM * pr;
	//首次适应算法
	pr = empty;
	while (pr != NULL)
	{	if (pr->length > pjob->length)	
		{	pjob->head = pr->head;	//直接把作业数据块插入已分配队列
			alloc_insert(pjob);
			//产生碎片,需要修改被分配空闲区的参数
			pr->head = pr->head + pjob->length;
			pr->length = pr->length - pjob->length;
			printf("!!!!!%s分配成功!!!!!\n", pjob->name);
			break;
		}
		if (pr->length == pjob->length)		//刚好满足
		{	pjob->head = pr->head;	//直接把作业数据块插入已分配队列
			alloc_insert(pjob);
			empty_remove(pr);	//从空闲队列中删除该空闲区
			printf("!!!!!%s分配成功!!!!!\n", pjob->name);
			break;
		}

		if (pr->length < pjob->length)
			pr = pr->link;
	}
	if (pr == NULL) 
		printf("!!!!!当前空闲区不能满足%s的大小%dK!\n", pjob->name, pjob->length);

}

//----------主程序-------------------
int main(int argc, char* argv[])
{	int jobnum;
	MEM * pr;
	init();
	jobnum = input();
	//为作业分配内存
	printf("\n-------------作业分配开始-----------!\n");
	pr =jobs;
	while (pr!=NULL)
	{	mem_alloc(pr);
		alloc_disp();
		empty_disp();
		_keygo();
		pr= pr->link;
	}
	printf("-------------作业分配结束-----------!\n");
	

	_keygo();
	return 0;
}