Аппаратная поддержка транзакционной памяти

Усилия программистов, необходимые для использования параллелизма, оправдываются, если новый код выполняется лучше или обеспечивает более быструю реактивность, чем последовательный код. Хотя современные системы STM масштабируются при возрастании числа процессоров на многоядерном кристалле, накладные расходы программных систем являются существенными. Даже при использовании оптимизирующих компиляторов STM-поток может выполняться в 2-7 раз медленнее последовательного кода [22, 26].

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

Аппаратная транзакционная память.

Интерес к полностью аппаратной реализации TM (HTM) появился после публикации двух первых статей про TM: статей Найта (Knight) [16] и Херлихи и Мосса [13]. В системах HTM не требуется программный инструментарий для обработки адресов памяти внутри кода транзакции. Аппаратура управляет версиями данных и отслеживает конфликты прозрачным образом при выполнении программами обычных операций чтения и записи. Устранение инструментария позволяет сократить накладные расходы прикладной программы и снимает потребность в специализированных телах функций, так что их можно вызывать и внутри, и вне транзакции.

В системах HTM для реализации управления версиями и выявления конфликтов используются иерархия кэшей и протокол согласования кэшей. Через кэши проходят все операции чтения и записи, задаваемые процессором, в них может буферизоваться значительный объем данных, и их ассоциативная организация позволяет производить эффективный поиск. Во всех HTM модифицируются кэши первого уровня, но этот подход может быть распространен на кэши более высокого уровня, как частные, так и совместно используемые. Для иллюстрации организации и функционирования систем HTM ниже сравнительно подробно описывается архитектура TCC, и кратко упоминаются ключевые особенности альтернативных разработок.

TCC (Transactional Coherence and Consistency) – это система HTM с откладываемыми изменениями, в которой выявление конфликтов производится на стадии фиксации транзакций [21]. Для отслеживания наборов прочитанных и измененных объектов каждый блок кэша помечается служебными битами R и W, которые устанавливаются при первом доступе к блоку внутри транзакции по чтению или записи соответственно. Блоки кэша, входящие в набор измененных объектов, действуют как буфера записи и не выталкиваются в память до фиксации транзакции.

Для фиксации транзакций в TCC используется двухфазный протокол. Сначала аппаратура с использованием протокола поддержки согласованности кэшей получает монопольный доступ ко всем блокам кэша из набора измененных объектов.
Если этот шаг проходит успешно, транзакция считается валидированной. На втором шаге аппаратура одновременно сбрасывает в кэше все биты W, что приводит к автоматической фиксации всех изменений данной транзакции. Новые версии данных теперь глобально доступны всем процессорам на основе обычного протокола согласования кэшей многоядерного кристалла. Если валидация не удается, поскольку другой процессор тоже пытается зафиксировать некоторую конфликтующую транзакцию, аппаратура обращается к программному обработчику, который может аварийно завершить данную транзакцию или попытаться зафиксировать ее с применением традиционной политики управления транзакциями. Когда транзакция фиксируется или завершается аварийно, все служебные биты одновременно очищаются с использованием групповой операции сброса. При отсутствии конфликтов параллельно может фиксироваться несколько транзакций. Выявление конфликтов происходит, когда другие процессоры получают сообщения о согласовании кэшей от фиксируемой транзакции. Аппаратура проверяет, не содержится ли блок с указанным адресом в локальных кэшах. Если этот блок содержится в кэше, и для него установлены биты R или W, то это значит, что между фиксируемой и локальной транзакциями имеется конфликт «read-write» или «write-write» соответственно. Аппаратура генерирует сигнал программному обработчику, который аварийно завершает локальную транзакцию и потенциально повторяет ее с некоторой задержкой. Аналогичные аппаратные методы могут применяться для поддержки систем HTM с непосредственным обновлением памяти и ранним обнаружением конфликтов [23]. Для систем с непосредственным обновлением аппаратура прозрачным образом журнализует исходное значение блока памяти до его первой модификации транзакцией. Если транзакция завершается аварийно, этот журнал используется для обратного выполнения операций обновления. Для раннего обнаружения конфликтов аппаратура получает монопольный доступ к блоку кэша при первой записи и удерживает этот режим доступа до фиксации транзакции.

При наличии небольшого числа конфликтов почти все системы HTM ведут себя схожим образом. Если конфликтов много, то подход с откладываемыми изменениями и обнаружением конфликтов приводит к меньшему числу патологических сценариев, с которыми можно легко справиться с применением политики задержек [3]. Потери производительности HTM-нити обычно составляет от 2-х до 10-ти процентов по сравнению с производительностью не транзакционного кода. Система HTM может превосходить по производительности систему STM, основанную на блокировках, в четыре раза, а систему STM с аппаратным ускорением – в два раза [22]. Тем не менее, системам HTM свойственно несколько проблем, которые отсутствуют в реализациях STM. Кэши, используемые для поддержки наборов прочитанных и измененных объектов, а также версий данных, обладают конечной емкостью и при выполнении длинной транзакции могут переполниться. Состояние транзакции, сохраняемое в кэше, имеет большой объем, и его трудно сохранять и восстанавливать при обработке прерываний, переключении контекста и подкачке. Длинные транзакции могут быть редкими, но их все равно необходимо выполнять с сохранением свойств атомарности и изолированности. С точки зрения программистов недопустимо устанавливать зависящие от реализации ограничения на размеры транзакций. Простой механизм обработки переполнения кэша или системных событий заключается в том, чтобы в любом случае обеспечить возможность выполнения транзакции до конца [21]. При возникновении одного из упомянутых выше событий система HTM может начать обновлять память напрямую, без поддержки наборов прочитанных и измененных объектов и старых версий данных. Однако в это время не могут выполняться другие транзакции, поскольку более невозможно выявление конфликтов. Кроме того, непосредственные обновления памяти без журнализации препятствуют использованию в транзакции явных операторов аварийного завершения или повторного выполнения. Райвар (Rajwar) и др. предложили альтернативный подход VTM (Virtualized TM), который позволяет поддерживать атомарность и изолированность даже в тех случаях, когда транзакция прерывается событиями переполнения кэша или прерываниями [25].

