Блокировка (информатика)

В информатике , замок или мьютекс (от взаимного исключения ) является примитив синхронизации : механизм , который накладывает ограничения на доступ к ресурсу , когда существует множество потоков выполнения . Блокировка предназначена для обеспечения соблюдения политики управления параллелизмом взаимного исключения , и с помощью множества возможных методов существует множество уникальных реализаций для разных приложений.

Типы

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

Самый простой тип блокировки - это двоичный семафор . Он обеспечивает эксклюзивный доступ к заблокированным данным. Другие схемы также предоставляют общий доступ для чтения данных. Другие широко применяемые режимы доступа - эксклюзивный, с намерением исключить и с намерением обновить.

Другой способ классификации блокировок - это то, что происходит, когда стратегия блокировки предотвращает продвижение потока. Большинство конструкций замка блокируют на выполнение в потоке запрашивающего блокировки , пока не будет разрешен доступ к заблокированному ресурсу. При спин-блокировке поток просто ждет («вращается»), пока блокировка не станет доступной. Это эффективно, если потоки блокируются на короткое время, поскольку позволяет избежать накладных расходов на перепланирование процессов операционной системы. Это неэффективно, если блокировка удерживается в течение длительного времени или если выполнение потока, удерживающего блокировку, зависит от вытеснения заблокированного потока.

Блокировки обычно требуют аппаратной поддержки для эффективной реализации. Эта поддержка обычно принимает форму одной или нескольких атомарных инструкций, таких как « test-and-set », « fetch-and-add » или « compare-and-swap ». Эти инструкции позволяют одному процессу проверить, свободна ли блокировка, и, если она свободна, получить блокировку за одну атомарную операцию.

В однопроцессорных архитектурах есть возможность использовать непрерывные последовательности инструкций - с использованием специальных инструкций или префиксов инструкций для временного отключения прерываний - но этот метод не работает для многопроцессорных машин с общей памятью. Правильная поддержка блокировок в многопроцессорной среде может потребовать довольно сложной аппаратной или программной поддержки со значительными проблемами синхронизации .

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

