Первый результат в Google для «вектора без блокировки» - это исследовательская статья, написанная в соавторстве с Дамианом Дечевым, Питером Пиркельбауэром и Бьярном Страуструпом, описывающая теоретический вектор без блокировки. Был ли реализован этот или любой другой безблокировочный вектор?
Существует ли реализация вектора без блокировки?
Ответы (2)
MS предоставляет ppl::concurrent_vector, а Intel предоставляет tbb::concurrent_vector. В Windows по крайней мере ppl и tbb являются частью C-Runtime.
person
Unknown1987
schedule
21.02.2012
Concurrent и lock-free — совершенно разные вещи.
- person David Rodríguez - dribeas; 22.02.2012
Вы правы, concurrent и lock-free - это не одно и то же. У меня сложилось впечатление, что реализация concurrent_vector в MS ppl не блокируется. Разве это не так?
- person Unknown1987; 22.02.2012
Я склонен предполагать, что, если не указано иное, никакая библиотека не является безблокировочной, и я не видел ни одной ссылки в кратком обзоре документации, в которой говорилось бы, что ppl::concurrent_vector не имеет блокировки.
- person David Rodríguez - dribeas; 22.02.2012
Я просмотрел реализацию, найденную в concurrent_vector.h, похоже, это смесь заблокированных и свободных от блокировок частей. Интересным моментом является нажатие и выталкивание, когда перераспределение и уплотнение не нужны, выполняются операции без блокировки.
- person Unknown1987; 23.02.2012
Я только что посмотрел, что такое вектор, в википедии.
Я думаю (всего лишь минута или две размышлений, ум), полностью безблокировочная версия немного проблематична.
Рассмотреть возможность; вы создаете массив, получаете к нему доступ как обычно и т. д. Для этого вам не нужна блокировка. Проблема возникает, когда вам нужно изменить размер. Поток, который приходит и обнаруживает это, должен вызывать malloc. Это действительно уникальная операция — другие потоки в этот момент должны блокироваться/раскручиваться. Если они пытались помочь, т.е. сделать malloc сами, у вас может быть много потоков, выдающих malloc. Теперь на практике может оказаться, что количество выполняемых потоков настолько мало, что все в порядке - в этом случае у вас может быть несколько потоков, выполняющих malloc, при этом победитель атомарно активирует новую память, а проигравшие видят это, а затем освобождаются ( )сохраняя их память.
Затем, чтобы выполнить копирование, когда поток обращается к элементу, ну, нам нужно отслеживать все выделенные массивы в списке, и мы обращаемся к ним через список, самый старый во-первых, пока мы не найдем нужный элемент, и если он не находится в самом последнем массиве, мы переместим его, а затем получим к нему доступ.
Затем нам также нужен способ, чтобы поток знал, что он переместил последний элемент, и может освободить этот массив, поэтому нам придется подсчитывать элементы; поэтому у нас есть риск потенциально неограниченных требований к распределению. Более того, структура данных (я сказал список, но это могут быть и другие вещи, хотя они, вероятно, будут не такими хорошими) должна быть атомарной (поскольку, возможно, потоки могут одновременно удалять массив) а атомарный список без блокировок до недавнего времени был вершиной структур данных без блокировок, какими бы сложными они ни были, требующими SMR и сложной реализацией.
(Говорю до недавнего времени - кто-то недавно изобрел безблокировочное красно-черное дерево, все дело, добавляй и удаляй!)
TBH, я не понимаю, зачем кому-то использовать вектор. Почему бы просто не использовать сбалансированное двоичное дерево или хэш?
person
Community
schedule
23.07.2012
std::vector, ответ прост: это невозможно. В зависимости от того, что вам не нужно отstd::vector, это может быть достижимо (я не отрицал, но вы должны четко указать свои требования, а также, если вы запрашиваете без блокировки, я не понять, почему вы принимаете ответ, который выполняет блокировку) - person David Rodríguez - dribeas schedule 22.02.2012resize- и остальные операции в любом случае легко свободны от блокировки. - person ytoledano schedule 26.12.2017