VTM отображает ключевые структуры данных, описывающие выполнение транзакции (наборы прочитанных и измененных данных, буфера записи или журнал откатов), в виртуальную память, которая является практически неограниченной, и на которую не влияют системные прерывания. В аппаратных кэшах сохраняется рабочий набор этих структур данных. Разработчики VTM также предлагали использовать аппаратные сигнатуры для устранения избыточного поиска в структурах в виртуальной памяти. Наконец, для решения проблемы ограниченности аппаратных ресурсов можно использовать гибридную систему HTM–STM [7, 17]. Выполнение транзакции начинается в режиме HTM с использованием аппаратных механизмов выявления конфликтов и поддержки версий данных. Если ресурсы HTM исчерпываются, то транзакция откатывается и запускается заново в режиме STM с применением дополнительного инструментария. Для использования этого подхода требуется наличие двух вариантов каждой функции, но обеспечивается хорошая производительность для коротких транзакций. Проблемой гибридных систем является выявление конфликтов между одновременно выполняемыми HTM- и STM-транзакциями.

Аппаратно-программный интерфейс для транзакционной памяти.

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

Безотносительно к объему аппаратуры, используемой для поддержки TM, важно то, что системы HTM обеспечивают функциональные возможности, полезные при разработке практических программных моделей и сред выполнения. Значительная часть исследований в области HTM посвящена аппаратно-программному интерфейсу, который может поддерживать развитые программные средства. Макдональд (McDonald) и др. предложили четыре интерфейсных механизма для систем HTM [20]. Первый механизм – это двухфазный протокол фиксации, который на архитектурном уровне разделяет вилидацию транзакции и фиксацию выполненных ею изменений в памяти. Второй механизм представляет собой транзакционные обработчики, позволяющие программному обеспечению реагировать на существенные события, такие как обнаружение конфликта, фиксация или аварийное завершение. Шрираман (Shriraman) и другие предлагают аналогичный механизм «alert-on-update», который вызывает программный обработчик, когда аппаратура HTM обнаруживает конфликт, или в ней возникает переполнение [31]. Третий механизм заключается в поддержке замкнутых и открыто-вложенных транзакций. Открытая вкладываемость позволяет программному обеспечение прерывать выполняемую транзакцию и исполнять некоторый служебный код (например, системный вызов) с независимыми гарантиями атомарности и изолированности. Другие исследователи полагают, что для обслуживания системных вызовов и операций ввода-вывода достаточно приостанавливать HTM-транзакции [24, 32]. Тем не менее, если в служебном коде для доступа к совместно используемым данным используются транзакции, требования задержки выполнения транзакции не существенно отличаются от требований открыто-вложенных транзакций. Наконец, и Макдональд, и Шрираман предлагают несколько типов инструкций чтения и записи, позволяющих компиляторам отличать доступ к частным данным потока управления, неизменяемым и идемпотентным данным от доступа к истинно разделяемым данным. При наличии таких механизмов системы HTM могут поддерживать широкий диапазон программных средств, от средств традиционной синхронизации и ограниченного ввода-вывода внутри транзакций [5,32] до высокоуровневых моделей параллелизма, позволяющих избегать аварийного завершения транзакций при конфликтах по памяти, если не нарушается семантика уровня приложений [4].

Аппаратное ускорение STM.

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

Система STM с аппаратным ускорением (hardware-accelerated STM, HASTM), предложенная Саха (Saha) и др. [26], была первой системой, где для снижения накладных расходов инструментария STM использовалась аппаратная поддержка. Вспомогательная аппаратура позволяет программному обеспечению построить быстрые фильтры, которые могут ускорить действия, требуемые для поддержки наборов прочитанных объектов. HASTM обеспечивает для STM две возможности на основе поддержки битов пометки потоков управления на уровне блоков кэша. Во-первых, программное обеспечение может проверить, не был бы ранее установлен бит пометки для данного блока памяти, и не производилась ли запись в этот блок в другом потоке после того, как он был помечен (выявление конфликта). Во-вторых, программное обеспечение может узнать, производилась ли запись в других потоках управления в какой-нибудь из блоков памяти, помеченных данным потоком (валидация).

В HASTM предлагалось реализовывать биты пометки за счет использования дополнительных метаданных для каждого блока процессорных кэшей многоядерного кристалла. Аппаратура отслеживает, не стал ли недействительным какой-либо помеченный блок кэша по причине выталкивания из кэша или записи, произведенной в него из другого потока управления. STM использует биты пометки следующим образом.
При вызове подпрограммы чтения проверяется и устанавливается бит пометки для блока памяти, содержащего заголовок соответствующего объекта. Если бит пометки уже установлен, т.е. данная транзакция ранее уже обращалась к объекту, то этот объект не добавляется к набору прочитанных объектов. Для валидации транзакции STM выясняет с помощью аппаратуры, стал ли недействительным какой-либо помеченный блок кэша. Если это не произошло, то значит все объекты, к которым производился доступ через инструментарий STM, являлись частными для данного потока управления в течение всего выполнения транзакции, и никакая дальнейшая валидация не требуется. Если некоторые помеченные блоки стали недействительными, система STM должна производить программную валидацию, проверяя номера версий или наличие блокировок для всех объектов из набора прочитанных объектов. На этом дорогостоящем шаге валидации определяется, был ли помеченный блок вытолкнут из кэша из-за его ограниченной емкости или из-за наличия реального конфликта между одновременно выполняемыми транзакциями. HASTM допускает возникновение при выполнении транзакций системных событий, таких как прерывания, переключения контекста и страничные отказы, поскольку биты пометки действуют всего лишь как фильтр. Если обработка системного события приводит к выталкиванию некоторых помеченных блоков, то незавершенная транзакция может продолжить свое последовательное выполнение без аварийного завершения. К такой транзакции просто будет применена программная валидация до ее фиксации. Аналогично, HASTM допускает приостановку транзакций и их обследование такими компонентами, как сборщик мусора или отладчик, выполняемыми в другом потоке. Ускорить выявление конфликтов в STM можно и без модификации аппаратных кэшей. Кэши первого уровня обычно располагаются в критическом контуре процессора и взаимодействуют со сложными подсистемами, такими как подсистема поддержки протокола согласованности кэшей. Даже незначительные изменения в аппаратуре кэша могут повлиять на тактовую частоту процессора и повысить сложность его разработки и верификации.

