Атомарна операція

Атомарна операція (англ. atomic operation, англ. atomic action) в програмуванні означає набір інструкцій з властивістю неперервності цілої операції. Окремі кроки операції можуть відбуватись в різний час та у різних частинах системи, однак для зовнішнього спостерігача така операція виглядає єдиною та неподільною[1].

Атомарна операція виконується повністю (або відбувається відмова у виконанні), без переривань. Атомарність має особливе значення в багатопроцесорних комп'ютерах і багатозадачних операційних системах, оскільки доступ до ресурсів, що не розподіляються, повинен бути обов'язково атомарним[джерело?].

Атомарна операція відкрита впливу тільки одної ниті[джерело?].

Атомарність буває апаратною (коли безперервність забезпечується апаратурою) і програмною, коли використовуються спеціальні засоби міжпрограмної взаємодії (м'ютекс, семафор). За своєю суттю програмні засоби забезпечення атомарності складаються з двох етапів — блокування ресурсу і виконання самої операції. Блокування є атомарною операцією, яка або успішна, або повертає повідомлення про зайнятість[джерело?].

Огляд

Наприклад, у випадку роботи декількох нитей, коли одна з них виконує атомарну операцію, решта не може бачити проміжні стани до завершення цієї операції. Система може перебувати лише або в стані, в якому вона була до початку операції, або ж після неї, але не в проміжному стані[2].

У випадку ACID, натомість, атомарність стосується набору певних дій зі зміни даних, оскільки умови доступу до спільних даних для читання визначені у властивості «ізольованості» (англ. isolation)[2].

Якщо дії зі зміни спільних даних (запис) згуртовано в єдину атомарну операцію (транзакцію), і ця операція не може бути завершена (через будь-який збій), тоді така операція має бути повністю скасована а спільні дані (наприклад, база даних) повернуті до початкового стану[2].

В системах без атомарності при збої транзакції виникає проблема з визначення які операції вже успішно виконано, а які — ні, а при повторній спробі виконати транзакцію певні операції можуть бути виконані двічі й тим самим спотворити стан системи[2].

Атомарність значно спрощує обробку помилок: якщо транзакцію скасовано, можна бути впевненим у тому, що система перебуває у початковому стані й можна здійснити повторну спробу її виконати[2].

Можливість скасування транзакції з автоматичним відкиданням всіх змін є основною властивістю у випадку ACID[2].

Умови

Набір дій може вважатися атомарним, коли виконуються дві умови:

  1. Поки повний набір дій не завершується, ніякий інший процес не може знати про зроблені зміни (невидимість); і
  2. Якщо будь-яка з дій не виконалася, тоді не виконується повний набір дій, і стан системи відновлюється до того стану, в якій це знаходилося перед тим, як будь-яка з дій почалася.

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

Реалізації

Мікропроцесори x86 та x86-64

Атомарні операції описані в третьому томі керівництва розробника для архітектури IA-32 та x86-64[3].

Мікропроцесори цих архітектур мають три взаємозалежні механізми для виконання атомарних операцій:[3]

  • гарантовано атомарні операції,
  • блокування шини із використанням сигналу LOCK# та префіксу інструкцій асемблера LOCK,
  • протоколи кеш когерентності, які гарантують виконання атомарних операцій над кешованими даними (блокування кешу).

Ці операції взаємно залежні оскільки:

  • Певні операції з пам'яттю (наприклад, зчитування чи запис байту) завжди атомарні. Тобто, мікропроцесор гарантує, що після початку такої операції вона буде завершена до того, як інший мікропроцесор або інший агент шини отримає доступ до цієї комірки пам'яті.
  • Мікропроцесор також підтримує блокування шини для виконання певних операцій (таких, як зчитування-зміна-запис в спільному регіоні пам'яті), які мають бути виконані атомарно, однак зазвичай не мають гарантій атомарного виконання.
  • Оскільки регіони пам'яті, до яких часто звертається мікропроцесор, може бути закешовано в кеші L1 або L2 мікропроцесора, операції можуть бути виконані атомарно в самому мікропроцесорі без блокування шини. В такому випадку протоколи кеш когерентності дбають про те, аби інші мікропроцесори, які могли закешувати ті самі регіони пам'яті, коректно оброблять атомарні операції виконані для кешованих даних[3].

Мікропроцесори сімейства Intel486 та новіші гарантують атомарність операцій:[3]

  • зчитування або запис одного байту,
  • зчитування або запис слова вирівненого за 16-бітовою границею,
  • зчитування або запис подвійного слова вирівненого за 32-бітовою границею.

Мікропроцесори сімейства Pentium та новіші додатково гарантують атомарність таких операцій:[3]

  • зчитування або запис чотири-слова вирівненого за 64-бітовою границею,
  • доступ до незакешованих 16-біт пам'яті що можуть поміститись всередині 32-бітової шини даних.

Мікропроцесори сімейства P6 та новіші додатково гарантують атомарність таких операцій:[3]

  • Невирівняний 16-, 32-, та 64-бітовий доступ до кешованих регіонів пам'яті, що повністю знаходиться в одному рядку кешу.

Приклад

Один процес

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

  1. процес читає значення в комірку пам'яті;
  2. процес додає один до значення;
  3. процес пише нове значення назад в комірку пам'яті.

Два процеси

Тепер уявімо два процеси виконують збільшенням одної, розподіленої комірки пам'яті:

  1. перший процес читає значення в комірку пам'яті;
  2. перший процес додає один до значення;

але перед тим, як перший процес зможе написати нове значення назад до розташування пам'яті, він зупиняється, і починає виконуватися другий процес:

  1. другий процес читає значення в комірку пам'яті, таке ж значення, що перше читання процесу;
  2. другий процес додає один до значення;
  3. другий процес вписує нове значення в комірку пам'яті.

Нарешті зупиняється і другий процес, і перший процес відновлює виконання:

  1. перший процес вписує тепер-хибне значення в комірку пам'яті, бо він непопереджений, що інший процес вже змінив значення в комірці пам'яті.

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

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

Блокування

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

Загальні примітиви

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

Наступні інструкції прямо використовуються компіляторами і операційними системами, але також можуть бути абстраговані і представлені як байт-код або бібліотечні функції в мовах високого рівня.

  • Atomic read and write (атомарні читатання та запис)
  • Test-and-set (провірити-і-встановити)
  • Fetch-and-add (вибрати-і-додати)
  • Compare-and-swap (порівняти-і-переставити)
  • Load-Link/Store-Conditional (Завантажити-зв'язати/Зберегти-умовно)

Багато з цих примітивів можуть бути реалізовані в термінах інших

Реалізації
  • atomic.h — більшість систем постачає низькорівневий C-інтерфейс до атомарних операцій, проте, найменування, порядок аргументів, повернуті значення і семантика значно різняться між операційними системами, тобто бібліотеки і застосунки, що використовують цей інтерфейс напряму, будуть прив'язані до конкретної операційної системи
  • APR — бібліотека Apache Portable Runtime постачає набір макросів з функціями атомарних операцій для використання в програмах з ліцензією MPL.
  • Атомарні операції в GLib
  • open-std.org: «An Atomic Operations Library for C++»
  • java.util.concurrent.atomic в JDK

Примітки
  1. Reed, D.P. (01 1979). Implementing Atomic Actions on Decentralized Data. Proceedings of the Seventh Symposium on Operating System Principles: 163. doi:10.1145/800215.806584.
  2. Martin Kleppmann (2017). Chapter 7: Transactions. Designing Data-Intensive Applications. с. 224. ISBN 978-1-449-37332-0.
  3. 8.1 Locked Atomic Operations. Intel 64 and IA-32 Architecture Software Developer's Manual. Volume 3: System Programming Guide.

Див. також


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.