Программная транзакционная память - Software transactional memory

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

Спектакль

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эта схема была реализована в Компилятор Glasgow Haskell.

Предлагаемая языковая поддержка

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

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

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

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

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

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

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

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

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

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

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

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

Все чаще применяемый метод управления конфликтами транзакций в Транзакционная память, и особенно в STM, Заказ обязательств (также называется заказом фиксации; CO). Он используется для достижения сериализуемость[2] оптимистично (т. е. без блокировки в случае конфликта и только блокировки для фиксации) «порядком фиксации» (например, Рамадан и др. 2009 г.,[7] и Zhang et al. 2006 г.[8]). Сериализуемость - это основа корректности (параллельных транзакций и) транзакционной памяти. Уже опубликованы десятки статей STM о «порядке фиксации», и этот метод защищен рядом патентов.

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

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

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

атомный {if (x! = y) while (true) {}}
атомный {x ++; y ++;}
Транзакция А
Транзакция B

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

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

Реализации

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

C / C ++

  • TinySTM[мертвая ссылка ] временный STM и Танжер для интеграции STM с C и C ++ через LLVM.
  • В Легкая библиотека транзакций (LibLTX), реализация C Роберта Энналса, ориентированная на эффективность и основанная на его статьях «Программная транзакционная память не должна быть свободной от препятствий» и «Программная транзакционная память, чувствительная к кэшу».
  • LibCMT, реализация с открытым исходным кодом на C от Duilio Protti на основе «Composable Memory Transactions».[6] Реализация также включает Привязка C #.
  • ТАРИФА является прототипом, который переносит ключевое слово "atomic" в C / C ++ путем инструментирования вывода компилятора на ассемблер.
  • Версия прототипа компилятора Intel STM реализует STM для C / C ++ непосредственно в компиляторе (Intel Compiler) для Linux или Windows, создавая 32- или 64-битный код для процессоров Intel или AMD. Реализует ключевое слово atomic, а также предоставляет способы декорировать определения функций (declspec) для управления / авторизации использования в атомарных разделах. Существенная реализация в компиляторе с заявленной целью, позволяющая проводить крупномасштабные эксперименты в программе C / C ++ любого размера. Корпорация Intel выпустила четыре исследовательских версии этой специальной экспериментальной версии компилятора своего продукта.
  • stmmap Реализация STM на C, основанная на отображении разделяемой памяти. Он предназначен для разделения памяти между потоками и / или процессами (а не только между потоками внутри процесса) с транзакционной семантикой. Многопоточная версия его распределителя памяти написана на C ++.
  • CTL Реализация STM на C, основанная на TL2, но с множеством расширений и оптимизаций.
  • STM на основе блокировки TL2 от Масштабируемая синхронизация исследовательская группа в Sun Microsystems Laboratories, как указано в статье DISC 2006 «Transactional Locking II».
  • Несколько реализаций Тима Харриса и Кейра Фрейзера, основанный на идеях из его статей «Поддержка языков для облегченных транзакций», «Практическая свобода от блокировок» и предстоящей неопубликованной работы.
  • RSTM В Университет Рочестера СТМ, написанная группой исследователей во главе с Майкл Л. Скотт.
  • G ++ 4.7 теперь поддерживает STM для C / C ++ непосредственно в компиляторе. Эта функция по-прежнему указана как «экспериментальная», но может предоставлять необходимые функции для тестирования.
  • STM является частью платформы транзакций picotm для C[9]

C #

  • Экранированный Строгий и в основном свободный от препятствий STM для .NET, написанный на C #. Возможности включают в себя: условные транзакции, коммутируемые (с низким уровнем конфликтов) операции, типы транзакционных коллекций и автоматическое создание транзакционных прокси-подклассов для объектов POCO.
  • STMNet Чистый C #, легкий программный API транзакционной памяти с открытым исходным кодом.
  • SXM, реализация транзакций для C # от Microsoft Research. Документация, Страница загрузки Снято с производства.
  • LibCMT, реализация с открытым исходным кодом на C от Duilio Protti на основе «Composable Memory Transactions».[6] Реализация также включает Привязка C #.
  • NSTM, Программная транзакционная память .NET, полностью написанная на C #, предлагает действительно вложенные транзакции и даже интегрируется с System.Transactions.
  • МикроКосмос Реализация модели STM, ориентированной на проверку, на C #.
  • ОбъектТкань ср. Реализации Java.
  • Sasa.TM Чистая реализация программной транзакционной памяти на C #.

Clojure

  • Clojure имеет поддержку STM, встроенную в основной язык

Common Lisp

  • CL-STM Мультиплатформенная реализация STM для Common Lisp.
  • STMX Активно поддерживаемая библиотека параллелизма с открытым исходным кодом, обеспечивающая программное обеспечение, оборудование и транзакции гибридной памяти для Common Lisp.

Erlang

  • Mnesia Распределенная транзакционная СУБД в памяти, встроенная в Erlang / OTP, которая выполняет роль STM; Возможно, самая старая реализация STM в дикой природе.

F #

  • F # их через [1] FSharpX - образец на [2] F #

Groovy

Haskell