Као Минь (Cao Minh) и др. [22] предложили подход к ускорению систем STM на основе сигнатур (SigTM). При этом подходе для пессимистического кодирования множеств прочитанных и измененных объектов программных транзакций используются аппаратные сигнатуры. Сигнатуры вычисляются вне кэшей с применением аппаратного фильтра Блюма. (Фильтр Блюма (Bloom filter) позволяет эффективно представлять надмножество элементов множества и быстро устанавливать, входит ли в это множество заданный элемент. Использование фильтров Блюма для обнаружения зависимостей при управлении выполнением нитей и транзакций было впервые предложено Сезом (Ceze) и др. [6].) Программный инструментарий обеспечивает фильтрам адреса объектов, читаемых или изменяемых внутри транзакции. Для распознавания конфликтов аппаратура компьютера отслеживает трафик протокола поддержки согласованности кэшей, обнаруживая в нем запросы монопольного доступа к блокам кэша, что означает изменение памяти. Анализируя сигнатуры транзакции, аппаратура проверяет, не может ли относиться адрес, содержащийся в запросе, к наборам прочитанных или измененных объектов этой транзакции. Если да, то считается, что обнаружен потенциальный конфликт, и система STM может либо аварийно завершить транзакцию, либо прибегнуть к программной валидации. И HASTM, и SigTM ускоряют поддержку наборов прочитанных объектов и валидацию в системах STM. Тем не менее, между этими подходами имеются архитектурные различия. SigTM кодирует наборы прочитанных и измененных объектов, размеры которых превышают размеры частных кэшей. Ограниченная емкость кэша и промахи при обнаружении конфликтов не приводят к потребности программной валидации, как при использовании HASTM. С другой стороны, в SigTM используются вероятностные сигнатуры, в результате чего истинные конфликты никогда не упускаются, но из-за наложения адресов в фильтрах Блюма могут выявляться ложные конфликты. Кроме того, аппаратные сигнатуры относительно компактны, и их легко обрабатывать, так что их можно сохранять и восстанавливать при переключении контекста и обработке прерываний.В HASTM биты пометки могут быть утрачены, если процессор используется для выполнения другой задачи. С другой стороны, в сигнатурах SigTM отражаются физические адреса, и содержимое сигнатуры становится недействительным при изменении отображения виртуальных страниц. Показано, что аппаратное ускорение управления наборами прочитанных объектов в два раза повышает производительность систем STM, основанных на блокировках, с непосредственным обновлением и отложенными изменениями [22, 26]. Возможны дополнительные усовершенствования с использованием аппаратных механизмов, которые поддерживают управление версиями объектов, изменяемых STM [31]. Однако, поскольку в большинстве программ читается гораздо больше объектов, чем изменяется, получаемое повышение производительности является незначительным.

Что такое транзакционная память?

Транзакция – это некоторая форма выполнения программ, перенятая от сообщества баз данных [8]. Параллельно исполняемые запросы конфликтуют, когда они читают и изменяют некоторый элемент базы данных, и возникающий конфликт может привести к ошибочному результату, который не мог бы получиться при последовательном выполнении этих запросов. Транзакции гарантируют, что все запросы произведут тот же самый результат, как если бы они выполнялись последовательно в некотором порядке (serially, «сериально»; это свойство называют «сериализуемостью» (serializability)). Декомпозиция семантики транзакции приводит к четырем требованиям, обычно называемым свойствами ACID: атомарность (atomicity), согласованность (consistency), изоляция (isolation) и долговечность (durability).

TM обеспечивает механизм легковесных транзакций для потоков управления, выполняемых в общем адресном пространстве. TM гарантирует атомарность и изолированность параллельно выполняемых задач. (Вообще говоря, согласованность и долговременность не обеспечиваются.) Атомарность гарантирует, что изменения состояния программы, производимые кодом, который выполняется в некоторой транзакции, являются невидимыми с точки зрения других, параллельно выполняемых транзакций. Другими словами, хотя код, выполняемый внутри транзакции, может изменять отдельные переменные посредством присваивания, в других вычислениях может наблюдаться состояние программы только либо непосредственно до, либо непосредственно после выполнения данной транзакции. Изолированность гарантирует, что параллельно выполняемые задачи не влияют на результат транзакции, так что транзакция производит один и тот же результат, как если бы не выполнялась никакая другая задача. Транзакции обеспечивают основу для построения параллельных абстракций, являющихся строительными блоками, которые можно комбинировать без знания их внутренних деталей, во многом подобно тому, как процедуры и объекты обеспечивают пригодные для компоновки абстракции для последовательного кода.

Литература

