Дэвид Родригес - dribeas написал в комментарии к StackOverflow, что «Не все коллекции могут быть реализованы без блокировок». Я не уверен, правда ли это, и я не могу найти доказательств в любом случае.
Это утверждение не очень точное, но позвольте мне попытаться перефразировать его немного более формально: для каждого типа коллекции C
существует тип коллекции C
LF без блокировки, который предлагает тот же набор операций, и где каждая операция в C
LF имеет ту же сложность big-O, что и соответствующая операция над C
.
Кстати, я не ожидаю трансформации.
LOCK
инструкцию процессора, а планировщик потока через мьютексы / семафоры / и т.д.Ответы:
Поскольку я сам был несколько смущен, я начну с разъяснения нескольких понятий в этом вопросе.
Коллекция . Я не вижу смысла тратить время на строгое определение того, что означает «сбор», когда мы можем просто спросить, что происходит со структурами данных в целом. Структура данных занимает часть памяти и имеет некоторые операции, которые могут обращаться к этой памяти и которые могут вызываться пользователями . Эти пользователи могут быть разными процессорами или просто разными потоками, нас это не касается. Важно только то, что они могут выполнять операции параллельно.
Без блокировки . Херлихи и Босс говорят, что структура данных не блокируется, когда сбойный пользователь не препятствует дальнейшему использованию структуры данных. Например, представьте, что вы льете воду на процессор, который находится в процессе вставки узла в отсортированный набор. Что ж, если другие процессоры позже попытаются вставить в этот отсортированный набор, они должны преуспеть. ( Редактировать: в соответствии с этим определением, это случай, когда структура данных использует блокировки, тогда она не свободна от блокировки, но это не тот случай, когда структура данных не использует блокировки, то она не блокируется.)
С этим определением, я думаю, что Херлихи и Босс в основном говорят, что ответ - превратить критические регионы в транзакции.
Но вы можете спросить, имеет ли это такую же сложность? Я не уверен, что вопрос имеет смысл. Посмотрим
push(x) { lock(); stack[size++] = x; unlock(); }
. Это операция с постоянным временем? Если вы игнорируете операцию блокировки и, следовательно, других пользователей, вы можете ответить ДА. Если вы не хотите игнорировать других пользователей, то на самом деле нет никакого способа сказать, будет ли push выполняться в постоянное время. Если вы поднимитесь на один уровень вверх и увидите, как стек используется каким-то конкретным алгоритмом, вы можете сказать, что push всегда будет занимать постоянное время (измеряется сейчас с точки зрения того, что происходит с входом вашего параллельного алгоритма). Но это действительно свойство вашего алгоритма, поэтому не имеет смысла говорить, что push - это операция с постоянным временем.Таким образом, если вы игнорируете, сколько пользователь, выполняющий операцию, ожидает других пользователей, то использование транзакций вместо критических областей отвечает на ваш вопрос утвердительно. Если вы не игнорируете время ожидания, вам нужно посмотреть, как используется структура данных.
источник
push
операция, как указано выше, не является операцией с постоянным временем. Для фиксированного числа процессоров и общей реализации,lock
которая гарантирует отсутствие голодания, вышеуказанная операция (в худшем случае для любого данного процессора занимает N_proc * O (1), который наивно можно считать равным O (1) ( число процессоров учитывается в скрытой константе).Я думаю, что «КОЛЛЕКЦИИ» означает «очереди, стеки, связанные списки, деревья, ...»
С http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
Благодаря тщательному проектированию и внедрению можно создавать структуры данных, которые безопасны для одновременного использования без необходимости управления блокировками или потоками блоков. Эти неблокирующие структуры данных могут повысить производительность, допуская дополнительный параллелизм, и повысить надежность, избегая некоторых проблем, вызванных инверсией приоритетов в локальных настройках или сбоями машин и каналов в распределенных системах.
Наилучшим общим введением в наши неблокирующие алгоритмы является документ «Параллельное программирование без блокировок», который в настоящее время находится на стадии представления, который охватывает наши проекты для многословного сравнения и замены, текстовой программной транзакционной памяти и объектной программной транзакционной памяти.
Если «без блокировки» означает «не использовать семафоры, мьютекс, мониторы и т. Д. Операционной системы», то я думаю (но я не эксперт), что каждая коллекция может быть освобождена от блокировки с использованием атомарного чтения-записи-записи. изменить примитивы, которые должны поддерживаться оборудованием.
Исчерпывающую документацию по теме можно найти в Интернете:
http://www.google.it/search?q=lock+free+algorithm+filetype%3Apdf
(... и дальнейшие ссылки в конце каждого документа)
источник