转跳到内容

每 日 算 法 挑 战 【第8期】


推荐贴

第8期来啦!

今天又到周五啦,所以是个模拟题哦!

第8期 内存管理

一个32位程序在运行时,用一个32位的无符号整数表示程序可以用到的内存范围,每一个整数表示一个字节。程序用这个方法,可以表示最多4GB的内存空间,这4GB的内存空间叫做程序的地址空间。之所以说是地址空间而不是内存空间,是因为这4GB内存空间不是一开始就一起划给程序的。程序在需要内存的时候,向操作系统提出申请,操作系统通过一系列比较复杂的操作为程序寻来内存空间,之后把这段内存空间映射到程序地址空间的一段地址上。比如,程序地址空间中30000-40000这10000字节的地址对应的实际存储地址可能分散在1000-6000,46000-48000,2500-5500几段。内存使用结束后,程序会通知操作系统收回这些内存,以备他用。这种方法可以使程序与内存单元解耦,程序可以在内存中转移而不影响其执行,也不会打扰其他程序的执行。

不妨认为程序刚开始运行时,程序没有所属的内存,地址空间中的全部地址都是未映射的。之后随着程序进行,根据其执行情况不断地分配或回收内存。今天我们模拟这一过程。当然了,不涉及操作系统如何寻来实际内存空间的部分。

输入

只有一个用例,其中包含多行,请读取到文件尾。为简便计,以下涉及的数字都是十进制的,均为正且在unsigned int的表示范围之内。

每行可能是下列请求中的一个:

  • malloc B L:表示分配若干实际内存给程序。B表示地址空间基址,L表示内存段的长度,单位为字节。若这个新分配段与其他已有的分配段重合或分配段超出了32位地址空间的限制(即有≥4294967296的部分),则输出一行Segmentation fault while allocating,并取消本次分配;
  • access p:表示程序要访问其地址空间中p位置对应的实存。若p已经分配给了程序,则不输出;否则,输出一行Access violation at p,其中p与输入的p含义相同;
  • free p:表示程序对地址空间基址为p的内存使用完毕,交操作系统回收这段内存。若p不是一个分配段的基址,则输出一行Segmentation fault while freeing,并取消本次内存回收;
  • list:输出当前程序地址空间的使用信息。每个内存段(包括已映射的和未映射的)一行,格式为B L allocated/free,B表示地址空间基址,L表示长度。

输出

参见输入。

样例输入

malloc 0 1000
malloc 2147483648 2147483649
list
access 1024
malloc 1000 1000
access 1024
free 500
access 500
malloc 5000 3000
free 1000
list

样例输出

Segmentation fault while allocating
0 1000 allocated
1000 4294966296 free
Access violation at 1024
Segmentation fault while freeing
0 1000 allocated
1000 4000 free
5000 3000 allocated
8000 4294959296 free

 

,由Mr.K 018修改
注释
摸鱼奇才咖啡喵 摸鱼奇才咖啡喵 200.00节操
链接到点评

唔……二楼补一个召唤阵吧

召唤阵:

@yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui @摸鱼奇才咖啡喵

 

顺便,今天这个题是有多种不同的数据结构可以做的,鼓励大家发现不同的方法

,由Mr.K 018修改

Mr.K 018目睹该饮使用黑魔法和萌懒签订契约使其成为了妹妹,得到3节操并碎了一地

链接到点评
22 分钟前, Mr.K 018 说道:

对付这个题有不少数据结构都能用,平衡树啊,B树啊,B+树啥的都能用

其实实际上我们需要的操作只有

find(x),找到元素x

findPrev(x),找到离x最近且不大于x的元素

findNext(x),找到离x最近且不小于x的元素

add(x),加入元素x并保持有序

delete(x),删除元素x并保持有序

这样mallo B L实际上就是findPrev(B) 然后检查B是否在范围内,findNext(B) 然后检查B+L是否在范围内,如果都安全,就add(B)

access p 实际上就是findPrev(p) 然后检查p是否在范围内

free p 实际上就是find(p),然后安全的话就delelte(p)

list 遍历一遍就好了

剩下的无非就是尽可能让这些操作效率更高就好了

yhz012目睹该饮使用黑魔法和萌懒签订契约使其成为了妹妹,得到2节操并碎了一地

链接到点评

我还是更倾向于用数组的

struct a{

    int data;

    int used;

    int start

}

struct a[2^32],一开始a.used都为0,表示未分配

malloc B L时先查找a到a[B+L],如果有一个used为1则不成功,否则a到a[B+L]中used都为1,start都为B,返回B,如果需要记录什么数据就a[B+i]=?;

access p就是先看a[p].used,再判断是否读a[p].data;

free p就是看a[p].start是否为p,如果是的话就把之后start为p的重置了;

list就是int start,count把整个数组遍历一遍综合看a[p].used和a[p].start,每次走完一段就输出start和count,然后刷新这两个变量

(还没学操作系统,基本上就这样?可能有些地方理解错误了,望指出,动脑是不可能动的,这辈子都不可能的)

 

,由随性而为修改
链接到点评
16 分钟前, 随性而为 说道:

我还是更倾向于用数组的

struct a{

    int data;

    int used;

    int start

}

struct a[2^32],一开始a.used都为0,表示未分配

malloc B L时先查找a到a[B+L],如果有一个used为1则不成功,否则a到a[B+L]中used都为1,start都为B,返回B,如果需要记录什么数据就a[B+i]=?;

access p就是先看a[p].used,再判断是否读a[p].data;

free p就是看a[p].start是否为p,如果是的话就把之后start为p的重置了;

list就是int start,count把整个数组遍历一遍综合看a[p].used和a[p].start,每次走完一段就输出start和count,然后刷新这两个变量

(还没学操作系统,基本上就这样?可能有些地方理解错误了,望指出,动脑是不可能动的,这辈子都不可能的)

 

这个程序,嗯怎么说呢

你没发现你记这个东西所需要的内存空间比32位程序的地址空间还大么

链接到点评
2 小时前, yhz012 说道:

其实实际上我们需要的操作只有

find(x),找到元素x

findPrev(x),找到离x最近且不大于x的元素

findNext(x),找到离x最近且不小于x的元素

add(x),加入元素x并保持有序

delete(x),删除元素x并保持有序

这样mallo B L实际上就是findPrev(B) 然后检查B是否在范围内,findNext(B) 然后检查B+L是否在范围内,如果都安全,就add(B)

access p 实际上就是findPrev(p) 然后检查p是否在范围内

free p 实际上就是find(p),然后安全的话就delelte(p)

list 遍历一遍就好了

剩下的无非就是尽可能让这些操作效率更高就好了

是的,基本上就是这样

不过在free那里有一个空区域合并的细节

链接到点评

用二叉树的思路:

struct{

  int max,min/*代表这一段地址的开始和结束*/,*p/*可以用p=new int[max-min]来存储这一段地址中的数据*/;

  struct btree *lchild,*rchild,*parent;

  int base/*判断是否是最底层,每当创造新结点就令该结点的base为1,令其父结点base变0*/

}btree

基本的结构:结点A表示的地址段和其左右结点的地址段的大小关系为  左子树地址段<父节点地址段<右子树地址段

malloc B L:struct *temp1,将B从根节点开始逐层比较,在这个过程中如果出现(结点A.min<B<结点A.max)则表示需要分配的地址重复,函数执行失败,否则,若A.min>B则temp=A.lchild,若A.max<B则temp=A.rchild,直到最底层,同理struct *temp1对B+L也如此操作,若temp==temp1表明他们在同一个未被分配的地址区间,创造一个结点New和已有的树建立联系,,New.min=B,New.max=B+L,同时New.p=new int[New.max-New.min],若temp!=temp1,说明max和min之间夹杂着已被分配的空间,函数执行失败.

