Как я могу написать структуру без блокировок?
https://stackoverflow.com/questions/92455
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
В моем многопоточном приложении я вижу сильную конкуренцию блокировок в нем, что препятствует хорошей масштабируемости на нескольких ядрах.Я решил использовать программирование без блокировок, чтобы решить эту проблему.
Как я могу написать структуру без блокировок?
Решение
Короткий ответ таков:
Ты не можешь.
Длинный ответ таков:
Если вы задаете этот вопрос, вы, вероятно, знаете недостаточно, чтобы иметь возможность создать структуру без блокировок.Создавать конструкции без замков чрезвычайно сложно, и сделать это могут только специалисты в этой области.Вместо того чтобы писать свой собственный, найдите существующую реализацию.Когда вы найдете его, проверьте, насколько широко он используется, насколько хорошо документирован, хорошо ли доказан, каковы ограничения - даже некоторые структуры без блокировок, опубликованные другими людьми, нарушены.
Если вы не нашли структуру без блокировок, соответствующую структуре, которую вы используете в данный момент, лучше адаптируйте алгоритм так, чтобы вы могли использовать какую-нибудь существующую.
Если вы все еще настаиваете на создании своей собственной структуры без блокировок, обязательно:
- начните с чего-нибудь очень простого
- понимать модель памяти вашей целевой платформы (включая ограничения на переупорядочение чтения / записи, какие операции являются атомарными)
- изучите много информации о проблемах, с которыми другие люди сталкивались при внедрении структур без блокировок
- не просто догадывайтесь, сработает ли это, докажите это
- тщательно протестируйте результат
Больше чтения:
Другие советы
Используйте библиотеку, такую как Многопоточные Строительные блоки Intel, он содержит довольно много структур и алгоритмов без блокировок.Я бы действительно не рекомендовал пытаться писать код без блокировки самостоятельно, он чрезвычайно подвержен ошибкам и его трудно исправить.
Написать потокобезопасный код без блокировки очень сложно;но эта статья от Херба Саттера это поможет вам начать.
Как блунди указывалось, что если все объекты неизменяемы и доступны только для чтения, вам не нужно беспокоиться о блокировке, однако это означает, что вам, возможно, придется часто копировать объекты.Копирование обычно включает в себя malloc, а malloc использует блокировку для синхронизации выделения памяти между потоками, поэтому неизменяемые объекты могут стоить вам меньше, чем вы думаете (сам malloc масштабируется довольно плохо, а malloc медленно;если вы выполняете много malloc в разделе, критичном к производительности, не ожидайте хорошей производительности).
Когда вам нужно обновить только простые переменные (например,32 или 64-битный int или указатели), выполнять просто операции сложения или вычитания над ними или просто менять местами значения двух переменных, большинство платформ предлагают для этого "атомарные операции" (в дальнейшем GCC также предлагает их). Атомарный - это не то же самое, что потокобезопасный.Однако atomic гарантирует, что если один поток, например, записывает 64-битное значение в ячейку памяти, а другой поток считывает из нее, считывающий поток либо получает значение до операции записи, либо после операции записи, но никогда сломанный значение между операцией записи (например,тот, где первые 32 бита уже являются новыми, последние 32 бита все еще являются старым значением!Это может произойти, если вы не используете атомарный доступ к такой переменной).
Однако, если у вас есть структура C с 3 значениями, которые нужно обновить, даже если вы обновляете все три с помощью атомарных операций, это три независимые операции, таким образом, читатель может увидеть структуру с одним значением, которое уже обновляется, а два не обновляются.Здесь вам понадобится блокировка, если вы должны гарантировать, что читатель либо увидит, что все значения в структуре являются либо старыми, либо новыми значениями.
Один из способов улучшить масштабирование замков - это использовать R / W замки.Во многих случаях обновления данных происходят довольно редко (операции записи), но доступ к данным происходит очень часто (чтение данных), подумайте о коллекциях (хэш-таблицах, деревьях).В этом случае R / W блокировки принесут вам огромный прирост производительности, так как многие потоки могут одновременно удерживать блокировку чтения (они не будут блокировать друг друга), и только если одному потоку требуется блокировка записи, все остальные потоки блокируются на время выполнения обновления.
Лучший способ избежать проблем с потоками - не обмениваться никакими данными между потоками.Если каждый поток большую часть времени имеет дело с данными, к которым ни один другой поток не имеет доступа, вам вообще не понадобится блокировка для этих данных (также никаких атомарных операций).Поэтому старайтесь делиться как можно меньшим количеством данных между потоками.Тогда вам нужен только быстрый способ перемещения данных между потоками, если вам действительно это необходимо (ITC, межпоточная коммуникация).В зависимости от вашей операционной системы, платформы и языка программирования (к сожалению, вы не сообщили нам ни того, ни другого) могут существовать различные мощные методы для ITC.
И, наконец, еще один трюк для работы с общими данными, но без какой-либо блокировки, заключается в том, чтобы убедиться, что потоки не обращаются к одним и тем же частям общих данных.Например.если два потока совместно используют массив, но один будет обращаться только к четным, а другой - только к нечетным индексам, вам не нужна блокировка.Или, если оба используют один и тот же блок памяти, и один использует только верхнюю его половину, а другой - только нижнюю, вам не нужна блокировка.Хотя и не сказано, что это приведет к хорошей производительности;особенно на многоядерных процессорах.Операции записи одним потоком этих общих данных (запущенных на одном ядре) могут привести к очистке кэша для другого потока (запущенного на другом ядре), и эти очистки кэша часто являются "бутылочным горлышком" для многопоточных приложений, работающих на современных многоядерных процессорах.
Как сказал классу мой профессор (Нир Шавит из "Искусства многопроцессорного программирования"):Пожалуйста, не надо.Основная причина заключается в тестируемости - вы не можете протестировать код синхронизации.Вы можете запускать симуляции, вы даже можете провести стресс-тест.Но в лучшем случае это грубое приближение.Что вам действительно нужно, так это доказательство математической корректности.И очень немногие способны понять их, не говоря уже о том, чтобы написать.Итак, как говорили другие:используйте существующие библиотеки. Блог Джо Даффи рассматриваются некоторые методы (раздел 28).Первое, что вам следует попробовать, - это разбиение на более мелкие задачи и объединение.
Неизменяемость - это один из подходов, позволяющих избежать блокировки.Видишь Обсуждение Эрика Липперта и реализация таких вещей, как неизменяемые стеки и очереди.
в огне.Ответ Сумы: Морис Херлити's показывает в книге "Искусство многопроцессорного программирования", что на самом деле что угодно может быть записан без блокировок (см. главу 6).iirc, это, по сути, включает в себя разделение задач на элементы узла обработки (например, закрытие функции) и постановку каждой из них в очередь.Потоки будут вычислять состояние, следуя по всем узлам из последнего кэшированного.Очевидно, что в худшем случае это может привести к последовательной производительности, но у него есть важные свойства без блокировки, предотвращающие сценарии, в которых потоки могут быть запланированы на длительные промежутки времени, когда они удерживают блокировки.Herlithy также обеспечивает теоретическую производительность без ожидания, что означает, что один поток не будет вечно ждать, чтобы получить атомарную очередь (это очень сложный код).
Многопоточная очередь / стек на удивление сложны (проверьте Проблема ABA).Другие вещи могут быть очень простыми.Привыкните к блокам while(true) {atomicCAS, пока я не поменял их местами};они невероятно могущественны.Интуиция относительно того, что правильно с CAS, может помочь разработке, хотя вам следует использовать хорошее тестирование и, возможно, более мощные инструменты (возможно ЭСКИЗ, предстоящий Массачусетский технологический институт Кендо, или вращение?) чтобы проверить корректность, если вы можете свести ее к простой структуре.
Пожалуйста, напишите подробнее о вашей проблеме.Трудно дать хороший ответ без подробностей.
Редактировать неизменяемость - это хорошо, но ее применимость ограничена, если я правильно ее понимаю.На самом деле это не устраняет опасности записи после чтения;рассмотрим два потока, выполняющих "mem = newNode(mem)".;они оба могли читать мем, а затем оба его записывали;неверно для классической функции увеличения.Кроме того, это, вероятно, происходит медленно из-за распределения кучи (которое должно быть синхронизировано между потоками).
Неизменяемость имела бы такой эффект.Изменения в объекте приводят к созданию нового объекта.Lisp работает таким образом под прикрытием.
Пункт 13 повестки дня Эффективная Java объясняет эту технику.
Клифф Клик провел несколько крупных исследований по безблокировочным структурам данных с использованием конечных автоматов, а также опубликовал множество реализаций для Java.Вы можете найти его статьи, слайды и реализации в его блоге: http://blogs.azulsystems.com/cliff/
Используйте существующую реализацию, поскольку эта область работы относится к компетенции экспертов в предметной области и докторов наук (если вы хотите, чтобы все было сделано правильно!).
Например, здесь есть библиотека кода:
Большинство алгоритмов или структур без блокировок начинаются с некоторой атомарной операции, т.е.изменение некоторой ячейки памяти, однажды начатое потоком, будет завершено до того, как любой другой поток сможет выполнить ту же операцию.Есть ли такая операция в вашем окружении?
Видишь здесь для канонической статьи на эту тему.
Также попробуйте это статья в Википедии статья для получения дополнительных идей и ссылок.
Основной принцип синхронизации без блокировки заключается в следующем:
всякий раз, когда вы читаете структуру, вы выполняете чтение с помощью теста, чтобы увидеть, была ли структура изменена с тех пор, как вы начали чтение, и повторяйте попытки до тех пор, пока вам не удастся прочитать без появления чего-либо еще и изменения, пока вы это делаете;
всякий раз, когда вы изменяете структуру, вы упорядочиваете свой алгоритм и данные таким образом, чтобы был один атомарный шаг, который, если он будет выполнен, приведет к тому, что все изменения станут видимыми для других потоков, и упорядочиваете вещи так, чтобы ни одно из изменений не было видно, пока этот шаг не будет выполнен.Для этого шага вы используете любой атомарный механизм без блокировки, существующий на вашей платформе (напримерсравнение и установка, привязка к загрузке+условное сохранение и т.д.).На этом шаге вы должны затем проверить, не мутировал ли какой-либо другой поток объект с момента начала операции мутации, зафиксировать, если этого не произошло, и начать все сначала, если это произошло.
В Интернете есть множество примеров конструкций без блокировок;не зная больше о том, что вы реализуете и на какой платформе, трудно быть более конкретным.
Если вы пишете свои собственные структуры данных без блокировки для многоядерного процессора, не забывайте о барьерах памяти!Кроме того, подумайте о том, чтобы изучить Память программных транзакций техники.
Ну, это зависит от типа структуры, но вы должны создать структуру таким образом, чтобы она тщательно и бесшумно обнаруживала и обрабатывала возможные конфликты.
Я сомневаюсь, что вы сможете создать систему, на 100% свободную от блокировок, но опять же, это зависит от того, какую структуру вам нужно построить.
Вам также может потребоваться разделить структуру, чтобы несколько потоков работали с отдельными элементами, а затем позже синхронизировать / рекомбинировать.
Как уже упоминалось, это действительно зависит от того, о каком типе структуры вы говорите.Например, вы можете написать ограниченную очередь без блокировки, но не такую, которая допускает произвольный доступ.
Уменьшите или устраните общее изменяемое состояние.
В Java используйте пакеты java.util.concurrent в JDK 5+ вместо того, чтобы писать свои собственные.Как упоминалось выше, это действительно область для экспертов, и если у вас нет свободного года или двух, создавать свою собственную - не вариант.
Можете ли вы пояснить, что вы подразумеваете под структурой?
Прямо сейчас, я предполагаю, что вы имеете в виду общую архитектуру.Вы можете достичь этого, не разделяя память между процессами, а используя модель актора для ваших процессов.
Взгляните на мой ссылка ConcurrentLinkedHashMap для примера того, как написать структуру данных без блокировки.Она не основана на каких-либо научных работах и не требует многолетних исследований, как предполагают другие.Это просто требует тщательной разработки.
Моя реализация использует ConcurrentHashMap, который представляет собой алгоритм блокировки для каждого сегмента, но он не полагается на эту деталь реализации.Его можно было бы легко заменить реализацией Cliff Click без блокировки.Я позаимствовал идею у Клиффа, но использовал гораздо более явно: моделировать все операции CAS с помощью конечного автомата.Это значительно упрощает модель, так как вы увидите, что у меня есть псевдозахваты через исходные состояния.Другой трюк заключается в том, чтобы позволить себе лениться и принимать решения по мере необходимости.Вы часто будете видеть это, возвращаясь назад или позволяя другим потокам "помогать" в очистке.В моем случае я решил разрешить удалять мертвые узлы из списка, когда они достигают начала, вместо того, чтобы иметь дело со сложностью удаления их из середины списка.Я могу изменить это, но я не полностью доверял своему алгоритму обратного отслеживания и хотел отложить серьезные изменения, такие как переход на 3-узловую блокировку.
Книга "Искусство многопроцессорного программирования" - отличный учебник.Однако в целом я бы рекомендовал избегать конструкций без блокировок в коде приложения.Часто это просто излишество, когда более подходят другие, менее подверженные ошибкам методы.
Если вы видите конфликт блокировок, я бы сначала попытался использовать более детализированные блокировки в ваших структурах данных, а не полностью свободные от блокировок алгоритмы.
Например, в настоящее время я работаю над многопоточным приложением, которое имеет пользовательскую систему обмена сообщениями (список очередей для каждого потока, очередь содержит сообщения для обработки потоком) для передачи информации между потоками.На эту структуру наложена глобальная блокировка.В моем случае мне не так уж нужна скорость, так что на самом деле это не имеет значения.Но если эта блокировка станет проблемой, ее можно было бы заменить отдельными блокировками, например, в каждой очереди.Тогда добавление / удаление элемента в / из конкретной очереди не повлияло бы на другие очереди.По-прежнему существовала бы глобальная блокировка для добавления новой очереди и тому подобного, но это не вызывало бы столько споров.
Даже одна очередь с несколькими производителями / потребителями может быть записана с детализированной блокировкой для каждого элемента вместо глобальной блокировки.Это также может устранить разногласия.
Если вы прочитаете несколько реализаций и статей, касающихся этой темы, вы заметите, что существует следующая общая тема:
1) Объекты общего состояния являются неизменяемыми в стиле lisp / clojure:то есть все операции записи реализуются копированием существующего состояния в новый объект, внесением изменений в новый объект и затем попыткой обновить общее состояние (полученное из выровненного указателя, который может быть обновлен с помощью примитива CAS).Другими словами, вы НИКОГДА НЕ изменяете существующий объект, который может быть прочитан не только текущим потоком.Изменяемость может быть оптимизирована с использованием семантики копирования при записи для больших, сложных объектов, но это еще одно ореховое дерево
2) вы четко указываете, какие допустимые переходы между текущим и следующим состоянием допустимы:Тогда проверка правильности алгоритма становится на порядки проще
3) Обрабатывать отброшенные ссылки в списках указателей опасности для каждого потока.После того как ссылочные объекты станут безопасными, по возможности повторно используйте их
Смотрите другой мой связанный пост, где некоторый код, реализованный с помощью семафоров и мьютексов, (частично) переопределен в стиле без блокировок:Взаимное исключение и семафоры
