内存压缩技术介绍.doc

摘要：介绍内存压缩技术和一个基于硬件的内存压缩系统模型，探讨内存压缩技术在嵌入式 系统中的应用；重点介绍内存压缩系统的硬件要求及操作系统对内存压缩机制的支持；简单 介绍内存压缩中常用的算法 Lempel-Ziv ，并就内存压缩技术在嵌入式系统中的应用问题作一 些探讨关键词：嵌入式系统 内存压缩 压缩内存控制器 Lempel-Ziv 算法1 内存压缩技术介绍为节省存储空间或传输带宽，人们已经在计算机系统中广泛地使用了数据压缩技术在磁介 质存储数据或网络传输数据时，人们使用基于硬件或软件的各种压缩技术当压缩技术在各 个领域都很流行时，内存压缩技术却由于其复杂性而一直未得到广泛使用近年来，由于在 并行压缩一解压算法以及在硅密度及速度方面取得的进展，使得内存压缩技术变得可行内存压缩技术的主要思想是将数据按照一定的算法压缩后存入压缩内存中，系统从压缩内存 中找到压缩过的数据， 将其解压后即可以供系统使用 这样既可以增加实际可用的内存空间， 又可以减少页面置换所带来的开销，从而以较小的成本提高系统的整体性能内存压缩机制是在系统的存储层次中逻辑地加入一层——压缩内存层系统在该层中以压缩 的格式保存物理页面，当页面再次被系统引用时，解压该压缩页后，即可使用。

我们将管理 这一压缩内存层的相关硬件及软件的集合统称为内存压缩系统 内存压缩系统对于 CPU、I/O 设备、设备驱动以及应用软件来说是透明的，但是操作系统必须具有管理内存大小变化以及 压缩比率变化的功能对于大多数的操作系统而言，要实现内存压缩，大部分体系结构都不需要改动在标准的操 作系统中，内存都是通过固定数目的物理页框( page frame )来描述的，由操作系统的 VMM来管理要支持内存压缩，OS要管理的实际内存大小和页框数目是基于内存的压缩比率来确 定的这里的实现内存是指操作系统可的内存大小， 它与物理内存的关系如下： 假设PM是物理内存，RM(t)是系统在t时刻的实际内存，而 CR(t )是压缩比率，在给定时刻 t可支持 的最大实际内存为 RM(t) =CR1( t )X PM然而，由于应用程序的数据压缩率是不依赖于 OS而动态变化的，未压缩的数据可能会耗尽物理内存，因此当物理内存接近耗尽时，操作系统 必须采取行动来解决这个问题2 内存压缩系统的硬件模型目前由于内存压缩的思想越来越引起人们的注意市场上也出现了一些基于软件的内存压缩 器这些内存压缩器主要是通过软件对数据进行压缩，但由于访问压缩数据带来的延迟，它 在系统性能方面改进并不明显，有些甚至降低了系统性能。

