动态分区算法

一个不知名大学生，江湖人称菜狗
original author: Jacky Li
Email : 3435673055@qq.com

Time of completion：2024.04.09
Last edited: 2024.04.09

目录

动态分区算法

第1关：首次适应算法

任务描述

相关知识

内存分配

内存回收

编程要求

测试说明

代码如下

第2关：最佳适应算法

相关知识

内存分配

内存回收

编程要求

测试说明

代码如下

动态分区算法

第1关：首次适应算法

任务描述

假设初始状态下可用的内存空间为55MB，并有如下的请求序列： 作业1申请15MB 作业2申请30MB 作业1释放15MB 作业3分配8MB 作业4分配6MB 作业2释放30MB 请采用首次适应算法进行内存块的分配和回收，并打印出空闲内存分区链的情况

相关知识

为了完成本关任务，你需要掌握使用首次适应算法进行内存块的分配与回收。

内存分配

空闲分区链按地址递增的顺序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首到链尾都找不到一个能满足要求的分区，则表明系统没有足够大的内存分配给该进程，内存分配失败返回。

内存回收

当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一： (1) 回收区与插入点的前一个空闲分区F1相邻接，此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。 (2) 回收分区与插入点的后一空闲分区F2相邻接，此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。 (3) 回收区同时与插入点的前、后两个分区F1和F2邻接，此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。 (4) 回收区前后没有空闲分区。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置

编程要求

空闲分区采用带头结点的双向链表来管理，主函数、链表初始化函数和打印函数已实现，只需要补充首次适应算法分配内存的函数 first_fit以及内存回收的函数recycle()即可。

bool first_fit(int id,int m_size)//使用首次适应算法给作业分配内存，id为作业号，m_size为作业大小 void recycle(int id)//回收内存,id为释放内存的作业号

测试说明

平台会对你编写的代码进行测试：

代码如下

#include <stdio.h>
#include <stdlib.h>

const int Max_length=55;//最大内存

struct areaNode//管理分区的结构体
{	
    int ID;//分区号	
    int size;//分区大小	
    int address;//分区地址	
    int flag;//使用状态，0为未占用，1为已占用
};

typedef struct DuNode//双向链表结点
{ 
  struct areaNode data;//数据域	
  struct DuNode *prior;//指针域	
  struct DuNode *next;
}*DuLinkList;
DuLinkList m_head = new DuNode, m_last = new DuNode;//双向链表首尾指针
  
void init()//分区链表初始化
{	
  m_head->prior = NULL;	
  m_head->next = m_last;	
  m_last->prior = m_head;	
  m_last->next = NULL;	
  m_head->data.size = 0;	
  m_last->data.address = 0;	
  m_last->data.size = Max_length;	
  m_last->data.ID = 0;
  m_last->data.flag = 0;
}

void show()
{	
  DuNode *p = m_head->next;//指向空闲区队列的首地址	
  printf("+++++++++++++++++++++++++++++++++++++++\n");	
  while (p)	
  {		
    printf("分区号：");		
	if (p->data.ID == 0)			
	  printf("FREE\n");		
	else			
	  printf("%d\n",p->data.ID);		
	printf("分区起始地址：%d\n",p->data.address);		
	printf("分区大小：%d\n",p->data.size);		
	printf("分区状态：");		
	if (p->data.flag)			
	  printf("已被占用\n");		
	else			
	  printf("空闲\n");		
	printf("——————————————————\n");		
	p = p->next;	
  }
} 

bool first_fit(int id,int m_size)//首次适应算法,id为作业号，m_size为作业大小 
{    
    //请补充使用首次适应算法给作业分配内存的函数代码
    DuLinkList temp=(DuLinkList)malloc(sizeof(DuNode));//申请双向链表指针节点temp(*a.b=a->b) 
    DuNode *p=m_head->next;
    temp->data.ID=id;//*temp.data.ID
    temp->data.size=m_size;
    temp->data.flag=1;
    
    while(p){//循环查找 
      
        if(p->data.flag==0&&p->data.size==m_size){//p节点未占用，并且空间刚好满足 
            p->data.flag=1;
            p->data.ID=id;
           return false;
        }
        if(p->data.flag==0&&p->data.size>m_size){//p节点未占用，且空间大于所需 
            temp->next=p;
            temp->prior=p->prior;//temp 插入p之前 
            
            temp->data.address=p->data.address;//分区起始地址 
            p->prior->next=temp;
            p->prior=temp;
            p->data.address=temp->data.address+temp->data.size;
            p->data.size-=m_size;
          return false;
        }
        p=p->next;
    }
  return true;

}


