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

• 作者: 张小强 彭元喜 彭林 谢伦国
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 软件事务性内存(STM) 冲突检测 验证 并发 多线程
• 年，卷（期）: 2008,（9）
• 所属期刊栏目: 算法理论
• 页码范围: 1517-1523
• 页数: 7页
• 分类号: TP301
• 字数: 6547字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谢伦国	国防科学技术大学计算机学院	17	61	5.0	7.0
2	彭林	国防科学技术大学计算机学院	8	36	4.0	5.0
3	张小强	国防科学技术大学计算机学院	5	42	3.0	5.0
4	彭元喜	国防科学技术大学计算机学院	11	82	5.0	9.0