一种避免页迁移的混合内存页管理策略

刘翠梅，杨 璇，贾刚勇，韩光洁

1(常州机电职业技术学院 信息工程学院，江苏 常州 213164)2(河海大学 物联网工程学院，江苏 常州 213022)3(杭州电子科技大学 计算机学院，杭州 310018)

1 引 言

近年来，移动终端和云计算的快速发展都对内存容量的需求日益提高.以动态随机存储器为主的内存系统具有易失性和高能耗两大缺点，于是对散热系统提出了更高的要求.目前，内存系统的能耗问题已经成为限制移动终端和云计算发展的一大瓶颈[1].

然而，相变存储器(Phase Change Memory，PCM)凭借其非易失性、能耗低、存储密度大、字节可寻址等诸多优势，为内存系统设计带来了新的前景和契机.

1)字节寻址，可以保证相变存储器可以按照随机存储器的字节访问方式与处理器进行交互，不用改变内存系统的寻址方式；

2)非易失性，可以提供持久的数据存储功能；

3)存储密度大，可以提供远超于动态随机存储器的存储密度和更低的能耗，非常适合移动终端的体积小和云计算的大容量需求特征.

但是，相变存储器也存在一些缺陷，主要体现在不能就地更新、读写不对称和有限的寿命.相变存储器写前需要擦除，不能直接进行写操作，而且写操作的时间远比读操作的时间长.相变存储器的读延迟约为50n，拥有与动态随机存储器相媲美的读取带宽.但写延迟比读延迟大得多，一般达到200～300ns.相变存储器元件经过多次的写操作后，一般在108～109次[2]，其相变元件会失效.基于单一的相变存储器构建内存系统目前还需解决写开销和寿命等问题，还尚未成熟.

基于相变存储器的特征，目前有两种主流的混合内存架构，动态随机存储器和相变存储器处在同一层次，共同组成统一的内存系统.混合内存架构即利用了动态随机存储器的优势也开发了相变存储器的优点，从而满足需求.

第一种混合内存架构是用动态随机存储器作为相变存储器的缓存[8]，这种架构存在一些问题：

1)内存的大小由相变存储器的容量决定，跟动态随机存储器的大小无关.也就是说动态随机存储器只能作为缓存.从而浪费了一些宝贵的存储资源；

2)实现起来比较复杂.涉及数据一致性问题，内存系统需要保证动态随机存储器上的数据和相变存储器上数据的一致性.这就增加了内存系统的实现复杂度.

3)增加了系统开销.内存访问过程需要先访问动态随机存储器，如果动态随机存储器中能找到相应数据，那么内存访问就结束了.但是，如果动态随机存储器中没有找到相应的数据，需要再一次访问相变存储器，从而导致了内存平均访问时间增加.

第二种混合内存架构是将相变存储器和动态随机存储器作为同级存储介质.这种架构能够避免第一种架构存在的问题，是目前的研究热点，本文的研究就是基于这种架构.针对这种内存架构，主要解决的问题就是数据存放.因为相变存储器和动态随机存储器处于相同级别，需要挖掘两种存储介质的优点，即将读频繁的数据放在相变存储器中，将写频繁的数据放在动态随机存储器中.目前主要通过动态迁移策略来完成这一目标.但是动态迁移存在几个缺点：

1)开销大.将页从一种存储介质迁移到另一种存储介质中，其实就是内存中两种存储介质间的数据拷贝，需要花费大量的处理器时间；

2)影响系统的响应时间.如果被访问的数据刚好处于迁移过程，那么访问需要等待，延迟了访问过程.

本文提出了一种避免页迁移的混合内存页管理策略(PMP)提高混合内存系统访问效率.本文提出的避免页迁移的混合内存页管理策略在给数据分配物理页框前，先通过模拟的方法分析每个虚拟页的使用行为，将虚拟页划分成两种类型，一种是读频繁页，一种是写频繁页.在给虚拟页分配物理页框时，根据虚拟页的类型映射到相应的存储介质中.读频繁页映射到相变存储器，写频繁页映射到动态随机存储器.系统运行过程中不再进行页迁移操作，避免因页迁移而导致的系统开销.实验数据显示，本文提出的避免页迁移的混合内存页管理策略能够有效的提高混合内存系统的效率.