Adl-Tabatabai, A.R., Lewis, B.T., Menon, V., Murphy, R., Saha, B., and Shpeisman, T. Abstract compiler and runtime support for efficient software transactional memory. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (Ottawa, Ontario, Canada, 2006). ACM, NY 26–37. Blundell, C., Lewis, E.C., and Martin, M.M.K. Subtleties of transactional memory atomicity semantics. IEEE Computer Architecture Letters 5 (Nov. 2006). Bobba, J., Moore, K.E., Volos, H., Yen, L., Hill, M.D., Swift, M.M., and Wood, D.A. Performance pathologies in hardware transactional memory. In Proceedings of the 34th International Symposium on Computer Architecture (San Diego, CA, 2007). ACM, NY, 81–91. Carlstrom, B. D., McDonald, A., Carbin, M., Kozyrakis, C., and Olukotun, K. Transactional collection classes. In Proceedings of the 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (San Jose, CA, 2007). ACM, NY, 56–67. Carlstrom, B.D., McDonald, A., Chafi, H., Chung, J., Minh, C.C., Kozyrakis, C., and Olukotun, K. The Atomos transactional programming language. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (Ottawa, Ontario, Canada, 2006). ACM, NY, 1–13. Ceze, L., Tuck, J., Torrellas, J., and Cascaval, C. Bulk disambiguation of speculative threads in multiprocessors. In Proceedings of the 33rd International Symposium on Computer Architecture (Boston, MA, 2006). ACM, NY, 227–238. Damron, P., Fedorova, A., Lev, Y., Luchangco, V., Moir, M., and Nussbaum, D. Hybrid transactional memory. In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems (San Jose, CA, 2006). ACM, NY, 336–346. Gray, J. and Reuter, A. Transaction Processing: Concepts and Techniques. Morgan Kaufmann Publishers, San Francisco, CA, 1992. Grossman, D. The transactional memory / garbage collection analogy.
In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (Montreal, Canada, 2007). ACM, NY, 695–706. Guerraoui, R., Herlihy, M., and Pochon, B. Polymorphic contention management. In Proceedings of the 19th International Symposium on Distributed Computing (Krakow, Poland, 2005). Springer Verlag, 303–323. Harris, T., Marlow, S., Peyton-Jones, S., and Herlihy, M. Composable memory transactions. In Proceedings of the 10th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Chicago, IL, 2005), ACM, NY, 48–60. Harris, T., Plesko, M., Shinnar, A., and Tarditi, D. Optimizing memory transactions. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (Ottawa, Ontario, Canada, 2006). ACM, NY, 14–25. Herlihy, M. and Moss, J.E.B. Transactional memory: Architectural support for lock-free data structures. In Proceedings of the 20th International Symposium on Computer Architecture. ACM, 1993, 289–300. Herlihy, M., Luchangco, V., Moir, M., and Scherer III, W.N. Software transactional memory for dynamic-sized data structures. In Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing (Boston, MA, 2003), 92–101 Isard, M., and Birrell, A. Automatic mutual exclusion. In Proceeding of the Usenix 11th Workshop on Hot Topics in Operating Systems (San Diego, CA, 2007). Knight, T.F. An architecture for mostly functional languages. In Proceedings of the 1986 ACM Lisp and Functional Programming Conference. ACM, NY. Kumar, S., Chu, M., Hughes, C.J., Kundu, P., and Nguyen, A. Hybrid transactional memory. In Proceedings of the 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM, NY, 2006, 209–220. Larus, J.R. and Rajwar, R. Transactional Memory. Morgan & Claypool, 2006. Lomet, D.B. Process structuring, synchronization, and recovery using atomic actions.

In Proceedings of the ACM Conference on Language Design for Reliable Software (Raleigh, NC, 1977). ACM, NY, 128–137. McDonald, A., Chung, J., Brian, D.C., Minh, C.C., Chafi, H., Kozyrakis, C., and Olukotun, K. Architectural semantics for practical transactional memory. In Proceedings of the 33rd International Symposium on Computer Architecture. ACM, 2006, 53–65. McDonald, A., Chung, J., Chafi, H., Cao Minh, C., Carlstrom, B.D., Hammond, L., Kozyrakis, C., and Olukotun, K. Characterization of TCC on chip-multiprocessors. In Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques. (St Louis, MO, 2005). IEEE, 63–74. Minh, C. C., Trautmann, M., Chung, J., McDonald, A., Bronson, N., Casper, J., Kozyrakis, C., and Olukotun, K. An effective hybrid transactional memory system with strong isolation guarantees. In Proceedings of the 34th International Symposium on Computer Architecture (San Diego, CA, 2007) ACM, NY, 69–80. Moore, K.E., Bobba, J., Moravan, M.J., Hill, M.D., and Wood, D.A. LogTM: Log-based transactional memory. In Proceedings of the 12th International Symposium on High-Performance Computer Architecture (Austin, TX, 2006). IEEE, 254–265. Moravan, M.J., Bobba, J., Moore, K.E., Yen, L., Hill, M.D., Liblit, B., Swift, M.M., and Wood, D.A. Supporting Nested Transactional Memory in LogTM. Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems (San Jose, CA, 2006). ACM, NY, 359–370. Rajwar, R., Herlihy, M., and Lai, K. Virtualizing transactional memory. In Proceedings of the 32nd International Symposium on Computer Architecture (Madison, WI, 2005). ACM. NY, 494–505. Saha, B., Adl-Tabatabai, A. R., and Jacobson, Q. Architectural support for software transactional memory. In Proceedings of the 39th International Symposium on Microarchitecture (Orlando, FL, 2006). IEEE, 185–196. Saha, B., Adl-Tabatabai, A.R., Hudson, R.L., Minh, C.C., and Hertzberg, B.

McRT-STM: A high performance software transactional memory system for a multi-core runtime. In Proceedings of the 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (2006). ACM, NY, 187–197. Scherer III, W.N., and Scott, M.L. Advanced contention management for dynamic software transactional memory. In Proceedings of the Twentyfourth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (Las Vegas, NV, 2005). ACM Press, 240–248. Shavit, N. and Touitou, D. Software transactional memory . In Proceedings of the 14th ACM Symposium on Principles of Distributed Computing (Ottawa, Canada, 1995). ACM, NY, 204–213. Shpeisman, T., Menon, V., Adl-Tabatabai, A.-R., Balensiefer, S., Grossman, D., Hudson, R.L., Moore, K.F., and Saha, B. Enforcing isolation and ordering in STM. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation (San Diego, CA, 2007). ACM, NY, 78–88. Shriraman, A., Spear, M.F., Hossain, H., Marathe, V.J., Dwarkadas, S., and Scott, M.L. An integrated hardware-software approach to flexible transactional memory. In Proceedings of the 34th International Symposium on Computer Architecture (San Diego, CA, 2007). ACM, NY, 104–115. Zilles, C. and Baugh, L. Extending hardware transactional memory to support nonbusy waiting and nontransactional actions. In Proceedings of the First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (Ottawa, Canada, 2006). ACM, NY.

