Неблокирующие алгоритмы: гарантия прогресса в многопоточной среде

Введение

Алгоритм в потоке, отказ которого не может вызвать отказ другого потока.

В информатике алгоритм называется неблокирующим, если отказ или приостановка любого потока не может привести к отказу или приостановке другого потока; для некоторых операций такие алгоритмы предоставляют полезную альтернативу традиционным блокирующим реализациям. Неблокирующий алгоритм считается безблокировочным, если гарантирован системный прогресс, и без ожидания, если также гарантирован прогресс для каждого потока. Термин "неблокирующий" использовался в литературе как синоним "безблокировочного" до введения понятия обструктивной свободы в 2003 году. Ранее слово "неблокирующий" традиционно использовалось для описания телекоммуникационных сетей, способных маршрутизировать соединение через набор реле "без необходимости перекоммутации существующих вызовов" (см. сеть Clos). Также, если телефонная станция "исправна, она всегда может установить соединение" (см. неблокирующий минимальный остовный коммутатор).

Мотивация

Традиционный подход к многопоточному программированию заключается в использовании блокировок для синхронизации доступа к общим ресурсам. Примитивы синхронизации, такие как мьютексы, семафоры и критические секции, – это механизмы, с помощью которых программист может гарантировать, что определенные участки кода не будут выполняться одновременно, если это может привести к повреждению структур общей памяти. Если одна нить пытается получить блокировку, которая уже занята другой нитью, эта нить будет заблокирована до тех пор, пока блокировка не освободится. Блокировка нити может быть нежелательна по многим причинам. Очевидная причина в том, что пока нить заблокирована, она не может выполнить никаких действий: если заблокированная нить выполняла задачу с высоким приоритетом или в режиме реального времени, остановка ее выполнения была бы крайне нежелательна. Другие проблемы менее очевидны. Например, определенные взаимодействия между блокировками могут привести к ошибкам, таким как взаимная блокировка (deadlock), состояние ожидания (livelock) и инверсия приоритетов. Использование блокировок также предполагает компромисс между блокировками с крупным гранулярностью, которые могут значительно снизить возможности для параллелизма, и блокировками с мелкой гранулярностью, которые требуют более тщательной разработки, увеличивают накладные расходы на блокировку и более подвержены ошибкам. В отличие от блокирующих алгоритмов, неблокирующие алгоритмы не имеют этих недостатков и, кроме того, безопасны для использования в обработчиках прерываний: даже если прерванная нить не может быть возобновлена, прогресс все равно возможен без нее. Напротив, глобальные структуры данных, защищенные взаимоисключением, не могут безопасно использоваться в обработчике прерывания, поскольку прерванная нить может быть той, которая удерживает блокировку, однако это можно легко исправить, маскируя запрос на прерывание во время критической секции. Структура данных без блокировок может быть использована для повышения производительности. Структура данных без блокировок увеличивает время, затрачиваемое на параллельное выполнение, а не на последовательное, улучшая производительность на многоядерном процессоре, поскольку доступ к общей структуре данных не нужно сериализовать для обеспечения согласованности.

Свобода ожидания

