Неблокирующий алгоритм
В информатике алгоритм если называется неблокирующим, сбой или приостановка любого потока не может вызвать сбой или приостановку другого потока; [1] для некоторых операций эти алгоритмы представляют собой полезную альтернативу традиционным реализациям блокировки . Неблокирующий алгоритм не требует блокировок, если гарантирован общесистемный прогресс , и не требует ожидания, если также гарантирован прогресс для каждого потока. «Неблокирующий» использовался в литературе как синоним «без блокировки» до введения свободы от препятствий в 2003 году. [2]
Слово «неблокируемый» традиционно использовалось для описания телекоммуникационных сетей , которые могли маршрутизировать соединение через набор ретрансляторов «без необходимости переорганизации существующих вызовов» (см. Сеть Clos ). Кроме того, если телефонная станция «не неисправна, она всегда может установить соединение» (см. неблокирующий переключатель минимального охвата ).
Мотивация [ править ]
Традиционный подход к многопоточному программированию заключается в использовании блокировок для синхронизации доступа к общим ресурсам . Примитивы синхронизации, такие как мьютексы , семафоры и критические секции, — это механизмы, с помощью которых программист может гарантировать, что определенные разделы кода не будут выполняться одновременно, если это приведет к повреждению структур общей памяти. Если один поток попытается получить блокировку, которая уже удерживается другим потоком, поток будет блокироваться до тех пор, пока блокировка не будет освобождена.
Блокировка потока может быть нежелательна по многим причинам. Очевидная причина заключается в том, что пока поток заблокирован, он не может ничего выполнить: если бы заблокированный поток выполнял высокоприоритетную задачу или задачу реального времени , было бы крайне нежелательно останавливать его работу.
Другие проблемы менее очевидны. Например, определенные взаимодействия между блокировками могут привести к возникновению ошибок, таких как взаимоблокировка , активная блокировка и инверсия приоритета . Использование блокировок также предполагает компромисс между грубой блокировкой, которая может значительно уменьшить возможности для параллелизма , и детальной блокировкой, которая требует более тщательного проектирования, увеличивает накладные расходы на блокировку и более подвержена ошибкам.
В отличие от блокирующих алгоритмов, неблокирующие алгоритмы не страдают этими недостатками и, кроме того, безопасны для использования в обработчиках прерываний : хотя вытесненный поток не может быть возобновлен, прогресс все равно возможен без него. Напротив, глобальные структуры данных, защищенные методом взаимного исключения, не могут быть безопасно доступны в обработчике прерываний, поскольку вытесненный поток может быть тем, который удерживает блокировку, но это можно легко исправить, замаскировав запрос прерывания во время критической секции. [3]
Для повышения производительности можно использовать структуру данных без блокировки. Структура данных без блокировки увеличивает количество времени, затрачиваемое на параллельное выполнение, а не на последовательное выполнение, повышая производительность многоядерного процессора , поскольку для обеспечения согласованности доступ к общей структуре данных не требует сериализации. [4]
Реализация [ править ]
За некоторыми исключениями, неблокирующие алгоритмы используют атомарные примитивы чтения-изменения-записи , которые должно обеспечивать аппаратное обеспечение, наиболее заметным из которых является сравнение и замена (CAS) . Критические секции почти всегда реализуются с использованием стандартных интерфейсов поверх этих примитивов (в общем случае критические секции будут блокирующими, даже если они реализованы с помощью этих примитивов). В 1990-е годы все неблокирующие алгоритмы приходилось писать «в исходном виде» с базовыми примитивами для достижения приемлемой производительности. Однако развивающаяся область программной транзакционной памяти обещает стандартные абстракции для написания эффективного неблокирующего кода. [5] [6]
Также было проведено много исследований по обеспечению базовых структур данных , таких как стеки , очереди , множества и хеш-таблицы . Это позволяет программам легко асинхронно обмениваться данными между потоками.
Кроме того, некоторые неблокирующие структуры данных достаточно слабы, чтобы их можно было реализовать без специальных атомарных примитивов. Эти исключения включают в себя:
- с одним считывателем и одной записью кольцевой буфер FIFO , размер которого равномерно делит переполнение одного из доступных целочисленных типов без знака, может быть безоговорочно безопасно реализован с использованием только барьера памяти
- Чтение-копирование-обновление с одним автором и любым количеством читателей. (Читатели не ждут ожидания; писатель обычно не блокируется, пока ему не потребуется освободить память).
- Чтение-копирование-обновление с несколькими авторами и любым количеством читателей. (Читатели не требуют ожидания; несколько устройств записи обычно сериализуются с блокировкой и не имеют препятствий).
Некоторые библиотеки используют методы блокировки без блокировки. [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] Таким образом, дополнительная алгоритмическая сложность алгоритма без ожидания может не стоить затраченных усилий, если не существует жестких сроков, которые необходимо соблюдать.
Свобода блокировки [ править ]
Свобода блокировок позволяет отдельным потокам «голодать», но гарантирует общесистемную пропускную способность. Алгоритм является блокировочным, если при работе потоков программы в течение достаточно длительного времени хотя бы один из потоков делает ошибку. прогресс (для некоторого разумного определения прогресса). Все алгоритмы без ожидания не блокируются.
В частности, если один поток приостановлен, то алгоритм блокировки гарантирует, что остальные потоки все еще смогут продолжить работу. Следовательно, если два потока могут конкурировать за одну и ту же блокировку мьютекса или спин-блокировку, то алгоритм не является свободным от блокировок. (Если мы приостановим один поток, удерживающий блокировку, второй поток заблокируется.)
Алгоритм является безблокировочным, если бесконечно часто работа некоторых процессоров завершается успешно за конечное число шагов. Например, если N процессоров пытаются выполнить операцию, некоторым из N процессов удастся завершить операцию за конечное число шагов, а другие могут потерпеть неудачу и повторить попытку в случае неудачи. Разница между режимом ожидания и блокировкой заключается в том, что операция без ожидания для каждого процесса гарантированно завершится за конечное число шагов, независимо от других процессоров.
В общем, алгоритм блокировки может работать в четыре этапа: завершение собственной операции, содействие препятствующей операции, прерывание препятствующей операции и ожидание. Завершение собственной операции осложняется возможностью одновременной помощи и аборта, но это неизменно самый быстрый путь к завершению.
Решение о том, когда оказать помощь, прервать или подождать при возникновении препятствия, является обязанностью диспетчера конфликтов . Это может быть очень просто (помогать операциям с более высоким приоритетом, прерывать операции с более низким приоритетом) или может быть более оптимизировано для достижения большей пропускной способности или снижения задержки операций с более высоким приоритетом.
Правильная параллельная поддержка обычно является самой сложной частью алгоритма без блокировок, и ее выполнение часто очень затратно: не только замедляется вспомогательный поток, но благодаря механике общей памяти замедляется и поток, которому оказывается помощь. , если он еще работает.
Свобода от препятствий [ править ]
Свобода от препятствий — самая слабая естественная гарантия неблокирующего прогресса. Алгоритм является беспрепятственным, если в любой момент один поток, выполняющийся изолированно (т. е. с приостановлением всех мешающих потоков) в течение ограниченного числа шагов, завершит свою работу. [15] Все алгоритмы блокировки не имеют препятствий.
Свобода от препятствий требует только того, чтобы любая частично завершенная операция могла быть прервана и внесенные изменения были отменены. Отказ от параллельной поддержки часто может привести к созданию гораздо более простых алгоритмов, которые легче проверить. системы Предотвращение постоянной блокировки — задача диспетчера конфликтов.
Некоторые алгоритмы без препятствий используют пару «маркеров согласованности» в структуре данных. Процессы, читающие структуру данных, сначала считывают один маркер согласованности, затем считывают соответствующие данные во внутренний буфер, затем считывают другой маркер и затем сравнивают маркеры. Данные согласованы, если два маркера идентичны. Маркеры могут быть неидентичными, если чтение прерывается другим процессом, обновляющим структуру данных. В таком случае процесс отбрасывает данные во внутреннем буфере и пытается повторить попытку.
См. также [ править ]
- Тупик
- Java ConcurrentMap#Атомарность без блокировок
- живость
- Лок (информатика)
- Взаимное исключение
- Инверсия приоритета
- Ресурсный голод
Ссылки [ править ]
- ^ Гетц, Брайан; Пайерлс, Тим; Блох, Джошуа; Боубир, Джозеф; Холмс, Дэвид; Леа, Дуг (2006). Параллелизм Java на практике . Река Аппер-Сэддл, Нью-Джерси: Аддисон-Уэсли. п. 41 . ISBN 9780321349606 .
- ^ Херлихи, М.; Лучанко, В.; Мойр, М. (2003). Беспрепятственная синхронизация: двусторонние очереди на примере (PDF) . 23-я Международная конференция по распределенным вычислительным системам . п. 522.
- ^ Батлер В. Лэмпсон ; Дэвид Д. Ределл (февраль 1980 г.). «Опыт работы с процессами и мониторами в Mesa» . Коммуникации АКМ . 23 (2): 105–117. CiteSeerX 10.1.1.142.5765 . дои : 10.1145/358818.358824 . S2CID 1594544 .
- ^ Гийом Марсе и Карл Кингсфорд. «Быстрый подход без блокировок для эффективного параллельного подсчета случаев появления k-меров» . Биоинформатика (2011) 27(6): 764-770. doi : 10.1093/bioinformatics/btr011 «Счетчик медуз» .
- ^ Харрис, Тим; Фрейзер, Кейр (26 ноября 2003 г.). «Языковая поддержка облегченных транзакций» (PDF) . Уведомления ACM SIGPLAN . 38 (11): 388. CiteSeerX 10.1.1.58.8466 . дои : 10.1145/949343.949340 .
- ^ Харрис, Тим; Марлоу, С.; Пейтон-Джонс, С.; Херлихи, М. (15–17 июня 2005 г.). «Составные транзакции с памятью». Материалы симпозиума ACM SIGPLAN 2005 г. по принципам и практике параллельного программирования, PPoPP '05: Чикаго, Иллинойс . Нью-Йорк, штат Нью-Йорк: ACM Press. стр. 48–60. дои : 10.1145/1065944.1065952 . ISBN 978-1-59593-080-4 . S2CID 53245159 .
- ^ libcds — библиотека C++ контейнеров без блокировок и схема безопасного освобождения памяти.
- ^ liblfds — библиотека структур данных без блокировок, написанная на C.
- ^ Concurrency Kit — библиотека AC для проектирования и реализации неблокирующей системы.
- ^ Херб Саттер. «Код без блокировки: ложное чувство безопасности» . Архивировано из оригинала 1 сентября 2015 г.
- ^ Херб Саттер. «Написание кода без блокировки: исправленная очередь» . Архивировано из оригинала 5 декабря 2008 г.
- ^ Херб Саттер. «Написание обобщенной параллельной очереди» .
- ^ Херб Саттер. «Проблема с замками» .
- ^ Брюс Доусон. «ARM и Lock-Free программирование» .
- ^ Перейти обратно: а б Энтони Уильямс. «Безопасность: выключено: Как не выстрелить себе в ногу атомикой C++» . 2015. п. 20.
- ^ Херлихи, Морис П. (1988). Невозможность и универсальность результатов для синхронизации без ожидания . Учеб. 7-й ежегодный симпозиум ACM. по принципам распределенных вычислений. стр. 276–290. дои : 10.1145/62546.62593 . ISBN 0-89791-277-2 .
- ^ Фич, Вера ; Хендлер, Дэнни; Шавит, Нир (2004). О присущей примитивам условной синхронизации слабости . Учеб. 23-й ежегодный симпозиум ACM по принципам распределенных вычислений (PODC). стр. 80–87. дои : 10.1145/1011767.1011780 . ISBN 1-58113-802-4 .
- ^ Коган, Алекс; Петранк, Эрез (2011). Очереди без ожидания с несколькими постановками в очередь и выводами из очереди (PDF) . Учеб. 16-й симпозиум ACM SIGPLAN. по принципам и практике параллельного программирования (PPOPP). стр. 223–234. дои : 10.1145/1941553.1941585 . ISBN 978-1-4503-0119-0 .
- ^ Майкл, Магед; Скотт, Майкл (1996). Простые, быстрые и практичные неблокирующие и блокирующие алгоритмы параллельной очереди . Учеб. 15-й ежегодный симпозиум ACM. по принципам распределенных вычислений (PODC). стр. 267–275. дои : 10.1145/248052.248106 . ISBN 0-89791-800-2 .
- ^ Коган, Алекс; Петранк, Эрез (2012). Метод создания быстрых структур данных без ожидания . Учеб. 17-й симпозиум ACM SIGPLAN. по принципам и практике параллельного программирования (PPOPP). стр. 141–150. дои : 10.1145/2145816.2145835 . ISBN 978-1-4503-1160-1 .
- ^ Тимнат, Шахар; Петранк, Эрез (2014). Практическое моделирование без ожидания для структур данных без блокировок . Учеб. 17-й симпозиум ACM SIGPLAN. по принципам и практике параллельного программирования (PPOPP). стр. 357–368. дои : 10.1145/2692916.2555261 . ISBN 978-1-4503-2656-8 .
- ^ Алистарх, Дэн; Цензор-Гилель, Керен; Шавит, Нир (2014). Являются ли параллельные алгоритмы без блокировок практически не требующими ожидания? . Учеб. 46-й ежегодный симпозиум ACM по теории вычислений (STOC'14). стр. 714–723. arXiv : 1311.3200 . дои : 10.1145/2591796.2591836 . ISBN 978-1-4503-2710-7 .