十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
编写C语言程序,模拟实现首次/最佳/最坏适应算法(选择其中之一即可)的内存块分配和回收,要求每次分配和回收后显示出空闲分区和已分配分区的情况。假设初始状态下,可用的内存空间为640KB。
假设下列作业请求序列:
(1)作业1 申请130 KB (2)作业2 申请60 KB (3)作业3 申请100 KB
(4)作业2 释放60 KB (5)作业3 释放100 KB (6)作业1 释放130 KB
显示每次作业申请或释放后当前内存情况。
根据题目,分析设计如下:
(1)程序初始需要提供用户选择方式。选择首次适应算法,还是最佳是适应算法,选择作业的回收,作业的展示,程序的退出能。
(2)当用户选择首次适应算法或者最佳适应算法,需要用户输入分配内存的大小。在输入大小时在根据算法的设计进行分配。
(3)当内存分配过后,如果分配成功就需要提示成功,如果失败则需要提示失败。
(4)内存回收需要用户输入回收作业的ID,根据作业的ID对内存进行回收。在回收时要分多种情况进行判断。
(5)作业展示,需要向用户展示,作业的ID,起始地址,内存大小,状态是已分配还是空闲。
(6)一个作业需要用到数据结构中的双向列表,用一个双向列表来表示节点。
#include#includestruct area
{int id; // 编号
int addr_front; //首地址
int addr_end; //结束地址
int size; //分区大小
int flag; //分配标志,0表示空闲,1表示占用
struct area *front; //上一分区
struct area *next; //下一分区
};
typedef struct area partion;
partion *head = NULL; //分区队列头节点
int need; //需求
int choice = 1; //操作选项
partion *createPartion(int id, int addr_front, int size, int flag); //生成一个节点
void inputNeed(); //输入需求量
void assign(partion *ptr, int need); //分配分区
void first_fit(); //首次适应算法
void best_fit(); //最佳适应算法
void showMemoryInfo(); //打印分区分配状况
void recovery(); //分区回收
void changeIdValue(partion *ptr, int delta); //改变从ptr开始所有节点的id值
int main(void)
{head = createPartion(0, 0, 640, 0);
while (choice != 0)
{puts("-------------------\n请选择操作:\n1:首次适应;\n2:最佳适应;\n3:内存回收;\n4:展示详细信息;\n0:推出......\n-------------------");
scanf("%d", &choice);
switch (choice)
{case 1:
inputNeed();
first_fit();
break;
case 2:
inputNeed();
best_fit();
break;
case 3:
recovery();
showMemoryInfo();
break;
case 4:
showMemoryInfo();
break;
case 0:
puts("byebye");
break;
default:
break;
}
}
return 0;
}
//创建一个节点
partion *createPartion(int id, int addr_front, int size, int flag)
{partion *p = (partion *)malloc(sizeof(partion));
p->id = id;
p->addr_front = addr_front;
p->addr_end=addr_front+size-1;
p->size = size;
p->flag = flag;
p->front = NULL;
p->next = NULL;
return p;
}
void inputNeed()
{printf("请输入需要的内存大小:");
scanf("%d", &need);
}
void first_fit()
{partion *fit = NULL;
partion *ptr = head;
while (ptr != NULL)
{if (ptr->size >= need && ptr->flag == 0)//如果是空闲并且大小大于则给予分配
{ fit = ptr;
break;
}
ptr = ptr->next;
}
if (fit != NULL)
{assign(fit, need);
printf("内存分配成功,分配如下:\n");
showMemoryInfo();
}
else
{puts("抱歉,内存分配失败!");
free(fit);
}
}
void best_fit()
{partion *fit = NULL;
partion *ptr = head;
int flag = 0; //flag 表示是否找到可分配的分区
while (ptr != NULL)
{if (ptr->flag == 0 && ptr->size >= need)
{ if (flag == 0)
{//只有遇到的第一个可分配分区会执行此操作
fit = ptr;
flag = 1;
}
else
{//若遇到可分配且分区更小即更适合的则更新
if (ptr->size< fit->size)
{ fit = ptr;
}
}
}
ptr = ptr->next;
}
//先处理没找到合适分区的情况
if (flag == 0)
{puts("抱歉,未找到合适的分区!");
free(fit);
return;
}
//找到则分配
assign(fit, need);
puts("内存分配成功,分配如下:\n!");
showMemoryInfo();
}
void showMemoryInfo()
{partion *ptr = head;
puts("\n\n---------------------------------------------");
puts("总内存分配情况如下:");
puts("---------------------------------------------");
puts("序号ID****开始地址****结束地址****内存大小****状态****");
while (ptr != NULL)
{printf("%-12d%-12d%-12d%-12d",ptr->id,ptr->addr_front,ptr->addr_end,ptr->size);
// printf("序号id:%21d%10c\n开始地址:%10d%10c\n", ptr->id, '|', ptr->addr_front, '|');
//printf("结束地址:%10d%10c\n", ptr->addr_end, '|');
//printf("内存大小:%11d%10c\n", ptr->size, '|');
printf("%-12s\n", ptr->flag == 0 ? "空闲" : "已分配");
puts("-----------------------------------------------------");
ptr = ptr->next;
}
puts("---------------------------------------------\n\n");
}
void assign(partion *ptr, int need)
{if (need == ptr->size)//空闲的空间恰好等同需要的空间
{ptr->flag = 1;
return;
}
//空闲的空间大于需要的空间
partion *assigned = createPartion(ptr->id, ptr->addr_front, need, 1);
assigned->next = ptr;
assigned->front = ptr->front;
changeIdValue(ptr, 1);//把后面的节点的id值都增加1
ptr->addr_front += need;
ptr->size -= need;
if (ptr->front != NULL)//空闲区的头不空,就在前一个节点后面添加分配的节点
{ptr->front->next = assigned;
}
else//空闲节点前没有节点
{head = assigned;
}
ptr->front = assigned;//空闲节点的头指向新分配的
}
void recovery()
{printf("请输入需要回收作业的ID号:");
int id, flag = 0;
scanf("%d", &id);
partion *ptr = head;
while (ptr != NULL)
{if (id == ptr->id)
{ flag = 1;
break;
}
ptr = ptr->next;
}
if (flag == 0)
{puts("没有找到你需要回收的作业!");
return;
}
if (ptr->flag == 0)
{puts("该ID已经是空闲的了");
return;
}
if (ptr->front == NULL)
{//第一个分区
if (ptr->next == NULL || ptr->next->flag == 1)
{ //后面不空或后面没有
ptr->flag = 0;
return;
}
if (ptr->next->flag == 0)
{ //后面空
ptr->size += ptr->next->size;
ptr->flag = 0;//标记为空闲
if (ptr->next->next != NULL)//把下一个节点的头指向该节点
{ptr->next->next->front = ptr;
}
ptr->next = ptr->next->next;//合并两个节点
free(ptr->next);//真实释放节点
return;
}
}
if (ptr->next == NULL)
{//最后一个分区
if (ptr->front == NULL || ptr->front->flag == 1)
{ //前面不空或者前没有
ptr->flag = 0;
return;
}
if (ptr->front->flag == 0)
{ //前面为空
ptr->front->size += ptr->size;
ptr->front->next = NULL;
free(ptr);
return;
}
}
if (ptr->front->flag == 0 && ptr->next->flag == 0)
{//上下都空
ptr->front->size += ptr->size + ptr->next->size;
ptr->front->next = ptr->next->next;
if (ptr->next->next != NULL)
{ ptr->next->next->front = ptr->front;
}
changeIdValue(ptr->front->next, -2); //更改id
free(ptr->next);
free(ptr);
return;
}
if (ptr->front->flag == 0 && ptr->next->flag == 1)
{//上空下不空
ptr->front->size += ptr->size;
ptr->front->next = ptr->next;
ptr->next->front = ptr->front;
changeIdValue(ptr->front->next, -1);
free(ptr);
return;
}
if (ptr->front->flag == 1 && ptr->next->flag == 0)
{//上不空下空
ptr->size += ptr->next->size;
if (ptr->next->next != NULL)
{ ptr->next->next->front = ptr;
}
partion *p_next = ptr->next; //保存一下下方为空的那个分区,以便一会释放
ptr->next = ptr->next->next;
ptr->flag = 0;
changeIdValue(ptr->next, -1);
free(p_next);
return;
}
if (ptr->front->flag == 1 && ptr->next->flag == 1)
{//上下都不空
ptr->flag = 0;
return;
}
}
void changeIdValue(partion *ptr, int delta)
{while (ptr != NULL)
{ptr->id += delta;
ptr = ptr->next;
}
}
4.运行截图首次适应算法
开始
(1)作业1 申请130 KB
(2)作业2 申请60 KB
(3)作业3 申请100 KB
(4)作业2 释放60 KB
(5)作业3 释放100 KB
(6)作业1 释放130 KB
最佳适应算法
开始:
(1)作业1 申请130 KB
(2)作业2 申请60 KB
(3)作业3 申请100 KB
(4)作业2 释放60 KB
(5)作业3 释放100 KB
(6)作业1 释放130 KB
总流程图:
总流程图是提供程序开始运行的界面图,供用户选择,其中用户可以选择的选项有,首次适应算法,最佳适应算法,内存回收,内存作业的显示。每选择一个功能就执行相应的函数代码。
首次适应算法流程图:
首次适应算法,首先用户输入作业需要的内存大小,然后程序从低地址向高地址寻找空间空间,如果找到空闲空间,如果空闲空间的大小比作业需要的空间大则进行分配,如果空闲空间比作业需要的空间小,则继续寻找下一个空闲空间。如果所有的空闲空间都寻找完也没有符合要求的,那么作业的内存分配失败。
最佳适应算法流程图
最佳适应算法,首页用户输入作业需要的内存空间,程序从低地址开始寻找空闲空间,如果第一次找合适的空间分配,就临时存储这个空间地址,继续向下继续寻找符合的地址空间,如果寻找到合适的空间空间范围,且新的空间大小比临时存储的空间大小还小,则新的符合空间更新为临时符合空间,依次类推到最后。如果程序没有临时最佳的地址空间,则并没有分配到内存,所以作业内存分配失败。如果有临时最佳空间地址,则把最佳的地址空间分配给作业。
内存回收流程图:
作业回收,首先需要需要输入回收作业的ID,先判断作业ID是否存在,存在才能进行释放,在ID存在的前提下判断,该ID的作业状态,只有为已分配状态猜才进行释放。释放则的分情况讨论。释放的节点分为头部,中间,尾部。如果释放的节点前后已经有空闲空间,就需要进行合并。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