Войти
В информатике, программное обеспечение транзакционная память (STM ) является механизмом управления параллелизмом, аналогичным транзакциям базы данных для управления доступом к разделяемой памяти в параллельных вычислениях. Это альтернатива синхронизации на основе блокировки. STM - это стратегия, реализованная в программном обеспечении, а не в качестве аппаратного компонента. Транзакция в этом контексте происходит, когда часть кода выполняет серию операций чтения и записи в общую память. Эти операции чтения и записи логически происходят в один момент времени; промежуточные состояния не видны другим (успешным) транзакциям. Идея аппаратной поддержки транзакций возникла в статье 1986 года Тома Найта. Идею популяризировали Морис Херлихи и Дж. Элиот Б. Мосс. В 1995 году Нир Шавит и Дэн Туиту распространили эту идею на программную транзакционную память (STM). С 2005 года STM находится в центре интенсивных исследований, и поддержка практических внедрений растет.
В отличие от методов блокировки, используемых в большинстве современных многопоточных приложений, STM часто очень оптимистичен : поток завершает изменения в разделяемой памяти без учитывая, что могут делать другие потоки, записывая каждое чтение и запись, которые он выполняет, в журнал. Вместо того, чтобы возлагать бремя на писателя, чтобы убедиться, что он не повлияет отрицательно на другие выполняемые операции, он возлагается на читателя, который после завершения всей транзакции проверяет, что другие потоки одновременно не внесли изменения в память, к которой он получил доступ в мимо. Эта последняя операция, в которой изменения транзакции проверяются и, если проверка прошла успешно, становятся постоянными, называется фиксацией. Транзакция также может быть прервана в любое время, в результате чего все предыдущие изменения будут отменены или отменены. Если транзакция не может быть зафиксирована из-за конфликтующих изменений, она обычно прерывается и выполняется заново с самого начала, пока не завершится успешно.
Преимущество этого оптимистичного подхода заключается в увеличении параллелизма: ни одному потоку не нужно ждать доступа к ресурсу, и разные потоки могут безопасно и одновременно изменять непересекающиеся части структуры данных, которые обычно были бы защищены одной и той же блокировкой..
Однако на практике системы STM также страдают от снижения производительности по сравнению с системами на основе мелкозернистых блокировок на небольшом количестве процессоров (от 1 до 4 в зависимости от приложения). Это связано в первую очередь с накладными расходами, связанными с ведением журнала, и временем, затраченным на фиксацию транзакций. Даже в этом случае производительность обычно не хуже, чем вдвое. Сторонники STM считают, что это наказание оправдано концептуальными преимуществами STM.
Теоретически наихудший случай пространственно-временной сложности n параллельных транзакций составляет O (n). Фактические потребности зависят от деталей реализации (можно вызвать сбой транзакций достаточно рано, чтобы избежать накладных расходов), но также будут случаи, хотя и редкие, когда алгоритмы на основе блокировок имеют лучшую временную сложность, чем программная транзакционная память.
Помимо преимуществ в производительности, STM значительно упрощает концептуальное понимание многопоточных программ и помогает сделать программы более удобными в обслуживании, работая в гармонии с существующими высокоуровневыми абстракциями, такими как объекты и модули. Программирование на основе блокировок имеет ряд хорошо известных проблем, которые часто возникают на практике:
Напротив, концепция транзакции памяти намного проще, потому что каждую транзакцию можно рассматривать изолированно как однопоточное вычисление. Взаимоблокировки и живые блокировки либо полностью предотвращаются, либо обрабатываются внешним менеджером транзакций; программисту не о чем беспокоиться. Инверсия приоритета по-прежнему может быть проблемой, но транзакции с высоким приоритетом могут прервать конфликтующие транзакции с более низким приоритетом, которые еще не были зафиксированы.
С другой стороны, необходимость прервать неудачные транзакции также накладывает ограничения на поведение транзакций: они не могут выполнять какие-либо операции, которые нельзя отменить, включая большинство операций ввода-вывода. Такие ограничения обычно преодолеваются на практике путем создания буферов, которые ставят в очередь необратимые операции и выполняют их позже, вне какой-либо транзакции. В Haskell это ограничение применяется во время компиляции системой типов.
В 2005 году Саймон Марлоу, Саймон Пейтон Джонс и Морис Херлихи описали построенную систему STM на Concurrent Haskell, который позволяет объединять произвольные атомарные операции в более крупные атомарные операции - полезная концепция, невозможная при программировании на основе блокировок. Процитируем авторов:
Возможно, наиболее фундаментальное возражение [...] состоит в том, что программы, основанные на блокировках, не составляют: правильные фрагменты могут не работать при объединении. Например, рассмотрим хеш-таблицу с поточно-безопасными операциями вставки и удаления. Теперь предположим, что мы хотим удалить один элемент A из таблицы t1 и вставить его в таблицу t2; но промежуточное состояние (в котором ни одна таблица не содержит элемента) не должно быть видно другим потокам. Если разработчик хэш-таблицы не предвидит эту потребность, нет никакого способа удовлетворить это требование. [...] Короче говоря, операции, которые являются правильными по отдельности (вставка, удаление), не могут быть объединены в более крупные правильные операции.. - Тим Харрис и др., «Транзакции составной памяти», Раздел 2: Предпосылки, стр. 2
С помощью STM эту проблему легко решить: простое объединение двух операций в транзакцию делает объединенную операцию атомарной. Единственным камнем преткновения является то, что вызывающему абоненту, который не знает деталей реализации методов компонента, неясно, когда им следует попытаться повторно выполнить транзакцию в случае сбоя. В ответ авторы предложили команду retry, которая использует журнал транзакций, сгенерированный неудачной транзакцией, чтобы определить, какие ячейки памяти были прочитаны, и автоматически повторяет транзакцию, когда одна из этих ячеек изменяется, на основе логики что транзакция не будет вести себя иначе, пока не будет изменено хотя бы одно такое значение.
Авторы также предложили механизм композиции альтернатив, функцию илиElse . Он запускает одну транзакцию и, если эта транзакция повторяет попытку, запускает вторую. Если оба повторяют попытку, он пробует их снова, как только будет внесено соответствующее изменение. Это средство, сравнимое с такими функциями, как вызов POSIX network select (), позволяет вызывающему абоненту ожидать одновременно любого из нескольких событий. Он также упрощает программные интерфейсы, например, предоставляя простой механизм для преобразования между блокирующими и неблокирующими операциями.
Эта схема была реализована в компиляторе Glasgow Haskell.
Концептуальная простота STM позволяет представить их программисту с использованием относительно простого синтаксиса языка. В работе Тима Харриса и Кейра Фрейзера «Языковая поддержка облегченных транзакций» была предложена идея использования классической условной критической области (CCR) для представления транзакций. В своей простейшей форме это просто «атомарный блок», блок кода, который логически возникает в один момент:
// Вставляем узел в двусвязный список атомарно атомарно {newNode->prev = узел; newNode->следующий = узел->следующий; узел->следующий->предыдущий = новый узел; узел->следующий = новый узел; }Когда достигается конец блока, транзакция фиксируется, если возможно, или прерывается и повторяется. (Это просто концептуальный пример, а не правильный код. Например, он ведет себя некорректно, если узел удаляется из списка во время транзакции.)
CCR также допускают условие защиты, которое позволяет транзакции ждать, пока у него есть работа:
atomic (queueSize>0) {удалить элемент из очереди и использовать его}Если условие не выполняется, диспетчер транзакций будет ждать, пока не будет выполнена другая транзакция фиксация, которая влияет на условие перед повторной попыткой. Эта слабая связь между производителями и потребителями повышает модульность по сравнению с явной передачей сигналов между потоками. «Транзакции составной памяти» пошли дальше с помощью команды retry (обсужденной выше), которая может в любой момент прервать транзакцию и дождаться, пока какое-то значение, ранее считанное транзакцией, не изменится, прежде чем повторять попытку. Например:
atomic {if (queueSize>0) {удалить элемент из очереди и использовать его} else {retry }}Эта возможность динамически повторять попытку в конце транзакция упрощает модель программирования и открывает новые возможности.
Одна из проблем заключается в том, как ведут себя исключения, когда они распространяются вне транзакций. В «Транзакции составной памяти» авторы решили, что это должно прервать транзакцию, поскольку исключения обычно указывают на неожиданные ошибки в Concurrent Haskell, но что исключение может сохранить информацию, выделенную и прочитанную во время транзакции, для диагностических целей. Они подчеркивают, что другие проектные решения могут быть разумными в других условиях.
STM может быть реализован как алгоритм без блокировки или может использовать блокировку. Существует два типа схем блокировки: при блокировке по времени (Ennals, Saha и Harris) запись в память выполняется путем временного получения блокировки для данного местоположения, непосредственной записи значения и регистрации его в журнале отмены. Блокировка во время фиксации блокирует участки памяти только на этапе фиксации.
Схема времени фиксации, названная «Transactional Locking II», реализованная Дайсом, Шалевым и Шавитом, использует часы глобальной версии. Каждая транзакция начинается с чтения текущего значения часов и сохранения его как версии для чтения. Затем при каждом чтении или записи версия определенной области памяти сравнивается с версией чтения; и, если он больше, транзакция прерывается. Это гарантирует, что код выполняется на согласованном снимке памяти. Во время фиксации все места записи блокируются, а номера версий всех мест чтения и записи повторно проверяются. Наконец, глобальные часы версии увеличиваются, новые значения записи из журнала записываются обратно в память и маркируются новой версией часов.
Все более широко используемым методом управления конфликтами транзакций в транзакционной памяти, и особенно в STM, является упорядочение фиксации (также называемое упорядочением фиксации; CO). Он используется для оптимистического достижения сериализуемости (т.е. без блокировки в случае конфликта и только блокировки для фиксации) с помощью «порядка фиксации» (например, Ramadan et al. 2009 и Zhang et al. 2006). Сериализуемость - это основа корректности (параллельных транзакций и) транзакционной памяти. Уже опубликованы десятки статей STM о «порядке фиксации», и этот метод защищен рядом патентов.
В CO желаемое свойство сериализуемости достигается путем фиксации транзакций только в хронологическом порядке, который совместим с порядком приоритета (как определено хронологическим порядком операций в конфликтах) соответствующих транзакций. Чтобы обеспечить выполнение CO, необходимо использовать некоторую реализацию Универсального локального алгоритма CO. В приведенном выше реферате патента описана общая реализация алгоритма с заранее определенным порядком фиксации (это относится к категории «универсального алгоритма CO с ограничениями в реальном времени»).
Одна из проблем при реализации программной транзакционной памяти с оптимистичным чтением заключается в том, что неполная транзакция может считывать несогласованное состояние (то есть читать смесь старых и новых значений написано другой транзакцией). Такая транзакция обречена на прерывание, если она когда-либо попытается выполнить фиксацию, поэтому это не нарушает условие согласованности, обеспечиваемое транзакционной системой, но это «временное» несовместимое состояние может привести к тому, что транзакция вызовет фатальное исключительное состояние, такое как как ошибку сегментации или даже зайти в бесконечный цикл, как в следующем надуманном примере из рисунка 4 «Поддержка языков для облегченных транзакций»:
|
Если изначально x = y, ни одна из вышеуказанных транзакций не изменяет этот инвариант, но возможно, что транзакция A прочитает x после того, как транзакция B обновит его, но прочитает y до того, как транзакция B обновит его, заставляя его войти в бесконечный цикл. Обычная стратегия решения этой проблемы - перехват любых фатальных исключений и прерывание любой недопустимой транзакции.
Одним из способов решения этих проблем является обнаружение транзакций, которые выполняют недопустимые операции или не могут завершиться, и корректно прерывают их; другой подход - схема транзакционной блокировки.
Было выпущено несколько реализаций STM (с разным уровнем качества и стабильности), многие из которых под либеральными лицензиями. К ним относятся:
