0

For high-performance multi-threading system, is there a deterministic way/methodology to determine what concurrency logic can be done using only compare-and-swap a.k.a. atomic operations, what must use locks, semophones and/or barriers?

My systems always involve a lot of concurrency and multi-threading issue. Some are simple as one can work out if a simple lock is needed quickly; but for some complicated problems, or trials to push performance to extreme, I found that I don't have a consistent deterministic methodology to tell if a problem can be resolved using only CAS. As an example:

  1. Typical producer/consumer model. Concurrent queue can resolve the problem using CAS only.

  2. Producer/consumer model with a lot of updates but conflated consumption. In this case if double-buffering is used, read/write lock must apply; however, if we use triple-buffering, then using CAS is essentially possible.

Roughly speaking, we could say if a piece of logic can be separated into several inter-dependent states, each need only CAS, then such logic can be resolved by only CAS. But applying this in real problems seems much more complicated, and I do feel lack of a good methodology to divided and determine if such logic division is possible.

Please kindly share me your experiences or any methodologies I am not aware of.

4

1 回答 1

0

这是我多年使用原子后的外行经验法则。

  1. 您的数据必须位于同一地点。
  2. 您的数据必须很小。
  3. 你不需要任何花哨的东西。
  4. 你想要细粒度的锁定。
  5. 你需要速度。
  6. 连连看。

同处一地。 要使用原子，必须以原子方式更改的所有数据都必须是连续的。因此，双链表对于原子来说几乎是不可能的，因为您必须同时更新不同节点上的指针。单个链表是微不足道的。

小的。 小意味着与系统允许的最大原子操作一样小。要使用原子更新结构中的 50 个字段，您需要创建新结构，然后以原子方式交换指向它的指针。

你不需要任何花哨的东西。 当以原子方式使用单链表时，您只能从列表的前面添加和删除项目。如果您可以使用哈希表、单链表、跳过列表或数组来做到这一点，则可以使用原子。原子非常适合构建结构，然后以原子方式交换指向该结构的指针。

你想要细粒度的锁定。 例如，使用原子哈希表，您可以在存储桶级别而不是列表级别“锁定”。我想你可以每个桶有一个互斥锁。

速度。 与原子相比，互斥锁真是太慢了。每次调用 malloc 时编写一个锁定互斥锁的内存分配器会很糟糕。大约 3 年前，我对 mutex 与 atomic 进行了基准测试，并得出了 40 倍的减速。

连连看！ 我在原子将是一个彻头彻尾的痛苦和混淆的地方使用互斥锁。我试图将这些情况限制在执行不多的代码上，因此我不会为性能损失买单。

据说所有这些限制我很容易在所有热点中使用原子，并且很少需要回退到互斥锁。

于 2014-05-16T00:55:27.947 回答