Как вы реализуете программную транзакционную память?

Ответ 1

Самый простой ответ - "это зависит". Есть тонны радикально разных реализаций, которые работают практически так, как можно вообразить.

Часть, которая таинственна для меня, заключается в том, что с учетом некоторого произвольного фрагмента кода вам нужен способ вернуться назад и определить, были ли значения, используемые на каждом шаге, действительными. Как вы это делаете и как вы делаете это эффективно?

Одним из решений является использование версий. Каждый раз, когда объект изменяется, его номер версии обновляется. Пока транзакция выполняется, вы проверяете каждую версию доступного объекта, и когда транзакция завершается, вы подтверждаете, что объекты все еще действительны. Эта проверка может быть простым целым сравнением (если transaction_start_version >= object_version, объект действителен), поэтому это можно сделать достаточно эффективно.

Это также показало бы, что, как и любое другое "блокирующее" решение, вы хотите, чтобы ваши критические разделы были как можно меньше (чтобы уменьшить вероятность конфликта), я прав?

Скорее всего. Я думаю, что несколько реализаций пошли по пути к тому, чтобы предполагать/требовать, чтобы все было транзакцией, но да, в большинстве реализаций транзакции представляют собой специально отмеченные куски кода, и чем дольше выполняется транзакция, тем больше вероятность конфликта, который может заставляют транзакции откатываться.

Кроме того, STM может просто обнаружить "другой поток, введенный в эту область во время выполнения вычисления, поэтому вычисление недействительно" или может ли оно фактически определить, были ли использованы сбитые значения (и, следовательно, по удачи иногда два потока могут выполнять один и тот же критический раздел без необходимости отката)?

Последний. Имейте в виду, что идея в TM заключается в защите данных, а не в коде.

Различные пути кода могут обращаться к одной и той же переменной в разных транзакциях. Это должно быть обнаружено системой ТМ. Там нет реального понятия "эта область", поскольку это относится к коду, а не к данным. Система TM не заботится о том, какой код выполняется, отслеживает, какие данные изменяются. Таким образом, он полностью отличается от критических секций (которые защищают код, а не данные)

Ответ 2

Некоторые статьи могут быть действительно трудными для чтения, но два, которые являются очень четкими и краткими:

Transactional Locking II, Dave Dice, Ori Shalev, Nir Shavit, который описывает алгоритм STM TL2 в терминах любого языка.

Deuce: неинвазивная программная транзакционная память в Java, Guy Korland, Nir Shavit, Pascal Felber, которая объясняет трансформатор класса времени нагрузки, который трансформирует регулярную java классы в классы памяти, которые имеют дополнительный байт-код для STM. Это относится к вопросу, поскольку в документе объясняется, как код без STM может быть механически преобразован в код, который выполняет STM на любом языке OO.

Рамка Deuce позволяет вам подключать фактический алгоритм, который вы хотите использовать; включая алгоритм TL2. Поскольку структура Deuce является Java, в следующем обсуждении используется терминология Java, но предполагается, что вы пишете на языке OO.

Ниже будет описан подход TL2. В документах есть ссылки на альтернативные подходы, но изучение одного алгоритма отвечает на множество вопросов.

как вы реализуете STM? Часть, которая таинственна для меня, заключается в том, что с учетом некоторого произвольного фрагмента кода вам нужен способ вернуться назад и определить, были ли значения, используемые на каждом шаге, действительными.

Один короткий ответ о том, как TL2 делает STM, - это "бухгалтерский учет", а затем только использование блокировок записи во время фиксации. Прочтите бумагу для мелких деталей, но контур кисти планшета выглядит следующим образом. Каждое свойство, которое вы можете использовать в исходном коде, будет иметь getter и setter. В преобразованном коде также будет номер версии свойства и дополнительный код, добавленный в getter и setter. Вам необходимо записать версию каждого атрибута, который вы читаете в транзакции, в качестве транзакции "read-set". Вы можете сделать это, если каждый getter добавит версию атрибута, замеченную в связанный с threadlocal список. Вам также необходимо буферизировать записи как "набор записей" в threadlocal, пока вы не зафиксируете. Обратите внимание, что методы getter должны проверять и возвращать значение threadlocal write-set для заданного поля, если оно у вас есть. Таким образом, вы видите свои незафиксированные записи в своих чтениях, но ни один другой поток не увидит их, пока вы не зафиксируете.

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

