共享数据与条件竞争

共享数据与条件竞争

在多线程编程中，共享数据的访问和修改是最容易引发问题的地方。如果共享数据只是只读，那么所有线程都能安全地访问这些数据，不会引起冲突；但一旦一个或多个线程尝试修改共享数据，就可能产生严重的问题，需要格外小心，确保所有线程都能正确工作。

不变量（Invariants）

不变量是指在程序运行过程中必须保持为真的条件，用来描述数据结构的正确状态。例如，在一个链表中，“节点数正确”、“每个节点的前后指针指向正确”等都是不变量。

更新数据时，不变量往往会被暂时破坏，直到更新完成，不变量才能恢复。

以双链表为例：

• 每个节点含有两个指针：一个指向前一个节点，一个指向后一个节点。
• 不变量是：每个节点的前后指针相互对应，保证链表结构正确。
• 删除一个节点时，必须同时修改前一个节点的后指针和后一个节点的前指针，完成后才能保证不变量不被破坏。

具体删除节点N的步骤如下：

a) 找到节点 N。

b) 将节点 N 的前一个节点的后指针指向节点 N 的下一个节点。

c) 将节点 N 的后一个节点的前指针指向节点 N 的前一个节点。

d) 删除节点 N。

如下图示：

可以看到，在步骤 b 和步骤 c 之间，不变量被暂时破坏。此时链表结构是不完整的。

共享数据导致的问题

在多线程环境中，如果一个线程正在删除节点且不变量被破坏，另一个线程恰好访问到此时的不完整结构，就可能导致读取非法数据、跳过节点、甚至链表损坏和程序崩溃。这就是条件竞争（race condition）问题的典型表现。

条件竞争

条件竞争指的是多个线程对共享资源的访问和操作顺序影响程序最终行为的情况。

举个生活中的例子：

你在电影院买电影票，有多个售票窗口同时卖票，大家抢最后几张票。你最终能买到的座位取决于谁先买走了哪些票。

在程序中，某些条件竞争是良性的，例如：

• 两个线程同时向任务队列添加任务，只要保证队列的结构不被破坏，添加顺序不影响整体功能。

但如果条件竞争破坏了不变量，就是恶性的，例如：

• 多线程同时修改链表的连接指针，导致链表结构临时不一致，造成数据损坏和程序崩溃。

C++标准中引入了“数据竞争”（data race）这个术语，指的是多个线程并发访问同一内存位置且至少有一个是写操作且未同步时的情况，数据竞争导致未定义行为，程序结果不可预测。

恶性条件竞争的特点：

• 通常涉及多个数据块的更新，比如修改链表中多个指针。
• 由于修改操作分多步完成，不变量在中间步骤被破坏，容易被其它线程观察到不一致状态。
• 发生概率低，但难以调试和重现，尤其是当系统负载大时，出现概率会增加。
• 在调试模式下可能不出现，因为调试影响执行时序。

避免恶性条件竞争

为了避免条件竞争，尤其是恶性条件竞争，常用方法有：

互斥锁（Mutex）

最常用且简单的方法。通过互斥锁保护共享数据：

• 修改数据前先锁住互斥量，保证修改过程的原子性和不变量完整性。
• 其他线程必须等待锁释放才能访问数据。

例如，C++标准库中的std::mutex，用法示例如下：

#include <mutex>
#include <list>

std::list<int> sharedList;
std::mutex listMutex;

void removeNode(int value) {
    std::lock_guard<std::mutex> lock(listMutex);
    for (auto it = sharedList.begin(); it != sharedList.end(); ++it) {
        if (*it == value) {
            sharedList.erase(it);
            break;
        }
    }
}

这里使用lock_guard自动上锁和解锁，确保删除操作对共享链表的独占访问，防止竞争。

无锁编程（Lock-Free）

设计数据结构和算法，使得操作是不可分割的（原子操作），或者能够容忍并发修改而不破坏不变量。

无锁编程可以提高性能和响应性，但设计和实现难度大，容易出错，需要深入理解内存模型和硬件细节。

软件事务内存（Software Transactional Memory, STM）

将对数据结构的修改封装在事务中：

• 线程先在本地记录操作日志。
• 事务提交时检测冲突，如果发现其它线程也修改了数据，则回滚重试。
• 类似数据库事务机制。

STM是一种活跃的研究领域，C++目前没有标准支持，但有相关技术规范和第三方库。

总结

• 共享数据的修改必须谨慎，否则会破坏数据结构不变量，导致条件竞争。
• 条件竞争分良性和恶性，只有恶性条件竞争才导致严重错误和崩溃。
• 避免恶性条件竞争最简单有效的方法是使用互斥锁保护共享数据。
• 复杂场景可考虑无锁编程或软件事务内存，但设计难度较高。