Програмна транзакційна пам'ять

В комп'ютерних технологіях, програмна транзакційна пам'ять (англ. software transactional memory, STM) являє собою механізм управління паралелізмом, аналогічний механізму транзакцій баз даних для управління доступом до спільно використовуваної пам'яті в паралельних обчисленнях. Це альтернатива для синхронізації на основі блокування. Транзакція в цьому контексті є частиною коду, який виконує зчитування і запис в поділювану (спільно використовувану) пам'ять. Зчитування і запис логічно відбувається в одиничний момент часу, а проміжні стани невидимі для інших (результативних) транзакцій. Ідея забезпечення транзакцій апаратною підтримкою зародилася в 1986 році в роботі і патенті Тома Найта^[en]^[1]. Ідея отримала публічне висвітлення завдяки Морісу Герлігі^[en] і Еліоту Моссу^[en]^[2]. У 1995 році Нір Шавіт^[en] і Ден Тойту доповнили цю ідею до програмної транзакційної пам'яті (ЅТМ)^[3]. STM як і раніше знаходиться в центрі інтенсивних досліджень^[4]; зростає її підтримка для практичних реалізацій.

Характеристика ред.

На відміну від методів блокування, що використовуються в більшості сучасних багатопоточних додатків, STM дуже оптимістична: потік завершує зміни поділюваної пам'яті без урахування того, що роблять інші потоки, і реєструє будь-яке зчитування і запис в лог. Замість того, щоб використовувати записувальний пристрій для перевірки, чи не має він негативного впливу на інші діючі операції, відповідальність передається зчитувальному пристрою, який після завершення повної транзакції перевіряє, чи не зробили інші потоки паралельно зміни в пам'яті, до якої був отриманий доступ в минулому. Ця остання операція, в якій перевіряються зміни транзакцій і яка, якщо перевірка успішна, залишається незмінною, називається фіксацією. Транзакція може припинитися в будь-який час, в результаті чого всі останні зміни будуть скасовані. Якщо транзакція не може бути здійснена через конфлікти змін, вона переривається і повторно виконується спочатку до тих пір, поки результативно не завершиться.

Перевага такого оптимістичного підходу зростає завдяки паралелізму: жодному потоку не потрібно чекати отримання доступу до ресурсу, і різні потоки можуть одночасно і безпечно модифікувати непересічні частини структури даних, які захищалися б одним локом.

Однак на практиці ЅТМ-системи програють в продуктивності дрібномодульним системам, заснованим на блокуваннях, на невеликій кількості процесорів (від 1 до 4 в залежності від програми). Це пов'язано в першу чергу з накладними витратами на підтримку лога і з часом, що витрачається на здійснення транзакцій. Але навіть у цьому випадку продуктивність відрізняється не більш, ніж в 2 рази^[5]. Прихильники STM вважають, що такі втрати виправдані концептуальними перевагами ЅТМ.

Теоретично, часова і просторова складності виконання n паралельних транзакцій в гіршому випадку - O(n). Фактичні витрати залежать від реалізації (можна скасувати транзакцію на ранній стадії, щоб уникнути накладних витрат), але завжди будуть випадки, хоч і рідкі, коли lock-алгоритми будуть мати кращу часову складність, ніж програмна транзакційна пам'ять.

Концептуальні переваги і недоліки ред.

Також STM значно спрощує концептуальне розуміння багатопотокових програм і допомагає їх зручному супроводу, злагоджено працюючи з існуючими високорівневими абстракціями, такими як об'єкти і модулі.

Lock-програмування містить ряд відомих проблем, які часто виникають на практиці:

Важливо пам'ятати про операції які пересікаються і часткових операціях в розділених і непов'язаних з першого погляду частинах коду — завдання дуже важке і в ньому можна зробити багато помилок.
Воно вимагає від програмістів освоювати політику блокування, щоб уникнути тупиків (Deadlock) та інших проблем управління процесами. Така політика часто приводиться у виконання довільним чином і буває помилковою, і коли виникають проблеми, їх важко відновити і налагодити.
Це може призвести до інверсії пріоритетів — явище, при якому високопріоритетний потік змушений очікувати низькопріоритетний потік, що має винятковий доступ до необхідного ресурсу.

