Лок (информатика)
В информатике блокировка , или мьютекс (от взаимного исключения ) — это примитив синхронизации который предотвращает изменение состояния или доступ к нему несколькими потоками выполнения одновременно. Блокировки реализуют политики управления параллелизмом взаимного исключения , и благодаря множеству возможных методов существует множество уникальных реализаций для разных приложений.
Типы [ править ]
Как правило, блокировки представляют собой рекомендательные блокировки , при которых каждый поток взаимодействует, получая блокировку перед доступом к соответствующим данным. Некоторые системы также реализуют обязательные блокировки , при которых попытка несанкционированного доступа к заблокированному ресурсу приводит к исключению объекта, пытающегося осуществить доступ.
Самый простой тип блокировки — двоичный семафор . Он обеспечивает эксклюзивный доступ к заблокированным данным. Другие схемы также предоставляют общий доступ для чтения данных. Другими широко реализованными режимами доступа являются эксклюзивный режим, режим с намерением исключить и режим с намерением обновить.
Другой способ классификации блокировок — это то, что происходит, когда стратегия блокировки препятствует выполнению потока. Большинство конструкций блокировки блокируют выполнение , потока . запрашивающего блокировку, до тех пор, пока ему не будет разрешен доступ к заблокированному ресурсу При использовании спин-блокировки поток просто ждет («вращается»), пока блокировка не станет доступной. Это эффективно, если потоки блокируются на короткое время, поскольку позволяет избежать накладных расходов на перепланирование процессов операционной системы. Это неэффективно, если блокировка удерживается в течение длительного времени или если ход потока, удерживающего блокировку, зависит от вытеснения заблокированного потока.
Для эффективной реализации блокировкам обычно требуется аппаратная поддержка. Эта поддержка обычно принимает форму одной или нескольких атомарных инструкций, таких как « тестирование и установка », « выборка и добавление » или « сравнение и замена ». Эти инструкции позволяют одному процессу проверить, свободна ли блокировка, и, если она свободна, получить блокировку за одну атомарную операцию.
В однопроцессорных архитектурах есть возможность использовать непрерываемые последовательности инструкций — используя специальные инструкции или префиксы инструкций для временного отключения прерываний — но этот метод не работает для многопроцессорных машин с общей памятью. Правильная поддержка блокировок в многопроцессорной среде может потребовать довольно сложной аппаратной или программной поддержки, сопровождающейся существенными проблемами синхронизации .
Причина, по которой требуется атомарная операция, заключается в параллелизме, когда несколько задач выполняют одну и ту же логику. Например, рассмотрим следующий код 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 ()
{
// делаем что-то
}
Детализация [ править ]
Прежде чем познакомиться с детализацией блокировок, необходимо понять три концепции блокировок:
- накладные расходы на блокировку : дополнительные ресурсы для использования блокировок, такие как пространство памяти, выделенное для блокировок, время ЦП для инициализации и уничтожения блокировок, а также время для получения или снятия блокировок. Чем больше блокировок использует программа, тем больше накладных расходов связано с их использованием;
- блокировок конфликт : это происходит всякий раз, когда один процесс или поток пытается получить блокировку, удерживаемую другим процессом или потоком. Чем более детальны доступные блокировки, тем меньше вероятность того, что один процесс/поток запросит блокировку, удерживаемую другим. (Например, блокировка строки, а не всей таблицы, или блокировка ячейки, а не всей строки);
- взаимоблокировка : ситуация, когда каждая из как минимум двух задач ожидает блокировки, удерживаемой другой задачей. Если что-то не будет сделано, эти две задачи будут ждать вечно.
При выборе количества синхронизируемых блокировок существует компромисс между уменьшением накладных расходов на блокировку и уменьшением количества конфликтов за блокировки.
Важным свойством блокировки является ее степень детализации . Детализация — это мера объема данных, которые защищает замок. В целом, выбор грубой детализации (небольшое количество блокировок, каждая из которых защищает большой сегмент данных) приводит к уменьшению накладных расходов на блокировку , когда один процесс обращается к защищенным данным, но к снижению производительности, когда несколько процессов выполняются одновременно. Это происходит из-за увеличения конфликтов блокировок . Чем грубее блокировка, тем выше вероятность того, что блокировка остановит выполнение несвязанного процесса. И наоборот, использование более высокой детализации (большое количество блокировок, каждая из которых защищает довольно небольшой объем данных) увеличивает накладные расходы на сами блокировки, но уменьшает конфликт блокировок. Детализированная блокировка, при которой каждый процесс должен удерживать несколько блокировок из общего набора блокировок, может создавать тонкие зависимости блокировок. Эта тонкость может увеличить вероятность того, что программист по незнанию создаст тупик . [ нужна цитата ]
Например, в системе управления базами данных блокировка может защищать в порядке убывания детализации часть поля, поле, запись, страницу данных или всю таблицу. Грубая степень детализации, например использование блокировок таблиц, обычно обеспечивает наилучшую производительность для одного пользователя, тогда как мелкая степень детализации, например блокировка записей, обычно обеспечивает наилучшую производительность для нескольких пользователей.
Блокировки базы данных [ править ]
Блокировки базы данных могут использоваться как средство обеспечения синхронности транзакций. т.е. при одновременной обработке транзакций (чередующихся транзакций) использование двухфазных блокировок гарантирует, что одновременное выполнение транзакции окажется эквивалентным некоторому последовательному упорядочиванию транзакции. Однако взаимоблокировки становятся досадным побочным эффектом блокировки баз данных. Взаимные блокировки либо предотвращаются путем предварительного определения порядка блокировки между транзакциями, либо обнаруживаются с помощью графиков ожидания . Альтернативой блокировке синхронности базы данных, позволяющей избежать взаимоблокировок, является использование полностью упорядоченных глобальных меток времени.
Существуют механизмы, используемые для управления действиями нескольких одновременных пользователей в базе данных — цель состоит в том, чтобы предотвратить потерю обновлений и некорректное чтение. Два типа блокировки — пессимистическая блокировка и оптимистическая блокировка :
- Пессимистическая блокировка : пользователь, который читает запись с намерением обновить ее, устанавливает исключительную блокировку записи, чтобы другие пользователи не могли манипулировать ею. Это означает, что никто другой не сможет манипулировать этой записью, пока пользователь не снимет блокировку. Обратной стороной является то, что пользователи могут быть заблокированы на очень долгое время, что замедляет общую реакцию системы и вызывает разочарование.
- Где использовать пессимистическую блокировку: она в основном используется в средах, где конфликты за данные (степень запросов пользователей к системе базы данных в любой момент времени) являются тяжелыми; где стоимость защиты данных с помощью блокировок меньше, чем стоимость отката транзакций в случае возникновения конфликтов параллелизма. Пессимистический параллелизм лучше всего реализовать, когда время блокировки будет коротким, как при программной обработке записей. Пессимистический параллелизм требует постоянного подключения к базе данных и не является масштабируемым вариантом, когда пользователи взаимодействуют с данными, поскольку записи могут быть заблокированы на относительно большие периоды времени. Он не подходит для использования при разработке веб-приложений.
- Оптимистическая блокировка : позволяет нескольким пользователям одновременно получать доступ к базе данных, в то время как система сохраняет копию первоначального чтения, сделанную каждым пользователем. Когда пользователь хочет обновить запись, приложение определяет, изменил ли другой пользователь запись с момента ее последнего чтения. Приложение делает это путем сравнения первоначального чтения, хранящегося в памяти, с записью базы данных, чтобы проверить любые изменения, внесенные в запись. Любые несоответствия между первоначальной записью чтения и записью базы данных нарушают правила параллелизма и, следовательно, заставляют систему игнорировать любой запрос на обновление. Выдается сообщение об ошибке, и пользователю предлагается снова запустить процесс обновления. Это повышает производительность базы данных за счет уменьшения количества необходимых блокировок, тем самым снижая нагрузку на сервер базы данных. Он эффективно работает с таблицами, которые требуют ограниченного обновления, поскольку ни один пользователь не заблокирован. Однако некоторые обновления могут не работать. Обратной стороной являются постоянные сбои при обновлении из-за большого количества запросов на обновление от нескольких одновременных пользователей. Это может расстраивать пользователей.
- Где использовать оптимистическую блокировку: это подходит в средах, где существует низкая конкуренция за данные или где требуется доступ к данным только для чтения. Оптимистический параллелизм широко используется в .NET для удовлетворения потребностей мобильных и автономных приложений. [4] где блокировка строк данных на длительный период времени была бы невозможна. Кроме того, для поддержания блокировки записей требуется постоянное соединение с сервером базы данных, что невозможно в отключенных приложениях.
Таблица совместимости блокировок [ править ]
Существует несколько вариаций и усовершенствований этих основных типов блокировок с соответствующими вариациями поведения блокировки. Если первая блокировка блокирует другую блокировку, две блокировки называются несовместимыми ; в противном случае замки совместимы . Часто типы блокировок, блокирующие взаимодействие, представлены в технической литературе Таблицей совместимости блокировок . Ниже приведен пример распространенных основных типов блокировок:
| Тип замка | блокировка чтения | блокировка записи |
|---|---|---|
| блокировка чтения | ✔ | Икс |
| блокировка записи | Икс | Икс |
- ✔ указывает на совместимость
- X указывает на несовместимость, т. е. случай, когда блокировка первого типа (в левом столбце) на объекте блокирует возможность получения блокировки второго типа (в верхнем ряду) на том же объекте (другой транзакцией). Объект обычно имеет очередь ожидания запрошенных (транзакциями) операций с соответствующими блокировками. Первая заблокированная блокировка операции в очереди получается, как только существующая блокирующая блокировка снимается с объекта, после чего выполняется соответствующая операция. Если блокировка операции в очереди не заблокирована какой-либо существующей блокировкой (одновременное существование нескольких совместимых блокировок на одном и том же объекте), она устанавливается немедленно.
Комментарий: В некоторых публикациях записи в таблице просто помечены «совместимо» или «несовместимо» или соответственно «да» или «нет». [5]
Недостатки [ править ]
Защита ресурсов на основе блокировок и синхронизация потоков/процессов имеют множество недостатков:
- Конфликт: некоторым потокам/процессам приходится ждать, пока не будет снята блокировка (или целый набор блокировок). Если один из потоков, удерживающих блокировку, умирает, останавливается, блокируется или входит в бесконечный цикл, другие потоки, ожидающие блокировки, могут ждать бесконечно, пока компьютер не выключится и не выключится .
- Накладные расходы: использование блокировок увеличивает накладные расходы при каждом доступе к ресурсу, даже если вероятность коллизии очень редка. (Однако любая вероятность таких столкновений является состоянием гонки .)
- Отладка: ошибки, связанные с блокировками, зависят от времени и могут быть очень незаметными, и их чрезвычайно трудно воспроизвести, например, взаимоблокировки .
- Нестабильность: оптимальный баланс между накладными расходами на блокировку и конфликтом блокировок может быть уникальным для проблемной области (приложения) и зависеть от проектирования, реализации и даже изменений в архитектуре системы низкого уровня. Эти балансы могут меняться в течение жизненного цикла приложения и могут повлечь за собой огромные изменения при обновлении (перебалансировке).
- Компонуемость: блокировки могут быть компонуемыми (например, управление несколькими одновременными блокировками для атомарного удаления элемента X из таблицы A и вставки X в таблицу B) только при относительно сложной (накладной) программной поддержке и идеальном соблюдении строгих соглашений при программировании приложений.
- Инверсия приоритетов : поток/процесс с низким приоритетом, удерживающий общую блокировку, может помешать продолжению потоков/процессов с высоким приоритетом. Наследование приоритетов можно использовать для сокращения продолжительности инверсии приоритетов. Протокол потолка приоритета можно использовать в однопроцессорных системах для минимизации продолжительности инверсии приоритета в наихудшем случае, а также для предотвращения взаимоблокировок .
- Конвоирование : все остальные потоки должны ждать, если поток, удерживающий блокировку, выключается из-за прерывания временного интервала или ошибки страницы.
Некоторые стратегии управления параллелизмом позволяют избежать некоторых или всех этих проблем. Например, воронка или сериализация токенов позволяют избежать самой большой проблемы: взаимоблокировок. Альтернативы блокировке включают неблокирующие методы синхронизации, такие как без блокировки методы программирования и транзакционная память . Однако такие альтернативные методы часто требуют, чтобы фактические механизмы блокировки были реализованы на более фундаментальном уровне операционного программного обеспечения. Таким образом, они могут лишь избавить уровень приложения от деталей реализации блокировок, при этом перечисленные выше проблемы все равно придется решать в рамках приложения.
В большинстве случаев правильная блокировка зависит от того, обеспечивает ли ЦП метод атомарной синхронизации потока команд (например, добавление или удаление элемента в конвейер требует, чтобы все одновременные операции, требующие добавления или удаления других элементов в конвейере, были приостановлены во время манипуляция содержимым памяти, необходимая для добавления или удаления определенного элемента). Таким образом, приложение часто может быть более надежным, если оно осознает нагрузку, которую оно накладывает на операционную систему, и способно любезно распознавать сообщения о невыполнимых требованиях. [ нужна цитата ]
Отсутствие компоновки [ править ]
Одна из самых больших проблем программирования на основе блокировок заключается в том, что «блокировки не компонуются »: трудно объединить небольшие, правильные модули на основе блокировок в одинаково правильные более крупные программы, не модифицируя модули или, по крайней мере, не зная их внутреннего устройства. Саймон Пейтон Джонс (сторонник программной транзакционной памяти ) приводит следующий пример банковского приложения: [6] спроектировать класс Учетная запись , которая позволяет нескольким одновременным клиентам вносить или снимать деньги на счет; и дать алгоритм перевода денег с одного счета на другой. Решение первой части проблемы на основе блокировки:
Класс Аккаунт:
баланс участника : целое число
мьютекс участника : блокировка
метод депозита (n: целое число)
мьютекс.блокировка()
баланс ← баланс + n
мьютекс.разблокировка()
метод вывода (n: целое число)
депозит(-n)
Вторая часть проблемы гораздо сложнее. А процедура передачи , правильная для последовательных программ, будет
передача функции (от: Счет, на: Счет, сумма: Целое число)
from.withdraw(сумма)
to.deposit(сумма)
В параллельной программе этот алгоритм неверен, поскольку, когда один поток завершает работу на полпути, передачи , другой может наблюдать состояние, в котором сумма снята с первого счета, но еще не зачислена на другой счет: деньги пропали из системы. Эту проблему можно полностью решить, только заблокировав обе учетные записи перед изменением любой из двух учетных записей, но тогда блокировки должны быть установлены в соответствии с каким-то произвольным глобальным порядком, чтобы предотвратить взаимоблокировку:
передача функции (от: Счет, на: Счет, сумма: Целое число)
if from < to // произвольный порядок на замках
из.lock()
закрывать()
еще
закрывать()
из.блокировка()
from.withdraw(сумма)
to.deposit(сумма)
из.unlock()
отпереть()
Это решение усложняется, когда задействовано больше блокировок, и Передаточная функция должна знать обо всех блокировках, чтобы их нельзя было скрыть .
Языковая поддержка [ править ]
Языки программирования различаются по поддержке синхронизации:
- Ада предоставляет защищенные объекты, которые имеют видимые защищенные подпрограммы или записи. [7] а также свидание. [8]
- Стандарт ISO/IEC C предоставляет стандартный взаимного исключения (блокировок), API начиная с C11 . Текущий стандарт ISO/IEC C++ поддерживает средства многопоточности, начиная с C++11 . Стандарт OpenMP поддерживается некоторыми компиляторами и позволяет указывать критические разделы с помощью прагм. API POSIX pthread обеспечивает поддержку блокировок. [9] Visual C++ предоставляет
synchronizeатрибут методов, подлежащих синхронизации, но это характерно для COM-объектов в архитектуре Windows и компилятора Visual C++ . [10] C и C++ могут легко получить доступ к любым собственным функциям блокировки операционной системы. - C# предоставляет
lockключевое слово в потоке, чтобы гарантировать его монопольный доступ к ресурсу. - VB.NET предоставляет
SyncLockключевое слово, такое как C#lockключевое слово. - Java предоставляет ключевое слово
synchronizedдля блокировки блоков кода, методов или объектов [11] и библиотеки с параллельными структурами данных. - Objective-C предоставляет ключевое слово
@synchronized[12] для блокировки блоков кода, а также предоставляет классы NSLock, [13] НСрекурсивлокок, [14] и НСкондициониллокк [15] вместе с протоколом NSLocking [16] для блокировки тоже. - PHP обеспечивает блокировку на основе файлов [17] также как и
Mutexкласс вpthreadsрасширение. [18] - Python низкого уровня предоставляет механизм мьютекса с
Lockкласс изthreadingмодуль. [19] - Стандарт ISO/IEC Fortran (ISO/IEC 1539-1:2010) обеспечивает
lock_typeпроизводный тип во встроенном модулеiso_fortran_envиlock/unlockзаявления начиная с Fortran 2008 . [20] - Ruby низкого уровня предоставляет объект -мьютекс и не имеет ключевого слова. [21]
- Rust предоставляет
Mutex<T>[22] структура. [23] - Сборка x86 обеспечивает
LOCKпрефикс для определенных операций, чтобы гарантировать их атомарность. - Haskell реализует блокировку через изменяемую структуру данных, называемую
MVar, который может быть пустым или содержать значение, обычно ссылку на ресурс. Поток, желающий использовать ресурс, «принимает» значениеMVar, оставляя его пустым, и возвращает его по завершении. Попытка взять ресурс из пустогоMVarприводит к блокировке потока до тех пор, пока ресурс не станет доступен. [24] реализация программной транзакционной памяти . В качестве альтернативы блокировке также существует [25] - Go предоставляет низкоуровневый объект Mutex библиотеки в стандартном пакете синхронизации . [26] Его можно использовать для блокировки блоков кода, методов или объектов .
Мьютексы против семафоров [ править ]
Мьютекс , — это механизм блокировки который иногда использует ту же базовую реализацию, что и двоичный семафор. Однако они различаются по способу использования. Хотя двоичный семафор в просторечии можно назвать мьютексом, настоящий мьютекс имеет более конкретный вариант использования и определение: только задача, которая заблокировала мьютекс, должна его разблокировать. Это ограничение направлено на решение некоторых потенциальных проблем использования семафоров:
- Инверсия приоритета : если мьютекс знает, кто его заблокировал, и должен его разблокировать, можно повысить приоритет этой задачи всякий раз, когда задача с более высоким приоритетом начинает ожидать мьютекса.
- Преждевременное завершение задачи. Мьютексы также могут обеспечивать безопасность удаления, когда задача, содержащая мьютекс, не может быть случайно удалена. [ нужна цитата ]
- Взаимная блокировка завершения: если задача, удерживающая мьютекс, завершается по какой-либо причине, ОС может освободить мьютекс и сигнализировать об ожидающих задачах этого условия.
- Тупик рекурсии: задаче разрешено блокировать повторно входящий мьютекс несколько раз, поскольку она разблокирует его равное количество раз.
- Случайное освобождение: при освобождении мьютекса возникает ошибка, если задача освобождения не является его владельцем.
См. также [ править ]
- Критический раздел
- Двойная проверка блокировки
- Блокировка файлов
- Алгоритмы без блокировки и без ожидания
- Монитор (синхронизация)
- Взаимное исключение
- Чтение/запись шаблона блокировки
Ссылки [ править ]
- ^ «Оператор блокировки (Справочник по C#)» .
- ^ «ThreadPoolPriority и MethodImplAttribute» . MSDN. п. ?? . Проверено 22 ноября 2011 г.
- ^ «C# с точки зрения Java-разработчика» . Архивировано из оригинала 02 января 2013 г. Проверено 22 ноября 2011 г.
- ^ «Проектирование компонентов уровня данных и передача данных через уровни» . Майкрософт . Август 2002 г. Архивировано из оригинала 8 мая 2008 г. Проверено 30 мая 2008 г.
- ^ «Протокол управления параллелизмом на основе блокировок в СУБД» . Гики для Гиков . 07.03.2018 . Проверено 28 декабря 2023 г.
- ^ Пейтон Джонс, Саймон (2007). «Красивый параллелизм» (PDF) . В Уилсоне, Грег; Орам, Энди (ред.). Красивый код: ведущие программисты объясняют, как они думают . О'Рейли.
- ^ ИСО/МЭК 8652:2007. «Охраняемые объекты и охраняемые объекты» . Справочное руководство по Аде 2005 . Проверено 27 февраля 2010 г.
Защищенный объект обеспечивает скоординированный доступ к общим данным посредством вызовов его видимых защищенных операций, которыми могут быть защищенные подпрограммы или защищенные записи.
{{cite book}}: CS1 maint: числовые имена: список авторов ( ссылка ) - ^ ИСО/МЭК 8652:2007. «Пример постановки задач и синхронизации» . Справочное руководство по Аде 2005 . Проверено 27 февраля 2010 г.
{{cite book}}: CS1 maint: числовые имена: список авторов ( ссылка ) - ^ Маршалл, Дэйв (март 1999 г.). «Блокировки взаимного исключения» . Проверено 30 мая 2008 г.
- ^ «Синхронизировать» . msdn.microsoft.com . Проверено 30 мая 2008 г.
- ^ «Синхронизация» . Сан Микросистемс . Проверено 30 мая 2008 г.
- ^ «Справочник по многопоточности Apple» . Apple, Inc. Проверено 17 октября 2009 г.
- ^ «Справочник по NSLock» . Apple, Inc. Проверено 17 октября 2009 г.
- ^ «Справочник по NSRecursiveLock» . Apple, Inc. Проверено 17 октября 2009 г.
- ^ «Справочник по NSConditionLock» . Apple, Inc. Проверено 17 октября 2009 г.
- ^ «Справочник по протоколу NSLocking» . Apple, Inc. Проверено 17 октября 2009 г.
- ^ «стадо» .
- ^ «Класс Мьютекса» . Архивировано из оригинала 4 июля 2017 г. Проверено 29 декабря 2016 г.
- ^ Лунд, Фредрик (июль 2007 г.). «Механизмы синхронизации потоков в Python» . Архивировано из оригинала 01.11.2020 . Проверено 30 мая 2008 г.
- ^ Джон Рид (2010). «Coarrays в следующем стандарте Фортрана» (PDF) . Проверено 17 февраля 2020 г.
- ^ «Программирование Ruby: потоки и процессы» . 2001 . Проверено 30 мая 2008 г.
- ^ "std::sync::Mutex — Rust" . doc.rust-lang.org . Проверено 3 ноября 2020 г. .
- ^ «Параллелизм с общим состоянием — язык программирования Rust» . doc.rust-lang.org . Проверено 3 ноября 2020 г. .
- ^ Марлоу, Саймон (август 2013 г.). «Базовый параллелизм: потоки и MVar». Параллельное и параллельное программирование на Haskell . О'Рейли Медиа . ISBN 9781449335946 .
- ^ Марлоу, Саймон (август 2013 г.). «Программная транзакционная память». Параллельное и параллельное программирование на Haskell . О'Рейли Медиа . ISBN 9781449335946 .
- ^ «пакет синхронизации — синхронизация — pkg.go.dev» . pkg.go.dev . Проверено 23 ноября 2021 г.