KAIST-CS431: Concurrent Data Structure

并发数据结构的关键点#

• 安全性： 安全是并发程序对CDS的最基本的要求
  • Sequential specification：多线程对数据结构的操作要能像一个队列一样
  • Synchronization：如在栈操作中，不同的线程进行pushing和popping操作时是要同步的，不能这边线程执行完了，另外一边无法感知到这边的操作。
  • 通过锁或者更加底层的同步原语来保护并发数据结构
• 可扩展性： 随着CPU核数/并发度的增长，有着良好的性能增长
  • 理想情况下，性能增长应该是线性的，但现实情况往往因为各种限制因素达不到线性增长
  • 通过减少锁保护范围（更细粒度的锁）来减少竞争
    • hand-over-hand locking, lock coupling, read-write locking
  • 通过避免写操作降低缓存失效
• Progress: guaranteeing the completion (or progress) of operations
  • Lock freedom: progress of at least one
  • Wait freedom: progress of everyone

无锁策略#

Lock-Free 和 Wait-Free 都旨在解决传统锁（如互斥锁 mutex）带来的性能和活性问题，但采用了不同的策略和提供了不同的保证。

Lock-Free#

Lock-Free 是一个相对较弱的保证，但仍然非常强大和有用。它的核心思想是：总会有一个线程能够前进，即使其他线程被任意延迟或阻塞。

核心特点：

• 没有死锁 (Deadlock-Free)： 由于没有线程需要等待其他线程释放锁，所以不会发生死锁。
• 没有活锁 (Livelock-Free)： 虽然有可能发生活锁（即线程反复尝试但总是失败），但通常通过回退策略（如指数退避）或设计良好的原子操作序列可以避免。然而，严格意义上的 Lock-Free 并不直接保证 Livelock-Free。
• 进度保证 (Progress Guarantee)： 只要系统不是完全停滞，总有一个或多个线程可以完成操作。这意味着整个系统的吞吐量不会因为某个线程的无限期暂停而归零。
• 饥饿可能 (Starvation Possible)： 某个特定的线程可能会无限期地重试它的操作，而从未成功（即所谓的“饥饿”）。这是 Lock-Free 与 Wait-Free 的一个主要区别。
• 实现方式： 主要依赖于原子操作，如CAS (Compare-And-Swap)，FAA (Fetch-And-Add)，LL/SC (Load-Link/Store-Conditional)等。这些操作通常由硬件提供，能够以原子方式读取、修改和写入内存位置，而无需使用操作系统级别的锁。
• 常见数据结构： 无锁队列 (Lock-Free Queue)，无锁栈 (Lock-Free Stack)，无锁哈希表 (Lock-Free Hash Table) 等。

工作原理示例（CAS）：

假设线程A想修改一个共享变量value：

1. 线程A读取value的当前值old_val。
2. 线程A计算出新的值new_val。
3. 线程A尝试使用CAS(address, old_val, new_val)来更新value。
   • 如果value在期间没有被其他线程修改，那么CAS成功，value被更新为new_val。
   • 如果value在期间被其他线程修改了，那么CAS失败。线程A会重新从第1步开始尝试（循环重试）。

在这个过程中，即使线程A反复失败，其他线程只要能够成功执行它们自己的CAS操作，系统就能继续前进。

优点：

• 消除死锁和活锁的风险（在一定程度上），简化了并发编程模型。
• 高并发性：在许多情况下可以提供比锁更高的吞吐量和更低的延迟，尤其是在竞争不激烈时。
• 避免了内核态切换：原子操作通常在用户空间完成，避免了锁导致的上下文切换开销。

缺点：

• 设计复杂： 正确设计和实现无锁数据结构非常困难，需要深入理解内存模型、原子操作和并发语义。
• ABA 问题： CAS 操作只能检查值是否相同，无法检测到值从A变为B再变回A的情况。需要使用版本号或double-CAS等技术解决。
• 内存序问题： 需要仔细处理编译器和CPU的内存重排，确保内存操作的可见性和顺序，通常通过内存屏障 (Memory Barriers) 来实现。
• 不保证公平性/避免饥饿： 如前所述，某些线程可能一直无法成功。

Wait-Free#

