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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Умови[ред.ред. код]

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

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

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

Приклад[ред.ред. код]

Один процес[ред.ред. код]

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

  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