stringtranslate.com

Лок (информатика)

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

Типы

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

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

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

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

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

Причина, по которой требуется атомарная операция , заключается в параллелизме, когда несколько задач выполняют одну и ту же логику. Например, рассмотрим следующий код 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] , где блокировка строк данных на длительные периоды времени невозможна. Кроме того, для поддержания блокировки записей требуется постоянное соединение с сервером базы данных, что невозможно в отключенных приложениях.

Таблица совместимости замков

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

Комментарий: В некоторых публикациях записи в таблице просто помечены «совместимо» или «несовместимо» или соответственно «да» или «нет». [5]

Недостатки

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

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

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

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

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

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

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

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

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

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

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

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

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

Мьютексы против семафоров

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

  1. Инверсия приоритета : если мьютекс знает, кто его заблокировал, и должен его разблокировать, можно повысить приоритет этой задачи всякий раз, когда задача с более высоким приоритетом начинает ожидать мьютекса.
  2. Преждевременное завершение задачи. Мьютексы также могут обеспечивать безопасность удаления, когда задача, содержащая мьютекс, не может быть случайно удалена. [ нужна цитата ]
  3. Взаимная блокировка завершения: если задача, удерживающая мьютекс, завершается по какой-либо причине, ОС может освободить мьютекс и сигнализировать об ожидающих задачах этого условия.
  4. Тупик рекурсии: задаче разрешено блокировать повторно входящий мьютекс несколько раз, поскольку она разблокирует его равное количество раз.
  5. Случайное освобождение: при освобождении мьютекса возникает ошибка, если задача освобождения не является его владельцем.

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

Рекомендации

  1. ^ «Оператор блокировки (ссылка на C#)» .
  2. ^ «ThreadPoolPriority и MethodImplAttribute». MSDN. п. ?? . Проверено 22 ноября 2011 г.
  3. ^ «C# с точки зрения разработчика Java». Архивировано из оригинала 02 января 2013 г. Проверено 22 ноября 2011 г.
  4. ^ «Проектирование компонентов уровня данных и передача данных через уровни» . Майкрософт . Август 2002 г. Архивировано из оригинала 8 мая 2008 г. Проверено 30 мая 2008 г.
  5. ^ «Протокол управления параллелизмом на основе блокировок в СУБД» . Гики для Гиков . 07.03.2018 . Проверено 28 декабря 2023 г.
  6. ^ Пейтон Джонс, Саймон (2007). «Красивый параллелизм» (PDF) . В Уилсоне, Грег; Орам, Энди (ред.). Красивый код: ведущие программисты объясняют, как они думают . О'Рейли.
  7. ^ ИСО/МЭК 8652:2007. «Охраняемые объекты и охраняемые объекты». Справочное руководство по Аде 2005 . Проверено 27 февраля 2010 г. Защищенный объект обеспечивает скоординированный доступ к общим данным посредством вызовов его видимых защищенных операций, которыми могут быть защищенные подпрограммы или защищенные записи.{{cite book}}: CS1 maint: числовые имена: список авторов ( ссылка )
  8. ^ ИСО/МЭК 8652:2007. «Пример постановки задач и синхронизации». Справочное руководство по Аде 2005 . Проверено 27 февраля 2010 г.{{cite book}}: CS1 maint: числовые имена: список авторов ( ссылка )
  9. ^ Маршалл, Дэйв (март 1999 г.). «Блокировки взаимного исключения» . Проверено 30 мая 2008 г.
  10. ^ «Синхронизировать». msdn.microsoft.com . Проверено 30 мая 2008 г.
  11. ^ «Синхронизация». Сан Микросистемс . Проверено 30 мая 2008 г.
  12. ^ «Справочник по многопоточности Apple» . Apple, Inc. Проверено 17 октября 2009 г.
  13. ^ "Справочник по NSLock". Apple, Inc. Проверено 17 октября 2009 г.
  14. ^ "Справочник по NSRecursiveLock" . Apple, Inc. Проверено 17 октября 2009 г.
  15. ^ "Справочник по NSConditionLock" . Apple, Inc. Проверено 17 октября 2009 г.
  16. ^ «Справочник по протоколу NSLocking». Apple, Inc. Проверено 17 октября 2009 г.
  17. ^ "стадо".
  18. ^ «Класс Mutex». Архивировано из оригинала 4 июля 2017 г. Проверено 29 декабря 2016 г.
  19. ^ Лунд, Фредрик (июль 2007 г.). «Механизмы синхронизации потоков в Python». Архивировано из оригинала 01.11.2020 . Проверено 30 мая 2008 г.
  20. ^ Джон Рид (2010). «Coarrays в следующем стандарте Фортрана» (PDF) . Проверено 17 февраля 2020 г.
  21. ^ «Программирование Ruby: потоки и процессы» . 2001 . Проверено 30 мая 2008 г.
  22. ^ «std::sync::Mutex — Rust». doc.rust-lang.org . Проверено 3 ноября 2020 г. .
  23. ^ «Параллелизм с общим состоянием — язык программирования Rust» . doc.rust-lang.org . Проверено 3 ноября 2020 г. .
  24. ^ Марлоу, Саймон (август 2013 г.). «Базовый параллелизм: потоки и MVar». Параллельное и параллельное программирование на Haskell. О'Рейли Медиа . ISBN 9781449335946.
  25. ^ Марлоу, Саймон (август 2013 г.). «Программная транзакционная память». Параллельное и параллельное программирование на Haskell. О'Рейли Медиа . ISBN 9781449335946.
  26. ^ "Пакет синхронизации - синхронизация - pkg.go.dev" . pkg.go.dev . Проверено 23 ноября 2021 г.

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