Журнал Communications of the ACM когда-то (лет 30 тому назад) был одним из лучших журналов в области аппаратуры и программного обеспечения компьютеров. В нем печатались статьи, которые оказывали огромное влияние на специалистов, преподавателей и студентов. Достаточно вспомнить статью Питера Деннинга об алгоритме управления виртуальной памятью на основе концепции рабочих наборов (P.J. Denning. The working set model for program behavior. Communications of the ACM, Volume 11, № 5, 1968) и основополагающую статью Дениса Ритчи и Кена Томпсона об операционной системе UNIX (D. M. Ritchie, K. Thompson. The Unix Time-Sharing System. Communications of the ACM, Volume 17, № 7, 1974). Начиная примерно с середины 1980-х журнал становился все скучнее и скучнее, и в новом тысячелетии в нем вообще стало трудно найти что-нибудь интересное. Однако ACM нашла в себе силы возродить журнал. С июля 2008-го года Communications of the ACM выходит в новом формате и наполнен интересными статьями.

Одну из этих статей я решил пересказать. По всей видимости, авторы статьи правы, утверждая, что транзакционная память может оказаться именно тем подходом, которого не хватает программистам для создания программ, эффективно использующим возможности многоядерных процессоров. Не могу об этом судить авторитетно, поскольку не являюсь специалистом в области параллельного программирования. Но мне кажется (и здесь мое мнение совпадает с мнением Майкла Стоунбрейкера, см. мой пересказ статьи OLTP в Зазеркалье), что технология транзакционной памяти может оказаться очень полезной для реализации систем управления базами данных в основной памяти в многоядерных архитектурах.

Транзакционная память пока не заняла свое место на коммерческом рынке, но я считаю, что интересно познакомиться с теми подходами к ее организации, которые существуют в настоящее время. Следует иметь в виду, что статья Ляруса и Казиракиса является кратким обзором достаточно сложных методов, для полного понимания которых нужно читать соответствующие полные статьи. Мне удалось найти в открытом доступе в Internet большую часть статей, на которые ссылаются Лярус и Казиракис, и я рекомендую вам обратить на них внимание.

Сергей Кузнецов

Ограничения транзакционной памяти.

Транзакции сами по себе не могут заменить всю синхронизацию в параллельной программе [2]. Кроме взаимного исключения, синхронизация часто используется для координации независимых задач, например, путем обеспечения средств, позволяющих одной задаче дожидаться окончания другой задачи или ограничивающих число потоков управления, в которых исполняется некоторая программа.

Сами по себе транзакции не слишком помогают в координации независимых задач. Например, рассмотрим взаимосвязь программ «производитель-потребитель», когда одна задача пишет значения, которые читаются другой задачей. Транзакции могут гарантировать, что задачи, обращающиеся к одним и тем же ресурсам, не помешают друг другу. Однако схема, требуемая в данном случае, слишком дорого реализуется с использованием транзакций, назначением которых является как раз предотвращение взаимодействия задач. Если транзакция-потребитель обнаруживает, что читать еще нечего, она может только лишь аварийно завершиться и повторить попытку чтения позже. Активное ожидание (busy waiting) с использованием аварийного завершения транзакции неэффективно, поскольку при аварийном завершении транзакции «откатываются» (roll back) все проделанные ей вычисления. Было бы лучше, если бы производитель мог подать сигнал потребителю, когда значение станет готовым для чтения. Однако, поскольку в соответствии с семантикой транзакций сигнал, поданный в одной транзакции, является невидимым в других транзакциях, во многих системах TM обеспечивается механизм предохранителей (guard), который не дает транзакции начаться до тех пор, пока соответствующий ей предикат не примет значение true.

В Haskell TM поддерживаются конструкции retry и orElse, первая из которых позволяет транзакции дождаться возникновения некоторого события, а вторая – упорядочить выполнение двух транзакций [11]. Выполнение оператора retry приводит к аварийному завершению включающей его транзакции. Она не может быть выполнена повторно до тех пор, пока не изменится значение переменной, прочитанной перед выполнением retry.
Это позволяет избежать использования наиболее грубой формы активного ожидания, при котором транзакция повторно считывает неизменившееся значение и аварийно завершается. Конструкция orElse обеспечивает возможность компоновать две транзакции, позволяя второй транзакции выполняться только в том случае, когда первая завершается аварийно. Этот распространенный сценарий трудно реализовать каким-либо другим способом, поскольку аварийное завершение и повторное выполнение транзакции происходят прозрачно для всех остальных частей программы. Плюсы и минусы программной модели TM, а также ее прагматика все еще до конца не понятны. Например, активные споры ведутся относительно вложенных транзакций. Предположим, что в коде, выполняемом в транзакции O, вызывается библиотечная подпрограмма, в которой начинается собственная транзакция I. Должны ли иметься какие-то способы взаимодействия этих транзакций, и как это влияет на реализацию TM и методику построения модульного программного обеспечения и библиотек? Пусть транзакция I успешно завершается. Должны ли ее результаты быть видимы только коду транзакции O, или и другим потокам управления тоже (открытая вложенность)? При выборе второго варианта, что произойдет, если транзакция O завершится аварийным образом? Аналогично, если аварийно завершится транзакция I, должно ли это привести к завершению и транзакции O, или же внутренняя транзакция должна откатиться и перезапуститься независимым образом? Наконец, производительность систем TM пока еще не слишком высока для их широкого использования. Программные системы TM (software TM system, STM) существенно нагружают код, выполняемый внутри транзакции, что уменьшает преимущества по производительности параллельных компьютеров. Аппаратные системы TM (hardware TM systems, HTM) могут снизить накладные расходы, но их коммерческие образцы только начинают появляться, и большинство систем HTM не справляется с обработкой крупных транзакций. Применение более совершенных методов реализации, вероятно, позволит улучшить оба вида систем, и в этой области ведутся активные исследования.

Открытые проблемы