Свобода ожидания – это самая сильная неблокирующая гарантия прогресса, сочетающая гарантированную пропускную способность всей системы со свободой от взаимной блокировки. Алгоритм считается алгоритмом с ожиданием, если для каждой операции существует ограничение на количество шагов, необходимых для её завершения. Это свойство критически важно для систем реального времени и всегда желательно, если стоимость производительности не слишком высока. Было показано, что в 1980-х годах все алгоритмы могут быть реализованы с ожиданием, и было продемонстрировано множество преобразований из последовательного кода, называемых универсальными конструкциями. Однако, производительность полученных решений, как правило, не соответствует даже наивным блокирующим конструкциям. Последующие работы улучшили производительность универсальных конструкций, но она все равно значительно ниже, чем у блокирующих конструкций. Ряд исследований посвящен сложности создания алгоритмов с ожиданием. Например, было показано, что широко распространенные атомарные условные примитивы CAS и LL/SC не могут обеспечить реализацию многих распространенных структур данных без взаимной блокировки, при этом затраты памяти растут линейно с увеличением числа потоков. Однако на практике эти нижние границы не являются непреодолимым препятствием, поскольку выделение кеш-линии или гранулы эксклюзивного резервирования (до 2 КБ на ARM) памяти на поток не считается чрезмерно дорогим для практических систем (обычно логически требуется один элемент памяти, но физически операции CAS на одной кеш-линии будут конфликтовать, а операции LL/SC в одной грануле эксклюзивного резервирования также будут конфликтовать, поэтому физически требуется больше памяти). Алгоритмы с ожиданием были редкостью до 2011 года как в исследованиях, так и на практике. Однако в 2011 году Коган и Петранк представили очередь с ожиданием, основанную на примитиве CAS, который обычно доступен на современном оборудовании. Их конструкция расширила неблокирующую очередь Майкла и Скотта, которая является эффективной очередью, часто используемой на практике. В последующей работе Коган и Петранк предложили метод повышения скорости алгоритмов с ожиданием и использовали его для ускорения очереди с ожиданием, сделав её практически такой же быстрой, как её неблокирующий аналог. В последующей статье Тимната и Петранка был представлен автоматический механизм для генерации структур данных с ожиданием из неблокирующих структур данных. Таким образом, сейчас доступны реализации с ожиданием для многих структур данных.

Wait freedom is the strongest non blocking guarantee of progress, combining guaranteed system wide throughput with starvation freedom. An algorithm is wait free if every operation has a bound on the number of steps the algorithm will take before the operation completes. This property is critical for real time systems and is always nice to have as long as the performance cost is not too high. It was shown in the 1980s that all algorithms can be implemented wait free, and many transformations from serial code, called universal constructions, have been demonstrated. However, the resulting performance does not in general match even naïve blocking designs. Several papers have since improved the performance of universal constructions, but still, their performance is far below blocking designs. Several papers have investigated the difficulty of creating wait free algorithms. For example, it has been shown that the widely available atomic conditional primitives, CAS and LL/SC, cannot provide starvation free implementations of many common data structures without memory costs growing linearly in the number of threads. But in practice these lower bounds do not present a real barrier as spending a cache line or exclusive reservation granule (up to 2 KB on ARM) of store per thread in the shared memory is not considered too costly for practical systems (typically the amount of store logically required is a word, but physically CAS operations on the same cache line will collide, and LL/SC operations in the same exclusive reservation granule will collide, so the amount of store physically required is greater). Wait free algorithms were rare until 2011, both in research and in practice. However, in 2011 Kogan and Petrank presented a wait free queue building on the CAS primitive, generally available on common hardware. Their construction expanded the lock free queue of Michael and Scott, which is an efficient queue often used in practice. A follow up paper by Kogan and Petrank provided a method for making wait free algorithms fast and used this method to make the wait free queue practically as fast as its lock free counterpart. A subsequent paper by Timnat and Petrank provided an automatic mechanism for generating wait free data structures from lock free ones. Thus, wait free implementations are now available for many data structures.

Свобода блокировки

