Home > 算法研究 > 操作系统 模拟可变分区内存管理实验 C语言描述

操作系统 模拟可变分区内存管理实验 C语言描述

December 10th, 2008 Leave a comment Go to comments

操作系统 模拟可变分区内存管理实验 C语言描述
《知识共享协议》下修改、传播、发行，
如需网络转载请保留作者注释
调试环境 GCC , Borland Turbo C , MS VC++

/*<!--HTML */
/*
*author CG
*www.lidaren.com
*环境 GCC ，Turbo C
*/
#include"stdio.h"
#include"stdlib.h"
#include"conio.h"
#define NULL 0
#define MAXSIZE 2000
#define MINSIZE 10
#define OFFSET 0
#define FALSE 0
#define TRUE 1
typedef int address;/*定义地址类型*/
typedef struct node{
    int size, used; /*定义分区大小和已经使用大小*/
    address add;/*定义起始地址*/
    int able;
    int id;/*分区ID*/
    char *info;/*其他信息*/
    struct node *pre, *next;
    }node,*list;
/**********以下定义全局变量********/
static int method=0;/*管理方法*/
static int jobId=0;/*作业ID*/
static list L=NULL;/*内存管理链表*/
static node * cnext=NULL;/*指向下以节点指针*/
/***********************************/
/*功能：分配分区，完成分区的分配功能
参数：node *n 被分配的空闲分区指针
int size请求的空间大小 int id 作业的ID
返回： ADD 分配后的节点的起始地址*/
node * distribute(node *n , int size , int id){
	node *p;
	if(n->size - size <= MINSIZE){
/*找到的节点符合需要且分配后剩余空间小于
MINSIZE，直接分配分区*/
		n->able = FALSE;
		n->used = size;
		n->size = size;
		n->id = id;
		return n;
	}/*if*/
	else{
/*找到的节点符合需要且分配后剩余空间大于
MINSIZE，将空闲分区切割，再分配分区*/
		p = (node *)malloc(sizeof(node));/*分配新空间节点*/
/*剩余空间重新组成的空间*/
		p->size = n->size-size;/*新节点初始化*/
		p->used = 0;
		p->add = n->add+size;/*新节点的起始地址*/
		p->able = TRUE;
		p->next = n->next;/*修改指针，完成节点插入*/
		n->next->pre = p;
		p->pre = n;
		n->next = p;
/*修改被分配分区节点的数据*/
		n->used = size;
		n->size = size;
		n->id = id;
		n->able = FALSE;
		return n;
	}/*else*/
}/*distribute*/
/*recycle 节点资源回收函数
*参数： node*n 传递要回收的节点指针
*返回：bool 返回操作是否成功*/
int recycle(node *n){
	node *r;/*备份指针*/
	if(n->pre->able == TRUE &#038;& n->add != 0)
	{
/*向上合并空闲区间，要求n节点的首地址不为0,为0直接
释放地址空间，n->add!=0可以防止地址假溢出*/
		r = n->pre;/*修改指针，删除节点*/
		r->pre->next = n;
		n->pre = r->pre;
		n->size += r->size;/*修改节点数据*/
		n->add = r->add;
		free(r);/*释放r*/
		recycle(n);/*递归调用回收函数*/
		return TRUE;
	}/*if*/
	else if(n->next->able == TRUE &#038;& n->next->add != 0)
	{
/*向下合并空闲区间，要求n节点的下一节点的首地址不为0,
为0会产生跨高低地址的分区n->next->add!=0可以防止地址假溢出*/
		r = n->next;/*修改指针*/
		n->next = r->next;
		r->next->pre = n;
		n->size += r->size;/*修改节点数据*/
		free(r);/*释放r*/
		recycle(n);/*递归调用回收函数*/
		return TRUE;
	}/*if*/
	else{
/*独立节点直接分配空间，以下也用于清理数据结构数据*/
		n->used = 0;
		n->able = TRUE;
		return TRUE;
	}/*else*/
}/*recycle*/
/*firstadapt 首次适应算法函数
*参数 list L 链表头节点
	int size 节点大小用于判断是否符合空间要求
* 返回 node * 成功查找获得的节点指针，失败返回NULL*/
node * firstAdapt(list L , int size){
	node * n;
	n = L;
	do{
	if(n->able == TRUE &#038;& n->size-MINSIZE >= size)
		return n;/*如果符合要求，返回n*/
	else n = n->next;/*n指针下移*/
	}while(n != L);/*n到达起始节点*/
	return NULL;
}/*firstadapt*/
/*cyclefirstadapt 循环首次适应算法函数
*参数 list start 链表开始查找节点
	int size 节点大小用于判断是否符合空间要求
* 返回 node * 成功查找获得的节点指针，失败返回NULL*/
node * cycleFirstAdapt(node * start , int size){
	node * n;
	n = start;
	do{
	if(n->able == TRUE &#038;& n->size - MINSIZE >= size)
		return n;
	else n = n->next;
	}while(n != start);
	return NULL;
}/*cyclefirstadapt*/
/*bestadapt 最佳适应算法函数，贪心算法
*参数 list L 链表头节点
	int size 节点大小用于判断是否符合空间要求
* 返回 node * 成功查找获得的节点指针，失败返回NULL*/
node * bestAdapt(list L , int size){
	node * n;/*遍历指针*/
	node * temp;/*临时指针，用于存放符合条件的节点*/
	int t ,flag;/*临时变量t存放结果差值，flag 成功标志位*/
	flag = FALSE;/*初始化标志*/
	n = L;
	temp = n;
	do{
	if(n->size - MINSIZE >= size){/*如果大小符合*/
		t = n->size - size;
		temp = n;
		flag = TRUE;/*查找标志置1*/
		break;
		}
	n = n->next;
	}while(n != L);
	do{
	if(n->size - MINSIZE >= size){/*取得第二个t*/
		if(t > n->size - size)
		{/*如果差值小于t, 替换t和temp*/
			t = n->size - size;
			temp = n;
			flag = TRUE;/*查找标志置1*/
		}/*if*/}/*if*/
	n = n->next;
	}while(n != L);
	if(flag)/*检查标志位*/
		return temp;
	else
		return NULL;
}/*bestadapt*/
/*worstadapt 首次适应算法函数
*参数 list L 链表头节点
	int size 节点大小用于判断是否符合空间要求
* 返回 node * 成功查找获得的节点指针，失败返回NULL*/
node * worstAdapt(list L , int size){
	node * n;/*变量指针*/
	node * temp;/*临时存放指针，用于存放查找结果*/
	n = L;/*n指向头节点*/
	temp = n;/*temp 初始值 n*/
	do{
	if(temp->size < n->next->size)
		temp=n->next;/*循环求最大的空间*/
	n = n->next;
	}while(n != L);
	if(temp->size - MINSIZE >= size)/*检查最大值是否符合分配前提*/
		return temp;
	else
		return NULL;
}/*worstadapt*/
/*searchbyid ID搜索函数
*参数：list L 链表头指针 int ID 要查找的ID
*返回：node * 节点指针，查找失败返回NULL*/
node * searchById(list L , int id){
	node * n;/*定义遍历指针*/
	n = L;
	do{
		if(n->id == id) return n;/*符合要求返回ID*/
		n = n->next;/*指针后移*/
	}while(n != L);
	return NULL;/*查找失败返回NULL*/
}/*search by id*/
/*schedule 算法调度函数，根据要求选择不同算法
参数 list L 链表头节点 int size 要分配的大小
返回 node * 返回的节点指针,失败返回NULL*/
node * schedule(list L , int size){
	node * n;
	switch(method){
	case 1 : n=firstAdapt(L,size); break;
	case 2 : n=cycleFirstAdapt(cnext,size);cnext=n->next; break;
	case 3 : n=bestAdapt(L , size); break;
	case 4 : n=worstAdapt(L , size); break;
	case 0 : leave();break;
	default : printf("ERROR: Unknown methodn");return NULL;
	}/*switch*/
	if(n)/*检查是否返回成功*/
		return n;
	else
		return NULL;
}/*schedule*/
/*newpart 新建分区函数
*返回 bool 分配空间是否成功
输入 int size 要分配的空间的大小*/
int newPart(){
	int size;/*定义空间大小*/
	node * n;
	printf("input SIZE the part needed:");
	scanf("%d",&#038;size);/*输入空间大小*/
	if(size <= MINSIZE){/*size太小*/
		printf("ERROR:Size too small!n");
		return FALSE;
	}/*if*/
	else if(size > MAXSIZE){/*size>最大可分配空间*/
		printf("ERROR:Size too large!n");
		return FALSE;
		}/*else*/
	if(method == 2)/*method=2，判断method是否为2？*/
		n = schedule( (list)cnext , size);/*查找空间 method=2*/
	else
		n = schedule(L , size);/*查找空间*/
	if(n == NULL){/*n返回为空？*/
		printf("ERROR:Can not distribute space!n");
		return FALSE;
		}/*if*/
	n = distribute(n , size , ++jobId);/*分配空间*/
	if(n){/*n返回成功*/
		printf("Distribute a part OKntWID:%d size:%d address:0x%Xn",
			n->id , n->used , n->add );
		return TRUE;
	}/*if*/
	else printf("ERRORn");
}/*newpart*/
/*freepart 释放空间函数
返回 bool 释放是否成功
输入 int id 输入要释放的wID*/
int freePart(){
	int id;
	node * n;
	printf("Input part WID you need to free:");
	scanf("%d",&#038;id);/*输入wid*/
	n = searchById(L , id);/*在L中查找ID*/
	if(n){/*查找成功*/
		if(recycle(n)){/*回收成功*/
			printf("Recycle a space successed WID:%dn",n->id);
			return TRUE;
			}
		else/*回收失败*/
			return FALSE;
	}/*if*/
	else{/*查找失败*/
	printf("ERROR:ID:%d Not found!n",id);
	return FALSE;
	}/*else*/
}/*freepart*/
/*output 结果输出函数
输出 列表形式输出L中的每一个节点的数据*/
int output(){
	node * n;/*定义遍历指针*/
	int count = 0;/*定义计数器，初始化为0*/
	n = L;
	printf("n|__BID___|__SIZE__|__ADD___|__USED__|__WID___|n");
	do{
		printf("|%8d|%8d|0x%-6X" , ++count , n->size , n->add);
		if(n -> able == TRUE)/*可用空间*/
			printf("|  FREE  |  FREE  |n");
		else/*已用空间*/
			printf("|%8d|%8d|n" , n->used , n->id);
	n = n->next;/*指针下移*/
	}while(n != L);
	return TRUE;/*输出完毕*/
}/*output*/
/*mainmenu 主菜单输出函数
输出 列表显示猪菜单
返回 bool 返回菜单是否打印成功*/
int mainmenu(){
printf("Method:method to manage partitionn");
printf(" -FtFirst Adpat (FA)n");
printf(" -CtCycle First Adapt (CFA)n");
printf(" -BtBest Adapt (BA)n");
printf(" -WtWorst Adapt (WA)n");
printf(" -XtExitn");
printf("ttype 'H' show help menun");
return TRUE;
}/*mainmenu*/
/*submenu 子菜单输出函数
输出 列表显示猪菜单
返回 bool 返回菜单是否打印成功*/
int submenu(){
printf("Command:command to operate listn");
printf(" -DtDistribute a new spacen");
printf(" -FtFree a exsit pacen");
printf(" -OtOutput all space listn");
printf(" -CtClear space listn");
printf(" -RtReturn to main menun");
printf(" -XtExitn");
printf("ttype 'H' show help menun");
return TRUE;
}/*submenu*/
/*init 初始化函数，用于初始化list L
返回 bool 初始化是否成功？*/
int init(){
	L = (node *)malloc(sizeof(node));/*分配节点*/
	L->next = L;/*初始化指针next=L，pre=L*/
	L->pre = L;
	L->add = 0;/*初始化数据结构*/
	L->able = TRUE;
	L->size = MAXSIZE;
	L->used = 0;
	L->id = 0;
	L->info = NULL;
	cnext = L;/*初始化全局变量cnext*/
	return TRUE;
}/*init*/
/*clear 链表清空函数
返回 bool 链表清除是否成功？*/
int clear(){
	node * n , * t;
	n = L;
	do{/*遍历链表*/
		t = n;
		n = n->next;/*指针下移*/
		free(t);
	}while(n != L);/*while*/
	L->next = L;/*初始化L指针*/
	L->pre = L;
	L->add = 0;/*初始化L数据结构*/
	L->able = TRUE;
	L->size = MAXSIZE;
	L->used = 0;
	L->info = NULL;
	printf("Clear list successed!n");
	return TRUE;
}/*init*/
/*leave 退出函数，用于退出时清理内存空间
返回 boo 清理是否成功？*/
int leave(){
	node *n,*t;/*定义遍历指针和临时指针 */
	n = L;
	do{/*遍历链表*/
		t = n;
		n = n->next;/*指针下移*/
		free(t);/*释放t*/
	}while(n != L);/*while*/
	free(L);/*释放头节点*/
	exit(0);
}/*leave*/
/*process 调度进程函数，用于整个进程的调度
返回 bool 程序是否正确执行？
输入 char 用于程序操作的命令*/
int process(){
char SELECT = NULL;/*定义输入字符*/
submenu();/*打印菜单*/
while(1){
	putchar('-');
	SELECT = getch();/*输入SELECT*/
switch(SELECT){
	case 'd':
	case 'D': newPart(); break;/*新建分区*/
	case 'f':
	case 'F': freePart(); break;/*释放分区*/
	case 'o':
	case 'O': output(); break;/*输出链表*/
	case 'c':
	case 'C': clear(); break;/*清空链表*/
	case 'x':
	case 'X': leave(); break;/*离开*/
	case 'h':
	case 'H': submenu(); break;/*帮助*/
	case 'r':
	case 'R': return TRUE;/*返回*/
	default : printf("ERRORn"); continue;/*输入错误*/
	}/*switch*/
}/*while*/
return FALSE;
}/*process*/
/*main 主函数*/
int main(){
char SELECT = NULL;/*定义输入区间*/
init();/*初始化*/
start: clrscr();/*清屏*/
	printf("Memeory Manage Use Flexable partitionn");
	printf("by CG t [email protected]");
	mainmenu();/*打印主菜单*/
while(1){
	putchar('-');
	SELECT = getch();/*输入SELECT*/
	switch(SELECT){
	case 'f':
	case 'F': method = 1; break;/*FA*/
	case 'c':
	case 'C': method = 2; break;/*CFA*/
	case 'b':
	case 'B': method = 3; break;/*BA*/
	case 'w':
	case 'W': method = 4; break;/*WA*/
	case 'x':
	case 'X': leave(); break;/*退出*/
	case 'h':
	case 'H': mainmenu(); continue;/*帮助*/
	default : printf("ERRORn"); continue;/*输入错误*/
	}/*switch*/
	if(process()==1)/*执行进程调度成功？*/
		goto start;
	else/*调度错误或失败*/
		leave();
}/*while*/
}/*main*/
/*-->*/
Categories: 算法研究 Tags: ,
  1. 小杨
    June 16th, 2019 at 15:54 | #1
    Reply | Quote

    头文件没有老哥

  1. No trackbacks yet.
You must be logged in to post a comment.