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

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

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

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

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

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

...

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

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

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

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

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

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

  1. ::contains(K const &key) - документация-ссылка

Функция применяет блокировку RCU внутри.

  1. к ::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 случая, описанных выше, когда даже в контейнерах без блокировки используются блокировки.

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

Источник

1 ответ

Решение

TL:DR: то, что вы спрашиваете, не имеет большого смысла, как отмечает Якк. Но так как вы только попросили способ сделать это без блокировки обоих контейнеров, вот что вы можете сделать. Если это не то, что вы ищете, то, возможно, это поможет проиллюстрировать одну из проблем с тем, как вы задали вопрос.

Блокировка нескольких считывателей / одного записывающего устройства на одном из контейнеров позволила бы это легко и разрешила бы проблему наблюдения обоих контейнеров.

Но тогда доступ без блокировки к блокируемому контейнеру никогда не будет разрешен, поэтому бессмысленно использовать контейнер без блокировки.

Если вы удерживаете блокировку чтения на блокирующем контейнере, когда наблюдаете контейнер без блокировки, то все, что вы узнали о блокирующем контейнере, остается верным, пока вы наблюдаете контейнер без блокировки.

Взятие блокировки записи в блокирующем контейнере мешает всем читателям наблюдать за заблокированной структурой данных, пока вы удаляете элемент. Таким образом, вы бы использовали алгоритм, как:

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 отмечает, что транзакционная память может поддерживать синхронизируемость.

Но основная проблема с вашей спецификацией заключается в том, что неясно, что именно вы пытаетесь помешать потенциальным наблюдателям наблюдать, поскольку они могут наблюдать только две структуры данных без блокировки в одном или другом порядке, а не атомарно, как указывает @Yakk,

Если вы контролируете, какой порядок выполняют наблюдатели, и какой порядок пишут авторы, это может быть все, что вам нужно.

Если вам нужна более сильная связь между двумя контейнерами, они, вероятно, должны быть спроектированы как единая структура данных без блокировки, которая знает об обоих контейнерах.

Источник
Другие вопросы по тегам