一种基于目录的软件事务性内存实现算法

软件事务性内存(STM)提供同步手段,让多线程程序高效并发执行.STM算法中一般包含记录所访问的共享数据、缓冲投机修改的数据以及处理事务冲突.STM中的主要开销在于维护共享数据访问记录和一致性验证.维护共享数据访问记录主要目的是便于进行验证.冲突检测(conflict detection)判断两个事务能否同时提交,而验证(validation)确保每个线程看到的数据状态是一致的.给出了关于STM一个简单模型,证明在STM中对共享数据的修改是线性的.提出的LDSTM算法通过在目录中维护版本信息,可以在读取各个共享对象时快速确定事务的内存视图是否处于一致状态,可以极大减少冲突检测和验证的开销.该算法可以实现早期发现写一写冲突,减少无效计算.在单线程情况下该算法开销很小.实验数据表明,LDSTM简单高效,冲突检测和验证开销减少明显.     

基于STM模型的面向可视化并行程序的设计

并行程序设计由于需要考虑进程之间的同步等问题使得编码过程十分复杂。可视化的并行程序设计为程序员提供了图形化的编程模板和骨架来进行并行程序的设计工作,在一定程度上减小了并行程序的设计难度。首先研究软件事务性内存模型,它相对于传统的并行程序设计方法而言有着接口简单灵活,可扩展性强等特点,之后将STM模型运用到可视化程序设计中来,使得其编程接口以UML活动图的形式提供给编程人员使用,不用依赖特定的软件或硬件环境,提高了可视化并行程序设计的通用性与可扩展性。     

Co-Work:基于HDFS的安全云存储数据一致性保持算法

针对云存储平台中用户隐私和敏感数据的安全保护问题,在前期提出的基于自主可控机制的安全云存储模型ASOM(All Self-Organization Model)基础上,对MDSS端元数据的管理操作、MDSS和DMS之间的通信过程做进一步优化,针对ASOM模型实际场景引入锁思想实现两个节点一致性的Co-Work算法,完成MDSS和DMS节点之间的协同工作和数据的一致性保持。同时,考虑网络带宽对ASOM中读写效率的影响,引入随机表机制,改变DSS上报的时间结点,以提高ASOM整体读写效率。测试结果表明:执行Co-Work算法后的ASOM模型实现了数据的物理与逻辑隔离,保证用户对元数据的自主控制和管理,而且随着数据尺寸增大读写效率明显提高,在数据达到1 GB时读写效率提高了12%。     

面向监听一致性协议的并发内存竞争记录算法

内存竞争记录是解决多核程序执行不确定性的关键技术,然而现有点到点的内存竞争记录机制带来的硬件开销大,难以应用到实际的片上多核处理器系统中.以降低点到点内存竞争记录方式的硬件开销为出发点,为采用监听一致性协议的片上多核处理器(chip multiprocessor, CMP)系统设计了基于并发记录策略的点到点内存竞争记录算法.该记录算法将两两线程间点到点的内存竞争关系扩展到所有线程,采用分布式记录方法为每个线程记录一个由内存竞争关系的一方构成的内存竞争日志;重演时采用简化的生产者消费者模型,确保了确定性重演的实现,有效降低了硬件消耗和带宽开销.在8核处理器系统中的仿真结果表明,该并发式点到点内存竞争记录算法为每个处理器核添加硬件资源约171B,每千条内存操作指令记录日志大小约2.3B,记录和重演阶段均添加不到1.5%的带宽开销.     

安全持久性内存存储研究综述

在计算机技术和互联网技术飞速发展的进程中,计算机安全防护和数据机密性保护一直是学术界和工业界关注的焦点.主流的内存安全机制通过提供硬件辅助的机密性与完整性验证,确保选定的代码在运行时的内存可信,达到数据保护、防止泄漏和遭篡改的目的.新型持久性内存可像DRAM一样放置在内存总线上,通过处理器load和store指令进行访问,此外,持久性内存能够提供大容量和数据持久性支持,具有高带宽和低延迟的数据访问特性.然而,由于介质特性上的差异,面向DRAM的内存安全机制无法在持久性内存上高效运行,甚至存在可用性问题.因此,构建基于持久性内存的安全内存存储系统将为大数据的安全高效存储带来新的机遇.首先,针对持久性内存的写特性,分析了将面向传统易失内存的安全防护措施应用于持久性内存会引起额外开销的原因,并介绍相关降低开销的研究工作.其次,针对持久性内存的非易失性,分析了为保障持久性内存在其生命周期内的安全性所面临的问题与挑战,并介绍了数据及其安全元数据的一致性管理相关研究工作.最后,总结了构建面向持久性内存的安全存储系统面临的挑战,对相关工作进行综合比较,并提出下一步研究展望.     

面向RISC-V内存一致性测试的自动化分析方法

