c++ - 具有细粒度锁的线程安全链表

Question

在一个程序中，我有一个 M 类:

class M{
    /*
      very big immutable fields
    */
    int status;
};

我需要一个 M 类型对象的链表。

三种类型的线程正在访问列表:

• 生产者:生产对象并将其附加到列表的末尾。所有新生成的对象的状态都为 NEW。 (运算时间 = O(1))
• 消费者:消费列表开头的对象。如果对象的状态=CONSUMER_ID，则对象可以被消费者消费。每个消费者都保留链表中它可以消费的第一个项目，因此消费是(摊销？)O(1)(见下面的注释)。
• 析构函数:当有通知表明对象已被正确使用时删除已使用的对象(操作时间 = O(1))。
• 修饰符:根据状态图更改对象的状态。任何对象的最终状态都是消费者的 ID(每个对象的操作时间 = O(1))。

消费者的数量少于 10 个。生产者的数量可能有几百个。有一个修饰符。

注意:修饰符可能会修改已经消费的对象，因此消费者存储的元素可能会来回移动。对于这个问题，我没有找到更好的解决方案(虽然对象之间的比较是 O(1)，但操作不再摊销 O(1))。

性能非常重要。因此，我想使用原子操作或细粒度锁(每个对象一个)来避免不必要的阻塞。

我的问题是:

1. 首选原子操作，因为它们更轻量。我想我必须使用锁来更新析构线程中的指针，我可以使用原子操作来处理其他线程之间的争用。请让我知道我是否遗漏了什么，并且有一个原因我不能在状态字段上使用原子操作。

2. 我想我不能使用 STL 列表，因为它不支持细粒度锁。但是您会推荐使用 Boost::Intrusive 列表(而不是自己编写)吗？ Here有人提到侵入式数据结构更难实现线程安全？这对细粒度锁来说是正确的吗？

3. 生产者、消费者和析构函数将基于某些事件被异步调用(我打算使用 Boost::asio。但我不知道如何运行修饰符以最小化它与其他线程的争用。选项是:

   • 与生产者异步。
   • 与消费者异步。
   • 使用自己的计时器。

只有在满足某些条件的情况下，任何此类调用才会对列表进行操作。我自己的直觉是，我如何调用修饰符之间没有区别。我错过了什么吗？

我的系统是 Linux/GCC，我使用的是 boost 1.47 以防万一。

类似问题:Thread-safe deletion of a linked list node, using the fine-grained approach

Answer 1

The performance is very important. Therefore, I want to use atomic operations or fine-grained locks (one per object) to avoid unnecessary blocking.

这会增加竞争线程(访问相同数据)在不同内核上同时运行的可能性，从而使性能变差。如果锁太细，线程可能会争用(它们的缓存之间的乒乓数据)并以缓慢的锁步运行而不会阻塞锁，从而导致糟糕的性能。

您希望使用足够粗的锁，以便争用同一数据 block 的线程尽快彼此阻塞。这将迫使调度程序调度非竞争线程，消除破坏性能的缓存乒乓。

您有一个常见的误解，认为阻塞是不好的。事实上，争用是不好的，因为它会将内核减慢到总线速度。阻塞结束争用。阻塞很好，因为它取消了竞争线程的调度，从而允许调度非竞争线程(可以全速并发运行)。