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

Question

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

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

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

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

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

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