Блокировка (информатика) - Lock (computer science)

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

Типы

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

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

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

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

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

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

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

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

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

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

общественный учебный класс Счет // Это монитор аккаунта{    частный десятичный _баланс = 0;    частный объект _balanceLock = новый объект();    общественный пустота Депозит(десятичный количество)    {        // Только один поток одновременно может выполнять этот оператор.        замок (_balanceLock)        {            _баланс += количество;        }    }    общественный пустота Снять со счета(десятичный количество)    {        // Только один поток одновременно может выполнять этот оператор.        замок (_balanceLock)        {            _баланс -= количество;        }    }}

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

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

[MethodImpl (MethodImplOptions.Synchronized)]общественный пустота SomeMethod(){    // делаем что-нибудь}

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

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

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

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

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

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

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

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

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

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

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

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

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

Недостатки

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

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

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

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

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

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

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

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

функция перевод (от: Аккаунт, на: Аккаунт, сумма: целое число) из. вывести (сумма) на. депозит (сумма)

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

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

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

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

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

• Ада предоставляет защищенные объекты, которые имеют видимые защищенные подпрограммы или записи^[6] а также рандеву.^[7]
• ISO / IEC C стандарт обеспечивает стандарт взаимное исключение (замки) API поскольку C11. Действующий ISO / IEC C ++ стандартные опоры средства нарезки поскольку C ++ 11. В OpenMP standard поддерживается некоторыми компиляторами и позволяет указывать критические разделы с помощью прагм. В POSIX pthread API обеспечивает поддержку блокировки.^[8] Visual C ++ предоставляет синхронизировать атрибут методов, которые необходимо синхронизировать, но он специфичен для COM-объектов в Windows архитектура и Visual C ++ компилятор.^[9] C и C ++ могут легко получить доступ к любым встроенным функциям блокировки операционной системы.
• C # предоставляет замок ключевое слово в потоке, чтобы гарантировать его монопольный доступ к ресурсу.
• VB.NET обеспечивает SyncLock ключевое слово вроде C # замок ключевое слово.
• Ява предоставляет ключевое слово синхронизированный для блокировки кодовых блоков, методы или же объекты^[10] и библиотеки с безопасными для параллелизма структурами данных.
• Цель-C предоставляет ключевое слово @synchronized^[11] для блокировки блоков кода, а также предоставляет классы NSLock,^[12] NSRecursiveLock,^[13] и NSConditionLock^[14] вместе с протоколом NSLocking^[15] также для запирания.
• PHP обеспечивает блокировку на основе файлов ^[16] также как и Мьютекс класс в pthreads расширение. ^[17]
• Python обеспечивает низкий уровень мьютекс механизм с Замок класс из заправка модуль.^[18]
• ISO / IEC Фортран стандарт (ISO / IEC 1539-1: 2010) обеспечивает lock_type производный тип во встроенном модуле iso_fortran_env и замок/разблокировать заявления с Фортран 2008.^[19]
• Рубин обеспечивает низкий уровень мьютекс объект и без ключевого слова.^[20]
• Ржавчина предоставляет Мьютекс ^[21] структура.^[22]
• сборка x86 предоставляет ЗАМОК префикс для определенных операций, чтобы гарантировать их атомарность.

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

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

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

внешняя ссылка

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