CN104298615B - 一种存储器交换分区损耗的均衡方法 - Google Patents

Abstract

本发明公开了一种存储器交换分区损耗的均衡方法，属于移动设备中的存储技术领域，它包括步骤1、NVRAM Swap分区上的每一个页槽设有一个记录页槽年龄的计数器，页槽每写一次，就将计数器加1；步骤2、建立一个用于保存NVRAM Swap分区中的页槽信息的小顶堆，小顶堆根据计数器上的页槽年龄，将最年轻的页槽置于堆顶；还建立一个用于保存所有空闲页槽的双向链表；步骤3将双向链表表头页槽与堆顶页槽的年龄之差，与阈值比较，确定要使用的页槽。本发明的技术效果是，在NVRAM Swap分区中找到了既空闲的、又写次数较少的页槽来承接的DRAM页面，实现了NVRAM Swap分区写的损耗均衡。

Description

一种存储器交换分区损耗的均衡方法

技术领域

本发明属于移动设备中的存储技术领域，具体涉及一种存储器交换分区损耗的均衡方法。

背景技术

随着移动微处理器和移动操作系统的发展，移动设备(例如智能手机，平板等)越来越普及，针对移动设备设计的应用功能越来越强大。这些功能丰富的应用一方面能帮助提高移动设备的用户体验，另一方面却需要更多的内存资源，存储资源。在现在的所有的移动设备中，都使用随机存取存储器(DRAM)作为内存。通过增加DRAM的大小，在一定程度上可以满足应用程序对内存资源的需求。但DRAM的增加会导致成本的上升，且DRAM耗电量大(，最多可占整个系统功耗的30％)，电池消耗快，同样影响用户体验。

Android操作系统是基于Linux kernel的操作系统，Linux kernel提供了通过交换分区(Swap分区)的方法来解决内存资源不足的问题。当内存资源不足时，操作系统会将一些不经常使用的内存页面放到Swap分区，从而减少对内存的占用。传统的Swap机制使用磁盘或闪存等块设备(Block Device)作为Swap分区，当内存资源紧张时，操作系统将一些不活跃的内存页面写回到磁盘或闪存，它们之间的数据传输由I/O驱动程序负责。Swap分区通常被划分为页槽(Page Slot)来进行管理，每个页槽的大小等于内存页面的大小以便于用来存储从内存换出的页面。

大多数的移动设备都使用eMMC接口的闪存作为存储设备。用闪存作为Swap分区虽然能够解决内存不足的问题，但使用闪存作为Swap分区仍有两个主要的问题：1)闪存速度慢且内存和闪存之间的数据传输需要I/O调度，读写延迟较大；2)闪存擦写次数有限，若将闪存作为Swap分区，频繁的换入/换出会大大的降低闪存的使用寿命。

近几年，随着半导体技术的发展，新型非易失存储器(NVM)，包括相变存储器(PCM)，忆阻器(memristor)等，正在受到越来越广泛的关注。由这些新型NVM所产生的RAM有PCRAM、STT-RAM和RRAM等，我们将这些RAM统称为非易失性随机存取存储器(NVRAM)。

保存在NVRAM里的数据具有掉电不丢失的特性，即非易失性，NVRAM能像动态随机存取存储器(DRAM)一样按字节寻址，且读写性能与DRAM相当。与DRAM相比，它在静态功耗和可缩性上具有很大的优势。目前国内外很多学者都提出了用NVRAM替代DRAM，从而使系统具有更低的功耗和扩展性。考虑到NVRAM的优点，参考文献[1]提出了以NVMRAM作为Swap分区，同时NVRAM直接和内存总线相连，NVRAM与DRAM在系统中处于同一层次。当DRAM不足时，操作系统将不活跃的DRAM页面通过内存接口拷贝到NVRAM，从而缓解内存的压力，当需要时，再将这些页面通过内存接口拷贝到DRAM。

用NVRAM作为Swap分区虽然具有很多优点，但目前NVRAM都存在耐久型低的缺点，表1给出了几种NVRAM与DRAM的特性对比。

表格1存储器性能比较

性能参数	PCRAM	RRAM	STT-RAM	DRAM
					耐久性	108	108	>1015	∞
读延迟(纳秒)	20-50	10-50	2-20	30
					写/擦除延迟(纳秒)	50/120	10-50	2-20	15
存储单元面积(F2)	6-12	6-10	6-20	6-10
					是否需要定期刷新	否	否	否	是

