1

我正在寻找可组合操作- 使用事务内存相当容易。（感谢阿米·塔沃里）

使用锁（互斥锁/自旋锁）很容易做到——但它会导致死锁——因此基于锁的算法只能通过手动调整来组合。

无锁算法不存在死锁问题，但它不可组合。需要将 2 个或更多容器设计为单个组合的无锁数据结构。

是否有任何方法、辅助实现或一些无锁算法 - 以原子方式使用多个无锁容器以保持一致性？

  • 检查一个项目是否同时在两个容器中
  • 以原子方式将元素从一个容器移动到另一个容器

...

或者 RCU 或危险指针可以帮助做到这一点吗？

众所周知，我们可以使用无锁容器，这在其实现中很困难，例如来自并发数据结构 (CDS) 库： http: //libcds.sourceforge.net/doc/cds-api/group__cds__nonintrusive__map.html

例如，我们可以使用像SkipList CDS-lib这样的无锁有序映射

但即使是简单的无锁算法在任何情况下都不是无锁的：

  1. 迭代器 文档链接

您只能在 RCU lock 下迭代跳过列表集项目。只有在这种情况下，迭代器是线程安全的，因为当 RCU 被锁定时，任何集合的项目都不能被回收。迭代期间对 RCU 锁定的要求意味着元素的删除（即擦除）是不可能的。

  1. ::contains(K const &key)-文档链接

该函数在内部应用 RCU 锁。

  1. 要::get(K const &key)更新我们得到的元素，我们应该使用 lock：documentation-link

例子：

typedef cds::container::SkipListMap< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > skip_list;
skip_list theList;
// ...
typename skip_list::raw_ptr pVal;
{
    // Lock RCU
    skip_list::rcu_lock lock;
    pVal = theList.get( 5 );
    if ( pVal ) {
        // Deal with pVal
        //...
    }
}
// You can manually release pVal after RCU-locked section
pVal.release();

但是如果我们使用 2 个无锁容器而不是 1 个，并且如果我们只使用总是无锁的方法，或者其中一个无锁的方法，那么我们可以在不锁定两个容器的情况下做到这一点吗？

typedef cds::urcu::gc< cds::urcu::general_buffered<> >  rcu_gpb;
cds::container::SkipListMap< rcu_gpb, int, int > map_1;
cds::container::SkipListMap< rcu_gpb, int, int > map_2;

我们可以map_1在map_2 不锁定两个容器的情况下原子地移动 1 个元素- 即map_1.erase(K const &key)，map_2.insert(K const &key, V const &val)如果我们想保持原子性和一致性：

  • 其他线程没有看到第一个容器中没有元素，他仍然没有出现在第二个容器中

  • 其他线程看不到第一个容器中有元素，而第二个容器中已经存在相同的元素

如果我们想保持原子性和一致性，我们可以用两个或多个无锁容器原子地做一些事情而不锁定两者吗？

回答：我们不能通过简单地使用它的常用函数来一次对两个或多个无锁容器进行任何原子操作而无需锁。

仅当我们在容器 API 中执行无锁算法提供的 1 次简单操作时，对于 2 个无锁容器来说，1 个锁就足够了，排除上述 3 种情况，即使在无锁容器中也使用锁。

如果您对无锁算法进行了复杂的自定义改进，那么“但可能会有一些额外的开销”，那么您可以提供一些可组合的，例如，“两个队列彼此了解，并且查看它们的代码是精心设计”，正如 Peter Cordes 所说。

4

1 回答 1

2

TL:DR: 正如 Yakk 所指出的，你所问的没有多大意义。但是，由于您只要求一种不锁定两个容器的方法，因此您可以这样做。如果这不是您要寻找的，那么也许这将有助于说明您如何提出问题的问题之一。

一个容器上的多读/单写锁可以轻松实现，并解决观察两个容器的问题。

但是，永远不允许对您锁定的容器进行无锁访问，因此使用无锁容器是没有意义的。

如果您在观察无锁容器时对锁定容器持有读锁，那么当您观察无锁容器时，您对锁定容器的了解仍然是正确的。

对锁定容器进行写锁定会阻止任何读者在删除元素时观察锁定的数据结构。所以你会使用这样的算法：

write_lock(A);  // exclude readers from A
tmp = pop(A);
push(B, tmp);
write_unlock(A); // allow readers to observe A again, after both ops are done

向另一个方向移动节点的工作方式相同：在锁定容器上持有写锁的同时执行删除和添加。

您可以通过暂时将元素放在两个容器中来保存复制，而不是暂时在两个容器中（复制到临时）。

write_lock(A);  // exclude readers from A
B.add(A[i]);    // copy directly from A to B
A.remove(i);
write_unlock(A); // allow readers to observe A again, after both ops are done

我并不是说没有无锁的方法可以做到这一点，顺便说一句。@Ami 指出事务内存可以支持同步可组合性。

但是您的规范的主要问题是，不清楚您究竟试图阻止潜在观察者观察什么，因为他们只能以一种或另一种顺序观察两个无锁数据结构，而不是原子地，正如@Yakk 指出的那样.

如果你控制观察者的观察顺序，以及作者写作的顺序，这可能就是你所需要的。

如果您需要在两个容器之间建立更牢固的链接，则可能必须将它们设计为了解两个容器的单个无锁数据结构。

于 2016-08-11T16:50:13.993 回答