Пользователь
0,2
рейтинг
5 мая 2014 в 02:00

Разработка → Транзакционная память: история и развитие

Определение


Параллельное программирование сложно. При использовании систем с общей памятью не обойтись без синхронизации доступа параллельных процессов/потоков к общему ресурсу (памяти). Для этого используются:
  • блокировки (mutex);
  • алгоритмы без блокировки (lockless, lock-free);
  • транзакционная память.


Транзакционная память — технология синхронизации конкурентных потоков. Она упрощает параллельное программирование, выделяя группы инструкций в атомарные транзакции. Конкурентные потоки работают параллельно1, пока не начинают модифицировать один и тот же участок памяти. К примеру, операции добавления узлов в красно-чёрное дерево (анимация в заголовке) способны работать параллельно в нескольких потоках.
Скрытый текст
/* Move item from one list to another */
int move(list *from, list *to) {
    __transaction_atomic {
        node *n = pop(from);
        push(to, n);
    }
}


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

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

Плюсы транзакционной памяти:
  • относительная простота использования (заключение целых методов в блок транзакции);
  • полное отсутствие блокировок и взаимных блокировок;
  • повышение уровня параллелизма, а следовательно, и производительности.

Транзакционная память — не серебряная пуля. Есть и минусы:
  • при неправильном использовании возможно падение производительности и некорректная работа;
  • ограниченность применения — в транзакции нельзя выполнять операции, действие от которых невозможно отменить;
  • сложность отладки — поставить breakpoint внутри транзакции невозможно.


Рождение технологии


Транзакции в базах данных существуют уже несколько десятилетий. Впервые идея переноса транзакций из мира баз данных в мир параллельного программирования возникла в 1980-х. Развивали и популяризовали технологию Maurice Herlihy, Ravi Rajwar, Nir Shavit. Первые исследования предлагали аппаратные реализации транзакционной памяти, которым не суждено было родиться ещё 30 лет.
В 1990-х появились первые программные реализации технологии, аппаратные реализации подтянулись к 2000-ым.

Программные реализации (Software Transactional Memory, STM)

Среди множества реализаций программной транзакционной памяти я хотел бы выделить четыре. Примеры доступны на github: JIghtuse/tm-experiments.

Clojure
Clojure — единственный язык, ядро которого поддерживает транзакционную память. Основные конструкции STM: ref (ссылка на данные, через которую данные меняются только в транзакции) и dosync (блок транзакции).

Подход к STM в Clojure называется управлением конкурентным доступом с помощью многоверсионности (MultiVersion Concurrency Control, MVCC): хранятся множественные логические версии данных, используемых в транзакции. В течение транзакции поток наблюдает снимок данных на момент её начала.
Скрытый текст

Диаграмма версий ссылок в транзакции Clojure.

Транзакции 1 и 2 начинаются в одно и то же время, получая одну копию версии ref v0. Внутри транзакций происходит обработка данных, которая меняет значение ref. Первая транзакция заканчивается раньше и выигрывает гонку за обновление ref новым значением. Затем заканчивается вторая транзакция, и её попытка обновить ref проваливается (красная стрелка на диаграмме), поскольку версия ref была не той, которая ожидалась. В этом случае транзакция перезапускается, получая копию новой версии ref. Поскольку ни одна другая транзакция не пытается изменить ref, во второй раз транзакция 2 успешно завершается.
Вычисления в транзакции 3 не меняют значения ref, поэтому перезапуск не вызывается и она успешно завершается.

Рассмотрим пример перевода средств между банковскими аккаунтами:
Скрытый текст
Программа работает в одном потоке, но потокобезопасно.
(def account1 (ref 100))
(def account2 (ref 0))
; для чтения текущего значения 'ref' используется (deref refname):
(deref account1)
100
; @refname - эквивалент (deref refname)
@account2
0

(defn transfer [amount from to]
    (dosync
       (alter from - amount)
       (alter to   + amount)))

(transfer 100 account1 account2)
100

Существуют варианты использования конкурентности, при которых среде позволяется «расслабиться» для достижения дополнительной производительности. К примеру, представьте что вы храните журнал транзакций за день. Порядок транзакций в журнале не важен, если вы знаете, что конечный баланс будет корректным. Если вы получаете два взноса в $100 и $50, очерёдность внесения их в журнал не играет роли. Взнос от двух транзакций коммутативен, и clojure предоставляет конкурентную операцию commute как раз для таких случаев.
Скрытый текст
(defn log-deposit [account amount]
     (dosync
        (println "Depositing $" amount " into account, balance now: "
            (commute account + amount))))

(def myaccount (ref 0))

(log-deposit myaccount 100)
(log-deposit myaccount 50)

; (as good as) equivalent to 

(log-deposit myaccount 50)
(log-deposit myaccount 100) 

Haskell

Транзакционная память в Haskell содержится в библиотеке STM, которая входит в Haskell Platform. Некорректное использование транзакционных типов определяется на этапе компиляции программы.

Haskell обладает мощной системой типов. Язык разделяет функции с побочными эффектами и чистые функции. Любое значение типа IO t называется действием. Для выполнения какого-либо действия атомарно в Haskell, действие предваряется словом atomically. Вызов atomically с действием в качестве аргумента даёт две гарантии:
  • атомарность — эффект от atomically act будет виден другим потокам сразу и целиком. Ни один другой поток не способен увидеть состояние внутри атомарного действия, лишь конечное состояние.
  • изоляция — во время вызова atomically act действие act выполняется абсолютно независимо от других потоков. Оно снимает состояние мира при запуске и выполняется в этом состоянии.

