基于嵌入式系统混合主存的页面管理方法
基于嵌入式系统混合主存的页面管理方法
【技术领域】
[0001] 本发明涉及一种页面管理的方法，尤其涉及一种基于嵌入式系统混合主存的页面 管理方法。
【背景技术】
[0002] 大数据时代，随着多核系统和新型应用程序的出现和普及，计算机系统模型已经 逐渐从计算驱动演化为数据驱动。因此，大容量的内存是保证整个计算机系统性能的关键。 然而，传统的基于DRAM的内存密度很难做到很大。研宄表明，未来DRAM工艺的密度不会小 于22nm。此外，DRAM的工作机制决定了其必须在一定的间隔内（2ms)对其进行刷新。这些 额外的刷新操作独立于数据的存储，但是其能量消耗在大多数应用中会占据整个DRAM能 量消耗的70%以上。造成的结果是，传统DRAM内存的能量消耗至少占整个计算机系统的 40%〇
[0003] 嵌入式系统是面向特定应用的，软硬件可剪裁的计算机系统。由于其本身固有的 特点，对存储器的面积和能量消耗有严格的要求。因此，传统DRAM的密度小和功耗大的 特点严重限制了大容量DRAM内存应用在嵌入式系统之中。而相变存储器（PhaseChange Memory,PCM)的出现为嵌入式系统中大容量内存提供了新的机遇。
[0004] PCM是一种以硫族化物（如Ge2Sb2Te5, Ge4SblTe5)作为存储介质的非易失性半 导体存储器，当系统掉电后，其存储单元内部的数据不会丢失。硫族化物是一种相变材料， 在不同的电压之下会呈现出结晶和非结晶状态。结晶状态具有较低的电阻值而在非结晶状 态具有较高的电阻值。利用该特性，可以分别存储计算机系统中的二进制1和〇。此外，为 了更大的增加PCM的密度以减小芯片面积。工业界利用相变材料高阻态和低阻态之间的其 它电阻状态来实现在一个存储单元内存储多个二进制位。该PCM工艺称之位Multi-Level Cell (MLC)，与之对应，一个SLC只能存储一位数据。由于MLC的特性复杂，而且写操作速度 比SLC慢很多，目前的研宄以SLC为主。与传统DRAM相比，PCM存储器作为内存具有以下 优点：
[0005] (1)高密度：不同于传统基于电容阵列的DRAM，PCM以相变材料作为存储介质，其 各个存储单元之间的距离可以做到非常小，研宄表明，PCM的密度可以在未来短时间内突破 16nm。早在2012年，三星公司就研制出20nm支撑的8GB相变存储器。而且，MLCPCM的存 储单元密度会更大。
[0006] (2)低能耗：由于PCM以电阻值差异存储数据，因此，不存在传统DRAM中的刷新操 作，极大地减少了存储器的能量消耗。此外，PCM内部没有机械传动装置，进一步减少能耗。
[0007] (3)非易失：PCM存储单元的内容在系统掉电后会保持不变。因此，如果将PCM作 为主存，在系统重新上电后会延续掉电之前系统状态而继续执行。有效的减小系统的启动 时间，保证了数据的安全性和一致性。
[0008] (4)抗干扰：传统DRAM内存需要采用电容作为存储单元，而电容都会存在耐压的 问题，如果电压超过额定电压，电容器就会损坏。而PCM不会存在这样的问题。
[0009] 鉴于PCM以上优点，将其作为嵌入式系统大容量主存是一个很好的选择。然而，目 前PCM存储器仍然存在不足，主要表现在以下几个方面：
[0010] (1)有限的写次数：当PCM存储单元写入一定量的数据之后，会变的不稳定，以至 于读出的数据和写入的数据不同。存储单元通常情况下，PCM存储单元的写次数限制大约 为 107-108。
[0011] (2)写延迟长：由于晶体材料状态改变需要维持较长的时间。因此，相对于传统 DRAM，PCM向存储单元中写入数据需要更长的时间。
[0012] (3)较高的动态能耗：PCM的写操作由于需要经过强电流加热和快速促灭使晶体 材料状态发生改变，使得写操作的功耗比读操作大大提高。在对PCM存储单元进行数据写 入时，会比传统DRAM消耗更多的能量。
[0013] 下表显示了PCM，DRAM与NANDFlash的各种参数对比：
[0015] 为了同时发挥PCM和DRAM两者优点的同时能有有效的避免各自缺点，学术界提出 了PCM和DRAM的混合主存架构（HybridMainMemoryArchitecture)。在该架构中，PCM和DRAM位于两个并列的线性地址空间中。操作系统会区分这两个空间并将大多数的写操 作位于DRAM完成而读操作在PCM中完成。该架构能够同时利用DRAM低的写延迟和动态功 耗的优点和PCM高密度和静态功耗的优点，同时又能有效避免两者缺点。
[0016]在该架构中，为了避免在PCM中产生过多的写操作，需要在传统操作系统页面管 理的基础上增加页面迀移策略。将位于PCM中经常被写的页面（write-hotpage)迀移到 DRAM中，而将DRAM中很少被写的页面迀移到PCM中以更加高效利用DRAM空间。然而，如何 预测未来页面的写特点是一件非常困难的事情。尽管今年来学术界对混合主存的页面管理 的研宄很多，但是普遍存在以下缺点：
[0017] (1)始终将读频繁的页面放置和迀移到PCM中：
[0018] 在写密集型的应用中，该策略是可行的；然而，在读密集型的应用中，DRAM存储空 间得不到有效的使用，而且由于页面缺失的问题导致的PCM写次数会大大增加。
[0019] (2)在页面管理策略运行之前需要用户确定很多参数的值：
[0020] 如PCM页面的写次数超过多少时迀移到DRAM;对于不同的应用程序，这些参数的 值往往很难确定。
[0021] (3)不能有效的预测写频繁的页：
[0022] 当策略检测到一个PCM页面频繁被写后，将其迀移到DRAM，但该页面此后不再被 写会造成错误的迀移；或者当策略检测到一个DARM页面很少被写后，将其迀移到PCM，但该 页面此后经常被写也会造成错误的迀移。
【发明内容】
[0023] 为了弥补现有技术存在的缺陷和不足，本发明提出了一种基于嵌入式系统混合主 存的页面管理方法，该方法针对嵌入式系统中的PCM/DRAM混合主存，能够极大地延长混合 主存的寿命，减小应用程序的执行延迟以及减小整个内存系统的能耗。
[0024] 为了达到以上目的，本发明的技术方案如下：
[0025] 一种基于嵌入式系统混合主存的页面管理方法，所述嵌入式系统混合主存为嵌入 式系统PCM/DRAM混合主存，嵌入式系统的CPU发送访问页面的请求，若CPU的请求数据或 者指令不在缓存中，则执行访问主存进行页面管理，包括以下步骤：
[0026] 步骤（1):构建存在于混合主存中页面的CLOCK链表和存储的数据为从CLOCK链 表中移出内存的页面的元数据的LRU链表；
[0027] 步骤（2):判断请求被访问的页面是否存储在嵌入式系统的混合主存中，若存储 在嵌入式系统的混合主存中，则访问CLOCK链表，并判断CLOCK链表中的页面的类型进行 页面标识位的更改操作或页面迀移操作；若没有存储在嵌入式系统的主存中，则进入步骤 (3)；
[0028] 步骤⑶：获取一个空闲页面作为被访问页面的存储空间，并访问LRU链表，再调 用页面插入算法将被访问页面插入到混合主存中。
[0029] 所述步骤（2)中的标识位包括：访问位、写位和建议位。
[0030] 所述步骤（2)中被访问页面命中的类型，包括最近被访问的页面和经常被访问的 页面，分别存储于CLOCK链表T1和CLOCK链表T2中。
[0031] 所述经常被访问的页面的判断过程为：
[0032] 如果从页面的访问位变为1开始，到变为0之前对该页面再次进行访问，则该页面 为经常被访问的页面。
[0033] 所述最近被访问的页面的判断过程为：
[0034] 如果命中的某一个页面的访问位为1，则该页面为最近被访问的页面。
[0035] 当被访问页面命中的类型是位于CLOCK链表T1的最近被访问的页面时，判断被访 问页面的访问位是否为1，若被访问页面的访问位是1，则将该页面迀移至链表T2的尾端， 页面访问结束；
[0036] 若被访问页面的访问位是0,则判断被访问页面的请求是否写操作，若是，则将被 访问页面的写位和访问位均设置为1，页面访问结束；否则，仅将被访问页面的访问位设置 为1，页面访问结束。
[0037] 当被访问页面命中的类型是位于CLOCK链表T2的经常被访问的页面时，判断被访 问页面的请求是否写操作，若被访问页面的请求不是写操作，则仅将被访问页面的访问位 设置为1，页面访问结束；
[0038] 若被访问页面的请求是写操作，则判断被访问页面的写位和访问位是否均设置为 1，若不是，则被访问页面的写位和访问位均设置为1，页面访问结束；若访问页面的写位和 访问位均已经为1，则判断被访问页面是否存储在PCM中，若被访问页面存储在PCM中，则将 被访问页面迀移到DARM中，否则将被访问页面的建议位设置为1，页面访问结束。
[0039] 所述步骤（3)中的LRU链表，包括链表B1和链表B2;链表B1用来存放从链表T1 中移出内存的页面；链表B2用来存放从链表T2中移出内存的页面。
[0040] 所述步骤（3)的过程包括：
[0041] 步骤（3. 1):当被访问页面命中链表B1，则分配给链表T1的目标容量大小加1，再 调用页面插入算法将被访问页面插入到混合主存中，并链接到T1中，访问结束；
[0042] 步骤（3. 2):当被访问页面命中链表B2,则分配给链表T1的目标容量大小减1，再 调用页面插入算法将被访问页面插入到混合主存中，并链接到T2中，访问结束；
[0043] 步骤（3. 3):当被访问页面在链表B1和链表B2中都不命中时，则链表T1的容量 大小不变，然后再调用页面插入算法将被访问页面插入到混合主存中，并链接到T1中，访 问结束。
[0044] 所述步骤⑶中的链表T1，链表T2,链表B1和链表B2大小满足如下条件：
[0045]T1 | + |T2| ^S (1)
[0046]T1 | + |B11 ^S (2)
[0047]T2| + |B2| ^ 2S(3)
[0048] 0 <|T11+1T2| +1B11+1B2 |<2S(4)
[0051] 其中，S的值为混合主存的总大小，以页为单位，每个页大小为4KB;|T1|、|T2|、 Bl|和|B2|分别表示链表T1，链表T2,链表B1和链表B2的容量大小。
[0052] 本发明的有益效果是：
[0053]1)降低了整个主存系统的能耗；
[0054] 2)延长了PCM存储器的使用寿命；
[0055] 3)减少了应用程序的执行时间；
[0056] 4)本发明的该方法能够有效的减小PCM/DRAM混合储存下对PCM的写次数；高效 的预测PCM中写频繁的页面并对其进行迀移；当内存满后，根据应用程序的内存访问模式， 有效预测未来较少使用的内存页面，并将其移除内存；
[0057] 5)同时，为确保策略的自适应性，在运行之前都不需要用户确定与应用程序有关 的任何参数，本发明的该方法运用在操作系统层面上。
【附图说明】
[0058] 图1为本发明的页面管理方法采用的混合主存架构；
[0059] 图2为本发明提出的页面管理方法数据结构；
[0060] 图3为页面管理策略总流程图；
[0061] 图4为页面插入算法流程图；
[0062] 图5为页面迁移算法流程图；
[0063] 图6为页面替换算法流程图；
[0064] 图7为本发明提出的页面管理方法与CLOCK、LRU-WPAM和CL0CK-DWF管理方法的 平均内存访问延迟；
[0065] 图8为本发明提出的页面管理方法与CLOCK、LRU-WPAM和CL0CK-DWF管理方法的 平均PCM写次数；
[0066] 图9为本发明提出的页面管理方法与CLOCK、LRU-WPAM和CL0CK-DWF管理方法的 平均页面迀移次数；
[0067] 图10为本发明提出的页面管理方法与CL0CK、LRU-WPAM和CL0CK-DWF管理方法的 平均内存能耗。
【具体实施方式】
[0068] 下面结合附图对本发明提出的基于嵌入式系统混合主存的页面管理方法作进一 步的详细描述：
[0069] 图1显示了本发明提出的基于嵌入式系统混合主存的页面管理方法所应用的混 合主存架构。在该架构中，DRAM和PCM同时作为主存的一部分，但是由于各自的物理属性 不同，所以分别设有不同的内存控制器-DRAMController以及PCMController。而在相对 上层的操作系统层面，DRAM和PCM处于同一个地址空间中，被操作系统按照统一的页面方 式进行管理。本发明即在该操作系统层面设计页面管理策略。当CPU进行访存时，首先需 要查找LICache，如果LICache不命中，贝1」查找L2Cache。在这里L2Cache作为最后一级的 缓存，即LLC(LastLevelCache)。当LLC也不命中的时候，将会发生主存的访问操作。同 样，当页面从LLC移出时，也会发生主存的访问操作。
[0070] 图2显示了本发明提出的基于嵌入式系统混合主存的页面管理方法所用的数据 结构。所用的数据结构主要包含四个链表。其中，T1用来存放在内存中最近访问的页面； T2用来存放内存中经常被访问的页面；B1用来存放最近从T1中移出内存的页面；B2用来 存放最近从T2中移出内存的页面。如果混合主存的总大小为S，其中混合主存的总大小以 page为单位，则自适应页面管理策略所能够管理的页面总数为2S页，其中，T1和T2总共可 以管理S个实际在主存的页，而B1和B2总共可以管理S各历史访问的页面。此外，为了策 略能够更好地工作，Tl，T2,Bl，B2满足如下不等式：
[0071]T1 | + |T2| ^S(1)
[0072]T1 | + |B11 ^S(2)
[0073]T2| + |B2| ^ 2S(3)
[0074] 0 ^ |T1 | + |T2| + |B1 | + |B2| ^ 2S(4)
[0077] 公式（1)表示：T1和T2链表的总长度不大于混合主存（PCM+DRAM)的总大小。
[0078] 公式⑵表示：T1和B1链表的总长度不大于混合主存（PCM+DRAM)的总大小。这 样做的目的保证了所有T1和B1中的页面都能够迀移到T2中。
[0079] 公式（3)表示：T2和B2链表的总长度不大于混合2倍的混合主存（PCM+DRAM)的 总大小。这样做的目的保证了所有T1和B1中的页面都能够迀移到T2中。此外还保证了 本发明提出的策略总共可以管理两倍的混合主存总大小。
[0080] 公式⑷表示：T1，T2，B1和B2链表的总长度不超过混合主存（PCM+DRAM)的总大 小的两倍。该公式的意思是，本发明提出的策略总共可以管理2倍的混合主存总大小。
[0081] 公式（5)表示：如果T1和T2的总大小没有达到最大，即混合主存没有发生页面的 替换，则B1和B2链表都为空。
[0082] 公式（6)表示：如果T1，T2，B1和B2链表的总长度大小大于混合主存总大小S，那 么可以推断T1和T2的总大小为S。
[0083] 其中，T1，T2，B1和B2链表的长度是以链表元素个数为单位；混合主存总大小S是 以页面个数为单位。[0084] 将操作系统管理的所有在主存中的页面分为两个循环链表，该循环链表为CLOCK 链表。一个链表中的元素为最近被访问的页，存储在链表T1中，即这些页面被访问的次数 很少，但是在该时间点之前较短的时间内被访问过。一个链表中的元素为经常被访问的页， 存储在链表T2,即这些页面虽然可能很久没有被CPU访问过，但是在之前经常被CPU访问。 为了利用历史信息来预测未来页面的访问模式，建立两个单项链表，该单链表为LRU链表， 分别为B1和B2。B1链表中的每个元素是从T1中移出内存的页面的元数据，B2链表中的 每个元素是从T2中移出内存的页面的元数据。其中，元数据指的是描述页面信息的数据， 包括页面标识符，页面指针以及页面有关的标志位；如果页面在内存中，则页面指针指向页 面在内存中的具体地址。
[0085] 对T1中的每个页，设置一个访问位（referencebit)和写位（dirtybit)。当一 个新的页面进入内存时，首先用T1链接该页面并且referencebit和dirtybit都清零。 当页面在T1中被访问时，referencebit为1 ;当页面在T1中被写访问时，dirtybit设置 为1。由此看出，referencebit代表最近的访问信息，而dirtybit代表最近的写信息。 同样，对T2中的每个页，设置referencebit和dirtybit。其意义与在T1中的意义相同。 当页面从T1迀移到T2后，referencebit和dirtybit都清零。除此之外，在T2中还设置 建议位（suggestbit)。当T2 中的一个DRAM页的referencebit和dirtybit都为 1 时， 表明该页可能为写频繁页。如果再次在该页面中发生写操作，则将该页面的suggestbit 设置为1。当suggestbit为1时，表明当该页面下次被加载到内存时，应该放到DARM中。 当页面从T2中被替换到B2中时，保留suggestbit位不变。Tl，T2,Bl，B2及其标志位的 可视化描述如附图2所示。
[0086] 本发明提出的方法中，关于页面在T1和T2之间的迀移过程为：如果T1中的一个 页面的referencebit为1，在其变为0之前，再次在该页面中发生一个内存读或者写操作， 表明该页为经常被访问页面，则将其迀移到T2的尾端。
[0087] 图3显示了自适应的页面替换策略总的流程图。它以一个内存访问请求作为 开端。如果这个请求的页面在混合主存中，说明页命中。命中的情况下，如果该页面的 referencebit已经为1，说明其最近经常被访问，应该将其迀移到T2中。否则，该页面的 referencebit为0,在该情况下，如果页面请求为读操作，则仅仅将其referencebit设置 为1，否则页面请求为写操作，应该将其referencebit和dirtybit同时设置为1。到此 为止，页面命中T1的页面访问过程结束。
[0088] 在页面命中T2的情况下，此时，如果该页面的访问类型为读操作，则简单的将其 referencebit设置为1。然而，如果操作为写操作，贝1」检查页面中目前的dirtybit和referencebit是否都为1，如果不是，将其都设置为1。如果是，说明该页为写频繁页，则检 查页面是否在DRAM中，如果是，则将它的suggestbit设置为1。如果在PCM中，则调用页 面迀移过程，将它迀移到DRAM中进行存储。到此为止，页面命中T2的页面访问过程结束。
[0089] 在页面不在内存的情况下，需要检查是否命中历史链表，即B1或者B2。如果命中 B1，说明之前不应该将此页面从T1中删除，S卩，分配给T1的目标大小太小了，应该对其进行 加1。同理，如果命中B2,说明之前不应该将此页面从T2中删除，S卩，分配给T2中的目标大 小太小了，应该对T2的目标大小进行加1 (对T1的目标大小减1)。如果页面都不命中，则 目标大小都不需要做任何改变。最后调用页面插入算法将新页面插入到混合主存中。到此 为止，针对页面不命中的页面访问过程到此结束。其中，新页面是指CPU正在访问的页面， 并且不在混合主存中的页数据。该页面数据可能位于外存中或者由CPU直接产生。
[0090] 图4显示了自适应的页面插入过程流程图。内存访问请求的页不在内存时，需要 将该新页面x插入到内存中。此时，可以有三种不同情况下的页面插入过程。
[0091] (1)第一种情况的页面插入过程，是页面X在B1中，表明该页面是一个不会经常被 访问的页面。此时，混合主存中获取一个空闲的页面（如果没有空闲页面，则调用页面替换 算法获得一个空闲页面），利用该空闲页面作为新页面x的存储空间，并链接到T1链表的尾 端。
[0092] (2)第二种情况下的页面插入过程，如果页面x即不在B1中，也不在B2中。则根 据局部性原理，如果对x的访问是写操作，则未来该页面可能经常被写。因此，需要从内存 中获取一个空闲的DRAM页面来存储x(如果内存中没有空闲DRAM页面，则调用页面替换过 程获取一个空闲的DRAM页面），利用该页面作为新页面x的存储空间，并链接到T1链表的 尾端。相反，如果对x的内存访问为读操作，则从混合主存中获取一个DRAM页面或者PCM 页面（如果混合主存已满，则调用页面替换算法获取一个空闲的DRAM页或者PCM页面），作 为x的存储空间，并链接到T1链表的尾端。
[0093] (3)第三种情况下，页面x在B2中。此时，需要检查页面x在B2中的suggestbit。 如果该位为1，则需要从混合主存中获取一个空闲的DRAM页面（如果没有空闲的DRAM页， 则调用页面替换算法获得一个空闲的DRAM页面），利用该页面作为新页面x的存储空间， 并链接到T2链表的尾端。相反，如果对x的内存访问为读操作，则从混合主存中获取一个 DRAM页面或者PCM页面（如果混合主存已满，则调用页面替换算法获取一个空闲的DRAM页 或者PCM页面），作为x的存储空间，并链接到T2链表的尾端。
[0094]对于以上三种情况下插入到内存中的页面，都将其页面的所有标志位设置为0。
[0095]图5显示了页面迀移过程的流程图。通过一系列的实验验证，对于写操作，写频率 高的页面未来一段时间内更趋向于被写。因此，本发明提出的自适应页面管理方法的页面 迀移过程仅仅发生在T2。这样有效的提高了页面迀移的效率，并有效的减少了错误迀移的 产生。所谓错误的迀移，是指，原来在PCM中的页面，发生了很多次的写操作后，将其迀移到 DRAM中，但是，在DRAM中却很少再次被写。同理，原来在DRAM中的页面，很少被写，将其迀 移到PCM中，但是，在PCM中却发生了多次的写操作。这些都是错误的迀移。理论上，错误 的迀移是无法避免的。当T2中需要有一个PCM页面p需要迀移到DRAM页面中时，利用Hdram 指针查找一个dirtybit为0的DRAM页面q将其作为与p之间进行相互页面迀移的页面。 在利用HdM进行页面查找的过程中。如果所遇到的DRAM或者PCM页面dirtybit为1，则 将其设置为〇。在页面的迀移过程中，要注意的是，两个页面P和q在T2链表中的相对位置 保持不变，仅仅是其存储介质发生转变。
[0096] 图6显示了页面替换过程的流程图。因此。本发明提出的页面管理方法中的页面 替换算法需要在不需要设置任何用户定义参数的情况下，灵活的基于"recency"（访问时 间）和"frequency"（访问频率）选择页面进行替换。T1和T2链表分别代表最近访问的 页面和最常访问的页面。当需要进行页面替换时，通过对比T1链表的实际大小是否大于为 其设置的目标大小，即TargetSize。如果大于TargetSize，则需要从T1中替换一个页面。 在页面替换过程中，如果指定需要替换DRAM页面，贝1」利用T1中的仏^指针选择reference bit和dirtybit同时为0 的冷页进行替换，在查找该类型页面的过程中，如果reference bit和dirtybit不同时为0,则将其都设置为0,并将指针指向下一个页面。而如果不指定 需要替换DRAM页，贝1」利用T1中的针选择referencebit为0的页进行替换，在查 找该类型页面的过程中，如果referencebit不为0,则将其设置为0,并将指针指向下一个 页面。
[0097] 当T1链表的实际大小不大于为其设置的大小TargetSize时，则需要从T2中替换 出一个页面到外存中。该过程和从T1中替换一个页面的过程类似，在此不做赘述。
[0098] 本发明解决的是混合主存下操作系统层面的页面管理问题，通过提出一种基于嵌 入式系统混合主存的页面管理方法来有效的减少PCM的写次数，PCM与DRAM之间的页面迀 移次数，在内存大小固定的情况下提高页面的命中率。
[0099] 通过修改Linux内核，实现本发明提出的页面管理策略并在 GEM5+NVMain+FlashSim综合仿真器中进行了验证。其中，GEM5能够运行Linux操作系统， NVMain能够精确的仿真DRAM和PCM的各项物理特性。而FlashSim能够仿真最前最先进的 Flash存储技术。
[0100] 本发明的基于嵌入式系统混合主存的页面管理方法AMR相对于其他其它页面管 理方法CL0CK、LRU-WPAM和CL0CK-DWF的实验结果，如图7-10所示。结果显示，相比于目前 存在的混合主存页面管理策略，本发明提出的自适应的页面管理策略能够极大地延长混合 主存的使用寿命，减小应用程序的执行延迟以及减小整个内存系统的能耗。
[0101] 上述虽然结合附图对本发明的【具体实施方式】进行了描述，但并非对本发明保护范 围的限制，所属领域技术人员应该明白，在本发明的技术方案的基础上，本领域技术人员不 需要付出创造性劳动即可做出的各种修改或变形仍在本发明的保护范围以内。
【主权项】
1. 一种基于嵌入式系统混合主存的页面管理方法，所述嵌入式系统混合主存为嵌入式 系统PCM/DRAM混合主存，嵌入式系统的CPU发送访问页面的请求，若CPU的请求数据或者 指令不在缓存中，则执行访问主存操作，页面管理方法开始执行，其特征在于，包括以下步 骤： 步骤（1):构建存在于混合主存中页面的CLOCK链表和存储的数据为从CLOCK链表中 移出内存的页面的元数据的LRU链表； 步骤（2):判断请求被访问的页面是否存储在嵌入式系统的混合主存中，若存储在嵌 入式系统的混合主存中，则访问CLOCK链表，并判断CLOCK链表中的页面的类型进行页面标 识位的更改操作或页面迀移操作；若没有存储在嵌入式系统的主存中，则进入步骤（3); 步骤（3):获取一个空闲页面作为被访问页面的存储空间，并访问LRU链表，再调用页 面插入算法将被访问页面插入到混合主存中。2. 如权利要求1所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 所述步骤（2)中被访问页面命中的类型，包括最近被访问的页面和经常被访问的页面，分 别存储于CLOCK链表Tl和CLOCK链表T2中。3. 如权利要求2所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 所述步骤（2)中的标识位包括：访问位、写位和建议位。4. 如权利要求3所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 所述经常被访问的页面的判断过程为： 如果从页面的访问位变为1开始，到变为0之前对该页面再次进行访问，则该页面为经 常被访问的页面。5. 如权利要求3所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 所述最近被访问的页面的判断过程为： 如果某一个页面的访问位为1，则该页面为最近被访问的页面。6. 如权利要求3所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 当被访问页面命中的类型是位于CLOCK链表Tl的最近被访问的页面时，判断被访问页面的 访问位是否为1，若被访问页面的访问位是1，则将该页面迀移至链表T2的尾端，页面访问 结束； 若被访问页面的访问位是0,则判断被访问页面的请求是否写操作，若是，则将被访问 页面的写位和访问位均设置为1且页面访问结束；否则，仅将被访问页面的访问位设置为 1，页面访问结束。7. 如权利要求3所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 当被访问页面命中的类型是位于CLOCK链表T2的经常被访问的页面时，判断被访问页面的 请求是否写操作，若被访问页面的请求不是写操作，则仅将被访问页面的访问位设置为1， 页面访问结束； 若被访问页面的请求是写操作，则判断被访问页面的写位和访问位是否均设置为1，若 不是，则被访问页面的写位和访问位均设置为1，页面访问结束；若访问页面的写位和访问 位均已经为1，则判断被访问页面是否存储在PCM中，若被访问页面存储在PCM中，则将被访 问页面迀移到DARM中，否则将被访问页面的建议位设置为1，页面访问结束。8. 如权利要求3所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 所述步骤（3)中的LRU链表，包括链表BI和链表B2 ;链表BI用来存放从链表Tl中移出内 存的页面；链表B2用来存放从链表T2中移出内存的页面。9. 如权利要求8所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 所述步骤（3)的过程包括： 步骤（3. 1):当被访问页面命中链表B1，则分配给链表Tl的目标容量大小加1，再调用 页面插入算法将被访问页面插入到混合主存中，并链接到Tl中，访问结束； 步骤（3. 2):当被访问页面命中链表B2,则分配给链表Tl的目标容量大小减1，再调用 页面插入算法将被访问页面插入到混合主存中，并链接到T2中，访问结束； 步骤（3. 3):当被访问页面在链表Bl和链表B2中都不命中时，则链表Tl的容量大小不 变，然后再调用页面插入算法将被访问页面插入到混合主存中，并链接到Tl中，访问结束。10. 如权利要求9所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 所述步骤（3)中的链表Tl，链表T2,链表Bl和链表B2大小满足如下条件： Tl|+|T2I ^ S (1) Tl|+|B1| ^ S (2) T2|+|B2| ^ 2S (3) 0 ^ |T1|+|T2|+|B1|+|B2| ^ 2S (4) |Γ1|+|Γ2 \<S<^>B\[jB2 = 0 (5) 1 Tl I +1Γ21 +1MI +1 521> 5 ?I Tl I +1Γ21= 5 (6) 其中，S的值为混合主存的总大小，以页为单位，每个页大小为4ΚΒ ; I Tl I、I Τ2 I、I BI I和 B2 I分别表示链表Tl，链表T2,链表Bl和链表B2的容量大小。
【专利摘要】本发明公开了一种基于嵌入式系统混合主存的页面管理方法，嵌入式系统混合主存为嵌入式系统PCM/DRAM混合主存，嵌入式系统的CPU发送访问页面请求，若该请求数据或者指令不在缓存中，则进行主存的访问，此时执行页面管理方法，包括构建存在于混合主存中页面的CLOCK链表和存储的数据为从CLOCK链表中移出内存的页面的元数据的LRU链表；判断请求被访问的页面是否存储在嵌入式系统的混合主存中，若存储在嵌入式系统的混合主存中，则访问CLOCK链表，并判断CLOCK链表中的页面的类型进行页面标识位的更改操作或页面迁移操作；若否，则进入下一步；获取一个空闲页面作为被访问页面的存储空间，并访问LRU链表，再调用页面插入算法将被访问页面插入到混合主存中。
【IPC分类】G06F12/02
【公开号】CN104899154
【申请号】CN201510315621
【发明人】蔡晓军, 孙志文, 贾智平, 鞠雷
【申请人】山东大学
【公开日】2015年9月9日
【申请日】2015年6月10日
【技术领域】
[0001] 本发明涉及一种页面管理的方法，尤其涉及一种基于嵌入式系统混合主存的页面 管理方法。
【背景技术】
[0002] 大数据时代，随着多核系统和新型应用程序的出现和普及，计算机系统模型已经 逐渐从计算驱动演化为数据驱动。因此，大容量的内存是保证整个计算机系统性能的关键。 然而，传统的基于DRAM的内存密度很难做到很大。研宄表明，未来DRAM工艺的密度不会小 于22nm。此外，DRAM的工作机制决定了其必须在一定的间隔内（2ms)对其进行刷新。这些 额外的刷新操作独立于数据的存储，但是其能量消耗在大多数应用中会占据整个DRAM能 量消耗的70%以上。造成的结果是，传统DRAM内存的能量消耗至少占整个计算机系统的 40%〇
[0003] 嵌入式系统是面向特定应用的，软硬件可剪裁的计算机系统。由于其本身固有的 特点，对存储器的面积和能量消耗有严格的要求。因此，传统DRAM的密度小和功耗大的 特点严重限制了大容量DRAM内存应用在嵌入式系统之中。而相变存储器（PhaseChange Memory,PCM)的出现为嵌入式系统中大容量内存提供了新的机遇。
[0004] PCM是一种以硫族化物（如Ge2Sb2Te5, Ge4SblTe5)作为存储介质的非易失性半 导体存储器，当系统掉电后，其存储单元内部的数据不会丢失。硫族化物是一种相变材料， 在不同的电压之下会呈现出结晶和非结晶状态。结晶状态具有较低的电阻值而在非结晶状 态具有较高的电阻值。利用该特性，可以分别存储计算机系统中的二进制1和〇。此外，为 了更大的增加PCM的密度以减小芯片面积。工业界利用相变材料高阻态和低阻态之间的其 它电阻状态来实现在一个存储单元内存储多个二进制位。该PCM工艺称之位Multi-Level Cell (MLC)，与之对应，一个SLC只能存储一位数据。由于MLC的特性复杂，而且写操作速度 比SLC慢很多，目前的研宄以SLC为主。与传统DRAM相比，PCM存储器作为内存具有以下 优点：
[0005] (1)高密度：不同于传统基于电容阵列的DRAM，PCM以相变材料作为存储介质，其 各个存储单元之间的距离可以做到非常小，研宄表明，PCM的密度可以在未来短时间内突破 16nm。早在2012年，三星公司就研制出20nm支撑的8GB相变存储器。而且，MLCPCM的存 储单元密度会更大。
[0006] (2)低能耗：由于PCM以电阻值差异存储数据，因此，不存在传统DRAM中的刷新操 作，极大地减少了存储器的能量消耗。此外，PCM内部没有机械传动装置，进一步减少能耗。
[0007] (3)非易失：PCM存储单元的内容在系统掉电后会保持不变。因此，如果将PCM作 为主存，在系统重新上电后会延续掉电之前系统状态而继续执行。有效的减小系统的启动 时间，保证了数据的安全性和一致性。
[0008] (4)抗干扰：传统DRAM内存需要采用电容作为存储单元，而电容都会存在耐压的 问题，如果电压超过额定电压，电容器就会损坏。而PCM不会存在这样的问题。
[0009] 鉴于PCM以上优点，将其作为嵌入式系统大容量主存是一个很好的选择。然而，目 前PCM存储器仍然存在不足，主要表现在以下几个方面：
[0010] (1)有限的写次数：当PCM存储单元写入一定量的数据之后，会变的不稳定，以至 于读出的数据和写入的数据不同。存储单元通常情况下，PCM存储单元的写次数限制大约 为 107-108。
[0011] (2)写延迟长：由于晶体材料状态改变需要维持较长的时间。因此，相对于传统 DRAM，PCM向存储单元中写入数据需要更长的时间。
[0012] (3)较高的动态能耗：PCM的写操作由于需要经过强电流加热和快速促灭使晶体 材料状态发生改变，使得写操作的功耗比读操作大大提高。在对PCM存储单元进行数据写 入时，会比传统DRAM消耗更多的能量。
[0013] 下表显示了PCM，DRAM与NANDFlash的各种参数对比：
[0015] 为了同时发挥PCM和DRAM两者优点的同时能有有效的避免各自缺点，学术界提出 了PCM和DRAM的混合主存架构（HybridMainMemoryArchitecture)。在该架构中，PCM和DRAM位于两个并列的线性地址空间中。操作系统会区分这两个空间并将大多数的写操 作位于DRAM完成而读操作在PCM中完成。该架构能够同时利用DRAM低的写延迟和动态功 耗的优点和PCM高密度和静态功耗的优点，同时又能有效避免两者缺点。
[0016]在该架构中，为了避免在PCM中产生过多的写操作，需要在传统操作系统页面管 理的基础上增加页面迀移策略。将位于PCM中经常被写的页面（write-hotpage)迀移到 DRAM中，而将DRAM中很少被写的页面迀移到PCM中以更加高效利用DRAM空间。然而，如何 预测未来页面的写特点是一件非常困难的事情。尽管今年来学术界对混合主存的页面管理 的研宄很多，但是普遍存在以下缺点：
[0017] (1)始终将读频繁的页面放置和迀移到PCM中：
[0018] 在写密集型的应用中，该策略是可行的；然而，在读密集型的应用中，DRAM存储空 间得不到有效的使用，而且由于页面缺失的问题导致的PCM写次数会大大增加。
[0019] (2)在页面管理策略运行之前需要用户确定很多参数的值：
[0020] 如PCM页面的写次数超过多少时迀移到DRAM;对于不同的应用程序，这些参数的 值往往很难确定。
[0021] (3)不能有效的预测写频繁的页：
[0022] 当策略检测到一个PCM页面频繁被写后，将其迀移到DRAM，但该页面此后不再被 写会造成错误的迀移；或者当策略检测到一个DARM页面很少被写后，将其迀移到PCM，但该 页面此后经常被写也会造成错误的迀移。
【发明内容】
[0023] 为了弥补现有技术存在的缺陷和不足，本发明提出了一种基于嵌入式系统混合主 存的页面管理方法，该方法针对嵌入式系统中的PCM/DRAM混合主存，能够极大地延长混合 主存的寿命，减小应用程序的执行延迟以及减小整个内存系统的能耗。
[0024] 为了达到以上目的，本发明的技术方案如下：
[0025] 一种基于嵌入式系统混合主存的页面管理方法，所述嵌入式系统混合主存为嵌入 式系统PCM/DRAM混合主存，嵌入式系统的CPU发送访问页面的请求，若CPU的请求数据或 者指令不在缓存中，则执行访问主存进行页面管理，包括以下步骤：
[0026] 步骤（1):构建存在于混合主存中页面的CLOCK链表和存储的数据为从CLOCK链 表中移出内存的页面的元数据的LRU链表；
[0027] 步骤（2):判断请求被访问的页面是否存储在嵌入式系统的混合主存中，若存储 在嵌入式系统的混合主存中，则访问CLOCK链表，并判断CLOCK链表中的页面的类型进行 页面标识位的更改操作或页面迀移操作；若没有存储在嵌入式系统的主存中，则进入步骤 (3)；
[0028] 步骤⑶：获取一个空闲页面作为被访问页面的存储空间，并访问LRU链表，再调 用页面插入算法将被访问页面插入到混合主存中。
[0029] 所述步骤（2)中的标识位包括：访问位、写位和建议位。
[0030] 所述步骤（2)中被访问页面命中的类型，包括最近被访问的页面和经常被访问的 页面，分别存储于CLOCK链表T1和CLOCK链表T2中。
[0031] 所述经常被访问的页面的判断过程为：
[0032] 如果从页面的访问位变为1开始，到变为0之前对该页面再次进行访问，则该页面 为经常被访问的页面。
[0033] 所述最近被访问的页面的判断过程为：
[0034] 如果命中的某一个页面的访问位为1，则该页面为最近被访问的页面。
[0035] 当被访问页面命中的类型是位于CLOCK链表T1的最近被访问的页面时，判断被访 问页面的访问位是否为1，若被访问页面的访问位是1，则将该页面迀移至链表T2的尾端， 页面访问结束；
[0036] 若被访问页面的访问位是0,则判断被访问页面的请求是否写操作，若是，则将被 访问页面的写位和访问位均设置为1，页面访问结束；否则，仅将被访问页面的访问位设置 为1，页面访问结束。
[0037] 当被访问页面命中的类型是位于CLOCK链表T2的经常被访问的页面时，判断被访 问页面的请求是否写操作，若被访问页面的请求不是写操作，则仅将被访问页面的访问位 设置为1，页面访问结束；
[0038] 若被访问页面的请求是写操作，则判断被访问页面的写位和访问位是否均设置为 1，若不是，则被访问页面的写位和访问位均设置为1，页面访问结束；若访问页面的写位和 访问位均已经为1，则判断被访问页面是否存储在PCM中，若被访问页面存储在PCM中，则将 被访问页面迀移到DARM中，否则将被访问页面的建议位设置为1，页面访问结束。
[0039] 所述步骤（3)中的LRU链表，包括链表B1和链表B2;链表B1用来存放从链表T1 中移出内存的页面；链表B2用来存放从链表T2中移出内存的页面。
[0040] 所述步骤（3)的过程包括：
[0041] 步骤（3. 1):当被访问页面命中链表B1，则分配给链表T1的目标容量大小加1，再 调用页面插入算法将被访问页面插入到混合主存中，并链接到T1中，访问结束；
[0042] 步骤（3. 2):当被访问页面命中链表B2,则分配给链表T1的目标容量大小减1，再 调用页面插入算法将被访问页面插入到混合主存中，并链接到T2中，访问结束；
[0043] 步骤（3. 3):当被访问页面在链表B1和链表B2中都不命中时，则链表T1的容量 大小不变，然后再调用页面插入算法将被访问页面插入到混合主存中，并链接到T1中，访 问结束。
[0044] 所述步骤⑶中的链表T1，链表T2,链表B1和链表B2大小满足如下条件：
[0045]T1 | + |T2| ^S (1)
[0046]T1 | + |B11 ^S (2)
[0047]T2| + |B2| ^ 2S(3)
[0048] 0 <|T11+1T2| +1B11+1B2 |<2S(4)
[0051] 其中，S的值为混合主存的总大小，以页为单位，每个页大小为4KB;|T1|、|T2|、 Bl|和|B2|分别表示链表T1，链表T2,链表B1和链表B2的容量大小。
[0052] 本发明的有益效果是：
[0053]1)降低了整个主存系统的能耗；
[0054] 2)延长了PCM存储器的使用寿命；
[0055] 3)减少了应用程序的执行时间；
[0056] 4)本发明的该方法能够有效的减小PCM/DRAM混合储存下对PCM的写次数；高效 的预测PCM中写频繁的页面并对其进行迀移；当内存满后，根据应用程序的内存访问模式， 有效预测未来较少使用的内存页面，并将其移除内存；
[0057] 5)同时，为确保策略的自适应性，在运行之前都不需要用户确定与应用程序有关 的任何参数，本发明的该方法运用在操作系统层面上。
【附图说明】
[0058] 图1为本发明的页面管理方法采用的混合主存架构；
[0059] 图2为本发明提出的页面管理方法数据结构；
[0060] 图3为页面管理策略总流程图；
[0061] 图4为页面插入算法流程图；
[0062] 图5为页面迁移算法流程图；
[0063] 图6为页面替换算法流程图；
[0064] 图7为本发明提出的页面管理方法与CLOCK、LRU-WPAM和CL0CK-DWF管理方法的 平均内存访问延迟；
[0065] 图8为本发明提出的页面管理方法与CLOCK、LRU-WPAM和CL0CK-DWF管理方法的 平均PCM写次数；
[0066] 图9为本发明提出的页面管理方法与CLOCK、LRU-WPAM和CL0CK-DWF管理方法的 平均页面迀移次数；
[0067] 图10为本发明提出的页面管理方法与CL0CK、LRU-WPAM和CL0CK-DWF管理方法的 平均内存能耗。
【具体实施方式】
[0068] 下面结合附图对本发明提出的基于嵌入式系统混合主存的页面管理方法作进一 步的详细描述：
[0069] 图1显示了本发明提出的基于嵌入式系统混合主存的页面管理方法所应用的混 合主存架构。在该架构中，DRAM和PCM同时作为主存的一部分，但是由于各自的物理属性 不同，所以分别设有不同的内存控制器-DRAMController以及PCMController。而在相对 上层的操作系统层面，DRAM和PCM处于同一个地址空间中，被操作系统按照统一的页面方 式进行管理。本发明即在该操作系统层面设计页面管理策略。当CPU进行访存时，首先需 要查找LICache，如果LICache不命中，贝1」查找L2Cache。在这里L2Cache作为最后一级的 缓存，即LLC(LastLevelCache)。当LLC也不命中的时候，将会发生主存的访问操作。同 样，当页面从LLC移出时，也会发生主存的访问操作。
[0070] 图2显示了本发明提出的基于嵌入式系统混合主存的页面管理方法所用的数据 结构。所用的数据结构主要包含四个链表。其中，T1用来存放在内存中最近访问的页面； T2用来存放内存中经常被访问的页面；B1用来存放最近从T1中移出内存的页面；B2用来 存放最近从T2中移出内存的页面。如果混合主存的总大小为S，其中混合主存的总大小以 page为单位，则自适应页面管理策略所能够管理的页面总数为2S页，其中，T1和T2总共可 以管理S个实际在主存的页，而B1和B2总共可以管理S各历史访问的页面。此外，为了策 略能够更好地工作，Tl，T2,Bl，B2满足如下不等式：
[0071]T1 | + |T2| ^S(1)
[0072]T1 | + |B11 ^S(2)
[0073]T2| + |B2| ^ 2S(3)
[0074] 0 ^ |T1 | + |T2| + |B1 | + |B2| ^ 2S(4)
[0077] 公式（1)表示：T1和T2链表的总长度不大于混合主存（PCM+DRAM)的总大小。
[0078] 公式⑵表示：T1和B1链表的总长度不大于混合主存（PCM+DRAM)的总大小。这 样做的目的保证了所有T1和B1中的页面都能够迀移到T2中。
[0079] 公式（3)表示：T2和B2链表的总长度不大于混合2倍的混合主存（PCM+DRAM)的 总大小。这样做的目的保证了所有T1和B1中的页面都能够迀移到T2中。此外还保证了 本发明提出的策略总共可以管理两倍的混合主存总大小。
[0080] 公式⑷表示：T1，T2，B1和B2链表的总长度不超过混合主存（PCM+DRAM)的总大 小的两倍。该公式的意思是，本发明提出的策略总共可以管理2倍的混合主存总大小。
[0081] 公式（5)表示：如果T1和T2的总大小没有达到最大，即混合主存没有发生页面的 替换，则B1和B2链表都为空。
[0082] 公式（6)表示：如果T1，T2，B1和B2链表的总长度大小大于混合主存总大小S，那 么可以推断T1和T2的总大小为S。
[0083] 其中，T1，T2，B1和B2链表的长度是以链表元素个数为单位；混合主存总大小S是 以页面个数为单位。[0084] 将操作系统管理的所有在主存中的页面分为两个循环链表，该循环链表为CLOCK 链表。一个链表中的元素为最近被访问的页，存储在链表T1中，即这些页面被访问的次数 很少，但是在该时间点之前较短的时间内被访问过。一个链表中的元素为经常被访问的页， 存储在链表T2,即这些页面虽然可能很久没有被CPU访问过，但是在之前经常被CPU访问。 为了利用历史信息来预测未来页面的访问模式，建立两个单项链表，该单链表为LRU链表， 分别为B1和B2。B1链表中的每个元素是从T1中移出内存的页面的元数据，B2链表中的 每个元素是从T2中移出内存的页面的元数据。其中，元数据指的是描述页面信息的数据， 包括页面标识符，页面指针以及页面有关的标志位；如果页面在内存中，则页面指针指向页 面在内存中的具体地址。
[0085] 对T1中的每个页，设置一个访问位（referencebit)和写位（dirtybit)。当一 个新的页面进入内存时，首先用T1链接该页面并且referencebit和dirtybit都清零。 当页面在T1中被访问时，referencebit为1 ;当页面在T1中被写访问时，dirtybit设置 为1。由此看出，referencebit代表最近的访问信息，而dirtybit代表最近的写信息。 同样，对T2中的每个页，设置referencebit和dirtybit。其意义与在T1中的意义相同。 当页面从T1迀移到T2后，referencebit和dirtybit都清零。除此之外，在T2中还设置 建议位（suggestbit)。当T2 中的一个DRAM页的referencebit和dirtybit都为 1 时， 表明该页可能为写频繁页。如果再次在该页面中发生写操作，则将该页面的suggestbit 设置为1。当suggestbit为1时，表明当该页面下次被加载到内存时，应该放到DARM中。 当页面从T2中被替换到B2中时，保留suggestbit位不变。Tl，T2,Bl，B2及其标志位的 可视化描述如附图2所示。
[0086] 本发明提出的方法中，关于页面在T1和T2之间的迀移过程为：如果T1中的一个 页面的referencebit为1，在其变为0之前，再次在该页面中发生一个内存读或者写操作， 表明该页为经常被访问页面，则将其迀移到T2的尾端。
[0087] 图3显示了自适应的页面替换策略总的流程图。它以一个内存访问请求作为 开端。如果这个请求的页面在混合主存中，说明页命中。命中的情况下，如果该页面的 referencebit已经为1，说明其最近经常被访问，应该将其迀移到T2中。否则，该页面的 referencebit为0,在该情况下，如果页面请求为读操作，则仅仅将其referencebit设置 为1，否则页面请求为写操作，应该将其referencebit和dirtybit同时设置为1。到此 为止，页面命中T1的页面访问过程结束。
[0088] 在页面命中T2的情况下，此时，如果该页面的访问类型为读操作，则简单的将其 referencebit设置为1。然而，如果操作为写操作，贝1」检查页面中目前的dirtybit和referencebit是否都为1，如果不是，将其都设置为1。如果是，说明该页为写频繁页，则检 查页面是否在DRAM中，如果是，则将它的suggestbit设置为1。如果在PCM中，则调用页 面迀移过程，将它迀移到DRAM中进行存储。到此为止，页面命中T2的页面访问过程结束。
[0089] 在页面不在内存的情况下，需要检查是否命中历史链表，即B1或者B2。如果命中 B1，说明之前不应该将此页面从T1中删除，S卩，分配给T1的目标大小太小了，应该对其进行 加1。同理，如果命中B2,说明之前不应该将此页面从T2中删除，S卩，分配给T2中的目标大 小太小了，应该对T2的目标大小进行加1 (对T1的目标大小减1)。如果页面都不命中，则 目标大小都不需要做任何改变。最后调用页面插入算法将新页面插入到混合主存中。到此 为止，针对页面不命中的页面访问过程到此结束。其中，新页面是指CPU正在访问的页面， 并且不在混合主存中的页数据。该页面数据可能位于外存中或者由CPU直接产生。
[0090] 图4显示了自适应的页面插入过程流程图。内存访问请求的页不在内存时，需要 将该新页面x插入到内存中。此时，可以有三种不同情况下的页面插入过程。
[0091] (1)第一种情况的页面插入过程，是页面X在B1中，表明该页面是一个不会经常被 访问的页面。此时，混合主存中获取一个空闲的页面（如果没有空闲页面，则调用页面替换 算法获得一个空闲页面），利用该空闲页面作为新页面x的存储空间，并链接到T1链表的尾 端。
[0092] (2)第二种情况下的页面插入过程，如果页面x即不在B1中，也不在B2中。则根 据局部性原理，如果对x的访问是写操作，则未来该页面可能经常被写。因此，需要从内存 中获取一个空闲的DRAM页面来存储x(如果内存中没有空闲DRAM页面，则调用页面替换过 程获取一个空闲的DRAM页面），利用该页面作为新页面x的存储空间，并链接到T1链表的 尾端。相反，如果对x的内存访问为读操作，则从混合主存中获取一个DRAM页面或者PCM 页面（如果混合主存已满，则调用页面替换算法获取一个空闲的DRAM页或者PCM页面），作 为x的存储空间，并链接到T1链表的尾端。
[0093] (3)第三种情况下，页面x在B2中。此时，需要检查页面x在B2中的suggestbit。 如果该位为1，则需要从混合主存中获取一个空闲的DRAM页面（如果没有空闲的DRAM页， 则调用页面替换算法获得一个空闲的DRAM页面），利用该页面作为新页面x的存储空间， 并链接到T2链表的尾端。相反，如果对x的内存访问为读操作，则从混合主存中获取一个 DRAM页面或者PCM页面（如果混合主存已满，则调用页面替换算法获取一个空闲的DRAM页 或者PCM页面），作为x的存储空间，并链接到T2链表的尾端。
[0094]对于以上三种情况下插入到内存中的页面，都将其页面的所有标志位设置为0。
[0095]图5显示了页面迀移过程的流程图。通过一系列的实验验证，对于写操作，写频率 高的页面未来一段时间内更趋向于被写。因此，本发明提出的自适应页面管理方法的页面 迀移过程仅仅发生在T2。这样有效的提高了页面迀移的效率，并有效的减少了错误迀移的 产生。所谓错误的迀移，是指，原来在PCM中的页面，发生了很多次的写操作后，将其迀移到 DRAM中，但是，在DRAM中却很少再次被写。同理，原来在DRAM中的页面，很少被写，将其迀 移到PCM中，但是，在PCM中却发生了多次的写操作。这些都是错误的迀移。理论上，错误 的迀移是无法避免的。当T2中需要有一个PCM页面p需要迀移到DRAM页面中时，利用Hdram 指针查找一个dirtybit为0的DRAM页面q将其作为与p之间进行相互页面迀移的页面。 在利用HdM进行页面查找的过程中。如果所遇到的DRAM或者PCM页面dirtybit为1，则 将其设置为〇。在页面的迀移过程中，要注意的是，两个页面P和q在T2链表中的相对位置 保持不变，仅仅是其存储介质发生转变。
[0096] 图6显示了页面替换过程的流程图。因此。本发明提出的页面管理方法中的页面 替换算法需要在不需要设置任何用户定义参数的情况下，灵活的基于"recency"（访问时 间）和"frequency"（访问频率）选择页面进行替换。T1和T2链表分别代表最近访问的 页面和最常访问的页面。当需要进行页面替换时，通过对比T1链表的实际大小是否大于为 其设置的目标大小，即TargetSize。如果大于TargetSize，则需要从T1中替换一个页面。 在页面替换过程中，如果指定需要替换DRAM页面，贝1」利用T1中的仏^指针选择reference bit和dirtybit同时为0 的冷页进行替换，在查找该类型页面的过程中，如果reference bit和dirtybit不同时为0,则将其都设置为0,并将指针指向下一个页面。而如果不指定 需要替换DRAM页，贝1」利用T1中的针选择referencebit为0的页进行替换，在查 找该类型页面的过程中，如果referencebit不为0,则将其设置为0,并将指针指向下一个 页面。
[0097] 当T1链表的实际大小不大于为其设置的大小TargetSize时，则需要从T2中替换 出一个页面到外存中。该过程和从T1中替换一个页面的过程类似，在此不做赘述。
[0098] 本发明解决的是混合主存下操作系统层面的页面管理问题，通过提出一种基于嵌 入式系统混合主存的页面管理方法来有效的减少PCM的写次数，PCM与DRAM之间的页面迀 移次数，在内存大小固定的情况下提高页面的命中率。
[0099] 通过修改Linux内核，实现本发明提出的页面管理策略并在 GEM5+NVMain+FlashSim综合仿真器中进行了验证。其中，GEM5能够运行Linux操作系统， NVMain能够精确的仿真DRAM和PCM的各项物理特性。而FlashSim能够仿真最前最先进的 Flash存储技术。
[0100] 本发明的基于嵌入式系统混合主存的页面管理方法AMR相对于其他其它页面管 理方法CL0CK、LRU-WPAM和CL0CK-DWF的实验结果，如图7-10所示。结果显示，相比于目前 存在的混合主存页面管理策略，本发明提出的自适应的页面管理策略能够极大地延长混合 主存的使用寿命，减小应用程序的执行延迟以及减小整个内存系统的能耗。
[0101] 上述虽然结合附图对本发明的【具体实施方式】进行了描述，但并非对本发明保护范 围的限制，所属领域技术人员应该明白，在本发明的技术方案的基础上，本领域技术人员不 需要付出创造性劳动即可做出的各种修改或变形仍在本发明的保护范围以内。
【主权项】
1. 一种基于嵌入式系统混合主存的页面管理方法，所述嵌入式系统混合主存为嵌入式 系统PCM/DRAM混合主存，嵌入式系统的CPU发送访问页面的请求，若CPU的请求数据或者 指令不在缓存中，则执行访问主存操作，页面管理方法开始执行，其特征在于，包括以下步 骤： 步骤（1):构建存在于混合主存中页面的CLOCK链表和存储的数据为从CLOCK链表中 移出内存的页面的元数据的LRU链表； 步骤（2):判断请求被访问的页面是否存储在嵌入式系统的混合主存中，若存储在嵌 入式系统的混合主存中，则访问CLOCK链表，并判断CLOCK链表中的页面的类型进行页面标 识位的更改操作或页面迀移操作；若没有存储在嵌入式系统的主存中，则进入步骤（3); 步骤（3):获取一个空闲页面作为被访问页面的存储空间，并访问LRU链表，再调用页 面插入算法将被访问页面插入到混合主存中。2. 如权利要求1所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 所述步骤（2)中被访问页面命中的类型，包括最近被访问的页面和经常被访问的页面，分 别存储于CLOCK链表Tl和CLOCK链表T2中。3. 如权利要求2所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 所述步骤（2)中的标识位包括：访问位、写位和建议位。4. 如权利要求3所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 所述经常被访问的页面的判断过程为： 如果从页面的访问位变为1开始，到变为0之前对该页面再次进行访问，则该页面为经 常被访问的页面。5. 如权利要求3所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 所述最近被访问的页面的判断过程为： 如果某一个页面的访问位为1，则该页面为最近被访问的页面。6. 如权利要求3所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 当被访问页面命中的类型是位于CLOCK链表Tl的最近被访问的页面时，判断被访问页面的 访问位是否为1，若被访问页面的访问位是1，则将该页面迀移至链表T2的尾端，页面访问 结束； 若被访问页面的访问位是0,则判断被访问页面的请求是否写操作，若是，则将被访问 页面的写位和访问位均设置为1且页面访问结束；否则，仅将被访问页面的访问位设置为 1，页面访问结束。7. 如权利要求3所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 当被访问页面命中的类型是位于CLOCK链表T2的经常被访问的页面时，判断被访问页面的 请求是否写操作，若被访问页面的请求不是写操作，则仅将被访问页面的访问位设置为1， 页面访问结束； 若被访问页面的请求是写操作，则判断被访问页面的写位和访问位是否均设置为1，若 不是，则被访问页面的写位和访问位均设置为1，页面访问结束；若访问页面的写位和访问 位均已经为1，则判断被访问页面是否存储在PCM中，若被访问页面存储在PCM中，则将被访 问页面迀移到DARM中，否则将被访问页面的建议位设置为1，页面访问结束。8. 如权利要求3所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 所述步骤（3)中的LRU链表，包括链表BI和链表B2 ;链表BI用来存放从链表Tl中移出内 存的页面；链表B2用来存放从链表T2中移出内存的页面。9. 如权利要求8所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 所述步骤（3)的过程包括： 步骤（3. 1):当被访问页面命中链表B1，则分配给链表Tl的目标容量大小加1，再调用 页面插入算法将被访问页面插入到混合主存中，并链接到Tl中，访问结束； 步骤（3. 2):当被访问页面命中链表B2,则分配给链表Tl的目标容量大小减1，再调用 页面插入算法将被访问页面插入到混合主存中，并链接到T2中，访问结束； 步骤（3. 3):当被访问页面在链表Bl和链表B2中都不命中时，则链表Tl的容量大小不 变，然后再调用页面插入算法将被访问页面插入到混合主存中，并链接到Tl中，访问结束。10. 如权利要求9所述的一种基于嵌入式系统混合主存的页面管理方法，其特征在于， 所述步骤（3)中的链表Tl，链表T2,链表Bl和链表B2大小满足如下条件： Tl|+|T2I ^ S (1) Tl|+|B1| ^ S (2) T2|+|B2| ^ 2S (3) 0 ^ |T1|+|T2|+|B1|+|B2| ^ 2S (4) |Γ1|+|Γ2 \<S<^>B\[jB2 = 0 (5) 1 Tl I +1Γ21 +1MI +1 521> 5 ?I Tl I +1Γ21= 5 (6) 其中，S的值为混合主存的总大小，以页为单位，每个页大小为4ΚΒ ; I Tl I、I Τ2 I、I BI I和 B2 I分别表示链表Tl，链表T2,链表Bl和链表B2的容量大小。
【专利摘要】本发明公开了一种基于嵌入式系统混合主存的页面管理方法，嵌入式系统混合主存为嵌入式系统PCM/DRAM混合主存，嵌入式系统的CPU发送访问页面请求，若该请求数据或者指令不在缓存中，则进行主存的访问，此时执行页面管理方法，包括构建存在于混合主存中页面的CLOCK链表和存储的数据为从CLOCK链表中移出内存的页面的元数据的LRU链表；判断请求被访问的页面是否存储在嵌入式系统的混合主存中，若存储在嵌入式系统的混合主存中，则访问CLOCK链表，并判断CLOCK链表中的页面的类型进行页面标识位的更改操作或页面迁移操作；若否，则进入下一步；获取一个空闲页面作为被访问页面的存储空间，并访问LRU链表，再调用页面插入算法将被访问页面插入到混合主存中。
【IPC分类】G06F12/02
【公开号】CN104899154
【申请号】CN201510315621
【发明人】蔡晓军, 孙志文, 贾智平, 鞠雷
【申请人】山东大学
【公开日】2015年9月9日
【申请日】2015年6月10日
最新回复(0)