本节介绍一种基于硬件的内存压 缩系统模型图1是一个典型的内存压缩系统的硬件模型，包括了压缩内存、 L3高速缓冲、压缩内存控制器等硬件部分其中压缩内存(133MHz SDRAM包含了压缩数据L3高速缓冲是一个共享的、 32MB4路组 相联、可回写的高速缓冲，每行大小为 1KB由两倍数据率(DDR SDRAM制定L3高速缓冲 包含了未压缩的缓冲行， 由于大部分的访问都可以在 L3 高速缓冲中命中， 因此它隐藏了访问 压缩主存引起的延迟 L3 高速缓冲对于存储分级体系中的上层而言就是主存， 它的操作对于 其它硬件，包括处理器和 I/O 来说都是透明的压缩内存控制器是整个内存压缩系统的控制 中心，它负责数据的压缩 / 解压，监控物理内存的使用情况以及实际地址到物理地址的寻址过 程数据压缩过程是这样的：压缩内存控制将 1KB的高速缓冲行压缩后写入压缩内存中，然后将它们从压缩内存中读出后解压 其压缩算法就是 Lempel-Ziv 算法，我们会在下一部分介绍这 个算法压缩机制将压缩的数据块以不同的长度格式存放到内存中压缩内存的存储单元是 一个256字节的区域按照压缩比率不同， 一个1KB的内存块（正好是L3每行的大小）可以 占据0〜4个压缩区域。

压缩内存控制器必须根据长度格式的不同将系统总线上的实际地址翻译成物理内存的中的物 理地址 实际地址是出现在处理器外部总线上常规地址 篁 址用来录十压缩内存的 256 字节 区域 实际地址空间存在于 L1/L2/L3 高速缓冲中， 用于立即访问 而其余的内存内容部分以 压缩形式存在于物理内存中 内存控制器通过查询压缩翻译表 （CTT）执行从实际地址到物理地址的翻译，这个表被保留在物理内存的某个位置图 2是CTT表的格式及内存控制器的寻址模式每个1KB内存块的实际地址映射到 CTT的一项，而CTT每项共16字节，包括四个物理区域地 址，每个地址指向物理内存听一个 256字节区域 对于少于 120 位的块， 如一个全为零的块， 则使用一种特殊的 CTT格式，称为通用行格式在这种格式中，压缩数据全部存放在 CTT项中，代替了四个地址指针 因此，一个1KB的通用块仅占用物理内存中的 16字节，其压缩比率达到 64： 1 压缩内存控制器中有一系列的寄存器用于监控物理内存使用 Sectors Used Register（SUR）向操作系统报告压缩内存的使用情况 The Sectors Used Threshold Registers,SUTHR 和 SUTLR用于设置内存耗尽情况的中断入口点。

SUTLR寄存器是PCI中断电路INTA的入口，而SUTHF寄存器是NMI中断的入口当 SUR超过了 SUTLR的值，内存控制器产生一个中断， 则操作系统采取措施来阻止内存消耗在实际地址到物理地址的转换中，一个有用的方法是快速页操作它允许控制器仅修改 CTT项的四个指针，从而将4KB的页面内容换出或清空 快速页操作通过将与 4KB页面相关的CTT 项全部修改通用行格式（即全为零），从而将这4KB页面的内容全部清空同样，一对页面可 以通过交换它们相关的 CTT项的区域指针来交换页面内容由于没有大量的数据移动发生， 快速页面操作速度相当快压缩内存控制器的压缩 /解压功能是基于 LempelZiv 算法来进行的， 因此下一节将简单介绍一 下该算法的思想3 内存压缩算法 Lempel-Ziv绝大多数的压缩算法， 包括用得特别流行的 Lempel-Ziv 压缩算法家庭， 都是基于对原子记录（Toke n）字符串的完全重复检测这个算法虽然不是最好的算法，但是， Lempel-Ziv 算法强调的是算法的简单与取得高压缩率的速率，因此它还是在内存压缩中得到了广泛的应用Lemple-Ziv算法(简称LZ)是编码时将一个位串分成词组，然后将数据流描述成一系列的对。

每个对组成一个新的词组，它包含一个数字(前一个词组的标识)和一个位(被附加到前一 个词组上)这种编码方式很庞大， 可是一旦应用到适合的字符串， 它就是相当有效率的编码 方式下面举例说明这种算法是如何编码的表示连接( 010++1=0101)， U=0010001101 是未被压缩的字符串 C 是压缩后的字符串 P(x)表示词组数x先看一下 U=0010001101发现，它可以被写为 U=0++010001101，因此得 到 P( 1)=P(0)++0现在继续将其写为 U=0++02++0001101,可得到 P(2)=P ( 1)++1现在 我们已经将 P( 2)描述为上一词组和一个新的位的组合下一步， U=0++01++00++01101，并得到 P(3)=P( 1)++0现在我们注意到， 有 U=0++01+00+011++01,而 P(4)=01 仁P(2)++1， 最后得到 P( 5) =P(1)++1 运算的步骤如表 1 所列一旦创建了表 1，就有了整个编码的图表要创建 Lempel-Ziv 数据流，则依照公式创建对 如果公式是 P(x)=P(A)++B，则每个对为(A++B。

因此 P( 1)=P(0)++0 变为(00++0), P( 2) =P(1)++0 变为( 01++0)，依此类推，将所有这些对连接起来，就得到了最后的字符串，结果 如表2所列这样，C就变成000011010101011，看来比U要长得多但这里由于U的长度短， 因此未能看出优势，而且包含 P( 0)的公式都没有压缩，所以也引起了长度增加Lempel-Ziv 字符串的解码是很简单的，就是抓住其中的对，对照表 1 进行重构表 1 编码过程步 骤 值 公 式 U0 - P(0) 00100011011 0 P(1)=P(0)++0 0++0100011012 01 P(2)=P(1)++1 0++01++00++011013 00 P(3)=P(1)++0 0++01++00++011014 011 P(4)=P(2)++1 0++01++00++011++015 01 P(5)=P(1)++1 0++01++00++011++01表 2 如何创建编码字符串公 式 P(1)=P(0)++0 P(2)=P(1)++1 P(3)=P(1)++0 P(4)=P(2)++1 P(5)=P(1)++1对 00++0=000 01++1=011 01++0=010 10=++1=101 01++1=011C000++011++010++101++011=0000110101010114 操作系统对内存压缩的支持在压缩内存系统中，内存大小指的是实际内存大小，它比物理内存大。

在引导时， BIOS 向操作系统报告的内存大小就比实际安装的物理内存要大例如，硬件原型安装的是 512MB的SDRAM但BIOS向操作系统报告的内存大小为 1GB当应用程序数据以 2 : 1或更高的比率压缩时，实际内存的工作方式与一般操作系统的内存工作方式是相同的但当应用程序以未压 缩数据来填充内存时 （如一个zip文件不可能达到2: 1的压缩比率），由于一般的OS只看到实际地址空间，因此不能意识到物理内存已经耗尽例如，一个操作系统的实际内存为 1024MB而牧师内存为 512MB这时实际内存已经分配了 600MB系统显示还有 424MB的空闲内存但是由于已分配内存的压缩率很低，此时物理内存的耗用已经接近 512MB如果再近一步地分配内存，那么系统就会因为物理内存的耗尽而崩溃，尽管它仍然显示还有 424MB的空闲内存这种情况下，必须由操作系统提供对压缩内存进行管理的支持由于内存压缩是一个比较新的概念，一般的情况作系统都没有这样的机制来区分实际地址和 物理地址，也不能处理“物理内存耗尽”的情况不过，只要对操作系统内核做一些小的改 动或者在操作系统之上增加一个设备驱动程序，即可达到目的一般来说，要从以下几方面对压缩内存进行管理。

1 ）监控物理内存使用情况通过轮询或中断法，查看物理内存的使用情况，并在物理内存耗尽前给出警告压缩内存管理例程是通过压缩内存控制器中的一些寄存器来实现对物理内存的监控 SUR报告物理内存的使用情况，SUTHR和SUTLR用于设置中断临界值压缩内存管理算法是基于物理内存使用 的 四 种 状 态 ， 分 别 为 steady 、 acquire 、 danger 和 interrupt ， 其 临 界 值 的 关 系 是 mc_th_acquire