Ява

  • Исследовательская группа SCAT реализация AtomJava.
  • JVSTM реализует концепцию Версионные коробки предложено Жоао Качопо и Антониу Рито Силва, членами Группа программной инженерии - INESC-ID. Начиная с версии 2.0, JVSTM полностью свободен от блокировок.
  • Двойка Среда выполнения для транзакционной памяти программного обеспечения Java, использующая манипуляции с байтовым кодом.
  • Мультивселенная Реализация программной транзакционной памяти (STM) на основе Java 1.6+, которая использует Мультиверсионный контроль параллелизма (MVCC) как механизм управления параллелизмом.
  • DSTM2 Библиотека транзакционной памяти динамического программного обеспечения Sun Lab
  • ОбъектТкань это реализация с открытым исходным кодом для Java и .NET. Его можно превратить в распределенный STM с помощью механизма расширения. Другие расширения позволяют вести журнал, уведомлять об изменениях и сохранять.
  • ScalaSTM - STM на основе библиотеки, написанный на Scala, который дополнительно предоставляет ориентированный на Java API, позволяющий использовать с объектами Runnable и Callable.

JavaScript

  • AtomizeJS реализует распределенную программную транзакционную память для веб-браузеров с помощью одного сервера NodeJS для проверки результатов транзакций.

OCaml

  • coThreads, библиотека параллельного программирования OCaml, предлагает STM (изначально STMLib ) как модуль. Как и любые другие компоненты в этой библиотеке, модуль STM можно использовать единообразно с потоками уровня ВМ, системными потоками и процессами.

Perl

Python

  • Вилка CPython с атомарными замками - Армин Риго объясняет свой патч CPython в электронное письмо в список pypy-dev.
  • PyPy STM с потоками объявление от Армина Риго для PyPy.
  • Попович, Мирослав; Кордич, Бранислав (2014). «PSTM: транзакционная память программного обеспечения Python». 2014 22-й Телекоммуникационный форум Telfor (TELFOR). С. 1106–1109. Дои:10.1109 / TELFOR.2014.7034600. ISBN  978-1-4799-6191-7.
  • Кордич, Бранислав; Попович, Мирослав; Басичевич, Илия (2015). "DPM-PSTM: Программная транзакционная память Python с двумя портами памяти". 2015 4-я Восточноевропейская региональная конференция по разработке компьютерных систем. С. 126–129. Дои:10.1109 / ECBS-EERC.2015.28. ISBN  978-1-4673-7967-0.

Рубин

  • MagLev представляет собой реализацию интерпретатора Ruby, построенного на основе GemStone / S виртуальная машина
  • Параллельный Ruby это библиотека, предоставляющая параллельные функции для Ruby, включая STM
  • Ractor :: TVar - это реализация Ractor и Thread на Ruby 3.0. Фунты

Scala

  • ScalaSTM - Проект предложения вместе с эталонной реализацией CCSTM[10] для включения в стандартную библиотеку Scala
  • Akka STM - The Акка framework содержит поддержку STM как в Scala, так и в Java
  • MUTS - Транзакции Манчестерского университета для Scala[11]
  • ЗИО - Реализация в ZIO, вдохновленная STM API в Haskell.
  • Кошки СТМ - Расширение Кошки Эффект с программной реализацией транзакционной памяти, подобной той, что в Haskell stm упаковка.

Болтовня

  • GemStone / S [3] Сервер объектов транзакционной памяти для Smalltalk.
  • СТМ для Smalltalk с открытым исходным кодом (лицензия MIT) Pharo

Другие языки

Рекомендации

  1. ^ Том Найт. Архитектура в основном для функциональных языков. Материалы конференции ACM 1986 года по LISP и функциональному программированию.
  2. ^ а б Морис Херлихи и Дж. Элиот Б. Мосс. Транзакционная память: архитектурная поддержка структур данных без блокировки. Материалы 20-го ежегодного международного симпозиума по компьютерной архитектуре (ISCA '93). Том 21, выпуск 2, май 1993 г.
  3. ^ Нир Шавит и Дэн Тоуиту. Программная транзакционная память. Распределенных вычислений. Том 10, номер 2. Февраль 1997 г.
  4. ^ ""программное обеспечение транзакционной памяти "- Google Scholar". Получено 10 ноября 2013.
  5. ^ Саймон Пейтон-Джонс. "Программирование в эпоху параллелизма: транзакционная память программного обеспечения". Канал 9. Получено 2007-06-09.
  6. ^ а б c d е Harris, T .; Marlow, S .; Пейтон-Джонс, С.; Херлихи, М. (2005). «Транзакции составной памяти» (PDF). Материалы десятого симпозиума ACM SIGPLAN по принципам и практике параллельного программирования - PPoPP '05. п. 48. Дои:10.1145/1065944.1065952. ISBN  1595930809.
  7. ^ Хани Э. Рамадан, Индраджит Рой, Морис Херлихи, Эммет Витчел (2009): «Фиксация конфликтующих транзакций в STM» Материалы 14-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования (PPoPP '09), ISBN  978-1-60558-397-6
  8. ^ Лингли Чжан, Винод К. Гровер, Майкл М. Магрудер, Дэвид Детлефс, Джон Джозеф Даффи, Гетц Грефе (2006): Порядок фиксации транзакции программного обеспечения и управление конфликтами Патент США 7711678, выдан 04.05.2010.
  9. ^ «picotm - Портативный интегрированный настраиваемый и открытый менеджер транзакций».
  10. ^ Н.Г. Бронсон, Х. Чафи и К. Олюкотун, CCSTM: STM на основе библиотеки для Scala. Материалы семинара Scala Days 2010 (Лозанна).
  11. ^ Д. Гудман, Б. Хан, С. Хан, К. Киркхэм, М. Лухан и Ян Уотсон, MUTS: собственные конструкции Scala для программной транзакционной памяти. Материалы семинара Scala Days 2011 (Стэнфорд).

внешняя ссылка