Википедия

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

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

Характеристика

править

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

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

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

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

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

править

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

Lock-программирование содержит ряд известных проблем, которые часто возникают на практике:

  • Важно помнить о перекрывающихся операциях и частичных операциях в разделённых и кажущихся несвязанными частях кода — задача очень тяжёлая и чреватая ошибками.
  • Оно требует от программистов осваивать политику блокировки во избежание тупиков (Deadlock, Лайвлоков) и других проблем управления процессами. Такая политика часто приводится в исполнение произвольным образом и бывает ошибочна, и когда возникают проблемы, их трудно воспроизвести и отладить.
  • Это может привести к инверсии приоритетов — явлению, при котором высокоприоритетный поток вынужден ожидать низкоприоритетный поток, имеющий исключительный доступ к необходимому ресурсу.

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

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

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

править

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

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

— (Тим Харрис и др.,"Компонуемая операция обращения к памяти", раздел 2. История вопроса,с.2)

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

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

Эта схема была реализована в компиляторе языка Хаскель GHC.

Предлагаемый вспомогательный язык

править

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

// Атомарная вставка узла в двусвязный список
atomic {
    newNode->prev = node;
    newNode->next = node->next;
    node->next->prev = newNode;
    node->next = newNode;
}

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

atomic (queueSize > 0) {
    remove item from queue and use it
}

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

atomic {
    if (queueSize > 0) {
        remove item from queue and use it
    } else {
        retry
    }
}

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

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

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

править

SТМ может быть реализована как алгоритм без блокировок и с блокировками. Есть два типа блокировки.

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

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

Всё более популярным методом управления транзакционными конфликтами в транзакционной памяти, особенно в SТМ, является порядок совершения[англ.] (СО). Он используется для достижения упорядочиваемости безблокировочно (то есть без блокировки при конфликте операций и только с блокировкой при совершении транзакции) при помощи изменения порядка совершения транзакций (например, Рамадан и соавторы, 2009, и Жанг и соавторы, 2006). Упорядочиваемость является основой для корректного состояния транзакционной памяти (при выполнении параллельных транзакций). Уже были опубликованы десятки статей и патентов об STM с применением « порядка совершения».

«Жанг и соавторы, 2006» — патент США, несущий название «Программное обеспечение порядка совершения транзакций и управление конфликтами» (который ссылается на патент США 5701480 о порядке совершения). Приведём выдержки: 

"Разрабатываются различные технологии и методы для применения порядка совершения в системе программной транзакционной памяти. 
Система  программной транзакционной памяти снабжена функцией, чтобы предопределённый порядок совершения был применим для 
множества  операций. Предопределённый порядок совершения используется во время выполнения, чтобы установить порядок, в котором 
совершать транзакции в системе программной транзакционной памяти. Процесс управления конфликтами вызывается, когда происходит 
конфликт между первой и второй транзакциями. Предопределённый порядок совершения используется в процессе управления конфликтами, 
чтобы определить, какая из транзакций должна выиграть конфликт и получить разрешение на продолжение".

С порядком совершения желаемое свойство упорядоченности осуществляется путём совершения транзакций только в хронологическом порядке, совместимом с порядком по приоритету (как определено хронологическим порядком операций в конфликтах)

Реализации

править

SRTM было реализовано (разного качества и стабильности) на разных языках программирования. Таких, как:

C/C++

