Рекурсивная блокировка (мьютекс) против нерекурсивной блокировки (мьютекс)

187

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

Другие API (API более высокого уровня) также обычно предлагают мьютексы, часто называемые блокировками. Некоторые системы / языки (например, Cocoa Objective-C) предлагают как рекурсивные, так и нерекурсивные мьютексы. Некоторые языки также предлагают только один или другой. Например, в Java мьютексы всегда рекурсивны (один и тот же поток может дважды «синхронизироваться» с одним и тем же объектом). В зависимости от того, какие другие функциональные возможности потоков они предлагают, отсутствие рекурсивных мьютексов может быть проблемой, поскольку их можно легко написать самостоятельно (я сам уже реализовал рекурсивные мьютексы на основе более простых операций мьютексов / условий).

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

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

Mecki
источник

Ответы:

156

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

Однако здесь есть и другие соображения.

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

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

Если вы обратитесь к классическому ядру VxWorks RTOS, они определяют три механизма:

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

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

Высокий Джефф
источник
12
Ваше объяснение нерекурсивного мьютекса больше походило на семафор. Мьютекс (рекурсивный или нерекурсивный) имеет понятие владения.
Jay D
@JayD Это очень сбивает с толку, когда люди спорят о подобных вещах ... так кто же определяет эти вещи?
Pacerier
14
@Pacerier Соответствующий стандарт. Этот ответ, например, неверен для posix (pthreads), где разблокировка нормального мьютекса в потоке, отличном от потока, который его заблокировал, является неопределенным поведением, а выполнение того же самого с проверкой ошибок или рекурсивным мьютексом приводит к предсказуемому коду ошибки. Другие системы и стандарты могут вести себя совсем иначе.
н.у.к.
Возможно, это наивно, но у меня сложилось впечатление, что основная идея мьютекса состоит в том, что блокирующий поток разблокирует мьютекс, а затем другие потоки могут делать то же самое. Из computing.llnl.gov/tutorials/pthreads :
user657862
2
@curiousguy - широковещательный выпуск освобождает все потоки, заблокированные на семафоре, без явного указания его (остается пустым), тогда как нормальный двоичный запрос освобождает только поток в начале очереди ожидания (при условии, что один заблокирован).
Высокий Джефф
125

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

Пример: A :: foo () получает блокировку. Затем он вызывает B :: bar (). Это нормально работало, когда вы это писали. Но через некоторое время кто-то изменяет B :: bar () на вызов A :: baz (), который также получает блокировку.

Что ж, если у вас нет рекурсивных мьютексов, это взаимоблокируется. Если они у вас есть, он работает, но может сломаться. A :: foo () мог оставить объект в несогласованном состоянии перед вызовом bar (), исходя из предположения, что baz () не может быть запущен, потому что он также получает мьютекс. Но, наверное, не должно работать! Человек, написавший A :: foo (), предположил, что никто не может вызвать A :: baz () одновременно - это и есть причина того, что оба этих метода получили блокировку.

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

Если вас устраивают повторные блокировки, то это только потому, что вам не приходилось отлаживать подобную проблему раньше. Между прочим, в Java сейчас есть нереентерабельные блокировки в java.util.concurrent.locks.

