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

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

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

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

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

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

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

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

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

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

У 2005 році Тім Харріс, Саймон Марлоу, Саймон Пейтон Джонс і Моріс Герлігі описали 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» і реалізована Дайсом, Шалевим і Шавітом, використовує глобальний час. Кожна транзакція починається із зчитування поточного значення часу і зберігає його для зчитування. Потім при кожному зчитуванні і записі версія певної області пам'яті порівнюється з версією для читання, і, якщо воно більше, то транзакція скасовується. Це гарантує, що код виконається на відповідній копії пам'яті. Під час вчинення всі області читання заблоковані, і значення даної версії всіх областей пам'яті для запису і читання повторно перевіряються. Нарешті, глобальний час збільшується, нові значення запису з журналу записуються назад в пам'ять із зазначенням нової версії часу.

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

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

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

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

• 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, 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 (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 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