Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Не путать с неблокирующим вводом-выводом .

В информатике , алгоритм называется неблокирующим , если отказ или приостановление каких - либо нити не может привести к поломке или суспензии другого потока; [1] для некоторых операций эти алгоритмы представляют собой полезную альтернативу традиционным реализациям блокировки . Неблокирующий алгоритм свободен от блокировок, если есть гарантированный прогресс в масштабе всей системы , и без ожидания, если также есть гарантированный прогресс для каждого потока. «Неблокирование» использовалось как синоним «без блокировки» в литературе до введения в 2003 г. свободы от препятствий [2].

Слово «неблокирующий» традиционно использовалось для описания телекоммуникационных сетей, которые могли маршрутизировать соединение через набор реле «без необходимости переупорядочивать существующие вызовы», см. Сеть Клоса . Кроме того, если телефонная станция «исправна, она всегда может установить соединение», см. Неблокирующий коммутатор с минимальным охватом .

Мотивация [ править ]

Основная статья: Недостатки замков

Традиционный подход к многопоточному программированию заключается в использовании блокировок для синхронизации доступа к общим ресурсам . Примитивы синхронизации, такие как мьютексы , семафоры и критические секции, - все это механизмы, с помощью которых программист может гарантировать, что определенные секции кода не будут выполняться одновременно, если это повредит структуры разделяемой памяти. Если один поток пытается получить блокировку, которая уже удерживается другим потоком, поток будет блокироваться до тех пор, пока блокировка не освободится.

Блокировка потока может быть нежелательной по многим причинам. Очевидная причина заключается в том, что пока поток заблокирован, он ничего не может сделать: если заблокированный поток выполнял высокоприоритетную задачу или задачу в реальном времени , было бы крайне нежелательно останавливать его выполнение.

Остальные проблемы менее очевидны. Например, определенные взаимодействия между блокировками могут привести к ошибочным состояниям, таким как тупик , активная блокировка и инверсия приоритета . Использование блокировок также предполагает компромисс между крупномасштабной блокировкой, которая может значительно уменьшить возможности параллелизма , и мелкозернистой блокировкой, которая требует более тщательного проектирования, увеличивает накладные расходы на блокировку и более подвержена ошибкам.

В отличие от алгоритмов блокировки, неблокирующие алгоритмы не страдают этими недостатками и, кроме того, безопасны для использования в обработчиках прерываний : даже если прерванный поток не может быть возобновлен, выполнение по-прежнему возможно без этого. Напротив, глобальные структуры данных, защищенные взаимным исключением, не могут быть безопасно доступны в обработчике прерывания, поскольку вытесняемый поток может быть тем, который удерживает блокировку, но это можно легко исправить, замаскировав запрос прерывания во время критического участка. [3]

Для повышения производительности можно использовать свободную от блокировок структуру данных. Безблокировочная структура данных увеличивает количество времени, затрачиваемого на параллельное выполнение, а не на последовательное, улучшая производительность многоядерного процессора , поскольку доступ к общей структуре данных не нужно сериализовать, чтобы оставаться согласованным. [4]

Реализация [ править ]

За некоторыми исключениями, неблокирующие алгоритмы используют атомарные примитивы чтения-изменения-записи, которые должно обеспечивать оборудование, наиболее заметным из которых является сравнение и замена (CAS) . Критические секции почти всегда реализуются с использованием стандартных интерфейсов над этими примитивами (в общем случае критические секции будут блокироваться, даже если они реализованы с этими примитивами). В 1990-х годах все неблокирующие алгоритмы должны были быть написаны «изначально» с базовыми примитивами для достижения приемлемой производительности. Однако развивающаяся область программной транзакционной памяти обещает стандартные абстракции для написания эффективного неблокирующего кода. [5] [6]

Также было проведено много исследований по предоставлению базовых структур данных, таких как стеки , очереди , наборы и хеш-таблицы . Это позволяет программам легко асинхронно обмениваться данными между потоками.