void recycle(int id)//回收内存,id为释放内存的作业号 
{    
    //请补充回收作业内存的代码
    
     DuLinkList n=m_head->next ;
    while(n)
    {
       
        DuLinkList q=n->next;
        if(n->data.ID==id)
        {
            if(n->prior!=m_head&&n->prior->data.flag==0&&n->next->data.flag==0)
            {
                n->prior->data.size = n->prior->data.size+q->data.size+n->data.size;
                 q->prior= n->prior;
                 n->prior->next=q;
                 
                 if(q==m_last)
                 {
                 n->prior->next=NULL;
                 n->prior->data.ID=0;
                 }
                 delete(n);
                
            }
            else if(n->prior!=m_head&&n->prior->data.flag==0&&n->next->data.flag != 0)
            { 
                n->prior->data.size+=n->data.size;
                n->prior->next=q;
                q->prior=n->prior;
                delete n;
                break; 
            }
            else if(n->next->data.flag==0&&n->prior->data.flag!=0&&n->prior!=m_head)
            { 
              n->data.size+=q->data.size;
              n->next=q->next;
              n->data.flag=0;
              q->next->prior=n;
              delete q;
              break;
            }
            else
            {
              n->data.flag=0;
              
              break;
            }
        }
        n=n->next;
    }
    
}
int main()
{
	init();
        
    printf("首次适应算法：\n");
	first_fit(1,15);
	first_fit(2,30);
	recycle(1);
	first_fit(3,8);
	first_fit(4,6);
	recycle(2);
	
	show();
	
	DuNode *p = m_head;
	while(p != NULL)
	{
		DuNode *temp =  p;
		p = p->next;
		delete(temp);
		temp = NULL;
	}
	
	return 0;
}

第2关：最佳适应算法

假设初始状态下可用的内存空间为55MB，并有如下的请求序列： 作业1申请15MB 作业2申请30MB 作业1释放15MB 作业3分配8MB 作业4分配6MB 作业2释放30MB 请采用最佳适应算法进行内存块的分配和回收，并打印出空闲内存分区链的情况

相关知识

为了完成本关任务，你需要掌握使用最佳适应算法进行内存块的分配与回收。

内存分配

每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。若从链首到链尾都找不到一个能满足要求的分区，则表明系统没有足够大的内存分配给该进程，内存分配失败返回。

内存回收

当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一： (1) 回收区与插入点的前一个空闲分区F1相邻接，此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。 (2) 回收分区与插入点的后一空闲分区F2相邻接，此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。 (3) 回收区同时与插入点的前、后两个分区F1和F2邻接，此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。 (4) 回收区前后没有空闲分区。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置

编程要求

空闲分区采用带头结点的双向链表来管理，主函数、链表初始化函数和打印函数已实现，只需要补充最佳适应算法分配内存的函数 best_fit以及内存回收的函数recycle()即可。

bool best_fit(int id,int m_size)//使用最佳适应算法给作业分配内存，id为作业号，m_size为作业大小 void recycle(int id)//回收内存,id为释放内存的作业号

测试说明

平台会对你编写的代码进行测试：

代码如下

#include <stdio.h>
#include <stdlib.h>

const int Max_length=55;//最大内存

struct areaNode//管理分区的结构体
{	
    int ID;//分区号	
    int size;//分区大小	
    int address;//分区地址	
    int flag;//使用状态，0为未占用，1为已占用
};

typedef struct DuNode//双向链表结点
{ 
  struct areaNode data;//数据域	
  struct DuNode *prior;//指针域	
  struct DuNode *next;
}*DuLinkList;
DuLinkList m_head = new DuNode, m_last = new DuNode;//双向链表首尾指针
  
void init()//分区链表初始化
{	
  m_head->prior = NULL;	
  m_head->next = m_last;	
  m_last->prior = m_head;	
  m_last->next = NULL;	
  m_head->data.size = 0;	
  m_last->data.address = 0;	
  m_last->data.size = Max_length;	
  m_last->data.ID = 0;
  m_last->data.flag = 0;
}