atomically имеет тип atomically :: STM a -> IO a. Действие типа STM a — аргумент. Как и действие IO, действие STM имеет побочные эффекты, но их диапазон значительно уже. В основном в действии STM происходит запись или чтение транзакционной переменной TVar a:
  • readTVar :: TVar a -> STM a
  • writeTVar :: TVar a -> a -> STM ()

Рассмотрим пример перевода средств между аккаунтами банка.
Скрытый текст
import System.IO
import Control.Concurrent.STM

-- Система типов защищает от чтения или записи переменные типа TVar вне транзакции
type Account = TVar Int

withdraw :: Account -> Int -> STM ()
withdraw acc amount = do
    bal <- readTVar acc
    writeTVar acc (bal - amount)

deposit :: Account -> Int -> STM ()
deposit acc amount = withdraw acc (- amount)

transfer :: Account -> Account -> Int -> IO ()
-- Перевести ’amount’ с аккаунта ’from’ на аккаунт ’to’
transfer from to amount 
    = atomically (do deposit to amount
                     withdraw from amount)

showAccount :: Account -> IO Int
showAccount acc = atomically (readTVar acc)

main = do
    from <- atomically (newTVar 200)
    to   <- atomically (newTVar 100)
    transfer from to 50
    v1 <- showAccount from
    v2 <- showAccount to
    putStrLn $ (show v1) ++ ", " ++ (show v2)

-- Программа распечатает "150, 150"

Scala

Реализация STM для Scala (ScalaSTM) разрабатывалась под впечатлением от реализаций в Haskell и Clojure. Помимо Scala, ScalaSTM вызывается из Java и Clojure. Реализация используется в популярном фреймворке для написания параллельных программ Akka.
ScalaSTM предоставляет ячейку Ref, изменяемую исключительно внутри транзакции. Структуры данных на основе неизменяемых объектов и Ref используются многими потоками.

Рассмотрим реализацию двусвязного потокобезопасного списка с использованием транзакционной памяти. К сожалению, собрать пример на Scala мне не удалось, оставляю это занятие читателю.
Скрытый текст
Полный пример на github: github.com/nbronson/scala-stm/blob/master/src/test/scala/scala/concurrent/stm/examples/ConcurrentIntList.scala

Для реализации разделяемой структуры указатели на следующий и предыдущий узел делают потокобезопасными. Если существует возможность того, что один поток записывает переменную в то же время, когда другой получает к ней доступ (читает или записывает), то используют Ref. Определим класс для узла списка и инициализируем голову списка. Список кольцевой: при создании указатели головного списка указывают на него же. Эти указатели никогда не равны null.

import scala.concurrent.stm._

class ConcurrentIntList {
  private class Node(val elem: Int, prev0: Node, next0: Node) {
    val isHeader = prev0 == null
    val prev = Ref(if (isHeader) this else prev0)
    val next = Ref(if (isHeader) this else next0)
  }

