（计算机软件与理论专业论文）使用内存压缩提高系统性能.pdf

使用内存压缩提高系统性能 a b s t r a c t f o rd e c a d e s ，c p u s p e e d s h a v ec o n t i n u e dt od o u b l e e v e r y1 8m o n t h s t o2 y e a r s ，b u td i s kl a t e n c i e sh a v ei m p r o v e do n l yv e r ys l o w l y d i s kl a t e n c i e sa r e f i v et os i xo r d e r so fm a g n i t u d eg r e a t e rt h a nm a i nm e m o r ya c c e s sl a t e n c i e s p r o g r a m s t h a tr u ne n t i r e l yi nr a mb e n e f i tf r o mi m p r o v e m e n t si nc p u s p e e d s ，b u tt h er u n t i m eo fp r o g r a mt h a tp a g e i s l i k e l yt ob ed o m i n a t e db y d i s ks e e k s ，a n dm a yr u n m a n y t i m e sm o r e s l o w l y t h a nc p u - b o u n d p r o g r a m s d u et ot h eg r e a tl a t e n c i e so fi oi n c u r r i n g b ys w a p p i n g , w e c a n b u y m o r e r a mt oi m p r o v et h es y s t e mp e r f o r m a n c e , b u t b yt h i sw a 弦t h es y s t e mc o s t s i n c r e a s e i no r d e rn o tt oi n c r e a s et h ec o s t so fc u r r e n t s y s t e m , w et a k e a d v a n t a g e o fm e m o r y c o m p r e s s i o n t h ei d e ao fm e m o r y c o m p r e s s i o n i st oh i d et h ed i s kl a t e n c i e sb y s t o r i n g s w a p p e d o u t p a g e f r a m e si nac o m p r e s s e df o r m , b u ts t i l li n p h y s i c a lm e m o r y o nas u b s e q u e n tp a g ef a u l t , t h ep a g ec a nb e q u i c k l yd e c o m p r e s s e da n d s u p p l i e d t ot h e a p p l i c a t i o np r o g r a m t h ea c t u a li m p l e m e n t a t i o no ft h ec o m p r e s s e dm e m o r y s y s t e mi s i nt h e f o r mo fal o a d a b l ed e v i c ed r i v e rm o d u l e t h i sm o d u l e p r o v i d e ss u p p o r t f o r c o m p r e s s e di n - m e m o r yc a c h i n g o fb l o c k d e v i c e s c o m p a r e d w i t ht h e p r e v i o u si m p l e m e n t a t i o n , o u rs y s t e m c a r lb e d y n a m i c a l l y l o a d e da n d u n l o a d e d t h et e s tw o r k sa p p r o v e dt h a tt h ed e m g nf t m c t i o ni ss a t i s f i e da n dt h e v a r i o u s a p p l i c a t i o n sg a i n v a r i o u s i m p r o v e m e n t s f r o mt h ed r i v e r k e y w o r d s ： v i r t u a lm e m o r 弦m e m o r y c o m p r e s s i o n , b l o c k d e v i c ed r i v e r i i 堡旦空壹垦塑堡壹墨竺丝堂 第一章引言 1 1 背景 由于c p u 和内存系统性能差异的不断增大，存储组织结构对整个计算机系 统性能的影响变得重要。这个问题在高速缓存( c a c h e ) 和主存( 内存) 系统组 织上引出了新的问题。然而，在存储系统和磁盘技术之间存在着一个更大的不匹 配。这个不匹配导致了几个数量级的性能差异，由于这个原因，虚存的换页开销 就显得格外得大。 同时，在过去的1 0 年中，普通程序对内存的需求却以每年5 0 一1 0 0 m 的速 率增长。随着使用大数据集的复杂应用程序和面向对象编程等高级编程技巧的进 一步使用，这个增长率还会一直保持下去。因此，以提高存储系统结构性能，或 减少程序对内存的需要为目标的方法，能给整个计算机系统的性能提供显著的提 高。 于是，在这种背景下，出现了通过减少系统访问磁盘次数而提高系统性能的 一个新的思想内存压缩。内存压缩这一机制在系统的存储层次中逻辑地加入 一层压缩内存层，如图1 1 所示。系统在该层中以压缩的格式保存需要换出 的物理页面，当页面再次被系统引用时，解压缩该压缩页后，即可被系统立即使 图1 - 1 内存压缩技术的使用，为系统带来了如下好处 在逻辑上扩充了物理内存的容量 堡旦空壹垦塑堡壹墨竺丝堂 第一章引言 1 1 背景 由于c p u 和内存系统性能差异的不断增大，存储组织结构对整个计算机系 统性能的影响变得重要。这个问题在高速缓存( c a c h e ) 和主存( 内存) 系统组 织上引出了新的问题。然而，在存储系统和磁盘技术之间存在着一个更大的不匹 配。这个不匹配导致了几个数量级的性能差异，由于这个原因，虚存的换页开销 就显得格外得大。 同时，在过去的1 0 年中，普通程序对内存的需求却以每年5 0 一1 0 0 m 的速 率增长。随着使用大数据集的复杂应用程序和面向对象编程等高级编程技巧的进 一步使用，这个增长率还会一直保持下去。因此，以提高存储系统结构性能，或 减少程序对内存的需要为目标的方法，能给整个计算机系统的性能提供显著的提 高。 于是，在这种背景下，出现了通过减少系统访问磁盘次数而提高系统性能的 一个新的思想内存压缩。内存压缩这一机制在系统的存储层次中逻辑地加入 一层压缩内存层，如图1 1 所示。系统在该层中以压缩的格式保存需要换出 的物理页面，当页面再次被系统引用时，解压缩该压缩页后，即可被系统立即使 图1 - 1 内存压缩技术的使用，为系统带来了如下好处 在逻辑上扩充了物理内存的容量 使用内存压缩提高系统性能 减少换页，降低了换页引起的开销，从而提高系统的性能 压缩内存这一观点最初由p a u lr w i l s o n 等人在9 0 年代初期提出，并由 d o u g l i s 和r u s s i n o v i c h ，c o g s w e l l 等人进行了验证。但是，d o u g l i s 的试验显示， 对有些程序，内存压缩带来了系统性能的提高，而对另外一些程序，并没有实质 上的性能提高，反而有些表现为系统性能的下降。而r u s s i n o v i c h 和c o g s w e l l 针 对不同负载的试验数据显示内存压缩技术只为系统带来了微乎其微的性能提升。 于是，人们普遍认为，压缩虚拟内存技术只对没有快速的本地磁盘的系统，如无 盘手持设备、网络计算机、或使用低速硬盘的膝上电脑有吸引力。但是，随着 c p u 的速度的不断提高，压缩虚拟内存技术会越来越具有吸引力。当前，压缩 内存的实现有多种途径，包括软件途径，例如修改操作系统的内核；硬件途径， 比如使用专用的压缩内存缓存线。前一种途径要求能够修改操作系统的内核源代 码，并且可能会很难在多个操作系统之间进行移植。而硬件实现会增大一台计算 机的价格。如果硬件实现途径使用一个增强的内存控制器，则这种实现只适用于 新的机器。 与此相反，我们的系统由一个可装载的设备驱动程序( 当前只支持l i n u x ) 构成。这种途径显然很容易在诸如w i n d o w sn t 、w i n d o w s2 0 0 0 和其它u n i x 系 统上移植。我们的系统的另一个好处是，当那些应用程序不能从内存压缩上取得 任何好处时，可以简单地将这个驱动程序卸载掉。由于不需要重新启动系统，这 一过程可以以对用户完全透明的方式，在一个正在运行的系统上进行。测试的结 果表明，相对于在没有内存压缩的系统中执行，这些应用程序分别得到了速度的 提高。 1 2 论文组织 本文首先介绍l i n u x 的虚存系统，然后分析了交换对系统性能的影响；针对 虚存对系统的影响，提出了内存压缩思想和实现。 第二章理论基础 主要讲述了l i n u x 的虚存系统，分析了交换对系统的影响，以及l i n u x 中交 换所涉及到的系统调用。 第三章内存压缩 提出内存压缩思想，以及设计思想。 第四章实现技术 具体分析了所采用的压缩算法和块设备驱动程序的实现。 第五章具体事项 讲述了设备内存管理模块的设计以及具体的函数设计。 2 使用内存压缩提高系统性能 减少换页，降低了换页引起的开销，从而提高系统的性能 压缩内存这一观点最初由p a u lr w i l s o n 等人在9 0 年代初期提出，并由 d o u g l i s 和r u s s i n o v i c h ，c o g s w e l l 等人进行了验证。但是，d o u g l i s 的试验显示， 对有些程序，内存压缩带来了系统性能的提高，而对另外一些程序，并没有实质 上的性能提高，反而有些表现为系统性能的下降。而r u s s i n o v i c h 和c o g s w e l l 针 对不同负载的试验数据显示内存压缩技术只为系统带来了微乎其微的性能提升。 于是，人们普遍认为，压缩虚拟内存技术只对没有快速的本地磁盘的系统，如无 盘手持设备、网络计算机、或使用低速硬盘的膝上电脑有吸引力。但是，随着 c p u 的速度的不断提高，压缩虚拟内存技术会越来越具有吸引力。当前，压缩 内存的实现有多种途径，包括软件途径，例如修改操作系统的内核；硬件途径， 比如使用专用的压缩内存缓存线。前一种途径要求能够修改操作系统的内核源代 码，并且可能会很难在多个操作系统之间进行移植。而硬件实现会增大一台计算 机的价格。如果硬件实现途径使用一个增强的内存控制器，则这种实现只适用于 新的机器。 与此相反，我们的系统由一个可装载的设备驱动程序( 当前只支持l i n u x ) 构成。这种途径显然很容易在诸如w i n d o w sn t 、w i n d o w s2 0 0 0 和其它u n i x 系 统上移植。我们的系统的另一个好处是，当那些应用程序不能从内存压缩上取得 任何好处时，可以简单地将这个驱动程序卸载掉。由于不需要重新启动系统，这 一过程可以以对用户完全透明的方式，在一个正在运行的系统上进行。测试的结 果表明，相对于在没有内存压缩的系统中执行，这些应用程序分别得到了速度的 提高。 1 2 论文组织 本文首先介绍l i n u x 的虚存系统，然后分析了交换对系统性能的影响；针对 虚存对系统的影响，提出了内存压缩思想和实现。 第二章理论基础 主要讲述了l i n u x 的虚存系统，分析了交换对系统的影响，以及l i n u x 中交 换所涉及到的系统调用。 第三章内存压缩 提出内存压缩思想，以及设计思想。 第四章实现技术 具体分析了所采用的压缩算法和块设备驱动程序的实现。 第五章具体事项 讲述了设备内存管理模块的设计以及具体的函数设计。 2 使用内存压缩提高系统性能 第六章测试 从功能和性能两方面对内存压缩系统进行测试，给出了测试报告。 使用内存压缩提高系统性能 第二章理论基础 2 1 内存管理 内存是计算机系统的重要组成部分。近年来，随着计算机技术的发展，系统 软件和应用程序在种类、功能及其所需存储空间等方面，都在急剧地膨胀，虽然 内存的容量也一直在不断地扩大，但仍不能满足现代软件的发展的需要，因此， 内存仍然是一种宝贵且紧俏的资源。如何对它们施行有效的管理，不仅直接影响 到内存的利用率，而且还对系统性能有重大的影响。 在一个只有一个程序执行的系统中，内存被划分为两个部分：一部分给操作 系统( 驻留监控器，内核) ，和给当前正在执行的程序的部分。在一个多任务系 统中，用户部分的内存必须更进一步划分以装载多个任务。这个进一步划分的任 务由操作系统动态的完成，也就是内存管理。 高效的内存管理对一个多任务系统是至关重要的。如果只有一些进程驻留内 存，那么绝大多数的时间里，所有的进程将会等待f o ，处理器就会显得空闲。 因此，内存必须被有效的分配以装载尽可能多的进程。 2 1 1 内存分区 内存管理的主要操作是将程序装入内存以便处理器执行。在几乎所有的现代 多道系统中，这都涉及到虚存系统。虚存系统，反过来又是基于分页和分段的使 用。在讨论虚存之前，我们必须首先需要理解那些不涉及到虚存系统的较简单的 技术。这些技术包括分区、简单分页以及简单分段等等。分区在一些老的系统中 使用过；而简单分页和简单分段从来没有被那个操作系统使用过。但是，对这些 技术的讨论会帮助我们澄清一些对虚存系统的讨论。 内存分区 分区式分配方式是一种可用于多道程序的一种较简单的存储管理方式。它又 可以进一步分为： 1 ) 固定分区式。这是将内存用户区划分成若干个固定大小的区域，每个区 域中驻留一道程序； 2 ) 动态分区。又称为可变分区，根据用户程序的大小，动态地对内存进行 划分，因此，各分区地大小是不定的，内存被划分成多少个分区，其数 目也是可变的。动态分区方式较之固定分区方式显著地提高了存储器的 4 使用内存压缩提高系统性能 第二章理论基础 2 1 内存管理 内存是计算机系统的重要组成部分。近年来，随着计算机技术的发展，系统 软件和应用程序在种类、功能及其所需存储空间等方面，都在急剧地膨胀，虽然 内存的容量也一直在不断地扩大，但仍不能满足现代软件的发展的需要，因此， 内存仍然是一种宝贵且紧俏的资源。如何对它们施行有效的管理，不仅直接影响 到内存的利用率，而且还对系统性能有重大的影响。 在一个只有一个程序执行的系统中，内存被划分为两个部分：一部分给操作 系统( 驻留监控器，内核) ，和给当前正在执行的程序的部分。在一个多任务系 统中，用户部分的内存必须更进一步划分以装载多个任务。这个进一步划分的任 务由操作系统动态的完成，也就是内存管理。 高效的内存管理对一个多任务系统是至关重要的。如果只有一些进程驻留内 存，那么绝大多数的时间里，所有的进程将会等待f o ，处理器就会显得空闲。 因此，内存必须被有效的分配以装载尽可能多的进程。 2 1 1 内存分区 内存管理的主要操作是将程序装入内存以便处理器执行。在几乎所有的现代 多道系统中，这都涉及到虚存系统。虚存系统，反过来又是基于分页和分段的使 用。在讨论虚存之前，我们必须首先需要理解那些不涉及到虚存系统的较简单的 技术。这些技术包括分区、简单分页以及简单分段等等。分区在一些老的系统中 使用过；而简单分页和简单分段从来没有被那个操作系统使用过。但是，对这些 技术的讨论会帮助我们澄清一些对虚存系统的讨论。 内存分区 分区式分配方式是一种可用于多道程序的一种较简单的存储管理方式。它又 可以进一步分为： 1 ) 固定分区式。这是将内存用户区划分成若干个固定大小的区域，每个区 域中驻留一道程序； 2 ) 动态分区。又称为可变分区，根据用户程序的大小，动态地对内存进行 划分，因此，各分区地大小是不定的，内存被划分成多少个分区，其数 目也是可变的。动态分区方式较之固定分区方式显著地提高了存储器的 4 使用内存压缩提高系统性能 利用率。 分区式分配方式由于要求将一个用户程序分配到一个连续的内存空间中，因 此可能产生多个不可利用的内存碎片。 2 1 2 简单分页 固定分区和动态分区这两种内存分配方式在内存使用上效率都不高；前者会 引起内部碎片，而后者产生外部碎片。假如，内存被划分成相对较小的固定大小 的块，同时，用户进程也被划分成同样大小的块。然后，一个进程的块，称为页， 能够被分配到内存中可用的块，称为框，或页框。 图2 - 1 指定进程页到空闲页 图2 - 1 阐明了页和页框的使用。在一个给定的时间点，内存中的有些页框是 空闲的，有些是正在被使用的。存储在磁盘上的进程a ，由4 页组成。当需要将 该进程装载到内存中时，操作系统找到4 个空闲的页框，然后将进程a 的4 个 使用内存压缩提高系统性能 页装载到那个4 个页框中( 图2 - l a ) 。进程b ，包含3 个页，进程c ，包含4 个 页，被顺序装载到内存中。随后，进程b 被挂起，然后被交换出内存。接着， 内存中所有的进程被阻塞，操作系统将新的进程一进程d ，包含5 个页，转载到 内存中。 现在假设，在上例中，如果内存中没有足够连续的页框可以容纳进程d ，那 么，这会阻止操作系统装载进程d 吗? 答案是否，因为我们再一次地使用逻辑 地址这一概念。一个简单的基地址寄存器不再够用。操作系统为每一个进程维护 一个页表。页表中显示每个进程的每个页的位置。在程序中，逻辑地址是由页号 和偏移量构成。在分页系统中，逻辑地址到物理地址的翻译还是由处理器的硬件 完成的。所以，处理器必须知道如何访问当前进程的页表。处理器通过页表将逻 辑地址转换成物理地址。 进程 a 页表 0 厂= = _ 1r _ 了 2e 爿 进程 b 页袭 进程 c 页表 0 厂百 1 宙 空闲页 帧链表 图2 2 图2 1 在时刻f 时的数据结构 图2 2 显示了在时刻( f ) 时，不同进程的页表。每个进程的每一个页在页 表中都有一项，这样，通过页号( 页号从0 开始) 就很容易地在页表中进行索引。 每个页表项中包含内存中的一帧的页帧号。除此以外，操作系统为内存中的所有 空闲并可用页帧维护一个空闲页帧链表。 简单分页与固定分区很相似。不同之处在于，在分页系统中，每个分区( 即 页) 相对很小，一个程序可能占据不止一个分区；并且这些分区不需要一定是连 续的。 2 2 虚存系统 前一节所介绍的内存管理方式，有一个共同的特点，即它们都要求将一个作 业全部装入内存方能运行。于是，出现了这样两种情况：( 1 ) 有的作业很大，其 所有的内存空间超过了内存总容量作业不能全部被装入内存，致使该作业无法运 行；( 2 ) 有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能 将少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待。显而 目 o l 2 3圉 0 1 2 3 使用内存压缩提高系统性能 页装载到那个4 个页框中( 图2 - l a ) 。进程b ，包含3 个页，进程c ，包含4 个 页，被顺序装载到内存中。随后，进程b 被挂起，然后被交换出内存。接着， 内存中所有的进程被阻塞，操作系统将新的进程一进程d ，包含5 个页，转载到 内存中。 现在假设，在上例中，如果内存中没有足够连续的页框可以容纳进程d ，那 么，这会阻止操作系统装载进程d 吗? 答案是否，因为我们再一次地使用逻辑 地址这一概念。一个简单的基地址寄存器不再够用。操作系统为每一个进程维护 一个页表。页表中显示每个进程的每个页的位置。在程序中，逻辑地址是由页号 和偏移量构成。在分页系统中，逻辑地址到物理地址的翻译还是由处理器的硬件 完成的。所以，处理器必须知道如何访问当前进程的页表。处理器通过页表将逻 辑地址转换成物理地址。 进程 a 页表 0 厂= = _ 1r _ 了 2e 爿 进程 b 页袭 进程 c 页表 0 厂百 1 宙 空闲页 帧链表 图2 2 图2 1 在时刻f 时的数据结构 图2 2 显示了在时刻( f ) 时，不同进程的页表。每个进程的每一个页在页 表中都有一项，这样，通过页号( 页号从0 开始) 就很容易地在页表中进行索引。 每个页表项中包含内存中的一帧的页帧号。除此以外，操作系统为内存中的所有 空闲并可用页帧维护一个空闲页帧链表。 简单分页与固定分区很相似。不同之处在于，在分页系统中，每个分区( 即 页) 相对很小，一个程序可能占据不止一个分区；并且这些分区不需要一定是连 续的。 2 2 虚存系统 前一节所介绍的内存管理方式，有一个共同的特点，即它们都要求将一个作 业全部装入内存方能运行。于是，出现了这样两种情况：( 1 ) 有的作业很大，其 所有的内存空间超过了内存总容量作业不能全部被装入内存，致使该作业无法运 行；( 2 ) 有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能 将少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待。显而 目 o l 2 3圉 0 1 2 3 使用内存压缩提高系统性能 易见的一种解决方式，是从物理上增加内存的容量，但这往往会受到机器自身的 限制，而且无疑要增加系统的成本，因此这种方法是受到一定限制的；另一种方 法是从逻辑上扩充内存容量，这正是虚存技术所要解决的主要问题。 2 2 1 虚存的基本概念 作业在每次运行时，并非用到其全部程序，因此，那种将作业“一次性”地 全部装入的方法，显然是一种对内存空间的浪费。此外，作业装入内存后，便一 直驻留在内存直至作业运行结束。尽管运行中的进程会因f o 而长期等待，或有 的程序运行一次后，就不再需要运行了，然而它们都将继续占据宝贵的内存资源， 此即驻留性。上述的一次性及驻留性，会使许多在进程运行时不用的，或暂时不 用的程序( 数据) 占据了大量的内存空间，而使一些需要运行的作业无法装入运 行。这样，将严重地降低内存的利用率，从而显著地减少了系统吞吐量。于是， 就有人提出了一次性及驻留性是否是程序运行时所必须的这些的问题。 2 2 2 虚存的引入 对于是否需要一次性地将作业全部装入，作业是否需要长期地驻留在内存的 问题，不少学者已进行了广泛的研究，这些研究结果为虚存的实现奠定了基础。 局部性原理 早在1 9 6 8 年，p d o i n g 就指出过，程序在执行时将呈现出局部性规律， 即在一较短时间内。程序的执行仅限于某个部分；相应地，它所访问的存储空间 也局限于某个区域。他提出了以下几点： ( 1 ) 程序在执行时，除了少部分的转移和过程调用指令外，在大多数情况 下，仍是顺序执行的。该论点也在后来许多学者们对高级程序设计语 言( 如f o r t r a n ，p 粥c a l 语言及c 语言) 规律的研究中被证实。 ( 2 ) 过程调用将会使程序的执行轨迹由部分内存区转至另一部分区域， 但经研究表明，在大多数情况下，过程调用的深度都不超过5 ，这就 + 是说，程序将会在一段时间内，都局限在这些进程的范围内运行。 ( 3 ) 程序中存在许多循环结构，它们虽由少数指令构成，但多次执行。 ( 4 ) 程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往 都局限于很小的范围内。 局限性又表现为： ( 1 ) 时间局限性。如果程序中的某条指令一旦执行，则不久以后该指令可 能再次执行；如果某个数据结构被访问，则不久以后该数据结构可能 7 使用内存压缩提高系统性能 易见的一种解决方式，是从物理上增加内存的容量，但这往往会受到机器自身的 限制，而且无疑要增加系统的成本，因此这种方法是受到一定限制的；另一种方 法是从逻辑上扩充内存容量，这正是虚存技术所要解决的主要问题。 2 2 1 虚存的基本概念 作业在每次运行时，并非用到其全部程序，因此，那种将作业“一次性”地 全部装入的方法，显然是一种对内存空间的浪费。此外，作业装入内存后，便一 直驻留在内存直至作业运行结束。尽管运行中的进程会因f o 而长期等待，或有 的程序运行一次后，就不再需要运行了，然而它们都将继续占据宝贵的内存资源， 此即驻留性。上述的一次性及驻留性，会使许多在进程运行时不用的，或暂时不 用的程序( 数据) 占据了大量的内存空间，而使一些需要运行的作业无法装入运 行。这样，将严重地降低内存的利用率，从而显著地减少了系统吞吐量。于是， 就有人提出了一次性及驻留性是否是程序运行时所必须的这些的问题。 2 2 2 虚存的引入 对于是否需要一次性地将作业全部装入，作业是否需要长期地驻留在内存的 问题，不少学者已进行了广泛的研究，这些研究结果为虚存的实现奠定了基础。 局部性原理 早在1 9 6 8 年，p d o i n g 就指出过，程序在执行时将呈现出局部性规律， 即在一较短时间内。程序的执行仅限于某个部分；相应地，它所访问的存储空间 也局限于某个区域。他提出了以下几点： ( 1 ) 程序在执行时，除了少部分的转移和过程调用指令外，在大多数情况 下，仍是顺序执行的。该论点也在后来许多学者们对高级程序设计语 言( 如f o r t r a n ，p 粥c a l 语言及c 语言) 规律的研究中被证实。 ( 2 ) 过程调用将会使程序的执行轨迹由部分内存区转至另一部分区域， 但经研究表明，在大多数情况下，过程调用的深度都不超过5 ，这就 + 是说，程序将会在一段时间内，都局限在这些进程的范围内运行。 ( 3 ) 程序中存在许多循环结构，它们虽由少数指令构成，但多次执行。 ( 4 ) 程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往 都局限于很小的范围内。 局限性又表现为： ( 1 ) 时间局限性。如果程序中的某条指令一旦执行，则不久以后该指令可 能再次执行；如果某个数据结构被访问，则不久以后该数据结构可能 7 使用内存压缩提高系统性能 易见的一种解决方式，是从物理上增加内存的容量，但这往往会受到机器自身的 限制，而且无疑要增加系统的成本，因此这种方法是受到一定限制的；另一种方 法是从逻辑上扩充内存容量，这正是虚存技术所要解决的主要问题。 2 2 1 虚存的基本概念 作业在每次运行时，并非用到其全部程序，因此，那种将作业“一次性”地 全部装入的方法，显然是一种对内存空间的浪费。此外，作业装入内存后，便一 直驻留在内存直至作业运行结束。尽管运行中的进程会因f o 而长期等待，或有 的程序运行一次后，就不再需要运行了，然而它们都将继续占据宝贵的内存资源， 此即驻留性。上述的一次性及驻留性，会使许多在进程运行时不用的，或暂时不 用的程序( 数据) 占据了大量的内存空间，而使一些需要运行的作业无法装入运 行。这样，将严重地降低内存的利用率，从而显著地减少了系统吞吐量。于是， 就有人提出了一次性及驻留性是否是程序运行时所必须的这些的问题。 2 2 2 虚存的引入 对于是否需要一次性地将作业全部装入，作业是否需要长期地驻留在内存的 问题，不少学者已进行了广泛的研究，这些研究结果为虚存的实现奠定了基础。 局部性原理 早在1 9 6 8 年，p d o i n g 就指出过，程序在执行时将呈现出局部性规律， 即在一较短时间内。程序的执行仅限于某个部分；相应地，它所访问的存储空间 也局限于某个区域。他提出了以下几点： ( 1 ) 程序在执行时，除了少部分的转移和过程调用指令外，在大多数情况 下，仍是顺序执行的。该论点也在后来许多学者们对高级程序设计语 言( 如f o r t r a n ，p 粥c a l 语言及c 语言) 规律的研究中被证实。 ( 2 ) 过程调用将会使程序的执行轨迹由部分内存区转至另一部分区域， 但经研究表明，在大多数情况下，过程调用的深度都不超过5 ，这就 + 是说，程序将会在一段时间内，都局限在这些进程的范围内运行。 ( 3 ) 程序中存在许多循环结构，它们虽由少数指令构成，但多次执行。 ( 4 ) 程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往 都局限于很小的范围内。 局限性又表现为： ( 1 ) 时间局限性。如果程序中的某条指令一旦执行，则不久以后该指令可 能再次执行；如果某个数据结构被访问，则不久以后该数据结构可能 7 再次被访问。产生时间局限性的典型原因是在程序中存在大量的循环 操作。 ( 2 ) 空间局限性。一旦程序访问了某个存储单元，在不久以后，其附近的 存储单元也被访问。即程序在一段时间内所访问的地址，可能集中在 一定的范围内，其典型的原因是程序的顺序执行。 虚存的定义 基于局部性原理，一个作业在运行之前，没有必要全部都装入内存，而仅将 那些当前要运行的那部分页面或段，先装入内存便可启动运行，其余部分暂时留 在磁盘上。程序在运行时，如果它所要访问的页( 段) 已调入内存，便可继续执 行下去，但如果程序所要访问的页( 段) 尚未调入内存( 成为缺页或缺段) ，此 时程序应利用操作系统所提供的请求调页( 段) 功能，将它们调入内存，以使进 程能继续执行下去。如果此时内存已满，无法再装入新的页( 段) ，则还须再利 用页( 段) 的置换功能，将内存中暂时不用的页( 段) 调出至磁盘上，腾出足够 的内存空间后，再将所要访问的页( 段) 调入内存，使程序继续执行下去、这样， 便可使一个大的用户程序在较小的内存空间中运行；也可使内存中同时装入更多 的进程并发执行。从用户的角度看，该系统所具有的内存容量，将比实际内存容 量大得多，人们把这样的存储器称为虚拟存储器，简称虚存。 虚存系统带来的好处是极具吸引力的，但是，这种机制是否实际昵? 在一段 时间内，在这个问题上，存在着极大的争议，但是，在不同操作系统上的试验证 明了虚存是可以工作的。基于此，虚存已经成为绝大多数现代操作系统中的一个 重要组成部件了。 为使虚存系统能有效地工作，两个因素必不可少。第一，必须有硬件支持的 分页或分段机制。第二，操作系统应具有管理换页或段的软件。接下来，我们分 析一下硬件方面是如何提供支持的，以及必要的控制结构，这些结构由操作系统 创建和维护，但是由内存管理硬件所使用。 2 2 3 分页 术语虚存通常与使用分页机制的系统相关联，虽然基于分段机制的虚存系统 也有使用的，但是由于l i n u x 使用分页机制，所以在此我们只讨论基于分页机制 的虚存系统。基于分页机制的虚存系统首次在a r i a s 上使用，不久以后就得到了 广泛的商业应用。 在简单的分页机制中，每个进程有自己的页表，并且当进程的所有页都被装 入内存时，进程的页表才被创建并被装入内存中。每个页表项包含内存中对应的 再次被访问。产生时间局限性的典型原因是在程序中存在大量的循环 操作。 ( 2 ) 空间局限性。一旦程序访问了某个存储单元，在不久以后，其附近的 存储单元也被访问。即程序在一段时间内所访问的地址，可能集中在 一定的范围内，其典型的原因是程序的顺序执行。 虚存的定义 基于局部性原理，一个作业在运行之前，没有必要全部都装入内存，而仅将 那些当前要运行的那部分页面或段，先装入内存便可启动运行，其余部分暂时留 在磁盘上。程序在运行时，如果它所要访问的页( 段) 已调入内存，便可继续执 行下去，但如果程序所要访问的页( 段) 尚未调入内存( 成为缺页或缺段) ，此 时程序应利用操作系统所提供的请求调页( 段) 功能，将它们调入内存，以使进 程能继续执行下去。如果此时内存已满，无法再装入新的页( 段) ，则还须再利 用页( 段) 的置换功能，将内存中暂时不用的页( 段) 调出至磁盘上，腾出足够 的内存空间后，再将所要访问的页( 段) 调入内存，使程序继续执行下去、这样， 便可使一个大的用户程序在较小的内存空间中运行；也可使内存中同时装入更多 的进程并发执行。从用户的角度看，该系统所具有的内存容量，将比实际内存容 量大得多，人们把这样的存储器称为虚拟存储器，简称虚存。 虚存系统带来的好处是极具吸引力的，但是，这种机制是否实际昵? 在一段 时间内，在这个问题上，存在着极大的争议，但是，在不同操作系统上的试验证 明了虚存是可以工作的。基于此，虚存已经成为绝大多数现代操作系统中的一个 重要组成部件了。 为使虚存系统能有效地工作，两个因素必不可少。第一，必须有硬件支持的 分页或分段机制。第二，操作系统应具有管理换页或段的软件。接下来，我们分 析一下硬件方面是如何提供支持的，以及必要的控制结构，这些结构由操作系统 创建和维护，但是由内存管理硬件所使用。 2 2 3 分页 术语虚存通常与使用分页机制的系统相关联，虽然基于分段机制的虚存系统 也有使用的，但是由于l i n u x 使用分页机制，所以在此我们只讨论基于分页机制 的虚存系统。基于分页机制的虚存系统首次在a r i a s 上使用，不久以后就得到了 广泛的商业应用。 在简单的分页机制中，每个进程有自己的页表，并且当进程的所有页都被装 入内存时，进程的页表才被创建并被装入内存中。每个页表项包含内存中对应的 使用内存压缩提高系统性能 页的页框号。当讨论基于分页的虚存系统时，同样的页表也是需要的。同样的， 每个进程也对应一个唯一的页表。不同的是，页表项变得更复杂( 如图2 3 所示) 。 由于一个进程的页只有部分在内存中，每个页表项中的一位被用来表示一个页是 否驻留( p ) 在内存中。如果该位表示一个页当前在内存中，那么这个页表项也 包含了该页的物理页框号。 虚地址 页表项 图2 3 页表项 页表项中另一个需要的控制位是修改( m ) 位，表示对应的页的内容从装入 内存中是否被改变过。如果该页没有被修改过，那么在需要换出该页时，就不需 要把该页写到交换区去。可能还会有其它控制位。比如，如果共享和保护实现在 页级别，那么基于这些目的的控制位也是需要的。 页表结构 从内存中读入一个字的基本机制涉及到通过页表，翻译由页号和偏移量构成 的虚地址，或逻辑地址到物理地址的过程。由于每个进程的大小不同，对应的页 表的大小也是不一样的，所以，我们不能期望能在寄存器中装入页表，而只能将 页表保存在内存中。当一个特定的进程运行时，一个寄存器中保存着这个进程页 表的起始地址。虚地址的页号被用来索引页表，查找对应的页框号。得到的页框 号与虚地址的偏移量部分组合，就得到了需要的真实地址。如图2 4 所示。 通过将虚拟地址映射到物理地址，虚拟内存可以以任何顺序映射到系统物理 页面。 9 使用内存压缩提高系统性能 建地址 l i一， im 4， ii 甄搬号i 骼移爨j ， 甲嚣袭 i - - - - i d - 0 l _ i 两撮号 程序分页机制 内存 请求调页 在物理内存比虚拟内存小得多的系统中，操作系统必须提高物理内存的使用 效率。节省物理内存的一种方法是仅加载那些正在被执行程序使用的虚拟页面。 比如说某个数据库程序可能要对某个数据库进行查询操作，此时并不是数据库的 所有内容都要加载到内存中去，而只加载那些要用的部分。如果此数据库查询是 一个搜索查询而无须对数据库进行添加记录操作，则加载添加记录的代码是毫无 意义的。这种仅将要访问的虚拟页面载入的技术叫请求调页。 当进程试图访问当前不在内存中的虚拟地址时，处理器在页表中无法找到所 引用地址的入口。处理器不能将此地址转换成物理地址，这时处理器通知操作系 统有页面错误发生。如果发生页面错的虚拟地址是无效的，则表明进程在试图访 问一个不存在的虚拟地址。这可能是应用程序出错而引起的。例如它试图对内存 进行一个随机的写操作，此时操作系统将终止此应用的运行，以保护系统中其他 进程不受此出错进程的影响。如果出错虚拟地址是有效的，但是它指向的页面当 前不在内存中，则操作系统必须将此页面从磁盘映像中读入到内存中来。由于访 盘时间较长，进程必须等待一段时间直到页面被取出来。如果系统中还存在其他 进程，操作系统就会在读取页面过程中的等待过程中选择其中之一来运行。读取 回来的页面将被放在一个空闲的物理页面框中，同时此进程的页表中将添加对应 此虚拟页面框号的入口，最后进程将从发生页面错误的地方重新开始运行。此时 1 0 使用内存压缩提高系统性能 整个虚拟内存访问过程告一段落，处理器又可以继续进行虚拟地址到物理地址转 换，而进程也得以继续运行。 l i n u x 使用请求调页，将可执行映像加载到进程的虚拟内存中。当命令执行 时，可执行的命令文件被打开，同时其内容被映射到进程的虚拟内存。这些操作 是通过修改描叙进程内存映象的数据结构来完成的此过程，称为内存映射。然而 只有映像的起始部分被调入物理内存，其余部分仍然留在磁盘上。当映像执行时， 它会产生页面错误。这样l i n u x 将决定将磁盘上哪些部分调入内存继续执行。 2 2 4 交换 如果进程需要把一个虚拟页面调入物理内存而正好系统中没有空闲的物理 页面，操作系统必须丢弃位于物理内存中的某些页面来为之腾出空间。如果那些 从物理内存中丢弃出来的页面来自于磁盘上的可执行文件或者数据文件并且没 有修改过，则不需要保存那些页面。当进程再次需要此页面时，直接从可执行文 件或者数据文件中读出。但是如果页面被修改过，则操作系统必须保留页面的内 容以备再次访问，这种页面被称为脏( d i r t y ) 页面j 当从内存中移出来时，它们 必须保存在叫做交换文件的特殊文件中。 相对于处理器和物理内存的速度，访问交换文件的速度是非常缓慢的。操作 系统必须在将这些标记为“脏”的页面写入磁盘和将其继续保留在内存中做出选 择。选择丢弃页面的算法经常需要判断哪些页面要丢弃或者交换。如果交换算法 效率很低，则会发生“抖动”现象。在这种情况下，页面不断的被写入磁盘又从 磁盘中读回来。这样一来，操作系统就无法进行其他任何工作。 一个进程当前经常使用的页面集合叫做工作集。高效的交换策略能够确保所 有进程的工作集保存在物理内存中。l i n u x 使用最近最少使用l r u 页面衰老算 法，来公平地选择将要从系统中抛弃的页面。这种策略为系统中的每个页面设置 一个年龄，它随页面访问次数而变化。页面被访问的次数越多，则页面年龄越年 轻；相反则越衰老。年龄较老的页面是待交换页面的最佳侯选者。 交换区 从内存中换出的页被保存在交换区( s w a pa r e a ) 中，交换区可以使用自己的 磁盘分区进行实现，也可以使用大型分区中所包含的文件来实现。可以定义几种 不同的交换区，最大个数由m a x _ s w a p f i l e s 宏( 通常被设置为8 ) 确定。 如果有多个交换区，就可以允许系统管理员把大的交换空间分布在几个磁盘 上，以便可以同时操作这些交换区；这样处理还允许在系统运行时不用重新启动 系统就可以扩大交换空间的大小。 使用内存压缩提高系统性能 函数1 1r wb l o c k ( ) 进入一个循环，处理b h 数组的所有非空元素。对于每 个缓冲区首部来说，它执行一下操作： 1 检查块大小bs i z e 是否和虚拟设备b 的块大小匹配。_dev 2 设置实际设备标识符( 通常只是把dr d e v 设置成bd e v ) 。 3 根据块号和块大小设置扇区号br s e c t o r 。 4 如果操作是w r i t e 或w r i t e a ，就检查确认这个块设备不是只读的。 5 设置缓冲区首部的b h _ r e q 标志来说明请求这个块的其它内核控制路 径。 6 调用m a k er e q u e s t ( ) 函数，向它传递实际设备的主号、i o 操作的类 型以及缓冲区首部的地址。 m a k e _ r e q u e s t ( ) 函数又要执行一下操作： 1 设置缓冲区首部的b hl o c k 标志。 2 检查确认br s e c t o r 没有超过块设备的扇区数。 3 如果一定要读取这个块，就检查确认它已经不是有效的块( 也就是说， b h _ u p t o d a t e 标志没有置位) 。如果一定要写这个块，就检查确认该块确 实是脏数据( 也就是说，b h _ d i r t y 已经置位) 。如果这两个条件都不成 立，就直接返回而不用请求发送数据，因为这些数据已经没有什么用处 了。 4 禁止局部中断并获得i o r e q u e s t1 0 c k 自旋锁。 5 如果定义了q u e u e 方法，就调用它，或者读取块设备描述符中的 c u r r e n t _ i e q u e s t 域来取得实际设备的请求队列地址。 6 执行以下子步骤中的一步： a ) 如果请求队列为空，就向其中插入一个新的请求描述符，并在稍后 调度激活的策略程序( s t r a t e g y r o u t i n e ) 。 b ) 如果请求队列不为空，就向其中插入一个新的请求描述符，并尽力 将其和队列中的其它请求组织在一起。 2 3 本章小节 l i n u x 系统中采用虚存系统的目的是： 扩展进程可以有效使用的地址空间 扩充动态r a m 的数量( 也就是内核代码和静态数据结构被初始化之后 剩余的r a m ) 来装载进程 而实现这些目的的手段就是请求调页和交换。但是，交换的缺点也是很明显 的。从性能方面来说，模拟的r a m 毕竟不如r a m 。进程对目前已被换出页的 l 矗 使用内存压缩提高系统性能 每次访问都把进程的执行时间增加了几个数量级。简而言之，如果我们最大程度 地追求性能，那么交换就应该是我们万不得已时的一种选择方案；增加r a m 芯 片仍就是处理目益增加的计算需求的最好方法。但是，公正地说，在某些情况下， 交换对整个系统来说还是有益的长时间运行的进程通常只会访问所获得页框的 一半。即使当还有一些r a m 可用时，把未用的页交换出去并使用r a m 作为磁 盘高速缓存也可以提高整个系统的性能。 随后，我们分析了l i n u x