Упрощает ли многопоточное программирование без блокировок что-либо?
Я только немного прочитал об этой теме, но, похоже, единственное преимущество - это обойти конфликтные ситуации, но это не окажет какого-либо существенного влияния на проблему взаимоблокировки, так как код, свободный от блокировки, настолько мал и фундаментален (fifos, lifos, hash) что никогда не было проблемы тупика.
Так что все дело в производительности - это правильно?
7 ответов
Программирование без блокировок (насколько я вижу) всегда связано с производительностью, в противном случае использование блокировки в большинстве случаев намного проще и, следовательно, предпочтительнее.
Однако обратите внимание, что с программированием без блокировок вы можете в конечном итоге обменять взаимоблокировку на live-lock, которую намного сложнее диагностировать, поскольку никакие известные мне инструменты не предназначены для ее диагностики (хотя я могу ошибаться там).
Я бы сказал, только идти по пути без блокировки, если вам нужно; то есть, у вас есть сценарий, когда у вас есть жесткая блокировка, которая ухудшает вашу производительность. (Если это не сломано, не исправляйте это).
Пара вопросов.
Скоро мы столкнемся с настольными системами с 64, 128 и 256 ядрами. Парализм в этой области отличается от нашего нынешнего опыта использования 2, 4, 8 ядер; алгоритмы, которые успешно работают в таких небольших системах, будут работать медленнее в высокопараллельных системах из-за конфликта.
В этом смысле важно отсутствие блокировок, поскольку это сильно способствует решению проблемы масштабируемости.
Есть также некоторые очень специфические области, где блокировка без ограничений чрезвычайно удобна, например ядро Windows, где существуют режимы выполнения, где запрещены спящие состояния любого типа (например, ожидания), что, очевидно, очень ограничивает в отношении структур данных, но где без блокировки обеспечивает хорошее решение.
Кроме того, структуры данных без блокировки часто не имеют режимов сбоя; на самом деле они не могут потерпеть неудачу, когда структуры данных на основе блокировок, конечно, могут не получить свои блокировки. Отсутствие необходимости беспокоиться о сбоях упрощает код.
Я написал библиотеку структур данных без блокировок, которую скоро опубликую. Я думаю, что если разработчик может получить хорошо зарекомендовавший себя API, он может просто использовать его - не имеет значения, без блокировки он или нет, ему не нужно беспокоиться о сложности базовой реализации - и это путь.
Это касается производительности - но также и способности принимать многопоточные загрузки:
блокировки предоставляют монопольный доступ к части кода: в то время как поток имеет блокировку, другие потоки вращаются (зацикливаясь при попытке получить блокировку) или блокируются, спят до тех пор, пока блокировка не будет снята (что обычно происходит, если вращение продолжается слишком долго);
атомарные операции предоставляют монопольный доступ к ресурсу (обычно переменной размера слова или указателю) с помощью непрерывных внутренних инструкций процессора.
Поскольку блокирует выполнение BLOCK других потоков, программа замедляется. Поскольку атомарные операции выполняются последовательно (одна за другой), блокировка отсутствует *.
(*) до тех пор, пока количество одновременных процессоров, пытающихся получить доступ к одному и тому же ресурсу, не создает узкого места - но у нас пока недостаточно ядер ЦП, чтобы рассматривать это как проблему.
Я работал над этим вопросом, чтобы написать хранилище Key-Value без ожидания (без блокировки без состояний ожидания) для сервера, на котором я работаю.
Такие библиотеки, как Tokyo Cabinet (даже TC-FIXED, простой массив), используют блокировки для сохранения целостности базы данных:
"Пока поток записи работает с базой данных, другие потоки чтения и записи блокируются" (документация Токийского кабинета министров)
Результаты теста без параллелизма (однопотоковый тест):
SQLite time: 56.4 ms (a B-tree)
TC time: 10.7 ms (a hash table)
TC-FIXED time: 1.3 ms (an array)
G-WAN KV time: 0.4 ms (something new which works, but I am not sure a name is needed)
При одновременном выполнении (запись и чтение нескольких потоков в одной и той же базе данных) только G-WAN KV выдержал один и тот же тест, поскольку (в отличие от других) он никогда не блокируется.
Так что, да, этот магазин KV облегчает его использование разработчиками, поскольку им не нужно заботиться о проблемах с многопоточностью. Однако заставить это работать не было тривиальным.
Для упреждающих потоков потоки, приостановленные при удержании блокировки, могут блокировать потоки, которые в противном случае могли бы продвигаться вперед. Без блокировки такой проблемы не возникает, поскольку по определению Херлихи какой-то другой поток всегда может продвигаться вперед.
Для не вытесняющих потоков это не имеет большого значения, поскольку даже решения на основе спин-блокировки по определению Херлихи не имеют блокировки.
Это также о масштабируемости. Чтобы получить прирост производительности в наши дни, вам придется распараллеливать проблемы, над которыми вы работаете, чтобы вы могли масштабировать их по нескольким ядрам - чем больше, тем лучше.
Традиционный способ сделать это - заблокировать структуры данных, которые требуют параллельного доступа, но чем больше потоков вы можете выполнять действительно параллельно, тем больше становится узкое место.
Так что да, речь идет о производительности...
Мне кажется, я видел статью, которая математически доказала, что любой алгоритм может быть написан без ожидания (что в основном означает, что вы можете быть уверены в том, что каждый поток всегда продвигается к своей цели). Это означает, что он может быть применен к любому крупномасштабному приложению (в конце концов, программа - это просто алгоритм со многими, многими параметрами), и потому что ожидание без ошибок гарантирует, что в нем не будет никакой мертвой / live-блокировки (до тех пор, пока она не ' У него нет ошибок, которые мешают ему быть действительно свободным от ожидания), это упрощает эту сторону программы. С другой стороны, математическое доказательство далеко от фактической реализации самого кода (AFAIK, даже нет полностью связанного списка без блокировки, который может работать на ПК, я видел те, которые охватывают большинство частей, но они обычно либо не могут обрабатывать некоторые общие функции, либо некоторые функции требуют, чтобы структура была заблокирована).
Кроме того, я обнаружил еще одно доказательство того, что любой алгоритм без блокировок может считаться без ожидания благодаря законам вероятности и различным другим факторам.
Масштабируемость является действительно важной проблемой в эффективном программировании мульти / маникюра. Наибольшим ограничивающим фактором на самом деле является секция кода, которая должна выполняться последовательно (см . Закон Амдала). Тем не менее, споры о замках также очень проблематичны.
Алгоритм без блокировок решает проблему масштабируемости, которую имеет устаревшая блокировка. Таким образом, я могу сказать, что блокировка свободна в основном для повышения производительности, а не для снижения вероятности тупика.
Однако, имейте в виду, что в современной архитектуре x86 написание общего алгоритма без блокировки невозможно. Это потому, что мы не можем атомарно обмениваться произвольным размером данных в текущем x86 (и также верно для других архитектур, за исключением ROCK от Sun). Таким образом, современные структуры данных без блокировок весьма ограничены и очень специализированы для конкретных целей.
Я думаю, что текущие структуры данных без блокировки больше не будут использоваться через десятилетие. Я настоятельно ожидаю, что аппаратный механизм без блокировок (да, это транзакционная память, TM) будет реализован в течение десятилетия. Если реализован какой-либо вид TM, хотя он не может полностью решить проблемы блокировок, многие проблемы (включая инверсию приоритетов и взаимоблокировки) будут устранены. Однако внедрить TM в аппаратные средства все еще очень сложно, а в x86 был предложен только черновик.
Это все еще слишком долго: 2 предложения.
Структура данных без блокировок не является панацеей для многопоточного программирования на основе блокировок (даже TM это не так. Если вам серьезно нужна масштабируемость и возникают проблемы с конфликтами блокировок, рассмотрите структуру данных без блокировок.