软件事务内存的动态竞争管理策略

软件事务内存是为了简化并行程序设计而出现的一种新的程序设计技术。为了降低软件事务内存系统中事务冲突的发生频率以提升系统整体性能,提出了一种新的基于动态控制和队列调度的竞争管理策略。定义了竞争强度的概念和系统总体框架,并在此基础上给出了利用运行时反馈信息动态调节竞争强度的方法。同时给出了事务序列化的设计方法与实现中应注意的问题,通过将冲突概率大的事务序列化以达到避免相同冲突再次发生的目的。结合常用的基准数据结构,对模型和算法进行了实验,最后结果表明了算法的正确性和有效性。

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

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

基于TL2软件事务内存的并发程序的精化验证

软件事务内存并发机制将对共享存储复杂的同步访问控制转嫁给底层系统开发者,从而大大减轻高层程序员开发并发程序的负担。TL2是一个经典的基于锁的高性能软件事务内存算法。本文以一个TL2读写事务的底层具体实现为验证目标,首先采用并发程序间的精化关系来刻画基于TL2的底层细粒度并发程序是某个具体的高层抽象原子事务代码块的正确实现,然后通过基于依赖保证的并发程序模拟技术证明两个程序间具有精化关系,完成读写事务的底层实现在代码级的验证并总结TL2算法满足的不变式,为完成TL2算法在代码级的完整验证奠定基础。

一种分布式非结构化数据副本管理模型

针对云存储系统中数据副本管理的延时响应等问题,提出一种面向非结构化数据的分布式副本管理模型。该模型采用机架选举算法,通过提高每个机架能源利用率的方法降低系统整体能耗,为绿色数据中心提供技术保障。运用多路线性散列算法,将数据副本动态均匀地分布到不同机架的不同节点中,以提高系统性能、平衡负载和资源利用率。仿真实验结果证明,与传统的全局映射法相比,该模型可以达到较高的存储与负载平衡,具有良好的扩展性和可用性。

面向STM的松弛存储一致性算法

软件事务性内存(STM)提供同步手段,让多线程程序高效并发执行。如果两个事务访问了同一个共享数据且至少一个事务进行了修改操作,则称发生了冲突。检测冲突后,一般选择一个事务终止。当前的STM实现都基于严格的线性一致性(Linearizability)语义模型,实现简单。但是,基于该语义会导致很多本来可以完成提交的事务失败,降低了系统效率。把因果一致性模型应用于STM,可以在保证程序准确性条件下取得较好的实际性能。实验数据表明,该算法简单高效,明显减少了冲突数目。

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

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