Навпаки, концепція транзакційної пам'яті набагато простіша, тому що кожна транзакція може розглядатися окремо, як однопотокове обчислення. Тупики або запобігаються повністю, або дозволяються зовнішньою програмою управління транзакціями; програмісту навряд чи потрібно турбуватися про це. Інверсія пріоритетів може бути проблемою, але пріоритетні транзакції можуть перервати конфліктуючі низькопріоритетні операції, які ще не були здійснені.

З іншого боку, необхідність переривання невдалих транзакцій також накладає обмеження на їх поведінку: вони не можуть виконувати будь-які операції, які не можуть бути скасовані, у тому числі більшість вводів-виводів. Такі обмеження, як правило, на практиці долаються шляхом створення буферів, які ставлять в чергу незворотні операції і виконують їх через деякий час поза будь-якою транзакцією. У мові Хаскель це обмеження приводиться у виконання системою типів під час компіляції.

Компонувальні операції ред.

У 2005 році Тім Харріс, Саймон Марлоу, Саймон Пейтон Джонс і Моріс Герлігі^[en] описали STM-систему, створену на Хаскелі, який реалізує паралелізм. Ця система дозволяє довільним атомарним операціями компонуватися в більш великі атомарні операції — корисна концепція, неможлива при lock-програмуванні. За словами авторів:

«Мабуть, найфундаментальніший недолік у тому, що lock-програми не можуть компонувати: коректні фрагменти можуть не спрацювати, пропри скомпонованість. Розглянемо, наприклад, геш-таблицю з потокобезпечними операціями вставлення і видалення. Тепер припустимо, що ми хочемо видалити один елемент з таблиці t1 і вставити його в таблицю t2, але проміжний стан (у якому жодна таблиця не містить цього елемента) не має бути видимим для інших потоків. Поки конструктор геш-таблиці не передбачить цієї потреби, просто не існує способу задовольнити цю вимогу. Загалом, операції, коректні поодинці (вставлення, видалення), не можна скомпонувати в більші коректні операції»

— Tim Harris et al., "Composable Memory Transactions", Section 2: Background, pg.2^[6]

З STM ця проблема вирішується просто: просте об'єднання двох операцій в одній транзакції перетворює операцію яка компонується в атомарну. Єдиним каменем спотикання є те, що для абонента, який не знає деталей реалізації методів компонування, неясно коли вони повинні спробувати повторно виконати транзакцію, якщо вона не проводиться. У відповідь на це, автори запропонували команду повторної спроби, яка використовує журнал транзакцій (log-файл), що генерується невдалою транзакцією для визначення нею ділянки пам'яті яка зчитується. Тоді вона знову автоматично запускає дану транзакцію, коли одна з цих ділянок пам'яті змінюється. Це ґрунтується на логіці, що транзакція не буде вести себе інакше, поки хоча б одне таке значення не змінилося.

Автори також запропонували механізм побудови альтернатив (функція абоІнакше — orElse). Він запускає одну транзакцію і, якщо транзакція робить повторну спробу, запускає другу. Якщо те ж відбувається і з другою, механізм запускає їх обидві знову, поки не відбудуться суттєві зміни. Дана функція, зіставлювана з функцією мережевого стандарту POSIX select(), дозволяє тому, хто викликає її, очікувати будь-яке з ряду подій одночасно. Вона також спрощує програмування інтерфейсів, наприклад, шляхом надання простого механізму конвертації між блокуючими і неблокуючими операціями.

Ця схема була реалізована в компіляторі мови Хаскель GHC.

Пропонована допоміжна мова ред.