void show()
{	
  DuNode *p = m_head->next;//指向空闲区队列的首地址	
  printf("+++++++++++++++++++++++++++++++++++++++\n");	
  while (p)	
  {		
    printf("分区号：");		
	if (p->data.ID == 0)			
	  printf("FREE\n");		
	else			
	  printf("%d\n",p->data.ID);		
	printf("分区起始地址：%d\n",p->data.address);		
	printf("分区大小：%d\n",p->data.size);		
	printf("分区状态：");		
	if (p->data.flag)			
	  printf("已被占用\n");		
	else			
	  printf("空闲\n");		
	printf("——————————————————\n");		
	p = p->next;	
  }
} 


bool best_fit(int id, int m_size)//最佳适应算法，其中需要查找最佳的存放位置
{	
    //请补充使用最佳适应算法给作业分配内存的函数代码
    
    DuLinkList m = new DuNode;
	DuNode *p = m_head->next; 
	DuNode *q;
	int min=1000;
	while(p)
	{
		
		if(p->data.flag==0) 
		{
			int size=p->data.size-m_size;
			if(size<min&&size>0) 
			{
				q=p;
				min = size;
			}
		}
		p=p->next;
	 }
	m->prior= q->prior;
	q->prior->next=m;
	m->next=q;
	q->prior =m;
	
	m->data.flag=1;
	if(m->prior==m_head)
	m->data.address= 0;
	else
	m->data.address=m->prior->data.address+m->prior->data.size;
	
	m->data.ID=id;
	m->data.size=m_size;
	
	q->data.address=m->data.address+m->data.size;
	q->data.ID=0;
	q->data.size = q->data.size-m_size; 
	
	 
	
}
	



void recycle(int id)//回收内存,id为释放内存的作业号 
{	
    //请补充回收作业内存的函数代码
     DuLinkList n=m_head->next ;
    while(n)
    {
       
        DuLinkList q=n->next;
        if(n->data.ID==id)
        {
            if(n->prior!=m_head&&n->prior->data.flag==0&&n->next->data.flag==0)
            {
                n->prior->data.size = n->prior->data.size+q->data.size+n->data.size;
                 q->prior= n->prior;
                 n->prior->next=q;
                 
                 if(q==m_last)
                 {
                 n->prior->next=NULL;
                 n->prior->data.ID=0;
                 }
                 delete(n);
                
            }
            else if(n->prior!=m_head&&n->prior->data.flag==0&&n->next->data.flag != 0)
            { 
                n->prior->data.size+=n->data.size;
                n->prior->next=q;
                q->prior=n->prior;
                delete n;
                break; 
            }
            else if(n->next->data.flag==0&&n->prior->data.flag!=0&&n->prior!=m_head)
            {
              n->data.size+=q->data.size;
              n->next=q->next;
              n->data.flag=0;
              q->next->prior=n;
              delete q;
              break;
            }
            else
            {
              n->data.flag=0;
              
              break;
            }
        }
        n=n->next;
    }
    
}

