Пожалуй я не сильно ошибусь, сказав что существует всего два механизма управления изменениями - пессимистичный и оптимистичный. Первый мы уже давно используем в своих программах в виде всевозможных мьютексов и семафоров. Второй механизм, до недавнего времени, применялся в различных СУБД.
Software transactional memory (STM) - реализация второго механизма управления изменениями, по сути это просто транзакции в коде. Вы помечаете участок кода, который должен выполняться в рамках одной транзакции. Во время выполнения, система запоминает все что вы читаете и записываете (поддерживает read set и write set). В случае, если произошел конфликт, несколько транзакций попытались изменить одни и те же переменные, происходит откат транзакции, система возвращается в исходное состояние, после чего транзакция выполняется повторно.
Существует множество реализаций STM на разных языках и платформах, тем не менее, это по прежнему экзотика. Про железные реализации я вообще молчу, не случившийся Rock и BlueGene/Q для суперкомпьютера IBM, но есть и повод для оптимизма.
Примерно год назад, Intel анонсировали новый процессор - Haswell, который будет поддерживать набор инструкций Transactional Synchronization Extensions (TSX). Restricted Transactional Memory (RTM) - это часть TSX, добавляющая поддержку транзакционной памяти. Как видно из названия - поддержку ограниченную.
Для программиста, RTM это четыре новых инструкции - XBEGIN, XEND, XABORT и XTEST.
XBEGIN - начинает транзакцию, XEND - ее фиксирует, XABORT - откатывает. Инструкция XTEST позволяет узнать, находимся мы сейчас в транзакции, или нет. В Visual Studio 2012 есть интринсики, с помощью которых можно удобно использовать эти инструкции. Называются они соответственно - _xbegin, _xend, _xabort и _xtest.
Работает это следующим образом, вы вызываете ф-ю _xbegin, которая возвращает статус транзакции. В случае, если ф-я вернула _XBEGIN_STARTED - транзакция была начата, в противном случае - произошел откат транзакции по какой-либо причине. В случае отката транзакции, управление возвращается в ее начало, то есть в _xbegin() и в этом случае, _xbegin вернет статус, отличный от _XBEGIN_STARTED. В конце транзакции вы должны вызвать ф-ю _xend, в этом случае произойдет фиксация транзакции. Ф-я _xabort прерывает выполняющуюся транзакцию, управление вернется в _xbegin. Разные биты статуса _xbegin позволяют определить причину отката транзакции, был это _xabort, конфликт записи или что-нибудь еще.
Но на самом деле все далеко не так радужно, как может показаться. Недаром в названии есть слово `Restricted`, существуют значительные ограничения на код, который может выполняться в транзакциях. Во первых, в транзакции можно выполнять только простые загрузки и сохранения, даже простое переключение контекста прервет транзакцию. Во вторых, размер write-set и read-set ограничен размером L1 кэша, если вы попытаетесь переписать в транзакции мегабайт памяти - ничего не получится. В третьих, RTM работает на уровне линий кэша, поэтому здесь возможен false sharing, в том случае, если разные переменные попадают на одну кэш линию.
Именно по этому, Intel не гарантирует, что транзакция вообще завершится когда-нибудь. Поэтому, код, использующий транзакции, должен следить за тем, сколько раз и по какой причине транзакция откатилась. Реализация должна предусматривать fallback механизм, например, если наша транзакция откатилась N раз, мы можем попытаться захватить соответствующую блокировку и выполнить тот же самый код без транзакции, используя эксклюзивный доступ к данным.
По этим причинам, код, выполняемый в транзакции, должен быть коротким, он не должен пытаться делать I/O или что-нибудь кроме простых загрузок и сохранений в память, он должен изменять и читать как можно меньше данных. Именно по этому, люди, ждущие от RTM чего-то похожего на STM из Haskell будут разочарованы.
На мой взгляд, RTM подходит для создания различных lock-free структур данных. Если без RTM написать lock-free очередь - было делом нетривиальным, то с RTM все станет намного проще. Вместо того, чтобы ломать себе голову над тем, как с помощью CAS реализовать ту или иную операцию, достаточно просто обернуть ее в транзакцию. Я уже молчу о более сложных структурах данных.
Для иллюстрации вышесказанного, я написал простой, lock-free двух-связный список. Элементы можно добавлять и удалять из любого конца списка.
Это всего лишь proof of concept, не более. Здесь не реализован fallback-механизм, поэтому в случае ошибки в коде, он может зациклиться. Помимо этого, данный код не будет работать на обычных процессорах. Он будет падать по `undefined instruction`. Запустить его можно только в эмуляторе:
Ссылки:
Exploring Intel® Transactional Synchronization Extensions with Intel® Software Development Emulator
Intel® Software Development Emulator
Intel® Architecture Instruction Set Extensions Programming Reference (Chapter 8)
Software transactional memory (STM) - реализация второго механизма управления изменениями, по сути это просто транзакции в коде. Вы помечаете участок кода, который должен выполняться в рамках одной транзакции. Во время выполнения, система запоминает все что вы читаете и записываете (поддерживает read set и write set). В случае, если произошел конфликт, несколько транзакций попытались изменить одни и те же переменные, происходит откат транзакции, система возвращается в исходное состояние, после чего транзакция выполняется повторно.
Существует множество реализаций STM на разных языках и платформах, тем не менее, это по прежнему экзотика. Про железные реализации я вообще молчу, не случившийся Rock и BlueGene/Q для суперкомпьютера IBM, но есть и повод для оптимизма.
Примерно год назад, Intel анонсировали новый процессор - Haswell, который будет поддерживать набор инструкций Transactional Synchronization Extensions (TSX). Restricted Transactional Memory (RTM) - это часть TSX, добавляющая поддержку транзакционной памяти. Как видно из названия - поддержку ограниченную.
Для программиста, RTM это четыре новых инструкции - XBEGIN, XEND, XABORT и XTEST.
XBEGIN - начинает транзакцию, XEND - ее фиксирует, XABORT - откатывает. Инструкция XTEST позволяет узнать, находимся мы сейчас в транзакции, или нет. В Visual Studio 2012 есть интринсики, с помощью которых можно удобно использовать эти инструкции. Называются они соответственно - _xbegin, _xend, _xabort и _xtest.
Работает это следующим образом, вы вызываете ф-ю _xbegin, которая возвращает статус транзакции. В случае, если ф-я вернула _XBEGIN_STARTED - транзакция была начата, в противном случае - произошел откат транзакции по какой-либо причине. В случае отката транзакции, управление возвращается в ее начало, то есть в _xbegin() и в этом случае, _xbegin вернет статус, отличный от _XBEGIN_STARTED. В конце транзакции вы должны вызвать ф-ю _xend, в этом случае произойдет фиксация транзакции. Ф-я _xabort прерывает выполняющуюся транзакцию, управление вернется в _xbegin. Разные биты статуса _xbegin позволяют определить причину отката транзакции, был это _xabort, конфликт записи или что-нибудь еще.
Но на самом деле все далеко не так радужно, как может показаться. Недаром в названии есть слово `Restricted`, существуют значительные ограничения на код, который может выполняться в транзакциях. Во первых, в транзакции можно выполнять только простые загрузки и сохранения, даже простое переключение контекста прервет транзакцию. Во вторых, размер write-set и read-set ограничен размером L1 кэша, если вы попытаетесь переписать в транзакции мегабайт памяти - ничего не получится. В третьих, RTM работает на уровне линий кэша, поэтому здесь возможен false sharing, в том случае, если разные переменные попадают на одну кэш линию.
Именно по этому, Intel не гарантирует, что транзакция вообще завершится когда-нибудь. Поэтому, код, использующий транзакции, должен следить за тем, сколько раз и по какой причине транзакция откатилась. Реализация должна предусматривать fallback механизм, например, если наша транзакция откатилась N раз, мы можем попытаться захватить соответствующую блокировку и выполнить тот же самый код без транзакции, используя эксклюзивный доступ к данным.
По этим причинам, код, выполняемый в транзакции, должен быть коротким, он не должен пытаться делать I/O или что-нибудь кроме простых загрузок и сохранений в память, он должен изменять и читать как можно меньше данных. Именно по этому, люди, ждущие от RTM чего-то похожего на STM из Haskell будут разочарованы.
На мой взгляд, RTM подходит для создания различных lock-free структур данных. Если без RTM написать lock-free очередь - было делом нетривиальным, то с RTM все станет намного проще. Вместо того, чтобы ломать себе голову над тем, как с помощью CAS реализовать ту или иную операцию, достаточно просто обернуть ее в транзакцию. Я уже молчу о более сложных структурах данных.
Для иллюстрации вышесказанного, я написал простой, lock-free двух-связный список. Элементы можно добавлять и удалять из любого конца списка.
Это всего лишь proof of concept, не более. Здесь не реализован fallback-механизм, поэтому в случае ошибки в коде, он может зациклиться. Помимо этого, данный код не будет работать на обычных процессорах. Он будет падать по `undefined instruction`. Запустить его можно только в эмуляторе:
sde -hsw -rtm-mode full -- appname.exeНа данный момент сложно судить о производительности. Я очень надеюсь на то, что RTM будет позволять писать код, который будет работать быстрее, чем аналогичный код, построенный на CAS. На это можно надеяться, так как транзакции все пишут в кэш, а для обнаружения конфликтов записи используется cache coherency протокол, который есть и сейчас. Насколько я понял, все операции записи внутри транзакции - неблокирующие, в отличии от xchg.
Ссылки:
Exploring Intel® Transactional Synchronization Extensions with Intel® Software Development Emulator
Intel® Software Development Emulator
Intel® Architecture Instruction Set Extensions Programming Reference (Chapter 8)
Комментариев нет:
Отправить комментарий