Концептуальна простота ЅТМ-систем дозволяє програмісту легко працювати з ними, використовуючи відносно простий синтаксис мови. У своїй книзі «Допоміжна мова для легких транзакцій» Тім Харріс і Кейр Фрейзер запропонували ідею використання класичної умовної критичної області (CCR) для подання транзакцій. У своїй найпростішій формі це всього лише «атомарний блок», ділянка коду, яка послідовно виконується в одиничний момент часу:

// Атомарна вставка вузла в двохзв'язний список
atomic {
    newNode->prev = node;
    newNode->next = node->next;
    node->next->prev = newNode;
    node->next = newNode;
}

По досягненні кінця блоку транзакція здійснюється, якщо це можливо, інакше припиняється і повторюється. Умовні критичні області також допускають умову збереження, що дозволяє транзакції очікувати виконання, поки діє її завдання.

atomic (queueSize > 0) {
    remove item from queue and use it
}

Якщо умова не виконується, програма управління (менеджер) транзакцій буде чекати, поки не прийде інша, яка вплине на умову перш, ніж повторить спробу. Такий вільний зв'язок між виробниками і споживачами удосконалює модульний принцип порівняно з чітким сигналізуванням між потоками. Книга «Компонована операція звернення до пам'яті» пішла далі зі своєю командою повторної спроби (див. вище), яка може в будь-який час перервати транзакцію і чекати, поки не відбудеться яка-небудь зміна значення, раніше зчитаного цією операцією, перед повторенням спроби. Приклад:

atomic {
    if (queueSize > 0) {
        remove item from queue and use it
    }  
    else {
        retry
    }
}

Ця здатність динамічного повторення в кінці транзакції спрощує модель програмування і відкриває нові можливості.

Однією з проблем є поведінка винятків, коли вони поширюються за межі транзакцій. У праці "Компонована операція звернення до пам'яті" автори вирішили, що це має перервати транзакцію, так як виключення зазвичай вказують на несподівані помилки в мові Хаскель (з паралелізмом), але те, що цей виняток може зберігати надану інформацію та зчитувати її під час транзакції в цілях діагностики. Вони підкреслюють, що ймовірні також інші проектні рішення при інших параметрах.

Транзакційне блокування ред.

ЅТМ може бути реалізована як алгоритм без блокувань і з блокуваннями. Є два типи блокування.

Блокування при зіткненні операцій (Еналса, Саха і Харріса), при якому записи в пам'ять здійснюються, спочатку тимчасово блокуючи цю область пам'яті, безпосередньо записуючи значення і реєструючи їх у журналі реєстрації відкатів операцій.
Блокування при здійсненні транзакції, яке блокує комірки пам'яті тільки під час вчинення фази.

Схема здійснення транзакції, названа «Транзакційне блокування-2» і реалізована Дайсом, Шалевим і Шавітом, використовує глобальний час. Кожна транзакція починається із зчитування поточного значення часу і зберігає його для зчитування. Потім при кожному зчитуванні і записі версія певної області пам'яті порівнюється з версією для читання, і, якщо воно більше, то транзакція скасовується. Це гарантує, що код виконається на відповідній копії пам'яті. Під час вчинення всі області читання заблоковані, і значення даної версії всіх областей пам'яті для запису і читання повторно перевіряються. Нарешті, глобальний час збільшується, нові значення запису з журналу записуються назад в пам'ять із зазначенням нової версії часу.

Все більш популярним методом управління транзакційними конфліктами в транзакційної пам'яті, особливо в ЅТМ, є порядок вчинення^[en] (ПВ). Він використовується для досягнення впорядкованості безблоковувано (тобто без блокування при конфлікті операцій і тільки з блокуванням при здійсненні транзакції) за допомогою зміни порядку здійснення транзакцій (наприклад, Рамадан і співавтори, 2009, і Жанг і співавтори, 2006). Впорядкованість є основою для коректного стану транзакційної пам'яті (при виконанні паралельних транзакцій). Вже були опубліковані десятки статей та патентів про STM із застосуванням «порядку вчинення».

