Транзакционные методы бесконфликтного доступа к памяти

В 90-х годах прошлого века M. Herlihy и J. E. B. Moss описали оригинальную аппаратную реализацию [herlihy] бесконфликтного доступа нескольких процессоров к разделяемой памяти: конкурентные операции чтения/записи разделяемой памяти процессора могут объединяться в некоторый атомарный (неделимый) набор действий — транзакцию — и выполняться совершенно независимо от операций других процессоров. Предложенный механизм доступа к памяти, который в настоящее время является объектом активных научных исследований, был назван транзакционной памятью, ТП (англ. transactional memory, TM). Однако можно отметить, что сама идея не так уж и нова: впервые применять подобный механизм для любых вычислительных процессов вообще, а не только для управления доступом к данным в базах данных, предложил D. B. Lomet. В своей работе [lomet] Lomet описал концепцию атомарных действий (англ. atomic actions), позже реализованную Liskov и Scheifler в языке распределенного программирования Argus [liskov]. Появление идеи транзакционной памяти стало результатом обработки и осмысления многолетних исследований в области традиционной синхронизации вычислительных процессов и моделей согласованности памяти с одной стороны: схожие принципы и соответствующие конструкции можно встретить у Хоара — концепция мониторов [hoare], и с другой стороны — в области теории транзакционной обработки данных в базах данных.

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

С точки зрения программиста, ТП — это некоторая универсальная языковая конструкция, набор библиотечных функций или набор аппаратно-программных инструкций. Самая первая идея реализации ТП, предложенная Herlihy и Moss в работе [herlihy], представляет собой многопроцессорную аппаратную архитектуру с модифицированным протоколом согласованности аппаратных кэшей и расширенным набором аппаратных инструкций, доступных программисту. Дополнительные инструкции подразделяются на две группы. Первая группа — инструкции по доступу к транзакционной памяти: загрузка значения из памяти в регистр (LT, англ. Load-Transactional), загрузка значения из памяти в регистр с пометкой “возможно обновление” считанного значения (LTX, англ. Load-Transactional-eXclusive), сохранение значения из регистра в память (ST, англ. Store-Transactional); вторая группа — инструкции для управления состоянием транзакции: фиксация измененных транзакцией значений (COMMIT), откат транзакции (ABORT), проверка сделанных изменений на согласованность (VALIDATE). В предложенной архитектуре присутствуют два кэша: обычный — для обычных операций с памятью и транзакционный, с модифицированным протоколом согласованности, который по сути и является основным алгоритмом транзакционной памяти в данном случае. Аппаратная природа предложенного подхода является его основным недостатком — для его применения необходимо вносить значительные изменения в уже существующие вычислительные архитектуры. Однако результаты симуляции, проведенной в работе, показали перспективность данного подхода по сравнению с традиционными архитектурами. Можно отметить, что в настоящее время ведущие производители процессорных устройств заявили и уже частично реализовали поддержку механизмов транзакционной памяти в ряде моделей процессоров новейших поколений [reinders, merrit].

Дальнейшее развитие идеи Herlihy и Moss получили в работе N. Shavit и D. Touitou [shavit], впервые описывающей принципы программной реализации ТП (англ. software transactional memory, STM). Как отмечалось выше, очень схожие идеи высказывал еще раньше Lomet. Однако предложенные Shavit и Touitou алгоритмы построены с использованием несколько других принципов: они неблокирующие и обладают свойством свободы от блокировок (см. параграф 1.4). Их основной особенностью и недостатком является то, что они рассчитаны на статические транзакции, т.е. транзакции, для которых заранее известны все адреса будущих обращений к памяти. Также, для реализации данных алгоритмов требуется наличие поддержки вложенной атомарной операции LL/SC (англ. Load-Linked/Store-Conditional).

Контрольные вопросы