头歌 计算机操作系统 动态分区算法

ops/2024/12/12 19:26:33/

第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");elseprintf("%d\n",p->data.ID);printf("分区起始地址：%d\n",p->data.address);printf("分区大小：%d\n",p->data.size);printf("分区状态：");if (p->data.flag)printf("已被占用\n");elseprintf("空闲\n");printf("——————————————————\n");p = p->next;}
}
bool first_fit(int id,int m_size)//首次适应算法,id为作业号，m_size为作业大小 
{//请补充使用首次适应算法给作业分配内存的函数代码DuLinkList p = m_head;while(p != m_last) {DuLinkList n = p->next;if(!n->data.flag && n->data.size >= m_size) {DuLinkList t = new DuNode();t->data.ID = id;t->data.size = m_size;t->data.address = n->data.address;t->data.flag = 1;n->data.address += m_size;n->data.size -= m_size;t->prior = p;t->next = n;p->next = t;n->prior = t;}p = n;}
}
void recycle(int id)//回收内存,id为释放内存的作业号 
{DuLinkList p = m_head;while(p != m_last) {DuLinkList n = p->next;if(n->data.ID == id) {p->next = n->next;n->next->prior = p;n->next->data.address -= n->data.size;m_last->data.size += n->data.size;delete n;n = n->next;}if(n != m_last)n->next->data.address = n->data.address + n->data.size;p = n;}
}
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");elseprintf("%d\n",p->data.ID);printf("分区起始地址：%d\n",p->data.address);printf("分区大小：%d\n",p->data.size);printf("分区状态：");if (p->data.flag)printf("已被占用\n");elseprintf("空闲\n");printf("——————————————————\n");p = p->next;}
}
bool best_fit(int id, int m_size)//最佳适应算法，其中需要查找最佳的存放位置
{//请补充使用最佳适应算法给作业分配内存的函数代码DuLinkList p = m_head;DuLinkList t = nullptr;while(p != m_last) {DuLinkList n = p->next;if(!n->data.flag && n->data.size >= m_size) {if(t == nullptr || t->data.size > n->data.size){t = n;}}p = n;}if(t == nullptr)return false;if(t->data.size == m_size) {t->data.flag = 1;t->data.ID = id;}else {DuLinkList t2 = new DuNode();t2->next = t;t2->prior = t->prior;t->prior->next = t2;t->prior = t2;t2->data.ID = id;t2->data.flag = 1;t2->data.address = t->data.address;t->data.address += m_size;t2->data.size = m_size;t->data.size -= m_size;}return true;
}
void recycle(int id)//回收内存,id为释放内存的作业号 
{//请补充回收作业内存的函数代码DuLinkList p = m_head;DuLinkList n = nullptr;while(p != m_last) {n = p->next;if(n->data.ID == id) {break;}p = n;}if(n == nullptr || n == m_last)return;n->data.flag = 0;n->data.ID = 0;DuLinkList np = n->prior;DuLinkList nn = n->next;if(np != m_head && np->data.flag == 0) {np->prior->next = n;n->prior = np->prior->next;n->data.address = np->data.address;n->data.size += np->data.size;delete np;}if((nn != nullptr || nn != m_last) && nn->data.flag == 0) {nn->next->prior = n;n->next = nn->next->prior;n->data.size += nn->data.size;delete nn;}
}
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;
}


http://www.ppmy.cn/ops/141318.html

相关文章

css 权重

css 权重

发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【宝藏入口】。 CSS 权重&#xff08;或称为 CSS 优先级&#xff09;决定了当多个 CSS 规则作用于同一元素时&#xff0c;哪一条规则会被应用。…
阅读更多...
Linux Minio 安装

Linux Minio 安装

找个安装目录 /usr/local/ 下 mkdir minio cd minio mkdir data mkdir bin chmod 777 data/ chmod 777 bin/ 日志文件 touch minio.log #wget https://dl.minio.org.cn/server/minio/release/linux-amd64/minio wget https://dl.minio.io/server/minio/release/linux-amd64/min…
阅读更多...
React之react-redux的使用

React之react-redux的使用

前言 前面我们讲过了redux的配置及使用&#xff0c;下面我们看一下react-redux的是如何使用的, 首先我们先了解一下redux和react-redux的关系&#xff1f; redux和react-redux的关系 redux是react中进行state状态管理的JS库&#xff08;并不是react插件&#xff09;&#xff0c…
阅读更多...
图论【Lecode_HOT100】

图论【Lecode_HOT100】

文章目录 1.岛屿数量No.2002.腐烂的橘子No.9943.课程表No.2074.实现Trie&#xff08;前缀树&#xff09;No.208 1.岛屿数量No.200 class Solution {public int numIslands(char[][] grid) {if (grid null || grid.length 0) {return 0;}int numIslands 0;int rows grid.len…
阅读更多...
Redis02 SpringBoot整合Redis

Redis02 SpringBoot整合Redis

使用方式 1.创建boot项目引入Web(Spring Web)NoSQl(Spring Data Redis(AccessDriver)) 2.修改配置文件 spring:redis:host: 127.0.0.1port: 6379password: 123456lettuce:pool:max-active: 8 #最大连接max-idle: 8 #最大空闲连接min-idle: 0 #最小空闲连接max-wait: 1000ms #…
阅读更多...
PT8M2103 触控 I/O 型 8-Bit MCU

PT8M2103 触控 I/O 型 8-Bit MCU

1 产品概述 ● PT8M2103 是一款可多次编程(MTP)I/O 型8位 MCU&#xff0c;其包括 2K*16bit MTP ROM、256*8bit SRAM、PWM、Touch 等功能&#xff0c;具有高性能精简指令集、低工作电压、低功耗特性且完全集成触控按键功能。为各种触控按键的应用&#xff0c;提供了一种简单而又…
阅读更多...
109.【C语言】数据结构之二叉树层序遍历

109.【C语言】数据结构之二叉树层序遍历

目录 1.知识回顾 2.代码实现 准备工作 LevelOrder函数 代码框架 关键代码 3.执行结果 1.知识回顾 层序遍历参见106.【C语言】数据结构之二叉树的三种递归遍历方式文章 截取的部分内容 定义:按层的方式遍历(,设n为树的深度,h1-->h2-->h3-->...-->hn) 以下面…
阅读更多...
15.Java 网络编程（网络相关概念、InetAddress、NetworkInterface、TCP 网络通信、UDP 网络通信、超时中断）

15.Java 网络编程（网络相关概念、InetAddress、NetworkInterface、TCP 网络通信、UDP 网络通信、超时中断）

一、网络相关概念 1、网络通信 网络通信指两台设备之间通过网络实现数据传输&#xff0c;将数据通过网络从一台设备传输到另一台设备 java.net 包下提供了一系列的类和接口用于完成网络通信 2、网络 两台以上设备通过一定物理设备连接构成网络&#xff0c;根据网络的覆盖范…
阅读更多...
最新文章

Copyright @ 2022~2023