«Жанг і співавтори, 2006» — патент США, який несе назву «Програмне забезпечення порядку здійснення транзакцій і управління конфліктами» (який посилається на патент США 5701480 про порядок вчинення). Розробляються різні технології та методи для застосування порядку вчинення в системі програмної транзакційної пам'яті. Система програмної транзакційної пам'яті забезпечена функцією, щоб зумовлений порядок вчинення був застосовний для безлічі операцій. Визначений порядок вчинення використовується під час виконання, щоб встановити порядок, в якому здійснювати транзакції в системі програмної транзакційної пам'яті. Процес управління конфліктами викликається, коли відбувається конфлікт між першою і другою транзакціями. Визначений порядок вчинення використовується в процесі управління конфліктами, щоб визначити, яка з транзакцій повинна виграти конфлікт і отримати дозвіл на продовження. З порядком здійснення бажана властивість впорядкованості відбувається шляхом здійснення транзакцій тільки в хронологічному порядку, сумісному з порядком по пріоритету (як визначено хронологічним порядком операцій в конфліктах)

Реалізації ред.

SRTM було реалізовано (різної якості і стабільності) на різних мовах програмування. Таких, як:

C/C++ ред.

TBoost.STM (formerly DracoSTM) Спільні зусилля CU-Boulder і Boost Libraries Group створили для C++ STM бібліотеку, в першу чергу автором якого є Justin E. Gottschlich і Jeremy G. Siek.
TinySTM a time-based STM і Tanger to integrate STMs з C and C++ через LLVM.
Lightweight Transaction Library (LibLTX), реалізація для C, (автор Robert Ennals) основний акцент зроблено на ефективність. Реалізація ґрунтується на його статтях «Software Transactional Memory Should Not Be Obstruction-Free» і «Cache Sensitive Software Transactional Memory».
LibCMT, реалізація з відкритим кодом для C, зроблена Duilio Protti і заснована на «Composable Memory Transactions». Ця реалізація також включає C# binding.
TARIFA є прототипом, який дає «atomic» ключове слово в C/C++.
Intel STM Compiler Prototype Edition реалізація STM для C/C++ безпосередньо в компіляторі (Intel Compiler) для Linux або Windows, генеруючому 32 або 64 бітний код для процесорів Intel і AMD. Реалізує «атомне» ключове слово, а також надає способи декорації визначення функцій (declspec) для управління / дозволу на використання в «атомних» секціях.
stmmap реалізація STM в C, заснована на поділюваній пам'яті. Призначена для спільного використання пам'яті між потоками і / або процесами (а не тільки між потоками всередині процесу) з семантикою транзакцій. В C++ реалізована багатопотокова версія даного аллокатора.
CTL реалізація STM в C, заснована на TL2, але з багатьма розширеннями і оптимізаціями.
Several implementations by Tim Harris & Keir Fraser, заснована на ідеї зі статей «Language Support for Lightweight Transactions», «Practical Lock Freedom», і майбутньої неопублікованій роботі.
RSTM University of Rochester STM написана командою вчених під керівництвом Michael L. Scott.
G++ 4.7 вже підтримує STM для C/C++ прямо в компіляторі. Ця можливість досі числиться експериментальною, але забезпечує необхідну для тестування функціональність.

C# ред.

SXM, реалізація для C# Microsoft Research. Documentation, Download page^{[недоступне посилання з червня 2019]}.
LibCMT, реалізація з відкритим кодом, (Duilio Protti) базується на «Composable Memory Transactions». Реалізація також включає C# binding.
NSTM, .NET Software Transactional Memory, написаний повністю на C#, пропонує вкладені транзакції і навіть інтеграцію з System.Transactions.
MikroKosmos A Verification-Oriented Model Implementation of an STM in C#.

Clojure підтримка STM вбудована в ядро мови.

Haskell ред.

STM бібліотека, як сказано в «Composable Memory Transactions», є частиною Haskell Platform.

