Блокування (програмування)

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

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

Типи блокування[ред. | ред. код]

  • М'яке блокування — кожен потік перед доступом до спільного ресурсу повинен заблокувати ресурс;
  • Обов'язкове блокування — коли доступ до заблокованого ресурсу породжує виняткову ситуацію в потоці, що намагався отримати доступ.

Блокування відрізняються по типу доступу до даних:

  • спільне (тільки для читання) англ. shared (read only);
  • ексклюзивне (для читання та запису) англ. exclusive (read-write).

Найпростіший спосіб блокування — бінарний семафор. Він не розрізняє типи доступу до даних.

Типи блокувань відрізняються по стратегії продовження виконання потока, що заблокований:

  • потік призупиняє виконання і планувальник потоків запускає наступний потік;
  • spinlock — потік в циклі очікує на доступ до ресурсу. Таке блокування має перевагу коли очікування є короткими.

Реалізація[ред. | ред. код]

Для ефективної реалізації механизму блокування потрібна підтримка на апаратному рівні, наприклад, у вигляді однієї із атомарних операції таких як «test-and-set», «fetch-and-add» чи«compare-and-swap», що дозволяють перевірити наявність блокування і якщо воно відсутнє встановити його.

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

В системах де не існує таких атомарних операцій можна використовувати алгоритм Декера чи алгоритм Пітерсона.

Гранулярність блокування[ред. | ред. код]

Гранулярність блокування — це міра кількості даних для блокування. Гранулярність блокування є компромісом між:

  • накладними витратами — розміром пам'яті для створення блокуваннь та команд процесора для блокування/розблокування ресурсів;
  • суперництвом за блокування — чим меншу кількість даних буде заблоковано, тим менша імовірність очікування зняття блокування;
  • взаємним блокуванням — чим більша кількість блокувань, вища імовірність отримати взаємне блокування.

Блокування читання та запису[ред. | ред. код]

Блокування читання та запису англ. read–write lock (RW lock) — примітив синхронізації для розв'язання задачі читачів та записувачів.

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

Застосовується для структур даних, що не можуть бути записані атомарною операцією (наприклад алгоритмом read-copy-update).

RW блокування може бути реалізоване з різними пріорітетами читання та запису:

  • RW блокування з пріорітетом читання — записувач не може заблокувати ресурс, якщо хоч один читач блокує його.
    • Режим з найбільшою паралельністю виконання, але можливий ресурсний голод для записувачів.
  • RW блокування з пріорітетом запису — забороняє новим читачам блокувати ресурс, якщо записувач очікує на отримання блокування.
    • Найменша паралельність виконання, можливий ресурсний голод для читачів. На відміну від попереднього випадку, потребує 2 м'ютекса, замість одного.
  • RW блокування без пріоритету — алгоритми без ресурсного голоду, наприклад FIFO.


Реалізація
  • pthread_rwlock_t в стандарті POSIX [1]
  • boost::shared_mutex та boost::upgrade_mutex в Boost[3]
  • System.Threading.ReaderWriterLockSlim в .NET[4]
  • ReadWriteLock[5] та ReentrantReadWriteLock[6] в Java version 5

Блокування (СУБД)[ред. | ред. код]

...


Примітки[ред. | ред. код]

  1. The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition: pthread_rwlock_destroy. The IEEE and The Open Group. Процитовано 14 May 2011. 
  2. Shared locking in C++
  3. Anthony Williams. Synchronization – Boost 1.52.0. Процитовано 31 Jan 2012. 
  4. ReaderWriteLockSlim Class (System.Threading). Microsoft Corporation. Процитовано 14 May 2011. 
  5. Шаблон:Javadoc:SE
  6. Шаблон:Javadoc:SE