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

Question

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

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

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

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

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

消费者数量少于10个.生产者数量可能高达数百个.有一个修饰符.

注意:修饰符可以修改已经消耗的对象,因此存储的消费者项目可以来回移动.我没有找到任何更好的解决方案来解决这个问题(虽然,对象之间的比较是O(1),操作不再分摊O(1)).

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

我的问题是:

原子操作是首选,因为它们更轻.我想我必须使用锁来更新析构函数线程中的指针,我可以使用原子操作来处理其他线程之间的争用.如果我遗漏了某些内容并且有理由不能在状态字段上使用原子操作,请告诉我.
我想我不能使用STL列表,因为它不支持细粒度锁.但是你会建议使用Boost :: Intrusive列表(而不是自己编写)吗？这里提到侵入式数据结构更难以实现线程安全吗？这对于细粒度锁是否正确？
生成器,使用者和析构函数将根据某些事件异步调用(我计划使用Boost :: asio.但我不知道如何运行修饰符以最小化与其他线程的争用.选项包括:
- 来自生产者的异步.
- 来自消费者的异步.
- 使用自己的计时器.

只有在某些条件成立时,任何此类呼叫才会在列表上运行.我自己的直觉是,我如何调用修饰符之间没有区别.我错过了什么吗？

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

Answer 1

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

这会通过增加竞争(访问相同数据)的线程在不同核心上同时运行的可能性而使性能变差.如果锁太精细,线程可能会争用(在缓存之间打乒乓数据)并以慢速锁定步骤运行而不会阻塞锁,从而导致可怕的性能.

您希望使用足够粗的锁,以便尽快将相互争用的线程相互阻塞.这将迫使调度程序安排非竞争线程,从而消除破坏性能的缓存ping-ponging.

你有一个普遍的误解,认为阻塞很糟糕.事实上,争用是不好的,因为它会降低内核的速度.阻止结束争用.阻塞是好的,因为它取消调度竞争线程,允许调度非竞争线程(可以全速并发运行).