C ++ потокобезопасный двусвязный список

Question

Мне нужна описанная выше структура данных для приложения, которое я пишу.Я задавался вопросом, есть ли библиотека, которая уже реализует это, или я должен написать это сам?

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

Answer 1

Может быть, но я думаю, что это был один из уроков, полученных на ранних этапах Java - синхронность данных обычно не на уровне функции-члена контейнера, а на один шаг выше.Вместо этого вы должны использовать объекты синхронизации, прежде чем обращаться к не поточнобезопасному списку.

Обратите внимание:

ThreadSafeQueue tsq;
tsq.push_back(...); // add lots of data

...

// Find the first element that returns true for search_criteria(elem);
auto iter = tsq.find_if(search_criteria); 
// (1)                                  
if(iter != tsq.end()) // (2)
{
    tsq.erase(iter);
}

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

Queue q;
q.push_back(...); // add lots of data

...

// Create some lock around a pre-existing mutex.
Lock lock(q_mutex);
// Find the first element that returns true for search_criteria(elem);
auto iter = q.find_if(search_criteria); 

if(iter != q.end())
{
    q.erase(iter);
}
// lock unlocks as it goes out of scope.

Здесь, поскольку блокировка имеет большую степень детализации, можно обеспечить согласованность всего написанного алгоритма.

Answer 2

Ссылка на связанное исследование: Возможен ли двухсвязный список без блокировки (ожидания)?

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

Примечание: хотя интерфейс и характеристики производительности выглядят как двойной связанный список, внутренне эти структуры очень сложны, основаны на хеш-таблицах или других структурах.Нет ничего, что было бы двойным внутренним списком и в то же время было бы заблокировано.Я не помню, чтобы видел доказательства, но я думаю, что это невозможно.

---

Исходя из вашей дополнительной информации, я думаю, что вам вообще не нужен двойной связанный список.Вы можете использовать единый связанный список Windows API вместо .Для добавления используйте InterlockedPushEntrySList, для удаления для обработки используйте InterlockedPopEntrySList.

Answer 3

Существует множество работ по написанию очередей без блокировок, использующих встроенные функции компилятора / компилятора для выполнения атомарных операций, но действительно трудно заставить их работать.

Поэтому, если вы можете использовать блокировки, возможно, используйте что-то вроде этого: Параллельная очередь FIFO с ускорением

Answer 4

будет ли http://www.boost.org/doc/libs/1_41_0/doc/html/boost/interprocess/message_queue.html работать?