嵌入式系统中的内存压缩技术

R的值，内存控制器产生一个中断，则操作系统采取措施来阻止内存消耗。

在实际地址到物理地址的转换中，一个有用的方法是快速页操作。它允许控制器仅修改CTT项的四个指针，从而将4KB的页面内容换出或清空。快速页操作通过将与4KB页面相关的CTT项全部修改通用行格式（即全为零），从而将这4KB页面的内容全部清空。同样，一对页面可以通过交换它们相关的CTT项的区域指针来交换页面内容。由于没有大量的数据移动发生，快速页面操作速度相当快。

压缩内存控制器的压缩/解压功能是基于LempelZiv算法来进行的，因此下一节将简单介绍一下该算法的思想。

3 内存压缩算法Lempel-Ziv

绝大多数的压缩算法，包括用得特别流行的Lempel-Ziv压缩算法家庭，都是基于对原子记录（Token）字符串的完全重复检测。这个算法虽然不是最好的算法，但是，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）=011=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 编码过程

步  骤	值	公  式	U
0	-	P(0)	0010001101
1	0	P(1)=P(0)++0	0++010001101
2	01	P(2)=P(1)++1	0++01++00++01101
3	00	P(3)=P(1)++0	0++01++00++01101
4	011	P(4)=P(2)++1	0++01++00++011++01
5	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=011
C	000++011++010++101++011=000011010101011

4 操作系统对内存压缩的支持

在压缩内存系统中，内存大小指的是实际内存大小，它比物理内存大。在引导时，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<mc_th_danger<mc_th_interrupt。

我们可以使用轮询和中断相结合的方法进行监控，并对物理内存使用的变化作出反应。通过时钟中断来驱动轮例程，该例程每10ms读取一次SUR的值，并将它与系统设定的临界值比较。当系统处于steady状态时，不用采取任何行动；当使用超过mc_th_acquire，应该增加nr_rsrv_pages来限制内存分配，但这并未引起内存缺乏；当使用超过mc_th_danger，应该增加nr_rsrv_pages到引起内存缺乏，并导致页面分配器和置换进程回收内存页面，一旦进入到该状态，物理内存管理例程会唤醒置换进程回收内存。

（2）回收内存以及清空空闲页面内容以减少使用

以标准的Linux内核为例，操作系统中有两具主要的变量来管理内存太少的情形。这两个变量是nr_free_pages和struct freepages。为了检测内存是否已耗尽，在分配内存前要进行检查。

if(nr_free_pages<freepages.min){

/*内存太少，回收页面*/

}

else

{/*可以进行分配*/

在内存压缩系统中，通过增加一个新变量nr_rsrv_pages来完成此功能。这样就使最小空闲页面数量变为：freepages.min'=freepages.min+nr_rsrv_pages。

通过动态地调整nr_rsrv_pages变量，压缩内存管理例程可以人为地造成内存缺乏的现象，从而引起置换进程回收页面，此时会将调用进程暂时挂起。回收内存包含缩减各种缓冲，并将进程页面置换到磁盘上。当页面返回到空闲页面池时，它们会被清零。我们可以使用前面提到的快速页面操作来减少清空页面操作所带来的开销。

（3）阻塞CPU周期以减少物理内存使用率

当物理内存使用超过监界值mc_th_interrupt，控制器就中断处理器，nr_rsrv_pages进一步增加，然后CPU blocker就开始运行。我们在轮询机制的基础上还使用了中断机制，因为中断机制比轮询机制更加快速。如果在10ms的间隔中，物理内存使用突然上升，硬件中断会比轮询例程更早检测到这一情况。为了更加安全，我们使用CPUblocker来阻塞引起物理内存使用的进程。CPU blocker是空闲线程，它们可以使CPU空忙。由于页面被置换到磁盘是以机器速度运行的，而物理内存使用却可以以内存访问速度运行，速度从而得到增加。当牧师内存使用持续增加，以至换页也无法缓解时，进程需要被阻塞。我们就通过启动CPUblocker来阻塞CPU周期直到换页机制能有效地降低物理内存使用。CPUblocker不会阻塞中断，而且每40ms它就会让出CPU以免其它进程被饿死。
javascript:window.open(this.src);" style="cursor:pointer;"/>
5 内存压缩技术在嵌入式系统中的应用

嵌入式系统是一种特殊的计算机系统，它是一个更大的系统或设备的一部分。通常，一个嵌入式系统是驻留在单处理机底板上的，其应用程序存储在ROM中。事实上，所有具有数字接口的设备——监视器、微波炉、VCRs、汽车等，都使用了嵌入式系统。一些嵌入式系统包含了操作系统，称为嵌入式操作系统。为了满足嵌入式应用的特殊要求，嵌入式微处理器虽然在功能上和标准微处理器基本是一样的，但和工业控制计算机相比，嵌入式微处理器具有体积小、重量轻、成本低、可靠性中，内存仍然是珍贵的资源，因此研究内存压缩技术在嵌入式系统中的应用具有一定的价值。

内存压缩的思想在一些嵌入式操作系统中，实际上已经得到了体现。例如在VxWorks中，当操作系统下载到目标机上时，其中一种方式是将引导程序和VxWorks映像都存放在ROM中。为了将其解压后再从ROM拷贝到RAM。这种基于软件的压缩方式，可以节省ROM空间，但其引导过程相对较慢。

以上的内存压缩技术在ROM中得到了应用，但对于RAM来讲，基于软件内存压缩技术，由于其访问压缩数据可能造成的延迟和不确定性，会对嵌入式系统的实时性造成和。因此它与虚拟内存技术一样，在嵌入式系统中未得到广泛应用。

本文所介绍的内存压缩系统是基于硬件的。在相同基准下，测试结果显示出，该系统的运行速度比标准系统的运行速度快1.3倍。如果要实现相同大小的内存，采用内存压缩系统的硬件费用比购买RAM的费用要低，而且内存越大，其节省的费用越多，可以达到一半的价钱。因此笔者认为在内存资源极其宝贵的嵌入式系统中，实现基于硬件的内存压缩系统具有较大的价值。

结语

本文介绍的内存压缩系统是基于专门的硬件支持，即L3高速缓冲和内存控制器。在目前大多数Pentium以上架构的硬件平台上，只需要对操作系统内核做一些小的屐，或者增加一个设备驱动及服务程序，即可完成此项功能。由于嵌入式系统对实时性的要求，基于硬件的内存压缩技术可以在增大可用内存的同时不影响系统的实时性，其硬件费用相对RAM的价格更低，具有一定的实用价值。

上一页  [1] [2]