February
1st,
2019
事务内存
原子构造
将语句以原子方式运行，系统会以锁的方式实现这个功能。
lock();
// do sth
unlock();
atomic{
// do sth
}
事务内存特点
- 原子性
- 一旦事务提交，所有事务中内存操作会生效
- 一旦事务终止，所有事务中内存操作会失效
- 孤立性：在事务提交之前，其他处理器无法看到结果
例子：树的操作。当两个线程改写节点3和4时，会同时读取节点1和2。使用锁会限制程序并行，可以使用事务内存。
性能
atomic与lock
- atomic：高层次原子性声明
- lock：低层次阻塞原语
- 锁可以用于实现原子块
- 原子块减少了数据结构的竞争性，但在程序中依然可能存在冲突，例如将一整个原子块错误拆分成两个原子块
事务内存的实现
data version
用于管理新版本数据与老版本数据
Eager（undo-log）
立即更新内存，并维护undo-log记录原数据。提交版本时直接清空undo-log，终止版本时用undo-log更新内存。
Lazy（write-buffer）
将修改记录至write-buffer。提交版本时用write-buffer更新内存，终止版本时清空write-buffer。
conflict detection
两种冲突：
- Read-Write： A读地址X，B写地址X
- Write-Write：A写地址X，B写地址X
Pessimistic detection
- 每次在载入/存储时检测冲突，然后停止。
- 硬件实现，见后面。
Optimistic detection
- 只有在提交事务时检测冲突；冲突后，对提交事务施加优先级，优先级低的可能终止。
- 硬件：类似于缓存一致性检测，检测写的有效性。
detection granularity
不同级别：
- 对象：额外开销小，大对象产生错误共享
- 机器字节：最小化错误共享，增加额外开销
- 缓存行：一种很好的妥协尺寸
example
- Hardware
- lazy+optimistic：standford TCC
- lazy+pessimistic：MIL LTM，Intel VTM
- eager+optimistic：Wisconsin LogTM
- eager+pessimistic：no
- software
- lazy+optimistic(r/w)：Sun TL2
- lazy+optimistic(r)/pessimistic(w)：MS OSTM
- eager+optimistic(rd)/pessimistic(w)：Intel STM
- eager+pessimistic(r/w)：Intel STM
硬件事务内存的实现
- data version用缓存行实现
- conflict detection用缓存一致性原则实现
- 略=。=