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