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

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

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

Программная транзакционная память. В первой статье Шавита (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 (как это показано исследователями) превосходит по производительности схемы с блокировками на тестовых наборах с мелкими транзакциями.

Системы с откладываемыми изменениями. В других системах 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 попыток получить доступ к требуемому объекту, и после каждой неудачной попытки она откатывается и выполняется заново.

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

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

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