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

Question

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

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

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

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

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

...

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

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

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

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

1. 迭代器 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.

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

The function applies RCU lock internally.

1. 要::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)和 map_2.insert(K const &key, V const &val)如果我们想保持原子性和一致性:

• 其他线程看不到第一个容器里没有元素，而他在第二个容器里还没有出现

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

如果我们想保持原子性和一致性，我们能否在不锁定两个或多个无锁容器的情况下以原子方式执行某些操作？

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

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

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

Answer 1

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

---

A 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 指出的那样。

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

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