网站进入百度沙盒,包含导航栏至少包含三个布局,seo公司后付费,零食网站推广策划书在C语言中我们会使用malloc来动态地分配内存#xff0c;这样做的一个主要理由是有些数据结构的大小只有在运行时才能确定。例如#xff0c;如果你正在编写一个程序#xff0c;需要用户输入一些数据#xff0c;但你不知道用户会输入多少数据#xff0c;那么你就需要使用动态…在C语言中我们会使用malloc来动态地分配内存这样做的一个主要理由是有些数据结构的大小只有在运行时才能确定。例如如果你正在编写一个程序需要用户输入一些数据但你不知道用户会输入多少数据那么你就需要使用动态内存分配。而堆是一种用于动态内存分配的数据结构当程序员使用 malloc 或其他动态内存分配函数请求内存时这些函数会从堆中分配内存。堆是由动态内存分配器管理的分为 显式分配器应用程序会分配和释放空间。例如在C语言中我们使用 malloc 来分配内存然后在不再需要的时候使用 free 来释放内存。这种分配器需要程序员明确地管理内存。 隐式分配器应用程序会分配但不会释放空间。例如在Java语言中我们使用 new 来分配内存但不需要也不能明确地释放内存。Java 有垃圾回收机制Garbage Collection它会自动管理和回收不再使用的内存。
说个题外话其实这里malloc是在虚拟内存空间中的堆区域分配内存关于虚拟内存后面再写这里可以就小提一下。
下图是一个简单的动态内存分配的顺序假设每一个块大小是8 byte这个分配顺序展示了我们在堆中分配和释放的过程。图中的alignment意思是例如在64位系统上必须满足16字节x86-64对齐图中箭头这里如果不空那一小块开始位置是72并不是16的倍数而再8就是80满足16字节对齐了。
一般为了让下一个块可以满足alignment前一个块都会计算好然后占据合适大小的空间因此图中的那个白色块应该是属于前一个已分配块的只不过它没有存任何东西属于是内部碎片化。这里箭头处画成白色的意思就是它没有存数据但它是已经被分配了的下面的内容会再次讲到这一点。 上面的例子看似很简单但其实也很低效因为我们无法控制和预测malloc每次请求的大小分配器必须在第一时间从现有的free块中找到合适的包括大小足够、满足alignment条件等这样就会导致整个堆的利用率不高比如有很多小的free块也叫碎片Fragmentation被分割出来却没法被使用。提到利用率一般来说我们使用吞吐量Throughput以及利用率Utilization来描述动态内存分配器的性能。这两个目标往往是相互冲突的。
吞吐量是每单位时间内完成的请求数量。例如如果在10秒内完成了5000次 malloc 调用和5000次 free 调用那么吞吐量就是1000次操作/秒。利用率是另一个关键的性能目标它衡量了分配内存即正在使用的内存占总内存的比例。
刚刚提到了碎片碎片化其实就是导致利用率utilization不高的原因内存碎片化的两种主要形式有内部碎片化和外部碎片化。这两种碎片化都会导致内存利用率低下。 内部碎片化Internal Fragmentation 当给定的内存块的有效负载payload小于块的大小时就会发生内部碎片化。这种碎片化发生在内存块的内部。当我们为一个小的内存请求分配一个大块的内存时分配出的内存块中的剩余部分就会形成内部碎片化。这些未使用的内存位于已分配的内存块内部因此称为内部碎片化。为什么分配的内存大小会比请求的大小大呢因为许多内存管理系统采用固定大小的块来分配内存。举个例子假设你有一个内存管理系统它总是分配4KB的内存块。如果一个程序请求1KB的内存系统会分配一个4KB的块但只有1KB被使用剩下的3KB就成了内部碎片。后面要讲的header和footer其实就会导致内部碎片化。 外部碎片化External Fragmentation 当存在足够的总体堆内存但没有单个空闲块足够大时就会发生外部碎片化。这种碎片化发生在内存块的外部。当内存中的空闲空间被分割成小块时这些小块可能无法满足大的内存请求即使它们的总和足够大。这些未使用的内存块位于已分配的内存块之间也就是外部因此称为外部碎片化。当然如果有一个足够小的内存请求那么之前形成的外部碎片也就是一些小的、分散的空闲内存块也是有可能被利用起来的。 内存管理器都要考虑的基本问题
上面讲了衡量内存管理器效率的指标除了这些外内存管理器还有很多最基本的功能和细节要考虑。比如给出一个地址要free掉怎么知道这个块的大小在分配和释放的过程中如何跟踪和维护空闲块们假如有多个合适的空闲块选择哪一个等。
使用header来存储内存块的大小
要知道各个块的大小可以为每个分配的块额外使用一个单词word也叫做header。这个header里存储记录块的大小以及一些其他信息比如当前块是否是已分配或者free等。这种方法的优点是简单、易于实现。但是缺点是因为每个分配的块都包含了一个固定大小的头部会额外占用空间导致内部碎片化。 在上图中每个块大小是8 byte。可以看到虽然我们malloc需要分配32byte但是由于有一个header以及alignment实际整个块的大小来到了48 byte。这里的alignment是为了让下一个块的地址符合要求要想让每个块都符合16 byte的alignment只需要让每个块的整体大小都是16的倍数即可。这里需要32header的840 byte所以需要再补个8来到48才是16的倍数这就是为什么有那一个大小为8的alignment块。这里的alignment依然属于内部碎片因为它属于这个被分配的块。
跟踪空闲块的三种方法重点
方法一隐式空闲列表 Implicit list 隐式空闲链表其实就是把heap分成一个个线性相连的块。上图中灰色部分就是已分配的白色部分是未分配的。每一个块都有一个header用来存放着个块的大小以及是否被分配。由于我们的块都是align对齐的特性一般来说是以16 bytes 来align那么16的倍数二进制的后四位一定都是0所以地址的低4位一定是0我们就可以用低位存储“是否被分配”这一信息。当读取header中的大小时把低位屏蔽掉就好。
Implicit list 中的 split
当我们准备分配内存空间时我们只能是从前向后按顺序遍历查找如果找到了一个空闲块的大小大于我们需要的内存大小为了避免浪费空间往往会进行split比如下面将64 bytes到分割成两个32 bytes大小的块。 Implicit list 中的 coalesce
接着上面的步骤如果我们马上又把刚刚分配的32 bytes 释放了那么我们就会有两个连续的32 bytes 大小的free block这不是我们想得到的我们还需要把它变成一个大小的64 bytes的块这种合二为一的过程就是coalesce。 上图就是一个部分正确coalesce的示例这种情况下我们free了中间的块然后因为它后面还跟着一个free块所以我们可以加上它后面块的大小得到321648。可是前面还有一个空闲块我们似乎就没法合并了因为我们很难知道前面块的大小无法定位到前面块的header。因此我们需要引入footer。 footer和header的内容完全一样这样我们通过一个header往前一位就能得到前面块的footer从而知道前面块的大小然后进行相关的coalesce。footer和header一般是必须的因此上面的这幅图其实才是一个最标准的implicit list。
方法二显式空闲列表 Explicit list
隐士空闲链表其实就是整个heap我们要找空闲块还得遍历一些已分配的块实在是太慢了。显式空闲列表则只管理空闲块用指针将空闲块们连起来做成一个双向链表。 我们直接在原来payload的部分放prev和next指针因为空闲块的payload必然都是空的所以在它空闲的时候用来存储指针没什么毛病。因此一个标准的显式空闲列表中一个free block的最小大小是32 bytesheaderprevnextfooter 各 8 bytes。
Explicit list 因为只管理空闲块所以效率大大提升了但是每次分配和释放内存包括coalesce时都要管理好这个双向链表涉及到链表的插入删除操作等实现起来是复杂一些但总体值得
当然这里我们使用了两个指针如果空闲块的最小大小这个由设计者决定足够我们在payload里放指针那么其实对空间没啥影响但如果payload大小都不够两个指针也就是16 bytes的话双指针就不能使用了可以考虑只保留一个指针做单向链表。 上面是explicit list 进行分配的例子当我们找到一个大小比所分配大小大的块后能split还是得split然后插入到列表当中。所以对于我们的双向链表来说这里实际上是“先删除了一个大的块然后又插入回了一个小的块”。
方法三分隔空闲列表 Segregated List (Seglist) 看图你就明白啦其实就是在 explicit list 基础上多弄了几个列表划分依据就是根据大小这样一来对于需要分配/释放的块我们只需要从相关大小的列表里找再一次加快了搜索的效率。
选择空闲块的四种策略
不管我们使用上面哪种空闲块管理方式在我们试图搜寻和分配空闲块时面对多个不同的满足条件的空闲块总会面临一些通用的选择困境。下面是一些通用的参考思想和选择方案。
首次适应First Fit 这个很简单就从内存的开始处搜索选择第一个足够大的空闲块进行分配。这种策略的优点是简单且速度较快但因为太无脑了可能会在内存的前部产生很多小的碎片。下一次适应Next Fit 类似于首次适应但是从上次搜索结束的地方开始搜索而非每次都从头开始。这种策略可以避免重新扫描无用的块通常会比首次适应稍快。举例来说假设我们有一个内存块列表大部分块的大小都接近只有一小部分块的大小远大于其他块。如果我们有一系列的大请求那在 Next Fit 中我们在找到大块并分配之后就可以记住这个位置那么下一次又有一个大请求时我们可以直接从这个位置开始扫描避免了重新扫描前面那些小块。但是这种场景也太苛刻了你又不知道下一个请求是多大的所以这个next fit看看了解就好。某些研究表明使用下一次适应可能会导致更严重的内存碎片化。最佳适应Best Fit 顾名思义遍历所有的空闲块然后在所有的空闲块中选择一个能够满足需求且剩余空间最小的块进行分配。这种策略可以最小化每次分配后的剩余空间从而减少内存碎片但是搜索的过程可能会比首次适应和下一次适应更慢。在极端情况下如果我们在分隔空闲列表 Segregated List (Seglist) 中为每个块都设立一个自己的大小类别那么这就等同于最佳适应Best Fit 。因为我们总是能找到和需求完全匹配的块不会有内存浪费。更好适应Better Fit Better Fit算法是First Fit和Best Fit的折中方案。在找到第一个足够大的空闲块后不立即进行分配而是继续向后搜索一定数量的空闲块。然后从这些块中选择最小的足够大的块进行分配。这种策略旨在在快速分配和减少空间浪费之间找到一种平衡但可能会略微增加搜索的时间和复杂度。 选择哪种策略取决于特定应用的需求。例如如果内存分配请求不频繁可以选择最佳适应以最小化碎片如果内存分配请求非常频繁那么首次适应或下一次适应可能更合适因为这两种策略的查找速度较快。
小结
以上大概是动态内存分配这块的重点内容要想更加深入的理解推荐去做大名鼎鼎的 malloc lab我做到满分还是花了很多时间要想提高分配器的utilization以及throughput需要使用segregate list去掉footer此时可以用header后面的倒数第二位来存储前一个块的是否被分配信息以及减少minimum block size再去掉prev指针等技巧还是比较有趣的