if  ( lock  ==  0 )  {  // блокировка свободна, установите ее  lock  =  myPID ; }

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

Неосторожное использование блокировок может привести к тупиковой или временной блокировке . Чтобы избежать взаимоблокировок или живых блокировок или выйти из них, можно использовать ряд стратегий как во время разработки, так и во время выполнения . (Наиболее распространенная стратегия - стандартизировать последовательности получения блокировок, чтобы комбинации взаимозависимых блокировок всегда регистрировались в специально определенном «каскадном» порядке.)

Некоторые языки поддерживают синтаксические блокировки. Пример на C # следующий:

public  class  Account  // Это монитор аккаунта {  private  decimal  _balance  =  0 ;  закрытый  объект  _balanceLock  =  новый  объект (); public  void  Deposit ( decimal  amount )  {  // Только один поток одновременно может выполнять этот оператор.  блокировка  ( _balanceLock )  {  _balance  + =  сумма ;  }  } public  void  Withdraw ( десятичная  сумма )  {  // Только один поток одновременно может выполнять этот оператор.  lock  ( _balanceLock )  {  _balance  - =  сумма ;  }  } }

Код lock(this)может привести к проблемам, если к экземпляру можно будет получить доступ публично. ^[1]

Подобно Java , C # также может синхронизировать целые методы с помощью атрибута MethodImplOptions.Synchronized. ^{[2] [3]}

[MethodImpl (MethodImplOptions.Synchronized)] public  void  SomeMethod () {  // что-то делать }

Гранулярность

Прежде чем познакомиться с гранулярностью блокировок, необходимо понять три концепции блокировок:

• накладные расходы на блокировку : дополнительные ресурсы для использования блокировок, такие как пространство памяти, выделенное для блокировок, время ЦП для инициализации и уничтожения блокировок и время для получения или снятия блокировок. Чем больше блокировок использует программа, тем больше накладных расходов, связанных с использованием;
• конфликт блокировки : это происходит всякий раз, когда один процесс или поток пытается получить блокировку, удерживаемую другим процессом или потоком. Чем более детализированы доступные блокировки, тем менее вероятно, что один процесс / поток запросит блокировку, удерживаемую другим. (Например, блокировка строки, а не всей таблицы, или блокировка ячейки, а не всей строки.);
• взаимоблокировка : ситуация, когда каждая из как минимум двух задач ожидает блокировки, удерживаемой другой задачей. Если что-то не будет сделано, две задачи будут ждать вечно.

При выборе количества блокировок для синхронизации существует компромисс между уменьшением накладных расходов на блокировку и уменьшением числа конфликтов блокировок.

Важным свойством замка является его гранулярность . Детализация - это мера объема данных, которые защищает блокировка. В общем, выбор грубой степени детализации (небольшое количество блокировок, каждая из которых защищает большой сегмент данных) приводит к меньшим накладным расходам на блокировку, когда один процесс обращается к защищенным данным, но к снижению производительности, когда несколько процессов работают одновременно. Это связано с увеличением числа конфликтов блокировок.. Чем грубее блокировка, тем выше вероятность того, что блокировка остановит выполнение несвязанного процесса. И наоборот, использование тонкой гранулярности (большее количество блокировок, каждая из которых защищает довольно небольшой объем данных) увеличивает накладные расходы самих блокировок, но снижает конкуренцию блокировок. Детализированная блокировка, когда каждый процесс должен удерживать несколько блокировок из общего набора блокировок, может создавать тонкие зависимости блокировок. Эта тонкость может увеличить вероятность того, что программист неосознанно зайдет в тупик . ^{[ необходима цитата ]}

В системе управления базой данных , например, блокировка может защищать в порядке уменьшения гранулярности часть поля, поле, запись, страницу данных или всю таблицу. Грубая детализация, такая как использование блокировок таблиц, обычно дает лучшую производительность для одного пользователя, тогда как мелкая детализация, такая как блокировки записей, имеет тенденцию обеспечивать лучшую производительность для нескольких пользователей.

Блокировки базы данных

Блокировки базы данных могут использоваться как средство обеспечения синхронности транзакций. т.е. при одновременной обработке транзакций (чередование транзакций) использование двухэтапных блокировок гарантирует, что параллельное выполнение транзакции оказывается эквивалентным некоторому последовательному упорядочиванию транзакции. Однако взаимоблокировки становятся нежелательным побочным эффектом блокировки в базах данных. Взаимоблокировки либо предотвращаются путем предварительного определения порядка блокировки между транзакциями, либо обнаруживаются с помощью графиков ожидания . Альтернатива блокировке для синхронности базы данных, позволяющая избежать взаимоблокировок, включает использование полностью упорядоченных глобальных меток времени.

Существуют механизмы, используемые для управления действиями нескольких одновременных пользователей в базе данных - цель состоит в том, чтобы предотвратить потерю обновлений и грязное чтение. Два типа блокировки - это пессимистическая блокировка и оптимистическая блокировка :

• Пессимистическая блокировка : пользователь, который читает запись с намерением обновить ее, устанавливает исключительную блокировку на запись, чтобы другие пользователи не могли ею манипулировать. Это означает, что никто другой не может управлять этой записью, пока пользователь не снимет блокировку. Обратной стороной является то, что пользователи могут быть заблокированы на очень долгое время, тем самым замедляя общую реакцию системы и вызывая разочарование.

Где использовать пессимистичную блокировку: это в основном используется в средах, где существует высокая конкуренция за данные (степень запросов пользователей к системе базы данных в любой момент времени); где стоимость защиты данных с помощью блокировок меньше, чем стоимость отката транзакций, если возникают конфликты параллелизма. Пессимистический параллелизм лучше всего реализовать, когда время блокировки будет коротким, как при программной обработке записей. Пессимистичный параллелизм требует постоянного подключения к базе данных и не является масштабируемым вариантом, когда пользователи взаимодействуют с данными, поскольку записи могут быть заблокированы на относительно большие периоды времени. Он не подходит для использования при разработке веб-приложений.

• Оптимистическая блокировка: это позволяет нескольким одновременным пользователям получить доступ к базе данных, в то время как система хранит копию начального чтения, сделанного каждым пользователем. Когда пользователь хочет обновить запись, приложение определяет, изменил ли другой пользователь запись с момента ее последнего чтения. Приложение делает это, сравнивая начальное чтение, хранящееся в памяти, с записью базы данных, чтобы проверить любые изменения, внесенные в запись. Любые расхождения между начальным чтением и записью в базе данных нарушают правила параллелизма и, следовательно, заставляют систему игнорировать любой запрос на обновление. Появляется сообщение об ошибке, и пользователя просят снова запустить процесс обновления. Это улучшает производительность базы данных за счет уменьшения количества требуемых блокировок, тем самым уменьшая нагрузку на сервер базы данных.Он эффективно работает с таблицами, требующими ограниченного обновления, поскольку ни один из пользователей не заблокирован. Однако некоторые обновления могут не работать. Обратной стороной являются постоянные сбои обновления из-за большого количества запросов на обновление от нескольких одновременно работающих пользователей - это может расстраивать пользователей.

Где использовать оптимистичную блокировку: это уместно в средах, где низкая конкуренция за данные или где требуется доступ только для чтения к данным. Оптимистический параллелизм широко используется в .NET для удовлетворения потребностей мобильных и отключенных приложений ^[4], где блокировка строк данных на длительные периоды времени была бы невозможна. Кроме того, для поддержания блокировок записей требуется постоянное соединение с сервером базы данных, что невозможно в отключенных приложениях.

Недостатки

Защита ресурсов на основе блокировок и синхронизация потоков / процессов имеют много недостатков:

• Разногласия: некоторые потоки / процессы должны ждать, пока не будет снята блокировка (или весь набор блокировок). Если один из потоков, удерживающих блокировку, умирает, останавливается, блокируется или входит в бесконечный цикл, другие потоки, ожидающие блокировки, могут ждать бесконечно.
• Накладные расходы: использование блокировок увеличивает накладные расходы для каждого доступа к ресурсу, даже если вероятность коллизии очень редка. (Однако любая вероятность таких столкновений - это состояние гонки .)
• Отладка: ошибки, связанные с блокировками, зависят от времени, могут быть очень незаметными и чрезвычайно сложными для репликации, например, взаимоблокировки .
• Нестабильность: оптимальный баланс между накладными расходами на блокировку и конкуренцией блокировок может быть уникальным для проблемной области (приложения) и зависеть от проектирования, реализации и даже низкоуровневых изменений архитектуры системы. Эти балансы могут изменяться в течение жизненного цикла приложения и могут повлечь за собой огромные изменения для обновления (повторного баланса).
• Возможность компоновки: блокировки могут быть составлены только (например, управление несколькими параллельными блокировками для атомарного удаления элемента X из таблицы A и вставки X в таблицу B) при относительно сложной (накладной) программной поддержке и безупречном соблюдении программных приложений со строгими соглашениями.
• Инверсия приоритета : поток / процесс с низким приоритетом, удерживающий общую блокировку, может препятствовать выполнению потоков / процессов с высоким приоритетом. Наследование приоритета может использоваться для уменьшения продолжительности инверсии приоритета. Протокол верхнего предела приоритета может использоваться в однопроцессорных системах для минимизации продолжительности инверсии приоритета в наихудшем случае, а также для предотвращения тупиковых ситуаций .
• Конвоирование : все другие потоки должны ждать, если поток, удерживающий блокировку, отменен из-за прерывания временного интервала или ошибки страницы.

Некоторые стратегии управления параллелизмом позволяют избежать некоторых или всех этих проблем. Например, с помощью воронки или сериализации токенов можно избежать самой большой проблемы: тупиковых ситуаций. Альтернативы блокировке включают неблокирующие методы синхронизации , такие как методы программирования без блокировки и транзакционная память . Однако такие альтернативные методы часто требуют, чтобы фактические механизмы блокировки были реализованы на более фундаментальном уровне операционного программного обеспечения. Следовательно, они могут только освободить уровень приложения от деталей реализации блокировок, при этом проблемы, перечисленные выше, по-прежнему необходимо решать в рамках приложения.

В большинстве случаев правильная блокировка зависит от ЦП, обеспечивающего метод синхронизации потока атомарных инструкций (например, добавление или удаление элемента в конвейер требует, чтобы все одновременные операции, требующие добавления или удаления других элементов в конвейере, были приостановлены во время манипулирование содержимым памяти, необходимое для добавления или удаления конкретного элемента). Следовательно, приложение часто может быть более надежным, если оно распознает бремя, которое оно возлагает на операционную систему, и способно любезно распознавать сообщения о невыполнимых требованиях. ^{[ необходима цитата ]}

Отсутствие возможности компоновки

Одна из самых больших проблем программирования на основе блокировок заключается в том, что «блокировки не составляют »: трудно объединить небольшие правильные модули на основе блокировок в одинаково правильные более крупные программы, не изменяя модули или, по крайней мере, не зная об их внутреннем устройстве. Саймон Пейтон Джонс (сторонник программной транзакционной памяти ) приводит следующий пример банковского приложения: ^[5] разработать класс Account, который позволяет нескольким одновременным клиентам вносить или снимать деньги на счет; и дать алгоритм перевода денег с одного счета на другой. Основанное на блокировке решение первой части проблемы:

класс Учетная запись: баланс участника : Целочисленный член мьютекса: Блокировка метод deposit (n: целое число) mutex.lock () баланс ← баланс + n mutex.unlock () метод вывода (n: целое число) депозит (−n)

Вторая часть проблемы намного сложнее. Процедура передачи , правильная для последовательных программ , будет

передача функции (от: Аккаунт, в: Аккаунт, сумма: целое число) from.withdraw (сумма) to.deposit (сумма)

В параллельной программе этот алгоритм неверен, потому что, когда один поток находится на полпути к передаче , другой может наблюдать состояние, когда сумма была снята с первого счета, но еще не переведена на другой счет: деньги пропали из системы. Эта проблема может быть решена полностью только путем блокировки обеих учетных записей перед изменением любой из двух учетных записей, но тогда блокировки должны быть приняты в соответствии с некоторым произвольным глобальным порядком, чтобы предотвратить взаимоблокировку:

передача функции (от: Account, to: Account, amount: integer) if from <to // произвольный порядок блокировок from.lock () запереть() еще запереть() from.lock () from.withdraw (сумма) to.deposit (сумма) from.unlock () отпирать()

Это решение усложняется, когда задействовано больше блокировок, и передаточная функция должна знать обо всех блокировках, чтобы их нельзя было скрыть .

Языковая поддержка

Языки программирования различаются по поддержке синхронизации:

• Ada предоставляет защищенные объекты, которые имеют видимые защищенные подпрограммы или записи ^[6], а также рандеву. ^[7]
• Стандарт ISO / IEC C предоставляет стандартный API взаимного исключения (блокировки), начиная с C11 . Текущий стандарт ISO / IEC C ++ поддерживает функции потоковой передачи, начиная с C ++ 11 . Стандарт OpenMP поддерживается некоторыми компиляторами и позволяет указывать критические разделы с помощью прагм. Потоковой POSIX API обеспечивает поддержку блокировки. ^[8] Visual C ++ предоставляет атрибут методов для синхронизации, но он специфичен для COM-объектов в архитектуре Windows и компилятора Visual C ++ . ^[9] synchronize C и C ++ могут легко получить доступ к любым встроенным функциям блокировки операционной системы.
• C # предоставляет lockключевое слово в потоке, чтобы гарантировать его монопольный доступ к ресурсу.
• VB.NET предоставляет такое SyncLockключевое слово, как ключевое слово C # lock.
• Java предоставляет ключевое слово synchronizedдля блокировки блоков кода, методов или объектов ^[10] и библиотек, содержащих структуры данных, безопасные для параллелизма.
• Objective-C предоставляет ключевое слово @synchronized^[11] для блокировки блоков кода, а также предоставляет классы NSLock, ^[12] NSRecursiveLock, ^[13] и NSConditionLock ^[14] вместе с протоколом NSLocking ^[15] для блокировки.
• PHP предоставляет блокировку на основе файлов ^[16], а также Mutexкласс в pthreadsрасширении. ^[17]
• Python предоставляет низкоуровневый механизм мьютекса с Lockклассом из threadingмодуля. ^[18]
• Стандарт ISO / IEC Fortran (ISO / IEC 1539-1: 2010) предоставляет lock_typeпроизводный тип во встроенном модуле iso_fortran_envи операторах lock/, unlockначиная с Fortran 2008 . ^[19]
• Ruby предоставляет объект мьютекса низкого уровня без ключевого слова. ^[20]
• Rust предоставляет структуру Mutex<T>^[21] . ^[22]
• Сборка x86 предоставляет LOCKпрефикс для определенных операций, чтобы гарантировать их атомарность.
• Haskell реализует блокировку с помощью изменяемой структуры данных, называемой an MVar, которая может быть пустой или содержать значение, обычно ссылку на ресурс. Поток, который хочет использовать ресурс, «берет» значение MVar, оставляя его пустым, и возвращает его по завершении. Попытка взять ресурс из пустого MVarприводит к блокировке потока до тех пор, пока ресурс не станет доступным. ^[23] В качестве альтернативы блокировке также существует реализация программной транзакционной памяти . ^[24]

Смотрите также

• Критический раздел
• Двойная проверка блокировки
• Блокировка файлов
• Алгоритмы блокировки и ожидания
• Монитор (синхронизация)
• Взаимное исключение
• Шаблон блокировки чтения / записи
• Семафор (программирование)

использованная литература

внешние ссылки

• Учебник по блокировкам и критическим разделам