由表中可以看出，与相比于DRAM，NVRAM具有有限的擦写次数。为了延长NVRAM的使用寿命，现有的技术可以分为两类：减少写和损耗均衡。减少写主要通过减少对NVRAM的写从而达到延长使用寿命的问题。损耗均衡是将写请求平均的分布在NVRAM所有的存储单元中，防止某个存储单元因过度的写操作而过早损坏，从而达到延长NVRAM使用寿命的目的。目前还没有针对NVRAM的Swap分区的损耗均衡算法，目前的损耗均衡算法都是针对NVRAM做内存，与本发明相关的针对NVRAM做内存的损耗均衡方法有以下两种：

一是基于数组(Array-Based)的损耗均衡方法，详见于参考文献[2]。如图1所示，NVRAM的全部页面(Physical Pages)被组织为一个数组，从0到M-1，每个NVRAM页面都有一个计数器(counter)记录它们被写过多少次，即它们的年纪。标兵指针(Pivot Pointer)把这个数组分为了两部分，下半部分越靠近Pivot Pointer的NVRAM页面年纪越大。当一某个NVRAM页面q被写了R次，就从p上面的K个NVRAM页面中找出一个最年轻的页面y，将y与q相交换，即原来写q，现在就去写y。写过之后Pivot Pointer移动到y的前面，这样就保证了y离Pivot Pointer越来越远，因为Pivot Pointer永远向上移动，y不会被立即用到。这个算法最基本的原理就是把年纪比较大的NVRAM页面放在比较远的地方，这样它们就会被较少的被使用到。

这种方法具有以下的缺点：

1)交换比较频繁，带来了很多额外的写，而且减低了性能；

2)在页面上不能区分写为均布的或者集中于一个点上。

二是基于段交换(Segment Swapping)的损耗均衡方法。中国专利文献CN102981972 A于2013年03月20日公开了一种相变存储器的损耗均衡方法，该方法把NVRAM分为多个段，每个段都用一个损耗均衡计数器来表示该段被写了多少次，通过将写次数较少的段和写次数较多的段进行交换，从而达到损耗均衡的目的。这种方法具有以下的缺点：

1)技术精度较差，不能如实的反应每个段内被写的情况；

2)段的大小通常比较大，远大于一个页面的大小，每次段交换的代价比较大。

要将写操作均匀的分布在NVRAM Swap分区中，即达到损耗均衡的目的，应当解决以下两个问题：

1)如何管理NVRAM Swap分区中的页面，使得其既方便分配和回收，又方便让他们损耗均衡；

2)怎样把被写次数较多的页面和被写次数较少的页面进行交换，防止某些页面被过早的写坏，从而达到损耗均衡的目的。

以上使用的参考文献分别是

参考文献[1]：K.Zhong,X.Zhu,T.Wang,D.Zhang,X.Luo,D.Liu,W.Liu,and E.H.-M.Sha,“DR.Swap:Energy-efficient paging for smarthpones,”in Proceedings ofISLPED,2014,pp.81–86.(作者：K.Zhong,X.Zhu,T.Wang,D.Zhang,X.Luo,D.Liu,W.Liu,andE.H.-M.Sha，论文题目：DR.Swap：智能手机的高能效分页机制，会议名称：低功耗电子设计(ISLPED)，年份：2014，论文集页码：81-86)

参考文献[2]：C.-H.Chen,P.-C.Hsiu,T.-W.Kuo,C.-L.Yang,and C.-Y.M.Wang,“Age-based PCM wear leveling with nearly zero search cost,”in Proceedings ofDAC,2012,pp.453–458.(作者：C.-H.Chen,P.-C.Hsiu,T.-W.Kuo,C.-L.Yang,and C.-Y.M.Wang，论文题目：近零成本的基于年龄的PCM损耗均衡方法，会议名称：设计自动化(DAC)，年份：2012，论文集页码：453-458)

以下将NVRAM Swap分区的页面称为页槽，以与DRAM页面相区分。

发明内容

本发明所要解决的技术问题就是在NVRAM Swap分区管理子系统中提供一种存储器交换分区损耗的均衡方法，该方法在把不活跃的页面从DRAM移到NVRAM Swap分区去时，能从NVRAM Swap分区中找出一个空闲的、且写的次数较少的页槽来存放从DRAM中换出来的页面，以实现写的损耗均衡。

本发明所要解决的技术问题是通过这样的技术方案实现的，它包括有以下步骤：

NVRAM Swap分区上的每一个页槽设有一个记录页槽年龄的计数器，页槽每写一次，就将计数器加1；

建立一个用于保存NVRAM Swap分区中的页槽信息的小顶堆，小顶堆根据计数器上的页槽年龄，将最年轻的页槽置于堆顶；还建立一个用于保存所有空闲页槽的双向链表；

将双向链表表头页槽与堆顶页槽的年龄之差，与阈值比较，确定要使用的页槽。

由于每一个页槽都有年龄记录，根据双向链表找出空闲页槽，根据小顶堆找到最年轻的页槽，两个页槽的年龄之差控制阈值之内，这样，在NVRAM Swap分区中找到了既空闲的、又写次数较少的页槽来承接的DRAM页面，从而实现了NVRAM Swap分区写的损耗均衡。

附图说明

本发明的附图说明如下：

图1为背景技术中基于数组的损耗均衡方法的NVRAM的页面结构示意图；

图2为本发明运行环境的层级结构示意图；

图3为NVRAM Swap分区组织结构图；

图4为小顶堆的组织结构图；

图5为双向链表的数据结构图；

图6为NVRAM Swap分区的页槽选择流程图；

图7为top页槽与head页槽交换的示意图；

图8为本发明的损耗均衡结果测试图。

具体实施方式

下面结合附图和实施例对本发明作进一步说明：

本发明的运行环境是：一台移动设备，它包含CPU，DRAM，Flash，NVRAM等必要的硬件设备，能够运行基于Linux kernel的操作系统。

本发明运行环境的层级结构如图2所示，最顶层是应用程序1，在应用程序之下是Android操作系统2的Dalvik虚拟机21以及运行库22，再之下是Linux kernel 3；Linuxkernel中包含了内存管理31、进程管理32和设备驱动程序33等；最下层具体的硬件4，包括DRAM 41、NVRAM 42以及Flash 43等。

作为Swap分区的NVRAM与DRAM一起连接在内存总线上，跟DRAM统一编址，由内存控制器(MMU)来实现对DRAM和NVRAM的访问控制。从操作系统的角度来看，NVRAM与DRAM没有任何分别，像通过虚拟地址访问DRAM上的数据一样操作系统可以访问NVRAM上的数据。NVRAM和DRAM之间的数据交换是通过内存接口，NVRAM上的数据可以通过内存拷贝复制到DRAM上，反之，亦可。

在操作系统中，本发明提供一种存储器交换分区损耗的均衡方法，包括以下步骤：

步骤1、NVRAM Swap分区上的每一个页槽设有一个记录页槽年龄的计数器(counter)，页槽每写一次，就将计数器加1。为了保证计数器的计数不丢失，我们将计数器存在NVRAM中。我们给NVRAM Swap分区增加一个头部(header)，如图3所示，这个header位于NVRAM的开始部分，大小根据NVRAM Swap分区的大小而定。每个页槽的年龄信息存储在这个header中，当系统启用NVRAM Swap分区时，header中页槽年龄信息被读入到DRAM中，当页槽年龄发生变化时，我们更新DRAM中的页槽年龄，并每隔固定时间将其同步到NVRAM中，这样可以保证NVRAM中存放页槽年龄的NVRAM单元不会过早的被写坏。

步骤2、建立一个用于保存NVRAM Swap分区中的页槽信息的小顶堆(Min-heap)。当系统启用NVRAM Swap分区的时候，根据从header中读出的每个页槽的年龄在DRAM中建立一个根据年龄排序的小顶堆，如图4所示，堆中任一子树的根节点所对应的页槽的年龄在该子树上是最小的。所以，小顶堆的根节点，即堆顶节点所对应的页槽的年龄是最小的。堆中每个节点包含两部分的内容：页槽的编号和指向该编号对应页槽的年龄计数器的指针。每当页槽年龄变化时，为了维持小顶堆的特性，需要对堆进行重新排序。

还建立一个用于保存所有空闲页槽的双向链表(Doubly linked list)。如图5所示，对于每个未使用的页槽，在这个页槽的前后两端存储两个信息：前一个空闲页槽(pre)和后一个空闲页槽(next)的编号，这样就形成了一个空闲页槽的双向链表。最前面的空闲页槽，即链表头页槽(head)只有next，同理，最后一个空闲页槽，即链表尾页槽(tail)只有pre。当系统启用NVRAM Swap时，根据页槽物理相对位置，建立空闲页槽链表，这时，所有的页槽都是空闲的，空闲链表head和tail的位置存储在DRAM中。当需要一个空闲页槽时，直接将head作为候选页槽，并将head的next作为新的head，这样，就实现了将head从空闲链表中删除。当回收一个空闲页槽时，将tail作为这个页槽的pre，并将这个页槽作为新的tail，这样，就实现了将不用的页槽加入到空闲链表的尾部。

步骤3、根据双向链表表头(head)的页槽和堆顶(top)页槽两个页槽的年龄之差，与阈值(TH)比较，确定要使用的页槽。