  private val header = new Node(-1, null, null)

Если x является Ref, то x() получает значение, сохранённое в x, а x() = v задаёт его равным величине v.
Ref читаются и записываются только внутри атомарного блока (транзакции). Это проверяется во время компиляции. Далее демонстрируется использование транзакции.
def addLast(elem: Int) {
    atomic { implicit txn =>
      val p = header.prev()
      val newNode = new Node(elem, p, header)
      p.next() = newNode
      header.prev() = newNode
    }
  }

Scala объединяет идеи многих парадигм программирования. Неудивительно, что и в области транзакционной памяти язык имеет самобытные технологии. Вышеупомянутый фреймворк Akka объединяет возможности акторов и транзакционной памяти, получая агенты и транзакторы, которые окончательно взорвут вам мозг.

C/C++ (GCC 4.7+)

Начиная с версии 4.7, GCC поддерживает транзакционную память. Реализация представляет собой библиотеку времени выполнения libitm, для компиляции указывается флаг -fgnu-tm (-mrtm, -mhle). Библиотека разрабатывалась с оглядкой на черновик транзакционных конструкций для C++ (предлагается включение в стандарт языка).

Большинство реализаций аппаратной транзакционной памяти используют принцип наибольшего усилия. Поэтому практичные реализации используют объединение технологий аппаратурной и программной транзакционной памяти. Такие системы называют системами «гибридной транзакционной памяти». К ним относится, в частности, реализация GCC.

В язык вводятся ключевые слова:
  • __transaction_atomic { … } — указание, что блок кода — транзакция;
  • __transaction_relaxed { … } — указание, что небезопасный код внутри блока не приводит к побочным эффектам;
  • __transaction_cancel — явная отмена транзакции;
  • attribute((transaction_safe)) — указание транзакционно-безопасной функции;
  • attribute((transaction_pure)) — указание функции без побочных эффектов.


Для демонстрации использования транзакционной памяти в C будем заполнять гистограмму данных в конкурентных потоках.
Скрытый текст
Полная реализация на github: github.com/JIghtuse/tm-experiments/blob/master/histogram/src/hist.c

Используется один блок транзакции на цикл обновления гистограммы. Библиотека времени выполнения (либо аппаратное обеспечение) определит, когда и какие транзакции перезапустить.
#ifdef _USE_TSX
    __transaction_atomic {
#endif
        for (i = 0; i < d->sz; ++i) {
            struct pixel p = d->pixels[i];

            unsigned int luminance = rY * p.red + gY * p.green + bY * p.blue;

#if defined _USE_TSX
            ++histogram[luminance/BORDER];
#elif defined _USE_MUTEX
            pthread_mutex_lock(&mut);
            ++histogram[luminance/BORDER];
            pthread_mutex_unlock(&mut);
#endif
        }
#ifdef _USE_TSX
    }
#endif


Аппаратные реализации (Hardware Transactional Memory, HTM)

Лишь в последнее время начали появляться аппаратные реализации транзакционной памяти.

Sun Rock (SPARC v9) 2007-2008




Микропроцессор Rock от компании Sun Microsystems был первым микропроцессором с аппаратной поддержкой транзакционной памяти. 64-разрядный процессор архитектуры SPARC v9 имел 16 ядер.

В 2007 компания объявила о поддержке технологии. Для функционирования транзакционной памяти были добавлены две новые инструкции chkpt и commit и один новый статусный регистр cps. Инструкция chkpt <fail_pc> использовалась для начала транзакции, а инструкция commit для её завершения. При отмене транзакции происходил переход на <fail_pc>, в это время можно было проверить регистр cps для определения причины отмены. Транзакции прерывались по причинам конфликтов данных, промахов TLB, прерываний, сложных инструкций. Тем не менее, во многих случаях использование транзакционной памяти в процессоре Rock давало преимущества в синхронизации.

В 2008 инженеры Sun представили интерфейс транзакционной памяти и симулятор Adaptive Transactional Memory Test Platform. После покупки компании Sun корпорацией Oracle проект Rock был закрыт: «Этот процессор имел два потрясающих свойства: он был невероятно медленным и потреблял громадное количество энергии. Он был настолько горячим, что им пришлось поставить сверху 12 дюймов охлаждающих вентиляторов, чтобы процессор не перегревался. Было бы безумием продолжать этот проект.»2

IBM BlueGene/Q (PowerPC A2) 2011



Суперкомпьютер Sequoia с архитектурой BlueGene/Q стал первой коммерческой системой с аппаратной поддержкой транзакционной памяти. Технология работает в 32-мегабайтном кэше второго уровня процессора PowerPC A2 (PowerPC BQC 16C). Данные в кэше имеют метку “версия”, и кэш способен хранить несколько версий одних и тех же данных.

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

Технология версионных меток в PowerPC A2 также используется для спекулятивного выполнения. Вместо ожидания новой версии данных поток может выполнить вычисления с имеющимися данными, спекулятивно производя полезную работу. Если данные были такими же, как и после обновления, поток завершает (commit) работу из кэша. Производительность выше: поток выполнил работу до получения финального значения. В противном случае результаты спекулятивной работы отклоняются и поток производит вычисления с корректными значениями.

Поддержка транзакционной памяти — в некотором роде логическое расширение возможности, давно присутствующей в процессорах PowerPC — “load-link/store-conditional”, или LL/SC. LL/SC — примитивная операция, которая может использоваться как строительный блок для всех потокобезопасных конструкций. Первая часть LL/SC — load-link — используется программой для получения данных из памяти. Далее поток изменяет данные и записывает их обратно в память с помощью store-conditional. Команда завершается успешно, если данные не менялись. В противном случае программа повторяет действия с данными с начала.

Транзакционная память — LL/SC на стероидах: потоки выполняют операции LL на множестве различных областей памяти, а операция завершения транзакции атомарно изменяет все области памяти или отменяет транзакцию (как SC).

Ruud Haring, который представил работу IBM по транзакционной памяти на Hot Chips, признался, что при реализации компания столкнулась со множеством нетривиальных проблем. При всей сложности, реализация имеет ограничения: она не предоставляет межпроцессорной поддержки транзакций. Проблема не актуальна для Sequoia и в то же время позволяет оценить выигрыш от использования транзакционной памяти.

IBM zEnterprise EC12 (Z/Architecture) 2012


Первый коммерческий сервер с поддержкой инструкций транзакционной памяти. При использовании транзакционной памяти IBM обнаружила рост производительности в 45% по сравнению с машиной z196 в базе данных DB2 и работах в виртуализированных серверных нагрузках.

IBM Power8 (Power) 2013



Контроллеры памяти Power 8 поддерживают транзакционную память. Поддержка технологии в ядре Linux появилась начиная с версии ядра 3.9.
Информации по HTM в Power8 удалось найти не так много, надеюсь она ещё появится.

Intel Haswell (x86) 2013



В 2012 компания Intel объявила о введении расширений транзакционной синхронизации (Transactional Syncrhonization Extensions, TSX) в набор инструкций x86. Расширения позволяют программистам помечать отдельные участки кода как транзакции.
В 2013 с выходом поколения процессоров Haswell аппаратная поддержка транзакционной памяти впервые становится доступной на потребительском уровне.

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

TSX состоит из двух частей. Аппаратное исключение блокировок (Hardware Lock Elision, HLE) предоставляет простую конвертацию программ на основе блокировок в транзакционные программы, причём полученные программы будут обратно совместимы с существующими процессорами. Ограниченная транзакционная память (Restricted Transactional Memory, RTM) является более полной реализацией транзакционной памяти.

Hardware Lock Elision

HLE слегка модифицирует инструкции для изменения участка памяти. Технология добавляет префиксы — инструкции, не производящие каких-либо действий, но меняющие интерпретацию следующей инструкции — для модификации инструкций взятия и освобождения блокировки (XACQUIRE и XRELEASE соответственно).

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

Таким образом, HLE позволяет общепринятому коду на основе блокировок работать оптимистично. Каждый поток будет считать, что получил блокировку, в то время как остальные потоки могут работать одновременно. До тех пор пока это безопасно, транзакции не отменяются.

Технология обратно совместима с процессорами без поддержки HTM. Операции по управлению блокировкой остаются, но со специальным префиксом. Процессоры Haswell будут учитывать префикс и использовать транзакционное исполнение вместо манипуляций с блокировками. Любой другой процессор будет игнорировать префикс и просто управлять блокировкой, используя традиционное поведение на основе блокировок. Инструкции XACQUIRE и XRELEASE уже существуют, но не несут какого-либо смысла, пока не используются со специфичными инструкциями.

HLE позволяет писать программы и операционные системы, которые будут использовать транзакции на Haswell, повышая уровень параллелизма без блокировок. Код будет работать корректно на текущих процессорах. В итоге, ввод новой возможности будет простым и безопасным.

HLE на простом примере
Операционные системы реализуют блокировки в ядре как участки памяти, обычно используя типичный для процессора целый тип. Берущий блокировку поток делает нечто с этим участком памяти, к примеру увеличивает значение с 0 на 1. Для освобождения блокировки применяется обратная операция (к примеру, декремент с 1 до 0). Изменения видимы каждому процессорному ядру и каждому потоку в системе, поэтому другие потоки сразу же определяют, что не могут взять блокировку и должны ждать её освобождения (приобретение значения 0).

С префиксами XACQUIRE/XRELEASE попытка взятия блокировки завершается успешно, и процесс полагает, что блокировка принадлежит ему и работает далее. Однако глобального изменения значения блокировки не происходит. Таким образом, поток с блокировкой будет полагать, что её значение равно 1, а остальные потоки системы будут по-прежнему видеть 0. Это позволяет другим потокам одновременно брать блокировку, и процессор вновь будет им лгать. Поток будет видеть блокировку взятой, а другие потоки так не будут считать.

Такое поведение объясняет название HLE: вместо изменения значения с 0 на 1 и обратно, оно просто остаётся равным 0. “Необязательная” запись исчезла.


Restricted Transactional Memory

RTM требует большего участия: он уходит от обратной совместимости и вводит три новых инструкции. В то время как HLE неявно использует транзакции, позволяя коду на основе блокировок работать параллельно, RTM делает начало, завершение и прерывание транзакций явными. Поток начинает транзакцию инструкцией XBEGIN, предоставляя “запасную” функцию, которая запускается в случае прерывания транзакции. Транзакция завершается инструкцией XEND, при этом процессор проводит транзакцию если не было конфликтов или прерывает её, переходя в запасную функцию. Транзакции явно прерываются в программе инструкцией XABORT.
Благодаря явному использованию границ и “запасному выходу”, RTM позволяет контролировать транзакции полнее, чем HLE. В долгосрочной перспективе RTM упростит реализацию возможностей транзакций.

Выводы


Использование транзакционной памяти — жизнеспособная альтернатива существующим методам синхронизации, которая позволяет упростить параллельное программирование.
О неточностях перевода, стилистики, и об опечатках просьба писать в личном сообщении.

Примечания