access p:没什么好说的……,就是逐层判断,看p在那个结点的max和min之间,然后访问那个结点的数组,如果找不到对应的max和min,说明未被分配,函数失败

free p:如果p必须是一开始分配时的基地址时,则逐层和min比较,找到了,则将该结点右子树数据复制给该结点,然后释放该结点的右子树(这样做不会改变基本的结构),如果p没什么严格要求的话,就逐层判断p是否在min,max之间,找到了,则该结点的max=p。如果以上两种情况都i没有找到,则函数执行失败

list :如果是这个结构的话好像就是树的中序遍历?当然要是也要显示free的起始和长度的话可以在btree结构体中加一个变量,但这样对这个变量操作有点烦,不如创一个数组记录每段的min和max,排序一下再遍历输出

 

注释
Mr.K 018 Mr.K 018 50.00节操 糖~(抱歉我只能发这么多)
链接到点评
13 分钟前, 随性而为 说道:

用二叉树的思路:

struct{

  int max,min/*代表这一段地址的开始和结束*/,*p/*可以用p=new int[max-min]来存储这一段地址中的数据*/;

  struct btree *lchild,*rchild,*parent;

  int base/*判断是否是最底层,每当创造新结点就令该结点的base为1,令其父结点base变0*/

}btree

基本的结构:结点A表示的地址段和其左右结点的地址段的大小关系为  左子树地址段<父节点地址段<右子树地址段

malloc B L:struct *temp1,将B从根节点开始逐层比较,在这个过程中如果出现(结点A.min<B<结点A.max)则表示需要分配的地址重复,函数执行失败,否则,若A.min>B则temp=A.lchild,若A.max<B则temp=A.rchild,直到最底层,同理struct *temp1对B+L也如此操作,若temp==temp1表明他们在同一个未被分配的地址区间,创造一个结点New和已有的树建立联系,,New.min=B,New.max=B+L,同时New.p=new int[New.max-New.min],若temp!=temp1,说明max和min之间夹杂着已被分配的空间,函数执行失败.

access p:没什么好说的……,就是逐层判断,看p在那个结点的max和min之间,然后访问那个结点的数组,如果找不到对应的max和min,说明未被分配,函数失败

free p:如果p必须是一开始分配时的基地址时,则逐层和min比较,找到了,则将该结点右子树数据复制给该结点,然后释放该结点的右子树(这样做不会改变基本的结构),如果p没什么严格要求的话,就逐层判断p是否在min,max之间,找到了,则该结点的max=p。如果以上两种情况都i没有找到,则函数执行失败

list :如果是这个结构的话好像就是树的中序遍历?当然要是也要显示free的起始和长度的话可以在btree结构体中加一个变量,但这样对这个变量操作有点烦,不如创一个数组记录每段的min和max,排序一下再遍历输出

 

方向有了,但是光二叉树是不够的,比如这个结构就可以构造输入让每一次的malloc操作变成O(n)

不过,方向是对的,真正的数据结构和这个差不多,不过需要在插入和删除的时候做一些工作来让整个树结构的深度差距不太大(比如一边有好多子树,另一边却是光的)

,由Mr.K 018修改
链接到点评
15 小时前, Mr.K 018 说道:

是的,基本上就是这样

不过在free那里有一个空区域合并的细节

:mx040:啊……咱的想法是没分配的直接就不保留信息了,所以空区域的长度是取决于后面一个分配的区域的基址的,当然如果后面没有分配的区域了,就直接用2^32带走就好了

链接到点评
1 小时前, yhz012 说道:

:mx040:啊……咱的想法是没分配的直接就不保留信息了,所以空区域的长度是取决于后面一个分配的区域的基址的,当然如果后面没有分配的区域了,就直接用2^32带走就好了

真实环境下肯定是要保存空区域信息的。但是,这个方法做本题应该是可以的

链接到点评
×
×
  • 新建...

重要消息

为使您更好地使用该站点,请仔细阅读以下内容: 使用条款