本文在第二部分着重介绍相关的工作和存在的问题，第三部分详细阐述了本文的动机；第四部分给出了算法的流程，第五部分介绍了实验验证方法及实验结果；最后，总结全文.

2 相关工作

目前基于相变存储器和动态随机存储器的混合内存管理主要有两种方法：一种是基于数据冷热度进行内存分配，一种是基于页的读写倾向进行内存分配.

一种比较典型的基于数据冷热度分配物理页框的算法是由Lee等人提出的混合内存置换算法CLOCK-DWF(CLOCK with dirty bits and write frequency)[9].该算法根据请求类型分配物理内存空间.为读请求页面分配相变存储器，为写请求页面分配到动态随机存储器.当在相变存储器上进行写操作时，把相应的页面迁移至动态随机存储器.若此时动态随机存储器已满，替换动态随机存储器中的最近最久未使用的页面，并将相变存储器中页迁移到该页.这种算法将所有涉及写操作的页全部放在动态随机存储器中，当动态随机存储器空间不足时，会导致频繁的替换，甚至抖动，降低性能.同时算法会增加大量从相变存储器到动态随机存储器的迁移操作，也就是增加了大量的性能开销，降低了系统性能.

一种比较典型的基于读写倾向分配物理页框的算法是由Seok等人提出的LRU-WPAM算法[10,11].LRU-WPAM算法对每个页面进行实时监控，记录每个页面的读写操作.根据页面的历史读写信息，基于一个权值的计算公式，通过这个权值确定页面的读写倾向.并且为动态随机存储器和相变存储器分别维护一个读倾向链表和写倾向链表.如果在动态随机存储器的读倾向链表中一个页面读倾向性超过一定阈值时，则将该页从动态随机存储器迁移到相变存储器中.如果在相变存储器的写倾向链表中一个页面写倾向性超过一定阈值时，则将该页从相变存储器迁移到动态随机存储器中.这种算法会导致一些页面在两种存储介质间来回反复迁移，增加大量的性能开销，降低系统性能.

不同于上面两种算法，MHR-LRU算法[12]维护了一个动态随机存储器的写链表DWL，只有在写命中时，链表才会发生改变，写命中的页面移动到链表的MRU端，这样使得MRU端的页面写操作更频繁，而LRU端页面写操作更少.当页面在LRU链表的非LRU端或在DWL链表的LRU端，有写请求到达，为了在动态随机存储器中为写请求腾出空间，会把在DWL链表LRU端的页面迁移至相变存储器中.如果数据不在DWL链表中或同时在两个链表的LRU端则不进行迁移而是直接进行置换.因为并不监控相变存储器的写操作，所以相变存储器中写频繁的页面会一直在相变存储器中进行写操作.降低了相变存储器的寿命.

APP-LRU算法[13]额外维护了一个历史元数据信息，记录访问过磁盘的物理页的读写历史，基于历史元数据信息来预测页面的读写趋势，在分配物理页框时将写倾向页面分配到动态随机存储器中.但是，这种算法存在几个问题：

1)进程的运行是动态的，即使同一个进程的两次运行其使用的物理内存也是不同的，所以记录物理内存页框来预测页的读写倾向性是不准确的[15]；

2)该算法也采用了迁移，同样增加了系统开销，降低了系统性能[16].

以上的这些方法在进行混合内存页管理时，数据采集都是通过监控物理页面的读写，或是基于单次的读写请求直接分配页面的存储介质，之后再通过迁移来实现物理分配[17].然而这些依赖迁移的混合内存管理方式存在大量的来回迁移操作，这些迁移增加了大量的系统开销，降低系统的性能.

3 动 机

3.1 评价模型

为了评价各算法的效果，本文提出了一个评价模型.首先，判断页面最适合位置的算法，因为相变存储器元件的理论写入次数一般是108次，运行时间按照连续运行时间计算，相变存储器的最大运行时间和相变存储器的写入频率成反比.相变存储器的写入频率可以按照相变存储器单位内存(页)在单个进程的运行周期内被写入次数来表示.而且可以获得满足预期运行时间的页面被写入次数的阈值.一个页面被写次数不超过该阈值时，该页面可以被分配到相变存储器中.本文使用Th表示读写比例的一个阈值，如果一个页面读写比例大于Th时，将该页面分配到相变存储器.

算法1.页面分配算法

输入：

Th：读写阈值

Tpcm：相变存储器预期运行时间

C：相变存储器写上限

T：进程运行时间

W：写阈值

Wn：第n个页的写次数

Rn：第n个页的读次数

N：进程占用内存总页数

输出：

适合的存储介质

算法：

Begin：

1：Tpcm= C*T/W;

2：W=Tpcm/(C*T);

3：if Wn>W

4： 分配DRAM；

5：else

6： if Rn/Wn >Th

7： 分配PCM；

8： else

9： 分配DRAM；

End

算法1给出了一种页面分配算法用于判断一个页面最适合的存储介质.根据这个算法，同时结合其他页面分配算法的结果(不包括迁移)，可以对不同算法页面错误的分配做出评价.进程运行过程中页面迁移的总次数，以及被分配至相变存储器中页面的写次数也分别作为评价指标之一.如果仅使用动态随机存储器而不使用相变存储器时，相变存储器中的写次数和两种存储介质间的迁移操作都是最优的，但这种情景无法发挥混合内存的优势，也无法发挥相变存储器大容量和非易失性优点，无法解决目前动态随机存储器的瓶颈问题，所以动态随机存储器和相变存储器的利用率也会作为评价指标之一.

3.2 现有算法的量化分析

现有对于混合内存架构的内存分配算法主要有以下几个缺点：

1)增加大量的迁移，从而增加系统性能开销；

2)增加不必要的写操作，从而导致相变存储器寿命缩短；

3)对动态随机存储器的大量需求，无法解决能耗问题.

3.2.1 迁移问题的分析

图1给出了四种不同算法在读取一个文件时的所产出的总迁移次数.这四种算法都涉及不同程度的迁移操作.LRU-WPAM算法需要4000多次的迁移操作，最少的APP-LRU算法，也需要100多次的迁移操作.这么多的迁移操作给系统带来了巨大的性能开销，严重的降低了系统的性能.

图1 各算法迁移次数Fig.1 Migration times of algorithms

为了详细分析各页面在系统运行过程中的迁移情况，图2给出了LRU-WPAM算法不同类型页面的迁移情况.页面迁移具有较强的聚集特征，大量迁移聚集在少量页面，其中单个页面的最大迁移次数3254，这部分页面的读操作和写操作均十分频繁，所以其页面的权值波动很大，导致页面频繁的在两种介质间迁移，造成该问题的原因是权值的计算具有局部性，受到局部访存行为的影响，无法描述页面在全局的访存行为.

3.2.2 相变存储器写操作分析

图3给出了4种不同算法在相变存储器中进行写操作的次数.虽然APP-LRU和MHR-LRU在迁移次数上相对较少，但是这两种算法存在大量的相变存储器写操作.APP-LRU算法的主要问题在于，页面迁移发生在页面分配的过程中，历史访存元数据信息只有在页面再次进入内存时为其分配合适的位置.合适位置和LRU-WPAM算法一样，具有局部性.而且对于一个频繁访问的页面，因为该页面在LRU链表中始终处于MRU端，那么这个页面被迁移的概率很小，即使这个页面在相变存储器中且进行了很多的写操作，该算法也无法将页面迁移至动态随机存储器，这就导致了相变存储器执行了大量的写操作.而MHR-LRU算法既有大量的迁移操作又有大量的相变存储器写操作.MHR-LRU算法产生大量写操作的原因在于它注重于把动态随机存储器中写较冷的页面迁移至相变存储器，但对于相变存储器中频繁进行写操作的页面并没有进行相应的处理，这导致了该算法虽然迁移次数较少，但其并没有有效的减少相变存储器中的写操作次数.在相变存储器中进行大量的写操作，对于相变存储器元件寿命损耗巨大，降低系统的执行效率，带来包括时间成本和设备成本的大量开销.

