Как объяснить “мертвую блокировку” лучше?

Цепочка блокировки возникает, когда работник заблокирован другим работником. A не может продолжаться из-за B. Цепочка может быть длиннее: A блокируется B, B блокируется C, C блокируется D.

Тупик - это когда цепочка замков образует петлю. A блокируется B, B C, C, A и цепь образовала петлю, прогресс невозможен.

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

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

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

Я изучил много концепций параллельного программирования, используя эти примеры, реализованные на Java.

  Thrd 1 --- Lock A        - atmpt lock on B -   
         \                /                   \
          \              /                     \           
           \            /                       \         
            --- Lock A /                         --- wait for lock on B

  Thrd 2--- Lock B         - atmpt lock on A -   
         \                /                   \
          \              /                     \           
           \            /                       \         
            --- Lock B /                         --- wait for lock on A

Поток 1 запускается, блокирует A, делает что-то, и прерывается потоком 2, который блокирует B, делает что-то и прерывается потоком 1, который пытается заблокировать B, но поток 2 заблокировал B, так что поток 1 ожидает и прерывается потоком 2, который пытается заблокировать A, но поток 1 имеет блокировку на A, поэтому поток 2 должен ждать.

Оба потока ждут, пока другой поток снимет блокировку с ресурса, на который они пытаются установить блокировку ...

Тупик

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

У меня есть пятилетний сын и трехлетняя дочь. Оба хотят сделать одну и ту же книжку-раскраску.

Дочь хватает карандаши, а сын - книгу. Ни один из них не откажется от того, что у них есть, пока не получит другого.

Это тупик. Это не становится проще, чем это.

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

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

Следование одному правилу гарантирует невозможность тупиковой ситуации:

• У всех потоков выполнения выделяются ресурсы в одном и том же порядке.

Следование некоторым дополнительным правилам сделает ваши потоки менее вероятными для замедления друг друга, но имейте в виду, что вышеприведенное правило должно иметь приоритет над всеми остальными:

• Распределять ресурсы только тогда, когда вы нужны они.
• Отпустите их, как только закончите с ними.

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

thread 1:
lock(a)
lock(b)

thread2:
lock(b)
lock(a)

Предположим, что поток 1 получает блокировку A и затем переходит в спящий режим. Поток 2 получает блокировку B, а затем пытается получить блокировку A; Так как блокировка A занята, поток 2 будет переведен в спящий режим, пока поток A не будет разблокирован. Теперь поток 1 возвращается в исходное состояние и пытается получить блокировку B и будет переведен в режим сна.

Для этого случая есть несколько способов предотвратить это:

1. Нить никогда не должна одновременно удерживать две блокировки.
2. Если две блокировки должны удерживаться одновременно, они всегда должны быть получены в одном и том же порядке (поэтому в моем примере выше необходимо изменить поток 2, чтобы запросить блокировку A перед запросом блокировки B).

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

Для взаимной блокировки требуется как минимум 2 блокировки, и оба потока должны содержать код, который принимает блокировки, а также ожидает снятия блокировок.

Поток 1 имеет блокировку A и хочет блокировку B, поэтому он ожидает снятия блокировки B.

Поток 2 имеет блокировку B и хочет блокировку A, поэтому он ожидает снятия блокировки A.

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

TakeLoce происходит, когда у вас есть 2 разных ресурса, которые 2 разных потока должны быть заблокированы для их использования. Темы блокируют их в противоположном порядке, поэтому становится невозможным для выполнения, чтобы продолжить до 1 из потоков.

У Википедии есть пара хороших реальных примеров тупика.

Описание Гуффы хорошее.

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

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

Эту статью хорошо прочитать об этой проблеме.

Философы столовой - у вас 4 человека сидят за столом, и 4 палочки для еды. Вам нужно 2 палочки для еды. Представьте, что каждый философ пытается есть следующим образом:

1. Возьмите левую палочку для еды.
2. Возьми правую палочку.
3. Ешь.
4. Верни правую палочку.
5. Установите левую палочку назад.

Все делают шаг 1. Теперь шаг 2 невозможен, так как каждый человек ждет, пока тот, кто справа, опустит левую палочку, чего он не сделает. Это тупик. Если бы они просто делали по очереди, то все могли бы поесть, а вместо этого все голодали.

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

Возможно, вас интересует HLVM , но на данный момент это не просто эксперимент.

(Слегка упрощено) Есть два человека, завинчивающих гайки на болты.

Процедура (одинаковая для обоих):

1. Поднимите гайку или болт
2. Поднимите болт или гайку (в зависимости от того, что у вас еще нет)
3. Вверните гайку на болт
4. Поместите готовую сборку в «готовую» кучу.
5. если гайки и болты остаются, переходите к шагу 1

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

Без специальных инструкций они будут сидеть там в тупике вечно.

Или вы можете просто показать им это видео

Еще один хороший способ продемонстрировать взаимоблокировку - это SQL Server.

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

Плюсом здесь является то, что вы можете продемонстрировать это с помощью SQL Management Studio. Я использовал это в прошлом, чтобы объяснить людям взаимоблокировки во время обучения на уровне «Введение в SQL Server».

Большинство участников имеют проблемы с теорией, но все (обычно) становится ясно, когда они видят это в действии.

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

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

(Слегка упрощено) Два человека навинчивают гайки на болты.

Процедура (одинаковая для обоих):

1. Поднимите гайку или болт
2. Поднимите болт или гайку (в зависимости от того, что у вас еще нет)
3. Навинтите гайку на болт
4. Поместите готовую сборку в стопку «Готово».
5. если гайка и болт остались, переходите к шагу 1.

Что же произойдет, если останутся только гайка и болт? Первый поднимает гайку, второй - болт. Пока все хорошо, но теперь они застряли, у каждого есть ресурсы, которые нужны другому.

Без особых указаний они будут сидеть в тупике вечно.

Или вы можете просто показать им это видео