Можно ли создавать многопоточные коллекции без блокировок?

Question

Это чисто вопрос интереса, любые вопросы приветствуются.

Так можно ли создавать поточно-ориентированные коллекции без каких-либо блокировок? Под блокировками я подразумеваю любые механизмы синхронизации потоков, включая Mutex, Semaphore и даже Interlocked - все они. Возможно ли это на уровне пользователя, без вызова системных функций? Хорошо, может быть, реализация неэффективна, меня интересует теоретическая возможность. Если нет, то каков минимум средств для этого?

РЕДАКТИРОВАТЬ: Почему неизменные коллекции не работают.

Это класс Stack с методами Add, который возвращает другой стек.

Теперь вот программа:

Stack stack = new ...;

ThreadedMethod()
{
   loop
   {
      //Do the loop
      stack = stack.Add(element);
   }
}

это выражение stack = stack.Add(element) не является атомарным, и вы можете перезаписать новый стек из другого потока.

Спасибо, Андрей

Answer 1

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

Необходимо различать атомарные операции и блокировки. Атомарные операции, такие как сравнение и своп, выполняют операцию (которая в противном случае потребовала бы двух или более инструкций) как одну непрерывную инструкцию. Блокировки строятся из атомарных операций, однако они могут привести к тому, что потоки будут заняты или ожидают, пока блокировка не будет разблокирована.

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

Было проведено множество исследований по внедрению различных структур данных без ожидания. В то время как код имеет тенденцию быть коротким, им может быть трудно доказать, что они действительно работают из-за возникающих тонких условий гонки. Отладка тоже кошмар. Однако была проделана большая работа, и вы можете найти хэш-карты без ожидания / без блокировки, очереди (очередь без блокировки Майкла Скотта), стеки, списки, деревья, список можно продолжать. Если вам повезет, вы также найдете несколько реализаций с открытым исходным кодом.

Просто гуглите «free-free-my-data-Structure» без блокировки и посмотрите, что вы получите.

Для дальнейшего чтения по этому интересному предмету начните с Искусство многопроцессорного программирования Мориса Херлихи.

Answer 2

Да, неизменные коллекции! :)

Answer 3

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

Я настоятельно рекомендую, если вам интересна эта тема, прочитать блог Cliff Click - Клифф - главный гуру Azul Systems, который производит оборудование + настраиваемую JVM для запуска Java-системы на массивной и массивно параллельной системе (примерно до 1000 ядер и в сотнях гигабайт области ОЗУ), и, очевидно, в таких системах блокировка может быть смертельной (отказ от ответственности: не сотрудник или клиент Azul, просто поклонник их работы).

Доктор Клик разработал неблокирующую HashTable, которая представляет собой сложный (но довольно блестящий) конечный автомат, использующий атомарные операции CompareAndSwap.

В блоге, состоящем из двух частей, описывается алгоритм ( часть первая , часть вторая ), а также выступление в Google ( слайды , video ) - последнее, в частности, является фантастическим введением. Мне понадобилось несколько раз, чтобы «достать» его - это сложно, давайте посмотрим правде в глаза! - но если вы будете упорствовать (или если вы будете умнее меня!), вы найдете это очень полезным.

Answer 4

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

Answer 5

Я так не думаю. Проблема в том, что в какой-то момент вам понадобится некоторый примитив взаимного исключения (возможно, на уровне машины), такой как атомарная операция тестирования и установки. В противном случае вы всегда можете придумать условия гонки. Если у вас есть тест и набор, у вас, по сути, будет блокировка.

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

Answer 6

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