图2 LRU-WPAM算法迁移页面百分比及对应的迁移次数Fig.2 Migration page ratio/migration times of LRU-WPAM algorithm

图3 不同算法在相变存储器中执行写操作的次数Fig.3 PCM write times of different algorithms

3.2.3 动态随机存储器需求分析

图4给出了四种算法在动态随机存储器上读操作次数.本文使用动态随机存储器上读操作次数来反映各种算法对动态随机存储器的需求大小.从图1到图3可以看出Clock-DWF算法迁移次数和相变存储器中写操作次数相对比较合理，但是图4可以发现Clock-DWF算法对于动态随机存储器的需求最大，远远大于其他算法.对于动态随机存储器需求越大，功耗也就越大.

通过对现有算法的量化分析，特别针对迁移次数、相变存储器上写次数和动态随机存储器上读次数，我们可以发现，现有的算法存在一个主要的问题，无法获取页面的读写行为，从而导致内存页分配存在一定的错误.进而只能通过迁移来弥补.本文正是针对这个问题提出了一种新的解决方法.

图4 四种算法在动态随机存储器上读操作次数Fig.4 DRAM read times of four different algorithms

3.2.4 现有算法总结

现有算法存在的大量迁移操作主要原因在于：在进行数据划分时统计物理页框的访问行为特征.然而物理页框的访问行为特征无法预先获取，这是因为物理页框是由操作系统的内存管理系统分配的.而且物理页框的分配是实时动态的，无法重现的一种行为.

但是，虚拟页的访存行为特征相对就比较固定，可以更加准确的反映数据的读写倾向性，从而可以更加有效的用于数据划分.而且虚拟页的访存行为可以通过模拟获取.基于这个特征，本文提出了避免迁移的混合内存管理策略.

4 避免迁移的混合内存管理策略(PMP)

因为模拟器可以获取进程每个虚拟页的读写行为特征，基于这个读写行为特征可以指导操作系统混合物理内存页管理，将读频繁页分配到相变存储器中，将写频繁页分配到动态随机存储器中.并且获得的虚拟页读写行为特征比物理页读写行为特征更能准确的反映页行为特征.物理页框是动态的，而虚拟页是静态的.所以本文提出的避免迁移的混合内存管理策略(PMP)是基于模拟器获得的页读写行为特征进行指导操作系统混合内存物理页框分配，一旦给虚拟页分配了物理页框，在系统运行的过程中不进行迁移的操作.从而避免了迁移带来的系统开销.

图5给出了避免迁移的混合内存管理策略(PMP)的整体架构图.图中主要包括4部分的内容.第1部分通过模拟器统计进程每个页面的读写操作；第2部分在系统中构建一个进程级的页面行为统计表，统计各进程所有页面的读写；第3部结合系统混合内存配置以及系统进程行为，判断各页面是读频繁型还是写频繁型；第4部分根据页面的读/写频繁型，分配相应存储介质.将读频繁型页面分配到相变存储器中，将写频繁型页面分配到动态随机存储器中.

1)基于模拟器统计进程页面的读写操作.避免迁移的混合内存管理策略(PMP)预先使用模拟器运行进程，模拟器中可以获取进程各页面的读写次数.因为涉及内存管理，PMP在统计进程页面的读写次数时，采用的是进程的虚拟页.如果基于物理页框记录读写次数准确度会受到影响.同一个虚拟页面由于页替换策略，导致映射到不同的物理页框.所以采用虚拟页面作为统计基础能够得到准确的结果.

图5 避免迁移的混合内存管理策略(PMP)的整体架构图Fig.5 Framework of PMP

2)构建进程级的页面行为统计表.在系统中需要给每个进程分配一个独立的数据结构，即进程的页面行为统计表，如表1.在这个统计表中，进程每个页面占用一个记录，进程的页面数决定了进程所对应页面行为统计表的大小.在页面行为统计表中主要记录了每个页面的读操作次数以及写操作次数.

表1 进程的页面行为统计表Table 1 Page behavior of process

3)确定进程各页面的读/写频繁型.虽然通过各进程的页面行为统计表可以获得了进程各页面的读/写次数，但是还是无法判断各页面的读/写频繁型.页面的读/写频繁型还与混合物理内存的配置有关，即混合物理内存中相变存储器占用多少物理内存空间，动态随机存储器占用多少物理内存空间.算法2给出了确定进程各页面的读/写频繁型的过程.

