名称: 软件事务内存 描述: ‘实现软件事务内存。使用场景：(1) 构建并发数据结构，(2) 简化无锁代码，(3) 组合原子操作。’ 版本: 1.0.0 标签:
- 并发
- stm
- 事务
- 同步 难度: 中级 语言:
- haskell
- rust 依赖项: []
软件事务内存
实现STM用于无锁并发编程。
使用场景
- 并发数据结构设计
- 简化无锁算法
- 组合原子操作
- 内存中的数据库风格事务
此技能的作用
- 实现事务 - 原子读写块
- 处理冲突 - 冲突检测和重试
- 提供可组合性 - 事务组合
- 优化性能 - 读/写集
关键概念
| 概念 | 描述 |
|---|---|
| 读集 | 事务中读取的变量 |
| 写集 | 事务中写入的变量 |
| 提交 | 验证和应用写入 |
| 中止 | 丢弃更改，重新开始 |
| 重试 | 等待条件，重新开始 |
| 或否则 | 中止时的替代方案 |
STM属性
- 原子性: 全有或全无
- 隔离性: 无中间状态可见
- 一致性: 保持不变量
- 可组合性: 组合操作
提示
- 保持事务简短
- 避免长时间运行的操作
- 使用重试进行阻塞
- 考虑竞争模式
- 分析中止率
相关技能
actor-model-implementer- 参与者并发race-detection-tool- 竞争检测weak-memory-model-verifier- 验证并发
研究工具与工件
STM实现:
| 系统 | 语言 | 学习要点 |
|---|---|---|
| Haskell STM | Haskell | 可组合事务 |
| Clojure refs | Clojure | 生产STM |
| Intel TSX | C/C++ | 硬件支持 |
| TinySTM | C | 快速STM |
关键论文
- Shavit & Touitou (1997) - 原始软件事务内存论文
- Herlihy & Moss (1993) - 硬件事务内存
- Harris, Marlow, Peyton Jones, Herlihy (2005) - “Composable Memory Transactions” (PPoPP 2005)
研究前沿
1. 硬件事务内存
- 目标: 硬件对事务的支持
- 方法: TSX, HTM
- 工具: Intel TSX
实现陷阱
| 陷阱 | 实际后果 | 解决方案 |
|---|---|---|
| 饥饿 | 事务永不提交 | 有界重试 |
| 竞争 | 高中止率 | 仔细设计 |