int main()
{
	init();
	 
    //最佳适应算法
	printf("最佳适应算法：\n");
	init();
	best_fit(1,15);
	best_fit(2,30);
	recycle(1);
	best_fit(3,8);
	best_fit(4,6);
	recycle(2); 
	

	show();
	
	DuNode *p = m_head;
	while(p != NULL)
	{
		DuNode *temp =  p;
		p = p->next;
		delete(temp);
		temp = NULL;
	}
	
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/528436.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

chronyd服务

chronyd服务

一、介绍 chronyd服务是CentOS8系统之后提供时间服务的应用&#xff0c;和之前的ntp服务功能是一样的。 chronyd服务的配置文件默认存在在/etc/chrony.conf中。 chronyd服务的开启方式和关闭&#xff1a; systemctl start chronyd systemctl status chronyd systemctl st…
阅读更多...
每天好好学习java第一天--复习巩固基础

每天好好学习java第一天--复习巩固基础

1.浮点数数据特殊&#xff1a; float z 2.0e8F; float类型要在后面加f或者F。但是double类型可以省略。 2.强制转换数据类型&#xff1a; 格式&#xff1a; (类型名)变量名 例 float z 2.0f; int x(int)z; 3.逻辑运算符 注意异或 4.条件运算符 每天学习一会java&…
阅读更多...
性能分析-数据库与磁盘知识

性能分析-数据库与磁盘知识

数据库 数据库&#xff0c;其实是数据库管理系统dbms。 数据库管理系统&#xff0c; 常见&#xff1a; 关系型数据库&#xff1a; mysql、pg、 库的表&#xff0c;表与表之间有关联关系&#xff1b; 表二维表统一标准的SQL&#xff08;不局限于CRUD&#xff09;非关系型数据…
阅读更多...
配置VM开机自启动

配置VM开机自启动

1. 在此电脑-右键选择“管理”-服务和应用程序-服务中找到VMware Workstation Server服务&#xff08;新版名称也可能是VMware自启动服务&#xff0c;自己找一下&#xff0c;服务属性里有描述信息的&#xff09;&#xff0c;将其启用并选择开机自动启动 新版参考官方文档&…
阅读更多...
C语言 函数——函数原型

C语言 函数——函数原型

目录 如何合并成一个完整的程序&#xff1f; 函数原型与函数定义的区别 函数原型的作用 如何合并成一个完整的程序&#xff1f; 问题&#xff1a;在一个函数中调用另一个函数&#xff0c;需要具备哪些条件呢&#xff1f; 若函数的定义出现在函数调用之前 若函数的定义出现…
阅读更多...
跨云迁移实操：AWS RDS for mysql 迁移至腾讯云mysql --DTS方式

跨云迁移实操：AWS RDS for mysql 迁移至腾讯云mysql --DTS方式

实操场景&#xff1a;从AWS RDS for mysql 迁移至腾讯云云数据库Mysql&#xff0c;通过腾讯云数据传输服务DTS,进行实时全量增量迁移. 下面九河云给大家带来具体实践介绍 购买迁移数据库--目的端机器&#xff08;腾讯云MYSQL&#xff09; 可以源端为5.7所以新建一个参数模版 其…
阅读更多...
4 万字 102 道Java经典面试题总结（2024修订版）- 多线程篇

4 万字 102 道Java经典面试题总结（2024修订版）- 多线程篇

&#x1f345; 作者简介&#xff1a;哪吒&#xff0c;CSDN2021博客之星亚军&#x1f3c6;、新星计划导师✌、博客专家&#x1f4aa; &#x1f345; 哪吒多年工作总结&#xff1a;Java学习路线总结&#xff0c;搬砖工逆袭Java架构师 &#x1f345; 技术交流&#xff1a;定期更新…
阅读更多...
全新AI天空任意生成解决方案，颠覆传统换天效果

全新AI天空任意生成解决方案，颠覆传统换天效果

在数字化时代&#xff0c;影像创作已经成为企业展示品牌形象、传递信息的重要手段。特别是在汽车拍摄和旅行拍摄等场景中&#xff0c;天空作为画面中不可或缺的元素&#xff0c;其表现往往直接关系到作品的质感和吸引力。然而&#xff0c;传统的天空替换技术往往操作繁琐、效果…
阅读更多...
中小初创企业如何做好媒体宣传?

中小初创企业如何做好媒体宣传?

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体网胡老师。 中小初创企业在做媒体宣传时&#xff0c;由于通常资源有限&#xff0c;需要更加精明地使用外部资源来提升品牌知名度和业务成长。利用专业的媒体服务商可以是一个非常有效的方法。 明确…
阅读更多...
可视化大屏的应用（9）：设备运行监控的应用案例

可视化大屏的应用（9）：设备运行监控的应用案例

通过可视化大屏&#xff0c;监控人员可以更加直观地了解设备的运行情况&#xff0c;及时发现问题并进行处理&#xff0c;提高设备的稳定性和可靠性&#xff0c;大千UI工场本期带来相关利用的案例&#xff0c;欢迎友友们品鉴。 可视化大屏在设备运行监控领域有以下作用&#xf…
阅读更多...
并发编程之AtomicInteger,AtomicLong,LongAdder

并发编程之AtomicInteger,AtomicLong,LongAdder

系列文章目录 文章目录 系列文章目录前言前言 前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站，这篇文章男女通用，看懂了就去分享给你的码吧。 AtomicInteger类是系统底层保护的int类型，通过提供执行方法的控制进行值…
阅读更多...
选择排序解读

选择排序解读

在计算机科学中&#xff0c;排序算法是一种将数据元素按照某种顺序排列的算法。今天&#xff0c;我们要探讨的是选择排序&#xff08;Selection Sort&#xff09;&#xff0c;这是一种简单直观的排序方法&#xff0c;通过不断选择剩余元素中的最小&#xff08;或最大&#xff0…
阅读更多...
python之正则表达式（2）

python之正则表达式（2）

1、贪婪量词和懒惰量词 贪婪量词&#xff1a;也就是尽可能多的匹配字符 懒惰量词&#xff1a;尽可能少的匹配字符&#xff08;在现在的计算机语言中大多默认为贪婪量词若想要使用 懒惰量词就需要在后面加上&#xff1f;即可&#xff09; 代码示例&#xff1a; import rep …
阅读更多...
[中级]软考_软件设计_计算机组成与体系结构_11_性能指标

[中级]软考_软件设计_计算机组成与体系结构_11_性能指标

性能指标 字长通路&#xff1a;运算速度总结往年真题 字长 总线字长假设为32位就是 2 32 2^{32} 232,也就是4G,现在所说的32位和64位计算机是由一定关系的。 通路&#xff1a; 一次允许通过的数据量&#xff0c;也是指数据脉冲 运算速度 主频影响运算速度。 主频与CPU时…
阅读更多...
RabbitMQ的介绍

RabbitMQ的介绍

为什么使用 MQ&#xff1f; 流量削峰和缓冲 如果订单系统最多能处理一万次订单&#xff0c;这个处理能力在足够应付正常时段的下单&#xff0c;但是在高峰期&#xff0c;可能会有两万次下单操作&#xff0c;订单系统只能处理一万次下单操作&#xff0c;剩下的一万次被阻塞。我们…
阅读更多...
回归测试覆盖率指的是什么？

回归测试覆盖率指的是什么？

定义 回归测试是指修改了旧代码后&#xff0c;重新进行测试以确认修改没有引入新的错误或导致其他代码产生错误。 在软件开发过程当中&#xff0c;一旦软件代码做了修改&#xff0c;就有可能引入新的问题&#xff0c;所以这个时候就需要把已经完成了的验证用例重新跑一下&…
阅读更多...
Colossal AI 多维TP

Colossal AI 多维TP

Colossal AI 多维TP 1. 2D TP 1.1. SUMMA 2D 矩阵乘法 数值示例&#xff1a; 条件&#xff1a;每个矩阵都可以均匀的拆分为 pq^2块&#xff08;行q块&#xff0c;列q块&#xff09; 1.2. Transformers上的应用 b: batch size s: seq_len h: hidden size p: GPUs q: pq^2 输…
阅读更多...
查分约束学习

查分约束学习

问题模型&#xff1a; 有n个变量&#xff1a;&#xff0c;有m个约束条件 令差分数组&#xff0c;可以知道如果x1x2<q&#xff0c;那么与j和i-1有关联 由画图可知&#xff0c;如果有在i-1至j建立的有向图中跑最短路&#xff0c;那么dis[n]即为最小的约束变量 另外&#x…
阅读更多...
数据库(mysql)-基础知识点-2

数据库(mysql)-基础知识点-2

子查询 MySQL中的子查询&#xff08;Subquery&#xff09;是嵌套在其他SQL查询中的查询。子查询可以出现在SELECT、FROM或WHERE子句中&#xff0c;并用于返回将被用于外部查询的数据。子查询的结果可以是一个单一的值、一行、一列或多行多列的数据集。 单行单列查询 实例 #查…
阅读更多...
Prompt提示工程上手指南:基础原理及实践(五)-思维树 (ToT)策略下的Prompt

Prompt提示工程上手指南:基础原理及实践(五)-思维树 (ToT)策略下的Prompt

前言 此篇文章已经是本系列的第五篇文章&#xff0c;之前我们已经将检索增强生成(RAG)策略&#xff0c;逐渐我们掌握的知识和技术都在不断提高&#xff0c;对于Prompt的技巧策略也不能只局限于局部运用而要适应LLM大模型的整体框架去进行改进休整。较为主流的LLM模型框架设计基…
阅读更多...
最新文章

Copyright @ 2022~2023