该翻译选自文献Dynamic Storage Allocation:A Survey and Critical Review里的第三节
三．分配器的分类
分配器通常是由他们使用并记录内存区域是空闲的机制和合并相邻的空闲块使其成为更大的空闲块（合并）进行分类。 同样重要的是方法和战略的影响，也就是说，无论是分配器是否适当利用了真正的请求流的规律。 在本节中，我们调查内存分配的方法问题和机制; 因为延迟的合并可以被添加到任何分配器，在介绍完大体的分配器机制后，在第3.11节进行讨论。
3.1分配器方法问题
我们认为必须明确几个重要的方法问题并且想要了解真正的分配器性能必须对他们进行解读：
- 内存重用的模式 .最近释放的自由块重用是否优先于旧的自由区域?内存区域的空闲块优先重复使用相同的大小（不确定类型）作为附近活动对象的对象？ 某些空闲块在一些区域内重用是否优先于该空闲块在其他区域（如优先重用空闲块朝向堆的一端）？
- 分割和合并 大空闲块分割成更小的块，以满足更小的对象的请求？ 相邻空闲块合并成较大的区域呢？ 是否可以所将有相邻的自由区域合并，或者在合并时做一些限制，因为它会简化操作？ 当合并是可能的，并且持续下去，或者是推迟避免不必要的合并和拆分在很短的时间内完成？
- 适合的 当一个特定大小的块被重复使用，优先使用大约相同大小的块还是其他许多不同大小的块？ 或许选择块的大小与其他一些有用的方法所要求的大小有关？
-分割的阈值 当将一个很大的块用来满足请求时，是否将它分割，然后剩余的作为重用？ 或者是将剩余未分配的割裂开，形成内部碎片，或为实现简单或作为一种方法牺牲内部碎片降低外部碎片？
所有这些问题可能会影响整体内存碎片，并且应该被视为方法，即使对于特定选择的原因是为了使机制（实现）简单或更快。 他们也可能对所在区域的产生影响; 例如，重用最近释放的块可以通过将重复使用的信息仍缓存在高速存储器，优先于存储器是为了不变而较长存储器增加的参考时间局部性。 （局部性超出了本文的范围，但它是一个重要的考虑因素。总的来说，我们相信, 有利于当前区域,最好的方法减少碎片，但我们不会在这详细讨论50）
3.2一些重要的底层机制
几种技术被用于不同的组合中使用的各种分配器，并能有助于使复杂的策略非常容易有效地实现.我们将描述是几个”基本”（高电平）的机制及一些非常底层的机制，这反过来落实方法。（不想深入了解的读者不妨略过这部分。）
头字段和队列。大多数分配器使用隐藏”头部“记录字段中的每个块内存储的有用信息。最常见的，块的大小被记录在首部。简化释放，在许多算法，因为大多数标准分配器接口（例如，标准C free（）程序）不需要的程序来传递释放的块在释放时的解除分配程序的大小。典型地，分配功能（例如，C的malloc（）存储器分配程序）仅通过请求大小，和分配器返回指向分配的块;free程序只传递该地址，并且它是由分配器如果必要的话所推断的大小（这可能在一些系统中是真实的具有强类型的系统。 ，其中对象的大小通常静态已知的。在这种情况下，编译器可以生成自动提供对象大小的释放程序代码。）其它信息同样可以存储在头部，比如块是不是在使用中，它的邻居关系，等等。 有关于存储的块的块信息，使得许多常见操作更为快捷。
头字段通常是一种机器字段; 在大多数现代机器，即4个8位字节，或32位。 （为方便起见，我们将假设字的大小是32位，除非另有说明。）在多数情况下，有足够的空间在一个机器字为存储大小字段加上两个或三个比特“标志”（布尔字段），这是因为大多数系统上所有基于堆的对象分配整词或双字地址边界,但大多数硬件字节寻址.51（这种约束通常是由编译器强加的，因为硬件问题使未对齐的数据慢甚至操作非法）。
这种队列意味着局部字不能被分配，请求字的非整数值舍入到最接近的字。 到字（或双字）的边界的舍入可确保一个块地址的低两个（或三个）位总是零。
头字段很方便，但它们消耗的空间 - 例如，每块一个字。 它是为块大小共同在许多现代系统进行平均的10个字的量级，给予或采取两种或这样的一个因素，因此，每头一个字可以由约10％增加内存使用情况，[BJW70，Ung86，ZG92 DDZ93，WJNB95]。
边界的标签。许多分配器实现一般合并使用边界标记一般合并(由于Knuth[Knu73])来支持自由领域的合并。每个内存块都有一个头部和一个“页脚”字段,这两个记录块的大小和是否在使用。（页脚，顾名思义，是在块内的隐藏字段，在从头部相对的端部）当一个块被释放，存储器的前一块的页脚被检查，看它是否是自由;同样地，下列块的头部被检查邻近自由区域被合并，以形成较大的自由块。
页眉和页脚的开销可能是大约具有约十个字的平均对象大小，例如，一个字的报头占用10％的开销和一个字页脚占用另外10％开销。
幸运的是，有一个简单的优化，能够避免页脚开销.52注意，当一个块在使用（持有活动对象），页脚需要的是用于合并的存储标志位是非可用。 当该块是空闲时，才需要大小字段，以便它的报头可以用于合并 。 因此，大小字段可以取出的块的最后一个字的存储器，当块被分配，它可以用来保持对象的一部分; 当对象被释放，大小字段可以从报头插入到所述页脚被复制，因为该空间不再需要保持对象的一部分。所需要的单位表示块是否在使用中可以从以下块的头部字段被读取而不会不适当地限制大小字段的范围内。53
块中的链接领域。对于使用空闲的列表或索引树来跟踪空闲块的分配器，列表或树节点通常嵌入在空闲块本身。 由于只有空闲块记录，并且由于其空间，否则将被浪费，它通常被认为是合理的使用“空”的块内的空间来容纳指针链接在一起。空间索引结构因此“自由”（几乎） 。
许多系统使用双向链接线性列表，以取出的空闲区域的一个“上一个”和“下一个”指针。 这支持快速合并; 当对象被合并到一起，它们中的至少一个必须从链表中移除使得所得块将只出现在列表中一次。 其指向的前身和块的继任者都能够快速地从列表中删除该块，通过调整这些对象的“下一个”和“上一个”指针跳过删除对象。
一些其他分配器使用树，空间为“左子树”和“右子树”（以及可能的“父节点”）取出的空闲区域的指针。
假设只需要在分配块的报头字段，有效对象大小是一，二或三字对象。 如果许多目标是只有一个或两个词长和两个是相当普遍的，显然空间可能被浪费。
查找表。有些分配器大小的范围类似地，而不是索引可以通过确切大小空闲块内处理块，它们将大致相同大小的块一起。 块大小范围也可以是合并机制重要。 对于2的幂次方经常使用，因为它很容易使用的大小的二进制表示来找出哪些幂次方落入该范围。 使用幂的二次方比较粗略，但是，可以有缺点，我们将在后面讨论。
其他功能（如Fibonacci序列）可以是更有益的，但它们在计算运行时消耗资源更多。 一种简单和有效的解决方案是使用一个查找表，这是一个简单的阵列，由大小，其值范围的数目的索引。 要查找其范围大小分为，你只需索引到数组并获取存储在那里的值。 这种技术简单，速度非常快。
如果用于索引到表中的值是可能很大，然而，查找表本身也可能是太大了。 这通常是通过使用查找表的以下一些阈值（见下文）避免。
特殊处理的小对象。在大多数系统中，越来越多的小对象是比大的对象要优先。 因此，通常值得特殊处理的小对象，在某种意义上或另一种。 这通常可以通过具有分配器检查，看是否大小比较小来完成，如果是这样，使用小的值的优化技术; 为较大的值，其可以使用较慢的技术。
这一原则的一个应用是用于小对象快速分配技术，以及路线节省空间的技术。 另一种方法是使用较小对象的快速查表技术和计算速度较慢线路，因此查找表不占用太多的空间。 在这种情况下，考虑的是，这是很困难的方案，以在短期内使用大量的大型对象的时间，它通常必须用它做什么分配的空间，例如，初始化分配的对象领域，做一些更多的，至少他们的一些价值观。 对于一些中等对象大小和以上，分配的可能的频率很低，以致一些额外的开销并不显著。 （反例是可能的，当然，但我们相信，它们是罕见的。）这里的基本思想是确保所用的时间分配的块是相对于在其上保存的数据的计算小。
特殊处理堆的结束块。分配器分配内存要求的程序，但分配程序本身必须从某处获取内存。 在现代系统中最常见的情况是，堆占据一个范围，虚拟地址和扩展”向上“，通过地址空间。要申请更多的（虚拟）内存，系统调用，如UNIX BRK（）54调用用来请求存储被映射到的地址空间区域，这样它可以被用来容纳数据.55典型地，该分配器保持一个”高位标记“该分割存储器到由存储背靠部和一部分不是。
（在固定的存储系统，如一些非虚拟内存系统，许多分配器保持类似的高水位标记为自己的目的，以跟踪哪些内存部分正在使用中，哪一部分是一个大的连续的可用空间。）
我们一般会假设一个分页虚拟内存在使用中。 在这种情况下，其取得多个存储器系统调用获得的页数一些积分数，（例如，4KB，8KB，12KB或16KB具有4KB页的机器上）。如果一个较大的块被请求时，一个较大的请求（如必要时多页）制成。
通常，分配器请求存储器从操作系统时，它不能以其他方式满足存储器请求，但它实际上只需要的存储器来满足请求（例如，10个字）量小。 这就提出了与由操作系统返回的存储器的其余部分完成的问题。
虽然这似乎是一个微不足道的事簿记，看来这个内存结束块“的治疗可能有某些情况下显著方法的后果。（我们将回到这个问题在3.5节）。
3.3基本机制
现在我们将给出分配器的相对传统的分类，主要基于机制，但前进的道路上我们将指出方法问题，以及替代机制，可以实现类似的方法。 （我们希望能有一个基于策略的分类，而是战略问题，以便了解甚少，他们将提供很少的结构。因此，我们的分类大致相似，一些以前的（尤其是斯坦迪什的[Sta80]），但更完整。）
我们讨论基本的分配机制是：
-顺序适配，包括第一次配合，接下来的配合，最适合，和最差的配合，
-空闲链表分离，包括简单的隔离存储和隔离配合，
-伙伴系统，包括传统的二进制加权，并斐波纳契死党，和双哥们，
-索引适配，其中使用结构化的索引来实现所期望的配合方法
-位图适配，这是一种特殊类型的索引适合的
这部分介绍顺序适配部分，下面是出现有特别重要的，许多基本的方法问题，以及方法讨论适用于许多不同的机制。
描述这些基本的分配程序后，我们将讨论适用于所有的延时合并技术。
3.4顺序适配
几种经典的分配算法是基于具有存储器的所有空闲块的一个线性表。 （名单往往是双向链接和/或循环链接。）通常情况下，连续的配合算法使用Knuth的边界标签技术，以及双向链表，以合并简单，快捷。
在考虑连续配合，这可能是最重要的是保持战略和方法问题的初衷。 经典的线性表的实现可能无法很好地扩展到大的堆，在时间成本方面; 作为空闲块的数量的增加，搜索列表中的时间可能变得不可接受。56更有效的和可扩展的技术是可用的，使用全部或部分有序的树，或偏析配合（参见第3.6节）。57
最佳适配。一个最合适的顺序分配适合的搜索空闲列表，找到最小的空闲块大到足以满足要求。 这里的基本策略是通过确保片段尽可能小到的浪费的空间量最小化。 这个策略可能适得其反在实践中，如果配合是太好，但并不完美，在这种情况下，大部分的每个块的将被使用，其余的将是非常小的，也许无法使用。58
在一般情况下，最佳拟合搜索是详尽无遗的，虽然当一个完美的结合被发现它可能会停止。 这穷举搜索意味着顺序最适合的搜索不能很好地扩展到许多空闲块大的堆。 （因此，最合适的方法更好地实现通常使用索引的配合或配合隔离机制，后面介绍。）
最佳匹配通常表现出相当不错的内存使用情况（使用合成和真正的踪迹研究）。 各种可伸缩的实现已经使用平衡二叉树，自调节的树木，及其分离的配合（稍后讨论）构建的。
最佳拟合的最坏情况下的性能差，其内存使用成比例分配的数据量的乘积的最大和最小对象大小之间的比率（即，Mn）的 [Rob77]。 这似乎没有在实践中发生的，或至少不常用。
首先契合。 首先适配简单地搜索从开始的列表中，并使用所述第一空闲块足够大，以满足请求。 如果块大于必需的，这是分裂的，其余的就是把空闲列表上。
与顺序的首先适配的一个问题是靠近列表的开头的更大的块一般会被第一个分割，而其余的片段产生具有很多小块附近的列表的开头。 这些“碎片”可以提高搜索时间，因为很多小空闲块积累，搜索必须走过去的每次请求较大的块时他们。经典（线性），因此第一个适合的扩展小，其中许多对象分配和许多系统不同大小的空闲块堆积。
与最佳拟合，但是，首先适配更加可扩展实现是
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[152781]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
课题毕业论文、外文翻译、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