Кроме обсуждавшихся выше реализационных проблем, в области TM имеется ряд проблем, являющихся предметом активных исследований. Одной из серьезных трудностей оптимистической TM является то, что в результате конфликта может откатиться транзакция, выполняющая операцию ввода-вывода. Под вводом-выводом в данном случае понимается любое взаимодействие с миром, расположенным вне системы TM. Если транзакция аварийно завершается, ее операции ввода-вывода также требуется откатить, что в общем случае сделать очень трудно, если не невозможно. Некоторые откаты позволяет производить буферизация данных, прочитанных или записанных транзакцией, но буферизация не удается даже в простых ситуациях, например, когда транзакция выдает приглашение и ожидает ввода данных от пользователя. Более общий подход состоит в назначении одной из транзакций привилегированного статуса, которой всегда гарантируется возможность завершения в ущерб всем конфликтующим с ней транзакцией. Ввод-вывод может производиться только привилегированной транзакцией (но эта привилегия может передаваться между транзакциями), что, к сожалению, ограничивает объем ввода-вывода, который может произвести программа.

Другой важной проблемой является сильная и слабая атомарность. В системах STM, вообще говоря, реализуется слабая атомарность, когда не транзакционный код не изолируется от кода транзакций. С другой стороны, в системах HTM реализуется сильная атомарность, обеспечивающая более детерминированную программную модель, в которой не транзакционный код не влияет на атомарность транзакции. Из-за этого различия возникает несколько проблем. Кроме потребности в ответе на основной вопрос (какая модель является лучшим базисом для написания программного обеспечения?), это семантическое различие затрудняет разработку программного обеспечения, которое может выполняться в системах обоих типов. Наименьшим общим знаменателем является слабая модель, но ошибочные программы будут производить на разных системах отличающиеся результаты. Альтернативная точка зрения состоит в том, что доступ к общим данным в двух потоках управления без синхронизации вообще является ошибкой, и если только в одном потоке выполняется транзакция, то это не является достаточной синхронизацией между потоками.
Следовательно, языки программирования, инструментальные средства, системы поддержки времени выполнения или аппаратура должны предотвращать или выявлять совместную работу с данными без синхронизации транзакционного и не транзакционного кода, и программисты должны исправлять этот дефект. Системы со слабой атомарностью также сталкиваются с трудностями, когда некоторый объект совместно используется транзакционным и не транзакционным кодом [30]. Когда некоторый поток управления делает некоторый объект видимым для других потоков (например, путем добавления его к некоторой глобальной очереди), происходит публикация этого объекта. Когда некоторый поток управления удаляет некоторый объект из разделяемого глобального пространства, происходит приватизация этого объекта. Частные (приватные) данные можно обрабатывать за пределами транзакции без синхронизации, но изменение состояния объекта с публичного на частный и наоборот должно координироваться системой TM, чтобы она не пыталась откатить состояние объекта, в то время как другой поток управления предполагает, что имеет к этому объекту исключительный, частный доступ. Наконец, TM должна сосуществовать и взаимодействовать с существующими программами и библиотеками. Непрактично требовать от программистов начать все с начала и полльзоваться новым набором транзакционных библиотек, чтобы использовать преимущества TM. Должна иметься возможность корректно исполнять в транзакции существующий последовательный код, возможно, с небольшим числом аннотаций и специальной компиляцией. Существующий параллельный код, в котором используются блокировки и другие формы синхронизации, должен продолжать выполнять правильно, даже если в некоторых потоках управления выполняются транзакции.

По мере развития компьютеров меняется

По мере развития компьютеров меняется и программирование. В последние несколько лет начался переход от последовательных к параллельным вычислениям в процессорах, используемых в большинстве серверов, персональных и мобильных компьютеров. Этот переход означает конец замечательного 30-летнего периода, в котором достижения полупроводниковой технологии и компьютерной архитектуры позволяли ежегодно повышать производительность последовательных процессоров на 40-50%. Постоянный рост производительности шел на пользу всему программному обеспечению, и этот прогресс являлся ключевым фактором, влиявшим на распространение программного обеспечения во всех областях современной жизни. Эта замечательная эпоха подошла к концу, когда практические ограничения на рассеяние мощности микропроцессоров сделали невозможным постоянное повышение тактовой частоты, и ограниченный параллелизм на уровне команд перестал оправдывать непрерывно возрастающую сложность архитектур процессоров. Эра закончилась не потому, что перестал действовать закон Мура. Технология полупроводников все еще в состоянии удваивать число транзисторов в кристалле через каждые два года. Однако теперь это все возрастающее количество транзисторов приводит к увеличению числа независимых процессоров на кристалле, а не ускоряет работу отдельного процессора. Результирующая архитектура компьютера, получившая название многоядерной, состоит в том, что на кристалле располагается несколько независимых процессоров (ядер), которые общаются через общую основную память. Сегодня общераспространенными являются двухядерные кристаллы, на рынок поступают черырехядерные процессоры, и имеются все основания полагать, что в течение ряда поколений кристаллов число ядер будет продолжать удваиваться. С одной стороны, хорошо, что пиковая производительность многоядерного компьютера удваивается при каждом удвоении числа ядер. С другой стороны, для достижения этой производительности требуется, чтобы программа распараллеливалась и масштабировалась при возрастании числа процессоров.
Сегодня существует не так уж много программ, способных к эффективному распараллеливанию. Частично это объясняется тем, что у большинства программистов не было доступа к параллельным компьютерам, распространенность которых была ограничена прикладными областями с крупными, естественным образом параллельными рабочими нагрузками. Параллельные компьютеры использовались, главным образом, для выполнения вычислений огромного масштаба. Поскольку основным течением было последовательное программирование, в большинстве существующих языков программирования, библиотек, паттернов проектирования и учебных курсов проблемы параллельного программирования просто не затрагивались. Очевидно, эта ситуация должна измениться до того, как программисты в массовом порядке начнут писать параллельные программы для многоядерных процессоров. Основная проблема состоит в том, чтобы найти лучшие абстракции для выражения параллельных вычислений и написания параллельных программ. Параллельному программированию свойственны все трудности последовательного программирования, но к ним добавляется трудная проблема координации взаимодействия параллельно выполняемых задач. Сегодня в большинстве параллельных программ используются низкоуровневые программные конструкции, которые являются всего лишь тонкой облицовкой используемых аппаратных средств. В чисто этих конструкций входят потоки управления (thread), представляющие собой абстрактные процессоры, и явная синхронизация (например, блокировки, семафоры и мониторы) для координации выполнения потоков. Опыт прошлых лет показывает, что параллельные программы, написанные с использованием этих конструкций, трудно разрабатывать, кодировать, отлаживать, сопровождать, и, в добавление ко всему этому, они часто не очень хорошо работают. Транзакционная память (transactional memory, TM), предложенная Ломе (Lomet) [19] и впервые практически реализованная Херлихи (Herlihy) и Моссом (Moss) [13], – это новая программная конструкция, обеспечивающая высокоуровневую абстракцию для написания параллельных программ.В последние несколько лет она привлекает значительный интерес, поскольку транзакции в течение долгого времени используются в системах баз данных для изоляции параллельных активностей. TM предоставляет механизм, позволяющий частям программы выполняться в изоляции, не обращая внимания на другие параллельно выполняемые задачи. Программист может обосновывать корректность кода внутри транзакции и не вынужден заботиться в сложных взаимодействиях с другими, параллельно выполняемыми частями транзакции. TM обеспечивает многообещающий, но еще не проверенный механизм для совершенствования параллельного программирования.

