Как лучше объяснить «тупик»?

Question

Я изо всех сил пытаюсь объяснить «тупик» в темах простыми словами, поэтому, пожалуйста, помогите. Что может быть лучшим примером «тупика» (скажем, в Java), и как это происходит поэтапно и как его предотвратить? Но не вдаваясь в детали слишком глубоко. Я знаю, это все равно что спрашивать о двух противоположных вещах, но все же. Если у вас есть опыт обучения параллельному программированию - это было бы великолепно!

Answer 1

Джек и Джилл хотят сделать бутерброд одновременно. Им обоим нужен кусок хлеба, поэтому они оба идут за хлебом и ножом.

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

Answer 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).

Answer 3

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

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

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

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

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

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

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

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

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

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

Answer 4

  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 должен ждать.

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

Тупик

Answer 5

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

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

Answer 6

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

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

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

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

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

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

Answer 7

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

Преступник никогда не освободит заложника, пока не получит деньги. Вы никогда не отпустите деньги, пока не получите заложника. Тупик.

---

Аналогия здесь:

• Вы и преступник являются потоков
• Чемодан , полный денег и заложник - это ресурсы

Answer 8

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

Answer 9

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

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

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

Эта статья хороша для прочтения этой проблемы.

Answer 10

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

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

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