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

Question

С точки зрения реальных низкоуровневых атомарных инструкций и ограждений памяти (я предполагаю, что они используются), как вы реализуете STM?

Для меня загадкой является то, что, учитывая некоторый произвольный фрагмент кода, вам нужен способ впоследствии вернуться и определить, были ли значения, используемые на каждом шаге, действительными.Как это сделать и как сделать это эффективно?Это также может означать, что, как и любое другое «блокирующее» решение, вы хотите, чтобы ваши критические секции были как можно меньшими (чтобы уменьшить вероятность конфликта), я прав?

Кроме того, может ли STM просто обнаружить, что «другой поток вошел в эту область во время выполнения вычислений, поэтому вычисление недействительно» или может ли он действительно определить, использовались ли затертые значения (и, таким образом, по счастливой случайности, иногда два потока могут выполнять одну и ту же критическую секцию одновременно без нужен откат)?

Answer 1

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

  

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

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

  

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

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

  

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

Последний. Помните, что идея в TM - защитить данные , а не код .

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

Answer 2

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

Транзакционная блокировка II, Дейв Дайс, Ори Шалев, Нир Шавит , в котором описывается «TL2»; Алгоритм STM с точки зрения любого языка.

Двойка: неинвазивная программная транзакционная память на Java, Гай Корланд, Нир Шавит, Паскаль Фелбер , который объясняет преобразователь класса времени загрузки, который преобразует обычные классы Java в классы в памяти, которые имеют дополнительный байт-код для выполнения STM. Это относится к вопросу, поскольку в документе объясняется, как код без STM можно механически преобразовать в код, выполняющий STM на любом языке OO.

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

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

  

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

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

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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

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

Основная идея заключается в том, что вам не нужно обнаруживать, изменил ли кто-либо еще дерево , пока вы на самом деле не поменяете местами новые и старые значения, чтобы не было " конфликтов " или «сжатые значения»; из типичного многопоточного программирования.

Answer 5

Если вы используете .NET Framework,

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

• .NET 4.0 СТМ.Нет
  
• Подкаст .NET на STM.Net: Дана Грофф и Йоси Леванони беседуют о STM