（计算机应用技术专业论文）实时系统的内存管理技术研究与实现(1).pdf

电r 科技大学硕i ：学位沦文实时系统的内存管理技术研究与宴现 摘要 随着实时系统的功能日益强大，应用成本的逐渐降低，实时系统在许多领域 已经得到了广泛应用。在传统的实时系统中，通常都没有使用虚拟内存技术，这 是因为虚拟内存技术涉及到页面i o 操作，使得时间性能分析非常困难。然而在现 在的安全关键实时系统中，越来越多的应用要求将不同关键级别的任务运行在同 个处理器上，因此我们希望能为软实时任务提供虚拟地址空间以提高灵活性， 同时也为硬实时任务提供可预测及高效的地址翻译。另外，为了让不同关键级别 的应用程序能够安全地共存，实时系统必须能够在空间和时间上对这些应用程序 进行恰当的隔离以保证资源的安全可用性，而通过使用虚拟内存技术和空间域保 护技术则可以有效地提供对这种隔离机制的支撑。 本文主要研究了实时系统中的虚拟内存技术以及空间域保护机制。通过比较 等价单地址宅间、单地址空间和多地址空间三种不同的地址空间的优缺点，我们 提出了一种组合的内存模型，使之不仅提供了虚拟内存，同时也可以很好地支持 实时地址空间，优化了实时环境的性能。在实时系统中，t l b 查找失败带来的时 间开销对系统的整体性能有非常大的影响，因此我们探讨了使用软件来有效地管 理t l b 的各种策略。另外，作为系统防危的重要机制之一，空间域保护技术已经 成为安全关键实时系统设计思想的一部分，本论文对这项技术在实时系统中的实 现做了详细的研究与讨论。最后，基于实时操作系统c r t o s i i ，我们完成了内存 管理系统的详细设计与实现，测试结果表明该系统能够同时支持实时环境和虚拟 内存。 【关键词】安全关键实时系统组合内存模型实时地址空间空间域保护 皂量! 垫查兰堡圭堂皇堡塞= = 窒堕墨竺竺塑童篁些垫查婴塞兰窒! 些 a b s t r a c t d u et ot h ef u n c t i o ne n h a n c e m e n to fr e a l t i m es y s t e ma n dt h ed e c r e a s eo fi t sc o s t ， t h er e a l - t i m e s y s t e m h a sb e e nm o r ea n dm o r e w i d e l y u s e di n m a n y f i e l d s c o n v e n t i o n a l l y ，t h eu s eo fv i r t u a lm e m o r yh a sb e e na v o i d e di nt h er e a l t i m es y s t e m s ， b e c a u s ev i r t u a lm e m o r yl e a d st ot h ei 0 o p e r a t i o nt h a tw i l lm a k et h et i m i n ga n a l y s i s v e r yd i f f i c u l t h o w e v e r , w i t h i ns a f e t y c r i t i c a ls y s t e m s ，t h e r e i sm o v et o w a r d s i m p l e m e n t a t i o n sw h e r et a s k so fd i f f e r i n gi n t e g r i t y l e v e l sa r ea l l o c a t e dt ot h es a m e p r o c e s s o r t h u si nt h es a m es y s t e m ，w eh o p et oo f f e rv i r t u a la d d r e s ss p a c ef o rs o f t r e a l t i m et a s k st or a i s et h e i rf l e x i b i l i t y , m e a n w h i l eo f f e r i n gt h ep r e d i c t a b l ea n de f f e c t i v e a d d r e s st r a n s l a t i o nf o rh a r dr e a l t i m es y s t e m s i na d d i t i o n ，i no r d e rt oe n a b l et a s k sw i t h d i f f e r i n gi n t e g r i t y l e v e l st os a f e l yc o e x i s ti nt h es a m es y s t e m ，r e a l t i m es y s t e mm u s t o f f e ra d e q u a t ep a r t i t i o n i n gt oe n s u r et h es a f ea v a i l a b i l i t yo ft h er e s o u r c e s t h r o u g ht h e u s a g eo fv i r t u a lm e m o r ya n ds p a c ed o m a i np r o t e c t i o nt e c h n o l o g y , w ec a r le f f e c t i v e l y s u p p o r tt h es e p a r a t i o np a r t i t i o n i n gm e c h a n i s m t h i sp a p e ri sf o c u s e do nt h er e s e a r c ho fv i r t u a lm e m o r yt e c h n o l o g ya n ds p a c e d o m a i np r o t e c t i o nm e c h a n i s mi nr e a l - t i m es y s t e m s t h r o u g ht h ec o m p a r i s o no ft h e a d v a n t a g e sa n dd i s a d v a n t a g e so ft h r e ed i f f e r e n ta d d r e s s i n gs p a c e ( t h ee q u a ls i n g l e a d d r e s ss p a c e ，t h es i n g l ea d d r e s ss p a c ea n dt h em u l t i p l ea d d r e s ss p a c e ) ，w ep r e s e n ta c o m b i n e dm e m o r ym o d e lw h i c hc a no f f e rv i r t u a l m e m o r ym e c h a n i s m ，m e a n w h i l e s u p p o r t i n g t h er e a l t i m ea d d r e s s s p a c e ，o p t i m i z i n g t h e p e r f o r m a n c e o fr e a l t i m e e n v i r o n m e n t i nr e a l - t i m e s y s t e m s ，t h e t i m eo v e r h e a dc a u s eb yt l bf a i l u r ew i l l s i g n i f i c a n t l ya f f e c tt h eo v e r a l lp e r f o r m a n c eo f t h es y s t e m ，t h u sw es t u d i e dt h es t r a t e g y o f t l bs o f t w a r em a n a g e m e n tt os o l v et h i sp r o b l e m i na d d i t i o n ，a so n eo f t h e i m p o r t a n t m e c h a n i s m so fs y s t e ms a f e t y , s p a c ed o m a i np r o t e c t i o nh a sb e e np a r to ft h ed e s i g n t h e o r yf o rs a f e t y - c r i t i c a lr e a l - t i m es y s t e m ，t h i sp a p e rr e s e a r c h e dt h ei m p l e m e n t a t i o no f t h i st e c h n o l o g yi nr e a l t i m es y s t e m s l a s t , b a s e do f ft h er e a l - t i m es y s t e mc r t o s i i ，w e h a v ef i n i s h e 6t h ed e t a i l e dd e s i g na n di m p l e m e n t a t i o no fam e m o r ym a n a g e m e n t s y s t e m ， t h et e s tr e s u l ts h o w st h a tt h i ss y s t e mc a ns i m u l t a n e o u s l ys u p p o r tr e a l - t i m ee n v i r o n m e n t a n dv i n u a im e m o r y 【k e yw o r d s a f e t y c r i t i c a lr e a l - t i m es y s t e m s c o m b i n e d m e m o r y m o d e l r e a l t i m ea d d r e s ss p a c e s p a c e d o m a i n p r o t e c t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教 育机构的学位或证书而使用过的资料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 签名日期：跏毕年哆月蚜日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被蠢阅 和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数 据库进行查阅，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名导师签名：藿彬 ：鳇冽节 日期龇每年碜月2p 电r 科技大学颤卜学位硷义 实时系统的内存管理技术 ! j 1 = 究与贸现 1 1 概述 第一章绪论 二十世纪七十年代以来，实时计算机系统被越来越广泛地用来监视和控制与 人类生活相关的一些物理过程。这些计算机系统监视其外部物理过程的变化，并 根据变化产生控制指令，引导物理过程按照正确的方式运转。典型的应用包括飞 行器和航天器的控制系统、汽车电子系统、工业过程控制系统、电站控制系统、 危重病人的生命维持系统、通信系统以及目前正在大规模兴起的消费类电子产品。 实时系统的正确性依赖于运行结果的逻辑正确性和运行结果产生的时间正确性， 即实时系统必须在规定的时间范围内正确地响应外部物理过程的变化。 随着实时系统的功能日益强大，应用成本的逐渐降低，实时系统在其应用领 域中所处地位迅速提高。目前，大量的实时系统作为安全关键系统的核心在运行 着。显然，如果实时系统无法满足设计要求的运算结果的逻辑正确性和时间正确 性，将造成重大的财产损失，甚至人身伤害，导致灾难性的后果。从以下的事例 中可以看出，实时系统的运行失败给人类生活带来了极大的威胁。 水手1 号发射失败( 1 9 6 2 ) 三里岛核电站的核泄漏事故( 1 9 7 8 ) 首次航天飞机发射推迟( 1 9 8 1 ) 美国长途电话业务瘫痪9 小时( 1 9 9 0 ) 阿里亚娜火箭发射失败( 1 9 9 6 ) 火星探路者计划失败( 1 9 9 8 ) 因此，如何保证实时系统具有一定的安全性、可靠性和防危性以避免灾难性 后果的发生，是当前实时系统一个十分重要的研究领域。 目前，实时系统存在几种不同定义，但不同定义均围绕实时系统的时间特性 展开。牛滓计算技术字典中给出了以下定义【3 1 】： 实时系统指系统输出的产生时间具有决定性意义的系统。这是因为系统的输 入来自于物理世界的某个动作，而输出是对该动作的响应。输入和输出间的延迟 必须小于某个确定的时间间隔。 由上述定义可知，实时系统不是一个自封闭的系统。它通过接受外部环境的 输入并按照一定的规则对其进行处理，产生输出以控制外部环境的行为。因此， 实时系统往住存在于一个更大的应用系统中，控审b 该应用系统的运行。因此，实 时系统又常常被形象得称作嵌入式系统。 电子科技大学颤： 二学位沦文 一蜜时系统的内存管理技术研究与吏现 实时系统的基本特性是任务响虑时间的确定性和系统处理任务的高吞吐量 【3 2 】。实时系统的应用领域十分广泛，不同的应用对时间确定性的要求也是不同的。 基于这种考虑，可以将实时系统分为硬实时系统和软实时系统两种。硬实时系统 用以描述对响应时间要求极其严格的实时系统。在硬实时系统中，若输出由于不 能满足响应时间确定性的要求而被放弃，系统的正确性将受到严重影响。相反， 在软实时系统中，只要响应时间超出确定的时间范围的频率低于某一阐值，则不 影响系统的正确性【3 3 】。 除了必须具备响应时间确定性以外，实时系统其它的重要特性包括并发性、 可预测性和可靠性。并发性是指实时系统必须能够在规定时段内处理多个外部输 入。可预测性实质上是对响应时间确定性的保证。外部输入的本质是并发和隧机 分布，每一个输入触发实时系统产生相应的动作，而这些动作的流程、所需的处 理器时间是可预知的。只有在这种情况下才能保证响应时间的确定性。 在实时操作系统中，内存管理是操作系统核心最重要的组成部分之一，用丁_ 提供内存资源的合理分配和存储保护等功能。在没有内存空间保护的系统中，由 于各个进程共存丁同一个地址空间中，常常会因为程序员的误操作而使一个进程 破坏另一个进程的数据，甚至导致整个系统崩溃，因此，对内存实行有效的空间 保护是非常重要的。在实时操作系统中，引入内存保护模块就能对非法的内存操 作进行一定程度上的拦截，从而保护整个系统的运行安全。 我们知道，在桌面操作系统( 如w i n d o w s ，l i n u x ) 中，使用虚拟内存技术来实 现内存保护和内存共享已经是比较成熟的技术，然而构建在实时系统基础上的安 全关键实时系统通常都没有使用虚拟内存技术。这主要是因为现代商业处理器的 m m u 一般都对平均性能进行了优化，却难以分析最坏情形下的时间性能。然而在 现在的安全关键实时系统中。越来越多的应用要求将不同关键级别的任务运行在 同一个处理器上，这就要求对不同关键级别的任务进行有效的隔离，而通过使用 m m u 和虚拟内存技术，我们可以提供对这种隔离机制的有效支撑。 本论文主要的研究工作就是在一个支持多种任务模型的实时系统中，引入虚 拟内存技术后仍能保证安全关键任务的时间性能，另一方面，对于没有严格时问 限制的低关键度任务虚拟内存的灵活性会大大减少对任务的功能限制。 1 2 实时系统的内存管理现状 在过去几十年内嵌入式系统设计者一直是在平面和无保护的内存体系结构 的操作系统中进行开发，例如m o t o r o l a6 8 0 0 0 系列。操作系统中没有使用m m u 和虚拟内存，所有的内存空间可以被任何程序或操作系统访问，进程之间传递数 据就是通过传递指针。 电j 二科技大学硕i 学位沦殳，实日f 系统的内存管理技术研究与实现 随着现代处理器的发展，许多大规模及流水线结构的芯片设计者都假设这些 芯片上的软件使用的都是虚拟内存，因此要求m m u 和c a c h e 使能。为了与更先进 的内嵌式m m u 的处理器兼容，大部分的嵌入式系统只是简单地打开m m u 并创 建单个的内存分区。仅仅打开m m u 丽在每次内存访问时执行地址翻译并不能称 为虚拟内存因为它只是简单地将内存模型变为一对一的映射关系。 因此尽管现代微处理器提供的m m u 单元允许以较高的性能实现内存的保护 和可靠性，在今天流行的嵌入式操作系统中也只有少数使用了这些内嵌的安全特 性。 1 3 研究背景和意义 操作系统作为计算机技术发展的灵魂，从六十年代至今经历了一个从无到有， 从慢到快的发展过程。早期的计算机以大型机为主，因为计算机资源紧缺，如何 提高系统效率更快更好的利用计算机完成工作成为人们重点关注的问题。在这种 情况下，操作系统应运而生。当时的操作系统以多道批处理操作系统为主，其主 要优势是系统资源利用率高，吞吐量大，可顺利解决任务处理时的资源瓶颈。在 随后儿年中，计算机目益普及，计算机用户飞速增加。这时，我们迫切需要一台 计算机能够同时为多个用户服务。并且用户之间彼此不相互影响。分时操作系统 的出现满足了这个需求。在分时系统中，各个用户使用自己的终端，采用时间片 轮转的方式分时共享计算机资源。系统通常根据用户任务的优先级为用户分配时 间片，分时响应用户的请求。在用户看来，这种情形就如同自己独立使用计算机， 与其他用户无关一样。近二十年来计算机硬件和体系结构的飞速发展成为主导 操作系统发展的决定性因素。操作系统的主要目的是尽可能支持更多的硬件设备， 充分利用提供的硬件资源，提高软件资源的管理和运行效率。另外网络支持成为 操作系统必不可少的部分。u n i x ，w i n d o w s 和l i n u x 的成功充分体现了上述特点。 目前，计算机已经进入了新的发展阶段，即被称为“无处不在的计算机”时 代。大量计算机被嵌入到备种机械和设备中，与其他设备结成一体，以控制设备 操作，对设备状态进行实时监视。这种计算机被称为“嵌入式计算机”，它的使用 方式大大提高了生产效率。嵌入式计算机的特点是资源有限，与传统计算机相比， 通常任务比较简单，另外，大部分嵌入式应用有一定的时间限制和正确性要求， 即需要保证任务在规定时间内被正确执行。在这样的条件下管理软硬件资源的系 统，通常被称为嵌入式实时操作系统。它和上述的其他类型的操作系统相比有着 明显的差别，其特点可用如下几个字概括：资源有限、结构紧凑、及时处理、安 全可靠、裁剪灵活。 电r 科技大学颐二i ：学技论文实时系统的内存管理技术研究与实现 嵌入式系统的发展提高了传统设备的智能化程度，是今后十年计算机发展的 新方向。嵌入式系统的广泛应用和自身特点决定了从一开始构造一个适合各种应 用，具有优异的可裁剪性和灵活性的嵌入式操作系统难度很大。因此，目前存在 有上百种不同的嵌入式实时操作系统，其中大多数在各自领域都得到较好的应用。 这和目前几种通用操作系统在微机或小型机上一统天下的局面大不相同。而这也 是我们要发展自己的民族软件业的重要机会之一，因为大家都站在同一起跑线上， 即使领先也不多。如果我们能够在嵌入式实时操作系统研究上取得突破性进展 拥有自己的嵌入式实时操作系统，打破欧美国家对我们的技术封锁，无论从学术 研究还是实际应用来说，这无疑是都是一件利国利民的大事。因此对嵌入式系 统的研究具有与国计民生相关的重要意义。 嵌入式实时操作系统具有不同于一般通用操作系统的特点，最基本的是实时 性、确定性、可裁减性和可配置性即不仅要求计算的结果正确，而且要求产生 正确结果的时间符合要求，以及可根据具体的应用场合对操作系统的组成部分进 行裁减和配置。因此在大的嵌入式实时操作系统中，引入内存管理模块就能对非 法的内存操作进行一定程度上的拦截，从而保护整个系统的运行安全。在本课题中 要求能够设计一个统一的管理模块，能对所有内存操作进行严格的监控、对所有 动态分配出的内存的走向进行追踪，这样就能大大提高对内存问题的定位效率。 高效的内存分配是实现强实时的重要保证，而内存空间保护是实现高可靠性 的重要支持。但内存分配的效率与内存空间保护的程度是一对矛盾体，如何平衡 两者的关系，使之符合嵌入式实时应用，对嵌入式实时操作系统的内存管理而言 是一个重要的课题，具有较大的实用价值。 1 4 本课题来源和完成的主要工作 本课题一高安全实时系统的内存管理技术的研究与实现一是在国防科工 委”十五”军事预研项目军用嵌入式实时操作系统的支持下展开的。本课题对 实时系统的虚拟内存技术和空间域保护机制进行了深入的研究，设计并实现了一 个支持强实时高安全的嵌入式操作系统的内存管理模型。 1 5 论文章节安排 本文第二章介绍存储器管理的基本理论，重点介绍了各种分区管理方法的利 弊。第三章我们介绍了虚拟内存技术的概念和实现细节，介绍了几种不同的处理 器体系结构上的虚拟内存机制，并详细讨论了操作系统软件为支持虚拟内存必须 4 电子科技大学颐l ：学位论文实寸系统的内存管理技术w f 究与实现 考虑的问题。在本文第四章中以前面的存储器管理和虚拟内存技术为基础，我 们对实时系统中的虚拟内存技术和空间域保护机制进行了研究，提出了一个组合 的内存模型。在第五章中，我们详细介绍了c r t o si i 中的内存管理系统的设计和 实现，并给出了测试结果和分析。最后，第六章对全文进行了总结。 电r 科技大学顾。卜学位l 仓文实时系统的内存管理技术研究与宴觋 2 1 存储器结构 第二章存储器管理 在研究存储器管理之前，有必要对存储器的层次结构做一些阐述。 计算机存储器的设计目标可以归纳成三个问题：容量、速度和价格。容量的 问题从某种意义上来说是无止境的，只有要容量，就能开发出应用程序使用它。 速度的问题很明确，即为了达到最佳性能，必须能够跟得上处理器的速度。而价 格也必须仔细考虑，对于一个实际的系统，存储器的价格与其他部件相比应该是 合理的。 2 1 1 存储器的分层结构及性能 存储器系统的设计必须考虑到价格、容量和访问时间这三个重要特性之间的 平衡，因此大多数的计算机存储系统都采用的是层次结构。一般来说，较小、较 贵的快速存储器由较大、较便宜的慢速存储器作为后援。 图2 i 存储器的层次结构 假设处理器存取两级存储器，1 级包含1 0 0 0 个字，存取时间为0 ius ；2 级包 含1 0 0 0 0 0 0 个字，存取时间为1us 。假定如果是存取l 级中的一个字，处理器直 电f 科技大学硕二l 学位沦文寅时系统的内存管理技术研究与实现 接存取，如果这个字在2 级，则它首先转移到l 级，然后再由处理器存取。为了 简单起见，我们忽略处理器用于确定这个字是在1 级还是在2 级所需的时间。 一个二级存储器的平均存取时间是关于命中率( h i tr a t i o ) h 的函数，h 定义为对 较快存储器( c a c h e ) 的存取与对所有存储器的存取之比，t 1 是1 级的存取时间，t 2 是2 级的存取时间。当1 级存取所占比例较高时，平均的总存取时间更接近于1 级而不是2 级。图2 2 显示了一个简单的2 级存储器的性能。 图2 2 一个简单的2 级存储器的性能 假设在c a c h e 中发现9 5 的存储器存取( h = 0 9 5 ) ，则访问一个字的平均存取 时间可表示为： ( o 9 5 ) ( o 1l as ) + ( o 0 5 ) ( o 1 1 ts + 1us ) = 0 0 9 5 + 0 0 5 5 。0 1 5us 结果非常接近于快速存储器的存取时间，但这个结果有效的基础是访问局部 性原理【7 。 根据上述原理，现代计算机系统的存储器系统多采用层次结构来组织数据， 使得存取级别较低的比率小于存取级别较高的比率。一般地，最快、最小和最贵 的存储器类型包括处理器内部的寄存器。典型地，一个处理器将包含很多这样的 寄存器，某些机器包含上百个寄存器。跳过两级，主存储器是计算机主要的内部 存储器系统。主存储器通常由一个高速的、较小的c a c h e 进行扩展。c a c h e 对程序 员，或者说对处理器是不可见的，这种设备用于在主存储器和处理器寄存器之间 分级移动数据，以提高性能。 以上形式的存储器通常是易失的，并且采用半导体技术。数据比较永久地保 电_ j ，科技大学硕一卜学位硷文 实时系统的内存管理技术研究与宴现 存在外部海量存储设备中，通常是硬盘或可更换的媒介。外部辅助存储器的管理 不属于本论文的讨论范围，因此这里不再深入阐述。 2 1 2 高速缓冲存储器 由于处理器的速度的提高一直快于存储器访问速度的提高，我们面临的是在 速度、价格和大小之间的折衷。解决方法是利用局部性原理，在处理器和主存储 器之间提供一个小而快的存储器，称为高速缓冲存储器( c a c h e ) 。 在全部指令j 吉j 期中，处理器在取指令时至少访问一次存储器，通常还要访问 多次，用于取操作数或保存结果。处理器执行指令的速度受存储周期的限制，由 于处理器和主存储器的速度不匹配，这个限制实际已经成为很严重的问题。近年 来，处理器速度的提高一直快于存储器访问速度的提高，我们面临的是在速度、 价格和大小之间的折衷。理想情况下，主存储器的构造可以采用与处理器寄存器 相同的技术，这样存储周期的时间就比得上处理器周期的时间，但这通常是成本 非常昂贵的一种策略。解决方法是利用局部性原理，在处理器和主存储器之间提 供一个小而快的存储器，称作高速缓冲存储器。 图2 3c a c h e 主存储器的结构 高速缓冲存储器试图使存储速度接近现有的最快的存储器，同时以较为便宜 的半导体存储器的成本提供大存储容量。图2 3 说明了这个概念，图中有一个相对 比较大而比较慢的主存储器和一个较小较快的c a c h e 存储器，c a c h e 包含部分主 存储器的副本。当处理器试图读取存储器中的一个字时，进行一次检查以确定这 电r 科技大学硕上学位沦殳 蜜日- l 系统的内存管理技术研究与实现 个字是否在c a c h e 中。如果在，该字被传递给处理器：如果不在，则由固定数目的 字组成的一块主存储器被读入c a c h e ，然后该字被传递给处理器。由于访问局部性 现象的存在，当一块数据被取八c a c h e 满足一次存储器访问时，很有可能下一次是 访问该块中的其他字。 图2 3 描述了c a c h e 主存储器系统的结构。主存储器由2 “个可寻址的字组成， 每个字有一个惟一的n 位地址。基于映射的目的，这个存储器可以看作是由一些同 定大小的块组成，每块包含k 个字，也就是说，一共有m = 2 k 个块。c a c h e 中有c 个存储槽，每个槽有k 个字，槽的数目远远小于m 。主存储器中块的某些子集驻留 在c a c h e 的槽中，如果读到了某一块存储器中的某一个字，而这个块又不在槽中， 则这个块被转移到一个槽中。由于块的数目比槽多，一个槽不可能惟一或永久对 应于一个块。因此，每个槽中有一个标签，用以标识当前存储的是哪一个块。标 签通常是地址中较高的若干位，表示以这些位开始的所有地址。 开始 从c p u 接收地址r ，t 、 包含r a 的块在、 否 9 a c h e 中n q ?一 ， 取队中的字并传递 绘处理器 访问主存储器中包 含r a 的块 将主存储器中的块i 载入c a c h e 糟中 把r a 中的字 传递给c p u 结束一一 | 璺| 2 4c a c h e 读操作 图2 4 说明了读操作的过程。处理器产生要读的字的地址r a 如果这个字在 c a c h e 中，它被传递给处理器；否贝，包含这个字的块被载入c a c h e ，然后这个字 被传递给处理器。 电r 科技大学颈士学位沦史实时系统拍内存管理技术研究与安现 2 2 存储器管理需求 计算机系统中的主存总是被组织成线性的或一维的地址空间，此空间由一系 列字节或字组成。辅存在物理层上也是按类似方式组织的。尽管这个组织几乎很 真实地反映出了实际的机器硬件，但它并不符合构造程序的典型方法。大多数程 序被组织成摸块某些模块是不可修改的某些包含可以修改的数据。如果操作 系统和计算机硬件可以以某种模块的形式有效地处理用户程序和数据则会带来 以下好处： 1 可以独立地写或编译模块，同时系统在运行时解析从一个模块到另一个模块的 所有引用。 2 通过最适度的额外开销，可以给不同的模块不同的保护级别( 只读、只执行) 。 3 可以引入某种机制，使得模块可以被多个进程共享。在模块级提供共享的优点 在于它符合用户看待问题的方式，因此用户也可以很容易地确定想要的共享。 计算机存储器至少被组织成两级，称作主存和辅存。主存以相对比较高的代 价提供快速的访问，此外，主存是易变的，不能提供永久存储。辅存比主存慢而 且便宜。它通常是不变的。因此，大容量的辅存可以用于长期存储程序和数据， 而比较小的主存保存当前要用的程序和数据。 在这个两级方案中，系统最关心的是主存和辅存之间的信息流的组织。如果 止程序员负责这个信息流，则会有以下两方面的问题： i ，可供程序和数据使用的主存可能是不够的。在这种情况下，程序员必须进行覆 盖，程序和数据被组织成以下方式：不同的模块可以指派给存储器中同一块区 域，主程序负责在需要时换入或换出模块。即使有编译程序的帮助，关于覆盖 的程序设计也会花赞程序员大量的时间。 2 在多道程序环境中，程序员在编写代码时不知道有多少空间可用或可用空间在 哪里。 因此，在两级存储器间移动信息的任务是系统的责任，这个任务就存储器管 理的本质所在。 简而言之，存储器管理的需求主要包括以下五点【8 】： 内存分配 地址映射 内存保护 内存共享 电碍技大掌硪士学位论文，实时系统酹内存管理技术研究与实现 内存扩充 2 2 1 内存分配 为了便于对主存储器进行有效的管理，我们把存储器分成若干个区域。即使 在最简单的单用户系统中，至少也要把它分成两个区域：在一个区域内存放系统 软件，如操作系统本身；而另一个存储区域则用于安置用户作业。显然，在多用 户系统中为了提高系统的利用率，需要将存储器划分成更多的区域，以便同时 存放多个用户作业。 因此操作系统必须能够按用户的要求把适当的存储空阔分配给耜应的作业。 一个有效的存储分配机制，应在用户请求时能做出快速的响应，分配相应的存储 空间；在用户不再使用它时，应立即回收，以供其他用户使用。为此，这个分配 机制应具有如下功能： 1 记住每个存储区域的状态。哪些是已分配的，哪些是可以用作分配的。 2 。实煎分配：在系统程序或用户提出申请时，按所需的量给予分配；修改相应的 分配记录表。 3 接受系统或用户释放的存储区域，并相应地修改分配记录表。 存储分配主要是讨论和解决多道作业之间共享主存的存储空间问题。解决存 储分配问题，一般有三种方式： 第一种是直接指定方式。这种方式中，程序员在编程序时，或由编译程序编 译源程序时对一个作业的所有信息确定了在主存存储空间中的位置。 第二种是静态分配方式( s t a t i ca l l o c a t i o n ) 。在这种分配方式中，用户编程或由 编译程序产生目的程序时均可从其地址空间的零地址开始：当装配程序对其进行 连接装入时才确定他们在主存中的相应位置，从而生成可执行程序。 第三种是动态分配( d y n a m i ca l l o c a t i o n ) 。这是一种更加有效的使用主存储器的 方法。作业在存储空间中的位置，也是在其装入时确定的；但在其执行过程中可 根据需要申请附加的存储空间。一个作业已占用的部分存储区域不再需要时，可 以要求归还泠系统。因此，这种存储分配机制能接受不可预测的分配和释放存储 区域的请求，实现个别存储区域的分配和回收。 2 2 2 地址映射 在多道程序系统中，可用的主存通常被许多进程共享。一般来说，程序员不 电子科技大学硕= l ：学位论文实时系统的内存管理技术研究与实现 可能事先知道在自己的程序执行期间其他哪个程序会驻留在主存中。此外，我们 希望能够把活动进程换入或换出主存通过提供一个巨大的就绪进程池，最大程 度地使用处理器。一旦程序被换出磁盘，当下一次被换入时，如果必须放在和以 前相同的存储器区域，这会带来很多限制。相反，我们可以把该进程重定位到存 储器的不同区域。 在一般的情况下，一个作业在装入时分配到的存储空间和它的地址空间是不 一致的。因此，作业在c p u 上运行时，其所要访问的指令和数据的实际地址和地 址空间中的地址是不同的。显然，如果在作业装入时或在其执行时，不对有关的 地址部分加以相应的修改，则将导致错误的结果。这种由于一个作业装入到与其 地址空间不一致的存储空间所引起的对有关地址部分的调整过程，就是我们所称 的地址重定位。实质上，这是一个地址变换过程是把作业地址空间中使用的逻 辑地址变换成主存空间中的物理地址的过程。这种地址变换也称为地址映射。 圉2 5 重定位的硬件支持 在早期的系统中，解决这个问题的方案是当程序调入内存时直接对指令进行 修改。对调入分区l 的程序，在程序的每个地址加上1 0 0 k 对调入分区2 的程序 在程序的每个地址加上2 0 0 k ，等等。为了在调入时对程序重定位，链接程序必须 在产生的二进制代码程序中包含位图或者链表，由它们指出哪些程序字的地址需 要重定位。而哪些是操作码、常数和其他一些不需要重定位的元素。 电于科技大带碳j 学位论文实叫系统的内存管理技术研究与实现 另一个解决重定位的方法是在机器里专门设置两个寄存器，分别称为基址 ( b a s e ) 和界限( 1 i m i t ) 寄存器，如图2 5 所示。在访问内存时，进程生成的每一个地址 被自动加上基址寄存器的内容如果基址寄存器是1 0 0 k ，一条c a l l1 0 0 指令实际 上被转换为c a l l1 0 0 k + 1 0 0 ，而指令本身不必修改。界限寄存器自动检查指令，以 确保它们没有试图访问当前分区以外的地址。由硬件保护基址和界限寄存器，以 防止用户程序修改它们。对重定位使用基址寄存器的另一个优点是，在程序执行 后，它可在内存中移动。当它移动后如果要再运行，所做的只是修改基址寄存器 的值。 在现代的处理器体系结构中无论是使用段页管理还是地址空间标识符管理， 都有专门的地址映射机构，可以将逻辑地址翻译成物理地址。 2 2 3 内存保护 每个进程都应该受到保护，以免其他进程有意或无意的干涉，因此，其他进 程中的程序不能为未经授权的读操作或写操作访问这个进程的存储器单元。在某 种意义上满足重定位的需求增加了满足保护需求的难度。由于程序在主存中的位 置是不可预测的，因而在编译时不可能为了确保保护要求而检查绝对地址。此外， 大多数程序设计语言允许在运行时动态计算地址。因此，必须在运行时检查一个 进程产生的所有存储器访问，以确保它们只访问了分配给该进程的存储空间。 通常，用户进程不能访问操作系统的任何部分，不论是程序还是数据。再者， 一个进程中的程序通常不能分支到另一个进程的指令，如果没有特别的安排，一 个进程中的理序不能访问另一个进程的数据区。处理器必须能够在执行时取消这 样的指令。 存储器保护要求必须由硬件来满足，而不由操作系统( 软件) 来满足。这是 因为操作系统不能预测一个程序可能产生的所有存储器访问，即使可以预测，为 提前屏蔽可能的存储器违法访问是相当费时的。因此，只能在访问指令执行时评 估是否允许这次存储器访问。为实现这一点，处理器硬件必须具有这个能力。 2 2 4 内存共享 任何保护机制必须具有一定的灵活性，以允许多个进程访问主存的同一部分。 例如如果许多进程正在执行同一个程序，则允许每个进程访问该程序的同一个 副本要优于让它们有自己单独的副本。在同一个任务上合作的进程可能需要共享 访问同一个数据结构。存储器管理系统必须允许对存储器共享区域的受控访问， 电干科技大学鞭l 。学位沧文 ，实时系统的出存管理技术研究与实观 而不会损害本质上的保护。 2 2 5 内存扩充 在虚拟存储器的思想提出之前，程序员在编写应用程序时必须知道目标系统 的物理内存大小及使用情况，否则如果应用程序的程序、数据和堆栈的总大小超 过了可用物理内存的大小，就无法在系统上运行。这个要求不仅对程序员提出了 很高的要求，也大大限制了系统的性能。 冈此对于内存管理人们提出了内存扩充的要求。当内存不够的时候，结合内 存和外存，为用户提供一个容量比实际内存大的多的虚拟存储器，这是操作系统 的存储功能；：勺重要任务。 2 3 存储器分区 表2 - i 存储器管理技术 技术说明优势弱点 固定分区在生成系统时，主存被划分成许实现简单，只需由于有内部碎 多静态分区。一个进程可以被装要极少的操作片，对存储器的 入与它大小相等或大于它的分系统开销使用低效；活跃 区中进程的最大数 目是固定的 动态分区 分区是动态创建的因而使得每 没有内部碎片由于需要压缩 个进程可以被装入到与它大小更有效地使用外部碎片，处理 正好相等的分区中内存器使用低效 简单分页主存被划分成许多大小相等的有很少数量的外部碎片 帧；每个进程被划分成许多大小内部碎片 与帧相等的页；装入一个进程通 过把它所有的页装入到可用的 但势不需要连续的帧中完成 简单分段每个进程被划分成许多段；载入没有内部碎片相对于动态分 个进程通过把它的所有段装区。提高了存储 入到不需要连续的动态分区中器利用率，减少 完成了开销 虚拟存储器分页除了不需要装入一个进程的所没有外部碎片：复杂的存储器 有页之外，与简单分页样；所更高程序的多管理开销 需的非常驻页在以后自动调入道程序设计；巨 大的虚拟地址 空间 虚拟存储器分段除了不需要装入一个进程的所没有内部碎片：复杂的存储器 4 电下科技大学颇 学位论文实时系统的内存管理技术研究与实现 有段之外，与简单分段+ 样所更高程序的多管理开销 需的非常驻段在以后自动凋入道程序设计：巨 大的虚拟地址 空间 存储器管理最基本的操作是由处理器把程序装入主存执行。在目前流行的现 代操作系统( 如w i n d o w s 2 0 0 0 ，l i n u x 等) 中，都用到了虚拟存储器的方案。但对 于许多嵌入式操作系统，由于必须优先考虑系统的实时性和紧凑性，仍然使用 了不涉及虚存的简单技术，详细内容见表2 - 1 。 2 3 1 固定分区 在大多数存储器管理方案中，我们可以假设操作系统占据了主存中的某些固 定部分，其余部分的主存储器可供多个进程使用。管理这个可用存储空间的最简 单的方案，是把它分区成边界固定的区域。 2 3 i 1 分区大小 在固定分区的方案中，分区大小可以有两种先择。一种是使用大小相等的分 区另一种则是使用大小不等的分区。 在第一种情况下大小小于或等于分区大小的任何进程可以装入到任何可用 的分区中。如果所有的分区都满了并且没有进程处于就绪或运行状态，操作系 统可以换出任何一个分区的进程，并装入另一个进程。但是这个方法有两个缺点： 第一，一个程序可能太大而不能放到一个分区中。在这种情况下，程序员必须使 用覆盖技术设计程序，使得任何时刻该程序只有部分需要放在主存中。当需要 的模块不在时，用户程序必须把这个模块装入到程序的分区中，覆盖掉那里的程 序和数据。第二，主存的利用率非常低。任何程序，不论多小，都占据了一个完 整的分区。由于装入的数据块小于分区，造成了内部碎片( i n t e r n a lf r a g m e n t m i o n ) 。 使用大小不等的分区可以在一定程度上解决以上两个问题，但是也不能完全 解决。 2 3 j 2 放置算法 对于大小相等的分区，进程在存储器中的放置是微不足道的。只要有一个可 用的分区，进程就可以装入该分区。由于所有的分区大小相等，因而使用哪个分 区都没有关系。 对于大小不等的分区，有两种方法可以把进程指定到分区。一种方法是把每 个进程指定到适应它的最小分区。在这种。隋况下，每个分区都需要一个调度队列， 用于保存为这个分区换出的进程。在一个作业到达时，它可以被放到能容纳这个 电r 科技大学顾i 学位隆文实时系统的内存管理技术研究与实现 作业的最小分区的输入队列里，在这种方案里分区的大小是确定的，没有被这 个作业使用的分区空间就不得不浪费掉。当把输入的作业排成若干个队列的时候， 且用于小分区的队列很满，而大分区的队列却很空的情况下，这个方案的缺点就 很明显。 改进方法是只使用一个队列。当某一个分区处于空闲时，把可被这个分区容 纳的作业中最接近队列前面的作业选择出来调入分区运行。为了不让一个小作业 浪赞一个大的分区，另一个策略是对全部输入队列进行搜索，找出这个分区所能 容纳的最大的一个作业。另一种解决方案是保留至少一个小分区，于是就不会因 为运行小作业而被迫分配大的分区。还有一个办法是，使用这样一种规则：对于 一个可运行的作业，它最多只允许被跳过k 次。每一次被跳过时，该作业就获得 一分，当一个作业得到了k 分以后，这个作业就不能再被忽略而跳过了。 使用大小不等的分区给固定分区提供了一定灵活度。但是，固定分区有以下 缺点：第一，分区的数目在系统生成时确定，它限制了系统中活跃进程的数目。第 二，由于分区的大小是在系统生成时事先设置的，因而小作业不能有效地利用分 区空间。 虽然在大多数情况下这种技术是低效的，但是在事先知道所有作业的主要存 储需求的环境下，这种方法也是合理的。此外，固定分区方案相对比较简单，需 要很小的操作系统软件和处理开销，因此，仍有嵌入式操作系统采用这样的分配方 案。 1 、 l i l w 蛆j 目2 6 围定分区中的存储器分配 1 6 电子科技大学硪上学位论文蛮时系统的内存管理技术研究与实趱 2 3 2