Действительно ли возможно создать ориентированные на многопотоковое исполнение наборы без блокировок?
Это чисто только для вопроса об интересе, любой вид вопросов приветствуются.
Таким образом, действительно ли возможно создать ориентированные на многопотоковое исполнение наборы без каких-либо блокировок? Блокировками я имею в виду любые механизмы синхронизации потока, включая Взаимное исключение, Семафор, и даже Взаимно блокируемый, все они. Действительно ли это возможно на уровне пользователя, не называя системные функции? Хорошо, может быть реализация, не является эффективным, я интересуюсь теоретической возможностью. Если не, что минимальное средство состоит в том, чтобы сделать это?
Править: Почему неизменные наборы не работают.
Это класса Stack с методами Add это возвращает другой Стек.
Теперь вот программа:
Stack stack = new ...;
ThreadedMethod()
{
loop
{
//Do the loop
stack = stack.Add(element);
}
}
это выражение stack = stack.Add(element) не является атомарным, и можно перезаписать новый стек от другого потока.
Спасибо, Andrey
6 ответов
Кажется, даже гуру-разработчики программного обеспечения неверно понимают, что представляет собой блокировка.
Следует различать атомарные операции и блокировки. Атомарные операции, такие как сравнение и замена, выполняют операцию (которая в противном случае потребовала бы двух или более инструкций) как одну бесперебойную инструкцию. Блокировки строятся из атомарных операций, однако они могут привести к тому, что потоки будут заняты ожиданием или спящим, пока блокировка не будет разблокирована.
В большинстве случаев, если вам удастся реализовать параллельный алгоритм с атомарными операциями, не прибегая к блокировке, вы обнаружите, что он будет на несколько порядков быстрее. Вот почему существует такой большой интерес к алгоритмам без ожидания и блокировки.
Было проведено множество исследований по реализации различных структур данных без ожидания. Хотя код имеет тенденцию быть коротким, их может быть очень сложно доказать, что они действительно работают из-за возникающих сложных условий гонки. Отладка - тоже кошмар. Однако была проделана большая работа, и вы можете найти хэш-карты без ожидания / без блокировки, очереди (свободная очередь от блокировки Майкла Скотта), стеки, списки, деревья, список можно продолжать. Если вам повезет, вы также найдете несколько реализаций с открытым исходным кодом.
Просто погуглите "lock-free my-data-structure" и посмотрите, что вы получите.
Для дальнейшего чтения по этой интересной теме начните с Искусство многопроцессорного программирования Мориса Херлихи.
По крайней мере, вам нужны атомарные операции. Существуют алгоритмы без блокировки для одного процессора. Я не уверен насчет нескольких процессоров
Я так не думаю. Проблема в том, что в какой-то момент вам понадобится какой-то примитив взаимного исключения (возможно, на машинном уровне), такой как атомная операция тестирования и установки. В противном случае вы всегда можете разработать условие расы. После того, как у вас есть тест и набор, у вас, по сути, есть замок.
При этом в старом оборудовании, которое не имело никакой поддержки этого в наборе инструкций, вы могли отключить прерывания и, таким образом, предотвратить захват другого «процесса», но эффективно постоянно помещать систему в сериализованный режим и принудительное взаимное исключение на некоторое время.
Это действительно зависит от того, как вы определяете термин (как обсуждали другие комментаторы), но да, это возможно для многих структур данных, по крайней мере, для реализации неблокирующим способом (без использования традиционных взаимно-исключающих блокировок).
Я настоятельно рекомендую, если вас интересует эта тема, прочитать блог Клиффа Клика - Клифф является главным гуру в Azul Systems, которые производят аппаратное обеспечение + пользовательскую JVM для запуска Java-систем на массивных и массивно параллельных (думайте о 1000 ядрах и сотнях гигабайт оперативной памяти) системах, и очевидно, что в таких системах блокировка может быть смертью (дисклеймер: не являюсь сотрудником или клиентом Azul, просто восхищаюсь их работой).
Доктор Клик знаменит тем, что придумал неблокирующую HashTable, которая, по сути, является сложной (но довольно блестящей) машиной состояний, использующей атомарные операции CompareAndSwap.
В блоге есть статья из двух частей, описывающая алгоритм (часть первая, часть вторая), а также доклад, сделанный в Google (слайды, видео) - последний, в частности, является фантастическим введением. Мне потребовалось несколько попыток, чтобы "понять" это - это сложно, давайте признаем это! -- но если вы проявите настойчивость (или если вы умнее меня в первую очередь!), вы найдете это очень полезным.
Да, можно сделать параллелизм без какой-либо поддержки со стороны системы. Вы можете использовать алгоритм Петерсона или более общий алгоритм bakery для эмуляции блокировки.