Кроме того, некоторые неблокирующие структуры данных достаточно слабы, чтобы их можно было реализовать без специальных атомарных примитивов. Эти исключения включают:

  • Кольцевой буфер FIFO с одним считывателем и одной записью , размер которого равномерно разделяет переполнение одного из доступных беззнаковых целочисленных типов, безоговорочно может быть безопасно реализован с использованием только барьера памяти
  • Чтение-копирование-обновление с одним писателем и любым количеством читателей. (Читатели не ждут; писатель обычно свободен от блокировок, пока ему не потребуется освободить память).
  • Чтение-копирование-обновление с несколькими авторами и любым количеством читателей. (Читатели не ждут; несколько писателей обычно сериализуются с блокировкой и не свободны от препятствий).

Некоторые библиотеки внутренне используют методы без блокировки, [7] [8] [9], но трудно написать правильный код без блокировки. [10] [11] [12] [13]

Свобода ожидания [ править ]

Свобода ожидания - это самая надежная неблокирующая гарантия прогресса, сочетающая гарантированную общесистемную пропускную способность со свободой от голода . Алгоритм не требует ожидания, если каждая операция имеет ограничение на количество шагов, которые алгоритм сделает до завершения операции. [14] Это свойство критически важно для систем реального времени, и всегда полезно иметь, если затраты на производительность не слишком высоки.

В 1980-х годах было показано [15], что все алгоритмы могут быть реализованы без ожидания, и были продемонстрированы многие преобразования из последовательного кода, называемые универсальными конструкциями . Однако получаемая производительность в целом не соответствует даже наивным схемам блокировки. С тех пор несколько работ улучшили характеристики универсальных конструкций, но, тем не менее, их характеристики намного ниже, чем у блочных конструкций.

В нескольких статьях исследовалась сложность создания алгоритмов без ожидания. Например, было показано [16], что широко доступные атомарные условные примитивы, CAS и LL / SC , не могут обеспечить безостановочную реализацию многих общих структур данных без увеличения затрат памяти, линейно возрастающих по количеству потоков.

Но на практике эти нижние границы не представляют собой реального препятствия, поскольку расходование строки кэша или гранулы эксклюзивного резервирования (до 2 КБ на ARM) хранилища на поток в общей памяти не считается слишком затратным для практических систем (обычно количество хранить логически требуется , это слово, но физически CAS операции на одной и той же строке кэша будут сталкиваться, и LL / SC операции в одном эксклюзивном гранулу бронирования столкнется, поэтому количество магазина физически требуется [ править ] больше).

Алгоритмы без ожидания были редкостью до 2011 года как в исследованиях, так и на практике. Однако в 2011 году Коган и Петранк [17] представили очередь без ожидания, построенную на примитиве CAS , обычно доступную на обычном оборудовании. Их конструкция расширила свободную от блокировок очередь Майкла и Скотта [18], которая является эффективной очередью, часто используемой на практике. В следующей статье Когана и Петранка [19] был предложен метод, позволяющий сделать алгоритмы без ожидания быстрыми, и использовался этот метод, чтобы сделать очередь без ожидания практически такой же быстрой, как и его аналог без блокировки. Последующая статья Тимната и Петранка [20]предоставил автоматический механизм для генерации структур данных без ожидания из структур без блокировки. Таким образом, для многих структур данных теперь доступны реализации без ожидания.

Lock-Freedom [ править ]

Отсутствие блокировки позволяет отдельным потокам зависать, но гарантирует пропускную способность всей системы. Алгоритм свободен от блокировок, если, когда потоки программы выполняются в течение достаточно длительного времени, по крайней мере один из потоков достигает прогресса (для некоторого разумного определения прогресса). Все алгоритмы без ожидания не требуют блокировок.

В частности, если один поток приостановлен, то алгоритм без блокировки гарантирует, что оставшиеся потоки все еще могут работать. Следовательно, если два потока могут бороться за одну и ту же блокировку мьютекса или спин-блокировку, то алгоритм не является свободным от блокировки. (Если мы приостановим один поток, удерживающий блокировку, второй поток будет заблокирован.)

