В информатике алгоритм называется неблокирующим, если сбой или приостановка любого потока не может вызвать сбой или приостановку другого потока; [1] для некоторых операций эти алгоритмы предоставляют полезную альтернативу традиционным реализациям блокировки . Неблокирующий алгоритм является безблокировочным , если гарантирован общесистемный прогресс , и безожидательным, если также гарантирован прогресс для каждого потока. «Неблокирующий» использовался как синоним «безблокировочного» в литературе до введения в 2003 году концепции обструкции-свободы. [2]
Слово «неблокируемый» традиционно использовалось для описания телекоммуникационных сетей , которые могли направлять соединение через набор реле «без необходимости переупорядочивать существующие вызовы» (см. сеть Clos ). Кроме того, если телефонная станция «не неисправна, она всегда может установить соединение» (см. неблокируемый минимальный охватывающий коммутатор ).
Традиционный подход к многопоточному программированию заключается в использовании блокировок для синхронизации доступа к общим ресурсам . Примитивы синхронизации, такие как мьютексы , семафоры и критические секции , — это механизмы, с помощью которых программист может гарантировать, что определенные разделы кода не будут выполняться одновременно, если это приведет к повреждению структур общей памяти. Если один поток попытается получить блокировку, которая уже удерживается другим потоком, поток заблокируется до тех пор, пока блокировка не будет освобождена.
Блокировка потока может быть нежелательной по многим причинам. Очевидная причина в том, что пока поток заблокирован, он не может ничего сделать: если бы заблокированный поток выполнял высокоприоритетную или оперативную задачу, было бы крайне нежелательно останавливать его выполнение.
Другие проблемы менее очевидны. Например, определенные взаимодействия между блокировками могут привести к таким ошибочным состояниям, как взаимоблокировка , оперативная блокировка и инверсия приоритетов . Использование блокировок также подразумевает компромисс между грубой блокировкой, которая может значительно сократить возможности для параллелизма , и мелкой блокировкой, которая требует более тщательного проектирования, увеличивает накладные расходы на блокировку и более подвержена ошибкам.
В отличие от блокирующих алгоритмов, неблокирующие алгоритмы не страдают от этих недостатков и, кроме того, безопасны для использования в обработчиках прерываний : даже если прерванный поток не может быть возобновлен, прогресс все еще возможен без него. Напротив, глобальные структуры данных, защищенные взаимным исключением, не могут быть безопасно доступны в обработчике прерываний, поскольку прерванный поток может быть тем, который удерживает блокировку. Хотя это можно исправить, маскируя запросы прерываний во время критической секции, это требует, чтобы код в критической секции имел ограниченное (и желательно короткое) время выполнения, иначе может наблюдаться чрезмерная задержка прерывания. [3]
Для повышения производительности можно использовать структуру данных без блокировки. Структура данных без блокировки увеличивает время, затрачиваемое на параллельное выполнение, а не на последовательное, что повышает производительность на многоядерном процессоре , поскольку доступ к общей структуре данных не требует сериализации, чтобы оставаться согласованным. [4]
За редкими исключениями, неблокирующие алгоритмы используют атомарные примитивы чтения-изменения-записи , которые должно предоставлять оборудование, наиболее заметным из которых является сравнение и обмен (CAS) . Критические секции почти всегда реализуются с использованием стандартных интерфейсов над этими примитивами (в общем случае критические секции будут блокирующими, даже если реализованы с этими примитивами). В 1990-х годах все неблокирующие алгоритмы должны были быть написаны «в исходном виде» с базовыми примитивами для достижения приемлемой производительности. Однако развивающаяся область программной транзакционной памяти обещает стандартные абстракции для написания эффективного неблокирующего кода. [5] [6]
Также было проведено много исследований в области предоставления базовых структур данных , таких как стеки , очереди , наборы и хэш-таблицы . Они позволяют программам легко обмениваться данными между потоками асинхронно.
Кроме того, некоторые неблокирующие структуры данных достаточно слабы, чтобы их можно было реализовать без специальных атомарных примитивов. К таким исключениям относятся:
Некоторые библиотеки используют внутренние методы безблокировочной обработки, [7] [8] [9] , но сложно написать корректный код безблокировочной обработки. [10] [11] [12] [13]
Неблокирующие алгоритмы обычно включают в себя ряд инструкций чтения, чтения-изменения-записи и записи в тщательно разработанном порядке. Оптимизирующие компиляторы могут агрессивно переупорядочивать операции. Даже когда они этого не делают, многие современные процессоры часто переупорядочивают такие операции (они имеют «слабую модель согласованности »), если только барьер памяти не используется, чтобы сказать процессору не переупорядочивать. Программисты C++11 могут использовать std::atomicв <atomic>, а программисты C11 могут использовать <stdatomic.h>, оба из которых предоставляют типы и функции, которые говорят компилятору не переупорядочивать такие инструкции и вставлять соответствующие барьеры памяти. [14]
Свобода от ожидания — самая сильная неблокирующая гарантия прогресса, объединяющая гарантированную пропускную способность всей системы с свободой от голодания . Алгоритм свободен от ожидания, если каждая операция имеет ограничение на количество шагов, которые алгоритм выполнит до завершения операции. [15] Это свойство имеет решающее значение для систем реального времени и всегда приятно иметь его, пока затраты на производительность не слишком высоки.
В 1980-х годах [16] было показано , что все алгоритмы могут быть реализованы без ожидания, и было продемонстрировано множество преобразований из последовательного кода, называемых универсальными конструкциями . Однако полученная производительность в целом не соответствует даже наивным блокирующим конструкциям. С тех пор в нескольких работах была улучшена производительность универсальных конструкций, но все равно их производительность намного ниже блокирующих конструкций.
В нескольких работах исследовалась сложность создания алгоритмов без ожидания. Например, было показано [17] , что широко распространенные атомарные условные примитивы CAS и LL/SC не могут обеспечить реализацию без голодания многих распространенных структур данных без линейного роста затрат памяти с числом потоков.
Однако на практике эти нижние границы не представляют собой реального препятствия, поскольку расход строки кэша или гранулы исключительного резервирования (до 2 КБ на ARM) хранилища на поток в общей памяти не считается слишком затратным для практических систем (обычно логически требуемый объем хранилища составляет слово, но физически операции CAS на одной и той же строке кэша будут конфликтовать, как и операции LL/SC в одной и той же грануле исключительного резервирования, поэтому физически требуемый объем хранилища [ требуется ссылка ] больше).
Алгоритмы без ожидания были редки до 2011 года, как в исследованиях, так и на практике. Однако в 2011 году Коган и Петран [18] представили очередь без ожидания, построенную на примитиве CAS , обычно доступном на обычном оборудовании. Их конструкция расширила очередь без блокировки Майкла и Скотта [19] , которая является эффективной очередью, часто используемой на практике. Последующая статья Когана и Петранка [20] предоставила метод для ускорения алгоритмов без ожидания и использовала этот метод, чтобы сделать очередь без ожидания практически такой же быстрой, как и ее аналог без блокировки. Последующая статья Тимната и Петранка [21] предоставила автоматический механизм для генерации структур данных без ожидания из структур без блокировки. Таким образом, реализации без ожидания теперь доступны для многих структур данных.
При разумных предположениях Алистарх, Цензор-Хиллел и Шавит показали, что алгоритмы без блокировок практически не требуют ожидания. [22] Таким образом, дополнительная алгоритмическая сложность алгоритма без ожидания может не стоить усилий, если нет жестких сроков, которые необходимо соблюдать.
Lock-free позволяет отдельным потокам голодать, но гарантирует пропускную способность всей системы. Алгоритм является lock-free, если при достаточно длительном выполнении программных потоков хотя бы один из потоков достигает прогресса (для некоторого разумного определения прогресса). Все wait-free алгоритмы являются lock-free.
В частности, если один поток приостановлен, то алгоритм без блокировки гарантирует, что оставшиеся потоки все еще смогут продолжить работу. Следовательно, если два потока могут бороться за одну и ту же блокировку мьютекса или спин-блокировку, то алгоритм не является алгоритмом без блокировки. (Если мы приостановим один поток, удерживающий блокировку, то второй поток заблокируется.)
Алгоритм является алгоритмом без блокировки, если бесконечно часто операция некоторых процессоров будет успешной за конечное число шагов. Например, если N процессоров пытаются выполнить операцию, некоторые из N процессов успешно завершат операцию за конечное число шагов, а другие могут потерпеть неудачу и повторить попытку в случае неудачи. Разница между wait-free и lock-free заключается в том, что wait-free операция каждым процессом гарантированно успешно завершится за конечное число шагов, независимо от других процессоров.
В общем, алгоритм без блокировки может работать в четыре фазы: завершение собственной операции, помощь в препятствующей операции, прерывание препятствующей операции и ожидание. Завершение собственной операции осложняется возможностью одновременной помощи и прерывания, но это неизменно самый быстрый путь к завершению.
Решение о том, когда помогать, прерывать или ждать при возникновении препятствия, принимает менеджер конфликтов . Это может быть очень просто (помочь операциям с более высоким приоритетом, прервать операции с более низким приоритетом) или может быть более оптимизированным для достижения лучшей пропускной способности или снижения задержки приоритетных операций.
Правильная параллельная помощь обычно является самой сложной частью алгоритма без блокировок и часто требует больших затрат на выполнение: не только замедляется вспомогательный поток, но и, благодаря механике общей памяти, замедляется и поток, которому оказывается помощь, если он все еще выполняется.
Свобода от препятствий — самая слабая естественная гарантия неблокируемого прогресса. Алгоритм свободен от препятствий, если в любой момент один поток, выполняемый изолированно (т. е. со всеми препятствующими потоками, приостановленными) для ограниченного числа шагов, завершит свою работу. [15] Все алгоритмы без блокировок свободны от препятствий.
Свобода от препятствий требует только того, чтобы любая частично завершенная операция могла быть прервана, а внесенные изменения откатились. Отказ от параллельной помощи часто может привести к гораздо более простым алгоритмам, которые легче проверить. Предотвращение постоянной блокировки системы в реальном времени является задачей менеджера конфликтов.
Некоторые алгоритмы без препятствий используют пару «маркеров согласованности» в структуре данных. Процессы, считывающие структуру данных, сначала считывают один маркер согласованности, затем считывают соответствующие данные во внутренний буфер, затем считывают другой маркер, а затем сравнивают маркеры. Данные согласованы, если два маркера идентичны. Маркеры могут быть неидентичными, когда чтение прерывается другим процессом, обновляющим структуру данных. В таком случае процесс отбрасывает данные во внутреннем буфере и повторяет попытку.