这篇文档属于类型a，即报告了一项原创性研究。以下是针对该研究的学术报告：

2PLSF：一种具有无饥饿特性的两阶段锁定并发控制算法

1. 研究作者、机构及发表信息

本文由Pedro Ramalhete（Cisco Systems）、Andreia Correia和Pascal Felber（University of Neuchâtel）合作完成，发表于PPoPP ‘23（ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming），会议时间为2023年2月25日至3月1日。

2. 学术背景

研究领域：本文属于并发控制算法（concurrency control algorithms）领域，聚焦于数据库管理系统（DBMS）中的事务处理。
研究动机：经典的两阶段锁定（Two-Phase Locking, 2PL）算法虽能提供事务的序列化（serializability）和不透明性（opacity），但存在以下问题：
- 活锁（live-lock）风险：高并发场景下事务可能因资源竞争陷入无限重启。
- 扩展性不足：读密集型工作负载（如索引结构中的根节点访问）因锁竞争导致性能下降。
研究目标：提出一种新型2PL算法2PLSF（Two-Phase Locking with Starvation-Freedom），通过改进读写锁设计，实现高扩展性且无饥饿（starvation-free）的事务处理。

3. 研究流程与方法

3.1 算法设计

2PLSF的核心创新包括：
1. 高效的读写锁：
- 分布式读指示器（read-indicator）：将读锁状态分散到多个缓存行，减少线程间竞争。
- 原子存储优化：读锁释放通过atomic store-release实现，比传统原子递减操作更高效。
- 冲突检测机制：仅在首次冲突时从全局时钟（conflictclock）获取时间戳，减少集中式时钟的竞争。

1. 无饥饿保证：
   
   • 事务重启次数上限为线程数减一（(N_{threads}-1)），确保最终提交。
     
   • 冲突时，事务仅需等待直接冲突方（而非所有低优先级事务），提升效率。
     

3.2 实验验证

实验环境：
- 硬件：双路Intel Xeon E5-2683 v4（32核/64线程）。
- 软件：Ubuntu 20.04，GCC 10.3.0。

测试对象与工作负载：
- 数据结构：链表、哈希表、跳表、Zip树、松弛AVL树（relaxed AVL tree）。
- 负载类型：
- 写密集型（50%插入+50%删除）。
- 读密集型（80%查询+10%插入/删除）。
- 纯查询（100%查询）。

对比算法：
- 传统2PL变体（no-wait、wait-or-die、deadlock-detection）。
- 乐观并发控制（如TL2、TinySTM、TicToc）。

性能指标：吞吐量（operations/s）、尾延迟（p90/p99）。

4. 主要结果

1. 读写锁优化效果：

   • 2PLSF在读密集型负载中接近乐观算法的性能（如TinySTM），而在写密集型负载中显著优于传统2PL（吞吐量提升2倍以上）。
     
   • 示例数据：在哈希表测试中，2PLSF的吞吐量达60M ops/s，而TL2因全局时钟竞争停滞在15M ops/s。
     

2. 无饥饿特性验证：

   • 在成对冲突测试中，2PLSF的尾延迟（p99）仅为2.4毫秒，而TL2和TinySTM分别达50毫秒和5秒。
     
   • 事务重启次数严格受限于(N_{threads}-1)，避免了活锁。
     

3. 索引结构兼容性：

   • 2PLSF可直接用于树形索引（如AVL树），而传统DBMS因2PL扩展性问题通常采用乐观读的索引。
     

5. 结论与价值

科学价值：
- 首次将无饥饿保证与高扩展性结合于2PL算法，填补了悲观并发控制在理论上的空白。
- 提出了冲突时排序（conflict-time ordering）机制，避免全局时钟瓶颈。

应用价值：
- 为DBMS提供统一的并发控制方案，简化索引与记录的锁管理。
- 适用于对尾延迟敏感的场景（如金融交易系统）。

6. 研究亮点

1. 创新锁设计：通过位级读指示器和原子存储优化，降低读锁开销。
   
2. 理论突破：严格证明事务重启次数的上限，确保无饥饿性。
   
3. 实践兼容性：算法可直接集成至现有DBMS（如DBx1000），无需修改底层存储引擎。
   

7. 其他贡献

• 调试友好性：2PLSF的悲观锁机制在调试时可提供一致的内存视图，优于乐观控制的“读后验证”问题。
  
• 内存回收优化：无需安全内存回收（SMR）机制，简化工程实现。
  

这篇报告全面介绍了2PLSF算法的设计、验证与贡献，为并发控制领域的研究者提供了重要参考。