C++不连续地分配数组

Question

让我们将这个C++代码视为一个粗略的例子.

int *A = new int [5];
int *B = new int [5];
int *C = new int [5];
delete []A;
delete []C;
int *D = new int [10];

显然,任何机器都可以处理这种情况,而不会出现缓冲区溢出或内存泄漏问题.但是,让我们假设长度乘以一百万甚至更大的数字.据我所知,所有数组元素的地址(至少是虚拟地址)都是连续的.因此,每当我创建一个数组时,我可以确定它们是虚拟内存中的连续块,如果我有指向第一个元素的指针,我可以执行指针运算来访问第n个元素.我的问题在下图中说明(为简单起见,忽略表示数组末尾的寄存器).

在堆中分配A,B,C之后,我们释放A和C并获得两个长度为5的空闲内存块(用绿点标记).当我想分配一个长度为10的数组时会发生什么？我认为有3种可能的情况.

• 因为没有连续的10长度内存块,我将得到bad_alloc异常.
• 程序将自动将数组B重新分配到堆的开头,并将剩余的未使用内存连接在一起.

• 数组D将被分成两部分并且不连续存储,导致数组的第n个元素的访问时间不恒定(如果有多于2个分裂,则它开始类似于链表而不是数组).

  哪一个是最可能的答案还是有其他可能的情况我没有考虑到？

Answer 1

你问的问题叫做堆碎片,这是一个真正的难题.

因为没有连续的10长度内存块,我将得到bad_alloc异常.

这就是理论.但这种情况实际上只能在32位进程中实现; 64位地址空间很大.

也就是说,使用64位进程,堆碎片更有可能阻止您的new实现重用某些内存,这会导致内存不足,因为它需要向内核请求整个D阵列的新内存一半.此外,当您尝试访问某个位置D而不是new抛出异常时,这样的OOM条件更有可能导致您的进程被OOM杀手攻击,因为内核不会意识到它已经过度使用了它的内存在为时已晚之前.有关更多信息,谷歌"内存过度使用".

程序将自动将数组B重新分配到堆的开头,并将剩余的未使用内存连接在一起.

不,它不能.您使用的是C++,并且您的运行时不知道您可能存储指针的位置B,因此它会冒着丢失需要修改的指针的危险,或者冒着修改不是指针B但发生的事情的危险具有相同的位模式.

数组D将被分成两部分并且不连续存储,导致数组的第n个元素的访问时间不恒定(如果有多于2个分裂,则它开始类似于链表而不是数组).

这也是不可能的,因为C++保证了数组的连续存储(允许通过指针算法实现数组访问).

Answer 2

因为没有连续的10长度内存块,我将得到bad_alloc异常.

这可能发生.

程序将自动将数组B重新分配到堆的开头,并将剩余的未使用内存连接在一起.

这不可能发生.在C++中无法将对象移动到其他地址,因为它会使现有指针无效.

数组D将被分成两部分并且不连续存储,导致数组的第n个元素的访问时间不恒定(如果有多于2个分裂,则它开始类似于链表而不是数组).

这也不可能发生.在C++中,数组元素是连续存储的,因此可以进行指针运算.

但实际上有更多的可能性.要理解它们,我们必须考虑到内存可以是虚拟的这一事实.除其他外,这意味着可用地址空间可能大于物理存在的存储器的数量.可以从可用地址空间为一块物理内存分配任何地址.

例如,考虑一台在64位CPU上运行64位操作系统的8GB(2 ^ 33字节)内存的计算机.分配给该程序的地址不会低于8GB; 它可以在地址0x00000000ffff0000接收一兆字节的内存,在地址0x0000ffffffff0000接收另一兆字节的内存.分配给程序的内存总量不能超过2 ^ 33个字节,但每个块可以位于2 ^ 64空间中的任何位置.(实际上这有点复杂,但与我所描述的相似).

在你的图片中,你有15个代表大块内存的小方块.让我们说它是物理记忆.虚拟内存是15,000个小方块,在任何给定时间你都可以使用任何 15个方块.

因此,考虑到这一事实,以下情况也是可能的.

• 为程序提供了一块虚拟地址空间,该虚拟地址空间不受实际物理内存的支持.当程序尝试访问此空间时,操作系统将尝试分配物理内存并将其映射到相应的地址,以便程序可以继续.如果此尝试失败,则程序可能被OS杀死.新的可用内存现在可供其他可能需要它的程序使用.
• 两个短内存块被映射到新的虚拟地址,使得它们在虚拟存储器空间中形成一个长的连续块.请记住,通常存在比物理内存更多的虚拟内存地址,并且通常很容易找到未分配的范围.通常,只有当所讨论的内存块很大时才会实现此方案.