【问题描述】
离第一个操作系统HNU-OS发布已经没有多少时间了,但它的一些组件还没有完成,内存管理器就是其中之一。根据开发人员的计划,在第一个版本中,内存管理器将非常简单和直观。它将支持三个操作:
-
alloc n —— 分配n个字节内存,返回已分配块的正整数标识符x(x初始值为0,每次分配增长1)
-
erase x —— 删除标识符x所在的块
-
defragment —— 整理空余内存碎片,将所有块尽量靠近内存的开始位置,并保持各自的顺序
在此情况下,内存模型非常简单,它是一个m字节的序列,为了方便起见,从第一个字节到第m字节进行编号。
第一个操作alloc n有一个参数n,表示被分配的内存块大小。在处理此操作时,内存中将分配n个连续字节的空闲块。 如果这些块的数量超过一个,则优先选择最接近内存开始(即第一个字节)的块。 所有这些字节都被标记为非空闲,内存管理器返回一个32位整数数字令牌,代表该块的标识符。 如果不可能分配这样大小的空闲块,则返回NULL。
第二个操作erase x以x为参数,表示某个块的标识符。此操作释放系统内存,将此块的字节标记为空闲以供进一步使用。 如果此标识符没有指向先前分配的块(该块尚未被释放),则返回ILLEGAL_ERASE_ARGUMENT。
最后一个操作defragment没有任何参数,只会使占用的内存部分更接近内存的开始,而不会更改它们各自的顺序。
在当前的实现中,将使用从1开始的连续整数作为标识符。每个成功的alloc操作过程都应该返回接下来的编号。不成功的alloc操作不影响计数。
编写内存管理器的实现,为每个alloc命令输出返回的值,为所有失败的erase命令输出ILLEGAL_ERASE_ARGUMENT。
【输入形式】
输入数据的第一行包含两个正整数t和m(1<=t<=500, 1<=m<=105),其中t表示需要内存管理器来处理的操作个数,m表示有效的内存字节大小。接下来的t行每一行代表一个操作。
【输出形式】
输出有多行,每行或者是alloc操作的结果,或者是失败的erase操作的结果ILLEGAL_ERASE_ARGUMENT。其顺序与输入的操作次序一致。
【样例输入】
6 10
alloc 5
alloc 3
erase 1
alloc 6
defragment
alloc 6
【样例输出】
1
2
NULL
3
【解题思路】
1.模拟内存空间:
由于数据量可能比较大,用vector
2.模拟占用内存操作
1)寻找空闲内存段
遍历vector,寻找第一个空闲位置,记录由它开始的最长空闲内存段,如果足够使用,则将这段内存块起始位置记录下来;如果不够,则继续往下找,直到遍历到了最后一个位置(此时无法插入新内存,返回NULL)
2)标记内存段
从记录的起点开始的长为所需大小的内存,标记上当前标识符数字,表示该 段内存被标识符x所占用
3)标识符更新
3.模拟清除内存操作
以标识符为参数,寻找内存中标记为x的内存位,将其标识为0,表示清空
若遍历vector仍未找到该标识符,则返回清楚无效
4.模拟内存整理操作
因为vector长度实际上是“无限的”,只是有规定的size约束内存大小;因此在进行内存块的迁移时,只要将所有的空闲位置删除,那么所有内存块就会靠近起始的位置
5.各项操作的输出:用flag作为标记操作的成功与否,对应进行输出
【AC代码】
#include#include #include #include #include using namespace std; void alloc(vector & v,int a_size,int &x){ int flag=0; int st=0; for(int i=0;i & v,int x){ bool flag=0; for(int i=0;i &v,int& x){ //使用删除0 末尾补零的操作 int s=v.size() ; for(int i=0;i >n; cin>>a_size; int x=0; vector v(a_size); for(int i=0;i >s; if(s=="alloc") { int one_size; cin>>one_size; alloc(v,one_size,x); }else if(s=="erase"){ int e; cin>>e; erase(v,e); e_times++; }else{ defragment(v,e_times); } //for(int i=0;i 【写在后面】
觉得对你有帮助的话记得点个小小的赞哦~ <(^-^)>
相关题目放在了【HNU CJ】专栏
如果有啥问题可以评论留言或者私我哦~