图6是head页槽和top页槽的选择流程图，该流程开始于步骤S01，然后：

在步骤S02，输入双向链表表头的head页槽和小顶堆堆顶的top页槽；

在步骤S03，将head页槽与top页槽的年龄之差与阈值TH比较，若年龄之差大于阈值TH，则执行步骤S05；若年龄之差不大于阈值TH，则执行步骤S04；

在步骤S04，选择head页槽，然后执行步骤S08；

在步骤S05，判定top页槽已使用，若已使用，则执行步骤S06；若未使用，则执行步骤S07；

在步骤S06，进行页槽交换，将top页槽的数据拷贝到head页槽中；然后执行步骤S07；

当DRAM的页面写到NVRAM Swap分区之后，这个DRAM页面对应的PTE会记录下该页面在NVRAM Swap分区的位置，以便将来需要时能够正确的将数据拷到DRAM。此时，进行页槽交换之后，PTE中的信息却没有得到更新。

为了解决这个问题，需要使用一个映射表(Mapping Table)，映射表将PTE中记录的页槽位置重新映射到一个新的位置。如图7所示，A页槽是一个位于小顶堆堆顶的top页槽，但已经被使用，存放着一个从DRAM中换出来的页面，这个页面对应着PTE X。B页槽是位于双向链表表头的head页槽，被选作为一个候选页槽来存放PTE Y所对应的DRAM页面。经过比较B页槽的年龄比A页槽的年纪大，且差超过了TH，所以进行页槽交换，将A页槽中的数据复制到B页槽中，则B页槽存储有PTE X对应的DRAM页面，同时更新映射表，并使用A页槽来存放PTE Y对应的DRAM页面。

在步骤S07，选择top页槽，然后执行步骤S08；

在步骤S08，程序结束。

上述阈值TH控制着损耗均衡的程度，TH越小，写操作将分部得更加均匀，但同时也需要更多的额外拷贝。页槽交换需要一次额外的数据拷贝，但通过设置交换阈值TH，可以有效的减少页槽交换的次数。本方法发明每次总是倾向于使用比较年轻的页面来存放DRAM页面，通过页槽交换，可以保证任意两个页槽之间的年龄差距不会超过TH，从而有效的将写均匀的分布在了NVRAM Swap分区的所有页槽中，达到了损耗均衡的目的。

本发明技术方案带来的有益效果

取不同的NVRAM Swap大小和不同阈值(Threshold)进行试验，试验中对NVRAMSwap分区进行一定量的写操作，试验结果如图8所示，图8中(a),(b),(c)和(d)分别对应阈值为16,64，128和256时，对不同NVRAM Swap大小所取得的损耗均衡的结果。在实验中，使用了三种不同的NVRAM Swap分区大小，分别是64MB，128MB和256MB。从图中可以看出，对NVRAM的写被均匀的分布在了整个NVRAM Swap分区的所有页槽中，页槽之间的年龄差距被阈值TH控制。当阈值(TH)较小时，例如图8(a)，所达到的损耗均衡结果较好，每个页槽被写的次数比较集中，但页槽交换的次数相对较多。当阈值(TH)较大时，例如图8(d)，所达到的损耗均衡结果相对较差，每个页槽被写的次数分布相对较广，但页槽交换的次数较少。

Claims (3)

1.一种存储器交换分区损耗的均衡方法，其特征是：包括有以下步骤：

NVRAM交换分区上的每一个页槽设有一个记录页槽年龄的计数器，页槽每写一次，就将计数器加1；

建立一个用于保存NVRAM交换分区中的页槽信息的小顶堆，小顶堆根据计数器上的页槽年龄，将最年轻的页槽置于堆顶；还建立一个用于保存所有空闲页槽的双向链表；

将双向链表表头页槽与堆顶页槽的年龄之差，与阈值比较，在双向链表表头页槽与堆顶页槽的年龄之差大于阈值的情况下，选择堆顶页槽；在双向链表表头页槽与堆顶页槽的年龄之差不大于阈值的情况下，选择双向链表表头的页槽。

2.根据权利要求1所述的一种存储器交换分区损耗的均衡方法,其特征是：所述双向链表是在空闲页槽内的前后两端存储两个信息：前一个空闲页槽和后一个空闲页槽的编号。

3.根据权利要求1所述的一种存储器交换分区损耗的均衡方法,其特征是：在双向链表表头页槽与堆顶页槽的年龄之差大于阈值的条件下，且堆顶页槽已使用，则将堆顶页槽的信息拷贝到双向链表表头页槽中，同时，用映射表将PTE中记录的页槽位置重新映射到一个新的位置。