Транзакционная память в программном обеспечении: механизмы управления конкурентным доступом.

Введение

Механизм управления конкурентным доступом в программном обеспечении
В информатике транзакционная память программного обеспечения (STM) — это механизм управления конкурентным доступом, аналогичный транзакциям баз данных, используемый для контроля доступа к разделяемой памяти в параллельных вычислениях. Это альтернатива синхронизации на основе блокировок. STM — это стратегия, реализованная в программном обеспечении, а не как аппаратный компонент. Транзакция в данном контексте возникает, когда фрагмент кода выполняет последовательность операций чтения и записи в разделяемую память. Эти операции чтения и записи логически происходят в один момент времени; промежуточные состояния не видны другим (успешно завершенным) транзакциям. Идея обеспечения аппаратной поддержки транзакций впервые была предложена в статье Тома Найта 1986 года. Эта идея получила широкое распространение благодаря работам Мориса Эрлихи и Дж. Элиота Б. Мосса. В 1995 году Нир Шавит и Дэн Туиту расширили эту идею до транзакционной памяти, реализованной исключительно программными средствами (STM). С 2005 года STM является предметом интенсивных исследований, и поддержка практических реализаций постоянно растет.

Выступление

В отличие от методов блокировки, используемых в большинстве современных многопоточных приложений, STM часто очень оптимистичен: потоки завершают изменения в разделяемой памяти, не заботясь о том, что делают другие потоки, записывая каждое чтение и запись в журнал. Вместо того, чтобы возлагать на пишущий поток ответственность за то, чтобы он не повлиял негативно на другие выполняющиеся операции, эта ответственность ложится на читающий поток, который после завершения всей транзакции проверяет, не внесли ли другие потоки одновременно изменения в память, к которой он обращался ранее. Эта заключительная операция, в которой изменения транзакции проверяются, и, в случае успешной проверки, становятся постоянными, называется коммитом (commit). Транзакция также может быть прервана в любой момент, что приводит к откату или отмене всех ее предыдущих изменений. Если транзакцию невозможно зафиксировать из-за конфликтующих изменений, она обычно прерывается и перезапускается с самого начала, пока не будет успешно завершена. Преимущество этого оптимистичного подхода – повышенная степень параллелизма: ни один поток не должен ждать доступа к ресурсу, и различные потоки могут безопасно и одновременно изменять непересекающиеся части структуры данных, которые обычно защищались бы одним и тем же замком. Однако на практике системы STM также демонстрируют снижение производительности по сравнению с системами с мелкозернистой блокировкой на небольшом количестве процессоров (от 1 до 4, в зависимости от приложения). Это связано главным образом с накладными расходами на ведение журнала и временем, затрачиваемым на коммит транзакций. Даже в этом случае производительность обычно не более чем в два раза ниже. Сторонники STM считают, что эта потеря производительности оправдана концептуальными преимуществами STM. Теоретически, наихудшая пространственно-временная сложность n параллельных транзакций составляет O(n). Фактические требования зависят от деталей реализации (можно добиться раннего прерывания транзакций, чтобы избежать накладных расходов), но также будут случаи, хотя и редкие, когда алгоритмы, основанные на блокировках, имеют лучшую временную сложность, чем программная транзакционная память.

Unlike the locking techniques used in most modern multithreaded applications, STM is often very optimistic: a thread completes modifications to shared memory without regard for what other threads might be doing, recording every read and write that it is performing in a log. Instead of placing the onus on the writer to make sure it does not adversely affect other operations in progress, it is placed on the reader, who after completing an entire transaction verifies that other threads have not concurrently made changes to memory that it accessed in the past. This final operation, in which the changes of a transaction are validated and, if validation is successful, made permanent, is called a commit. A transaction may also abort at any time, causing all of its prior changes to be rolled back or undone. If a transaction cannot be committed due to conflicting changes, it is typically aborted and re executed from the beginning until it succeeds. The benefit of this optimistic approach is increased concurrency: no thread needs to wait for access to a resource, and different threads can safely and simultaneously modify disjoint parts of a data structure that would normally be protected under the same lock. However, in practice, STM systems also suffer a performance hit compared to fine grained lock based systems on small numbers of processors (1 to 4 depending on the application). This is due primarily to the overhead associated with maintaining the log and the time spent committing transactions. Even in this case performance is typically no worse than twice as slow. Advocates of STM believe this penalty is justified by the conceptual benefits of STM. Theoretically, the worst case space and time complexity of n concurrent transactions is O(n). Actual needs depend on implementation details (one can make transactions fail early enough to avoid overhead), but there will also be cases, albeit rare, where lock based algorithms have better time complexity than software transactional memory.

Концептуальные преимущества и недостатки

