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