В информатике блокировка или мьютекс (от взаимного исключения ) — это примитив синхронизации , который предотвращает изменение состояния или доступ к нему несколькими потоками выполнения одновременно. Блокировки реализуют политики управления параллелизмом взаимного исключения , и благодаря множеству возможных методов существует множество уникальных реализаций для разных приложений.
Как правило, блокировки представляют собой рекомендательные блокировки , при которых каждый поток взаимодействует, получая блокировку перед доступом к соответствующим данным. Некоторые системы также реализуют обязательные блокировки , при которых попытка несанкционированного доступа к заблокированному ресурсу приводит к исключению объекта, пытающегося осуществить доступ.
Самый простой тип блокировки — двоичный семафор . Он обеспечивает эксклюзивный доступ к заблокированным данным. Другие схемы также предоставляют общий доступ для чтения данных. Другими широко реализованными режимами доступа являются эксклюзивный режим, режим с намерением исключить и режим с намерением обновить.
Другой способ классификации блокировок — это то, что происходит, когда стратегия блокировки препятствует выполнению потока. Большинство конструкций блокировки блокируют выполнение потока , запрашивающего блокировку, до тех пор, пока ему не будет разрешен доступ к заблокированному ресурсу . При использовании спин-блокировки поток просто ждет («вращается»), пока блокировка не станет доступной. Это эффективно, если потоки блокируются на короткое время, поскольку позволяет избежать накладных расходов на перепланирование процессов операционной системы. Это неэффективно, если блокировка удерживается в течение длительного времени или если ход потока, удерживающего блокировку, зависит от вытеснения заблокированного потока.
Для эффективной реализации блокировкам обычно требуется аппаратная поддержка. Эта поддержка обычно принимает форму одной или нескольких атомарных инструкций, таких как « тестирование и установка », « выборка и добавление » или « сравнение и замена ». Эти инструкции позволяют одному процессу проверить, свободна ли блокировка, и, если она свободна, получить блокировку за одну атомарную операцию.
В однопроцессорных архитектурах есть возможность использовать непрерываемые последовательности инструкций — используя специальные инструкции или префиксы инструкций для временного отключения прерываний — но этот метод не работает для многопроцессорных машин с общей памятью. Правильная поддержка блокировок в многопроцессорной среде может потребовать довольно сложной аппаратной или программной поддержки, сопровождающейся существенными проблемами синхронизации .
Причина, по которой требуется атомарная операция, заключается в параллелизме, когда несколько задач выполняют одну и ту же логику. Например, рассмотрим следующий код C :
if ( lock == 0 ) { // блокировка свободна, устанавливаем lock = myPID ; }
Приведенный выше пример не гарантирует, что задача имеет блокировку, поскольку одновременно несколько задач могут проверять блокировку. Поскольку обе задачи обнаружат, что блокировка свободна, обе задачи попытаются установить блокировку, не зная, что другая задача также устанавливает блокировку. Алгоритм Деккера или Петерсона является возможной заменой, если операции атомарной блокировки недоступны.
Неосторожное использование блокировок может привести к взаимоблокировке или активной блокировке . Чтобы избежать или устранить взаимоблокировки или активные блокировки, можно использовать ряд стратегий как во время разработки, так и во время выполнения . (Наиболее распространенной стратегией является стандартизация последовательности получения блокировок, чтобы комбинации взаимозависимых блокировок всегда приобретались в специально определенном «каскадном» порядке.)
Некоторые языки поддерживают синтаксические блокировки. Ниже приведен пример на C# :
public class Account // Это монитор учетной записи { private decimal _balance = 0 ; частный объект _balanceLock = новый объект (); public void Deposit ( decimal sum ) { // Только один поток одновременно может выполнять этот оператор. блокировка ( _balanceLock ) { _balance += сумма ; } } public void Withdraw ( decimal sum ) { // Только один поток одновременно может выполнять этот оператор. блокировка ( _balanceLock ) { _balance -= сумма ; } } }
Код lock(this)
может привести к проблемам, если к экземпляру можно получить публичный доступ. [1]
Подобно Java , C# также может синхронизировать целые методы, используя атрибут MethodImplOptions.Synchronized. [2] [3]
[MethodImpl(MethodImplOptions.Synchronized)] public void SomeMethod () { // делаем что-то }
Прежде чем познакомиться с детализацией блокировок, необходимо понять три концепции блокировок:
При выборе количества синхронизируемых блокировок существует компромисс между уменьшением накладных расходов на блокировку и уменьшением количества конфликтов за блокировки.
Важным свойством блокировки является ее степень детализации . Детализация — это мера объема данных, которые защищает замок. В целом, выбор грубой детализации (небольшое количество блокировок, каждая из которых защищает большой сегмент данных) приводит к уменьшению накладных расходов на блокировку , когда один процесс обращается к защищенным данным, но к снижению производительности, когда несколько процессов выполняются одновременно. Это происходит из-за увеличения конфликтов блокировок . Чем грубее блокировка, тем выше вероятность того, что блокировка остановит выполнение несвязанного процесса. И наоборот, использование более высокой детализации (большое количество блокировок, каждая из которых защищает довольно небольшой объем данных) увеличивает накладные расходы на сами блокировки, но уменьшает конфликт блокировок. Детализированная блокировка, при которой каждый процесс должен удерживать несколько блокировок из общего набора блокировок, может создавать тонкие зависимости блокировок. Эта тонкость может увеличить вероятность того, что программист по незнанию создаст тупик . [ нужна цитата ]
Например, в системе управления базами данных блокировка может защищать в порядке убывания детализации часть поля, поле, запись, страницу данных или всю таблицу. Грубая степень детализации, например использование блокировок таблиц, обычно обеспечивает наилучшую производительность для одного пользователя, тогда как мелкая степень детализации, например блокировка записей, обычно обеспечивает наилучшую производительность для нескольких пользователей.
Блокировки базы данных можно использовать как средство обеспечения синхронности транзакций. т.е. при одновременной обработке транзакций (чередующихся транзакций) использование двухфазных блокировок гарантирует, что одновременное выполнение транзакции окажется эквивалентным некоторому последовательному упорядочиванию транзакции. Однако взаимоблокировки становятся досадным побочным эффектом блокировки баз данных. Взаимные блокировки либо предотвращаются путем предварительного определения порядка блокировки между транзакциями, либо обнаруживаются с помощью графиков ожидания . Альтернативой блокировке синхронности базы данных, позволяющей избежать взаимоблокировок, является использование полностью упорядоченных глобальных меток времени.
Существуют механизмы, используемые для управления действиями нескольких одновременных пользователей в базе данных — цель состоит в том, чтобы предотвратить потерю обновлений и некорректное чтение. Два типа блокировки — пессимистическая блокировка и оптимистическая блокировка :
Существует несколько вариаций и усовершенствований этих основных типов блокировок с соответствующими вариациями поведения блокировки. Если первая блокировка блокирует другую блокировку, две блокировки называются несовместимыми ; в противном случае замки совместимы . Часто типы блокировок, блокирующие взаимодействие, представлены в технической литературе Таблицей совместимости блокировок . Ниже приведен пример распространенных основных типов блокировок:
Комментарий: В некоторых публикациях записи в таблице просто помечены «совместимо» или «несовместимо» или соответственно «да» или «нет». [5]
Защита ресурсов на основе блокировок и синхронизация потоков/процессов имеют множество недостатков:
Некоторые стратегии управления параллелизмом позволяют избежать некоторых или всех этих проблем. Например, воронка или сериализация токенов позволяют избежать самой большой проблемы: взаимоблокировок. Альтернативы блокировке включают неблокирующие методы синхронизации, такие как методы программирования без блокировки и транзакционную память . Однако такие альтернативные методы часто требуют, чтобы фактические механизмы блокировки были реализованы на более фундаментальном уровне операционной системы. Таким образом, они могут лишь освободить уровень приложения от деталей реализации блокировок, при этом перечисленные выше проблемы все равно придется решать в рамках приложения.
В большинстве случаев правильная блокировка зависит от того, обеспечивает ли ЦП метод атомарной синхронизации потока команд (например, добавление или удаление элемента в конвейер требует, чтобы все одновременные операции, требующие добавления или удаления других элементов в конвейере, были приостановлены во время манипуляция содержимым памяти, необходимая для добавления или удаления определенного элемента). Таким образом, приложение часто может быть более надежным, если оно осознает нагрузку, которую оно накладывает на операционную систему, и способно любезно распознавать сообщения о невыполнимых требованиях. [ нужна цитата ]
Одна из самых больших проблем программирования на основе блокировок заключается в том, что «блокировки не компонуются »: трудно объединить небольшие, правильные модули на основе блокировок в одинаково правильные более крупные программы, не модифицируя модули или, по крайней мере, не зная их внутреннего устройства. Саймон Пейтон Джонс (сторонник программной транзакционной памяти ) приводит следующий пример банковского приложения: [6] спроектируйте класс Account , который позволяет нескольким одновременным клиентам вносить или снимать деньги на счет; и дать алгоритм перевода денег с одного счета на другой. Решение первой части проблемы на основе блокировки:
Учетная запись класса : баланс участника : Целочисленный мьютекс члена : Блокировка метод депозита (n: целое число) мьютекс.блокировка() баланс ← баланс + n мьютекс.разблокировка() метод вывода (n: целое число) депозит(-n)
Вторая часть проблемы гораздо сложнее. Процедура передачи , правильная для последовательных программ, будет такой:
передача функции (от: Счет, на: Счет, сумма: Целое число) from.withdraw(сумма) to.deposit(сумма)
В параллельной программе этот алгоритм неверен, поскольку, когда один поток находится на полпути перевода , другой может наблюдать состояние, когда сумма была снята с первого счета, но еще не переведена на другой счет: деньги пропали из системы. Эту проблему можно полностью решить, только заблокировав обе учетные записи перед изменением любой из двух учетных записей, но тогда блокировки должны быть установлены в соответствии с каким-то произвольным глобальным порядком, чтобы предотвратить взаимоблокировку:
функция Transfer(from: Account, to: Account, sum: Integer) if from < to // произвольный порядок на замках из.блокировка() закрывать() еще закрывать() из.блокировка() from.withdraw(сумма) to.deposit(сумма) из.unlock() отпереть()
Это решение усложняется, когда задействовано больше блокировок, и передаточной функции необходимо знать обо всех блокировках, чтобы их нельзя было скрыть .
Языки программирования различаются по поддержке синхронизации:
synchronize
lock
ключевое слово в потоке, чтобы гарантировать его монопольный доступ к ресурсу.SyncLock
ключевое слово, подобное ключевому слову C# lock
.synchronized
для блокировки блоков кода, методов или объектов [11] и библиотек с безопасными для параллелизма структурами данных.@synchronized
[12] для блокировки блоков кода, а также классы NSLock, [13] NSRecursiveLock, [14] и NSConditionLock [15], а также протокол NSLocking [16] для блокировки.Mutex
класс в pthreads
расширении. [18]Lock
классом из threading
модуля. [19]lock_type
производный тип во встроенном модуле iso_fortran_env
и операторах lock
/ unlock
, начиная с Fortran 2008 . [20]Mutex<T>
[22] . [23]LOCK
префикс для определенных операций, чтобы гарантировать их атомарность.MVar
, которая может быть либо пустой, либо содержать значение, обычно ссылку на ресурс. Поток, который хочет использовать ресурс, «принимает» значение MVar
, оставляя его пустым, и возвращает его после завершения. Попытка взять ресурс из пустого MVar
приводит к блокировке потока до тех пор, пока ресурс не станет доступен. [24] В качестве альтернативы блокировке также существует реализация программной транзакционной памяти . [25]Мьютекс — это механизм блокировки , который иногда использует ту же базовую реализацию, что и двоичный семафор. Однако они различаются по способу использования. Хотя двоичный семафор в просторечии можно назвать мьютексом, настоящий мьютекс имеет более конкретный вариант использования и определение: только задача, которая заблокировала мьютекс, должна его разблокировать. Это ограничение направлено на решение некоторых потенциальных проблем использования семафоров:
Защищенный объект обеспечивает скоординированный доступ к общим данным посредством вызовов его видимых защищенных операций, которыми могут быть защищенные подпрограммы или защищенные записи.
{{cite book}}
: CS1 maint: числовые имена: список авторов ( ссылка ){{cite book}}
: CS1 maint: числовые имена: список авторов ( ссылка )