Джонатан
источник
4
Мне потребовалось время, чтобы понять, что вы говорили о недействительности инварианта, когда вы захватываете блокировку во второй раз. Хорошая точка зрения! Что, если бы это была блокировка чтения-записи (например, ReadWriteLock в Java), и вы получили блокировку чтения, а затем повторно получили блокировку чтения во второй раз в том же потоке. Вы же не стали бы недействительным инвариант после получения блокировки чтения, верно? Таким образом, когда вы получаете вторую блокировку чтения, инвариант остается верным.
dgrant 09
1
@Jonathan Есть ли в Java в наши дни нереентерабельные блокировки в java.util.concurrent.locks ??
user454322
1
+1 Я полагаю, что наиболее распространенное использование реентерабельной блокировки - внутри одного класса, где некоторые методы могут быть вызваны как из защищенных, так и из незащищенных частей кода. На самом деле это всегда можно исключить. @ user454322 Конечно, Semaphore.
maaartinus
1
Простите за недоразумение, но я не понимаю, какое отношение это имеет к мьютексам. Предположим, что не задействованы многопоточность и блокировка, A::foo()возможно, объект все еще оставался в несогласованном состоянии перед вызовом A::bar(). Какое отношение имеет мьютекс, рекурсивный или нет, к этому случаю?
Сиюань Рен
1
@SiyuanRen: Проблема в том, чтобы локально рассуждать о коде. Люди (по крайней мере, я) обучены распознавать заблокированные области как поддержание инварианта, то есть в то время, когда вы получаете блокировку, никакой другой поток не изменяет состояние, поэтому инварианты в критической области сохраняются. Это не жесткое правило, и вы можете кодировать, не учитывая инвариантов, но это только усложнит обоснование и поддержку вашего кода. То же самое происходит в однопоточном режиме без мьютексов, но там мы не обучены рассуждать локально вокруг защищенной области.
Дэвид Родригес - дрибес
94

Как написал сам Дэйв Бутенхоф :

«Самая большая из всех больших проблем с рекурсивными мьютексами заключается в том, что они побуждают вас полностью потерять контроль над схемой блокировки и областью действия. Это смертельно. Зло. Это« пожиратель потоков ». Вы удерживаете блокировки в течение максимально короткого времени. Период. Всегда. Если вы вызываете что-то с заблокированной блокировкой просто потому, что не знаете, что она удерживается, или потому что вы не знаете, нужен ли вызываемый мьютекс, значит, вы удерживаете его слишком долго. нацелить дробовик на ваше приложение и нажать на курок. Предположительно, вы начали использовать потоки для обеспечения параллелизма, но вы просто ПРЕДОТВРАЩАЛИ параллелизм ».

Крис Клиланд
источник
9
Также обратите внимание на заключительную часть ответа ...you're not DONE until they're [recursive mutex] all gone.. Or sit back and let someone else do the design.
Бутенхофа
2
Он также говорит, что использование одного глобального рекурсивного мьютекса (по его мнению, вам нужен только один) - это нормально в качестве костыля для сознательного откладывания тяжелой работы по пониманию инвариантности внешней библиотеки, когда вы начинаете использовать ее в многопоточном коде. Но вы не должны использовать костыли навсегда, а в конечном итоге потратите время на понимание и исправление инвариантов параллелизма кода. Итак, мы могли бы перефразировать, что использование рекурсивного мьютекса - это технический долг.
FooF
13

Правильная ментальная модель использования мьютексов: мьютекс защищает инвариант.

Почему вы уверены, что это действительно правильная ментальная модель использования мьютексов? Я думаю, что правильная модель защищает данные, а не инварианты.

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

Более того, если вам нужно защитить инварианты, вы все равно можете использовать двоичный семафор, который никогда не является рекурсивным.


источник
Правда. Есть более эффективные механизмы защиты инварианта.
ActiveTrayPrntrTagDataStrDrvr
8
Это должен быть комментарий к ответу, в котором содержалось это утверждение. Мьютексы не только защищают данные, они также защищают инварианты. Попробуйте написать какой-нибудь простой контейнер (самый простой из них - стек) в терминах атомики (где данные защищают себя) вместо мьютексов, и вы поймете утверждение.
Дэвид Родригес - dribeas
Мьютексы не защищают данные, они защищают инвариант. Однако этот инвариант можно использовать для защиты данных.
Джон Ханна
5

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

avis
источник
5

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

Если методы используют другие методы (например: addNewArray () вызывает addNewPoint () и завершает с помощью recheckBounds ()), но любая из этих функций сама по себе должна блокировать мьютекс, тогда рекурсивный мьютекс является беспроигрышным.

В любом другом случае (решать просто плохую кодировку, использовать ее даже в разных объектах) явно неправильно!

