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

Программная транзакционная память
Wiki letter w.svg
 Для улучшения этой статьи желательно?:
  • Проверить качество перевода с иностранного языка.

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

// Insert a node into a doubly linked list atomically
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 a time-based STM и Tanger to integrate STMs с C and 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 producing 32 or 64 битного кода для Intel или AMD процессоров. Реализует "атомное" ключевое слово, а также предоставляет способы украсить (declspec) определения функций для управления / разрешения на использование в "атомные" разделы.
  • 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 написанная командой ученых под руководством led by Michael L. Scott.

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 - Armin Rigo объясняет свой патч для CPython в an email to the pypy-dev list.
  • pypy-stm - надстройка над PyPy c рабочей реализацией интерпретатора Python 2.7, поддерживающая одновременное исполнение нитей существующих многопоточных приложений на разных ядрах CPU.

Scala

  • scala-stm framework, реализующий STM
  • ScalaSTM Проект предложен для STM и включает стандартную библиотеку Scala.
  • Akka STM the Akka framework содержит поддержку STM в Scala & Java

Smalltalk

  • GemStone/S [1] Transactional Memory Object Server для Smalltalk.

Другие языки

Примечания

  1. ↑ Tom Knight. An architecture for mostly functional languages. 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. Архивировано из первоисточника 2 сентября 2012. Проверено 9 июня 2007.

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Полезное


Смотреть что такое "Программная транзакционная память" в других словарях:

  • Снимок файловой системы — или снапшот (от англ. SnapShot, [мгновенный снимок])  моментальный снимок, копия файлов и директорий файловой системы на определённый момент времени. Содержание 1 Описание 2 Реализация …   Википедия

  • Snapshot (computer storage) — Снимок файловой системы или снапшот  моментальный снимок, копия файлов и директорий файловой системы на определённый момент времени. Содержание 1 Описание 2 Реализация 2.1 Управление томами …   Википедия

  • PyPy — Тип Интерпретатор и компилятор Python Написана на Python Операционная система Кроссплатформенный Последняя версия 1.9 (8 июня 201 …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»