Программная транзакционная память

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

Производительность

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

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

Однако на практике системы STM также страдают от снижения производительности по сравнению с системами на основе детальной блокировки на небольшом количестве процессоров (от 1 до 4 в зависимости от приложения). Это связано в первую очередь с накладными расходами, связанными с ведением журнала и временем, затраченным на фиксацию транзакций. Даже в этом случае производительность обычно не хуже, чем в два раза. Сторонники СТМ считают, что это наказание оправдано концептуальными преимуществами СТМ.

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

преимущества

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

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

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

Однако необходимость повторять и прерывать транзакции ограничивает их поведение. Любая операция, выполняемая внутри транзакции, должна быть идемпотентной, поскольку транзакция может быть повторена. Кроме того, если операция имеет побочные эффекты , которые необходимо отменить в случае прерывания транзакции, отката необходимо включить соответствующую операцию . Это ввода-вывода затрудняет или делает невозможным выполнение многих операций в рамках транзакций. На практике такие ограничения обычно преодолеваются путем создания буферов, которые ставят в очередь необратимые операции и выполняют их после успешного завершения транзакции. В Haskell это ограничение применяется во время компиляции системой данных типов .

Составные операции

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

Возможно, самое фундаментальное возражение [...] заключается в том, что программы, основанные на блокировках, не компонуют : правильные фрагменты могут потерпеть неудачу при объединении. Например, рассмотрим хеш-таблицу с потокобезопасными операциями вставки и удаления. Теперь предположим, что мы хотим удалить один элемент A из таблицы t1 и вставить его в таблицу t2; но промежуточное состояние (в котором ни одна таблица не содержит элемента) не должно быть видимым для других потоков. Если разработчик хеш-таблицы не предусмотрит эту необходимость, просто невозможно удовлетворить это требование. [...] Короче говоря, операции, которые являются правильными по отдельности (вставка, удаление), не могут быть объединены в более крупные правильные операции.
— Тим Харрис и др., «Транзакции с составной памятью», Раздел 2: Предыстория, стр. 2.

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

Авторы также предложили механизм композиции альтернатив , orElseфункция. Он запускает одну транзакцию и, если эта транзакция повторяет попытку , запускает вторую. Если оба повторят попытку, он попытается выполнить обе попытки снова, как только будет сделано соответствующее изменение. Эта возможность сравнима с такими функциями, как сетевой интерфейс переносимой операционной системы ( POSIX ). select()call, позволяет вызывающему абоненту одновременно ожидать любого из нескольких событий. Он также упрощает интерфейсы программирования, например, предоставляя простой механизм преобразования между блокирующими и неблокирующими операциями.

Эта схема реализована в компиляторе Glasgow Haskell Compiler .

языковая

Концептуальная простота STM позволяет программисту использовать их с помощью относительно простого синтаксиса языка . В книге Тима Харриса и Кейра Фрейзера «Языковая поддержка легких транзакций» была предложена идея использования классической условно критической области (CCR) для представления транзакций. В своей простейшей форме это просто «атомарный блок», блок кода, который логически возникает в один момент:

// Вставляем узел в двусвязный список атомарно 
  атомарно  { 
       новыйУзел->предыдущий = узел; 
       новыйNode->следующий = узел->следующий; 
       узел->следующий->предыдущий = новыйNode; 
       узел->следующий = новыйузел; 
   } 
 

Когда достигается конец блока, транзакция фиксируется, если это возможно, или прерывается и повторяется. (Это просто концептуальный пример, а не правильный код. Например, он ведет себя неправильно, если узел удаляется из списка во время транзакции.)

CCR также допускают защитное условие , которое позволяет транзакции ждать, пока у нее не появится работа:

 атомарный  (queueSize > 0) { 
       удалить элемент из очереди и использовать его 
   } 
 

Если условие не удовлетворено, менеджер транзакций будет ждать, пока другая транзакция не выполнит фиксацию , которая повлияет на условие, прежде чем повторить попытку. Эта слабая связь между производителями и потребителями повышает модульность по сравнению с явной передачей сигналов между потоками. «Транзакции составной памяти» пошел еще дальше с помощью своей команды повтора (обсуждаемой выше), которая может в любой момент прервать транзакцию и дождаться, пока некоторое значение, ранее прочитанное транзакцией, не будет изменено, прежде чем повторять попытку. Например:

 атомный  { 
       если (queueSize > 0) { 
           удалить элемент из очереди и использовать его 
       } еще { 
           повторить попытку 
       } 
   } 
 

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

Одна из проблем заключается в том, как ведут себя исключения, когда они распространяются за пределы транзакций. В разделе «Транзакции с составной памятью» авторы решили, что это должно прервать транзакцию, поскольку исключения обычно указывают на непредвиденные ошибки в Concurrent Haskell, но исключение может сохранять информацию, выделенную и прочитанную во время транзакции, в диагностических целях. Они подчеркивают, что другие проектные решения могут быть разумными в других условиях.

Транзакционная блокировка

STM может быть реализован как алгоритм без блокировки или использовать блокировку. Существует два типа схем блокировки: при блокировке во время встречи (Энналс, Саха и Харрис) запись в память выполняется путем сначала временного получения блокировки для данного места, прямой записи значения и регистрации его в журнале отмены. Блокировка времени фиксации блокирует ячейки памяти только на этапе фиксации.

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

Проблемы реализации

Одна из проблем реализации программной транзакционной памяти с оптимистическим чтением заключается в том, что незавершенная транзакция может прочитать противоречивое состояние (то есть прочитать смесь старых и новых значений, записанных другой транзакцией). Такая транзакция обречена на прерывание, если она когда-либо попытается зафиксироваться, поэтому это не нарушает условие согласованности, налагаемое транзакционной системой, но возможно, что это «временное» несогласованное состояние приведет к тому, что транзакция вызовет фатальное исключительное состояние, такое как как ошибка сегментации или даже войти в бесконечный цикл, как в следующем надуманном примере на рисунке 4 «Языковой поддержки для облегченных транзакций»:

атомный { если (х != у) в то время как (истина) { } } атомный { х++; у++; } Транзакция А Транзакция Б

При условии, что изначально x = y , ни одна из транзакций выше не изменяет этот инвариант, но возможно, что транзакция A прочитает x после того, как транзакция B обновит его, но прочитает y до того, как транзакция B обновит его, что приведет к входу в бесконечный цикл. Обычная стратегия решения этой проблемы — перехват любых фатальных исключений и прерывание любой недействительной транзакции.

Одним из способов решения этих проблем является обнаружение транзакций, которые выполняют незаконные операции или не могут их завершить и аккуратно прервать; другой подход — схема блокировки транзакций .

Практические реализации

• Хаскелл GHC
• С++ cpp_stm_free
• Ссылки на Clojure , портирован на node-stm
• Иди Кашмир
• Rust асинхронный-stm
• масштаб ЗИО
• OCaml Kcas