我们可以用两个或更多的无锁容器来做一些原子性的事情吗？

Question

我正在寻找可组合运算 --使用事务性内存相当容易。(感谢阿美·塔沃里)

而且它很容易使用锁(互斥锁/自旋锁)，但它会导致死锁，因此基于锁的算法只能通过手动调优组合。

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

是否有任何方法、辅助实现或一些无锁算法来原子化与多个无锁容器一起工作以保持一致性？

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

..。

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

众所周知，我们可以使用无锁容器，这在它的实现中是很困难的，例如来自并发数据结构库：map.html。

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

但是，即使是简单的无锁算法也不是没有锁的：

1. 迭代器 文件-链接

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

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

该函数在内部应用RCU锁。

1. 对于我们得到的::get(K const &key)和update元素，应该使用：文件-链接

示例：

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();

但是，如果我们使用两个无锁容器而不是一个，如果我们只使用方法wich总是没有锁，或者其中一个没有锁，那么我们可以不同时锁定两个容器吗？

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;

如果我们想保持原子性和一致性，那么我们可以原子地将1元素从map_1移动到map_2 而不同时锁定容器-即map_1.erase(K const &key)和map_2.insert(K const &key, V const &val)：

• 其他线程没有看到第一个容器中没有元素，并且他仍然没有出现在第二个容器中。
• 其他线程看不到第一个容器中有元素，而第二个容器中已经有相同的元素。

如果我们想要保持原子性和一致性，那么如果我们想要保持原子性和一致性，我们可以用两个或更多没有锁的容器原子化地做一些事情吗？

回答：我们不能一次使用两个或多个没有锁的无锁容器执行任何原子操作，只需使用它通常的函数。

只有当我们做了一个简单的操作提供的无锁算法提供的容器-API，那么对于2个无锁容器，它是足够1锁，排除上述3种情况下，即使在无锁容器使用锁。

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

Answer 1

医生:正如牦牛所指出的，你的要求没有多大意义。但是，由于您只要求一种不锁定两个容器的方法，所以这里有一些您可以做的事情。如果这不是你想要的，那么也许这将有助于说明你如何提出这个问题的问题之一。

A 多读取器/单写锁 on one 可轻松实现，并解决了观察两个容器的问题。

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

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

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

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

，我并不是说没有无锁的方法来做，BTW.@Ami指出，事务性内存可以支持同步可组合性。

但是您的规范的主要问题是，不清楚您到底想阻止潜在的观察者观察什么，，因为他们只能以这样或那样的顺序观察两个无锁的数据结构，而不是像@Yakk所指出的那样原子地观察两个数据结构。

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

如果您需要在两个容器之间进行更强的链接，那么它们可能必须设计成一个了解两个容器的单一无锁数据结构。