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

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:

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.

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

The function applies RCU lock internally.

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.

Recommended topics

Hot tags