我们可以用 2 个或更多无锁容器原子地做一些事情而不锁定两者吗？

Question

我正在寻找 Composable operations - 使用事务内存很容易做到。（感谢 Ami Tavory）

使用锁很容易做到 (mutex/spinlock) - 但它可能导致死锁 - 因此基于锁的算法只能通过手动调整组合。

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

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

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

...

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

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

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

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

迭代器 documentation-link

You may iterate over skip-list set items only under RCU lock. Only in this case the iterator is thread-safe since while RCU is locked any set's item cannot be reclaimed. The requirement of RCU lock during iterating means that deletion of the elements (i.e. erase) is not possible.

::contains(K const &key) - documentation-link

The function applies RCU lock internally.

到::get(K const &key)更新我们得到的元素，我们应该使用锁：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;

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

其他线程看不到第一个容器里没有元素，第二个容器里他还没有出现
其他线程看不到第一个容器中有元素，而第二个容器中已经有相同的元素

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

答案：我们不能通过简单地使用其通常的功能，在没有锁的情况下同时对两个或多个无锁容器进行任何原子操作。

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

另外 "but maybe something with a bunch of extra overhead" 如果您对无锁算法进行了复杂的自定义改进，那么您可以提供一些可组合的，例如，如 Peter Cordes 所指出的 "the two queues know about each other, and the code looking at them is carefully designed"。

Answer 1

TL:DR：正如 Yakk 指出的那样，您的要求没有多大意义。但是由于您只要求一种无需锁定 both 容器的方法，因此您可以执行以下操作。如果这不是您要查找的内容，那么也许这将有助于说明您提出问题的方式存在的问题之一。

一个容器上的multiple-readers / single-writer lock可以轻松实现，并解决观察两个容器的问题。

但是对你锁定的容器的无锁访问是永远不允许的，所以使用无锁容器是没有意义的。

如果在观察无锁容器时在锁定容器上持有读锁，那么在观察无锁容器时，关于锁定容器的任何知识仍然是正确的。

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

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 指出事务内存可以支持 synchronization composability.

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

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

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

我们可以用 2 个或更多无锁容器原子地做一些事情而不锁定两者吗？

Can we do something atomically with 2 or more lock-free containers without locking both?

c++

multithreading

concurrency

lock-free

libcds