资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

首次适应算法动态分区分配方式的模拟C语言——课程设计实习-创新互联

设计目的

所谓动态分区分配,就是指内存在初始时不会划分区域,而是会在进程装入时,根据所要装入的进程大小动态地对内存空间进行划分,以提高内存空间利用率,降低碎片的大小 动态分区分配算法有以下四种:

网站设计、成都网站制作的开发,更需要了解用户,从用户角度来建设网站,获得较好的用户体验。成都创新互联公司多年互联网经验,见的多,沟通容易、能帮助客户提出的运营建议。作为成都一家网络公司,打造的就是网站建设产品直销的概念。选择成都创新互联公司,不只是建站,我们把建站作为产品,不断的更新、完善,让每位来访用户感受到浩方产品的价值服务。
  • 首次适应算法(First Fit)
    空闲分区以地址递增的次序链接。分配内存时顺序查找,找到大小满足要求的第一个空闲分区就进行分配
  • 邻近适应算法(Next Fit)
    又称循环首次适应法,由首次适应法演变而成,不同之处是分配内存时从上一次查找结束的位置开始继续查找
  • 最佳适应算法(Best Fit)
    空闲分区按容量递增形成分区链,找到第一个能满足要求的空闲分区就进行分配
  • 最坏适应算法(Next Fit)
    又称大适应算法(Largest Fit),空闲分区以容量递减的次序链接,找到第一个能满足要求的空闲分区(也就是大的分区)就进行分配
设计内容及要求
  • 用C语言实现采用首次适应算法的动态分区分配过程alloc()和回收过程free()。其中,空闲分区通过空闲分区链表来管理,在进行内存分配时,系统优先使用空闲区低端的空间
  • 假设初始状态如下,可用的内存空间为640KB,并有下列的请求序列;采用首次适应算法进行内存块的分配和回收,同时显示内存块分配和回收后空闲内存分区链的情况
  • 假设初始状态如下,可用的内存空间为640KB,并有下列的请求序列;
    作业1申请130KB
    作业2申请60KB
    作业3申请100KB
    作业2释放60KB
    作业4申请200 KB
    作业3释放100 KB
    作业1释放130 KB
    作业5申请140 KB
    作业6申请60 KB
    作业7申请50KB
    作业6释放60 KB
    请采用循环首次适应算法进行内存块的分配和回收,同时显示内存块分配和回收后空闲内存分区链的情况。
设计准备 首次适应算法:
  • 算法思想:
    将空闲分区链以地址递增的顺序连接;在进行内存分配时,从链首开始顺序查找,直到找到一块分区的大小可以满足需求时,按照该作业的大小,从该分区中分配出内存,将剩下的空闲分区仍然链在空闲分区链中
  • 优点:高址部分的大的空闲分区得到保留,为大作业的内存分配创造了条件
  • 缺点:(1)每次都是优先利用低址部分的空闲分区,造成低址部分产生大量的外碎片。(2)每次都是从低址部分查找,使得查找空闲分区的开销增大
内存回收:

将释放作业所在内存块的状态改为空闲状态,删除其作业名,设置为空。并判断该空闲块是否与其他空闲块相连,若释放的内存空间与空闲块相连时,则合并为同一个空闲块,同时修改分区大小及起始地址

设计过程

我们以空闲分区链为例来说明采用FF算法时的分配情况,FF算法要求空闲分区链以地址递增的次序链接

  • 在分配内存时,从链首开始顺序查找,直至找到一个大小能满足要求的空闲分区为止
  • 然后再按照作业的大小,从该分区中划出一块内存空间分配给请求者,余下的空闲分区仍留在空闲链中
  • 若从链首直至链尾都不能找到一个能满足要求的分区,则此次内存分配失败,返回