4)分配物理内存.根据页面的读/写频繁型，分配物理内存.如果是读频繁型，分配相变存储器，如果是写频繁型，分配动态随机存储器.

算法2.确定页面读/写频繁型的算法

输入：

Ri：页面的读次数

Wi：页面的写次数

PCM：相变存储器的容量

DRAM：动态随机存储器的容量

输出：

读频繁型/写频繁型

算法：

Begin：

1：T = Ri/Wi;

2：T1 = PCM/DRAM;

3：if T>T1

4： 读频繁型；

5：else

6： 写频繁型；

End

5 实验结果

本文使用Multi2Sim模拟器对测试程序进行了仿真运行，来获取不同进程页面的读写行为.使用真实的访存痕迹对不同的算法进行模拟.并按本文提出的避免迁移的混合内存页管理策略对页面进行划分.

5.1 实验配置和方法

为了实现进程页行为特征分析，在默认的Multi2Sim模拟器上进行修改，增加进程页面的行为统计表.本文采用的进程页面大小为操作系统默认的4KB.基于大量的程序访存行为的特征分析，用于评价多种不同的算法，并在其中挑出了三类有代表性的访存应用作为测试程序，如表2所示.

表2 测试程序集Table 2 Benchmarks

因为实验所测试程序是单个进程运行时产生的访存行为，单个进程实际使用的页面数量有限，所以我们设置了总的混合内存大小为400个物理页框的大小，既1.6MB.其中相变存储器占3/4，即300个页框，而动态随机存储器占1/4，即100个页框.FFT的测试程序用于验证所需页框小于系统配置的混合内存大小，但是大于系统配置的动态随机存储器大小.OCEAN测试程序用于验证所需页框大小略大于系统配置的混合内存大小.而OpenFile测试程序用于验证所需页框大小大于系统配置的混合内存大小.

5.2 实验结果

图6给出了FFT测试程序在不同算法下对比结果.图6(a)给出了不同算法迁移次数的对比，图6(b)给出了不同算法对相变存储器的写操作次数对比，图6(c)给出了不同算法对动态随机存取读操作次数对比.算法在动态随机存储器读操作次数主要用于反映算法对动态随机存储器的容量敏感度.

图6 FFT测试程序在不同算法下的对比结果Fig.6 Comparisons of FFT test programs under different algorithms

图7 OCEAN测试程序不同算法下的对比结果Fig.7 Comparisons of OCEAN test programs under different algorithms

从图6中可以发现,LRU-WPAM算法所需迁移次数远远大于其他算法，而且该算法对相变存取的写操作和对动态随机存储器的需求都比较大.MHR-LRU和APP-LRU两个算法虽然跟本文提出的PMP算法一样没有迁移，但是这两个算法产生大量的相变存储器写操作.CLOCK-DWF算法在运行FFT测试程序时跟本文提出的算法在性能比较接近，但是CLOCK-DWF需要少量的迁移，而PMP不需要任何迁移，所以PMP还是优于CLOCK-DWF.

图7给出了OCEAN测试程序在不同算法下对比结果.当进程所需页框大小略大于系统配置的混合内存大小时，PMP同样呈现出很好的结果.

图8给出了OPENFILE测试程序在不同算法下对比结果.针对进程所需页框大小大于系统配置的混合内存大小时，PMP也能获得很好的结果.

6 结束语

本文提出了一种避免页迁移的混合内存页管理策略(PMP)提高混合内存系统访问效率.PMP主要包括四部分的内容.第一部分通过模拟器统计进程每个页面的读写操作；第二部分在系统中构建一个进程级的页面行为统计表，统计各进程所有页面的读写；第三部结合系统混合内存配置以及系统进程行为，判断各页面是读频繁型还是写频繁型；第四部分根据页面的读/写频繁型，分配相应介质的物理内存页.将读频繁型页面分配到相变存储器中，将写频繁型页面分配到动态随机存储器中.实验结果表明本文提出的PMP算法能够高效的管理混合内存.