开源架构RISC-V定义了其内存一致性模型RVWMO,作为多核RISC-V系统软硬件设计开发的重要规范。在多核芯片的验证阶段,需要对芯片的内存一致性进行严格全面的测试。测试通常针对某一访存顺序模式,选取典型的并行程序片段进行大规模测试（又称Litmus测试）,通过程序运行的最终状态推测芯片内存一致性模型。通常,更为宽松的内存一致性会导致更多的程序状态。分析Litmus测试结果对于验证芯片的RVWMO兼容性、探索多核系统的内存一致性优化的可能性具有重要意义。以RVWMO规范下允许的程序状态为基准,芯片实测得到更多的程序状态表明其存在兼容性问题,得到更少的程序状态表明其仍具有优化空间。面对规模庞大、行为复杂的Litmus测试,如何对其测试结果进行自动化分析是亟待解决的问题。本文对Litmus测试的原理和输出结果进行了深入分析,提出一种面向RISC-V内存一致性测试的自动化分析方法,采用形式化方法对Litmus测试进行基于RVWMO规范的模拟运行,并通过与芯片的实测结果进行对比分析给出测试结论。本方法基于Hifive Unmatched开发板开展测试。实验表明,本文提出的方法可快速、有效地对RISC-V内存一致性测试进行自动化分析。     

面向非易失内存的数据一致性研究综述

随着DRAM技术面临密度扩展瓶颈以及高泄漏功耗问题,新型非易失内存(non-volatile memory, NVM)因其非易失、高密度、字节寻址和低静态功耗等特性,已经得到学术界和工业界的广泛关注.新型非易失内存如相变内存(phase change memory, PCM)很可能替代DRAM或与DRAM混合作为系统主内存.然而,由于NVM的非易失特性,存储在NVM的数据在面临系统故障时可能由于部分更新或内存控制器写重排序而产生不一致性的问题.为了保证NVM中数据的一致性,确保对NVM写操作的顺序化和持久化是基本要求.NVM有着内在缺陷如有限的写耐久性以及较高的写延迟,在保证NVM数据一致性的前提下,减少NVM写次数有助于延长NVM的寿命并提高NVM系统的性能.重点讨论了基于NVM构建的持久索引、文件系统以及持久性事务等数据一致性研究,以便为实现低开销的数据一致性提供更好的解决方案或思路.最后给出了基于NVM的数据一致性研究展望.     

一种基于HashGraph的NoSQL型分布式存储因果一致性模型

分布式环境中的数据因果一致性指的是对具有因果依赖性的数据进行更新时,须同步更新其他分布式副本中的依赖性元数据,同时满足较高的可用性和性能需求.为解决现有成果中更新可见延迟较高的问题,在数据中心稳定向量的基础上,结合混合逻辑时钟和HashGraph原理,提出了Causal-Pdh模型.使用部分向量和校验值作为消息签名代替了所有向量,并且借鉴HashGraph的原理,改进了各个数据中心同步最新条目的过程,各个父节点随机与其他父节点同步最新状态,从而降低了虚拟投票所使用的时间.最后通过实验验证了Causal-Pdh模型不仅没有影响客户端的吞吐量,而且在时钟偏移较严重时降低了20.85%的用户PUT等待延迟,在系统中存在查询放大的情况时,PUT响应时间降低了23.27%.     

MOTEC: 一个存储一致性模型验证工具

由于缺乏可利用的额外观察条件,在芯片流片后阶段进行存储一致性模型验证较困难。为此,利用多核处理器系统中通用的性能计数器,通过定期扫描性能计数器以获得关键活动访存指令集合的信息,实现MOTEC工具。该工具由MOTEC随机指令发生模块、多核处理器性能计数器记录模块和MOTEC分析模块3个部分组成。对其核心算法的分析结果表明,MOTEC的时间复杂度仅为 ,在目前流片后阶段进行验证的工具中时间复杂度最低。     

片上多核处理器存储一致性验证

存储一致性验证是片上多核处理器功能验证的重要部分.由于验证并行程序的执行结果是否符合存储一致性模型理论上是NP难问题,现有的验证方法中只能采用一些时间复杂度大于O(n3)的不完全方法.发现在支持写原子性的多处理器系统中,两条执行时间不重叠的操作之间存在确定的时间序.通过引入时间序的概念,设计并实现了一种线性时间复杂度的存储一致性验证工具LCHECK.LCHECK利用时间序将验证局部化,使得在表示程序执行结果的有向图中,序关系边的推导和正确性检测都被限定在有限范围内.与现有其他方法相比,LCHECK时间复杂度低,对程序长度和访存地址数没有限制,因此验证效率更高.作为国产片上多核处理器龙芯3号的重要验证工具, LCHECK发现了一些存储系统的设计错误.     

面向数据库的持久化事务内存

硬件事务内存(hardware transactional memory, HTM)和可字节寻址的非易失性内存(nonvolatile memory, NVM)已经可以在新的计算机设备中使用.使用HTM确保一致性和隔离性,使用NVM确保持久性,组合使用两者可以实现满足原子性、一致性、隔离性和持久性(atomicity, consistency, isolation and durability, ACID)特性的事务.ACID事务在数据库中非常有价值,但由于数据库事务通常较大,其面临的挑战是HTM固有的容量限制和争用水平.首先提出了一种通过HTM进行ACID事务处理的软硬件解决方案——持久化HTM(persistent HTM, PHTM).使用2种方法来消除PHTM的局限性:1)持久化混合事务内存(persistent hybrid TM, PHyTM),允许PHTM事务与支持任意大小的纯软件事务(software transactional memory, STM)并发执行;2)分离事务执行(split transaction execution, STE)算法,该算法为关系数据库事务量身定制,解决了大多数事务超过PHTM的容量限制的问题.简而言之,讨论了利用NVM将HTM扩展到ACID数据库事务的问题.     

面向对象的存储一致性模型OC

提出了一种新的面向对象的存储一致性模型-OC．该模型基于位置一致性（Location Consistency）模型中所描述的偏序关系，从而打破了传统的存储密致性（Memory Coherence）所要求的全局序的限制．该模型是较高的软件层次上的存储模型，结合了现代程序设计中面向对象的特色，可广泛应用到共享存储的编程语言中．我们还论述了OC的主要特性，并将OC与其它存储模型进行了简单的比较．最后在仿真器上对它的行为进行了仿真验证．     

一种基于时间戳的高扩展性的持久性软件事务内存

新兴的非易失性内存(non-volatile memory, NVM)具有字节寻址、持久性、大容量和低功耗等优点,然而,在NVM上进行并发编程往往比较困难,用户既要保证数据的崩溃一致性又要保证并发的正确性.为了降低用户开发难度,研究人员提出持久性事务内存方案,但是现有持久性事务内存普遍存在扩展性较差问题.测试发现限制扩展性的关键因素在于全局逻辑时钟和冗余NVM写操作.针对这2个方面,提出了线程逻辑时钟方法,通过允许每个线程拥有一个独立时钟,消除全局逻辑时钟中心化问题;提出了缓存行感知的双版本方法,为数据维护2个版本,通过循环更新这2个版本来保证数据的崩溃一致性,从而消除冗余的NVM写操作.基于所提出的这2个方法,实现了一个基于时间戳的高扩展的持久性软件事务内存(scalable durable transactional memory, SDTM),对比测试显示,在YCSB负载下,与DudeTM和PMDK相比,SDTM的性能最多分别提高了2.8倍和29倍.     

以操作系统为中心的存储一致性模型--线程一致性模型

分布共享存储系统为保证程序的正确执行，必须通过存储一致性模型对共享存储访问顺序加以限制，而现有模型在可扩展性和操作系统级实现方面存在不足。结合多线程的特点，提出了一种以操作系统为中心的线程一致性模型，通过并行程序执行过程中线程状态的变化来观察和限制存储访问事件的正确顺序，有利于系统的可扩展性、一致性维护信息获取的方便性和完备性以及操作系统本身的设计和实现。分别从模型的定义、正确性证明、实现方案和性能分析等几个方面展开了论述。     

一种分布式持久性内存文件系统的一致性机制

持久性内存(persistent memory, PM)和远程直接内存访问(remote direct memory access, RDMA)具有高带宽、低延迟的硬件性能,这为设计高性能的分布式存储系统提供了新的机遇.然而,它们这些新的特性为高效的数据一致性管理引出了诸多问题：一方面,持久性内存数据一致性依赖于CPU主动执行硬件指令刷写缓存实现,而这类指令开销极高,严重影响CPU处理性能;另一方面,RDMA在服务器端CPU不参与的情况下直接读写服务器端内存,因此服务器端CPU无法主动感知数据写入事件以执行数据刷写操作,一旦系统崩溃会造成数据不一致的问题.针对以上2个问题,提出一种分布式持久性内存文件系统的一致性机制(crash consistency mechanism, CCM)：首先设计实现了基于操作日志的一致性保障策略,通过将每次操作的元信息记录至日志,并持久化,以保障系统的一致性状态;其次,设计了一种客户端对服务器端的远程写一致性策略,在完成数据传输的同时使服务器端CPU主动执行数据刷写;最后实现了一种服务器端的数据异步持久化,以提高系统的处理能力.测试结果表明,基于CCM的文件系统写吞吐可达到网络裸带宽的88%.相比于现有系统Octopus,CCM性能下降控制在1%以内.     

弱一致性模型下的分布式垃圾回收算法RRDGC

垃圾回收有效地减轻了编程人员的负担、优化了程序的设计,在基于弱一致性模型的分布式共享存储系统中进行自动垃圾回收是非常困难的和低效的,本文提出了一种基于跟踪策略的实时分布式垃圾回收算法--RRDGC，使得各节点回收进程可以和应用程序并发执行，同时有效减少了弱一致性模型下额外的通信开销，降低了程序的响应时间．算法确保了垃圾回收的正确性和有效性，体现了增量和实时性的特点．最后通过仿真实验对比论证了该算法的正确性和高效性．     

一种准串行化并发控制算法

由于实时数据库应用的特性是满足事务的时限,在多数情况下,可串行化协议不适合实时数据库系统,必须放松标准。本文提出基于相似性的高优先级两段锁协议(H2PL)算法,在系统可以忍受的不一致性范围内,系统的性能提高了。