Алгоритм является свободным от блокировок, если бесконечно часто работа некоторых процессоров будет успешной за конечное число шагов. Например, если N процессоров пытаются выполнить операцию, некоторые из N процессов завершат операцию за конечное количество шагов, а другие могут выйти из строя и попытаться повторить попытку. Разница между режимом ожидания и блокировкой заключается в том, что операция без ожидания для каждого процесса гарантированно завершится за конечное число шагов, независимо от других процессоров.

В общем, алгоритм без блокировок может выполняться в четыре этапа: завершение собственной операции, оказание помощи в блокирующей операции, прерывание блокирующей операции и ожидание. Самостоятельное завершение операции осложняется возможностью одновременной помощи и аборта, но это всегда самый быстрый путь к завершению.

Решение о том, когда помочь, прервать или подождать, когда будет встречено препятствие, является обязанностью диспетчера конфликтов . Это может быть очень просто (поддержка операций с более высоким приоритетом, прерывание операций с более низким приоритетом) или может быть более оптимизированным для достижения большей пропускной способности или уменьшения задержки приоритетных операций.

Правильная параллельная поддержка, как правило, является наиболее сложной частью алгоритма без блокировок и часто требует больших затрат для выполнения: не только замедляется вспомогательный поток, но и благодаря механике разделяемой памяти поток, которому оказывается помощь, также замедляется. , если он все еще работает.

Свобода препятствий [ править ]

Свобода препятствий - самая слабая естественная неблокирующая гарантия прогресса. Алгоритм свободен от препятствий, если в любой момент единственный поток, выполняемый изолированно (т. Е. Со всеми блокирующими потоками, приостановленными) в течение ограниченного числа шагов, завершит свою работу. [14] Все алгоритмы без блокировок не имеют препятствий.

Отсутствие препятствий требует только того, чтобы любая частично завершенная операция могла быть прервана, а внесенные изменения были отменены. Отказ от одновременной поддержки часто может привести к гораздо более простым алгоритмам, которые легче проверить. Предотвращение постоянной блокировки системы в реальном времени - задача диспетчера конфликтов.

Некоторые алгоритмы без препятствий используют пару «маркеров согласованности» в структуре данных. Процессы, считывающие структуру данных, сначала считывают один маркер согласованности, затем считывают соответствующие данные во внутренний буфер, затем считывают другой маркер, а затем сравнивают маркеры. Данные согласованы, если два маркера идентичны. Маркеры могут быть неидентичными, когда чтение прерывается другим процессом, обновляющим структуру данных. В таком случае процесс сбрасывает данные во внутреннем буфере и пытается снова.

См. Также [ править ]

  • Тупик
  • Java ConcurrentMap # Атомарность без блокировок
  • Живучесть
  • Блокировка (программная инженерия)
  • Взаимное исключение
  • Инверсия приоритета
  • Ресурсное голодание

