Реентерабельный мьютекс

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

Хотя любая попытка выполнить операцию «блокировки» над обычным мьютексом (блокировкой) либо потерпит неудачу, либо заблокируется, когда мьютекс уже заблокирован, на рекурсивном мьютексе эта операция будет успешной тогда и только тогда, когда блокирующий поток является тем, который уже удерживается. замок. Обычно рекурсивный мьютекс отслеживает количество раз, когда он был заблокирован, и требует выполнения одинакового количества операций разблокировки, прежде чем другие потоки смогут его заблокировать.

Мотивация

Рекурсивные мьютексы решают проблему отсутствия повторного входа в обычные мьютексы: если функция, которая принимает блокировку и выполняет обратный вызов, сама вызывается обратным вызовом, возникает взаимоблокировка . ^[1] В псевдокоде это следующая ситуация:

var m : Mutex  // A non-recursive mutex, initially unlocked.

function lock_and_call(i : Integer)
    m.lock()
    callback(i)
    m.unlock()

function callback(i : Integer)
    if i > 0
        lock_and_call(i - 1)

lock_and_call(1)  // Invoking the function

Учитывая эти определения, вызов функции lock_and_call(1) вызовет следующую последовательность событий:

m.lock() — мьютекс заблокирован
обратный вызов(1)
lock_and_call(0) — потому что я > 0
m.lock() — тупик, потому что m уже заблокирован, поэтому исполняющий поток заблокируется, ожидая себя.

Замена мьютекса на рекурсивный решает проблему, потому что финальный m.lock() завершится успешно без блокировки.

Практическое использование

У. Ричард Стивенс отмечает, что рекурсивные блокировки «сложно» использовать правильно, и рекомендует их использовать для адаптации однопоточного кода без изменения API , но «только тогда, когда другое решение невозможно». ^[2]

Monitor Собственный механизм синхронизации языка Java, , использует рекурсивные блокировки. Синтаксически блокировка — это блок кода, перед которым стоит ключевое слово «synchronized», а также любая ссылка на объект в круглых скобках, которая будет использоваться в качестве мьютекса. Внутри синхронизированного блока данный объект можно использовать в качестве условной переменной, выполнив для него функции wait(), notify() или notifyAll(). Таким образом, все объекты являются как рекурсивными мьютексами, так и условными переменными . ^[3]

Пример

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

Программная эмуляция

Программная эмуляция может быть выполнена ^{[ нужны разъяснения ]} используя следующую структуру: ^{[ нужна ссылка ]}

«контроля» Условие с использованием обычного замка
Идентификатор владельца, уникальный для каждого потока (по умолчанию пустой/не установлен)
Количество приобретений (по умолчанию равно нулю)

Приобретение

Получите условие управления.
Если установлен владелец, а не текущий поток, дождитесь уведомления об условии управления (это также отменяет условие).
Установите владельца текущего потока. Идентификатор владельца на этом этапе уже должен быть очищен, если только покупатель еще не является владельцем.
Увеличьте количество приобретений (для новых владельцев всегда должно быть 1).
Отмените условие управления.

Выпускать

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

Ссылки

^ Бушманн, Франк; Хенни, Кевлин; Шмидт, Дуглас К. (2007). Архитектура программного обеспечения, ориентированная на шаблоны, язык шаблонов для распределенных вычислений . Джон Уайли и сыновья. п. 374. ИСБН 9780470065303 .
^ Стивенс, В. Ричард; Раго, Стивен А. (2013). Расширенное программирование в среде UNIX . Аддисон-Уэсли. п. 434.
^ Дэвид Ховмейер. «Лекция 17: Java-потоки, синхронизация» . CS 365 — Параллельные и распределенные вычисления . Проверено 4 июня 2015 г. {{cite book}}: |work= игнорируется ( помогите )

[1] Бушманн, Франк; Хенни, Кевлин; Шмидт, Дуглас К. (2007). Архитектура программного обеспечения, ориентированная на шаблоны, язык шаблонов для распределенных вычислений . Джон Уайли и сыновья. п. 374. ИСБН 9780470065303 .

[2] Стивенс, В. Ричард; Раго, Стивен А. (2013). Расширенное программирование в среде UNIX . Аддисон-Уэсли. п. 434.

[3] Дэвид Ховмейер. «Лекция 17: Java-потоки, синхронизация» . CS 365 — Параллельные и распределенные вычисления . Проверено 4 июня 2015 г. {{cite book}}: |work= игнорируется ( помогите )

[1]

[2]

[3]