Wait-Free 是比 Lock-Free 更强的保证，它承诺：在有限数量的步骤内，每个线程都能完成其操作，无论其他线程的行为如何。

核心特点：

• 包含 Lock-Free 的所有优点： 无死锁、无活锁。
• 无饥饿 (Starvation-Free)： 这是 Wait-Free 的最重要特性。FSM（Fair Share Model）确保了即使单个线程无限期地暂停或延迟，其他活跃的线程也能在有限的步数内完成它们的操作。每个线程都有一个固定的上限来完成它的操作。
• 进度保证更强： 不仅仅是“总有一个线程前进”，而是“每个线程都能前进”。
• 实现难度： 远超 Lock-Free，是并发编程中最难实现的技术之一。
• 实现方式： 通常涉及到更复杂的算法，可能不仅仅是简单的原子操作，还可能涉及“帮助”其他线程完成它们的操作。

工作原理示例（通用 Wait-Free 方案）：

通常 Wait-Free 算法会涉及如下模式：

1. 每个线程在共享内存中维护一个表示其当前“意图”或“进度”的状态。
2. 当一个线程尝试执行操作时，它会首先检查是否有其他线程被阻塞，并且需要帮助。
3. 如果发现需要帮助的线程，当前线程可能会暂时暂停自己的操作，而去执行被阻塞线程的部分任务，帮助其前进。
4. 一旦被帮助的线程完成了它的操作（或者当前线程帮助它完成了足够的任务），当前线程再继续执行自己的操作。
5. 这种帮助机制确保了没有线程可以无限期地被阻塞。

优点：

• 最强的活性保证： 保证所有线程都能在有限时间内完成操作，彻底消除饥饿。
• 容错性高： 即使部分线程崩溃，其他线程也能继续正常工作。

缺点：

• 极致的复杂性： 设计和实现 Wait-Free 算法的难度非常高，需要高级的数学证明和深刻的并发理论知识。
• 性能开销： 通常为了提供无饥饿的保证，Wait-Free 算法可能需要线程执行额外的工作（例如，帮助其他线程），这可能导致在竞争不激烈或无竞争的情况下，性能低于 Lock-Free 或甚至基于锁的方案。在某些场景下，为了保证无饥饿，操作所需的总步骤数会显著增加。
• 不广泛适用： 只有少数特定场景（例如，需要极高可靠性和确定性实时响应的系统）才值得投入巨大的成本去实现 Wait-Free。

Lock Coupling#

Lock-coupled linked list#

最初级的并发链表实现思路是使用一个粗粒度的大锁，在对链表中任意一个成员进行访问时，都需要这把锁的保护。显然，这种方式极大降低了链表的并发性。如果链表很长，即便两个链表成员间毫无关联，也不能进行并发访问。

一个优化思路是，将大锁拆成每个成员独享的小锁，访问成员需要先申请这把锁。同时，这把锁也还保护着链表成员里面的next指针，在获取了下一个成员的锁后，当前成员的锁才会被释放（hand-over-hand），保证当前成员没有被释放。

操作#

Insert#

struct node {
  pthread_mutex_t mu;

  int data;
  struct node* next;
};
typedef struct node node_t;

node_t *llist_insert(node_t *prev, node_t *n) {
  pthread_mutex_lock(&(prev->mu));
  n->next = prev->next;
  prev->next = n;
  pthread_mutex_unlock(&(prev->mu));

  return n;
}

Remove#

优缺点#

• 在保证了扩展性的同时实现简单
• 因为需要获取锁，即便是读取操作也会导致缓存失效
• 在实现时需要小心死锁

无锁数据结构#

Treiber’s Stack#

思想：利用CAS对栈顶进行入栈和出栈操作

Michael-Scott Queue#

Lock-Free Linked List#

操作#

遍历策略#

其他无锁数据结构#

环形队列#

• https://people.mpi-sws.org/~dreyer/papers/gps/paper.pdf

Chase-Lev work-stealing deque#

• https://www.dre.vanderbilt.edu/~schmidt/PDF/work-stealing-dequeue.pdf
• https://fzn.fr/readings/ppopp13.pdf
• https://github.com/jeehoonkang/crossbeam-rfcs/blob/deque-proof/text/2018-01-07-deque-proof.md