（计算机软件与理论专业论文）对嵌入式系统中内存保护的研究及其设计.pdf

四川大学碗士学位论文 对嵌入式系统中内存保护的研究及其设计 计算机软件与磷论专业 研究生周念念指导老9 酉李涛 摘要： 简洁而高效的内存管理是操作系统理论及其设计实现中一个恒久的话题。 操作系统发展至今，从当初简单的前后台系统到如今复杂的多用户多任务环 境，内存管理的宪善与否一直是评价一个操作系统好坏的重要标准。 在当今大多数的主枫搡作系统中( 服务器和p c 丰几) ，内存管理都已实现 的孝糕当完善，不管是u n i x 家族或者w i n d o w s 系列，攫拟内存的设计思想祓 广泛应用予内存管理之中，不仅为系统中每一个进程提供了曼为广阔的寻址空 间同时也隔离每一个进程的寻址空间，通过地址映射的方式提供了一秘有效的 保护，让整个系统更加稳定，安全和健壮。 但是在嵌入式世界中，由于硬件资源受限以及实时性等多方面的原因，大 多数系统中的内存管理都相当简单，所有的进程或任务和操作系统共享同样的 物理地址空间并且没有任何保护机制。这样，一个进程出现了程序错误极可能 影响到其他进程游运行，甚至很多对假破坏操作系统的运行空闻导致整个系统 的崩溃。更为糟糕鲍是在这群一令虞平模式的陡存中，开发调试人员缀难准确 的定位究竟哪个程序才是造成错误的真凶。 本文在分析了主机操作系统的内存管理后，将主机系统和嵌入系统在运行 环境，系统资源，系统任务等多方面进行了对比，阐明了不能直接使用虚拟内 存管理的原因，同时明确了在嵌入式系统中对内存保护的需求。在此基础k 本 文提出了一种在不改变原有操作系统内存管理格局的前提下，用软硬件相结合 的方式对系统内存进行保护的新方法。在这种方法的保护下，系统中所有的避 四川大学预士学位论文 程将只能访问自己的内存空间而不能肆意去改写其他进程或操作系统的内存区 域。一旦访问越界，会有一个由硬件促发的错误报告通知用户或开发人员，哪 一个进程在怎样的上下文环境中出现了内存访问错误，这样可以极大的方便开 发者对程序错误进行调试。 由于实际工作的原因，本文主要针对无线通讯领域的一些大型嵌入式设 备，如b s c ，p c u 或s g s n 中的内存保护问题，同时兼顾解决方案的通用 性，以求在做一些改动后能将其实现在其他的嵌入式平台上。 因为在通讯领域，m o t o r o l ap o w e r p c 和v x w o r k s 的组合是很多厂家的首 选，因此本文基于这一平台对这种内存保护模式进行了详细设计及都分实现， 并在此基础上对系统的优化提出了改进方案。 关键词：嵌入式系统内存保护v x w o r k s伙伴算法s l a b 算法 四川大学硕士学位论文 t h er e s e a r c ha n dd e s i g na b o u tm 匝m o r y p r o t e c t i n g i ne m b e d d e dc o m p u t e r s m a j o r ：c o m p u t e rs o f t w a r e p o s t g r a d u a t e ：z h o un i a n n i a ns u p e r v i s o r ：l it a o a b s t r a c t ： h o wt om a n a g et h em e m o r yt e r s e l ya n de f f i c i e n t l yi sal a s t i n gt o p i ci nt h et h e o r y a n dd e s i g no fc o m p u t e ro p e r a t i n gs y s t e m ( o s ) a sf a ra sn o w , t h eo sh a v eb e c o m e a na d m i n i s t r a t o ro f as y s t e mw h i c hh a sm u l t i - u s e r sa n dm u l t i - t a s k sa tt h es a m et i m e f r o mas i m p l ef o r e - b a c kg r o u n ds o f t w a r e i nt h ep r o c e s so fo s d e v e l o p m e n t , w h e t h e rt h em e m o r y m a n a g e m e n t i sp e r f e c ti sa l w a y sa l li m p o r ts t a n d a r dt ov e r i f ya o se x c e l l e n to rt e r r i b l e n o w ，t h em o s to s 0 1 1h o s tc o m p u t e r , s e r v e ra n dp c , h a sap e r f e c tm e m o 拶 m a n a g e m e n ts u b s y s t e m ，w h a t e v e ri nu n i x s e r i e so ri nw i n d o wf a m i l y , w h i c h a d o p tt h ed e s i g no f v i r t u a lm e m o r yw i d e l yt op r o v i d ea h u g ea n ds e p a r a t ea d d r e s s s p a c ef o re v e r yp r o c e s sa n dp r o t e c tt h em e m o r yb ya d d r e s sm a p p i n g s ot h ew h o l e s y s t e mb e c o m e ss t a b l e ，s e c u r ea n dl u s t y b u t i nt h ee m b e d d e dc o m p u t e rw o r l d ，t h em o s to fe m b e d d e do sh a sas i m p l ee v e n r o u g hm e m o r ym a n a g e m e n ts u b - s y s t e mf o rt h el i m i th a r d w a i er e s o u r c 宅a n dt h e r e q u k e m e mo fr e a lt i m e i nt h es y s t e m ，a l lp r o c e s s e so rt a s k ss h a r et h ew h o l e p h y s i c a lm e m o r ys p a c ed i r e c t l yi na f i a tm o d e l s o , v e r yp o s s i b l y , o n ep r o c e s so r t a s kw i t hs o m e p r o g r a mb u gw o u l di m p a c tt h eo t h e rp r o c e s so rt a s k sw o r k , e v c n d e s t r o yo s sk e r n e la r e aa n dc r a s ht h ew h o l es y s t e m m o r et e r r i b l y ，w i t h i nt h ef i a t 四川大学硕士学位论文 m e m o r ym o d e l ，i ti sv e r yd i f f i c u l tf o rad e v e l o p e rt of o u n dt h er e a lr o o tc a u s ea f t e r a ne r r o r a f t e r 强a l y z i i i gt h ep r i n c i p l eo f ah o s tc o m p u t e ro s sm e m o r ym a n a g e m e n t ，t h e c o m p a r ea b o u tr u n n i n ge n v i r o n m e n t ，h a r d w a r er e s o u r c ea n ds y s t e mt a r g e tb e t w e e n t h eh o s ta n de m b e d d e dc o m p u t e rh a sb e e ng i v e no u ta n dt h er e a s o nw h yi n e m b e d d e d , t h ev i r t u a lm e m o r yc a n n o tb e u s e dh a sb e e nr e p r e s e n t e dc l e a r l yi nt h i s p a p e r b a s e do nt h e s e ，am e t h o dt op r o t e c te m b e d d e dc o m p u t e r sm e m o r yw i t h o u t m o d i f y i n go r i g i n a lo s sm e m o r ym a n a g e m e n t sf i a m ei sp u tf o r w a r d w i 也t h e 、p r o t e c t i o n , e a c hp r o c e s sc a no n l ya c c e s si t so w nm e m o r ya r e a o n c et h ea o c c s so v e r t h eb o u n d ，t h e r ew i l lb eaf a u l tr e p o r tt ot e l lu s e r so rd e v e l o p e r sw h i c hp r o c e s sh a s f a u l t e da n dw h a tt h ec o n t e x ti sw h e ne r r o r s od e v e l o p e rc a l li n v e s t i g a t et h er o o t c a u s ee a s i l y t h e ni ti sg i v e no u tt h a th o wt od e s i g na n di m p l e m e n ts u c ham e m o r yp r o t e c t i n g m o d u l eo nap o w e r p cc p ua n dv x w o r k so si nt h i sp a p e r a n da f t e rf i r s tt e s t , s o m e o p t i m i z i n gm e t h o di su s e df o rt h eb e t t e rm e m o r yu s a g ea n ds y s t e m p e r f o r m a n c e a tl a s t , i ti st h o u g h tt h a tt h em e m o r yp r o t e c tm e t h o di sf e a s i b l ea n d m e e tt h eg o a l k e yw o r d s ：e m b e d d e dc o m p u t e r s ，m e m o r yp r o t e c t i n g , v x w o r k s ，b u d d i e s - a r i t h m e t i c , s l a b a r i t h m e t i c 四川大学硕士学位论文 1 绪论 随着信息技术的飞速发展，特别是互联网的普及，微电子技术的突破， 嵌入式系统在各行各业的应用程度达n t 前所未有的状况。据美国嵌入式系统 专业杂志r t c 报道，2 1 世纪初的十年中，全球嵌入式系统市场需求量具有比 p c 市场大1 0 至1 0 0 倍的商机。在芝加哥举办的嵌入式系统会议上，专家一致 认为，2 1 世纪嵌入式系统将无所不在，为人类生产带来革命性的发展【1 8 l 。除 了良好的硬件平台外，一个优秀稳定的嵌入式操作系统越来越被业界所重视， 在很多应用中，特别是航空，航天，军事等高科技领域正起着举足轻重的作 用。2 0 0 4 年年初，成功登陆火星的美国“勇气号”上装载了v x w o r k s 实时操 作系统i l 川，。勇气号”从升空到着陆，以及火星巡游，都是在该系统的指引 下完成的。故而，发展强有力的嵌入式操作系统( e m b e d d e dr e a l - t i m e o p e r a t i n gs y s t e m ，e r t o s ) ，成了嵌入式系统发展的核心部分i l 哪。世界各国 在这一领域展开了激烈的竞争，许多著名高等学府如加州大学等都在嵌入式操 作系统的研究上投入了大量的人力物力。 嵌入式系统没有统一的架构，软硬件的组合多样，技术密集，市场容量 大，有较大的创新空间。但由于在大多数应用场合对设备本身的体积有所限 制，硬件资源部可能像主机系统那样丰富，所以系统内核既要精简，又要保证 功能完成的实时性和稳定性因此，设计和实现高效可靠的内核管理模块，如 内存管理，多任务环境管理等是保证嵌入式操作系统快速发展的关键技术之 1 1 嵌入式操作系统的特点 按照英国电气工程师协会( i e e ) 所下的定义【1 7 l ，嵌入式系统是用来控制 或监视机器，装置或工厂等的大规模系统的设备。嵌入式系统是电脑硬件和软 件的综合体，它是以应用为中心，以计算机和信息技术的发展为基础，将用户 所需的特定功能嵌入到产品装置或大型系统中，软硬件可裁减，从而能够适应 实际应用中对功能，可靠性，成本，体积，功耗等严格要求的专用计算机系 统。嵌入式系统的特点主要表现在以下几个方面： 四川大学硕士学位论文 嵌入式系统是将先进的微处理器技术，超大规模集成电路技术，网络通信 技术以及嵌入式软件技术与各个行业的具体应用紧密结合的产物。 嵌入式系统的“嵌入”特性意味着这些系统本身与其所控制和管理的对象 是融为一体的，是其中的一个有机组成部分。 嵌入式系统中的c p u 具有低功耗，体积小，集成度高等特点，能够把通 用c p u 中许多由板卡完成的任务集成到芯片内部，从而有利于整个系统设计 趋于小型化。 嵌入式操作系统所使用的技术，基本上是从台式计算机操作系统演变过来 的。由于应用的需要和硬件条件的限制，嵌入式操作系统必须重视效率，针对 具体需求，去除冗余，才能达到理想的性能。 虽然嵌入式系统本身是针对不同应用场合的，但是嵌入式操作系统的设计 确是力求独立于硬件和应用，用一种通用的方案去管理不同应用中相同的硬 件，软件部分。当然这种通用性不是绝对的，不同的应用可根据自身的特点对 操作系统进行裁减。目前市场上流行的嵌入式操作系统有许多种，例如 v x w o r k s ，p s o s ，w i n c e ，a c o s 【刎这些操作系统都具有一些共同的特 点： 1 可裁减性 在嵌入式世界中所使用的硬件设备各不相同，大型的有通讯基站，交换机 等具有几百兆内存，高速处理能力的印u ：也有那种体积微小，只有几百k 内 存的微型设备例如手持p d a ，对讲机等等。这就决定了用户在使用操作系统 时，不能也不需要用到操作系统中的每一个部件。为了节省存储器空间、提高 运行效率，需要根据用户自己的应用裁减操作系统。例如，v x w o r k s 由一个 体积很小的内核和一些根据需要定制的系统模块组成。它的内核最小为8 k b ， 加上其它必要模块，所占空间也很小，且不失其实时、多任务的系统特征用 户可以很容易对它进行定制或适当开发，来满足自己的实际应用需要。 2 实时性 嵌入式操作系统与通用操作系统之间的最大不同就是要满足处理与时间的 关系。通用系统的要求是系统吞吐量大，响应速度合理，对每个系统用户 或事件相对公平地进行系统资源分配。然而，嵌入式操作系统的关键是进行实 2 四川大学碗士学位论文 时的任务调度，要求系统对外部事件实时的响应。实时性的根本要求是保证实 时任务的时间正确性，即是否满足死限( d e a d l i n e1 1 9 1 ) 对于弱实时( s o f t r c a l t i m e ) 系统，错过死限不会导致严重的后果，只是导致服务质量或者计算 精度的下降，例如电话的偶尔掉线；而对于强实时( h a r dr c a l t i m e ) 系统，一 旦错过死限就意味着巨大的损失和灾难，例如核电站的控制系统对堆芯过热的 及时处理。总之，系统的正确性依赖于计算的逻辑结果和结果产生的时间。 3 任务的驱动 不同的任务有不同的驱动方式，实时任务总是由事件或时间驱动“”。 ( 1 ) 事件驱动一一内部事件驱动是指某一程序运行的结果导致另一任务的 启动，内部事件驱动的任务一般属于同步范畴。外部事件是不可预测的控制对 象或环境发生变化或出现异常的事件，必须立刻请求c p u 处理，它的优先级 最高。 ( 2 ) 时间驱动一一绝对时间驱动是指在某指定时刻执行的任务，系统中的 某些事件是以绝对时间为基准执行的，例如导航卫星与地面系统的对时，就是 为了与外部绝对时间同步。相对时间是指周期性的执行任务，总是相对于上一 次执行时间计时。 “ 4 中断与中断优先级1 2 中断是嵌入式系统中软件系统与硬件系统共同提供的功能。涉及到中断 源、中断优先级、中断处理程序及中断任务等概念。嵌入式实时操作系统充分 利用中断来改变c p u 执行程序的顺序，以达到实时处理的目的。中断源和中 断优先级是实时系统赖以工作的基础。当c p u 接到中断源的请求处理信号 后，先判断该中断源的优先级是否比当前正在执行的任务的优先级更高，若更 高，则中断当前正在执行的程序转而执行对应于该请求信号的中断处理程序 正是由于以上这些因素，在大多数嵌入式操作系统，特别是强实时系统中 要求内核微小，停留时间短，任务切换的速度快。所以在内存管理方面，很多 操作系统不得不做出了牺牲，采用非常简单的内存管理策略，使用扁平内存模 式来满足资源受限的硬件条件同时这样加快了不同任务间的切换速度，力求在 最大程度上满足实时性的要求。 四川大学硕士学位论文 1 2 问题的提出 在我们牺牲了内存管理的完备性来满足实时性的同时，也给我们系统的 稳定性带来了隐患。 首先，由于扁平模式纠在嵌入式操作系统中的广泛使用，运行在系统中的 所有任务共享同样的物理内存空间，并且在任务与任务之间没有任何保护这 就是说一个任务可以访问任何地址，即使这个地址本不该由自己来访问。这让 整个系统的完全性在错误的程序实现面前变得更加脆弱，一旦某一个任务的代 码出现了b u g ，如错误的指针操作，它可能会影响到其他任何任务，甚至破坏 操作系统的内核，导致整个系统的崩溃。例如下面图示的这个例子，这幅图描 述了由于任务l 的程序错误，修改了任务2 的内存空间，这将导致任务2 某一 时刻运行失败或者产生错误的行为。根据笔者的经验，这种错误会随着时间的 流逝在系统中不断的积累，放大。在某一时刻最终导致系统的崩溃。甚至，也 有可能任务l 直接错误的破坏了操作系统k e r n e l 的内存范围，那么很快，系 统将出现无法预期的严重错误。 图1 1 ：一个错误的程序破坏其他程序的例子 4 四川大学硕士学位论文 在这种缺乏内存保护的系统中，只能依靠应用的开发者写出百分之百正确 的程序来避免这种情况的发生，但是我们从软件工程学所获得的经验来看，在 稍微复杂的系统中( 当代码总量超过1 0 0 0 0 行时) 这是非常困难的事 再者，由于这种错误导致的一个更加严重的问题在于，当错误发生以后， 开发调试人员很难去追踪和定位这个问题究竟发生在什么地方。也就是说即使 测试者发现了问题的存在，但是开发人员却没办法修正它l 笔者在工作中对这 一点也是深有体会。如同我们在图一中所示的这个例子，当任务2 的内存区域 被破坏后，它可能又会产生错误行为去修改一个不属于自己的地址在这种连 锁反应后，最终可能有一个任务产生错误的表现被测试者发现，但是此时此 刻，这一b u g 的始作俑者早已隐藏在混乱的内存中，而那些表现出错误的 任务往往都只是真正错误的受害者。另一个更稽糕的情况是，有可能当测试者 发现问题时，系统已经处于完全崩溃的状态( c p uh u n g ) ，系统失去了任何 对外界的响应，这对开发人员来说更是无从下手去d e b u g 这一错误。 1 3 本文的研究工作 正是由于上一节中提到的种种原因，本文提出了一种方法，在不使用虚拟 内存管理【1 6 】和尽量不影响系统性能的前提下，使用基于页面保护【2 l 的方法和一 次分配多次使用【9 】的策略来实施对各进程内存区域的保护，并在基于p o w e r p c 和v x w o r k s 的平台上进行了详细的设计 5 四川大学硕士学位论文 2 嵌入式系统的独特性与其内存保护模块的需求分析 2 1 主机系统中的内存管理与内存保护 在嵌入式系统的发展过程中，许多技术的使用是从主机系统中得到了启 发。为了让我们的内存保护模块的设计更加合理，有效，这一节我们将首先以 l i n u x 为例来深入分析在主机系统中，内存保护是如何实现并融会于内存管理 模块中的。 在d o s 时代，主机操作系统的内存管理相当简单单道应用程序可以访 问整个内存空间和所有的外设端臼，并且对c p u 状态不进行区分( 不区分核 心态与用户态) ，这样一旦某一个应用程序在运行过程中发生错误如越界或非 法访阅外设，整个系统将受到影响。随着硬件技术的不断发展，c p u 状态的 区分以及在x 8 6 架构中实模式与保护模式的区分，现代主机操作系统如 l i n u x , w 矾n t 等都多任务环境置于保护模式下，利用硬件m m u 单元配合 软件手段，采用段式或页式隐射来管理和使用整个逻辑和物理内存空间，让每 个进程运行在各自单独的地址空间中，就好像自身完全使用整个4 g 的内存空 间一样，互不干扰，从而保护每个进程和操作系统k e r n e l 同时也扩展了内存 的使用效率，让整个系统变得更加健壮，可靠和高效下面我们将具体分析 l i n u x 的段页式内存管理机制是如何实现这一目标的。 l i n u x 使用虚拟内存技术，使得系统中为有限物理内存竞争的进程所需 内存空间得到满足。 虚拟内存技术不仅仅可让程序使用更多的内存。它还提供了以下功能： 巨大的寻址空间 操作系统让系统看上去有比实际内存大得多的内存空间虚拟内存可以是 系统中实际物理空间的许多倍。每个进程运行在其独立的虚拟地址空间中这 些虚拟空间相互之问都完全隔离开来，所以进程间不会互相影响。同时，硬件 虚拟内存机构可以将内存的某些区域设置成不可写。这样可以保护代码与数据 不会受恶意程序的干扰。 进程的保护 6 四川大学硕士学位论文 系统中的每一个进程都有自己的虚拟地址空间。这些虚拟地址空间是完全 分开的，这样一个进程的运行不会影响其他进程。并且，硬件上的虚拟内存机 制是被保护的，内存不能被写入，这样可以防止迷失的应用程序覆盖代码的数 据。 内存映射 内存映射技术可以将映象文件和数据文件直接映射到进程的地址空间。在 内存映射中，文件的内容被直接连接到进程虚拟地址空间上 公平的物理内存分配 内存管理子系统允许系统中每个运行的进程公平地共享系统中的物理内 存。 共享虚拟内存 尽管虚拟内存允许进程有其独立的虚拟地址空间，但有时也需要在进程之 间共享内存。例如有可能系统中有几个进程同时运行b a s h 命令外壳程序。 为了避免在每个进程的虚拟内存空间内都存在b a s h 程序的拷贝，较好的解 决办法是系统物理内存中只存在一份b a s h 的拷贝并在多个进程问共享。动 态库则是另外一种进程间共享执行代码的方式。共享内存可用来作为进程闻通 讯( 口c ) 的手段，多个进程通过共享内存来交换信息。u n 畎支持s y s t e mv 的共享内存口c 机制。 7 四川大学硕士学位论文 2 1 1 虚拟内存的抽象模型 - _ x v n h v p 一 v m v p ， v ! y p _ 0 图2 - 1 虚拟地址到物理地址映射的抽象模型i i i 在讨论l j n 峨是如何具体实现对虚拟内存的支持前，有必要看一下更简单 的抽象模型。 在处理器执行程序时需要将其从内存中读出再进行指令解码。在指令解码 之前它必须向内存中某个位置取出或者存入某个值。然后执行此指令并指向程 序中下一条指令在此过程中处理器必须频繁访问内存，要么取指取数，要么 存储数据。虚拟内存系统中的所有地址都是虚拟地址而不是物理地址。通过 操作系统所维护的一系列表格由处理器实现由虚拟地址到物理地址的转换 为了使转换更加简单，虚拟内存与物理内存都以页面来组织。不同系统中页面 的大小可以相同，也可以不同，这样将带来管理的不便。a l p h aa x p 处理器上 运行的l i n u x 页面大小为8 k b ，而i n t e lx 8 6 系统上使用4 k b 页面。每个页面 通过一个叫页面框号的数字来标示( p f n ) 8 、 四川大学硕士学位论文 页面模式下的虚拟地址由两部分构成：页面框号和页面内偏移值。如果页 面大小为4 k b ，则虚拟地址的1 1 ：0 位表示虚拟地址偏移值，1 2 位以上表示 虚拟页面框号处理器处理虚拟地址时必须完成地址分离工作。在页表的帮助 下，它将虚拟页面框号转换成物理页面框号，然后访问物理页面中相应偏移 处图3 1 给出了两个进程x 和y 的虚拟地址空间，它们拥有各自的页表。 这些页表将各个进程的虚拟页面映射到内存中的物理页面。在图中，进程x 的虚拟页面框号o 被映射到了物理页面框号4 。理论上每个页表入口应包含以 下内容： 有效标记，表示此页表入口是有效的 页表入口描叙的物理页面框号 访问控制信息。用来描叙此页可以进行哪些操作，是否可写，是否可执 行 虚拟页面框号是为页表中的偏移。虚拟页面框号5 对应表中的第6 个单元 ( o 是第一个) 。为了将虚拟地址转换为物理地址，处理器首先必须得到虚拟 地址页面框号及页内偏移。一般将页面大小设为2 的次幂将图3 1 中的页面 大小设为0 x 2 0 0 0 字节( 十进制为8 1 9 2 ) 并且在进程y 的虚拟地址空间中某个 地址为0 x 2 1 9 4 ，则处理器将其转换为虚拟页面框号1 及页内偏移0 x 1 9 4 。 处理器使用虚拟页面框号为索引来访问处理器页表，检索页表入口。如果 在此位置的页表入口有效，则处理器将从此入口中得到物理页面框号。如果此 入口无效，则意味着处理器存取的是虚拟内存中一个不存在的区域。在这种情 况下，处理器是不能进行地址转换的，它必须将控制传递给操作系统来完成这 个工作。某个进程试图访问处理器无法进行有效地址转换的虚拟地址时，处 理器如何将控制传递到操作系统依赖于具体的处理器通常的做法是：处理器 引发一个页面失效错而陷入操作系统核心，这样操作系统将得到有关无效虚拟 地址的信息以及发生页面错误的原因。 、 再以图2 - 1 为例，进程y 的虚拟页面框号1 被映射到系统物理页面框号 4 ，则再物理内存中的起始位置为0 x 8 0 0 0 ( 4 o x 2 0 0 0 ) 。加上0 x 1 9 4 字节偏移则 得到最终的物理地址0 x 8 1 9 4 。通过将虚拟地址映射到物理地址，虚拟内存可 以以任何顺序映射到系统物理页面。例如，在图2 1 中，进程x 的虚拟页面框 9 四川大学硕士学位论文 号0 被映射到物理页面框号l 而虚拟页面框号7 被映射到物理页面框号o ，虽 然后者的虚拟页面框号要高于前者。这样虚拟内存技术带来了有趣的结果：虚 拟内存中的页面无须在物理内存保持特定顺序 在物理内存比虚拟内存小得多的系统中，操作系统必须提高物理内存的使 用效率节省物理内存的一种方法是仅加载那些正在被执行程序使用的虚拟页 面。比如说，某个数据库程序可能要对某个数据库进行查询操作，此时并不是 数据库的所有内容都要加载到内存中去，而只加载那些要用的部分。如果此数 据库查询是一个搜索查询而无须对数据库进行添加记录操作，则加载添加记录 、 的代码是毫无意义的。这种仅将要访问的虚拟页面载入的技术叫请求换页。 当进程试图访问当前不在内存中的虚拟地址时，处理器在页表中无法找到 所引用地址的入口。在图2 1 中，对于虚拟页面框号2 ，进程x 的页表中没有 入口，这样当进程x 试图访问虚拟页面框号2 内容时，处理器不能将此地址 转换成物理地址。这时处理器通知操作系统有页面错误发生。 如果发生页面错的虚拟地址是无效的，则表明进程在试图访问一个不存在 的虚拟地址。这可能是应用程序出错而引起的，例如它试图对内存进行一个随 机的写操作。此时操作系统将终止此应用的运行以保护系统中其他进程不受此 出错进程的影响。 如果出错虚拟地址是有效的，但是它指向的页面当前不在内存中，则操作 系统必须将此页面从磁盘映象中读入到内存中来由于访盘时间较长，进程必 须等待一段时间直到页面被取出来。如果系统中还存在其他进程，操作系统就 会在读取页面过程中的等待过程中选择其中之一来运行。读取回来的页面将被 放在一个空闲的物理页面框中，同时此进程的页表中将添加对应此虚拟页面框 号的入口。最后进程将从发生页面错误的地方重新开始运行。此时整个虚拟内 存访问过程告一段落，处理器又可以继续进行虚拟地址到物理地址转换，而进 程也得以继续运行 l i a u x 使用请求换页将可执行映象加载到进程的虚拟内存中。当命令执行 时，可执行的命令文件被打开，同时其内容被映射到进程的虚拟内存。这些操 作是通过修改描叙进程内存映象的数据结构来完成的，此过程称为内存映射。 然而只有映象的起始部分被调入物理内存，其余部分仍然留在磁盘上当映象 四川大学硕士学位论文 执行时，它会产生页面错误，这样l i n u x 将决定将磁盘上哪些部分调入内存继 续执行 如果进程需要把一个虚拟页面调入物理内存而正好系统中没有空闲的物理 页面，操作系统必须丢弃位于物理内存中的某些页面来为之腾出空间。 如果那些从物理内存中丢弃出来的页面来自于磁盘上的可执行文件或者数 据文件，并且没有修改过则不需要保存那些页面。当进程再次需要此页面时， 直接从可执行文件或者数据文件中读出 但是如果页面被修改过，则操作系统必须保留页面的内容以备再次访问。 这种页面被称为d i r t y 页面， 当从内存中移出来时，它们必须保存在叫做交换 文件的特殊文件中。相对于处理器和物理内存的速度，访问交换文件的速度是 非常缓慢的，操作系统必须在将这些d i r t y 页面写入磁盘和将其继续保留在内 存中做出选择。 选择丢弃页面的算法经常需要判断哪些页面要丢弃或者交换，如果交换算 法效率很低，则会发生”颠簸”现象1 1 6 1 。在这种情况下，页面不断的被写入磁盘 又从磁盘中读回来，这样一来操作系统就无法进行其他任何工作以图3 1 为 例，如果物理页面框号i 被频繁使用，则页面丢弃算法将其作为交换到硬盘的 侯选者是不恰当的。一个进程当前经常使用的页面集合叫做工作集高效的交 换策略能够确保所有进程的工作集保存在物理内存中。 l i n u x 使用最近最少使用( l r u ) 页面衰老算法1 1 6 】来公平地选择将要从系 统中抛弃的页面。这种策略为系统中的每个页面设置一个年龄，它随页面访问 次数而变化。页面被访问的次数越多则页面年龄越年轻；相反则越衰老。年龄 较老的页面是待交换页面的最佳侯选者。 虚拟内存让多个进程之间可以方便地共享内存。所有的内存访问都是通过 每个进程自身的页表进行。对于两个共享同一物理页面的进程，在各自的赢 四川大学硕士学位论文 页表入口包含了访问控制信息由于处理器已经将页表入口作为虚拟地址 到物理地址的映射，那么可以很方便地使用访问控制信息来判断处理器是否在 以其应有的方式来访问内存。 诸多因素使得有必要严格控制对内存区域的访问。有些内存，如包含执行 代码的部分，显然应该是只读的，操作系统决不能允许进程对此区域的写操 作。相反包含数据的页面应该是可写的，但是去执行这段数据肯定将导致错 误发生。多数处理器至少有两种执行方式：核心态与用户态任何人都不会允 许在用户态下执行核心代码或者在用户态下修改核心数据结构。 b “1 3 【2l ii o ，0765432t o 图2 - 2a l p h aa x p 页表入口 页表入口中的访问控制信息是处理器相关的；图2 - 2 是a l p h aa x p 处理器 的p t e ( p a g et a b l e e n t r y ) 。这些位域的含义如下： v 有效，如果此位置位，表明此p 1 e 有效 f o e 四川大学硕士学位论文 “执行时失效”，无论合时只要执行包含在此页面中的指令，处理器 都将报告页面错误并将控制传递 f o w “写时失效抻 除了页面错误发生在对此页面的写时，其他与上相 同。 f o r “读时失效”，除了页面错误发生在对此页面的读时，其他与上相 同。 a s m 地址空间匹配。被操作系统用于清洗转换缓冲中的某些入口 k r e 运行在核心模式下的代码可以读此页面。 u r e 运行在用户模式下的代码可以读此页面。 g h 将整个块映射到单个而不是多个转换缓冲时的隐含粒度。 k w e 运行在核心模式下的代码可以写此页面。 u w e 运行在用户模式下的代码可以写此页面。 p a g ef r a m en u m b e r 对于v 位置位的p t e ，此域包含了对应此i r l 限的物理页面框号： 对于无效f t e ，此域不为0 ，它包含了页面在交换文件中位置的信息。 以下两位由l i n u x 定义并使用。 j a g e d i r t y 如果置位，此页面要被写入交换文件。 ja - g e _ a c c e s s e d l i n e x 用它表示页面已经被访问过。 四川大学硕士学位论文 2 1 2l i n u x 页表 图2 - 3l i n u x 的三级页表结构【1 i l i n u x 总是假定处理器有三级页表每个页表通过所包含的下级页表的页 面框号来访问。图2 3 给出了虚拟地址是如何分割成多个域的，每个域提供了 某个指定页表的偏移。为了将虚拟地址转换成物理地址，处理器必须得到每个 域的值。这个过程将持续三次直到对应于虚拟地址的物理页面框号被找到。最 后再使用虚拟地址中的最后一个域，得到了页面中数据的地址。 为了实现跨平台运行，i j n u x 提供了一系列转换宏使得核心可以访问特定 进程的页表。这样核心无需知道页表入口的结构以及它们的排列方式。 这种策略相当成功。无论在具有三级页表结构的a l p h aa x p 还是两级页表 的i n t c lx 8 6 处理器中，l i n u x 总是使用相同的页表操纵代码。 1 4 四川大学硕士学位论文 2 1 4 页面分配与回收 对系统中物理页面的请求十分频繁例如当一个可执行映象被调入内存 时，操作系统必须为其分配页面当映象执行完毕和卸载时这些页面必须被释 放。物理页面的另一个用途是存储页表这些核心数据结构。虚拟内存子系统中 负责页面分配与回收的数据结构和机制可能用处最大。 系统中所有的物理页面用包含m e m _ m a p _ t 结构的链表m e m _ m a p 来描叙， 这些结构在系统启动时初始化。每个m e m _ m a p _ t 描叙了一个物理页面。其中 与内存管理相关的重要域如下： 、c 叩n t 、 记录使用此页面的用户个数。当这个页面在多个进程之间共享时，它的 值大于1 。 a g e 此域描叙页面的年龄，用于选择将适当的页面抛弃或者置换出内存时 m a p _ n r 记录本m e m _ m a p _ t 描叙的物理页面框号。 页面分配代码使用f r e e _ a r e a 数组来寻找和释放页面，此机制负责整个缓冲 管理。另外此代码与处理器使用的页面大小和物理分页机制无关。 f r e ea r e a 中的每个元素都包含页面块的信息。数组中第一个元素描叙1 个 页面，第二个表示2 个页面大小的块而接下来表示4 个页面大小的块，总之都 是2 的次幂倍大小。l i s t 域表示一个队列头，它包含指向m e m _ m a p 数组中 p a g e 数据结构的指针。所有的空闲页面都在此队列中。m a p 域是指向某个特定 页面尺寸的页面组分配情况位图的指针。当页面的第n 块空闲时，位图的第 n 位放置位。 图2 _ 4 画出了f r e ea r e a 结构。第一个元素有个自由页面( 页面框号o ) ， 第二个元素有4 个页面大小的2 个自由块，前一个从页面框号4 开始而后一个 从页面框号5 6 开始。 四川i 大学硕士擘位论文 2 1 4 1 页面分配 l i n u x 使用b u d d y 算法【1 卸u 】来有效的分配与回收页面块页面分配代码每 次分配包含一个或者多个物理页面的内存块。页面以2 的次幂的内存块来分 配。这意味着它可以分配1 个、2 个和4 个页面的块只要系统中有足够的空 闲页面来满足这个要求( m _ f r _ p a g c s r a i nb e _ p a g e ) ，内存分配代码将在 自雠a r e a 中寻找一个与请求大小相同的空闲块。f z c c 中的每个元素保存着_arca 一个反映这样大小的已分配与空闲页面的位图。例如，丘 c c _ a r c a 数组中第二 个元素指向一个反映大小为四个页面的内存块分配情况的内存映象。 分配算法首先搜寻满足请求大小的页面。它从f r c c 数据结构的list域_axca 着手沿链来搜索空闲页面。如果没有这样请求大小的空闲页面，则它搜索两倍 h 。i m d p h y - 岛c a l , m e m o r y 图2 - 4l i n u x 的f z e em e a 数据结构 暑 7 d j 4 3 2 j n p e n 四川大学硕士学位论文 于请求大小的内存块这个过程一直将持续到f r e c 被搜索完或找到满足_area 要求的内存块为止。如果找到的页面块大于请求的块则对其进行分割以使其大 小与请求块匹配由于块大小都是2 的次幂所以分割过程十分简单。空闲块被 连进相应的队列而这个页面块被分配给调用者。 在图2 - 4 中，当系统中有大小为两个页面块的请求发出时，第一个4 页面 大小的内存块( 从页面框号4 开始) 将分成两个2 页面大小的块。前一个，从 页面框号4 开始的。将分配出去返回给请求者，而后一个，从页面框号6 开 始，将被添加到f t c c 数组中表示两个页面大小的空闲块的元素l中。_area ，、 2 1 4 2 页面回收 将大的页面块打碎进行分配将增加系统中零碎空闲页面块的数目页面回 收代码在适当时机下要将这些页面结合起来形成单一大页面块。事实上页面块 大小决定了页面重新组合的难易程度。 当页面块被释放时，代码将检查是否有相同大小的相邻或者b u d d y 内存块 存在。如果有，则将它们结合起来形成一个大小为原来两倍的新空闲块每次 结合完之后，代码还要检查是否可以继续合并成更大的页面。最佳情况是系统 的空闲页面块将和允许分配的最大内存一样大。 在图2 - 4 中，如果释放页面框号1 ，它将和空闲页面框号0 结合作为大小 为2 个页面的空闲块排入f r c ca r e a 的第一个元素中 2 1 5 内存映射 映象执行时，可执行映象的内容将被调入进程虚拟地址空间中。可执行映 象使用的共享库同样如此。然而可执行文件实际上并没有调入物理内存，而是 仅仅连接到进程的虚拟内存。当程序的其他部分运行时引用到这部分时才把它 们从磁盘上调入内存。将映象连接到进程虚拟地址空间的过程称为内存映射 每个进程的虚拟内存用一个m m _ s t r u c t 来表示。它包含当前执行的映象 ( 如b a s h ) 以及指向v m a r e a s t r u c t 的大量指针。每个v m a r e a s t r u c t 数据 结构描叙了虚拟内存的起始与结束位置，进程对此内存区域的存取权限以及一 组内存操作函数。这些函数都是l i n u x 在操纵虚拟内存区域时必须用到的子程 1 7 四川大学硕士学位论文 序其中一个负责处理进程试图访问不在当前物理内存中的虚拟内存( 通过页 面失效) 的情况。此函数叫n o p a g e 。它用在l i n u x 试图将可执行映象的页面调 入内存时。 、 可执行映象映射到进程虚拟地址时将产生一组相应的v ma r e as t r u c t 数据 结构。每个v m a r e a s t r u c t 数据结构表示可执行映象的一部分：可执行代码、 初始化数据( 变量) 、未初始化数据等等。l i n u x 支持许多标准的虚拟内存操作 函数，创建v m a r e a s t r u c t 数据结构时有一组相应的虚拟内存操作函数与之对 应。 、 2 1 6 请求换页操作 当可执行映象到进程虚拟地址空间的映射完成后，它就可以开始运行了。 由于只有很少部分的映象调入内存，所以很快就会发生对不在物理内存中的虚 拟内存区域的访问。当进程访问无有效页表入口的虚拟地址时，处理器将向 l i n u x 报告一个页面错误。 页面错误带有失效发生的虚拟地址及引发失效的访存方式。l i n u x 必须找 到表示此区域的v m a r e a s t r u c t 结构。对v m a r e a s t r u c t 数据结构的搜寻速度 决定了处理页面错误的效率，而所有v m a r e a s t r u c t 结构是通过一种 a v l ( a d d s o n