В моем многопоточном приложении, и я вижу в нем сильный конфликт, предотвращая хорошую масштабируемость в нескольких ядрах. Я решил использовать программирование с блокировкой для решения этой проблемы.
Как я могу написать структуру, свободную от блокировки?
Короткий ответ:
Вы не можете.
Длинный ответ:
Если вы задаете этот вопрос, вы, вероятно, не знаете достаточно, чтобы создать свободную от блокировки структуру. Создание незакрепленных конструкций чрезвычайно сложно, и только специалисты в этой области могут это сделать. Вместо того, чтобы писать свои собственные, выполните поиск существующей реализации. Когда вы его найдете, проверьте, насколько широко он используется, насколько хорошо он задокументирован, если он хорошо доказан, каковы ограничения - даже некоторая свободная от блокировки структура, опубликованная другими людьми, нарушена.
Если вы не найдете структуру, свободную от блокировки, соответствующую структуре, которую вы сейчас используете, скорее скопируйте алгоритм так, чтобы вы могли использовать какой-то существующий.
Если вы все еще настаиваете на создании своей собственной свободной структуры блокировки, убедитесь, что:
Дополнительная информация:
Используйте библиотеку, такую как Intel Threading Building Blocks, она содержит довольно много незакрепленных структур и алгоритмов. Я действительно не рекомендовал бы писать код без блокировки самостоятельно, это чрезвычайно склонно к ошибкам и труднодоступно.
Написание потокобезопасного кода, свободного от блокировки, сложно; но эта статья из Herb Sutter поможет вам начать работу.
Как было указано, если все объекты неизменяемы, только для чтения, вам не нужно беспокоиться о блокировке, однако это означает, что вам, возможно, придется много копировать объекты. Копирование обычно включает в себя malloc, а malloc использует блокировку для синхронизации распределений памяти по потокам, поэтому неизменяемые объекты могут купить вас меньше, чем вы думаете (сам malloc масштабируется довольно плохо, а malloc - медленный; если вы делаете много malloc в критическом для производительности разделе, не ожидайте хорошей производительности).
Когда вам нужно только обновлять простые переменные (например, 32 или 64-битные int или указатели), выполнять просто операции сложения или вычитания на них или просто менять значения двух переменных, большинство платформ предлагают для этого "атомные операции" (далее GCC предлагает их также). Atomic - это не то же самое, что потокобезопасное. Тем не менее, атомарная уверенность в том, что если один поток записывает 64-битное значение в ячейку памяти, например, и другой поток считывает из него, считывание либо получает значение перед операцией записи, либо после операции записи, но никогда не сломанное значение в промежутке между операцией записи (например, когда первые 32 бит уже являются новыми, последние 32 бит по-прежнему являются старым значением! Это может произойти, если вы не используете атомный доступ для такой переменной).
Однако, если у вас есть C-структура с 3 значениями, которые хотят обновиться, даже если вы обновите все три с помощью атомных операций, это три независимые операции, поэтому читатель может увидеть структуру с одним значением, которое уже обновляется, и два не обновляются. Здесь вам понадобится блокировка, если вы убедитесь, читатель либо видит, что все значения в структуре являются либо старыми, либо новыми значениями.
Один из способов сделать блокировки масштабируется намного лучше, используя блокировки R/W. Во многих случаях обновления данных довольно редки (операции записи), но доступ к данным очень часто (чтение данных), просмотр коллекций (хеш-таблицы, деревья). В этом случае блокировки R/W купят вам огромное увеличение производительности, так как многие потоки могут одновременно удерживать блокировку чтения (они не будут блокировать друг друга), и только если один поток хочет блокировку записи, все остальные потоки блокируются на время обновления.
Лучший способ избежать проблем с потоками - не передавать какие-либо данные по потокам. Если каждый поток обрабатывает большую часть времени с данными, к которым ни один другой поток не имеет доступа, вам вообще не понадобится блокировка для этих данных (также нет атомных операций). Поэтому старайтесь делиться как можно меньше данных между потоками. Тогда вам нужен только быстрый способ перемещения данных между потоками, если вам действительно нужно (ITC, Inter Thread Communication). В зависимости от вашей операционной системы, платформы и языка программирования (к сожалению, вы не сказали нам ни об этом) могут существовать различные мощные методы для ИТЦ.
И, наконец, еще один трюк для работы с общими данными, но без блокировки - это убедиться, что потоки не имеют доступа к тем же частям общих данных. Например. если два потока совместно используют массив, но один будет доступным только, а другой - только нечетные индексы, вам не нужно блокировать. Или если оба имеют один и тот же блок памяти, а один использует только верхнюю половину, другой - только нижний, вам не нужно блокировки. Хотя он не сказал, что это приведет к хорошей работе; особенно не для многоядерных процессоров. Запись операций одного потока на эти общие данные (с одним ядром) может привести к тому, что кэш будет очищен для другого потока (работает на другом ядре), и эти кеширующие потоки часто являются шеей бутылки для многопоточных приложений, работающих на современных многоядерных процессорах.
Как сказал мой профессор (Нир Шавит из "Искусство многопроцессорного программирования" ): Пожалуйста, не надо. Основная причина - тестируемость - вы не можете протестировать код синхронизации. Вы можете запускать симуляции, вы можете даже стресс тест. Но в лучшем случае это приблизительное приближение. То, что вам действительно нужно, - это доказательство математической корректности. И очень немногие способны понять их, не говоря уже о их написании. Итак, как говорили другие: используйте существующие библиотеки. Блог Джо Даффи рассматривает некоторые методы (раздел 28). Первый, который вы должны попробовать, - разбиение дерева - перерыв на меньшие задачи и объединение.
Неизменность - это один из способов избежать блокировки. См. обсуждение Эрика Липперта и реализация таких вещей, как неизменные стеки и очереди.
в re. Ответ Сумы, Maurice Herlithy показывает в "Искусстве многопроцессорного программирования", что на самом деле все можно записать без блокировок (см. Главу 6). iirc. Это, по сути, включает разделение задач на обработку элементов node (например, закрытие функции) и включение каждого из них. Потоки будут вычислять состояние, следуя всем узлам из последнего кэшированного. Очевидно, что в худшем случае это может привести к последовательной производительности, но оно имеет важные незащищенные свойства, предотвращая сценарии, когда потоки могут быть запланированы для длительных периодов времени, когда они удерживают блокировки. Herlithy также достигает теоретической ожидаемой производительности, что означает, что один поток не будет в конечном итоге ждать, чтобы выиграть атомную очередь (это сложный код).
Многопоточная очередь/стек удивительно сложна (проверьте проблему SKETCH, предстоящий MIT Kendo, или spin?), чтобы проверить правильность если вы можете свести его к простой структуре.
Пожалуйста, напишите больше о вашей проблеме. Трудно дать хороший ответ без подробностей.
изменить неизменяемость - это хорошо, но применимость ограничена, если я правильно понимаю. Это действительно не претерпевает опасности записи после чтения; рассмотрите два потока, выполняющих "mem = NewNode (mem)"; они могли оба читать mem, затем оба пишут; не является правильным для классической функции приращения. Кроме того, он, вероятно, замедляется из-за распределения кучи (которое должно быть синхронизировано по потокам).
Неизменяемость имела бы такой эффект. Изменения объекта приводят к новому объекту. Lisp работает таким образом под обложками.
Пункт 13 Эффективная Java объясняет эту технику.
Cliff Click имеет купол некоторых крупных исследований по структурам данных, свободных от блокировки, используя машины конечного состояния, а также опубликовал множество реализаций для Java. Вы можете найти его документы, слайды и реализации в своем блоге: http://blogs.azulsystems.com/cliff/
Используйте существующую реализацию, так как эта область работы является областью экспертов домена и PhD (если вы хотите, чтобы все было правильно!)
Например, здесь есть библиотека кода:
Основным принципом синхронизации без блокировки является следующее:
всякий раз, когда вы читаете структуру, вы следуете за чтением с тестом, чтобы узнать, была ли эта структура изменена с момента начала чтения и повторите попытку, пока вы не добьетесь успеха в чтении, если что-то еще не появится и не изменится, пока вы делая это;
всякий раз, когда вы мутируете структуру, вы упорядочиваете свой алгоритм и данные так, чтобы был один атомный шаг, который, если его принять, заставляет все изменения становиться видимыми для других потоков и упорядочивает вещи так, чтобы ни один изменения видны, если только этот шаг не сделан. Вы используете любой атомный механизм lockfree на вашей платформе для этого шага (например, сравнение и набор, связанный с загрузкой + хранилище-условный и т.д.). На этом этапе вы должны проверить, не изменил ли какой-либо другой поток объект с момента начала операции мутации, зафиксировать, если он не существует, и начать его, если он есть.
Существует множество примеров незакрепленных конструкций в Интернете; не зная больше о том, что вы реализуете, и на какой платформе трудно быть более конкретным.
Большинство алгоритмов или структур без блокировки начинаются с некоторой атомарной операции, т.е. изменение какой-либо ячейки памяти, которая когда-то начинается потоком, будет завершена до того, как любой другой поток сможет выполнить эту же операцию. У вас есть такая операция в вашей среде?
См. здесь для канонической статьи по этому вопросу.
Также попробуйте статью в википедии для дальнейших идей и ссылок.
Если вы пишете свои собственные блокированные структуры данных для многоядерного процессора, не забывайте о барьерах памяти! Кроме того, рассмотрите возможность поиска в Методы обмена файлами программного обеспечения.
Если вы видите конфликт блокировок, я сначала попытаюсь использовать более гранулированные блокировки для ваших структур данных, а не полностью блокирующие алгоритмы.
Например, я в настоящее время работаю над многопоточным приложением, которое имеет собственную систему обмена сообщениями (список очередей для каждого потока, очередь содержит сообщения для потока для обработки) для передачи информации между потоками. Существует глобальная блокировка этой структуры. В моем случае мне не нужна скорость, поэтому это не имеет большого значения. Но если этот замок станет проблемой, он может быть заменен отдельными блокировками в каждой очереди, например. Затем добавление/удаление элемента в/из конкретной очереди не повлияло бы на другие очереди. До сих пор существует глобальная блокировка для добавления новой очереди и т.д., Но это было бы не так много.
Даже одна очередь нескольких производителей/потребителей может быть записана с гранулированной блокировкой для каждого элемента вместо глобальной блокировки. Это также может устранить конфликт.
Ну, это зависит от типа структуры, но вы должны сделать структуру так, чтобы она тщательно и молча обнаруживала и обрабатывала возможные конфликты.
Я сомневаюсь, что вы можете сделать тот, который на 100% свободен от блокировки, но опять же, это зависит от того, какую структуру вам нужно построить.
Вам также может потребоваться очертить структуру, чтобы несколько потоков работали над отдельными элементами, а затем позже синхронизировали/рекомбинировали.
Как уже упоминалось, это действительно зависит от того, о какой структуре вы говорите. Например, вы можете написать ограниченную незафиксированную очередь, но не такую, которая допускает произвольный доступ.
Уменьшить или исключить совместное измененное состояние.
В Java используйте пакеты java.util.concurrent в JDK 5+ вместо того, чтобы писать свои собственные. Как уже упоминалось выше, это действительно поле для экспертов, и, если у вас нет лишнего года или двух, кататься самостоятельно не вариант.
Можете ли вы пояснить, что вы подразумеваете под структурой?
Сейчас я предполагаю, что вы имеете в виду общую архитектуру. Вы можете выполнить это, не разделяя память между процессами и используя модель актера для своих процессов.
Если вы прочитали несколько реализаций и документов по теме, вы заметите, что существует следующая общая тема:
1) Общие объекты состояния lisp/clojure style inmutable: то есть все операции записи реализованы, копируя существующее состояние в новом объекте, внося изменения в новый объект и затем попытайтесь обновить общее состояние (полученное из выровненного указателя, который может быть обновлен с помощью примитива CAS). Другими словами, вы НИКОГДА НЕ МОЖЕТ изменить существующий объект, который может быть прочитан больше, чем текущий поток. Интенсивность можно оптимизировать с помощью семантики Copy-on-Write для больших сложных объектов, но это другое дерево орехов
2) вы четко указываете, какие допустимые переходы между текущим и следующим состоянием действительны.. Затем проверка того, что алгоритм действителен, упрощается на порядок.
3) Обрабатывать отброшенные ссылки в списках указателей опасности на поток. После того, как ссылочные объекты безопасны, повторное использование, если возможно
См. другой родственный пост, где некоторый код, реализованный с помощью семафоров и мьютексов (частично) переопределяется в стиле без блокировки: Взаимное исключение и семафоры