了解动态分区分配中使用的数据结构和分配算法,并进一步加深对动态分区存储管理方式及其实现过程的理解。采用首次适应算法的动态分区分配过程alloc()和回收过程free()。空闲分区通过空闲分区链表来管理,在进行内存分配时,系统优先使用空闲区低端的空间,即每次分配内存空间是总是从低址部分开始进行循环,找到第一个合适的空间,便按作业所需分配的大小分配给作业。 作业完成时,需要释放作业所占空间,此时要考虑到四种情况:

  • 回收区与插入点的前一个空闲分区相邻接。此时将二者合并,修改前一分区的大小。
  • 回收区与插入点的后一空闲分区相邻接,将二者合并,用回收区的首址作为新空闲区的首址。
  • 回收区同时与插入点的前后两个空闲分区相邻接,三者合并,使用前一空闲分区的表项和首址。
  • 回收区单独存在。
设计结果并分析

菜单
菜单
作业1申请130KB
1
作业2申请60KB
2
作业3申请100KB
3
作业2释放60KB
4
作业4申请200KB
5
作业3释放100KB
6
作业1释放100KB
7
作业5申请140KB
8
作业6申请60KB
9
作业7申请50KB
10
作业6释放60KB
11

原理框图

在这里插入图片描述

模块设计
  • void initNode(struct nodespace *p)
    创建一个双链表存储信息

  • void myMalloc1(int teskid,int size,struct nodespace *node)
    申请空间函数

  • void myFree(int teskid,struct nodespace *node)
    释放空间函数

  • void printNode(struct nodespace *node)
    打印输出节点存储信息了,即内存申请剩余情况

  • void destory(struct nodespace *node)
    退出程序并销毁清空节点

  • void menu()
    主菜单,提示用户进行相应的操作