Преимущества транзакционной памяти.

При параллельном программировании приходится сталкиваться со многими трудностями, но одной из наиболее серьезных проблем при написании корректного кода является координация доступа к данным, совместно используемым в нескольких потоках управления. Последствиями попыток обеспечить взаимное исключение со слишком слабой или слишком сильной синхронизацией являются конфликты при доступе к данным (data race), синхронизационные тупики (deadlock) и плохая масштабируемость. TM обеспечивает более простую альтернативу взаимного исключения, снимая ношу корректной синхронизации с программиста и возлагая ее на систему TM [9]. Теоретически от разработчика программы требуется только обозначить последовательность операций, которая должна будет выполняться атомарно по отношению к другим параллельно выполняющимся потокам управления. Это обеспечивается системой TM на основе многочисленных механизмов, описываемых в этой статье.

Харрис (Harris) и Пейтон-Джонс (Peyton-Jones) [11] утверждают, что, помимо обеспечения улучшенной программной абстракции, транзакции также делают синхронизацию компонуемой, что позволяет конструировать абстракции параллельного программирования. Программная абстракция является компонуемой, если ее можно корректно комбинировать с другими абстракциями без потребности понимания ее функционирования.

Простая схема блокировок не является компонуемой. Рассмотрим, например, класс, реализующий набор банковских счетов. В этом классе имеются две безопасные для потоков управления операции Deposit и Withdraw, предназначенные для зачисления денег на счет и снятия их со счета соответственно. Предположим, что требуется произвести композицию этих операций в безопасную для потоков операцию Transfer, которая переводит деньги с одного счета на другой. Промежуточное состояние, когда деньги сняты с одного счета и не зачислены на другой счет, не должно быть видимым для других потоков управления (т.е. перевод должен быть атомарным). Поскольку в операциях Deposit и Withdraw счет блокируется только на время их выполнения, для правильной реализации операции Transfer требуется понять дисциплину блокировок, используемую в данном классе, и изменить ее путем добавления метода для блокировки всех счетов или какого-нибудь одного счета. Последний подход позволяет выполнять параллельно операции переводов с разными счетами, но при этом появляется возможность синхронизационного тупика, если выполнение операции перевода со счета A на счет B перекрывается во времени с выполнением операции перевода со счета B на счет A.

TM позволяет прямо компоновать операции. Каждая из операций Deposit и Withdraw выполняется в некоторой транзакции, чтобы защитить их работу с общими данными. Операция Transfer также выполняется в некоторой транзакции, которая превращает используемые в ней исходные операции Deposit и Withdraw в единое атомарное действие.

Программная модель TM.

Программная модель обеспечивает логическое обоснование конструкций языков программирования и методологические принципы конструирования программ. Подобно многим другим аспектам TM, ее программная модель все еще является предметом активных исследований. В большинстве систем TM обеспечиваются простые атомарные операторы, выполняющие блок кода (и вызываемые в нем подпрограммы) как транзакцию. Атомарный блок изолирует код от параллельно выполняемых нитей, но блок не заменяет общую синхронизацию, обеспечиваемую, например, семафорами или условными переменными [2]. В частности, атомарные блоки сами по себе не обеспечивают средства для координации кода, выполняемого в параллельных потоках управления.

В отличие от этого, автоматическое взаимное исключение (automatic mutual exclusion, AME) выворачивает транзакционную модель «на изнанку» за счет выполнения большей части программы в транзакциях [15]. AME поддерживает асинхронное программирование, в котором при вызове любой функции начинается одно или несколько асинхронных вычислений, и затем для получения результатов этих вызовов требуются рандеву. Эта программная модель часто применяется для решения проблемы непредвиденных задержек в управляемых пользователями и распределенных системах. Атомарность, обеспечиваемая транзакциями, гарантирует, что асинхронное вычисление, выполняемое с непредсказуемой скоростью, не мешает выполнению других асинхронных вычислений.

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

. В первой статье Шавита (Shavit) и Туиту (Touitou), посвященной STM [29], было показано, что можно полностью программным образом реализовать свободные от блокировок (lock-free) атомарные операции над несколькими переменными, но для этого в программе нужно заранее объявить, к каким ячейкам памяти будет обращаться данная транзакция.

Описанная Херлихи и др. в [14] система Dynamic STM (DSTM) была первой системой STM, в которой это требование снималось. DSTM является системой STM с гранулированностью на уровне объектов и откладываемыми изменениями (deferred-update). Это означает, что транзакция модифицирует частные копии объектов и делает видимыми изменения другим транзакциям при своей фиксации. Транзакция имеет монопольный доступ к этим копиям без синхронизации. Однако к исходным объектам могут обращаться другие транзакции, что приводит к возникновению логического конфликта, распознаваемого системой STM и разрешаемого путем аварийного завершения одной из транзакций.