править
  • TBoost.STM (formerly DracoSTM) Совместные усилия CU-Boulder и Boost Libraries Group создали для C++ STM библиотеку, в первую очередь автором которого является Justin E. Gottschlich и Jeremy G. Siek.
  • TinySTM основанная на времени STM и Tanger для интеграции STM с C и C++ через LLVM.
  • Lightweight Transaction Library (LibLTX), реализация для С, (автор Robert Ennals) основной акцент сделан на эффективность. Реализация основывается на его статьях «Software Transactional Memory Should Not Be Obstruction-Free» и «Cache Sensitive Software Transactional Memory».
  • LibCMT, реализация с открытым кодом для C, сделанная Duilio Protti и основанная на «Composable Memory Transactions». Эта реализация также включает C# binding.
  • TARIFA является прототипом, который реализует ключевое слово «atomic» в C/C++.
  • Intel STM Compiler Prototype Edition реализация STM для C/C++ непосредственно в компиляторе (Intel Compiler) для Linux или Windows, генерирующем 32 или 64 битный код для процессоров Intel и AMD. Реализует ключевое слово «atomic», а также предоставляет способы декорации определения функций (declspec) для управления / разрешения на использование в «atomic» секциях.
  • stmmap реализация STM в C, основанная на разделяемой памяти. Предназначена для совместного использования памяти между потоками и / или процессами (а не только между потоками внутри процесса) с семантикой транзакций. В C++ реализована многопоточная версия данного аллокатора.
  • CTL реализация STM в C, основанная на TL2, но со многими расширениями и оптимизациями.
  • Several implementations by Tim Harris & Keir Fraser, основанная на идее из статей «Language Support for Lightweight Transactions», «Practical Lock Freedom», и предстоящей неопубликованной работе.
  • RSTM University of Rochester STM написанная командой учёных под руководством Michael L. Scott.
  • G++ 4.7 уже поддерживает STM для C/C++ прямо в компиляторе. Эта возможность до сих пор числится экспериментальной, но обеспечивает необходимую для тестирования функциональность.

C#

править
  • SXM, реализация для C# Microsoft Research. Documentation, Download page (недоступная ссылка).
  • LibCMT, реализация с открытым кодом, (Duilio Protti) базируемая на «Composable Memory Transactions». Реализация также включает C# binding.
  • NSTM, .NET Software Transactional Memory, написанное полностью на C#, предлагает вложенные транзакции и даже интеграцию с System.Transactions.
  • MikroKosmos A Verification-Oriented Model Implementation of an STM in C#.

Clojure

править
  • Clojure поддержка STM встроена в ядро языка.

Common Lisp

править
  • CL-STM мультиплатформенная реализация STM для Common Lisp.

Haskell

править

Java

править
  • SCAT research group реализация AtomJava.
  • JVSTM реализует концепцию Versioned Boxes, предложенную João Cachopo и António Rito Silva, членами Software Engineering Group — INESC-ID
  • XSTM является открытым исходным кодом для Java и .NET с расширяемой архитектурой. XSTM реализован в виде библиотеки, а также предоставляет расширения для уведомления об изменениях, настойчивости и репликации объектов.
  • Deuce Среда разработки для Java Software Transactional Memory, использующая байт-код.
  • Multiverse Java 1.6+ основанная на Software Transactional Memory (STM). Эта реализация, использует Multi Version Concurrency Control (MVCC) в качестве параллельного механизма контроля.
  • DSTM2 Sun Lab’s Dynamic STM библиотека.
  • ObjectFabric дистрибутив STM.

OCaml

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

Perl

править

Python

править
  • Durus простая, но полная и быстрая, STM реализация для Python, что позволяет использовать STM внутри одного процесса и STM в server/multiple клиент архитектуре. В дополнение к встроенной памяти формата существуют и другие, например Berkeley DB доступна здесь.
  • Fork of CPython with atomic locks Архивная копия от 25 марта 2012 на Wayback Machine — Armin Rigo объясняет свой патч для CPython в an email to the pypy-dev list.
  • pypy-stm Архивная копия от 5 декабря 2013 на Wayback Machine — надстройка над PyPy c рабочей реализацией интерпретатора Python 2.7, поддерживающая одновременное исполнение нитей существующих многопоточных приложений на разных ядрах CPU.

Scala

править
  • ScalaSTM Лёгкая библиотечная STM для Scala.
  • RadonSTM STM для Scala, которая была реализована как часть проекта Activate Framework

Smalltalk

править
  • GemStone/S [1] Transactional Memory Object Server для Smalltalk.

Другие языки

править

Примечания

править
  1. ↑ Tom Knight. An architecture for mostly functional languages. Архивная копия от 1 ноября 2013 на Wayback Machine Proceedings of the 1986 ACM conference on LISP and functional programming.
  2. ↑ Maurice Herlihy and J. Eliot B. Moss. Transactional memory: architectural support for lock-free data structures. Proceedings of the 20th annual international symposium on Computer architecture (ISCA '93). Volume 21, Issue 2, May 1993.
  3. ↑ Simon Peyton-Jones. Programming in the Age of Concurrency: Software Transactional Memory. Channel 9. Дата обращения: 9 июня 2007. Архивировано 2 сентября 2012 года.

Ссылки

править
Источник — https://ru.wiki.x.io/w/index.php?title=Программная_транзакционная_память&oldid=138176015