FIFO页面置换算法的实现以及异常问题的讨论

在操作系统虚拟页式存储管理中,当系统总没有空闲页时,则要进行页面置换。针对FIFO页面置换算法以及它可能存在的异常问题进行了讨论,最后模拟实现FIFO页面置换算法。     

对LRU页面置换算法的理论改进

在对内存进行虚拟管理时，页面置换算法的好坏直接影响着系统的性能．现有的常用算法有四五种，文章对其中比较合理的算法——最近最少使用算法(LRU)进行理论上的改进。     

页面置换算法的Z规格说明

虚拟存储系统中,如果使用段页式存储管理或者页式存储管理,当发生缺页,而主存中已没有空闲页架时,则需要选一页淘汰,进行页面置换.本文首先简要介绍先进先出算法(FIFO)和最近最少使用算法(LRU)的原理.接着对这两种算法用Z规格说明语言进行了比较详尽的描述.最后给出了一些操作模式的前置条件,并对系统中的一个定理进行了证明.     

计算机操作系统页面置换算法教学中的几点探讨

整个操作系统课程可大概分为处理机管理，存储器管理。设备管理、文件管理，用户界面和接口五部分。其中，内存是计算机工作的瓶颈，存储管理得当能较大的提高系统效率。页面置换算法是存储管理中重要的一环。     

基于空间局部性的PCM和DRAM混合内存页面调度算法简

提出一种新的PCM（phase change memory,相变内存）和DRAM混合内存构架页面调度算法CLOCK-S。该算法根据一个内存页的读写属性以及相邻页的空间局部性,把该页调度到不同的存储器中,从而达到减少对PCM的写操作,延长其寿命的目的。该算法利用各个存储器的优点,避免其缺点。实验表明,相较于传统页面调度CLOCK算法,该算法可减少对PCM的写操作平均达10％。     

基于空间局部性的PCM和DRAM混合内存页面调度算法

提出一种新的PCM(phase change memory,相变内存)和DRAM混合内存构架页面调度算法CLOCK-S。该算法根据一个内存页的读写属性以及相邻页的空间局部性,把该页调度到不同的存储器中,从而达到减少对PCM的写操作,延长其寿命的目的。该算法利用各个存储器的优点,避免其缺点。实验表明,相较于传统页面调度CLOCK算法,该算法可减少对PCM的写操作平均达10%。     

一种基于贝叶斯算法的页面置换评测系统

页面调度算法会影响到操作系统的性能,文章针对操作系统的效率提高性评估原则,提出了一种基于贝叶斯算法的页面置换策略评测系统。通过这种评测系统促进页面置换策略的改进,从而提高操作系统的性能。     

一种基于闪存的低能耗缓冲区管理算法

闪存以其低能耗、低延迟、小巧轻便及高抗震性等特点广泛应用于不同环境中以消除磁盘机械寻址所带来的高能耗及高延迟等问题。提出一种基于闪存硬盘(SSD)的低能耗缓冲区置换算法AFC。当需要选择置换页时,AFC使用基于代价的启发式来选择置换页。AFC的设计目标是基于用户设定的权值,在最小化能耗和最大化吞吐量之间取得平衡。对不同型号的闪存芯片进行了实验验证,实验结果表明,基于AFC来管理缓冲区数据时,可以显著降低系统的能耗。     

一种基于双窗口的NAND闪存缓冲区管理算法

为提升NAND闪存使用寿命和存储性能,提出了一种基于双窗口的NAND闪存区管理算法DW-LRU。DW-LRU算法利用4个LRU链表来捕获访问次数和冷热特征,且根据访问新近度将页面分为了6类:冷干净页面、冷脏页面、旧热干净页面、非旧热干净页面、旧热脏页面、非旧热脏页面。算法在冷干净LRU链表上设置了一个静态窗口,避免最近写入缓存区中的冷干净页面被频繁置换出;在热脏LRU链表上设置了一个动态窗口,用来处理长时间没被访问的热脏页面。实验结果表明:与LRU、LRU-WSR、PR-LRU算法相比,DW-LRU算法缓冲区命中率平均提升了16.8%、12.3%、2.8%。DW-LRU算法可以提高缓冲区命中率,减少闪存写操作次数和算法运行时间。     

基于MWM的闪存数据库缓冲区置换算法

针对现有闪存数据库缓冲区置换算法无法充分发挥闪存存储器性能的现状,提出了一种基于最小权重矩阵(MWM)的高效缓冲区置换算法.该算法基于缓冲区代价置换算法思想,使用MWM来组织管理缓冲区的数据块,将数据访问频度映射为权重参数,用来参与缓冲区中数据块的置换.在闪存感知平台Flash-DBSim上针对几种典型测试类型数据集进行对比实验,结果表明:本文算法充分利用数据访问特征,特别适用于数据库中数据使用频率高的应用场景.     

基于块更新序号的NAND闪存垃圾回收算法

传统NAND闪存垃圾回收算法的管理粒度为块,后续逐渐发展为基于页管理,以更大的内存消耗为代价来提高对数据热度判断的准确度。针对现有算法中存在的不足,提出了一种基于块更新序号的NAND闪存垃圾回收算法。该算法将管理粒度重新定位到块上,定义块的更新序号,提出新的基于动态阈值分段处理的数据热度计算方法以进行更有效的冷热分离,同时回收块选择策略采用新的代价函数以兼顾回收效率与磨损均衡。实验结果表明,提出算法在减少系统内存消耗的同时,获得了比GR、CB、CAT、FaGC、LRGC和LRGC+算法更好的垃圾回收效率和磨损均衡效果。     

