Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 24.06.2014 | нет комментариев

Определение

Параллельное программирование трудно. При применении систем с всеобщей памятью не обойтись без синхронизации доступа параллельных процессов/потоков к всеобщему источнику (памяти). Для этого применяются:

  • блокировки (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 HerlihyRavi RajwarNir Shavit. Первые изыскания предлагали аппаратные реализации транзакционной памяти, которым не суждено было родиться ещё 30 лет.
В 1990-х возникли первые программные реализации спецтехнологии, аппаратные реализации подтянулись к 2000-ым.

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

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

Clojure

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

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

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

1-й торговый сервер с помощью инструкций транзакционной памяти. При применении транзакционной памяти 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 состоит из 2-х частей. Аппаратное исключение блокировок (Hardware Lock Elision, HLE) предоставляет примитивную конвертацию программ на основе блокировок в транзакционные программы, причём полученные программы будут обратно совместимы с существующими процессорами. Ограниченная транзакционная память (Restricted Transactional Memory, RTM) является больше полной реализацией транзакционной памяти.

Hardware Lock Elision

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

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

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

Спецтехнология обратно совместима с процессорами без поддержки HTM. Операции по управлению блокиро_rqvmk!

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

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

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

Увлекателен ли пост, требуется moar?

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

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

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB