（计算机科学与技术专业论文）分布式内存管理系统的设计与实现.pdf

塑! ! 室塑皇查兰塑丝壅 坌鱼苎宣童笪堡墨竺笪堡盐皇壅望 分布式内存管理系统的设计与实现 摘要 传统的大型数据文件一般存放在磁盘或者光盘等二级存储介质 上，其慢速的i 0 操作性能严重影响了c p u 的处理速度和效率，成 为整个系统的瓶颈。随着技术的进步，曾出现的非分布式内存数据库 管理技术，是利用数据库的缓存系统提高存取数据的，但由于其内存 资源有限，并且非动态分配，所以也不能从根本上解决这个系统的瓶 颈。本文提出一种分布式内存管理的体系结构分布式内存管理系 统( d i s t r i b u t e dm e m o r ym a n a g e m e n ts y s t e m ，以下简称d m m s ) ， 并在这个系统上实现了数据保护的协议机制，利用内存技术和网络技 术讨论从根本上解决这个瓶颈。 分布式内存管理系统的功能主要是提供给用户能够透明的使用 局域网上的内存资源，而且在使用内存资源的同时，用户可以享受高 可靠性的内存保护功能。对于整个系统的设计我们采取灵活的框架结 构，系统的各个部分功能相对独立，在实现中所用到的协议和算法都 封装起来，可以随时替换，以实现系统的高灵活性和可扩展性的特点。 d m m s 的分析、设计和实现都是基于中小企业的应用需求，即， 应用数据量不是很大；对应用数据的实时更新速度要求较高；应用数 据的用户访问量很大。 d m m s 设计中巧妙地利用了o s p f 的路由协议在思路上的优势， 利用分布式系统处理速度快的结构上的优点提出分布式内存管理系 统的体系策略和数据保护策略，利用d m m s 这种机制来克服磁盘阵 列存储数据的输入输出性能瓶颈从根本上解决了上述系统的问题。 d m m s 体系策略是将数据放到局域网的机器的内存中，来代替放到 传统的磁盘阵列存储介质中，直接利用内存读入读出数据，同时对这 种内存中的数据做一个保护备份机制，保证数据的安全。系统的处理 速度依赖于网络的带宽和内存处理数据的速度，对于现在的局域网中 的机器系统，网络的带宽和内存的效率都已经不是问题。相信在未来 不长的时间内，计算机工业的发展将使这种系统的性能提高更快。 本文给出了利用分布式内存管理策略实现的分布式内存管理系 北京邮电大学计算机应用实验室 塑j ! 室塑皇查兰堡圭堡塞 坌塑壅由鱼笪望至堕塑堡! 兰塞翌 统的分析设计思路和具体实现。第一章提出要解决的问题并给出文中 涉及到的技术理论，第二章进行系统的需求分析给出了系统中内存数 据的组织方式，第三章给出系统的设计和体系架构描述，第四章描述 系统实现，第五章记录系统实际运行情况，第六章提出需要进一步研 究的问题，最后结束语总结系统的开发，给出结论。 关键词分布式内存分布式内存管理系统包包管理实体自适 应机制 北京邮电大学计算机应用实验室 i l l 北京邮电大学硕十论文 分布式内存管理系统的设计与实现 d e s i g na n i ) i m p l e m e n t a t i o no fd i s t r i b u t e d m e m o r ym a n a g e m e n ts y s t e m a b s t r a c t a sl a r g es c a l ed a t ak e e pn o r m a l l yi nh a r dd i s ko rc o m p a c td i s c t r a d i t i o n a l l y i t ss l o wi os p e e dh a v ea f f e c t e dt h eh a n d l i n go fc p us p e e d a n de f f i c i e n c ys e r i o u s l ya n da l r e a d yb e c o m ee n t i r es y s t e m a t i cb o t t l e n e c k w i t 1t h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g ya n dm e m o r yt e c h n o l o g y p e o p l ea d o p tm a i nm e m o r yd a t a b a s et e c h n o l o g yt os t o r ed a t aw h i c hc a n n o ts o l v et h i sb o t t l e n e c kf r o mf o u n d a t i o ny e t t h i sp a d e rp u tf o r w a r da s t r a t e g yo fd i s t r i b u t e dm e m o r ym a n a g e m e n ts y s t e m ( d m m s ) t os o l v e t h i sp r o b l e mf r o mf o u n d a t i o n d i s t r i b u t e dm e m o r ym a n a g e m e n ts y s t e m i sa ni n t e r e s t i n ga v a i l a b l eo p t i o nt oi m p l e m e n tad i s t r i b u t e ds y s t e m ，g i v e s u s e r st r a n s p a r e n tu s eo fm e m o r yr e s o u r c e si nl o c a la r e an e t w o r k ，a n da t t h es a m et i m e ，u s e rc o u l da l s oe n j o yt h eh i g hr e l i a b i l i t yo fi t sm e m o r y p r o t e c t i o n i nd m m s e v e r yp a r ti sd e s i g n e dt ob ee n c a p s u l a t e da n d i n d e p e n d e n t ，s oi tc a nb es u b s t i t u t e da c c o r d i n gt or e q u i r e m e n t s t h u s d m m ss h o w sv e r yg o o df l e x i b i l i t ya n de x t e n s i b i l i t y a l lt h ea n a l y s i s ，d e s i g na n di m p l e m e n t a t i o no fd m m sb a s e do nt h e r e q u i r e m e n t so fm e d i u m s i z e da n ds m a l l s i z e dc o r p o r a t i o n s t h i sp a p e ri so r g a n i z e da sf o l l o w s c h a p t e r1 p u t sf o r w a r dt h e p r o b l e m ，c h a p t e r2c a r r i e st h r o u g hr e q u i r e m e n ta n a l y s i sa n db u i l d u pd a t a i nt h em a i nm e m o r y c h a p t e r3d e s c r i b e st h ed e s i g no ft h ed 删s a r c h i t e c t u r e ，c h a p t e r4d e s c r i b e st h ei m p l e m e n t a t i o no fd m m s ，c h a p t e r 5r e c o r d st h et e s t i n ga n dd e b u g g i n gd a t aa n dp r o v i d e st h en l n l l 毒n g e n v i r o n m e n to fd m m s c h a p t e r6p r o v i d e st h ev i e wo ff u r t h e rs t u d i e s a n di nt h ee n dw ed r a wac o n c l u s i o nt h a td si ss u c c e s s f u la n dh a sa g o o df u t u r e 北京邮电人学计算机应用实验室 北京邮电大学硕士论文 分布式内存管理系统的设计与实现 k e yw o r d sd i s t r i b u t e d m a i n ，m e m o r y d i s t r i b u t e dm a i n m e m o r ym a n a g e m e n ts y s t e m ( d m m s ) p a c k a g e m a i n m e m o r ym a n a g e m e n ts e l f - a d a p t e ds t r a t e g y 北京邮电大学计算机脚用实验室v 答辩程序 、答辩委员会秘书向会议介绍答辩委员会成员名单、职称。 二、答辩委员会土艚宣矾j 答i i t j l ：始。 三、秘粥向会议介“答7 i i t i j f 宄生的简历、学习成绩、谍程通过情况 以及是否有资格参加答辩。 四、答辩研究生报告论文的j i 要内容( 约 - - i - - 4 、i t , l - ) 。 五、答辩委员会提问题山答7 i 7 t i ) 1 - 究* - i - i e i 答。 六、答辩委员会召开秘密会议，对答辩成绩进行讨论和表决，进行 无 己名投票，经全体答辩委员的三分之二以上同意者为通过。 七、答辩委员会主席宣布对沦文的评语、成绩和表决结果。 塑j ! 皇塑皇查兰堡主堡奎 坌塑苎塑鱼笪墨墨竺塑堡生兰壅翌 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：韭日期：丝堕：! ：望 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校町以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：一矽 导师签名：堡! i 投 北京邮电大学计算机应用实验室 日期：竺：! ：兰2 ： 日期：211 ：! ! 兰2 1 1 问题的提出 第一章综述 传统的大型数据文件一般存放在磁盘或者光盘等二级存储介质上，在这样的 系统中，需要处理数据的时候，要先通过磁盘的摆臂操作到光盘或者磁盘阵列里 去寻找数据，然后把数据读入内存，再进行处理，这种机械的输入输出( i 0 ) 操作方式对于计算机高速的c p u 处理系统来讲严重影响了处理速度和效率，成为 整个系统的瓶颈。由于磁盘的u o 操作与系统c p u 的处理速度相差甚远，根本不 处于同一数量级，所以想通过简单地提高系统硬件的性能，使得磁盘操作的速度 加快，从而提高系统效率的解决方案不能解决以上问题。 另一种解决方案是使用传统的非分布式内存数据库技术，在这样的数据库 中，所有或者绝大部分数据都存放在内存中，数据访问速度大大提高，避免了磁 盘数据库操作中的很大一部分开销f 磁盘读写) ，大大地提高了处理速度，消除i o 瓶颈，以获得c p u 直接访问数据库数据的极高存取速度。由于这种系统的“工 作版本”( 当然也可以是整个数据库) 常驻内存，因此，它需要大容量内存提供 保证，虽然计算机技术的发展使存储器单位容量的价格不断下降，但是在现有条 件下，内存容量仍然无法满足传统的内存数据库应用对大容量内存的需求，于是 传统的非分布式内存数据库系统实质上是利用数据库的缓存系统提高存取数据 的，所以这种技术不能从根本上解决这个系统的瓶颈。 所以我们开始寻求新的解决方案，据调查研究分析发现，近几年来，随着计 算机工业的迅猛发展，内存技术和网络技术也都随之取得了显著的进展，计算机 内存的容量正在以惊人的速度增加，价格也越来越便宜。网络技术也发生了显著 的变化，网络带宽、速度都得到了大幅度的提高。文献【5 】【6 】【7 的研究表明，目 前在高速局域网络中对网络主机内存c a c h e 的存取速度已经高于直接存取本机 硬盘速度，是后者的2 到1 0 倍。而且，内存和网络技术这两个方面的发展势头 依然强劲。与此同时，基于内存和网络技术的分布式技术也己成为计算机技术发 展中的一个重要方面和研究热点之一。分布式计算机系统具有很多优点，如：坚 定性强、扩充容易、可靠性好、维护方便和效率高等。所以我们想要利用分布式 技术和内存数据库技术各自的优点提出一种新的解决方案，即：分布式内存管理 北京邮屯大学计算机应用实验室1 塑韭室业皇犬兰堡主堡苎坌查茎堕查笪型墨竺塑堡盐! 壅墨 系统策略。 据调查研究，目前在已有条件下开发的分布式内存管理系统的实际应用比较 符合中小企业的实际的需求。首先，中小企业具有这样的特点：中小企业的应用 数据量不是很大；对应用数据的实时更新速度要求较高；应用数据的用户访问量 很大。其次，在现有技术水平的前提下，计算机系统本身存在着相当程度的不稳 定性，如经常可能发生电源和网络的中断。基于以上两点对实际应用的考虑，本 课题的实际设计开发就以上述中小企业的需求为基础来设计实际应用的系统。 即：本课题目前要实现的系统是基于中小企业的应用需求，研究分布式内存管理 系统在实际中应用于上述中小企业的局域网系统中，使用何种协议和策略进行设 计和实现一个系统，来提高中小企业系统的性能和资源利用率。 本课题巧妙的利用了o s p f 的路由协议思路上的优势，利用分布式系统处理 速度快的结构上的优点提出分布式内存管理系统( d i s t r i b u t e dm e m o r y m a n a g e m e n ts y s t e m ，以下简称d m m s ) 的策略来从根本上解决上述问题，利用 d m m s 这种机制来克服磁盘阵列存储数据的输入输出性能瓶颈。d m m s 体系策 略是将数据放到局域网的机器的内存中，来代替放到传统的磁盘阵列存储介质 中，直接利用内存读入读出数据，同时对这种内存中的数据做一个保护备份机制， 保证数据的安全。系统的处理速度依赖于网络的带宽和内存处理数据的速度，对 于现在的局域网中的机器系统，网络的带宽和内存的效率都已经不是问题。相信 在未来不长的时间内，计算机工业的发展将使这种系统的性能提高更快。 为了提高本系统的通用性，我们对d m m s 整个系统的设计，都采取了灵活 的框架结构，系统的各个部分功能相对独立。在实现中，又把用到的协议和算法 都封装起来，保证每部分的独立性，这样就可以随时替换各部分协议和算法，以 实现系统的高灵活性和可扩展性的特点。正是由于系统中用到的协议和策略都是 灵活可替换的，所以可以随时根据实际应用对系统不同的需求，对系统体系进行 算法和协议替换，使系统满足不同应用的需求。 1 2 技术背景 本课题的研究涉及到很多方面的热点技术，如，分布式计算技术，内存数据 库技术，网络数据库技术，分御式数据库设计实现技术，内存管理的策略，网格 计算技术以及路由算法协议标准等各个方面。下面简要地介绍最主要的几个方面 的技术背景，分别为：分布式计算技术，内存数据库技术，内存管理策略，分布 北京邮电大学汁算机应用实验室 璺i ! 室塑皇盔兰堡主堡苎 坌塑苎立查笪墨墨堕塑堡生兰塞型 式数据库技术，路由算法_ 二一开放最短路径优先算法( o s p f ) 。它们的研究现状 和发展状况如下。 1 2 1 分布式计算技术 1 2 1 1 分布式系统概述 分布式系统的大致描述是：个分布式系统是一些独立的计算机的集合，但 是对这个系统的用户来说，系统就像一台计算机一样。 在客户机朋艮务器结构兴起之后，许多系统便是用这种结构来设计。随着客 户机服务器结构技术的成熟，使用这种结构的应用系统也执行得非常的平顺。 这种结构本身也包含了一些问题，比如当这种结构经常把应用系统的企业逻辑编 写在客户端的应用程序之中，因此当应用系统需要改变时，所有在客户端的应用 程序都必须改变，这对于系统的维护来说成本太高了。虽然有一些企业把系统逻 辑改写在数据库之中，但是这样的机构有更大的问题，因为如此一来不但应用系 统都绑死在特定的数据库上，此外许多应用逻辑的程序代码并不适合在数据库之 中执行，因为使用大量计算的程序代码会严重的拖累数据库的执行效率。 为了解决这些重复开发应用系统的成本以及为了增加应用系统的重复使用 性，分布式计算结构在这些方面克服了这些问题，发挥面向对象分析面向对象 设计的功能，解决了传统的客户机服务器结构存在的问题。采用这种包含应用 程分布式计算结构有许多的好处，除了可以增加企业对象的重复使用性之外，整 个系统的开发和维护成本都立刻的降低下来了。因为整个应用系统的执行是分成 数个不同的部分并且执行在不同的机器之中。 由于分布式结构把系统不同的运作部分分布式在独立的机器之中，所以整个 应用系统的延展性也大为提升。分布式应用系统强调系统的稳定性，延展性以及 执行效率。所以现在有许多的分布式应用系统提供了容错能力以及负载平衡的能 力。在具备容错能力和负载平衡的能力的分布式应用系统中，主要是在应用程序 服务器部分提供多台不同的应用程序服务器，当客户端应用程序或是w e b 服务器 需要使用企业对象的服务时，可以依据目前每一台应用程序服务器的负荷以及是 否可以提供服务的情形来动态决定连接到哪一台应用程序服务器之中。 1 2 1 2 分布式计算使用的技术 目前分布式结构使用的核心大致上可以分别两种不同的工业标准，第一种是 m i c r o s o f t $ 1 j 定的c o m d c o m 以及c o m + ，第二种则是由7 0 0 多个厂商共同提倡的 c o r b a ( c o m m o no b j e c tr e q u e s tb r o k e ra r c h i t e c t u r e l 。由于分布式结构的广为流 北京邮电大学计算机应用实验室 塑j ! 室塑皇查兰堡主堡苎坌塑苎塑查笪堡墨篓塑堂! 皇壅塑 行，所以现在也有愈来愈多酌分布式技术是根据这两种分布式核心技术再加以演 进而产生的，例如e j b ( e n t e r p r i s ej a v a b e a n ) 等。 12 1 3 分布计算技术的发展历程 分布计算( d i s t r i b u t e dc o m p u t i n g ) 技术是近2 0 年来影响计算技术发展的最活跃 因素之一。从8 0 年代中期开始至今，分布计算技术己经走过了第一代，目前正处 于第二代的成熟期，并且开始孕育第三代( 参见表l 一1 ) 。 第一代第二代第三代 ( 8 0 年代中至9 0 年代初)( 9 0 年代)( 2 0 0 0 年以后) 面向的丰要问信息共享异构环境下的智能化的协同工 题应用互操作作 体系结构经典的客户服务器计算面向对象的多 自主的多a g e n t 模型层客户服务器模型 计算模型 关键技术特点运用传统的计算概念和将面向对象技 面向a g e n t 的拟 设施( 如过程调用和文 术应用于分布人化的交互环境 件1 计算 表1 1 分布计算技术发展的三个阶段 1 2 14 分布式系统设计的要点 分布式系统设计的要点主要集中在以下五点：透明性，灵活性，可靠性，性 能，可伸缩性。 第一，透明性( t r a n s p a r e n c y l 透明度可分为两个级别：最容易做到的就是对用户隐藏系统的分布性。例如， 当一个u n i x 用户键入m a k e 命令来重新编辑一个目录中的大量文件时，他并不需 要知道所有编辑是在不同计算机上并行处理的，也不需要知道他使用了大量的文 件服务器。对用户而言，唯一不寻常的是系统的性能部分损失了。就终端的命令 发布和结果显示而言，可以将分布式系统建成像一个单处理机系统一样。 透明的概念适用于分布式系统的多个方面，如表1 2 所示。 1 种类含义 位置透明用户不知道资源位于何处 迁移透明资源可以不改名的随意移动 复制透明用户不知道有多少个拷贝存在 并发透明多个用户可以自动地共享资源 并行透明系统活动可以在用户没有感觉的情况下并行发生 北京邮电大学计算机应用实验室 表1 2 分布式透明的种类和含叉 北京邮电人学硕上论文 分布式内存管理系统的故计与实现 位置透b ( 1 0 c a t i o nt r a n s p a r e n c y ) 是指在一个真正的分布式系统中，用户不知 道硬、软件资源如c p u 、打印机、文件和数据库的位置。资源的名字不应隐含有 资源的位置信息。迁移透明( m i g r a t i o n t r a n s p a r e n c y ) 是指资源无需更名就可自由地 从一地迁往另一地。如果分布式系统是复制透明( r e p l i c a t i o n t r a n s p a r e n c y ) 的，操 作系统可以随意地为文件和其他资源进行附加拷贝而无须用户知道。分布式系统 通常有多个独立的用户。当两个或多个的用户试图在同一时间访问相同的资源 时，系统应该怎么办呢? 如果系统是并发透明( c o n c u r r e n c yt r a n s p a r e n c y ) 的，任一 用户不会发现其他用户的存在。获得这种透明类型的机制是：一旦某个用户开始 使用一个资源时，系统就自动锁定此资源，直到该用户使用完后再解锁。而在这 种方式下，所有资源只能串行使用，而决不是并发使用的。 第二，灵活性 设计的第二个关键问题是灵活性。有关分布式系统结构的观点有两种：一种 观点认为，每台机器都运行一个传统的内核，内核自身提供了大多数的服务；另 外一种观点认为是内核应尽可能少地提供服务，大量的操作系统服务可从用户级 服务器上获得。这两种模型分别称为单内核( m o n o l i t h i ck e r n e l ) 和微内核( m i c r o k e r n e l ) 。 单内核基本上是目前的集中式操作系统，增加了网络功能和远程服务集合。 大部分系统调用都通过陷阱到达内核，在内核中完成所需要的工作，然后内核再 将所要求的结果返回给用户进程。使用这种方法，大部分机器都拥有自己的磁盘， 也能够管理自己本地文件系统。 微内核具有更好的灵活性，因为它几乎不作什么，只提供四种最小的服务： ( 1 ) 进程间通信机制； ( 2 ) 某些内存管理功能； ( 3 ) 少量的底层进程管理和调度； ( 4 ) 底层输入输出服务。 具体说，微内核与单内核不同，它不提供对文件系统、目录系统、整个进程 管理，或许多系统调用的处理。微内核中提供的服务包括那些因为在其他地方提 供它们很困难，或因为代价昂贵的服务。主要目的是让它保持小。许多其它的操 作系统服务都作为用户级服务器来实现，如找一个名字、读文件或获得其他服务， 用户都是发送消息给适当的服务器，由这个服务器完成相应的工作并返回结果。 这种方法的优点是高度的模块化，对于每一个服务( 服务器能理解的消息的集合) 北京邮电大学计算机应用实验室 塑! ! 室业皇盔兰堡丝壅坌鱼塞堕壹篁堡墨竺塑堡生皇塞翌 都有一个定义好的接口，每一个服务程序对所有客户来说都是可以访问的，且和 位置无关。另外，该系统易于实现、安装和调试新的服务程序，因为增加或改变 一个服务程序不需要象有一个单内核那样停止系统和启动一个新的内核。正是因 为它所具有的添加、删除和修改服务的功能使得微内核具有很高的灵活性。此外， 用户如不满意一个通用的服务程序，也可以编写自己的服务程序来替代它。 单内核系统唯一潜在的优点是性能。使用内核陷阱并且在其上执行工作要比 给远程服务器发消息更快。 第三，可靠性 建立分布式系统的最初目的之一就是使系统比单处理机系统更靠。一个高度 可靠的系统必须有高可用性，但仅仅如此并不够。存储在和进入系统的数据不能 丢失或以任何方式混淆。如果文件冗余地存放在多个服务器上，那么所有备份都 必须保持一致。一般来说，保存的备份越多，可用性越好，但不一致的可能性却 越大，特别是在频繁进行修改的情况下更是如此。 整体可靠性别的方面还有安全性和容错。总的来说，分布式系统能设计成可 以屏蔽错误，也就是对用户隐藏错误。如果一个文件服务或其它服务实际上是有 一组紧密协同工作的服务器构成，它应该能够采用这样一种结构，即用户不会意 识到损失了一个或两个服务器，而只是感到些性能上的降低。 第四，性能 如果建立了一个透明、灵活和可靠的分布式系统，但是运行速度却非常慢， 那么它没有什么实际的用处。如果在分布式系统中运行一个具体的应用，它的速 度不应该比在一个单处理机运行同一个应用慢。可以使用不同的性能标准进行衡 量。其中之一是响应时间，还有吞吐量( 每小时完成的工作量) 、系统的利用率和 网络容量消耗程度。 第五，可伸缩性 适用这一规模的分布式系统不一定就适合别的规模的系统。所以可伸缩性对 于分布式系统的设计也非常重要。于是必须避免该种方法：从所有地点收集信息， 把这些信息送到单个机器上去处理，然后发布结果的算法。只有分布式算法可阻 使用。这些算法与集中式算法比较，其特点如下： ( 1 ) 没有一台机器上存放关于系统状态的全部信息； ( 2 ) 机器只是基于本地信息做出决定； 北京山拄电大学计算机应用实验室 北京邮电人学硕l 论史 分布式内存管理系统的设计与实现 ( 3 ) 一台机器出故障不会破坏算法； ( 4 ) 不一定存在全局时钟。 综上所述，我们开始看到分布式系统的优点正是我们系统需要的，所以我们 的设计主要考虑以上分布式系统的可靠性，性能特点和可伸缩性来设计我们的系 统的局域网部分，透明性和灵活性在d m m s 系统中我们采用智能客户端这个实体 来实现这两个特点。 1 2 2 内存数据库技术 内存数据库( m a i nm e m o r yd a t a b a s e ， 对什么是内存数据库有几种不同的说法， 观点一，整个数据库全部常驻内存， 存足够大，以容纳数据库的所有数据。 简称m m d b ) 是一个较新的研究领域 存取数据时无须i o 操作。这就要求内 观点二，数据库常驻磁盘，在事务执行前将所需数据集调入内存，提交时所 有对数据库的修改必须写回磁盘。 观点三，数据库常驻磁盘，在内存中开辟一个大缓冲区f 或c a c h e ) ，通过适 当的缓冲管理以减少内外存i o 操作。 目前，大多数内存数据库都是基于第一种观点的。然而在很多现实应用中， 往往难以保证内存总是能够容纳整个数据库。因此，内存数据库的含义必须包含 内存不足以容纳整个数据库的情形。所以我们认为，内存数据库的本质特征是其 主拷贝或“工作版本”常驻内存。内存数据库的定义不应涉及内存的大小、i o 次数及数据被调入内存的时机等。据此，我们给出如下定义。 定义：设有数据库d b ，d b m ( f ) 是f 时亥i d b 在内存中的数据集，d b m ( 订 是d b 的子集；t s 为所有事务的集合，4t ( ，) 是r 时刻的活动事务集，爿r ( 幻 是，s 的子集：pt 4t ( o ，d t ( 丁) 为丁在t 时刻的操作数据集，d t ( r ) 是d b 的子集；若在任一时刻f ，均有：pte at ( 0 ，d t ( r ) 是d b m ( n 的子集成立， 则称d b 为一个内存数据库，简记为m m d b 。 按此定义，m m d b 的“工作版本”( 当然也可以是整个数据库) 常驻内存， 任何一个事务在执行过程中没有内外存间的数据i o 。显然，它需要一定的内存 容量，但并不要求整个数据库都必须常驻在内存。需要指出的是，传统的磁盘数 据库即使缓冲区足够大，以致可以容纳所有数据也不能算是一个m m d b 。 北京邮电大学计算机心用实验室 因为它是针对磁盘特性、在数据库常驻磁盘的假定下设计的。例如，索引结 构还是针对磁盘存取的，数据的存取仍必须经过缓冲区管理等。内存数据库的组 织与管理要求新的适于内存特点的数据结构和算法，对于数据的组织与安置、数 据库存取、内外存数据交换、查询处理及优化、并发控制及数据库恢复都需要研 究新的策略与机制( m m d b ) 。 随着存储器芯片集成度的提高和造价的降低，内存数据库( m m d bm a i n m e m o r yd a t a b a s e ) 有了更大的发展空间，目前，内存数据库已经成为实时数据 库系统发展的主要方向之一。由于内存数据库中的事务本身往往不涉及i p o ，因 此内存数据库往往能比磁盘数据库提供更快速的数据响应和更高的事务吞吐量。 但出于主存中信息的易失性，在系统出现故障时，内存数据库中的数据将丢失， 为此，内存数据库必须提供高效、可靠的恢复机制以使在发生系统故障的时候能 将数据库恢复，通常内存数据库采用检查点和日志的方法来实现系统恢复。 但是，在实际中内存数据库没有得到广泛的应用，其原因与内存数据库中涉 及到的其他技术发展状况有关。其中最重要的就是高可用性系统技术。所谓高可 用性系统( h i g ha v a i l a b i l i t ys y s t e m ，简称h a 系统) 是指通用的计算机，通过对关键 的软件失效部件进行冗余，结合对失效的有效探测和恢复，提供了一个可靠的计 算环境。高可用性系统的性能价格比优于传统的容错机，不仅对硬件错误、操作 系统和数据库错误有良好的容错能力，而且还能够检测应用软件的错误。常见的 失效因素有以下几个方面：提供服务的主机挂起、关机或不可用；连接用户和服 务器的网络失效：用户试图访问的服务器上的应用不能正确工作、挂起或离线： 用户试图访问的工作站上的应用不能正确工作、挂起或离线；服务器提供的数据 服务已经离线。 由于内存数据库系统中总有一些数据暂存在内存中，没有高可用性的保证， 出现上述任何一种失效时，都将造成数据的不完整。所以我们研究我们的分布式 内存管理系统，利用分布式系统可靠性的特点来进行数据的保护和恢复工作，来 弥补内存数据库技术的不足，设计我们的d m m s 系统。 1 2 3 内存管理策略 内存是计算机中仅次于c p u 的第二重要资源，它是用来存贮、交换数据等 重要信息的场所，因此对内存的利用和管理成为计算机管理中非常重要的课题。 既然内存作为系统的存储介质，作用十分重要，那么内存管理也是操作系统五大 管理中的重点。因此了解内存配置，充分利用内存资源，如何管理内存成为设计 中很重要的一个方面。这里先介绍通用操作系统中的内存管理技术，然后简要描 北京邮电大学计算机麻用实验室 塑! ! 室塑皇奎兰堕主鲨茎坌塑茎由堡笪里至堕盟堡生兰塞翌 述本文考虑到的内存管理的策略。 1 2 3 1 通用操作系统的内存管理 由存储单元( 字节或字) 组成的一维连续的地址空间，简称内存空间。内存 空间用来存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的、 办即程序计数器所指的存储器，分为：系统区和用户区。系统区是用于存放操作 系统：用户区是用于装入并存放用户程序和数据。 第一，内存管理的任务 在理想的情况下，每个应用都会喜欢的是无穷大、快速并且内容不易变( 即 掉电后内容不易丢失) 的存储器，同时又希望它是廉价的。但不幸的是，当前的 技术没有能够提供这样的存储器，因此大部分的计算机都有一个存储器层次结 构，它由少量的非常快速、昂贵、易变的高速缓存( c a c h e ) ，数十或数百兆字节的 中等速度、中等价格、易变的主存储器( r a m ) ，和数十吉字节的低速、廉价、不 易变的磁盘组成。操作系统的工作就是协调这些存储器的使用。而实际上，通用 的操作系统都是在运行期间将进程在主存和磁盘之间移动的系统，也就是说，存 储器的管理主要是内存的管理。 ( 1 ) 内存空间的管理、分配与回收。内存分配：静态方式与动态方式。 ( 2 ) 存储共享：是指两个或多个进程共用内存中相同区域。 第二，分区存储管理方案 ( 1 ) 分区分配：系统把内存用户区划分为若干分区，分区大小可以相等，也可以 不等。一个进程占据一个分区，分区分配分为固定分区和可变分区。 固定分区：预先把可分配的内存空间分割成若干个连续区域，每一区域称 为分区。每个分区的大小可以相同也可以不同，分区大小固定不变，每个分区装 一个且只能装一个作业。优点是管理方便，算法简单；缺点是内存管理浪费大( 大 作业放不下，小作业占大空间) 。 可变分区的基本思想是：内存不是预先划分好的，作业装入时，根据作业 的需求和内存空间的使用情况来决定是否分配，若有足够的空间，则按需要分割 一部分分区给该进程；否则令其等待内存空间。 ( 2 ) 分配分区时需要考虑的问题 首先，是动态分配的三种分配算法：首先适配、最佳适配、最差适配。其次， 北京邮电大学计算机心用实验室 9 北京邮电大学顺士论文分布式内存管理系统的设计与实现 内存回收：当某一块归还后，前后空间合并，修改内存空闲块表。最后是“碎片” 问题：经过段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个 都很小，彳i 足以满足分配要求，但其总和满足分配要求。这些空闲块被称为碎片。 碎片造成存储资源的浪费。通常的解决方法是采用紧凑技术，即通过在内存移动 程序，将所有小的空闲区域合并为大的空闲区域。在进行页面替换时不能换出处 于等待v o 状态的进程，有些v 0 进程因d m a 而不能换出内存或换出前需要操作 系统的特殊帮助。 第三，覆盖技术与交换技术 覆盖技术与交换技术是在多道环境下扩充内存的方法，用以解决在较小的存 储空间中运行较大程序时遇到的矛盾。覆盖技术主要用在早期的操作系统中，交 换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现。交 换技术与覆盖技术共同点：进程的程序和数据主要放在外存，当前需要执行的部 分放在内存，内外存之间进行信息交换。覆盖技术是把程序划分为若干个功能上 相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同 一块内存区域。程序段先保存在磁盘上，当有关程序段的i j 仃一部分执行结束，把 后续程序段调入内存，覆盖前面的程序段( 内存“扩大”了) 。一般要求作业各模 块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后由由操作系统完 成自动覆盖。该方法的缺点是：对用户不透明，增加了用户负担。 交换技术是当内存空间紧张时，系统将内存中某些进程暂时移到外存，把外 存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与外存 之j 1 日j 的动态调度，多用于分时系统中。交换技术要实现的几个问题如下： ( 1 ) 选择将哪个进程换出内存。 ( 2 ) 交换时机的确定：通常有两种方法来确定交换时机，即，只要不用就换出( 很 少再用) 和只在内存空间不够或有不够的危险时换出。 ( 3 ) 交换时需要做的工作：需要一个足够大的磁盘交换区以存放所有用户程序的 所有内存映像的拷贝；必须对这些内存映像的可以直接存取。 ( 4 ) 换回内存时位置的确定：页面换出后再次换入内存的位置是否一定要在换出 前的位置上，受地址“绑定”技术的影响，即绝对地址产生时机的限制。与覆盖 技术相比，交换技术不要求用户给出程序段之间的逻辑结构；而且，交换发生在 进程或作业之间，而覆盖发生在同一进程或作业内。此外，覆盖只能覆盖那些与 北京邮电大学计算机应用实验室 堂! ! 室塑皇叁堂婴生笙兰坌鱼茎由鱼筻堡墨堕塑堡堡量兰型 覆盖段无关的程序段。 第四，虚拟存储 在程序执行时，往往会出现程序长度大于内存容量的问题，由于程序暂时不 执行或运行完时没有必要占用内存，因此，产生了操作系统中的虚拟存储技术， 即以c p u 时间和外存空间换取昂贵内存空间。基本思想是：程序、数据、堆栈 的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把 其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换。 实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外 存，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作。 虚拟页式存储管理的基本思想和设计如下： ( 1 ) 基本思想：在进程开始运行之前，不是装入全部页面，而是装入一个或零个 页面，之后根据进程运行的需要，动态装入其它页面：当内存空间己满，而又需 要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。 ( 2 ) 页表表项设计：据需要进行设计。 ( 3 ) 缺页中断( p a g ef a u l t ) 处理：首先，在地址映射过程中，在页表中发现所要访 问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中 断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下 去。其次，如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页 表中相应页表项目的驻留位及相应的内存块号。最后，若此时内存中没有空闲块， 则要淘汰某页，若该页在内存期问被修改过，则要将其写回外存。 ( 4 ) 页面淘汰算法： 理想淘汰算法最佳页面算法( o p t ) ：淘汰以后不再需要的或最远的将 来才会用到的页面。这种算法实际上是不可实现的，因为无法界定哪一个 页面是真正满足要求的。 先进先出页面淘汰算法( f i f o ) ：选择在内存中驻留时间最长的页并淘汰 之。 第二次机会淘汰算法( s c r - s e c o n dc h a n c e ) ：按照先进先出算法选择某一页 面，检查其访问位，如果为0 ，则淘汰该页，如果为1 ，则给第二次机会， 并将访问位置。 北京邮电大学计算机应用实验室 圆北京邮电大学硕十论文分布式内存管理系统的设计与实现 最近未使用页面淘汰算法( n r u i n o tr e c e n t l yu s e d ) ：选择在最近一段时间 内未使用过的一页并淘汰之。 最近最久未使用页碰淘汰算法( l r u l e a s tr e c e n t l yu s e d ) ：选择最后一次 访问时间距离当前时间最长的一页并淘汰之，即淘汰没有使用的时间最长 的页。 最不经常使用( n f u n o tf r e q u e n t l yu s e d ) ：选择访问次数最少的页面淘汰 之。 i 2 3 2 内存管理的几种策略 内存经过一个历史的演变过程，从只有6 4 k b 的可访问内存发展至现在的几 百几千m b 。为了有效地利用内存，进而提高计算系统的效率，本文在设计中主 要侧重对以下集中内存管理策略进行考虑。 ( 1 ) 尽量扩大常规内存策略； ( 2 ) 利用虚拟存储技术进行数据在内存外存间换入换出策略； ( 3 ) 利用覆盖技术解决程序容量超过实际主存的程序运行策略； ( 4 ) 利用交换技术来解决内存不足策略； ( 5 ) 利用“空洞”内存建立高速磁盘缓存策略； ( 6 ) 减少不必要的内存常驻程序驻留内存策略。 本课题是针对内存管理的特点，并根据以上几种策略的考虑，来设计d m m s 系统，管理好系统内计算机的内存资源，提高内存的利用率。 1 2 4 分布式数据库技术 12 41 分布式数据库系统概述 数据库系统是针对文件系统缺乏数据共享和对数据的集中统一管理而提出 的。数据库对数据的管理具有持久性、有效性和共享性的特点，极大地减少了数 据的冗余，消除了数据不一致性的隐患，提高了存储和查询效率。然而，随着计 算机技术的发展，人们期望着符合现实需要、能处理分散地域、具备数据库管理 特点的新的数据库系统的出现。因此，人们以“数据库系统+ 计算机网络”的构 想来实现分布式数据库系统。 下面我们来看看分布式数据库系统的定义，分布式数据库系统包两个重要的 北京邮电大学计算机应用实验室 2 塑韭室塑皇查兰塑堡苎坌塑茎塑查笪堡墨竺塑堡生皇窭墨 成分：分布式数据库和分布式数据库管理系统。分布式数据库( d i s t r i b u t e dd a t a b a s e ，d d b ) 是一组数据集，逻辑上它们属于同一系统，而物理上它们分散在用 计算机网络连接的多个场地上，并统一由一个分布式数据管理系统管理。 分布式数据库系统( d i s t r i b u t e dd a t ab a s es y s t e m ，d d b s ) 是面向地理上分散， 而管理上又需要不同程度集中管理的企业、事业单位提供数据管理的信息管理系 统。它负责管理分布环境下逻辑集成数据的存取、一致性、有效性和完整性等。 同时，在管理机制上还必须具有计算机网络通讯协议上的分布管理特性。 分布式数据库系统的特点主要有如下方面： ( 1 ) 位置透明 数据库系统的应用程序和用户在访问数据时，不必知道与操作有关的数据存 储和处理的具体地点，即是在哪些数据库服务器上以及它们的物理位置和网络地 址等。 ( 2 ) 结点自治性 构成分布式数据库的每一个物理数据库都是独立的，可以由数据库管理员分 别进行管理，如同一个非网络本地数据库。 ( 3 ) 分布数据操作 分布式数据库的体系结构支持全部数据库操纵语言，包括对远程数据库数据 的查询、插入、更新和删除等，并且可以将本地数据库和远程数据库的关联操作， 定义为一个事务，系统会自动维护其一致性和完整性。 “) 分阶段事务提交机制 能够提供与非分布式数据库环境一样的数据一致