Pre-record:一种高效的进程动态迁移算法

后拷贝迁移算法需要在地址空间不完整的情况下恢复进程运行,导致进程由于缺页错误过多而频频中断,严重影响了迁移的整体效率.针对这一问题,提出了Pre-record算法.该算法延长进程在源节点上的执行时间并对该过程中访问的地址空间页面加以记录,迁移时源节点优先迁移被记录的页面,然后继续推送剩余地址空间页面,保证在缺页错误发生频率最高的进程恢复运行初期能够获取所需内存页面.分析及实验结果表明,该算法能够有效降低迁移过程中缺页错误的发生率,进而提高了进程迁移的整体效率,并具有冻结时间短、剩余依赖度低等优点.     

HFB:一种闪存上的块页混合缓存管理方法

闪存有多种优良特性,但是它却还具有较严重的缺点,这使得闪存的性能不高,成为了系统的性能瓶颈。该文提出了一种名为HFB(hybrid flash buffer)的高效闪存缓存管理方法。HFB方法提供页和块两种粒度的缓存管理策略,发挥两种不同粒度替换策略的优势,可以适应随机和顺序性的工作负载。HFB优先减少在闪存上较耗时的写操作,也减少了读和擦除操作。HFB采用八叉树组织缓存数据,实现了对数据的高效管理。该文对HFB进行了理论分析,并采用DiskSim模拟器和实际工作负载对其进行评测。理论分析和实验结果表明:HFB的加权缓存命中率高于其他典型的闪存缓存管理方法。     

基于老化算法的分布式文件缓存算法

为提升数据检索读的性能, 基于老化算法采取Cache方法, 通过设计合理的缓存结构, 给出一种新的分布式文件缓存算法. 该算法在缓存实现部分, 使用了LRU算法中常用的老化算法, 并将其由一个页面置换算法改进为一个文件缓存替换算法, 且在该过程中完好地继承了老化算法的优点. 评测结果显示了改进方法的有效性.     

基于闪存系统的多进制LDPC码译码研究

为了进一步提高闪存系统的可靠性,基于闪存系统的分级调制架构,提出了一种新的多进制LDPC(low density parity check)码译码算法?该译码算法引 入了预处理过程以纠正分级解调器输出的非法符号,通过变量节点和校验节点的迭代运算纠正由噪声干扰带来的错误符号?在迭代运算过程中,变量节点的更新条件设计为只有在不满足2个以上检验和的情况下,才更新该变量节点的符号;且在更新变量节点符号时,考虑到分级调制架构容易出现的相邻换位错误,以及噪声对各单元层次造成的不同影响,选择较有可能被发送的那个符号作为更新符号?仿真结果表明,提出的译码算法性能优于已有的译码算法;通过对比不同的变量节点更新条件得出,设计的更新条件具有更好的性能?     

高速BCH编码译码器的设计

针对闪存(flash)因制造工艺的不断提高而导致其内部数据区随机错误不断增加的现象,设计并实现一种高速BCH编码译码器,通过BCH编码技术对flash中的随机错误进行纠错,以达到错误检测与纠错的目的.实验结果显示优化设计的BCH(4 224,4096)编码译码器可以工作在25 MHz的工作频率下,其单页数据(512 Byte)的纠错能力从普遍的3 bit提高到15 bit,从而提高了flash数据存储与读取的可靠性.     

基于PageRank与HITS的改进算法的网页排名优化

针对传统网页排序算法PageRank和HITS中存在的主题漂移、检索效率低等不足,本文提出了一种改进算法PHIA(PageRank and HITS Improved Algorithm)。该算法继承了HITS算法获取根集和基本集的方法,并且使用根集中所有网页的PageRank值作为Hub和Authority初始迭代值,最后根据马尔可夫链求随机矩阵的特征向量的方式来获取网页排名的静态分布。基于随机关键词的检索结果可知,相比于传统的PageRank和HITS算法,改进PHIA算法具有更快的收敛速度,并且在一定程度上提高了网页排序的准确度。     

请求分页式系统设计的性能保证

请求分页式是当今应用最为广泛的虚拟存储技术.要保证其获得良好的性能,仅关心页面置换算法是不够的,还必须关注诸如存储器分配策略、页面大小、程序结构等多个方面.请求分页式系统的理论依据是局部性原理,在此基础上,结合已有研究成果,从设计者和应用者的角度着重就其中几个因素进行了讨论和研究,力求在理论上得出一般性的结论.     

一种基于MLC SSD的异质感知的ECC设计方法

已有研究发现,同一闪存芯片上的页面在性能、可靠性和持久性方面都存在很大差异.这种页面之间的异质性结构为设计和实现固态盘提供了新的探索空间.该文利用这种异质性结构来设计灵活的纠错码(ECC)从而提高固态盘的性能并延长其寿命.实验结果表明,采用异质感知的ECC方案可以获得大约50%的性能改进和线性的寿命增长.     

关于NAND闪存损耗均衡算法的优化

为了改善NAND闪存不耐擦写的特性,本文对传统的损耗均衡算法(HWL算法)进行优化,主要包括触发机制的优化和将现有的静态损耗均衡与动态损耗均衡策略相结合的优化策略.最后根据需求设计了评估损耗均衡算法效果的测试实验.结果表明:与当前算法相比,本优化算法展现了良好的磨损均衡效果,解决了NAND闪存不耐擦写的缺陷.