Java ред.

SCAT research group реалізація AtomJava.
JVSTM реалізує концепцію Versioned Boxes, запропоновану João Cachopo і António Rito Silva, членами Software Engineering Group — INESC-ID
XSTM є відкритим вихідним кодом для Java і .NET з розширюваною архітектурою. XSTM реалізований у вигляді бібліотеки, а також надає розширення для повідомлення про зміни, наполегливості і реплікації об'єктів.
Deuce Середовище розробки для Java Software Transactional Memory, використовує байт-код.
Multiverse Java 1.6+ заснована на Software Transactional Memory (STM). Ця реалізація, використовує Multi Version Concurrency Control (MVCC) як паралельний механізм контролю.
DSTM2 Sun lab's Dynamic STM бібліотека.
ObjectFabric дистрибутив STM.

OCaml ред.

coThreads і одночасно бібліотека програмування OCaml, пропонує STM (originally STMLib) як модуль. Як і будь-який інший компонент у цій бібліотеці, STM модуль може бути використаний разом з VM-level threads, системою потоків і процесів.

Perl ред.

STM для Perl 6 був реалізований в Pugs через STM бібліотеку Glasgow Haskell Compiler.

Python ред.

Durus проста, але повна і швидка, STM реалізація для Python, що дозволяє використовувати STM усередині одного процесу і STM в server/multiple клієнт архітектурі. На додаток до вбудованої пам'яті формату існують і інші, наприклад Berkeley DB доступна тут.
Fork of CPython with atomic locks — Armin Rigo пояснює свій патч для CPython в an email to the pypy-dev list.
pypy-stm — надбудова над PyPy c робочої реалізацією інтерпретатора Python 2.7, підтримує одночасне виконання ниток існуючих багатопоточних додатків на різних ядрах CPU.

Scala ред.

ScalaSTM Легка бібліотечна STM для Scala.
RadonSTM STM для Scala, яка була реалізована як частина проекту Activate Framework

atomic (queueSize > 0) {
    remove item from queue and use it
}

Якщо умова не виконується, програма управління (менеджер) транзакцій буде чекати, поки не прийде інша, яка вплине на умову перш, ніж повторить спробу. Такий вільний зв'язок між виробниками і споживачами удосконалює модульний принцип порівняно з чітким сигналізуванням між потоками. Книга «Компонована операція звернення до пам'яті» пішла далі зі своєю командою повторної спроби (див. вище), яка може в будь-який час перервати транзакцію і чекати, поки не відбудеться яка-небудь зміна значення, раніше зчитаного цією операцією, перед повторенням спроби. Приклад:

ЅТМ може бути реалізована як алгоритм без блокувань і з блокуваннями. Є два типи блокування.

Блокування при зіткненні операцій (Еналса, Саха і Харріса), при якому записи в пам'ять здійснюються, спочатку тимчасово блокуючи цю область пам'яті, безпосередньо записуючи значення і реєструючи їх у журналі реєстрації відкатів операцій.
Блокування при здійсненні транзакції, яке блокує комірки пам'яті тільки під час вчинення фази.

З порядком здійснення бажана властивість впорядкованості відбувається шляхом здійснення транзакцій тільки в хронологічному порядку, сумісному з порядком по пріоритету (як визначено хронологічним порядком операцій в конфліктах)

Smalltalk

GemStone/S [1] Transactional Memory Object Server для Smalltalk.

Інші мови ред.

Fortress мова розроблений Sun, використовує DSTM2
STM.NET

Примітки ред.

