（计算机应用技术专业论文）提高实时数据处理性能的内存管理研究.pdf

提高实时数据处理性能的内存管理研究 摘要 实时数据库是指其数据和事务都具有时间属性或显式时间约束 的数据库，是现代数据库技术的一个热点，在工业领域、特别是自动 控制领域具有重要的使用价值。 查询速度是衡量实时数据库性能的一个重要指标。而数据扫描是 查询执行阶段的最基本操作。本文从c a c h e 的工作特性出发，研究能 使同一数据库表记录紧密存放在一起的内存管理方法，以提高数据库 表的遍历性能。论文首先介绍课题的背景、提高数据访问速度技术研 究进展、意义与所作的工作；然后介绍c a c h e 的工作特性；设计了两 种内存管理方法：多位图方法和多种大小块方法，通过对比，多位图 方法被确定为实时数据处理的内存管理方法；接着实现了基于多位图 的内存管理模块，该内存管理模块的分配和回收接口和通用的内存管 理模块一样，应用程序可以很方便地执行内存分配和回收，为了适应 具体的应用情形，该内存管理模块的工作参数可以调整，该模块还能 检查内存的非法释放；测试表明基于多位图的内存管理方法的应用程 序的性能显著提高；最后总结课题，并指出将来可进一步研究的工作。 关键词：c a c h e内存管理多位图方法多种大小块方法实时数 据库 r e s e a r c ho nm e m o r ym a n a g e m e n tt oim p r o v ep e r f o r m a n c e o fr e a l - tim ed a t ap r o c e s sln g a b s t r a c t r e a l - t i m ed a t a b a s ei st h eo n ew h o s ed a t u ma n da f f a i rh a st i m e l i n e s s a n da p p a r e n ts a n c t i o n ，i tw a sa l s ot h er e s e a r c hh o to fm o d e md a m b a s e t e c h n o l o g y , a n dh a si m p o r t a n ta p p l i c a t i o nv a l u ei ni n d u s t r i a ld o m a i n , e s p e c i a l l ya u t o m a t i o nc o n t r o l s p e e do fq u e r yi st h em o s ti m p o r t a n tf a c t o ro fr e a l - t i m ed a m b a s e p e r f o r m a n c e ，a n dd a t as c a ni st h eb a s i so p e r a t o ro fq u e r ye x e c u t i o n b a s e do nt h ec h a r a c t e r i s t i c so fc a c h e ，t h er e s e a r c hf o c u so nm e m o r y m a n a g e m e n t , t h er e c o r d so ft h es a m ed a t a b a s et a b l ew e r ec o m p a c t l y s t o r e dt o g e t h e ri nt h em e m o r yb yt h em e m o r ym a n a g e m e n t , w h i c hc a n i m p r o v et h et r a v e r s es p e e do fd a t a b a s et a b l e a tf i r s t , t h eb a c k g r o u n d ，t h e s i t u a t i o no ft h es u b j e c ta n dt h ed e f a u l to fb a s em e m o r ym a n a g e m e m m e t h o d si nr e a l - t i m ed a t ap r o c e s s i n gw e r ei n t r o d u c e d t h e nt h et h e s i s i n t r o d u c e dc h a r a c t e r i s t i c so fc a c h eo p e r a t i o n i nt h et h e s i s ，w ed e s i g n e d t w om e t h o d so fm e m o r ym a n a g e m e n t ：m u l t i p l eb i t m a pm e t h o da n d v a r i o u s - s i z eb l o c km e t h o d , b yc o m p a r i s o n ，m u l t i p l e - b i t m a pm e t h o dw a s d e c i d e da st h em e m o r ym a n a g e m e mm e t h o do fr e a l - t i m ep r o c e s s i n g t h e nt h ei m p l e m e n to fm u l t i p l eb i t m a pm e m o r ym a n a g e m e mm o d u l e w a sg i v e n ，t h ea l l o c a t e f r e ei n t e r f a c eo ft h ec u s t o m i z e dm e m o 巧m a n a g e w a sa st h es a m ea sg e n e r a lo n e ，a p p l i c a t i o nc a na p p l ya n df r e em e m o 巧 s p a c ec o n v e n i e n t l y , t h em e m o r ym a n a g e m e n tm o d u l eh a da ni n t e r f a c et o s e t ，t h ew o r kp a r a m e t e rt oa d a p t i n gs p e c i f i cc i r c u m s t a n c e s ；i tc a na l s o c h e c kw h e t h e rf r e e i n gm e m o r yw a si l l e g a l t h et e s ts h o w e dt h a tt h e p e r f o r m a n c eo fa p p l i c a t i o nb a s e d0 1 1t h ed e s i g n e dm e m o 可m a n a g e m e m m e t h o dh a sb e e n i m p r o v e do b v i o u s l y f i n a l l y , t h e t h e s i sm a d ea c o n c l u s i o na n dp o i n t e do u ti t sf u r t h e rr e s e a r c h k e y w o r d s ：c a c h e ；m e m o 巧m a n a g e m e n t ；m u l t i p l eb i t m a pm e t h o d ； v a r i o u s s i z eb l o c km e t h o d ；r e a l - t i m ed a t a b a s e h i 广西，“莹司n b 掌岱时e 文提高薯 - 争魏据笼理性能的内存蕾理研究 1 1 实时数据库概况 第一章绪论 数据库技术的发展极其迅速，其应用日益广泛，在当今的信息社会中，几乎 无所不在，以关系型为代表的数据库在传统的商业和管理等事务性应用中取得了 极大成功，然而在现代的工程和时间关键型应用面前却显得软弱无力，由此导致 了实时数据库的产生和发展。 所谓实时数据库“卜啪是指其数据和事务都具有时间属性或显式时间约束的 数据库，既系统的正确性不仅依赖于逻辑结果，而且还依赖于逻辑结果产生的时 间，处理的事务要求在截止时间之前完成，超时将消弱事务处理的结果甚至使其 变为无效。 为了实现事务处理的实时性，必须尽可能加快实时数据库的响应和处理速 度。但对于磁盘而言，由于磁盘数据存储存在着缓冲区管理、排队等待及锁的延 迟，使得事务平均执行时间和估算的最坏情况执行时间相差很大，不能满足及时 性的要求。如果将整个数据库或其主要的工作部分放入内存，由于每个事务的执 行没有磁盘i o ，系统能较准确估算和安排事务的运行时间，使之具有较好的动 态可预报性；并且随着微电子技术的发展，存储量很大并且廉价的动态存储器的 大量使用使得数据库完全装入内存成为可能，因此，将数据库的主拷贝或工作版 本常驻内存、使用内存作为实时数据库信息的存储介质是支持实时事务处理的最 佳技术“。 实时数据库是是现代数据库技术的一个热点“瑚，在工业领域、特别是自动 控制领域具有重要的使用价值。在商品化的实时数据产品开发上，国外有很多著 名公司在原来的主营业务上推出了相应的实时数据库产品，澳大利亚的 m o t h e r w e l l i n f o r m a t i o ns y s t e m 公司于1 9 8 2 年较早地推出了m a c r o v i e w 产品，美 国o s i 公司于8 0 年代中期推出了p l a n ti n f o r m a t i o ns y s t e m , 简称p i 产品；还有美 国a s p e n t e c h 公司的i n f o p l u s 2 1 系列；美国的h o n e y w e l l 公司的u n i f o r m a n c e ( p h d ) 系列等。国内研究起步于2 0 世纪9 0 年代初，随着国内工业界对d c s 的大量引 进和应用，国内科技教育界率先研究实时数据库理论，其中比较有名的有华中科 期归薯；时囊据冀癯佳e 的内存蕾理研究 技大学的刘云生教授，指导完成了a r t s i 型实时数据库系统的雏形，目前，国 内已相继出现了一些商业化实时数据系统产品，如三维公司的力控数据库系统平 台，三维天地计算技术开发有限公司的s u p e r l n f o 系统等。 1 2 实时数据库查询处理研究进展 从大量的数据库应用系统的实例来看，查询在各种操作中占的比例最大，查 询的效率是数据库系统的重要性能指标，高效的查询能极大地提高系统的性能， 查询处理技术的研究一直是各种数据库技术研究的热点。 1 2 1 查询优化 查询的基本步骤包括：1 语法分析和翻译；2 查询优化；3 执行。用户的查 询输入在经过语法分析和翻译后，转化为数据库系统的内部表示，这通常基于关 系代数式。查询优化的工作就是将来自第一阶段的输出，经过一系列逻辑演算， 得到逻辑等价而代价( 接近) 最少的关系代数式。由于连接运算顺序对于减少查 询中间结果集的大小很重要，因此，大多数的查询优化都在连接次序上花了较多 功夫。 传统的查询优化通常采用基于时间代价、减少磁盘i o 的策略。而磁盘i o 瓶颈消除后，c p u 运算速度和内存访问速度不匹配成为影响实时数据库性能的 新挑战旧；并且查询优化结果的获得本身是一个n p 难度问题m 。因此，实时数 据库的查询优化往往以次优解为目标。 刘云生等人咖9 1 将遗传算法引入查询语法树的优化，遗传算法将编码后的查 询语法树，转化为多个a n d 子旬，将o r 操作提到顶层，再进行各种遗传算法的 操作，将结果中的每一个a n d 子句根据上述规则判断好坏，优化的最终结果的适 应度为得分最少的结果。 许峰等人在文献 1 0 中提出了改进的遗传算法，该算法的交叉变异概率基于 s r i n v i v a s 提出的算法，使群体中最大适应度值的个体的交叉率和变异率不为 零，相应地提高到群体中表现优良个体的交叉率和变异率，使得不会处于一种近 似停滞不前的状态；变异操作使用基因交换表示，以减少生成非法连接树的概率， 并且交换尽量选择大的基因，以保持子树树型。 2 撮离曩 时效据楚葺l 佳期拍9 内存蕾理研究 遗传算法的局部搜索能力不强，因此解的质量不够高。为了改进这一不足， 倪小剑等人在文献e 1 1 中提出混合型的遗传算法，该算法在遗传算法的每次迭代 过程中增加一个新的步骤，这个新的步骤基于在领域搜索中能沿着改进问题解质 量的方向前进的爬山法；陈继华等人在文献 1 2 中将模拟退火算法引入查询优 化，也取得了不错的效果。 1 2 2 数据索； 数据扫描( d a t as c a n ) 是查询执行阶段的基本操作。研究人员设计了各种索 引结构，快速定位到指定位置，以加快扫描速度。一些在磁盘数库中使用的检索 技术在实时数据库并不能取得很好的效果，例如在磁盘数据库系统中广泛适用的 b + 数等索引，由于其索引也存储部分被索引数据，从而在查询时可以直接访问 被索引数据，而不需要根据索引从磁盘读取数据；在磁盘数据库需要考虑的b + 树深度问题，也由于实时数据库的特性显得并不是那么重要索引树的深度再 深，也只是增加几次内存访问而已，开销很小。但是如今，随着对计算机系统结 构的认识逐渐加深，特别是c a c h e ，数据访问技术的热点研究方向表现为在数据 访问的过程利用好c a c h e ，使得性能得到最大的优化。人们重新研究曾普遍使用 的索引，发现这些索引对缓存的利用率很差，反而限制了其性能的发掘“”“”。 由t j l e h m a n 和m j c a r e y 提出的t - 树，被广泛地用作内存数据库的索引结 构，然而从c a c h e 的特性出发，t - 树存在着不足之处：每个节点中存放多个关键 字，却只有两端的关键字是用于比较。 由于t - 树结点大小通常大于c a c h e 块大小，因此不能一次被c a c h e 全部命中。 c s t - 树“”是根据访问频率的高低将原来t 树结点中的内容划分为高频和低频两 部分，在结点中只保留高频部分，而将低频部分单独保存，这样可以使节点的大 小总是小于c a c h e 块大小，使一个结点一次就可以被c a c h e 完全命中，从而可以 获得比t - 树更高的c a c h e 命中率。 b + 树是一种平衡的多路查找树，是在传统数据库中得到广泛应用的一种索 引结构。尽管b + - 树主要用于磁盘数据库系统，但实际上，与t 树相比，b + - 树具 有更好的c a c h e 性能。但是由于b + - 树每个内部节点中要为每一个关键字保存一 个指向子节点的指针，而指向实际记录的指针只保存在叶子节点中，因此，b + - j - - 西大粤明曩士掌位论3 期t ，首实时羲期诅佳期曲内存蕾罩l 研究 树的c a c h e 性能也不是很好。 由j r a o 和k a r o s s 提出的c s s 树“6 1 是b + 树的变形。与b + 树相比，c s t 树“”、结点近似等于c a c h e 块大小，并且节点内只保存关键字，而不保存指向 孩子结点的指针，结点的孩子结点组成结点组连续存放在数组中，使每个c a c h e 块能容纳更多的关键字用于比较，因而，与b + 树相比查找性能大大提高。但c s s 树只能支持批量更新操作。 c s b + - 树“”中只保留指向第一个孩子结点的指针，除了提高b 乞树的查找性能 外，在c s s 树的基础上又增加了更新功能。 同时，多种针对缓存效率优化的方法，如合理设置节点大小“”、减少t l b 却失呻1 、c a c h e 预取例等，也被使用。 1 3 课题的意义 1 提高遍历数据库表应用场合的性能 数据库查询阶段的扫描操作可以分为两种：扫描索引，索引中的信息指示满 足要求后访问相应记录；直接扫描记录。由于存在没有建立索引的情形，甚至在 在使用索引对应的字段进行非等值比较时( 索引建立的是字段与记录的1 ：l 影 射关系) 直接扫描记录能取得更好的效果，因此，与首先扫描索引相比，直接扫 描记录对查询的性能影响更大。 本文研究提高直接扫描记录性能的方法，该方法通过在为新记录分配内存时 选择合适的空间来完成这一目的，这是因为：现代计算机的存储体系结构的最高 层为c a c h e ，c p u 访问数据从c a c h e 开始，而c a c h e 存取内存数据以块为单位， 因此数据在内存中的分布对c a c h e 缺失有影响；另一方面，内存管理模块在服务 内存申请时按照一定的策略选择空间，而申请者将数据存放到返回的内存空间， 因此内存管理模块决定了数据的内存分布，进而影响相关数据的访问速度。 基本内存管理方法一个主要不足是不能为同一数据库表的记录分配连续的 空间，并且基本内存管理方法中的碎片增大了记录在内存中的分布范围。c p u 在遍历使用基本内存管理方法构建立的数据库表时，会发生更多的缺失。 本文设计的内存管理方法能够将同一数据库表的记录紧密地组织在一起，因 此提高遍历数据库表应用场合的速度。除前面提到的查询执行阶段的速度外，还 4 ，西大掣嘱曩士掌位论文提离实时散据笼习i 臼j t 的内存蕾毒l 研究 包括提供数据库导入导出的速度，因为遍历也是导入，导出的基本操作。 此外，本文设计的内存管理方法能够提高的性能 2 减轻数据库乃至整个计算机系统的负荷 实时数据库是操作系统管理的一个用户进程，数据库系统执行过程中的所有 内存分配请求都直接向操作系统提出，必将增加操作系统的负担。设计运行在用 户态的内存管理模块能够减轻系统负担。”。对数据库系统而言，则由于管理内存 空间的模块运行在用户态，减少了运行开销。 1 4 本文所做的工作和特色 本文从c a c h e 的工作特性出发，研究内存管理，所作的工作如下： 1 研究c a c h e 的工作特性； 2 从c a c h e 的工作特性出发，设计在数据库表中插入记录时使用的两种内存 管理方法。通过精心的设置，这种内存管理方法能够做到没有碎片，并且由于能 使同一数据表中的记录更加紧密地存放在内存中，所以能够减少c a c h e 发生缺失 的次数，因此能够提高遍历数据库表的这一应用的执行速度。通过两种方法初始 化代价和对c a c h e 缺失的影响，最终确定使用多位图方法为新插入的记录分配内 存空间； 3 基于多位图方法的内存管理模块实现。该内存管理模块具有以下特点：由 于分配和回收的接口同通用的内存管理模块一样，应用程序可以很方便地执行内 存分配和回收操作；采用参数化设计，内存管理模块支持在程序运行时设置内存 管理模块的工作参数，不需要在源程序中修改参数以适应具体的应用场合；另外， 该内存管理模块具有检查非法释放的功能； 4 通过实验验证设计的多位图方法能够提高遍历数据库表这一应用场合的 性能。使用的测试项目有三个，它们是：对数据库表进行遍历查询、将记录写入 文件和从文件读记录。另外，作为内存管理方法，本文也对分配和回收的速度进 行了测试。 本文的主要特色是从c a c h e 的工作特性研究问题。如分析将内存管理中的管 理数据按照类型而不是所属的区间存放在一起、比较设计的两种内存管理方法 时，使用c a c h e 的工作特性来考察运行时间；元素数量较少时，分析顺序查找甚 5 f - 西，“堂司n b 茸啦能文棚臼霄实时致据笼理性麓的内存f 理研究 至要比二分查找需要更少的运行时间也使用了c a c h e 的工作特性。 1 5 论文的结构 本文主要研究提高遍历存放实时数据的数据库表性能的内存管理技术。全文 各章内容如下： 第一章对论文的内容作整体性介绍。首先简要介绍实时数据库的基本情况； 接着对提高实时数据库查询处理方法做一个综述；然后指出本文研究课题的意 义；接着介绍论文所作的工作和特色，最后介绍论文的结构。 第二章是基础知识，介绍c a c h e 的工作特性。 第三章是本文的重点。首先介绍通过一次系统调用申请内存的原因；然后确 定区分记录所属表的策略；设计两种方法( 多种大小块和多位图方法) 用于在数 据库表中插入记录时分配空间；最后通过两者的性能对比，确定使用多位图方法 作为实时数据处理的内存管理方法。 论文第四章介绍基于多位图方法的内存管理模块的实现。在这部分介绍实现 的策略、内存管理模块的构架、接口设计、分配以及在内存回收时对非法释放的 处理过程。 在第五章，对本文设计的内存管理方法进行实验测试。使用的工具是本文实 现的多位图内存管理模块，比较的对象为编译器中的内存管理模块。比较的项目 包括两个部分：内存空间的管理性能；使用两个内存管理模块搭建的应用程序， 在遍历数据库表应用中的速度。 论文第六章对本文进行总结，并指出下一步开展的工作。 6 提葺陲时数据笼理性l 的内存蕾。理研究 第二章c a c h e 的工作特性 中央处理器运算速度和内存访问速度存在着极大的差异。为了避免每次使用 内存数据都需要访问内存，现代计算机系统结构中通常都包含有高速缓存 c a c h e 。c a c h e 通常是c p u 的一部分，是计算机系统中除寄存器外的次高层的存 储部件。现代计算机系统中的存储结构如图2 一l 所示。 c p u 日_!：!竺礤和各种辅助存储部件： 圈 图2 1 计算机系统中的存储层次结构 f i 9 2 一lt h el e v e l so f m o r yh i e r m _ c h yi nc o m p u t e rs y s t e m 2 1 c a c h e 与内存的映射关系 c a c h e 的基本单位为块，用于保存内存数据的拷贝。按照c a c h e 块中数据的 内存来源，c a c h e 可以分为三类： 1 直接映射。这种映射关系的c a c h e 中，内存数据块只能出现在c a c h e 中的 惟一位置，映射方法通常是： 内存数据块在c a c h e 中的块号= ( 内存块号) ( c a c h e 中的块数) 如图2 2 ，假设c a c h e 由8 个块组成，c a c h e 取内存数据块1 8 时，该块将 被保存在c a c h e 中的块2 中。 2 全关联映射。这种映射关系的c a c h e 中，内存数据块能够出现在c a c h e 中的任何位置，如图2 2 中，c a c h e 在取内存数据块1 8 时，c a c h e 中的任何块 都有可能用于保存内存数据块1 8 。 3 组相联映射。具有这种映射关系的c a c h e ，其中的块被分为若干组。对于 一个内存数据块而言，保存该块的c a c h e 组号是确定的，即： 保存内存数据块的组号= ( 内存块号) ( c a c h e 中组的数量) 内存数据块可以保存在该组任何一个c a c h e 块中。 7 期臼肯薯 时敦据处理佳能的内存管理研究 如图2 2 所示，假设c a c h e 中的8 个块被分为4 组，则内存数据块1 8 将被 保存到组2 中，对应改组的c a c h e 块4 和5 都可以用于保存内存数据块1 8 。 直接映射： 块1 9 只能进入 块4 ( 1 2 m o d 8 ) 全相联： 块1 8 可进入 任何一个块 组相联映射： 块1 8 可进入组2 中 任何一块( 1 8 m o d 4 ) c a c ：础块瑚块瑚 存储器 縻 图2 2c a c h e 与内存的映射关系 f i 9 2 2m 印r e l a t i o nb 酏y e c nc a c h ea n dm e m o r y 2 2o p u 读内存数据的过程 c p u 执行对内存数据的读操作首先从高速缓存开始：首先检查c a c h e 中是否 有被访问内存地址中的数据拷贝，如果c a c h e 命中，则直接从c a c h e 中取这个数 据；只有在c a c h e 中没有内存数据、发生c a c h e 缺失的时候才去访问内存，从内 存中取相应的数据。 c a c h e 读写内存数据是以块而不是以字节为单位的。这样，在发生一次c a c h e 读缺失的 时候，会一次装入多个字节信息，可以避免接下来访问相邻的数据再次发生缺失。 2 3o p u 写内存数据的过程 2 3 1 写直达和写回法 写直达( w r i t et h r o u g h ) 和写回法( w r i t eb a c k ) 啪1 是处理c a c h e 中被 8 组0组： o 组， 组o 65432o987654320987654320 争 埏 舅u 霄薯 时数据笼理性能的内存蕾理研究 修改的数据块的两种策略。 在c a c h e 数据块发生修改时，写直达立即将更新后的数据写入内存。这种方 法易于实现，能够保证内存中的数据是当前最新数据的副本，简化了数据一致性 问题。 写回法只修改c a c h e 中的数据。一直到c a c h e 中没有空闲空间、要为从内存 中读取的新数据块空出一块空间，并且按照某种替换策略刚刚选中这个块时，才 执行将这个被修改的块写入内存中的操作。因此，即使是被c p u 修改的块也会在 c a c h e 中存在一端时间，这段时间执行对这个修改块的读写操作，不会发生缺失。 由于对内存数据的更新操作不需要立即更新内存中的副本，因此写回法中的写操 作和c a c h e 的速度一致，速度很快。并且对同一个块的多次写操作仅需要对内存 进行一次写操作，写回法需要较小的存储带宽。 2 3 2 写分配和不按写分配 因为写操作不需要数据，因此对写缺失有两种处理方法乜1 1 ：不按写( n o - w r i t e a l l o c a t e ) 和写分配( w r i t ea l l o c a t e ) 。 不按写是指c a c h e 发生内存数据缺失时，不将内存数据块读入c a c h e 中，而 直接修改内存中数据的值。 写分配是指在发生写缺失时，与读缺失一样，需要首先从内存中读入内存数 据块，然后在c a c h e 中执行对内存数据的写操作。 虽然两种写缺失的处理方法都可以被应用到写回法或写直达法中，但是采用 写回法的c a c h e 通常采用写分配，而写直达法经常与不按写分配配合使用1 。通 常c a c h e 写采用的是写回法和写分配策略。 2 4 替换算法 当c p u 发出内存访问指令时，根据它产生的内存地址分为两种情形：一种 是需要的数据已经在c a c h e 中，那么只需直接访问c a c h e ，从对应单元中读取信息 到数据总线：另一种是需要的数据尚未装入c a c h e ，c p u 需从内存中读取的同时， c a c h e 替换部件把该地址所在的内存块读入c a c h e 中：若c a c h e 中相应位置己被 占满，就必须去掉旧块。为了保证c p u 访问时有较高的命中率，c a c h e 中的内 9 提离薯；时奢0 据楚理佳能的内存蕾l 霉i 研究 容应该按一定的算法进行替换。 常见的替换算法有以下几种，其中f i f o 和l r u 策略使用比较多1 2 2 1 1 2 3 1 1 2 4 1 ： ( 1 ) 先进现出替换策略( h f o ) f i f o ( f i r s ti nf i r s to u t ) 策略是把最先调入的c a c h e 块替换出去，它不需要 随时记录各个块的使用情况，较容易实现；缺点是经常使用的块，如一个包含循 环的程序的块也可能由于它是较早的块而背替换掉。f i f o 策略效果不是很好， 不符合程序的局部性原则，经常出现所谓的“颠簸”现象。 ( 2 ) 最近最少使用替换策略( l r u ) l r u ( l e a s tr e c e n t l yu s e d ) 策略是把当前c a c h e 中使用次数最少块替换出去， 这种替换策略需要随时记录c a c h e 块中字节的使用情况。因此需要为每块设置一 个计数器，把命中块的计数器清零，其他各行计数器加1 。替换时，淘汰块计数 器值最大的数据块出局。l r u 的平均命中率也会提高，由于符合程序访问的局 部性原理，l r u 策略是目前使用较多的一种替换策略。 ( 3 ) 随机替换策略 硬件上容易实现并且速度快，虽然表面看起来算法比较随意，但实际模拟显 示其性能不错，失效率比较低。 2 5 数据预取 为了进一步提高c a c h e 命中率以及减少c a c h e 缺失代价，c a c h e 设置有预取 ( p r c f e 劬) 机制。c a c h e 所用的预取算法基本上属于按需取进法1 1 2 3 1 ，也就是在 c a c h e 发生数据缺失需要从内存中取数据时，将预取的数据块一起读入c a c h e 中， 并且根据数据使用的空间局部性原理以及硬件实现的简便性，通常取相邻位置上 的内存块。 2 6 程序运行时间与连续使用的数据在内存中分布的关系 通常内存的访问速度是几十甚至上百个c p t j 时钟周期，而c a c h e 的速度只需 要两三个时钟周期。因此，如果c p u 大多数时间情况下在c a c h e 中执行对数据的 读写操作，则程序只需要运行很少的时间。下面是程序在计算机中的运行时间公 式。”： 1 0 璺臼膏薯 时羲据处罩e 性麓的内存雀l 曩e 研究 程序的执行时间= 执行的指令数量( 平均每条指令的执行时间+ 平均每条 指令访问内存的次数( c a c h e 命中率平均每次c a c h e 访问时间- - c a c h e 缺失 率平均每次内存访问时间) 从一个程序考虑，影响程序运行时间的因素有：执行的指令总数量和指令的 类型。因此，减少程序总的指令数量、限制长运行时间和访存指令的使用，能够 提高程序的运行速度。但是，对于一个具体任务而言，使用上面的方法改进程序 运行性能的效果不是很理想。 然而，不同的内存数据的组织对程序运行时间有很大的影响。如图2 3 ， 现在假设c p u 只有两个c a c h e 块，并且都为空闲。现在在c p u 上运行的程序需要 对数据块1 、2 、3 执行检索操作，比如这蓄数据块中存放的是工业现场各个位 置的温度信息，现在要检索那个位置的温度最高。在情形一中，c p u 读数据块1 时，由于所有的c a c h e 都为空闲，找不到数据块1 ，发生一次读缺失，c a c h e 从 内存中读取数据块1 ，并且认为相邻的位置可能会被访问到，所以会将相邻的块 也读入，在情形一中这是一个接下来不会被访问的数据；之后，c p u 需要读取数 据块2 ，检查c a c h e ，c a c h e 中没有数据块2 的拷贝，则需要再执行一次对内存 数据的访问；在读取数据块3 时也发生一次缺失。整个过程发生3 次缺失，访问 每个数据块的时候都发生了缺失。在情形2 中，c a c h e 首先发生一次缺失以读入 数据块l ；在读取数据块2 的时候也发生一次缺失；在访问数据块3 时，由于数 据块2 缺失时，高速缓存会将把相邻的块带入高速缓存，所以不会发生缺失。整 个过程发生了2 次缺失，与情形1 相比，少了一次缺失。 情形一被连续访问的数据相隔很远 c a c h e 能容纳两个内存决 情形二被连续访问的数据块位置接近 图2 3 数据块在内存中的两种不同存放方法对程序运行时间的影响 f i 薛一3t h e h f f l u e n c eo f p r o g r a me x e c u t i o na sd a t as a v e di nt w od i f f e r e n tw a y 提高鲁；时数据爿涅性能的内存管理研究 可以看出，不同的内存组织对程序的运行速度存在着影响。在c a c h e 机制 中，为了提高程序的运行性能，应该按照数据的使用特点将被连续访问的数据组 织在内存中的相邻位置，以便在程序运行时，c p u 对数据的读写的大多数情况下 在c a c h e 中进行，进而避免了费时的访问内存的操作。 2 7 本章小节 本章介绍c a c h e 的工作特性。首先介绍c a c h e 与内存的映射关系；然后分别 介绍c p u 读写内存数据块的微观过程；接着介绍了c a c h e 的替换算法和预取机制。 最后说明数据在内存中的分布位置影响程序运行时间的原因。 朔l ，薯；_ 于舅据爿灌佳能的内存管理研究 第三章内存管理方法分析与设计 在绪论中提到，基本内存管理在实时数据处理的一个主要问题是不能区分记 录所属的表、将不同表中的记录混合存放在内存中。而根据第二章介绍的c a c h e 的工作特性，在遍历这样的数据库表时，将发生更多的c a c h e 缺失。在本章将要 通过在内存分配时选择合适的空间，使同一数据库表的记录存放在连续内存中， 解决整个问题。 3 1 动态内存应用中的软件体系结构 用户程序经过编译、连接形成的映射文件中有一个代码段和数据段( 包括 d a t a 段和b s s 段) ，并且代码段在下，数据段在上。数据段中包含了所有静态分 配的数据空间( 包括全局变量和使用s t a t i c 关键字说明的局部变量) ，这些空间 是进程必须的基本要求，所以操作系统内核在建立一个进程的运行映像时就分配 好这些空间，包括虚存地址空间和物理页面并建立好两者的映射。另外，堆栈使 用的空间也属于基本要求，所以在建立进程时就分配好了( 但可以扩充) ，所不 同的是，堆栈空间安置在虚存空间的顶部，运行由高地址向低地址延伸，代码段 和数据段则在低地址部分，运行时固定不变，并不向上延伸。从数据段的顶部到 堆栈段地址的下沿这个中问区域则是一个巨大的空洞，这就是可以在运行时动态 分配的空间。程序逻辑空间的组成如图3 1 所示。 计算机操作系统是整个系统内存资源的管理者，进程通过系统调用申请释 放内存空间。系统调用。”汹1 对应着软中断，进程执行系统调用后，c p o 中的中断 硬件捕获这个软中断后，通过中断向量表找到对应的中断处理程序，软中断对应 的中断处理程序即为系统调用处理程序。这个程序分析系统调用传递的参数，这 些参数中包括系统调用名。系统调用处理程序为了找到系统调用的入口也需要查 表。 从上面的过程可以看出通过系统调用使用操作系统管理的资源存在着开销。 内存的分配和释放操作直接通过系统调用进行、由操作系统管理内存资源的方式 的性能不是很理想。一个提高性能的设想是在用户进程中构建一个内存管理模 块，这个内存管理模块通过少量的系统调用从操作系统中申请需要资源的最大数 1 3 埘u 协- 于数据楚曩l 性“由内存蕾摹l 研究 量，进程对内存空间的申请和释放由该模块直接管理，从而减少系统调用开销。 m a l l o c f r e e 库函数和c + + 语言成分n e w d e l e t e 是基于这种思想的实现。 这样，动态内存应用中的软件体系结构包含三个实体：用户进程、用户态内 存管理模块和操作系统内存管理模块，如图3 2 所示。操作系统内存管理模块 位于底层，是整个结构的基础；用户态内存管理可以实现特定目的，如前面提到 的减少系统调用开销，而本文构建该模块的主要目的是使相同数据库表的记录连 续存放，以减少遍历数据库表的c a c h e 缺失。 系统 堆栈区间 空洞 躅产。 数据和 1 代码区间 问 间 图3 - 1 进程逻辑空间的组成 图3 2 应用程序分配和释放内存主要在用户态下进行 f i 9 3 - 1c o i s to f t i l ep r o c e 鼹l o g i cs p a c e f i 9 3 2a l l o c a t ea n df r e em e m o r ym a i n l yi nu s e rm o d e 3 2 区分记录所属表的策略 可以在申请内存时直接提交记录所属表的信息来解决这个问题。这种方法的 不足是需要执行分配的内存管理模块“了解”所有的表，并且在为记录申请内存 空间时需要提交所属表的描述信息。 本文使用的是依照数据类型长度来识别记录所属表的策略。理由如下： 首先，不同表的记录通常具有不同的长度，存放实时数据的数据库表更是如 此：表记录模式大部分字段相同，差别在于存放描述节点工作环境信息的字段上， 如保存开关状态需要一字节( 使用一个比特位能够区分开关的开和关这两种状 态，但是编程语言通常不支持比特数据类型) ；温度需要两字节；使用浮点数表 示现场的压力数据。 1 4 搦膏蜜时羲据笼理性泊9 内存蕾嗣e 研究 另外，通用内存管理模块提供的内存分配接口只需要申请空间的大小信息。 如r e a l l o c f r e e 形式接口的内存管理模块的分配函数原型为： v o i d * m a l l o c ( s i z e _ ts i z e ) ： 使用长度区分记录所属表的策略，由于不需要了解更多的信息，程序员能够 很方便的使用基于这个策略的内存管理模块。 3 3 多种大小的块式内存管理 3 3 1 基本思想 分区方法嘲嗍伽是一种被广泛认知的内存管理方法，其基本模型如图3 2 所 示。分区方法可以分为固定分区和动态分区两种，两者的不同之处在于：固定分 区的单元大小、位置，在开始阶段就已经确定，分配时，用户需要的空间大小为 l l ，找到的空闲块为l 2 ( l ：l 1 ) ，则将整个大小为l 的空闲块返回；而动态分区 返回内存块的大小为l 。，剩余的( k l ，) 大小的内存块仍为空闲，可用于下一次分 配。 序写起始地址终止地蜘状态 l02 5 6 k空闲 2 2 5 6 k 3 6 4 k 分配 33 6 4 k6 2 0 k 空闲 46 2 0 k8 7 6 k空闲 58 7 6 k1 0 2 4 k分配 6 1 0 2 4 k1 1 5 2 k空闲 口空闲囹已分配 02 5 6 k 3 6 4 k6 2 0 k8 7 6 k1 0 2 4 k 1 1 5 2 k 图3 3 分区内存管理 f i 9 3 3r e g i o nm e m o r ym a n a g e m e n t 多种大小的块式内存管理是固定分区内存管理的扩展，以适应实时数据快速 访问需求。多种大小块方法管理一块连续的内存空间，这一空间被划分成多个区 间，区间被进一步划分为内存块。不同区间内的内存块大小不同，而同一区间内 的单元块大小相同，使用链表管理该区间的空闲内存块。在分配时仅需要提交申 捆l 龠薯 时羲据建理柑浇的内存管理研究 请空间的大小参数，回收时仅需要提交释放空间的地址参数。如图3 4 所示。 分配：申请空间的大小 回收：释放空间的地址 内存管理模块 区间1 的管理垂c 据 m 个区闻 区间m 的管理数据 1 内存块大小= l 。1 内存块大小- l - 2 区间范围 2 区间范围 3 空闲块链表头、尾指针3 空闲块链袁共、尾指针 区闻1jf 区间m 1r | 1li 1 。j 1 17 l 医二一量二：= l j 翟= 二叠 连续内存 3 3 2 管理数据 图3 4 多种大小块方法框架 f i 9 3 4a r c h i t e c t u r eo f m u l f i p l e - s i ：z eb l o c km e t h o d 多种大小块方法的管理数据主要包括两个部分：区间描述信息和存放在空闲 块中的指针。 区间的描述信息有：该区间内存块的大小，区间范围，以及空闲块链表头、 尾指针。 存放在空闲块的指针用于指示下一个空闲块的地址。空闲块在分配以后，指 针占有的空间仍可以用于存放数据。块方法管理数据的组织方式要优于分区方 法，如图3 5 所示，分区方法中的每个空闲块中除了存放下一个空闲块的指针 信息外，还需要保存该块的大小，并且空闲单元在分配以后，存放大小信息的空 间不能存放数据，因为分区方法在回收释放内存块时需要用到其大小信息。因此， 内存块大小信息通常存放在指针信息的前面。 1 6 广西，叫煳士掣啦崔演捆归膏蜜时数据处理佳能的内- 存蕾理司院 管 理 数 据 分区方法基本单元 块方法基拳单元 单元大小 下一空闲单元指针下一空闲块指针 图3 - 5 块方法和分区方法中的基本单元 f i 9 3 5e l e m e n t 蚰 u c t u r eo f r e g i o na n db l o c km e t h o d s 3 3 2 分配和回收过程 在用户进程调用内存管理模块提供的申请内存空间的接口后，多种大小块内 存管理模块执行分配。分配包括两个过程： 1 由于不同区间内的内存块大小不同，相同区间内的内存块大小相同，区间 和其中内存块大小的一一映射关系，使得分配时首先应根据传入的记录长度确定 分配内存的区间； 2 从该区间的空闲块链表中取第一个块，返回该空闲块的起始地址如果链 表为空，则返回表示空地址的标识，如c c + + 中的n u l l 。 回收也包括两个过程： 1 释放块空间时，提交释放空间的起始地址信息。根据该地址信息找到释 放空间所在的区间； 2 判断释放是否合法。如果合法，则将释放空间作为最后一个空闲块链入空 闲块链表，而不是作为第一个空闲块链在链表，这种做法能够大致保证内存管理 模块工作的起始阶段为连续插入的新记录分配连续的内存空间，遍历这些记录时 将发生更少的缺失。如图3 6 所示，使用将释放块链在空闲块链表尾部的策略， 空闲块的分配顺序为：2 0 、2 1 、3 1 、4 ；使用将释放块链在空闲块链表首 部的策略，空闲块的分配顺序为：4 、2 0 、2 1 、3 1 。为新插入的记录i 和 i + 1 分配内存，使用链在尾部的策略，记录i 存放在块2 0 ，记录i + l 存放在块 2 1 ，假设c a c h e 每次读两条记录，则依次访问记录i 和i + l 将发生1 次c a c h e 缺