В дополнение к преимуществам производительности, STM значительно упрощает концептуальное понимание многопоточных программ и помогает сделать программы более удобными в сопровождении, работая в гармонии с существующими абстракциями высокого уровня, такими как объекты и модули. Программирование с использованием блокировок имеет ряд хорошо известных проблем, которые часто возникают на практике: блокировки требуют обдумывания перекрывающихся и частичных операций в удалённых и, казалось бы, не связанных между собой участках кода, что является сложной и подверженной ошибкам задачей. Блокировки требуют от программистов выработки политики блокировки для предотвращения взаимных блокировок, зависаний и других ситуаций, приводящих к отсутствию прогресса. Такие политики часто применяются неформально и ненадежны, а когда эти проблемы возникают, их коварно трудно воспроизвести и отладить. Блокировки могут приводить к инверсии приоритетов, когда высокоприоритетная нить вынуждена ждать низкоприоритетную нить, удерживающую исключительный доступ к необходимому ей ресурсу. В отличие от этого, концепция транзакции памяти гораздо проще, поскольку каждую транзакцию можно рассматривать в изоляции как однопоточное вычисление. Взаимные блокировки и зависания либо полностью предотвращаются, либо обрабатываются внешним менеджером транзакций, и программисту редко приходится об этом беспокоиться. Инверсия приоритетов всё ещё может быть проблемой, но высокоприоритетные транзакции могут прерывать конфликтующие низкоприоритетные транзакции, которые ещё не были зафиксированы. Однако необходимость повторных попыток и отмены транзакций ограничивает их поведение. Любая операция, выполняемая внутри транзакции, должна быть идемпотентной, поскольку транзакция может быть повторена. Кроме того, если операция имеет побочные эффекты, которые необходимо отменить в случае отмены транзакции, то должна быть предусмотрена соответствующая операция отката. Это делает многие операции ввода-вывода (I/O) сложными или невозможными для выполнения внутри транзакций. Обычно эти ограничения обходятся на практике путём создания буферов, в которых накапливаются необратимые операции и выполняются после успешного завершения транзакции. В Haskell это ограничение обеспечивается на этапе компиляции системой типов данных.

In addition to their performance benefits, STM greatly simplifies conceptual understanding of multithreaded programs and helps make programs more maintainable by working in harmony with existing high level abstractions such as objects and modules. Lock based programming has a number of well known problems that frequently arise in practice:

Locking requires thinking about overlapping operations and partial operations in distantly separated and seemingly unrelated sections of code, a task which is very difficult and error prone. Locking requires programmers to adopt a locking policy to prevent deadlock, livelock, and other failures to make progress. Such policies are often informally enforced and fallible, and when these issues arise they are insidiously difficult to reproduce and debug. Locking can lead to priority inversion, a phenomenon where a high priority thread is forced to wait for a low priority thread holding exclusive access to a resource that it needs. In contrast, the concept of a memory transaction is much simpler, because each transaction can be viewed in isolation as a single threaded computation. Deadlock and livelock are either prevented entirely or handled by an external transaction manager; the programmer need hardly worry about it. Priority inversion can still be an issue, but high priority transactions can abort conflicting lower priority transactions that have not already committed. However, the need to retry and abort transactions limits their behavior. Any operation performed within a transaction must be idempotent since a transaction might be retried. Additionally, if an operation has side effects that must be undone if the transaction is aborted, then a corresponding rollback operation must be included. This makes many input/output (I/O) operations difficult or impossible to perform within transactions. Such limits are typically overcome in practice by creating buffers that queue up the irreversible operations and perform them after the transaction succeeds. In Haskell, this limit is enforced at compile time by the data type system.

Композиционные операции

В 2005 году Тим Харрис, Саймон Марлоу, Саймон Пейтон Джонс и Морис Эрлихи описали систему STM, построенную на Concurrent Haskell, которая позволяет произвольно составлять атомные операции в более крупные атомные операции, что является полезной концепцией, невозможной в программировании с использованием блокировок. Цитируя авторов:

Возможно, самое фундаментальное возражение [ ] заключается в том, что программы, основанные на блокировках, не компонуются: корректные фрагменты могут завершиться неудачей при объединении. Например, рассмотрим хеш-таблицу с потокобезопасными операциями вставки и удаления. Теперь предположим, что мы хотим удалить элемент A из таблицы t1 и вставить его в таблицу t2; но промежуточное состояние (в котором ни одна из таблиц не содержит элемент) не должно быть видимо другим потокам. Если разработчик хеш-таблицы не предусмотрел такую возможность, удовлетворить это требование просто невозможно. [ ] Короче говоря, операции, которые корректны по отдельности (вставка, удаление), нельзя скомпоновать в более крупные корректные операции. — Tim Harris et al., "Composable Memory Transactions", Section 2: Background, pg.2

С STM эту проблему легко решить: достаточно обернуть две операции в транзакцию, чтобы объединенная операция стала атомарной. Единственная сложность заключается в том, что вызывающей стороне, не знающей деталей реализации компонентных методов, неясно, когда следует попытаться повторить транзакцию в случае неудачи. В ответ авторы предложили команду повтора (retry), которая использует журнал транзакций, сгенерированный неудачной транзакцией, для определения ячеек памяти, которые она читала, и автоматически повторяет транзакцию при изменении одной из этих ячеек, исходя из логики, что транзакция не будет вести себя иначе, пока не изменится хотя бы одно из этих значений. Авторы также предложили механизм для компоновки альтернатив – функцию `orElse`. Она выполняет одну транзакцию и, если эта транзакция выполняет повтор, запускает вторую. Если обе транзакции выполняют повтор, они обе повторяются снова, как только происходит соответствующее изменение. Эта возможность, сопоставимая с функциями, такими как вызов `select` сетевого интерфейса POSIX (Portable Operating System Interface), позволяет вызывающей стороне одновременно ожидать любое из ряда событий. Она также упрощает программные интерфейсы, например, предоставляя простой механизм для преобразования между блокирующими и неблокирующими операциями. Эта схема была реализована в компиляторе Glasgow Haskell.