（计算机科学与技术专业论文）可控动态内存分配器的研究与开发.pdf

乞s 己己譬【 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：么缮导师签名生垄日期：型垒年互月尘日 ii i i i ii i i i h i 9 5 3 硕士学位论文摘要 摘要 动态内存分配器是操作系统最基本的组成部分，在进程的执行过 程中为进程提供动态的内存区域。进程能够根据需要向动态内存分配 器申请新的内存区域或者是释放已经分配了的内存区域。动态内存分 配器也在高级语言程序设计中占有重要作用，其设计优劣直接关系到 进程的速度和内存空间使用效率。 本文设计了一个基于类u n i x 操作系统的用户态下具有可控性 的动态内存分配器z t m a l l o c 。z t m a l l o c 根据用户进程所申请的内 存空间大小使用三种不同的分配模式实现，即小型、中型和大型模式。 小型模式下，z t m a l l o c 对内存块进行两次划分，第一次划分成为 大小相等的内存行，第二次将行划分成大小相等的内存区域，然后选 择空闲区域分配给用户进程。 中型模式下，z t m a l l o c 使用伙伴内存系统，对内存块进行划分广 然后选择合适的区域进行分配。 大型模式下，z t m a l l o c 取所需内存空间大小向上向内存块大小的 整数倍取整的结果作为用户进程所需的内存区域。 为了提高性能，z t m a l l o c 还使用了包括多线程优化、快速缓冲存 储器优化、虚拟内存系统优化在内的诸多优化方式。 本文对于z t m a l l o c 的性能进行了分析和测试，测试结果表明， z t m a l l o c 性能良好，具有一定的竞争力。 关键词动态内存分配，可控性，虚拟内存系统，内存碎片 硕士学位论文 a b s t r a c t d y n a m i cm e m o r ya l l o c a t o r s a lef u n d a m e n t a lp a r t so fo p e r a t i n g s y s t e m sw h i c hp r o v i d ed y n a m i cm e m o r yr e g i o n st op r o c e s s e s p r o c e s s e s r e q u e s to rr e l e a s em e m o r yr e g i o n sf r o md y n a m i cm e m o r ya l l o c a t o r s w h e nn e e d e d d y n a m i cm e m o r ya l l o c a t o r sa l s op l a yav e r yi m p o r t a n tr o l e i nt h eh i g h l e v e lp r o g r a m m i n gl a n g u a g ed o m a i na n dd e t e r m i n et h es p e e d o f p r o c e s s e sa n dt h eu t i l i z a t i o no fm e m o r ys p a c e t h i st h e s i sd e s i g n e dac o n t r o l l a b l ed y n a m i cm e m o r ya l l o c a t o rb a s e d o nu n i x l i k eo p e r a t i n gs y s t e m st h a tr h a si nu s e r - m o d e ，w h i c hi sc a l l e d z t m a l l o c t h r e ed i f f e r e n tm o d e sa l ei n t r o d u c e dt oc o p ew i t ht h er e q u e s t s a c c o r d i n gt ot h ea m o u n to ft h es p a c er e q u e s t e d ，w h i c ha l es m a l lm o d e ， m e d i u mm o d e ，a n dl a r g em o d e 一 ， i nt h es m a l lm o d e ，z t m a l l o cs p l i t sm e m o r yb l o c k st w i c e ，t h a ti s ， s p l i t i n gt h em e m o r yb l o c k si n t o l i n e s f o rt h ef i r s tt i m e ，a n dt h e n t o m e m o r yr e g i o n so f t h es a m es i z e s a tl a s t ，z t m a l l o cs e l e c t sas u i t a b l ef r e e r e g i o nf o rt h e u s e rp r o c e s s i nt h em e d i u mm o d e ，z t m a l l o cu s e sb u d d ys y s t e m st os p l i tm e m o r y b l o c k s ，a n dt h e ns e l e c t so n et oa l l o c a t e i nt h el a r g em o d e ，z t m a l l o cr o u n d st h er e q u e s t e ds i z eu pt om u l t i p l e t i m e so fm e m o r yc h u n k s ，a n da l l o c a t eam e m o r ya r e ao ft h a ts i z ef o rt h e u s e rp r o c e s s v a r i a n to fm e a n si s e m p l o y e db y z t m a l l o ct o i m p r o v e t h e p e r f o r m a n c e i n c l u d i n g m u l t i - t h r e a d i n g o p t i m i z a t i o n s ， c a c h e o p t i m i z a t i o n s ，a n dv i r t u a lm e m o r ys y s t e mo p t i m i z a t i o n s ，e t c t h i st h e s i sa l s oa n a l y z e da n dm e a s u r e dt h ep e r f o r m a n c eo fz t m a l l o c ， - 一一 a n ds h o w e dt h ew e l lb e h a v i o ra n dc o m p e t i t i v ep o w e ro fi t k e y w o r d sd y n a m i cm e m o r ya l l o c a t i o n ，c o n t r o l l a b i l i t y , v i r t u a lm e m o r y s y s t e m ，f r a g m e n t a t i o n i l 目录 i i i i i i 1 1 。2 一3 。4 5 5 。5 。7 一7 l o 1 0 2 4 面临的问题1 l 2 4 1 内存碎片1 l 2 4 2 数据对齐和内存访问颗粒度1 3 2 4 3多线程1 4 2 4 4内存区域之间的依存与局部性1 4 2 5 计算机体系结构的影响1 5 2 5 1 存储空间的访问方式增强了局部性j 。1 5 2 5 2 内存访问的一致性1 5 2 5 3c p u 与内存之间的速度差距1 6 2 5 4 内存发展趋势1 7 2 6 操作系统的影响1 8 2 7 本章小结1 9 第三章 内存分配器的设计2 0 3 1 接口2 0 3 2 内存的分配模式2 0 3 3 内存分配。2 l 3 3 1 小型模式及其分配2 2 3 3 2 中型模式及其分配2 6 3 3 3 大型模式及其分配3l 3 4 内存释放3 4 3 4 1 小型模式下的内存释放3 5 3 4 2中型模式下的内存释放3 5 3 4 3 大型模式下的内存释放3 8 i l l 硕士学位论文 目录 3 5 内存区域大小的改变3 9 3 6 本章小结一4 0 第四章实际应用和性能测试4 l 4 1c 语言和c + + 语言环境中的使用一4 l 4 2 优化4 l 4 2 1多线程的优化一4 2 4 2 2 空间分配时的内存地址对齐4 2 4 2 3 快速缓冲存储器的优化4 2 4 2 4 虚拟内存系统的优化4 3 4 2 5 安全性4 3 4 3 内存空间生存周期控制4 3 4 4 内存占用率分析4 4 4 5 性能测试4 4 4 5 1 速度测试4 5 4 5 2 不同线程数目下的速度测试4 5 4 ：5 3 + 内存利用率测试j _ ：j ：- ：4 7 4 6 内存布局图4 7 4 7 本章小结。4 8 第五章总结与展望4 9 5 1 总结4 9 5 2 展望。：j 4 9 参考文献。51 致谢5 4 攻读学位期间主要的研究成果_ ：i 5 5 i v 硕士学位论文第一章绪论 1 1课题来源和意义 第一章绪论 除了少数简单的程序，所有的程序都需要动态地分配内存。现代程序设计语 言对于内存空间的管理分为三种方式：自动内存分配、禁止内存分配和手动内存 分配【l 】。例如c 语言在进行内存管理的时候使用静态和自动两种方式。静态存在 的变量主要被放置在内存的固定地址，并且在整个程序的生命周期都存在；自动 变量被放置在内存的栈之上，随着函数的调用和返回而产生和消亡。分配给静态 存在的变量的内存空间大小的值是在程序编译的时候就已知的常量【2 】【3 1 。 内存空间的存在时间不管是对于静态变量还是自动变量都是一个需要考虑 的问题。自动分配的数据不能在多次的函数调用后仍然保持原样，但是静态数据 在整个进程运行的生命周期内都存在，甚至没有被使用时也是一直存在【4 1 。如果 所需的内存空间大小只有到了运行时刻才会知道，那么就不能使用固定内存空间 来表示。在很多情况下，程序员需要更加灵活地控制内存的分配、避免这些限制， 而动态内存分配就可以完全满足要求。在动态内存分配情况之下，进程需要使用 相应的系统调用来进行内存管理。这种方式需要进程显式地操作，因而具有一定 的复杂性。一一 c 语言标准中定义了进行动态内存分配和释放的函数：m a l l o c 、c a l l o c 、r e a l l o c 、 f r e e 。这四个函数对从系统申请来的内存空间进行管理，提高空间利用率。函数 m a l l o c 就是用来进行空间分配的内存分配器，进程通过m a l l o c 函数返回值来获 得内存空间的地址。当进程不再需要使用已分配的空间的时候，指针则被传递给 f r e e 来进行空间释放。 某些开发平台提供了其它的函数来进行内存的分配和释放，但是并不是在堆 中进行，而是在栈中进行，如许多类u n i x 操作系统都提供的a l l o c a 函数，当函 数调用过程结束返回后这些空间将被自动的释放掉【5 】。然而c 9 9 支持变长数组， 因此，就不必通过使用内存分配器在栈中分配空间了。 所有的编译环境都将这些内存管理函数实现为用户态的库函数，而不是系统 调用，所以m a l l o c 函数必须通过系统调用来向操作系统申请内存，例如在类u n i x 操作系统上面，m a l l o c 通过系统调用b r k 和m m a p 来申请堆空间【6 】【7 】【8 】【9 】。这些系 统调用都是以页为单位，颗粒度大，缺乏灵活性，所以进程就需要对于所申请来 的空间进行再次划分以提高利用率。每次调用m a l l o c ，都会使之在已经申请的堆 空间中寻找指定大小的合适的空闲内存区域并返回给用户进程，如果找不到指定 大小的空闲内存区域，则m a l l o c 会通过系统调用b r k 或m m a p 申请更多的内存。 硕士学位论文 第一章绪论 但是c 语言的m a l l o c 存在诸多不足： 首先，它的接口简单，只需要指定需要分配的内存大小，这样能够简化其使 用方式，但同时也导致程序员难以控制其运行细节。 其次，m a l l o c 使用一定的算法在非连续的空闲存储空间中寻找大小合适的返 回给用户进程。毫无疑问，每种算法都有其最适应的环境，但是这些算法都是已 经在分配器建立时就已经固定在其中，用户无法根据自己的需要进行修改。 此外，现代计算机的存储器发展趋势是容量增长远大于速度的增长，对于内 存分配算法同样是速度的重要性大于容量的重要性。因此，在内存分配时，用户 希望适当的调整在容量与速度中间的折衷，而m a l l o c 的参数太少，不能够满足 此种需求。 固定分配策略的内存分配器由于不能定制其行为，从而使其难以满足多种不 同场合的需要。在对于内存分配器某一方面要求特别高的领域，需要有更强可控 性的分配器来满足需要。 1 2现有分配器实现 目前已经存在许多的动态内存分配器的实现。有些操作系统已经提供了自己 的实现，有些则仅仅提供了最基本的内存分配的系统调用，需要用户自行安装内 存分配器。更多的操作系统则是提供了自己的实现，同时允许用户安装其它的替 代品。几个比较典型的实现包括： 1 l i b m a l l o c ， l i b m a l l o c 提供了与i s oc 内存分配函数相匹配的接口。此库包括m a l l o p t 工具，进程可以设置参数来控制内存的分配的具体行为细节。此外，还包括 m a u i n f o ，提供了对于每次内存分配的统计功能。l i b m a l l o c 主要侧重在于与i s oc 的动态内存分配函数相兼容，这一点与z t m a l l o c 不同。 2 v m a l l o c v m a l l o c 允许进程依照不同的技术来分配不同的内存空间。除了函数v m a l l o c 之外，该库也提供了对于i s oc 内存分配函数的模拟功能【8 】【1 0 1 。v m a u o c 有比 z t m a l l o c 更强的可定制性，不过分配模式单一。 3 q u i c k - f i t 由于历史原因，标准的m a l l o c 算法要么使用最佳匹配，要么使用首次匹配 内存分配策略。q u i c k f i t 比以上的任何一种都要快，但是需要占用更多的内存空 间。q u i c k - f i t 使用的算法基于将内存分割成许多不同大小的缓冲，然后维护这些 根据大小链接在不同空闲块链上的没有使用的缓冲【l l 】。q u i c k f i t 使用单一的分配 模式，而不是z t m a l l o c 的多种模式。 2 硕士学位论文 第一章绪论 4 a l l o c a a l l o c a 有着与m a l l o e 一样的调用方式，但是，它不是将内存在堆中进行划 分，内存是在当前函数的栈帧中分配的。好处就在于不需要进行内存的释放操作， 当函数调用结束后，自然就被释放了。然而缺点也显而易见，并不是所有的操作 系统都支持在函数调用以后改变栈的大小，从而也不能支持a l l o c a 函数，不过仍 然有许多软件使用该函数。a l l o c a 的内存分配在栈中进行，而不是像z t m a l l o c 一 样在堆中进行。 5 h o a r dm a l l o c 这个分配器只使用了m m a p ，但是以6 4 k b 为单位来进行内存管理。堆被从 逻辑上分为一个单独的全局堆和一些小的处理器独占的堆。此外，每个线程都还 有一个单独的缓冲，能够包含一定量的内存单元。分配器从线程独有的缓冲或者 是处理器独有的缓冲分配空间，从而使得这些缓冲空间能够被其它进程所使用。 这个分配器能够将内存碎片保留到很低的水平，同时达到近乎与线程数目成比例 的性能增长【1 2 】。与z t m a l l o c 相比，h o a r dm a u o c 的可定制性略差。 6 j e m a u o c 从7 0 版开始，f r e e b s d 采用了新的动态内存分配器，称为i e m a l l o c ，由j a s o n e v a n s 所编写。这个新的分配器能够动态地适应多线程环境。为了避免锁竞争， j e m a l l o c 对于每个c p u 使用了独立的记录分配信息的数据结构。与z t m a l l o c 相比， j e m a u o c 在多线程方面做了更多的优化工作。 1 3课题研究内容 本课题旨在设计一种用于类u n i x 操作系统的内存分配器咄a u o c ，要 求具有较快的分配和回收速度，以及高可控性，可以满足对内存分配有着高要求 的进程的需要，使程序员能够更好的根据程序调整参数和在不同的参数之间进行 的折衷和取舍。 主要的研究内容包括： 一 一 z t m a l l o c 在进行初始化和内存分配时所使用的内存空间布局及空闲内存区 域的选择算法； z t m a u o c 通过提供给用户控制内存区域生存空间选择参数的方式来对空闲 内存区域的选择进行优化； z t m a u o c 在多线程、快速缓冲存储器的使用上的优化，以此进一步提高分配 器的性能。 硕士学位论文 第一章绪论 1 4论文结构安排 第一章介绍课题的背景、研究现状、研究意义和课题的研究内容。 第二章叙述动态内存分配的需求的产生，实现的基本原理，常见的使用技术， 以及动态内存分配器在设计过程中所要面临的主要问题：内存碎片，以及其它的 多线程、局部性等问题。还介绍了当前计算机体系结构和操作系统的发展对于内 存分配器设计的影响。 第三章描述动态内存分配器z t m a l l o c 的设计，包括其分配模式的划分，不同 的分配模式下的内存分配和回收的实现，以及已分配内存空间大小的改变的方 法。 第四章阐明z t m a l l o c 的实际使用方式，包括在c 和c + + 环境下的使用方式。 本章还对z t m a l l o c 进行了实际工作环境下的性能测试。 第五章总结本文主要内容，并且对于未来动态内存分配器的发展进行了展 ， 望。 一 4 硕士学位论文 第二章动态内存分配的原理与技术 第二章动态内存分配的原理与技术 2 1进程的虚拟地址空间 在使用虚拟内存系统的情况下，进程运行时所使用的内存空间不再是物理地 址空间，而是虚拟地址空间。大多数虚拟内存系统使用分页来实现【1 3 】【1 4 】。操作 系统将虚拟地址空间划分成许多大小相等的页，同时，操作系统也将物理内存划 分成同样大小相等的页。当进程需要使用虚拟地址空间时，操作系统就将所需空 间所在的页面换入空闲物理页面，如果找不到，则在物理内存中以某种算法选择 不需要的页面换出到辅存上，然后再将空间所在的页面放置在腾出的空闲空间之 中。进程的这种页面的换入换出通常是由被称为内存管理单元的硬件完成的。页 面之间的映射关系由页表来保存【1 5 】。 进程的虚拟地址空间没有完全利用，实际使用的虚拟地址空间大小由操作系 统根据实际的运行状况进行管理。进程也可以提出申请分配虚拟地址空间。不同 操作系统下，进程的虚拟地址空间各不相同，进程向操作系统申请动态内存的方 式也各不相刚川。 2 1 1u n i x 类操作系统的虚拟地址空间 在不启用物理地址扩展的情况下，3 2 位的操作系统所能够访问的最大物理 地址空间为4 g b 。在类u n i x 操作系统下，高地址的1 g b 用于操作系统本身， 低地址的3 g b 用于用户进程，如图2 1 所示。 内存的高地址区域的1 g b 的空间为内核使用，用于内核数据、常驻内存的 系统进程等。剩下的3 g b 用于用户进程。这也意味着整个进程在执行时，所有 代码、数据空间之和不能超过3 g b 。 从硬件层面上来讲，3 2 位地址只能访问4 g b 的物理内存。但是自从扩展至 3 6 位地址线之后，新的映射方式可以访问到更多的空间，i n t e l 称之为物理地址 扩展【1 7 1 1 引。 进程空间并不是一块整体，而是被分成许多段，每一段都有单独的用途【1 9 1 。 在操作系统里，虚拟内存地址除了用来映射可执行文件中各个段以外，还可以有 其它的作用。操作系统通过使用虚拟内存地址来对进程空间进行管理。进程中的 堆、栈在进程的虚拟空间中也是以虚拟内存地址的形式存在，在很多情况下，堆 和栈分别都有一个对应的虚拟内存地址。 5 硕士学位论文 第二章动态内存分配的原理与技术 l g b 3 g b 内核空间 栈 内存映射区域 t 移3 。 。砰j 鼍 + “端 堆 数据段 代码段 图2 - 1u n i x 类操作系统的进程虚拟地址空间 f l m n a b d e b u g _ r a n g d d e b u g 一女r d e b u g j l 畦 o k b u ga b b t e v d e b u gm f o d e b u ga 口j l 嚣 h b cn f 惜j _ n h s 曲 g o t 曲 g o t d t r di o c r 0 1 1 5 h i d a n 群cc s c e p t i 出k “f r a n 幢 i ha _ c 慨妯r r - b t o d a m t i m 峨一f t e e l b _ f n h o l ea b i - i a s e l f h c 撕 图2 - 2 应用程序映像与内存空间之间的映射关系 可执行文件最终要被操作系统装载运行，这个装载过程一般是通过虚拟内存 的页映射机制完成。在映射过程中，页是映射的最小单位。对于i n t e l 系列处理 器来说，默认的页的大小为4 k b 。也就是说，要将一段物理内存和进程的虚拟 地址空间之间建立映射关系，这段内存空间的长度必须是4 k b 的整数倍。由于 有着长度和起始地址的限制，对于可执行文件来说，它应该尽量的优化自己的空 间和地址的安排，以节省空间。进程的映像文件中每个段的长度都不相同，要将 每个段都映射到虚拟内存空间，最简单的办法就是每个段分别映射，而对于长度 6 硕士学位论文第二章动态内存分配的原理与技术 不足一个页的部分则占一整页。图2 2 表示了这种映射关系。 2 1 2w i n d o w s 操作系统的虚拟地址空间 在3 2 位的w i n d o w s 操作系统上，每个用户进程的默认地址空间有2 g b ，操 作系统使用另外2 g b 空间。用户进程占用2 g b 空间的内容包括应用程序的代码、 全局变量、每个线程的栈以及d l l 代码。操作系统占用的高2 g b 的空间包括系 统缓存、换页内存池、非换页内存池、进程页表、超空间、内核和执行体代码、 h a l 、引导驱动程序等【2 0 】【2 l 】，如图2 3 所示。 系统空问 用户空间 系统缓存 换页内存池 非换页内存池 进程页表 超空问 内核和执行体 h a l 引导驱动程序 应用程序代码 令局变量 每个线程的栈 d l l 代码 图2 - 3w i n d o w s 操作系统的进程虚拟地址空间 2 1 3 动态内存分配的原理 内存申请主要分为堆中的动态内存分配和栈中的动态内存分配两种。前者将 通过系统调用从操作系统申请堆空间。而后者则是通过移动栈顶指针来达到动态 内存分配的目的。 在堆中分配动态内存时，用户进程可以使用两种方式，即较旧的b r k 系统调 用和较新的m m a p 系统调用。 b r k 系统调用改变了堆顶指针，以此来改变分配给应用程序的空间大小。堆 顶指针通常被称为b r e a k ，即在进程未初始化数据段后面的第一个地址。但是这 种改变方式要求必须是连续内存空间，缺乏灵活性，并且会因为应用程序释放以 前分配的空间并且继续使用新分配的空间，从而造成空间中出现外部碎片，从而 降低了利用率。 与b r k 类似的还有一个s b r k 系统调用，它的作用就是将堆顶指针增加或者减 小一定的量，从而达到内存分配的目的。 7 硕士学位论文第二章动态内存分配的原理与技术 m m a p 系统调用所分配的空间不需要连续。应用程序在释放了以前的空间并 且继续使用新分配的空间的时候，尽管虚拟地址不再连续，但是并不影响到应用 程序的工作，也不会造成外部内存碎片，继而导致空间的浪费，提高了内存空间 的利用率。 带有内存管理单元的系统支持请求调页。当进程调用b r k 系统调用或者 m m a p 系统调用的时候，内核将更新该进程堆的内存空间。当进程尝试访问一个 虚拟地址的时候，该地址的页面尚未进入物理内存，即仍然在辅助存储器上，这 时就会产生一个异常，从而一个内存页面被分配到此进程。 很多程序在编译的时候并不能确定需要使用的内存空间大小，只有到了运行 的时候才能根据运行状态、输入数据来进行确定。那么就不能在编译的时候确定， 只能够在运行的时候动态的进行内存分配。 虽然分配给每个进程的虚拟空间大小都是一定的，但是其中用作堆空间的空 间大小大约只占到2 3 ，并且这个比例还要随着进程本身的不同有所差异。 已经分配的内存管理主要是通过一定的数据结构将已经分配的内存区域的 起始位置和大小记录下来，一般是通过链表或树来组织【2 2 1 。典型的分配器通过 使用链表跟踪在b s s 段结尾与b r e a k 指针之间的内存空间。链表中的每项包括一 个状态标志指示内存空间是否已经使用，指向下一个项的指针。在某些情况下， 还需要指向前一个项的指针，以此来增加内存分配和释放的速度。 当应用程序调用分配器进行内存分配的时候，分配器就会从头至尾遍历整个 链表。如果有足够大的空闲空间能够满足申请的需要的话，那么这个空闲空间的 首地址就会作为分配器函数的返回值返回给应用程序。 内存区域的选择算法是指那些将动态内存划分成为很多小区域的内存分配 算法，需要在已经存在的小区域中选择合适的小区域返回给进程，完成内存的分 配。常见的选择算法包括首次适应算法、循环首次适应算法、最佳适应算法、最 差适应算法【2 3 】【2 4 】【2 5 1 。 首次适应算法。在使用此种算法的时候，分配器会在所有空闲的空间中查找 能够满足分配请求的空闲空间，当找到第一个这样的空间的时候，就将它作为进 程所申请的空间返回。即使所找到的空闲空间的大小远远大于所需要的大小，也 继续进行分配。首次适应算法往往采用单向链表来进行空闲空间的记录，并且每 次查找都是从链表的头节点开始的，因此当内存量非常大的时候开销也会变得比 较大【2 5 】。 循环首次适应算法。该算法是首次适应算法的一种变种。循环首次适应算法 一般采用单向循环链表记录空闲空间信息，当新的内存分配请求到达之后，分配 器就从上次所查找的结束位置继续查找。 8 硕士学位论文第二章动态内存分配的原理与技术 最佳适应算法。这种算法会在所有空闲区域中找到大小能够满足分配请求的 最小的空闲内存区域，也就是最接近的空闲区域。这种算法产生的内部碎片较少， 但是外部碎片却会很多【2 5 1 。 最差适应算法。最差适应算法总是查找大小最大的空闲内存区域，然后划分 之后分配给用户进程。这种算法产生的内存碎片少，内存空间的利用率高。 表2 1 比较了以上几种分配算法优缺点。 图2 - 4 描绘了首次适应算法、最佳适应算法、循环首次适应算法之间的分配 效率的比较。由图中可以看出，在平均分配大小较小的时候，首次适应算法具有 明显的优势，最差适应算法的结果不理想。但是随着平均分配大小的增大，各种 分配算法的效率趋近一致。 表2 - 1 常见内存分配算法比较 8 0 7 5 7 0 图2 _ 4 各种常见分配算法之问的效率比较 9 鑫埒凝酲求 硕士学位论文 第二章动态内存分配的原理与技术 2 2高级语言中的动态内存分配 高级语言需要处理大量的高级数据类型，但是这往往只有在运行时根据程序 运行的具体情况来确定，因此几乎所有高级程序设计语言都需要使用动态内存分 配技术。在c 语言和高级汇编语言中，程序员需要使用m a u o e 和f r e e 函数来完 成内存分配，p a s c a l 语言提供了n e w 和d i s p o s e ，c + + 则提供了n e w 和d e l e t e 运算 符【2 7 】【2 8 】。其它的语言也提供了类似的方式。这些内存分配过程都有着以下共同 点： 1 它们能够让程序员指定所需要请求分配的内存空间的大小： 2 它们返回一个指向这个新分配的存储空间的指针； 3 它们都提供了将已经分配的内存空间返回给操作系统的工具。一旦这些 已经分配的空间都不再需要了，它们就能够将这些空间返回给操作系统 以供后面的内存分配之用。 硕士学位论文第二章动态内存分配的原理与技术 非常重要。 5 高兼容性 一个分配器需要能够与其他程序保持兼容，特别是遵循p o s i x 标准。好的 兼容性能够使得现有的程序不需要进行修改就能够很好的使用新的分配器。 6 高可移植性 分配器要遵循所有已知的对于对齐和寻址的限制。内存分配器要尽可能少的 依赖操作系统的某些特有的功能，例如特有的库函数、系统调用。同时对其它的 可选的有用的功能提供支持。 7 高效的错误检测能力 内存分配器需要提供检测错误的方法。某些错误可能会引起程序计算错误， 甚至导致用户数据丢失。内存分配器需要能够尽可能的检测到用户程序在使用内 存分配器时所产生的错误，例如覆盖已分配内存区域，重复释放已释放的区域等 等。 一般说来，占用最少的空间应当是内存分配器设计中的首要目标。不过，时 间与空间之间的折衷却很难确定。使用最差的对齐标准会使得分配器在两次不同 的分配之间保留一定的空闲空间，使得这两次分配能够尽可能的遵循计算机体系 的内存对齐要求。对于分配器的动态调整一方面能够提高分配器对于具体应用的 适应性，提高其工作效率，但是另一方面却会导致更多的间接层，也会导致跳转 的次数，进而严重的影响其效率。对于错误的检测将会限制分配器的适用范围。 例如，不管运行于何种平台，当前的分配器都会在内部处理分配大小的参数，将 其作为有符号的整数；同时将非正参数当作请求分配0 字节。很多用户都将这个 当作分配器的一个功能而不是一个设计缺陷。但是，实际上这是一个设计缺陷。 遵循其它分配器的某些特有的功能能够使得分配器的兼容性提高，但是这也 会导致灵活性和性能的降低。 2 4面临的问题 由于动态内存分配请求的不可预知性，动态内存分配器需要面对静态内存分 配所没有面临的新的难题。这些问题主要包括内存碎片、数据对齐和内存访问颗 粒度、多线程和局部性的问题。 2 4 1 内存碎片 内存碎片是指内存空间没有被有效地使用，因而导致了实际可使用内存空间 减少和应用程序性能下降。内存分配算法必须能够处理好内存碎片，这是整个分 配器的核心问题【2 9 j 。 硕士学位论文第二章动态内存分配的原理与技术 内存碎片可以分为两种情况：内部碎片和外部碎片。 当存储器的空间被分配，但是却不会被使用的时候，就会产生内部碎片，被 分配的内存空间利用率下降。虽然内部碎片会导致空间的浪费，但是这种浪费在 很多时候却能够带来效率上的提升和分配器结构的简化。“内部 指的是没有使 用的内存区域存在于已经分配的内存区域之内。 图2 5 描绘了这样的一种情况。用户进程申请3 k b 的空间，但操作系统在 进行虚拟地址空间的分配的时候以页面大小为单位，假定为4 k b ，于是操作系 统分配4 k b 的空间给了用户进程，最终导致多余的i k b 的空间被分配给用户进 程。但是这i k b 的空间永远不会被使用，形成了内部碎片。 3 k bl k b ， 、弋厂b 二二l i i 。 4 k b 图2 5 内部碎片 内部碎片很难被回收，通常最好的办法就是更改内存分配器的设计从而使得 分配器在分配内存的时候不会产生内部碎片，但是这也将带来效率上的降低。 外部碎片指空闲的内存空间被分割成了许多小块，这些小块太小，不能够满 足任何一次内存分配的请求，从而造成了浪费。 - 例如进程申请1 0 0 0 字节，但最大的连续空闲空间的大小只有3 0 0 字节。即 使有1 0 块3 0 0 字节的空闲空间，由于这些空闲空间相互间并不相连，因此并不 能满足内存申请。这些不连续的难以利用的小空间就是外部碎片。 图2 - 6 描绘了外部碎片的情况，在多次分配和释放之后，剩下极少量的连续 空间，这段连续空间无法满足绝大多数的分配请求，从而造成了外部内存碎片。 一 连续牵闲窄问过小。无法作为进程所需 4 k b 图2 石外部碎片 最差情况下的内存碎片下限通常与当前所分配的内存区域的数量乘上最大 内存区域与最小内存区域的比的对数呈正比，即m l 0 9 2 n ，m 为当前所分配的内 1 2 硕士学位论文 第二章动态内存分配的原理与技术 存区域的数量，1 1 是最大内存区域与最小内存区域的比。 内存碎片无法完全消除，内存分配器必须处理好内存碎片问题，使其保持在 尽可能小的范围之内。 2 4 2 数据对齐和内存访问颗粒度 现代计算机访问内存时，不管是写还是读，都是以块为单位进行访问，也就 是指内存访问的颗粒度就是一个块的大小。在3 2 位的使用虚拟内存系统的系统 上，一个块通常是4 k b 3 0 】【3 l 】。内存数据对齐就是在放置数据时将数据放在偏移 量为数据块整数倍的地址上，这样就能充分利用c p u 访问内存方式，减少内存 访问次数。为了将内存数据对齐，有时就需要填充无意义的字节或者是跳过若干 个字节大小的内存空间来放置数据。内存数据对齐可以从三个角度来看： 1 高速缓冲存储器角度； 2 虚拟内存系统角度； 3 c p u 内存访问角度。 在动态内存分配时也需要考虑到数据对齐的问题。例如，进程请求分配4 0 0 0 字节大小的空间后，再请求分配4 0 0 0 字节大小的空间。第一次分配4 0 0 0 字节后， 内存分配器分配了4 0 0 0 字节，而一个块的大小是4 0 9 6 字节，一个块中尚有9 6 字节剩余，那第二次分配时，就不能从这9 6 字节开始分配，因为这样将导致第 二次分配的内存空间起始地址并不是数据块大小的整数倍，这样系统在访问这次 新分配的数据空间中的数据时，需要进行两次内存访问。在更早高的情况下，在 使用了虚拟内存系统的机器上，如果第一个块的数据在物理内存中，而第二个块 的数据却被换出了物理内存，置于交换空间之内，这就将导致页面错误，从而造 成系统访问辅助存储器，严重地影响系统的性能。为了防止这种情况的出现，第 二次内存分配的时候，上次所遗留的9 6 字节空间就不能够使用，而必须从第二 个数据块开始分配，这样就能保证第二次分配的所有空间都能够在一个数据块之 中，提升了系统的性铱 计算机在访问内存时是以一个字为单位。每次访问时如果数据最高地址和最 低地址分别处在两个不同的字之中，访问这个数据就需要两次内存访问。 计算机访问内存时每次读取或者写入一个字的数据。如果内存的字的大小至 少和计算机的原始数据类型一样大，内存访问的时候总是边界对齐。对于未对齐 的数据的访问可能不是这样。 如果需要访问的数据中的最高和最低字节并不处在同一个字之中，计算机必 须将以此内存访问分成多次数据访问。这需要许多复杂的步骤来进行协调。为了 处理好同一个字处在不同的内存页面之中的问题，处理器必须确定相关的两个页 1 3 硕士学位论文 第二章动态内存分配的原理与技术 都在物理内存之中，不然就会在内存访问的时候出现t l b 失效或者页面错误， 造成额外的访问周期。 单个内存字的访问具有原子性，也就是说，整个内存的字都是一次性的读或 者写，其他的设备必须等到读或者写操作结束之后才能访问内存。但是，没有对 齐的数据需要多次访问，也就是说，第一个字被一个设备所读取，两个字都被第 二个设备所写入，然后第二个字被第一个设备读取，然后，读取的两个字并不是 在整个数据被第二个设备改写之前的数据，也不是改写之后的数据。尽管这种可 能性很小，但是，一旦发生就很难鉴别。 x 8 6 体系结构原本不需要内存对齐访问，但是，s s e 2 和x 8 6 6 4 指令需要按 1 2 8 位对齐，也就是1 6 字节。并且，在这种体系结构上使用对齐的数据能够在 一定程度上提升性能。 2 4 3 多线程 在多线程情况下，内存分配器将面临多种在单线程模式下所不具备的问题， 包括： 多次释放同一内存区域。第一个线程申请释放第一个区域，在此申请尚未结 束时，第二个线程也发出了内存申请请求。如果第一个线程传入的参数被第二个 线程传入的参数所覆盖，将会使得第二个线程所申请释放的内存区域被释放两 次，在大多数操作系统上，这将导致段访问错误，操作系统将终止进程。 获得悬挂的指针。这种问题出现在内存分配器本身。如果一个线程申请空间 尚未完成时，另一个线程也发出了请求，后一个请求可能会在前一个尚未完成时 覆盖前一个所产生的数据，从而造成第一个请求出现异常，线程将获得一个悬挂 的指针。 更加容易导致内存泄漏。设计错误的分配器会由于多个线程之间使用同一个 存储区域而导致已经分配的内存区域没有被记录下，进而导致内存泄漏，造成内 存空间的浪费。对于长时间运行的进程，内存泄漏将会导致严重后果。它会使得 进程所占用的空间不断增长，而不会减少，最终导致内存耗尽。 2 4 4 内存区域之间的依存与局部性 在相近时间内分配的内存区域也会在相近的时间内释放。如果内存区域被分 配在连续的空间之内，则往往也会被连续释放。另一方面，大小不同的内存区域 也往往用作不同的用途，也往往意味着会有不同的生命周期。 如果内存分配器能够利用用户进程所申请的内存区域的顺序与大小从而推 测出各个内存区域之间的相互依存关系，那么它就能够将生命周期长度相当的内 1 4 硕士学位论文第二章动态内存分配的原理与技术 存分配请求的区域放置在连续的位置。这样，在进行内存释放的时候就能够尽可 能的减少内存碎片的产生，从而提高内存空间的利用率。 内存访问的时候还具有局部性，包括时间局部性和空间局部性两个方面。 时间局部性是指动态内存分配的时候，相近时间内分配的内存大多会在相近 的时间内释放。 空间局部性则是指在相近时间内分配的内存，其中的某个内存区域被访问之 后，其它相邻的区域或者是虚拟空间地址上相隔近的区域也会在相近的时间内被 访问。 动态内存分配器必须处理好局部性的问题。处理得当将会使得用户进程访问 内存的速度得以提升。 2 5计算机体系结构的影响 计算机的体系结构对于内存访问方式有着直接的影响，这也迸一步影响到了 内存分配器的工作方式。 2 5 1 存储空间的访问方式增强了局部性 d r a m 将存储空间划分成了许多行，每行又被划分成为许多列。当进行内 存访问的时候，首先找到所需要访问的内存区域所在的行，然后将该行放置在一 个缓存之中，接着，找到这个行中所需要的列，即所需访问的存储单元，通常是 一个字，最后将这个存储单元中的数据通过数据总线传递给处理器。如果下一次 内存访问地址仍然在这行之中