  1. О разнице понятий «конкурентность» и «параллелизм» грамотно выразился Rob Pike в выступлении "Concurrency is not Parallelism": «Конкурентность — работа с множеством вещей за один раз, параллелизм — выполнение множества вещей за один раз»
  2. Да-да, помимо пачки отличных программных продуктов (OpenSolaris, MySQL, OpenOffice) Oracle забросила и перспективную аппаратную технологию

Источники


Считаете ли вы технологию транзакционной памяти перспективной?

Проголосовало 443 человека. Воздержалось 126 человек.

Интересен ли пост, требуется moar?

Проголосовало 379 человек. Воздержалось 143 человека.

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

@JIghtuse
карма
89,2
рейтинг 0,2
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (34)

  • +1
    Досмотрел анимацию с кружочками в начале поста до конца.
    • +3
      Попробуйте ещё и статью прочесть.
  • 0
    А у AMD ничего такого в процессорах нет?
    • +4
      Официально ничего объявлено не было. Есть несколько статей про AMD ASF (Advanced Synchronization Facility) — черновик расширения ISA и описаний его работы на симуляторах:

      1. developer.amd.com/community/blog/just-released-advanced-synchronization-facility-asf-specification/
      2. Implementing AMD's Advanced Synchronization Facility in an out-of-order x86 core / Stephan Diestelhorst, Martin Pohlack, Michael Hohmuth et al. // 5th ACMSIGPLAN Workshop on Transactional Computing. 2010. 8 p. URL: www.amd64.org/fileadmin/user_upload/pub/transact10-asfooo.pdf
      3. Chung Jaewoong, Diestelhorst Stephan, Pohlack Martin et al. ASF: AMD64 Extension for Lock-free Data Structures and Transactional Memory. 2010.

