我们可以用两个或更多的无锁的容器进行原子操作而不锁定两个？ [英] Can we do something atomically with 2 or more lock-free containers without locking both?

问题描述

我在寻找 可组合操作 相当容易做到使用事务内存。 （感谢Ami Tavory）

它很容易使用锁（互斥/自旋锁） - 但它可能导致死锁 - 所以基于锁的算法只能与手动调整。

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

有任何方法，辅助实现或一些无锁算法 - 使用几个无锁容器来保持一致性？

• 要检查项目是否在两个容器中一次


• 将元素从一个容器移动到另一个原子

...

或者可以使用RCU或危险指针来帮助这样做吗？

可以使用无锁的容器，这是它的实现困难，例如，从并行数据结构（CDS）库： http://libcds.sourceforge.net/doc/cds-api/group__cds__nonintrusive__map.html

例如，我们可以使用无锁有序地图如 SkipList CDS-lib中

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

1. 迭代器 文档链接

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

< ol start =2>

:: contains（K const& key） - 文件链接

此函数在内部应用RCU锁。

3. 对 :: get（K const& key） 和更新元素，我们使用锁：文档，链接

示例：

  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; 
 {
 //锁RCU 
 skip_list :: rcu_lock lock; 
 pVal = theList.get（5）; 
 if（pVal）{
 //处理pVal 
 // ... 
} 
} 
 //您可以在RCU后手动释放pVal锁定部分
 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中原子地移动1个元素 


$ b <到 map_2 没有锁定两个容器 - 即的 map_1.erase（K const& key） 和 map_2.insert（K常量和放大器;键，V&const的放大器; VAL） 如果我们想保持原子性和一致性：

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




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

我们可以用两个或更多的无锁容器进行原子操作，我们要保持原子性和一致性？

我们不能同时使用两个或多个无锁容器进行任何原子操作没有锁通过使用简单的其通常的功能。

只有当我们做简单的操作时，在container-API中提供的无锁算法，然后对于2个无锁的容器，就足够1个锁，排除上述3个当即使是在无锁的容器使用锁。

也，但或许真的有一堆额外的开销，如果你做的无锁的算法复杂的自定义改进，那么你可以提供一些可组合的，例如，两个队列彼此了解，并且看看它们的代码是精心设计的，Peter Cordes指出。

解决方案

TL：DR：Yakk指出，你所要求的不是很有意义。但由于您只需要一种方法即可在不锁定两个容器的情况下进行操作，因此您可以执行此操作。如果这不是你要找的，那么也许这将有助于说明你提出这个问题的一个问题。

---

多读者/单作者锁

$

但是，那么不允许无锁访问您锁定的容器，因此不允许使用无锁的容器。

如果您在锁定上持有读锁定容器，而你观察到无锁的容器，那么无论你学到了什么锁定容器仍然是真的，而你观察到无锁的容器。

---

对锁定容器采取写锁定会阻止任何读取器在删除元素时观察锁定的数据结构。所以你可以使用一个算法：

  write_lock（A）; //从A 
中排除读者tmp = pop（A）; 
 push（B，tmp）; 
 write_unlock（A） //允许读者在两个操作完成后再次观察A 
  

您可以通过临时在两个容器中包含元素来保存复制，

  write_lock（A）;而不是暂时不在两者中（复制到临时）。 //从A 
中排除读者B.add（A [i]）; //直接从A拷贝到B 
 A.remove（i）; 
 write_unlock（A） //允许读者在两个操作完成后再次观察A 
  

---

$ b b

我没有声称没有任何无锁的方式可以这样做，BTW。 @Ami指出事务内存可以支持同步可组合性。

但是您的规范的主要问题是不清楚您要阻止潜在观察者观察的内容，因为它们只能观察两个无锁数据

如果你控制观察者观察的顺序，以及作者做什么样的命令，这可能是你需要的。

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

I'm looking for Composable operations - it fairly easily to do using transactional memory. (Thanks to Ami Tavory)

And it easily to do using locks (mutex/spinlock) - but it can lead to deadlocks - so lock-based algorithms composable only with manual tuning.

Lock-free algorithms do not have the problem of deadlocks, but it is not composable. Required to designed 2 or more containers as a single composed lock-free data structure.

Is there any approach, helper-implementation or some lock-free algorithms - to atomically work with several lock-free containers to maintain consistency?

• To check if if an item is in both containers at once
• To move element from one container to another atomically

...

Or can RCU or hazard-pointers help to do this?

As known, we can use lock-free containers, which is difficult in its implementations, for example from Concurrent Data Structures (CDS) library: http://libcds.sourceforge.net/doc/cds-api/group__cds__nonintrusive__map.html

And for example we can use lock-free ordered-map like SkipList CDS-lib

But even simple lock-free algorithm is not lock-free for any cases:

1. Iterators 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.

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

The function applies RCU lock internally.

3. To ::get(K const &key) and update element which we got, we should use lock: documentation-link

Example:

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

But if we use 2 lock-free containers instead of 1, and if we use only methods wich is always lock-free, or one of it lock-free, then can we do it without locking both containers?

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;

Can we atomically move 1 element from map_1 to map_2 without locking both containers - i.e. map_1.erase(K const &key) and map_2.insert(K const &key, V const &val) if we want to maintain atomicity and consistency:

• that other threads do not see that there is no element in the first container, and he still had not appear in the second

• that other threads do not see that there is element in the first container, and the same element already in the second

Can we do something atomically with 2 or more lock-free containers without locking both - if we want to maintain atomicity and consistency?

ANSWER: We can't do any atomically operations with two or more lock-free containers at once without locks by using simply its usual functions.

Only if we do 1 simply operation provided by lock-free algorithm in containers-API then for 2 lock-free containers it is enough 1 lock, exclude 3 cases described above when even in lock-free containers uses locks.

Also "but maybe something with a bunch of extra overhead" if you made complicated custom improvements of lock-free algorithms then you can provide some composable, for example, as "the two queues know about each other, and the code looking at them is carefully designed" as Peter Cordes noted.

解决方案

TL:DR: what you're asking doesn't make a lot of sense, as Yakk points out. But since you only asked for a way to do it without locking both containers, here's something you can do. If this isn't what you're looking for, then maybe this will help illustrate one of the problems with how you've posed the question.

---

A multiple-readers / single-writer lock on one of the containers would allow it easily, and solve the problem of observing both containers.

But then lock-free access to the container you lock is never allowed, so it's pointless to use a lock-free container.

If you hold a read-lock on the locking container while you observe the lock-free container, then whatever you learned about the locking container is still true while you observe the lock-free container.

---

Taking a write-lock on the locking container stops any readers from observing the locked data structure while you remove an element. So you'd use an algorithm like:

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

Moving a node in the other direction works the same way: do both the remove and add while holding a write-lock on the locking container.

You can save copying by temporarily having the element in both containers, instead of temporarily in neither (copied to a temporary).

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

---

I'm not claiming that there is no lock-free way to do this, BTW. @Ami points out that transactional memory can support synchronization composability.

But the major problem with your specification is that it's not clear what exactly you're trying to stop potential observers from observing, since they can only observe two lock-free data structures in one order or another, not atomically, as @Yakk points out.

If you control which order the observers do their observing, and which order the writers do their writing, that might be all you need.

If you need stronger linking between two containers, they probably have to be designed as a single lock-free data structure that knows about both containers.

这篇关于我们可以用两个或更多的无锁的容器进行原子操作而不锁定两个？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！