DarkZeros
источник
Не могу не согласиться. Здесь есть только плохие варианты: 1. Не используйте никаких блокировок из функций-членов - вместо этого имейте блокировку вызывающего кода до того, как он вызовет любую функцию (подход «не моя проблема»). 2. Придумайте программную логику «тот же поток уже заблокирован» для каждого класса, который необходимо заблокировать. Еще больше кода, который сложно понять (расы), сопровождающие все еще должны знать, как это делать правильно. 3. Дизайн с учетом неизменности (ваш список из 10 000 000 элементов при изменении возвращает новый список) (нельзя использовать стандартные типы по соображениям эффективности). 4. Клиент ненавидит ваше постоянно зависшее приложение.
BitTickler,
1

Для чего нужны нерекурсивные мьютексы?

Они абсолютно хороши, когда вам нужно убедиться, что мьютекс разблокирован, прежде чем что-то делать. Это потому, что pthread_mutex_unlockможет гарантировать, что мьютекс разблокирован, только если он не рекурсивен.

pthread_mutex_t      g_mutex;

void foo()
{
    pthread_mutex_lock(&g_mutex);
    // Do something.
    pthread_mutex_unlock(&g_mutex);

    bar();
}

Если g_mutexнерекурсивный, приведенный выше код гарантированно будет вызывать bar()с разблокированным мьютексом. .

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

Если бы он g_mutexбыл рекурсивным, просто не было бы возможности убедиться, что он разблокирован, прежде чем делать вызов.

Игорь Г
источник
Это не совсем здоровый подход. Пример: class foo { ensureContains(item); hasItem(item); addItem(); }если ensureContains()используется hasItem()и addItem(), ваша разблокировка перед вызовом кого-то еще может предотвратить автоматическую взаимоблокировку, но также не позволяет ее правильному выполнению при наличии нескольких потоков. Как будто вы вообще не блокировали.
BitTickler,
@BitTickler, конечно! Несомненно, существуют сценарии, в которых мьютекс должен оставаться заблокированным при вызове какого-либо другого метода, и ваш пример является одним из них. Однако, если по какой-либо причине мьютекс должен быть разблокирован перед вызовом, то единственный выход - нерекурсивные мьютексы. Что, собственно, и было основной идеей этого ответа.
Игорь Г
1

ИМХО, большинство аргументов против рекурсивных блокировок (которые я использую 99,9% времени, например, за 20 лет параллельного программирования) смешивают вопрос о том, хороши они или плохи, с другими проблемами проектирования программного обеспечения, которые совершенно не связаны. Назовем одну из них, проблему «обратного вызова», которая исчерпывающе разработана без какой-либо точки зрения, связанной с многопоточностью, например, в книге « Программное обеспечение компонентов - за пределами объектно-ориентированного программирования». .

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

class EvilFoo {
  std::vector<std::string> data;
  std::vector<std::function<void(EvilFoo&)> > changedEventHandlers;
public:
  size_t registerChangedHandler( std::function<void(EvilFoo&)> handler) { // ...  
  }
  void unregisterChangedHandler(size_t handlerId) { // ...
  }
  void fireChangedEvent() { 
    // bad bad, even evil idea!
    for( auto& handler : changedEventHandlers ) {
      handler(*this);
    }
  }
  void AddItem(const std::string& item) { 
    data.push_back(item);
    fireChangedEvent();
  }
};

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

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

Таким образом, злой стороной EvilFooявляются события и то, как они реализованы, а не рекурсивная блокировка. fireChangedEvent()сначала нужно будет создать копию changedEventHandlersи использовать ее для итерации.

Еще один часто обсуждаемый аспект - это определение того, что блокировка должна делать в первую очередь:

  • Защитите фрагмент кода от повторного входа
  • Защитите ресурс от одновременного использования (несколькими потоками).

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

void EvilFoo::bar() {
   auto_lock lock(this); // this->lock_holder = this->lock_if_not_already_locked_by_same_thread())
   // do what we gotta do
   
   // ~auto_lock() { if (lock_holder) unlock() }
}

И как только в игру войдут события или подобные конструкции (посетители ?!), я не надеюсь, что все последующие проблемы дизайна будут решены какой-нибудь нерекурсивной блокировкой.

BitTickler
источник