В документе объясняется, что алгоритм может прерваться раньше, если он обнаружит, что атрибут, который был прочитан, был записан с момента начала tx. У бумаги есть некоторые аккуратные трюки, чтобы ускорить транзакции только для чтения. У него даже есть хитрость, чтобы определить, какие блоки доступны только для чтения и которые являются "читать-писать". Любой, кто проявляет интерес к таким вещам, действительно должен пользоваться этими двумя документами.

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

Преобразование обычного кода в код STM (особенно во время выполнения) интересно, но если вам нужно написать структуру данных с поддержкой STM, вам не нужен какой-либо волшебный соус. Вместо этого просто создайте класс Ref с get() и set(x) и сделайте каждую взаимосвязь между объектами структуры данных, состоящими из дескрипторов Ref. В get и set вашего класса Ref вы можете выполнять threadlocal bookwork. Затем вы можете реализовать простую версию "TL2" или любой другой алгоритм, который хорошо работает для ваших структур данных и вашего concurrency для чтения и записи.

Это также показало бы, что, как и любая другая "блокировка", вы хотите, чтобы ваши критические разделы были как можно меньше (чтобы уменьшить вероятность конфликта), я прав?

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

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

Кроме того, STM может просто определить "другой поток, введенный в эту область, в то время как вычисление выполнялось, поэтому вычисление недействительно" или может ли он фактически определить, были ли использованы сбитые значения (и, следовательно, по удачи иногда два потока могут выполнять один и тот же критический раздел одновременно без необходимости отката)?

Подход TL2, как и все данные, считанные или написанные не о коде, который это делает. Это то, что вы получаете и устанавливаете, и что считается; и просочился ли какой-либо другой поток на ваши пальцы перед тем, как вы очистите все записи. Все, что требуется от кода, состоит в том, что в бизнес-логике есть begin(), commit() и rollback(), чтобы начать, завершить и прервать транзакцию. Даже это может быть сгенерированный код. С помощью Java вы можете пометить свои методы с помощью аннотации @Transactional на методах, а затем сгенерировать код, который обертывает ваши вызовы методов в try/catch/finally, что делает begin/commit/rollback как идиоматическую java. Deuce вводит такую ​​логику в момент загрузки класса.

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

Ответ 3

GHC Реализация STM описана в шестом разделе:

Композитные транзакции памяти. Тим Харрис, Саймон Марлоу, Саймон Пейтон Джонс, Морис Херлихи. PPoPP'05: Симпозиум ACM SIGPLAN по принципам и практике параллельного программирования, Чикаго, Иллинойс, июнь 2005 г.

И пятый раздел:

Транзакционная память с инвариантами данных. Тим Харрис, Саймон Пейтон-Джонс. Март 2006 г. TRANSACT '06

Ответ 4

Я предлагаю вам посмотреть эту презентацию: http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

Во второй половине объясняется, как обновлять значения, не оставляя их в состоянии undefined. Например, если у вас есть дерево, которое вы хотите обновить в STM-стиле, вы не измените предыдущую версию вообще. Скажем, что tree является указателем на корень дерева. Единственное, что вы создаете, это узлы, которые изменились (но они могут ссылаться на узлы в исходном снимке дерева.

Затем вы выполняете сравнение и свопинг с указателем tree. Если это сработает, то теперь все будут видеть ваше новое дерево, а старое - сбор мусора. Если это не так, вы повторяете процесс, и дерево, которое вы только что создали, - это сбор мусора.

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

Ответ 5

Если вы собираетесь работать с .NET framework,

Вы можете проверить этот экспериментальный

• .NET 4.0 STM.Net
  
• .NET rock podcast на STM.Net: Дана Грофф и Йосси Леванони Обсуждение STM