      Если кратко, то вот что было задумано.
      1. Новые инструкции: SPECULATE, COMMIT, ABORT для старта, завершения и явной отмены транзакции, и RELEASE — оптимизирующий hint для ASF, разрешающий больше не проверять конфликты для определённого региона.
      2. Внутри транзакции новый смысл придаётся инструкциям LOCK MOV — она используется для чтения и записи в память. Обычные доступы в память происходят в обход системы HTM, допустимы в транзакциях и могут быть использованы для уменьшения нагрузки на аппаратуру, управляющую точками сохранения.
      3. Для сообщения причины отмены транзакции код причины сохраняется в регистре RAX.
      4. На транзакцию не влияют такие события, как неправильное предсказание перехода, промах TLB и ближние вызовы функций.
      5. Предоставление гарантированного успешного завершения транзакции, если она в процессе своей работы использует не более четырёх линий кэш-памяти. Т.е. достаточно малые спекулятивные регионы могут использоваться без необходимости написания fallback-ветви.
      • +1
        Скажите пожалуйста, а как в принципе можно гарантировать пункт номер 5? Ведь это от процессора не зависит. Или они умудряются как-то контролировать работу конвейера альтернативных ветвей исполнения, чтобы текущая ветвь завершилась удачно? Уж больно сомнительно выглядит.

        Или речь идет только о том что начатая операция COMMIT завершится удачно без дополнительной вероятности отказа даже в случае того что данные не были конкурентно изменены.
        • +12
          Скажите пожалуйста, а как в принципе можно гарантировать пункт номер 5

          Этот пункт гарантировать можно. Более того, в IBM System z так и сделано — один из видов транзакций (constrained transaction) гарантирует успешное завершение. Однако для этого на регион кода накладывают множество ограничений [1]:
          — максимум 32 инструкции длиной,
          — все инструкции должны уместиться в последовательных 256 байтах в памяти,
          — если внутри есть инструкции перехода, то они должны указывать только вперёд (т.е. не должно быть циклов),
          — нет вызовов процеду,
          — работа идёт максимум с четырьмя выровненными секциями по 32 байта памяти,
          — транзакция не содержит «сложных» инструкций (напр. FPU).
          Т.е. простые типовые операции типа добавления элемента в список можно оформить как constrained transaction.

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

          В Intel RTM таких гарантий, например, нет. Поэтому приходится писать код, в котором после нескольких неудачных попыток выполнить XBEGIN-XEND захватывается обычный lock, и нужная секция исполняется нетранзакционно. Пример, почему это нужно (сам на практике натыкался) — отсутствие страницы (Page Fault) при обращении внутри транзакции не вызывает обработчик ОС, который бы эту страницу подкачал с диска, а откатывает исполнение и состояние на начало, и всё заново, и опять тот же промах. Единственное «обычное» исполнение разблокирует нам транзакционный путь (страница будет подкачана), но его надо предусмотреть.