Система STM может распознать конфликт при первом обращении транзакции к объекту (early detection, раннее выявление) или в то время, когда транзакция пытается выполнить операцию фиксации (late detection, отложенное выявление). Оба подхода приводят к одним и тем же результатам, но могут выполняться по-разному, и, к сожалению, ни один из них не обладает существенными преимуществами над другим. Раннее выявление предотвращает выполнение транзакциями излишних вычислений, которые будут отброшены при последующем откате. При отложенном выявлении можно избежать излишних откатов, которые могут возникнуть, когда конфликтующая транзакция откатывается сама по причине конфликта с третьей транзакцией.

Еще одной сложностью является конфликт между транзакцией, которая только читает некоторый объект, и другой транзакцией, которая изменяет этот объект. Поскольку чтения более распространены, чем записи, системы STM клонируют только модифицируемые объекты. Для сокращения накладных расходов транзакция отслеживает прочитанные объекты и до своей фиксации убеждается в том, что эти объекты не модифицировались никакой другой транзакцией.
Рис. 1. TMObject – это оболочка для данного объекта. Он указывает на локатор, который, в свою очередь, ссылается транзакцию, открывшую объект, исходную («old») версию объекта и частную для данной транзакции («new») копию данного объекта. DSTM – это библиотека. Любой объект, к которому производятся обращения внутри транзакции, сначала регистрируется в системе DSTM, возвращающей объект-оболочку TMObject для данного объекта (рис. 1). Впоследствии программа, выполняемая внутри транзакции, может открыть TMObject только для чтения или для чтения и записи, получив в ответ указатель на исходную или клонированную версию объекта соответственно. В любом случае после этого транзакция работает с объектом напрямую без дополнительной синхронизации. Транзакция завершается, когда программа пытается зафиксировать изменения, произведенные при выполнении данной транзакции. Если транзакция успешно фиксируется, система DSTM для всех модифицированных объектов автоматически заменяет их старую структуру в локаторе соответствующей измененной версией. Транзакция T может успешно зафиксироваться, если выполняются два условия. Первое условие состоит в том, что не должна существовать параллельно выполняемая транзакция, изменившая некоторый объект, который был прочитан транзакцией T. DSTM отслеживает объекты, открытые транзакцией для чтения, и проверяет элементы набора прочитанных объектов, когда транзакция пытается зафиксироваться. Объект из этого набора считается отвечающим условию фиксации, если его версия не изменилась с тех пор, как транзакция T открыла его в первый раз. DSTM также проверяет набор прочитанных объектов при каждом следующем открытии объекта, чтобы устранить возможность продолжения выполнения транзакции при ошибочном состоянии программы, в котором некоторые объекты были изменены после начала выполнения данной транзакции. Вторым условием успешной фиксации является то, что транзакция T не должна модифицировать какой-либо объект, измененный другой транзакцией.

DSTM предупреждает возникновение конфликтов этого типа, разрешая только одной транзакции открывать объект для модификации. При возникновении конфликта «write-write» DSTM аварийно завершает одну из двух конфликтующих транзакций, разрешая другой продолжать свое выполнение. DSTM откатывает одну из двух конфликтующих транзакций в ее исходное состояние и позволяет ей выполниться повторно. Политика, используемая для выбора транзакции-жертвы, может влиять на производительность системы, включая ее жизнеспособность, но не должна никаким образом воздействовать на семантику системы STM [28]. Производительность DSTM, как и других систем STM, зависит от деталей рабочей нагрузки. Вообще говоря, при небольшом числе процессоров накладные расходы систем STM оказываются более существенными, чем у схем с блокировками. Однако при возрастании числа процессоров повышаются и уровень конкуренции на отдельную блокировку, и стоимость ее установки. В таких условиях при наличии редко возникающих конфликтов STM (как это показано исследователями) превосходит по производительности схемы с блокировками на тестовых наборах с мелкими транзакциями.

Реализация транзакционной памяти

TM можно реализовывать полностью программным образом (STM) или с использованием специальной аппаратной поддержки (HTM). Предлагалось много разных методов реализации, и в этой статье авторы не приводят подробный обзор литературы, а фокусируются только на нескольких ключевых методах. Более полный обзор приведен, например, в [18].

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

Системы с непосредственным обновлением.

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

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

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

Системы с откладываемыми изменениями.

В других системах STM с откладываемыми изменениями применяются альтернативные реализационные методы. В системе Харриса (Tim Harris) и Фрейзера (Keir Fraser) WSTM конфликты обнаруживаются на уровне слов, а не объектов. Такой подход может позволить избежать излишних конфликтов, если две транзакции обращаются к разным полям некоторого объекта, но эта идея настолько усложняет реализацию, что была применена лишь в нескольких системах STM (хотя в системах HTM принято выявлять конфликты на уровне слов или блоков кэша). WTSM также была первой системой STM, интегрированной в язык программирования. Харрис и Фрейзер расширили язык Java атомарным оператором, который выполняет свой блок внутри транзакции, например:

atomic { int x = lst.head; lst = lst.tail; … }

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

Существенное внимание уделялось исследованию политик выбора транзакции, которую следует аварийно завершить в случае конфликтов [10, 28]. Ни одна политика не обеспечивает наилучшее поведение во всех случаях, однако в целом неплохо работает политика «полька» (polka). При применении этой политики для каждой транзакции запоминается число открытых ей объектов, и этот счетчик используется в качестве ее приоритета. Если какая-то транзакция пытается запросить доступ к некоторому объекту, то это приводит к немедленному аварийному завершению конфликтующей транзакции с более низким приоритетом. Если приоритет у транзакции, запрашивающей доступ, оказывается ниже, чем у конфликтующей с ней транзакции, то она откатывается N раз, где N равно разнице в приоритетах, с экспоненциально возрастающим временным интервалом между попытками. Другими словами, такой транзакции дается N попыток получить доступ к требуемому объекту, и после каждой неудачной попытки она откатывается и выполняется заново.

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

Джеймс Лярус, Кристос Козиракис
Пересказ: Сергей Кузнецов

Джеймс Лярус, Кристос Козиракис
Пересказ: Сергей Кузнецов
Оригинал: James Larus, Christos Kozyrakis. Transactional Memory. Communications of the ACM, July 2008, vol. 51, no. 7

Вряд ли транзакционная память сама

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