面向硬件事务存储系统冲突管理机制的研究

摘要

随着多核处理器的出现，多核之间共享存储编程模式的有效线程同步问题变得更加严峻和迫切。事务存储最早作为一种替代锁同步的并行编程模型被提出，现在已经成为了在并行程序设计方面的一个热点领域。硬件事务存储以其高性能和强原子性而受到欢迎。但硬件事务存储也同其它实现方式一样存在着事务冲突的问题。虽然近年来在解决事务冲突领域已经开展了很多卓有成效的研究，但面对事务冲突仍然存在着以下的挑战：
　　挑战之一，事务冲突直接影响着事务存储系统的性能。在事务冲突不严重时，现有的硬件事务存储系统会达到和锁相当或更好的性能，但当事务冲突比较严重时，系统的性能就明显下降，在极端的情况下甚至会造成死锁或活锁。
　　挑战之二，不同的应用通常具有不同事务特征，这就造成了事务冲突特征的多样性。虽然有一些负载分析的方法，通过统计事务特征，诸如事务寿命、读/写集大小、读/写的频度等来帮助理解事务的冲突特征，但这些方法多半都是离线的、后验的，难以对实际应用的事务特征提出有效的优化建议。
　　挑战之三，当事务冲突严重时事务存储系统的性能会显著降低，为此 Bobba等学者引入病态的的概念来描述严重的事务冲突状态，并有针对性地提出了解决病态的方案。但以他们的方法，很难找出一种能够适用于不同应用的通用冲突管理策略。
　　挑战之四，现有绝大多数冲突管理策略是基于事务的局部信息做决策的，但在全局的角度看来局部的优化未必是全局的优化。
　　本文的研究针对以上的挑战，主要围绕着如何有效地解决硬件事务存储系统的冲突尤其是严重的事务冲突展开。本文的主要研究内容如下：
　　第一，为了方便地理解严重的事务冲突，本文引入了事务拥塞的概念来描述严重的事务冲突。并定义了处于暂停、放弃和退避阶段的事务个数和死锁或活锁的发生次数这两个指标衡量是否发生事务拥塞。
　　第二，本文以TMProf在线性能检测器为基础，实现了事务性能监测器，使它能够及时发现事务拥塞并向全局冲突管理发出警告。
　　第三，提出了基于监测的全局冲突管理机制，并以此为框架实现了三个具体的机制。这三个机制如下：
　　首先，提出了基于SAB(Stall, Abort and Backoff)的全局冲突管理机制。该机制在轻度拥塞出现时，由全局冲突管理器帮助系统解决拥塞，选择一个或者几个处于暂停状态的处理器让它们放弃，释放它们占有的资源给其他需要的事务。优点在于它的实现代价较低并为系统开发了更多的并行度。
　　然后，提出了面向死锁和活锁的冲突管理机制。当死锁或活锁发生时，本文认为系统陷入了重度拥塞。全局冲突管理器介入进来帮助系统摆脱死锁或活锁的状态。这种方法能够有效地防止了死锁活锁发生时系统性能的下降。
　　最后，提出了基于重试队列的全局事务管理机制。这个方案同时采用SAB及死锁和活锁这两个指标来监测事务存储系统是否发生拥塞。经过一个采样周期，如果事务性能监测器监测到拥塞的现象，全局冲突管理器就会介入。使用重试队列避免了选择的盲目性，减小事务的执行开销。
　　本文针对每一个具体的全局冲突管理机制都进行了基于全系统仿真的性能评估，实验结果表明这三种全局冲突管理机制都能有效地提高系统的性能。

目录

面向硬件事务存储系统冲突管理机制的研究

RESEARCH ON CONTENTION MANAGEMENTFOR HARDWARE TRANSACTIONAL MEMORYSYSTEM

摘要

Abstract

Contents

第 1 章 绪 论

1.1 课题背景及研究的目的和意义

1.1.1 业界动态

1.1.2 并行编程的困难

1.3 硬件事务存储

1.4.1 基于SAB的全局冲突管理机制

1.4.2 面向死锁和活锁的全局冲突管理机制

1.4.3 基于重试队列的全局冲突管理机制

第 2 章 基于监测的全局冲突管理机制

2.2.1 早期的冲突解决策略

2.2.2 病态现象及其解决策略

2.2.3 基于冲突密度的冲突解决方案

2.3.1 事务性能监测器

2.3.2 全局冲突管理器

2.3.3 基于监测的全局冲突管理机制的特点

第 3 章 基于SAB的全局冲突管理机制

3.1 引言

3.2 轻度事务拥塞

3.3 基于SAB的监测

3.4 基于SAB的全局冲突管理机制

3.5 性能评估方法

3.6 实验结果及分析

3.6.1 用于比较分析的冲突管理策略

3.6.2 加速比结果及分析

3.6.3 事务执行时间的比例构成

3.6.4 放弃操作对性能的影响

3.7 本章小结

第 4 章 面向死锁和活锁的全局冲突管理机制

4.1 引言

4.2 面向死锁或活锁的全局性能监测

4.3 面向死锁或活锁的全局冲突管理机制

4.4 性能评估方法

4.5 实验结果及分析

4.5.1 加速比结果及分析

4.5.2 对死锁和活锁的影响

4.5.3 事务执行时间的比例构成

4.5.4 放弃操作对性能的影响

4.6 本章小结

第 5 章 基于重试队列的全局冲突管理机制

5.1 引言

5.2 基于重试队列的全局冲突管理机制

5.3 性能评估方法

5.4 实验结果及分析

5.4.1 加速比结果及分析

5.4.2 对死锁和活锁的影响

5.4.3 事务执行时间的比例构成

5.4.4 放弃操作对性能的影响

5.5 三种基于监测的全局冲突管理机制的比较

5.5.1 实现代价的比较

5.5.2 性能的比较

5.5.3 三种机制的适用领域

5.6 本章小结

结论

参考文献

攻读博士学位期间发表的论文及其它成果

哈尔滨工业大学学位论文原创性声明及使用授权说明

致谢

个人简历