Свобода блокировки позволяет отдельным потокам испытывать задержку, но гарантирует общую пропускную способность системы. Алгоритм считается безблокировочным, если при достаточно длительном выполнении потоков программы, хотя бы один из потоков добивается прогресса (при разумном определении прогресса). Все алгоритмы без ожидания являются безблокировочными. В частности, если один поток приостановлен, безблокировочный алгоритм гарантирует, что остальные потоки все еще могут добиваться прогресса. Следовательно, если два потока могут конкурировать за один и тот же мьютекс или спин-лок, алгоритм не является безблокировочным. (Если приостановить поток, удерживающий блокировку, второй поток будет заблокирован.) Алгоритм является безблокировочным, если бесконечно часто операции, выполняемые некоторыми процессорами, завершаются за конечное число шагов. Например, если процессоры пытаются выполнить операцию, некоторые из них завершат ее за конечное число шагов, а другие могут потерпеть неудачу и повторить попытку. Разница между алгоритмами без ожидания и безблокировочными заключается в том, что в алгоритмах без ожидания работа каждого процессора гарантированно завершается за конечное число шагов, независимо от других процессоров. В общем случае, безблокировочный алгоритм может выполняться в четыре фазы: завершение собственной операции, помощь в выполнении прерываемой операции, прерывание прерываемой операции и ожидание. Завершение собственной операции усложняется возможностью одновременной помощи и прерывания, но обычно является самым быстрым способом завершения. Решение о том, когда помогать, прерывать или ждать при возникновении препятствия, лежит на менеджере конкуренции. Он может быть очень простым (помогать операциям с более высоким приоритетом, прерывать операции с более низким приоритетом) или более оптимизированным для достижения большей пропускной способности или снижения задержки для приоритетных операций. Корректная одновременная помощь обычно является наиболее сложной частью безблокировочного алгоритма и часто требует значительных вычислительных затрат: замедляется не только помогающий поток, но и поток, которому оказывается помощь, если он все еще выполняется, из-за особенностей работы с общей памятью.

Lock freedom allows individual threads to starve but guarantees system wide throughput. An algorithm is lock free if, when the program threads are run for a sufficiently long time, at least one of the threads makes
progress (for some sensible definition of progress). All wait free algorithms are lock free. In particular, if one thread is suspended, then a lock free algorithm guarantees that the remaining threads can still make progress. Hence, if two threads can contend for the same mutex lock or spinlock, then the algorithm is not lock free. (If we suspend one thread that holds the lock, then the second thread will block.) An algorithm is lock free if infinitely often operation by some processors will succeed in a finite number of steps. For instance, if processors are trying to execute an operation, some of the processes will succeed in finishing the operation in a finite number of steps and others might fail and retry on failure. The difference between wait free and lock free is that wait free operation by each process is guaranteed to succeed in a finite number of steps, regardless of the other processors. In general, a lock free algorithm can run in four phases: completing one's own operation, assisting an obstructing operation, aborting an obstructing operation, and waiting. Completing one's own operation is complicated by the possibility of concurrent assistance and abortion, but is invariably the fastest path to completion. The decision about when to assist, abort or wait when an obstruction is met is the responsibility of a contention manager. This may be very simple (assist higher priority operations, abort lower priority ones), or may be more optimized to achieve better throughput, or lower the latency of prioritized operations. Correct concurrent assistance is typically the most complex part of a lock free algorithm, and often very costly to execute: not only does the assisting thread slow down, but thanks to the mechanics of shared memory, the thread being assisted will be slowed, too, if it is still running.

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

Свобода от блокировок — самая слабая естественная гарантия продвижения. Алгоритм считается свободным от блокировок, если в любой момент времени одна нить, выполняемая изолированно (то есть при приостановке всех конкурирующих нитей) в течение ограниченного числа шагов, сможет завершить свою операцию. Все алгоритмы, не использующие блокировки, свободны от блокировок. Свобода от блокировок требует лишь того, чтобы любую частично завершенную операцию можно было прервать и отменить внесенные изменения. Отказ от взаимной поддержки часто позволяет создать гораздо более простые алгоритмы, которые легче верифицировать. Предотвращение постоянных взаимных блокировок — задача менеджера конкуренции. Некоторые алгоритмы, свободные от блокировок, используют пару "маркеров согласованности" в структуре данных. Процессы, читающие структуру данных, сначала считывают один маркер согласованности, затем соответствующие данные во внутренний буфер, затем другой маркер и, наконец, сравнивают маркеры. Данные считаются согласованными, если оба маркера идентичны. Маркеры могут быть не идентичны, если чтение прерывается другим процессом, обновляющим структуру данных. В этом случае процесс отбрасывает данные из внутреннего буфера и повторяет попытку.