C语言源程序——建议使用Devc ++ 运行
#include#includestruct nodespace{int teskid;   // 作业号 
	int begin;    // 开始地址 
	int size;     // 大小 
	int status;   // 状态 0代表占用,1代表空闲 
	struct nodespace *next;  // 后指针 
};
void initNode(struct nodespace *p){if(p == NULL){//如果为空则新创建一个 
		p = (struct nodespace*)malloc(sizeof(struct nodespace));
	}
	p->teskid = -1;
	p->begin = 0;
	p->size = 640;
	p->status = 1;
	p->next =NULL; 
}  
void myMalloc1(int teskid,int size,struct nodespace *node){while(node != NULL){if(node->status == 1){//空闲的空间 
			if(node->size >size){//当需求小于剩余空间充足的情况 
				//分配后剩余的空间 
				struct nodespace *p = (struct nodespace*)malloc(sizeof(struct nodespace));
				p->begin = node->begin + size;
				p->size = node->size - size;
				p->status = 1;
				p->teskid = -1;
				//分配的空间 
				node->teskid = teskid; 
				node->size = size;
				node->status = 0;
				//改变节点的连接 
				p->next = node->next; 
				node->next = p;
				printf("==================================分配内存成功!==================================\n");
				break; 
			}else if(node->size == size){//需求空间和空闲空间大小相等时 
				node->teskid = teskid; 
				node->size = size;
				node->status = 0;
				printf("==================================分配内存成功!==================================\n");
				break;
			}	
		}
		if(node->next == NULL){	printf("===============================分配失败,没有足够的空间!=============================\n");
			break;
		}
		node = node->next;
	}
} 
void myFree(int teskid,struct nodespace *node){if(node->next == NULL && node->teskid == -1){printf("================================您还没有分配任何作业!================================\n");
	}
	
	while(node != NULL){if(node->status == 1 && node->next->status ==0 && node->next->teskid == teskid){	
			struct nodespace *q = node->next;
			node->next = node->next->next;
			free(q);
			printf("==================================释放内存成功!==================================\n");
			if(node->next->status == 1){//下一个空间是空闲空间时 
				node->size = node->size + node->next->size;
				struct nodespace *q = node->next;
				node->next = node->next->next;
				free(q);
				printf("==================================释放内存成功!==================================\n");
			}
			break;
		}else if(node->status == 0 && node->teskid == teskid){//释放空间和空闲空间不连续时  
			node->status = 1;
			node->teskid = -1;
			if(node->next != NULL && node->next->status == 1){//下一个空间是空闲空间时 
				node->size = node->size + node->next->size;
				struct nodespace *q = node->next;
				node->next = node->next->next;
				free(q);
			}
			printf("==================================释放内存成功!==================================\n");
			break;
		}else if(node->next == NULL){//作业号不匹配时 
			printf("==================================没有此作业!!==================================\n");
			break;
		}
		node = node->next;
	}
	
	 
} 
void printNode(struct nodespace *node){printf("                        内存情况                        \n"); 
	printf(" -------------------------------------------------------\n");
	printf("| 起始地址\t结束地址\t大小\t状态\t作业号\t|\n");
	while(node != NULL){if(node->status==1){	printf("| %d\t\t%d\t\t%dKB\tfree\t 无\t|\n", node->begin + 1, node->begin+node->size, node->size);
		}else{	printf("| %d\t\t%d\t\t%dKB\tbusy\t %d\t|\n", node->begin + 1, node->begin+node->size, node->size, node->teskid);
		}
		node = node->next;
	}
	printf(" -------------------------------------------------------\n");
}
void destory(struct nodespace *node){struct nodespace *q = node;
	while(node != NULL){node = node->next;
		free(q);
		q = node;
	}
} 
void menu(){printf("\n"); 
	printf("\t\t\t\t   ╭═════════════════════════════════○●○●═══╮\n");
		printf("\t\t\t\t   │    首次适应算法的动态分区分配方式模拟      │\n");
		printf("\t\t\t\t   ╰═══○●○●═════════════════════════════════╯\n");
		printf("\t\t\t\t   ┌───────────────────────────────────────────-┐\n");
		printf("\t\t\t\t   │                                            │\n");
		printf("\t\t\t\t   │                 1. 申请内存                │\n");
		printf("\t\t\t\t   │                                            │\n");
		printf("\t\t\t\t   │                 2. 回收内存                │\n");
		printf("\t\t\t\t   │                                            │\n");
		printf("\t\t\t\t   │                 3. 查看内存情况            │\n");
		printf("\t\t\t\t   │                                            │\n");
		printf("\t\t\t\t   │                 4. 退出                    │\n");
		printf("\t\t\t\t   │                                            │\n");
		printf("\t\t\t\t   └────────────────────────────────────────────┘\n");
		printf("\t\t\t\t\t\t  请您选择(1-4):\t");
}
 
int main(){// node为整个空间 
	system("color 0f");
	//system("mode con cols=120 lines=50");
	struct nodespace *init = (struct nodespace*)malloc(sizeof(struct nodespace));
	struct nodespace *node = NULL;
	initNode(init);			//初始化主链 
	node = init; 			//指向链表头 
	int option; 
	int teskid;
	int size;
	while(1){menu();		//打印想要进行的操作
		scanf("%d",&option);
		if(option == 1){	printf("请输入作业号;");
			scanf("%d",&teskid);
			printf("此作业申请的空间大小(KB):");
			scanf("%d",&size);
			myMalloc1(teskid,size,node);
			printf("\n"); 
			printNode(node);
		}else if(option == 2){	printf("请输入作业号:");
			scanf("%d",&teskid);
			myFree(teskid,node);
			printf("\n"); 
			printNode(node);
		}else if(option == 3){	printNode(node);
		}else if(option == 4){	destory(node);
			initNode(init);
			node = init;
			break;
		}else{	printf("===========================您的输入有误,请重新输入!============================\n");
			continue;
		}
	}
return 0;
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


本文名称:首次适应算法动态分区分配方式的模拟C语言——课程设计实习-创新互联
本文地址:http://cdkjz.cn/article/ieigj.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220