Ссылки [ править ]

  1. ^ Гётц, Брайан; Пайерлс, Тим; Блох, Джошуа; Bowbeer, Джозеф; Холмс, Дэвид; Ли, Дуг (2006). Параллелизм Java на практике . Река Аппер Сэдл, Нью-Джерси: Аддисон-Уэсли. п. 41 . ISBN 9780321349606.
  2. ^ Herlihy, M .; Luchangco, V .; Мойр, М. (2003). Синхронизация без препятствий: двусторонние очереди в качестве примера (PDF) . 23-я Международная конференция по распределенным вычислительным системам . п. 522.
  3. ^ Батлер В. Лэмпсон ; Дэвид Д. Ределл (февраль 1980 г.). «Опыт работы с процессами и мониторами в Мезе» . Коммуникации ACM . 23 (2): 105–117. CiteSeerX 10.1.1.142.5765 . DOI : 10.1145 / 358818.358824 . 
  4. ^ Гийом Марсе и Карл Кингсфорд. «Быстрый подход без блокировок для эффективного параллельного подсчета появления k-мер» . Биоинформатика (2011) 27 (6): 764-770. doi : 10.1093 / bioinformatics / btr011 « Счетчик медузы» .
  5. ^ Харрис, Тим; Фрейзер, Кейр (26 ноября 2003 г.). «Поддержка языков для облегченных транзакций» (PDF) . Уведомления ACM SIGPLAN . 38 (11): 388. CiteSeerX 10.1.1.58.8466 . DOI : 10.1145 / 949343.949340 .  
  6. ^ Харрис, Тим; Marlow, S .; Peyton-Jones, S .; Херлихи, М. (15–17 июня 2005 г.). «Транзакции составной памяти». Материалы симпозиума ACM SIGPLAN 2005 г. по принципам и практике параллельного программирования, PPoPP '05: Чикаго, Иллинойс . Нью-Йорк, штат Нью-Йорк: ACM Press. С. 48–60. DOI : 10.1145 / 1065944.1065952 . ISBN 978-1-59593-080-4.
  7. ^ libcds - C ++ библиотека безблокирующих контейнеров и схема безопасного восстановления памяти
  8. ^ liblfds - библиотека структур данных без блокировок, написанная на C
  9. ^ Concurrency Kit - библиотека AC для проектирования и реализации неблокирующей системы
  10. ^ Херб Саттер. «Lock-Free Code: ложное чувство безопасности» . Архивировано из оригинала на 2015-09-01.
  11. ^ Херб Саттер. «Написание кода без блокировки: исправленная очередь» . Архивировано из оригинала на 2008-12-05.
  12. ^ Херб Саттер. «Написание обобщенной параллельной очереди» .
  13. ^ Херб Саттер. «Беда с замками» .
  14. ^ a b Энтони Уильямс. «Безопасность: выключено: Как не прострелить себе ногу с помощью атомики C ++» . 2015. стр. 20.
  15. ^ Херлихи, Морис П. (1988). Невозможность и универсальность результатов без ожидания синхронизации . Proc. 7-й ежегодный симпозиум ACM. по принципам распределенных вычислений. С. 276–290. DOI : 10.1145 / 62546.62593 . ISBN 0-89791-277-2.
  16. ^ Fich, Вера ; Хендлер, Дэнни; Шавит, Нир (2004). О слабости, присущей примитивам условной синхронизации . Proc. 23-й ежегодный симпозиум ACM по принципам распределенных вычислений (PODC). С. 80–87. DOI : 10.1145 / 1011767.1011780 . ISBN 1-58113-802-4.
  17. ^ Коган, Алекс; Петранк, Эрез (2011). Очереди без ожидания с несколькими установками в очередь и извлечения из очереди (PDF) . Proc. 16-я конференция ACM SIGPLAN Symp. по принципам и практике параллельного программирования (PPOPP). С. 223–234. DOI : 10.1145 / 1941553.1941585 . ISBN  978-1-4503-0119-0.
  18. ^ Майкл, Магед; Скотт, Майкл (1996). Простые, быстрые и практичные алгоритмы одновременной неблокирующей и блокирующей очереди . Proc. 15-й ежегодный симпозиум ACM. по принципам распределенных вычислений (PODC). С. 267–275. DOI : 10.1145 / 248052.248106 . ISBN 0-89791-800-2.
  19. ^ Коган, Алекс; Петранк, Эрез (2012). Метод создания быстрых структур данных без ожидания . Proc. 17-я конференция ACM SIGPLAN Symp. по принципам и практике параллельного программирования (PPOPP). С. 141–150. DOI : 10.1145 / 2145816.2145835 . ISBN 978-1-4503-1160-1.
  20. ^ Тимнат, Шахар; Петранк, Эрез (2014). Практическое моделирование без ожидания структур данных без блокировки . Proc. 17-я конференция ACM SIGPLAN Symp. по принципам и практике параллельного программирования (PPOPP). С. 357–368. DOI : 10.1145 / 2692916.2555261 . ISBN 978-1-4503-2656-8.

Внешние ссылки [ править ]

  • Введение в программирование без блокировок
  • Неблокирующие алгоритмы