↑ Tom Knight. An architecture for mostly functional languages. Proceedings of the 1986 ACM conference on LISP and functional programming.
↑ Maurice Herlihy and J. Eliot B. Moss. Transactional memory: architectural support for lock-free data structures. Proceedings of the 20th annual international symposium on Computer architecture (ISCA '93). Volume 21, Issue 2, May 1993.
↑ Nir Shavit and Dan Touitou. Software transactional memory. Distributed Computing. Volume 10, Number 2. February 1997.
↑ "software transactional memory" - Google Scholar. Процитовано 10 листопада 2013.
↑ Simon Peyton-Jones. Programming in the Age of Concurrency: Software Transactional Memory. Channel 9. Процитовано 9 червня 2007.
↑ Harris, T.; Marlow, S.; Peyton-Jones, S.; Herlihy, M. (2005). Composable memory transactions (PDF). Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming - PPoPP '05. с. 48. doi:10.1145/1065944.1065952. ISBN 1595930809.

Посилання ред.

Morry Katz, PARATRAN: A transparent transaction based runtime mechanism for execution of parallel Scheme, MIT LCS, 1989
Nir Shavit and Dan Touitou. Software Transactional Memory. Proceedings of the 14th ACM Symposium on Principles of Distributed Computing^[en], pp. 204-213. August 1995. The paper originating STM.
Maurice Herlihy, Victor Luchangco, Mark Moir, and William N. Scherer III. Software Transactional Memory for Dynamic-Sized Data Structures. Proceedings of the Twenty-Second Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing^[en] (PODC), 92-101. July 2003.
Tim Harris and Keir Fraser. Language Support for Lightweight Transactions. Object-Oriented Programming, Systems, Languages, and Applications, pp. 388-402. October 2003.
Tim Harris, Simon Marlow, Simon Peyton Jones and Maurice Herlihy. Composable Memory Transactions. ACM Symposium on Principles and Practice of Parallel Programming^[en] 2005 (PPoPP'05). 2005.
Robert Ennals. Software Transactional Memory Should Not Be Obstruction-Free.
Michael L. Scott et al. Lowering the Overhead of Nonblocking Software Transactional Memory gives a good introduction not only to the RSTM but also about existing STM approaches.
Torvald Riegel and Pascal Felber and Christof Fetzer, A Lazy Snapshot Algorithm with Eager Validation introduces the first time-based STM.
Dave Dice, Ori Shalev, and Nir Shavit. Transactional Locking II.
Knight, TF, An architecture for mostly functional languages, ACM Lisp and Functional Programming Conference, August, 1986.
Knight, TF, System and method for parallel processing with mostly functional languages, US Patent 4,825,360, April, 1989.
Ali-Reza Adl-Tabatabai, Christos Kozyrakis, Bratin Saha, Unlocking concurrency, ACM Queue 4, 10 (December 2006), pp 24-33. Ties multicore processors and the research/interest in STM together.
James R Larus, Ravi Rajwar, Transactional Memory, Morgan and Claypool Publishers, 2006.
Леонід Черняк. Транзакційна пам'ять — перші кроки // «Відкриті системи» , № 04, 2007

Це незавершена стаття про програмування.
Ви можете допомогти проєкту, виправивши або дописавши її.

[1] Tom Knight. An architecture for mostly functional languages. Proceedings of the 1986 ACM conference on LISP and functional programming.

[Herlihy1993-2] Maurice Herlihy and J. Eliot B. Moss. Transactional memory: architectural support for lock-free data structures. Proceedings of the 20th annual international symposium on Computer architecture (ISCA '93). Volume 21, Issue 2, May 1993.

[3] Nir Shavit and Dan Touitou. Software transactional memory. Distributed Computing. Volume 10, Number 2. February 1997.

[4] "software transactional memory" - Google Scholar. Процитовано 10 листопада 2013.

[5] Simon Peyton-Jones. Programming in the Age of Concurrency: Software Transactional Memory. Channel 9. Процитовано 9 червня 2007.

[cmt-6] Harris, T.; Marlow, S.; Peyton-Jones, S.; Herlihy, M. (2005). Composable memory transactions (PDF). Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming - PPoPP '05. с. 48. doi:10.1145/1065944.1065952. ISBN 1595930809.

[1]

[2]

[3]

[4]

[5]

[6]