Можем ли мы что-то сделать атомарно с двумя или более контейнерами без блокировки, не блокируя оба?

я ищу Композиционные операции — это довольно легко сделать используя транзакционную память. (Спасибо Ами Тавори)

И это легко сделать с помощью блокировок (мьютекс / спин-блокировка) — но это может привести к тупикам — поэтому алгоритмы на основе блокировок можно комбинировать только с ручной настройкой.

Алгоритмы без блокировок не имеют проблемы взаимоблокировок, но они не компонуются. Требуется для разработки двух или более контейнеров в виде единой составной структуры данных без блокировки.

Есть ли какой-либо подход, вспомогательная реализация или некоторые алгоритмы без блокировки — к атомарно работать с несколькими безблокировочными контейнерами для обеспечения согласованности?

• Проверить, находится ли товар в обоих контейнерах одновременно
• Переместить элемент из одного контейнера в другой атомарно

…

Или RCU или указатели опасности могут помочь в этом?

Как известно, мы можем использовать контейнеры без блокировок, что сложно реализовать, например, из библиотеки Concurrent Data Structures (CDS): http://libcds.sourceforge.net/doc/cds-api/group__cds__nonintrusive__map.html

И, например, мы можем использовать безблокировочного упорядоченная карта как SkipList CDS-lib

Но даже простой алгоритм без блокировки не блокируется ни для каких случаев:

1. итераторы документация-ссылка

Вы можете перебирать элементы списка пропуска только под замком RCU. Только в
в этом случае итератор является потокобезопасным, поскольку в то время как RCU заблокирован любой
предмет набора не может быть восстановлен. Требование блокировки RCU во время
повторение означает, что удаление элементов (т.е. удаление) не является
возможный.

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;
{
// 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) если мы хотим сохранить атомарность и последовательность:

• что другие потоки не видят, что нет элемента в первом контейнере, и он все еще не появился во втором

• что другие потоки не видят, что есть элемент в первом контейнере, и тот же элемент уже во втором

Можем ли мы что-то сделать атомарно с двумя или более контейнерами без блокировки, не блокируя оба — если мы хотим сохранить атомарность и согласованность?

ОТВЕТ: Мы не можем выполнять атомарные операции с двумя или более контейнерами без блокировки одновременно без блокировок, просто используя его обычные функции.

Только если мы делаем 1 простую операцию, предусмотренную алгоритмом без блокировок в контейнере-API, тогда для 2 контейнеров без блокировок достаточно 1 блокировки, исключая 3 случая, описанных выше, когда даже в контейнерах без блокировки используются блокировки.

Кроме того, «но может быть что-то с кучей дополнительных затрат», если вы сделали сложные пользовательские улучшения алгоритмов без блокировок, то вы можете предоставить некоторые компонуемые, например, «две очереди знают друг о друге, и код, рассматривающий их, тщательно продуманный «, как отметил Питер Кордес.

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