          [1] Christian Jacobi, Timothy Slegel, Dan Greiner. Transactional Memory Architecture and Implementation for IBM System z. 2012 IEEE/ACM 45th Annual International Symposium on Microarchitecture www.christianjacobi.de/publications/jsg12_tx.pdf
          • 0
            Спасибо за столь развернутый комментарий, очень интересно!
  • 0
    Эх, вы меня опередили, хотел примерно такой же пост про транзакционную память забабахать :-). Ваше описание ТМ мне очень понарвилось!
    • 0
      Спасибо вам за активность и ссылки! Есть что почитать.
  • +1
    А какие языки/библиотеки поддерживают эти инструкции? Также интересно узнать, насколько просаживается производительность при нормальном (без конфликтов) течении программы и при возникновении конфликтов.
    • 0
      Сильно не интересовался этим, но знаю что в Boost идет разработка Boost.AFIO (Async file i/o library for Boost) и там используется TSX.
    • +2
      Точно знаю, что GCC (libitm) поддерживает интринсики и использует FASTPATH для процессоров, поддерживающих Intel TSX и Power8 (о Power8 есть ещё в Release Changes 4.9). Словом, пока только C/C++, я не слышал чтобы HTM использовали в других языках.

      Насчёт производительности — есть много исследований, где изучался этот вопрос. По Intel у них на сайте сгруппировано удобно: Web Resources about Intel® Transactional Synchronization Extensions, в посте есть эта ссылка. В частности в свежем исследовании 2014 об отменах транзакций есть: Performance Evaluation of Intel® Transactional Synchronization Extensions for High-Performance Computing.

      Есть ещё у меня репозиторий, где собираю ссылки на работы. Давненько не обновлял правда, нужно заняться.
      • 0
        Есть ещё у меня репозиторий, где собираю ссылки на работы

        Вот ещё списочек работ по HTM, вроде не все у Вас есть (напр. по тому же AMD ASF).
        У меня есть и ещё один списочек по более общей области TM (я за ней слежу с 2007 года), если интересно, откопаю.

        Да-да, помимо пачки отличных программных продуктов (OpenSolaris, MySQL, OpenOffice) Oracle забросила и перспективную аппаратную технологию

        Технология аппаратной транзакционной памяти может быть и перспективная, а вот ROCK у Sun, если верить описаниям, действительно выходил монструозным и не совсем соответствующим рынку, тем более рынку, на котором работает Oracle. Легче было отменить проект, чем пытаться вытащить его, да ещё делать это одновременно с процессом интеграции одной компании в другую.
      • 0
        Могу еще предложить статью с реализацией транзакционной памяти на Smalltalk.
        • 0
          Спасибо. Встречал презентацию на ту же тему на slideshare, интересно.
    • 0
      Glibc для Linux относительно свежая должна использовать Intel RTM (если железо поддерживает) для обеспечения некоторых атомарных операций из стандарта POSIX-thread. Возможно, это не включено по умолчанию; я работал с версиями, которые требовали установку переменной окружения перед запуском приложений.
  • –1
    Почему я проголосовал «нет» на перспективу:
    — Хорошая идея — всегда видеть консистентное состояние на начало транзакции. Но этого недостаточно. Изначальная идея транзакций — чтобы параллельные вычисления выполнялись с точностью так, как бы они выполнялись последовательно, допуская единичные коллизии. MVCC такого не гарантирует — требуются блокировки (на чтение).
    — Архитектура большинства систем предполагает хранение состояния в persistence storage, а оперативная память используется лишь как временная внутри одной операции. Storage уже имеет все средства транзакций, плюс ряд преимуществ как масштабируемость, отказоустойчивость, etc… Для хранения состояния в памяти есть также куча in-memory storage.

    Для полноты картины реализации STM на Java:
    multiverse.codehaus.org/overview.html
    sites.google.com/site/deucestm/
    • 0
      TM — это альтернатива locked/lockfree алгоритмам, скажем для очереди заданий. когда несколько ядер интенсивно работают с одной структурой данных, TM позволяет уменьшить накладные расходы на синхронизацию. и алгоритмы с использованием транзакций писать проще
      • 0
        и алгоритмы с использованием транзакций писать проще

        Ещё пока сложно сказать, насколько проще — не хватает массива опытных данных. Однако есть исследования, подтверждающие это.

        Я могу сказать, что транзакции имеют одно преимущество при разработке перед классическими локами — это композиционность. Т.е. если мы одну транзакцию заворачиваем в другую (например, внутренняя пришла из библиотечной функции), то у нас всё продолжает работать согласно ожиданиям. Если же внутри одной критической секции мы пытаемся зайти ещё в одну, захватив ещё один lock, то можно оказаться в ситуации дедлока.
  • +1
    Статья мало понятная, больше похоже на обзор для тех кто уже в теме. Я весьма с трудом понял о чем речь и почти непонял профита, или случаем когда и как это можно использовать.
    Из примера на с++, построение гистограммы, если я правильно понял происходит «защита» доступа к массиву histogram. Так вот вопросы:
    1. Не понял зачем весь цикл выполняется в __transaction_atomic. Ведь получается что транзакцией выступает конечный результат всего цикла, а если это и есть основное действие выполняемое каждым из потоков, то как это вяжется с тем что транзакция будет отменена в случае если кто то другой уже успел изменить данные?
    2. Или же расчитывается на свойство комутативности операции ++, и типо в конце все транзакции будут применены по очереди? Это означает что результаты всех транзакйций должны быть сложены вместе. А почему не вычтены или замещены?
    3. А если мы всетаки делает не комутативные операции, или же они комутативны но с ограничениями? Работа с unsigned типом и операциями "-". Работа одного потока горантирует что тип не будет переполнен. Но если применять операции сразу из несколььких потоков в произвольном порядке то мы получим переполнение.
    • 0
      Хорошие вопросы, вы здорово разобрались.
      Общую информацию я поместил в начало, чтобы было более-менее понятно, как работает технология. Видимо, неудачно описал. Буду благодарен рекомендации, что поправить.
      Когда и как использовать технологию рекомендации вырабатываются. Можно сказать что в некоторых областях параллельного/многопоточного программирования технология будет полезной. Есть исследования по транзакционализации существующего кода, кое-кто даже для интереса в ядре Linux перевёл подсистему FUSE на использование транзакций. В библиотеке GLIBC «под капотом» уже используются транзакции, если их поддерживает аппаратное обеспечение.
      pthread_mutex_lock
      # define LLL_MUTEX_LOCK_ELISION(mutex) \
        lll_lock_elision ((mutex)->__data.__lock, (mutex)->__data.__elision, \
      		   PTHREAD_MUTEX_PSHARED (mutex))
      
      int
      __pthread_mutex_lock (mutex)
           pthread_mutex_t *mutex;
      {
       /* code */
      
      return LLL_MUTEX_LOCK_ELISION (mutex);
      
       /* code */
      
        return 0;
      }
      


      Где lll_lock_elision (lowlevellock.h):
      #define lll_lock_elision(futex, adapt_count, private) \
        __lll_lock_elision (&(futex), &(adapt_count), private)
      


      А __lll_lock_elision в свою очередь (elision-lock.c):
      /* Adaptive lock using transactions.
         By default the lock region is run as a transaction, and when it
         aborts or the lock is busy the lock adapts itself.  */
      int
      __lll_lock_elision (int *futex, short *adapt_count, EXTRAARG int private)
      {
        if (*adapt_count <= 0)
          {
            unsigned status;
            int try_xbegin;
      
            for (try_xbegin = aconf.retry_try_xbegin;
      	   try_xbegin > 0;
      	   try_xbegin--)
      	{
      	  if ((status = _xbegin()) == _XBEGIN_STARTED)
      	    {
      	      if (*futex == 0)
      		return 0;
      
      	      /* Lock was busy.  Fall back to normal locking.
      		 Could also _xend here but xabort with 0xff code
      		 is more visible in the profiler.  */
      	      _xabort (_ABORT_LOCK_BUSY);
      	    }
      
      	  if (!(status & _XABORT_RETRY))
      	    {
      	      if ((status & _XABORT_EXPLICIT)
      			&& _XABORT_CODE (status) == _ABORT_LOCK_BUSY)
      	        {
      		  /* Right now we skip here.  Better would be to wait a bit
      		     and retry.  This likely needs some spinning.  */
      		  if (*adapt_count != aconf.skip_lock_busy)
      		    *adapt_count = aconf.skip_lock_busy;
      		}
      	      /* Internal abort.  There is no chance for retry.
      		 Use the normal locking and next time use lock.
      		 Be careful to avoid writing to the lock.  */
      	      else if (*adapt_count != aconf.skip_lock_internal_abort)
      		*adapt_count = aconf.skip_lock_internal_abort;
      	      break;
      	    }
      	}
          }
        else
          {
            /* Use a normal lock until the threshold counter runs out.
      	 Lost updates possible.  */
            (*adapt_count)--;
          }
      
        /* Use a normal lock here.  */
        return LLL_LOCK ((*futex), private);
      }
      

      Насчёт примера с гистограммой: видимо, я себе плохо представляю работает __transaction_atomic в GCC. Когда я писал пример, сначала поставил блок транзакции на инкремент значения в массиве, внутри цикла. Производительность оказалась очень низкой. Потом я поместил весь цикл в транзакцию и производительность меня устроила — работает быстрее, чем код с атомарными операциями. Проверил корректность работы — всё в порядке. Сообщу вам, когда разберусь как это работает. Пока приложу дамп функции hist_updater, который GCC выдаёт по флагу -fdump-tree-tmlower:

      Версия с транзакцией внутри цикла:
      Скрытый текст
      hist_updater (void * data)
      {
        int D.4096;
        int D.4095;
        unsigned int D.4094;
        unsigned int luminance;
        struct pixel p;
        struct data * d;
        size_t i;
        void * D.4098;
        long unsigned int D.4097;
        double D.4093;
        double D.4092;
        double bY.2;
        double D.4090;
        int D.4089;
        unsigned char D.4088;
        double D.4087;
        double D.4086;
        double gY.1;
        double D.4084;
        int D.4083;
        unsigned char D.4082;
        double D.4081;
        double rY.0;
        double D.4079;
        int D.4078;
        unsigned char D.4077;
        struct pixel * D.4076;
        long unsigned int D.4075;
        struct pixel * D.4074;
      
        d = data;
        i = 0;
        goto <D.3999>;
        <D.3998>:
        try
          {
            D.4074 = d->pixels;
            D.4075 = i * 3;
            D.4076 = D.4074 + D.4075;
            p = *D.4076;
            D.4077 = p.red;
            D.4078 = (int) D.4077;
            D.4079 = (double) D.4078;
            rY.0 = 2.1260000000000001119104808822157792747020721435546875e-1;
            D.4081 = D.4079 * rY.0;
            D.4082 = p.green;
            D.4083 = (int) D.4082;
            D.4084 = (double) D.4083;
            gY.1 = 7.1519999999999994688693050193251110613346099853515625e-1;
            D.4086 = D.4084 * gY.1;
            D.4087 = D.4081 + D.4086;
            D.4088 = p.blue;
            D.4089 = (int) D.4088;
            D.4090 = (double) D.4089;
            bY.2 = 7.220000000000000028865798640254070051014423370361328125e-2;
            D.4092 = D.4090 * bY.2;
            D.4093 = D.4087 + D.4092;
            luminance = (unsigned int) D.4093;
            luminance = luminance + 1;
            __transaction_atomic  // SUBCODE=[ GTMA_HAVE_LOAD GTMA_HAVE_STORE ]
            try
              {
                D.4094 = luminance / 16;
                D.4095 = histogram[D.4094];
                D.4096 = D.4095 + 1;
                histogram[D.4094] = D.4096;
              }
            finally
              {
                __builtin__ITM_commitTransaction ();
              }
          }
        finally
          {
            p = {CLOBBER};
          }
        i = i + 1;
        <D.3999>:
        D.4097 = d->sz;
        if (D.4097 > i) goto <D.3998>; else goto <D.4000>;
        <D.4000>:
        free (d);
        D.4098 = 0B;
        goto <D.4099>;
        <D.4099>:
        return D.4098;
      }
      


      Версия с циклом внутри транзакции:
      Скрытый текст
      hist_updater (void * data)
      {
        unsigned int luminance;
        struct pixel p;
        long unsigned int D.4097;
        int D.4096;
        int D.4095;
        unsigned int D.4094;
        double D.4093;
        double D.4092;
        double bY.2;
        double D.4090;
        int D.4089;
        unsigned char D.4088;
        double D.4087;
        double D.4086;
        double gY.1;
        double D.4084;
        int D.4083;
        unsigned char D.4082;
        double D.4081;
        double rY.0;
        double D.4079;
        int D.4078;
        unsigned char D.4077;
        struct pixel * D.4076;
        long unsigned int D.4075;
        struct pixel * D.4074;
        struct data * d;
        size_t i;
        void * D.4098;
      
        d = data;
        __transaction_atomic  // SUBCODE=[ GTMA_HAVE_LOAD GTMA_HAVE_STORE ]
        try
          {
            i = 0;
            goto <D.3999>;
            <D.3998>:
            try
              {
                D.4074 = d->pixels;
                D.4075 = i * 3;
                D.4076 = D.4074 + D.4075;
                p = *D.4076;
                D.4077 = p.red;
                D.4078 = (int) D.4077;
                D.4079 = (double) D.4078;
                rY.0 = 2.1260000000000001119104808822157792747020721435546875e-1;
                D.4081 = D.4079 * rY.0;
                D.4082 = p.green;
                D.4083 = (int) D.4082;
                D.4084 = (double) D.4083;
                gY.1 = 7.1519999999999994688693050193251110613346099853515625e-1;
                D.4086 = D.4084 * gY.1;
                D.4087 = D.4081 + D.4086;
                D.4088 = p.blue;
                D.4089 = (int) D.4088;
                D.4090 = (double) D.4089;
                bY.2 = 7.220000000000000028865798640254070051014423370361328125e-2;
                D.4092 = D.4090 * bY.2;
                D.4093 = D.4087 + D.4092;
                luminance = (unsigned int) D.4093;
                luminance = luminance + 1;
                D.4094 = luminance / 16;
                D.4095 = histogram[D.4094];
                D.4096 = D.4095 + 1;
                histogram[D.4094] = D.4096;
              }
            finally
              {
                p = {CLOBBER};
              }
            i = i + 1;
            <D.3999>:
            D.4097 = d->sz;
            if (D.4097 > i) goto <D.3998>; else goto <D.4000>;
            <D.4000>:
          }
        finally
          {
            __builtin__ITM_commitTransaction ();
          }
        free (d);
        D.4098 = 0B;
        goto <D.4099>;
        <D.4099>:
        return D.4098;
      }
      


      • 0
        плохо оно может работать из-за того что изменения в одной строке памяти (64 байта) из разных ядер — очень медленная операция. так что тут важно что с блокировками будет ещё хуже (да и то не факт)
        • 0
          У меня так получалось:
          Скрытый текст

          Тот же график без одной ветви:

          • 0
            т.е. разница между мютексом и атомиком/транзакцией на порядок, а между атомиком и транзакцией почти нету. Последнее не плохо, хотябы потому что атомик это сугубо счетчик, а под транзакцией можно делать весьма сложную работа с данными. Но в этом случае я думаю и график измениться.

            Было бы интерестно посмотреть пример работы с ассоциативным контейнером в многопоточсное среде. Несовсем понятно должнали реализацию оного быть выполнена в транзакционном стиле.
          • 0
            кстати, а эти графики, в случае если цикл находить в транзакции? Вопрос в том находился ли цикл под мютексом в аналогичном примере, если нет, но это неправильный тест.
      • 0
        Думаю стоит сравнить сколько времени заимает захват мютекса с поддержкой транзакций и без. Это сильно бы прояснило перспективность подхода. Притом в двух случаях, конкурентный захват и нет.
  • 0
    del
  • 0
    Хм, а как HLE обеспечивает откат транзакционных операций?
    То есть пусть всем потокам сказано что лока нет, они проделали какую-то работу с разными непересекаюшимися участками памяти.
    Затем происходит модификация общих данных, и один из потоков продолжает выполнение, а что происходит с остальными?
    • 0
      А остальные откатываются на начало, если были конфликты. И повторяют вход в критическую секцию, или элизионно, или классически с атомарной инструкцией. Детали зависят от реализации.
      В классической схеме им бы просто не дали войти в критическую секцию, и все потоки, кроме одного, консервативно сидели на начале критической секции и по одиночке её проходили, даже если конфликт возникает крайне редко.

      Чтобы работал откат, во внутреннем буфере сохраняются состояния всех регистров перед входом в транзакцию. Есть и другие механизмы, например, вести лог изменений.
      • –1
        Понятно что можно много чего сделать, но используется ли это в текущем железе, вот в чем вопрос.
        В принципе проверить-то не сложно, только Haswell'a под рукой нет.
        Кроме регистров можно изменить еще много чего.
  • 0
    > В принципе проверить-то не сложно, только Haswell'a под рукой нет.
    Проверить так легко не получится, т.к. внутри транзакции нельзя остановиться дебаггером — такая попытка вызовет её откат.

    > Кроме регистров можно изменить еще много чего.
    Вообще рекомендую посмотреть спецификации, они многое объяснят — что можно делать внутри HLE-региона, а что нет. Например, x87 FPU, MSR, CR0-CR8, LDTR, GDTR и т.д. трогать нельзя — это вызовет откат. Свойство атомарности не зря придумано для транзакций.
  • 0
    Какие-то чуваки перевели статью и запостили на англоязычный аналог хабра без указания оригинала. Понятное дело, смысл терялся при прямом и обратном переводе. Балбесы =)
  • 0
    Интересно, тут вот говорят что STM хотели включить в .NET 4 (во всяком случае выпустили особую версию с ним). Неужто заглохло?
  • 0
    Возможно ли использовать трензакционную память не совсем по назначению?
    Например, решая переборную задачу, начинать транзакцию на каждый вариант и прерывать их, если в другой транзакции вариант оказался лучше?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.