Что такое тупик?

159

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

Мои вопросы к сообществу:

  1. Что такое тупик?

  2. Как вы их обнаруживаете?

  3. Вы справляетесь с ними?

  4. И, наконец, как вы предотвращаете их появление?

bmurphy1976
источник

Ответы:

207

Блокировка происходит , когда несколько процессов пытаются получить доступ к одному ресурсу одновременно.

Один процесс проигрывает и должен ждать завершения другого.

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

Итак, пример:

Ресурс A и ресурс B используются процессом X и процессом Y

  • Х начинает использовать А.
  • X и Y пытаются начать использовать B
  • Y 'выигрывает' и получает B первым
  • теперь Y нужно использовать A
  • A заблокирован X, который ждет Y

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

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

Кит
источник
9
Я использую процесс здесь как обобщение, а не как процесс ОС. Это могут быть потоки, но также могут быть совершенно разные приложения или соединения с базой данных. Шаблон тот же.
Кит
1
Привет, учитывая этот сценарий: поток A блокирует ресурс A и имеет длительный процесс. Поток B ожидает блокировки ресурса A. Загрузка ЦП: 20%, можете ли вы считать это тупиковой ситуацией?
rickyProgrammer
2
@rickyProgrammer нет, это просто обычное ожидание блокировки, хотя разница немного академична. B, ожидающий на медленной A, является блокировкой, B, ожидающей A, ожидающей B, является тупиком.
Кит
Таким образом, взаимоблокировка - это больше двух процессов с заблокированными ресурсами, ожидающими освобождения этих ресурсов ...
rickyProgrammer
2
@rickyProgrammer - это блокировка, которая не станет свободной, независимо от того, как долго вы будете ждать из-за циклической очереди.
Кит
126

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

Криминальная и полицейская сцена

введите описание изображения здесь

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

Еще одно объяснение высокого уровня тупика: разбитые сердца

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

Левент Дивилиоглу
источник
Должны ли потоки принадлежать разным процессам? Могут ли потоки, принадлежащие одному и тому же процессу, вызвать взаимоблокировку?
lordvcs
1
@diabolicfreak Не имеет значения, принадлежат ли потоки одному и тому же процессу или нет.
Сэм Малаек
2
Другим примером из реальной жизни могут быть четыре автомобиля, идущие на пересечение двух равных дорог в четырех направлениях одновременно. Каждый должен проложить путь к машине с правой стороны, чтобы никто не мог продолжить.
LoBo
35

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

Способы избежать тупиков:

  • избегать замков (если это возможно),
  • избегать использования более одного замка
  • всегда берите замки в одном и том же порядке.
Матс Фредрикссон
источник
Третий пункт предотвращения тупика (всегда берите блокировки в одном и том же порядке) является жизненно важным, что довольно легко забыть в практике кодирования.
Цян Сюй
20

Чтобы определить тупик, сначала я бы определил процесс.

Процесс : Как мы знаем, процесс не что иное, как programвыполнение.

Ресурс : Для выполнения процесса программы необходимы некоторые ресурсы. Категории ресурсов могут включать память, принтеры, процессоры, открытые файлы, ленточные накопители, компакт-диски и т. Д.

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

Состояние или ситуация тупика

введите описание изображения здесь

На приведенной выше схеме есть два процесса P1 и p2 и два ресурса R1 и R2 .

Ресурс R1 выделяется для процесса P1, а ресурс R2 выделяется для процесса p2 . Для завершения выполнения процесса P1 необходим ресурс R2 , поэтому запрос P1 для R2 , но R2 уже выделен для P2 .

Точно так же процесс P2 для завершения своего выполнения требует R1 , но R1 уже выделен для P1 .

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

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

  1. Взаимное исключение - каждый ресурс либо в настоящее время выделен ровно одному процессу, либо он доступен. (Два процесса не могут одновременно управлять одним и тем же ресурсом или находиться в своем критическом разделе).
  2. Удерживать и ждать - процессы, в настоящее время хранящие ресурсы, могут запрашивать новые ресурсы.
  3. Нет вытеснения - если процесс удерживает ресурс, он не может быть удален другим процессом или ядром.
  4. Циклическое ожидание - каждый процесс ожидает получения ресурса, который удерживается другим процессом.

и все эти условия выполняются на диаграмме выше.

Варуна
источник
8

Тупик возникает, когда поток ожидает чего-то, что никогда не происходит.

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

Это также часто случается, когда вы сталкиваетесь с двумя потоками и двумя блокировками:

Thread 1               Thread 2

Lock1->Lock();         Lock2->Lock();
WaitForLock2();        WaitForLock1();   <-- Oops!

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

17 из 26
источник
Тупик возникает, когда поток ожидает чего-то, что не может произойти.
Маркиз Лорн
4

Вы можете взглянуть на эту замечательную статью в разделе Deadlock . Это в C #, но идея остается той же для другой платформы. Я цитирую здесь для удобства чтения

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

object locker1 = new object();
object locker2 = new object();

new Thread (() => {
                    lock (locker1)
                    {
                      Thread.Sleep (1000);
                      lock (locker2);      // Deadlock
                    }
                  }).Start();
lock (locker2)
{
  Thread.Sleep (1000);
  lock (locker1);                          // Deadlock
}
onmyway133
источник
4

Deadlock является распространенной проблемой в многопроцессорных / многопрограммных задачах в ОС. Скажем, есть два процесса P1, P2 и два глобально разделяемых ресурса R1, R2, и в критическом разделе должны быть доступны оба ресурса

Первоначально ОС назначает R1 для обработки P1 и R2 для обработки P2. Поскольку оба процесса работают одновременно, они могут начать выполнять свой код, но ПРОБЛЕМА возникает, когда процесс попадает в критическую секцию. Таким образом, процесс R1 будет ждать, пока процесс P2 освободит R2, и наоборот ... Таким образом, они будут ждать вечно (СОСТОЯНИЕ ОТКЛЮЧЕНИЯ).

Небольшая АНАЛОГИЯ ...

Твоя Мать (OS),
Ты (P1),
Твой брат (P2),
Apple (R1),
Нож (R2),
критическая секция (разрезание яблока ножом).

Твоя мать вначале дает тебе яблоко и нож твоему брату.
Оба счастливы и играют (исполняют свои коды).
Любой из вас хочет отрезать яблоко (критический раздел) в какой-то момент.
Вы не хотите давать яблоко своему брату.
Твой брат не хочет дать тебе нож.
Так что вы оба будете ждать очень долго очень долго :)

Рохит Сингх
источник
2

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

Иосиф Стуртевант
источник
2

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

Маркиз Лорн
источник
Я голосую за вас. Ваш ответ более краткий, чем приведенный выше, потому что они приводят к путанице в тупике, возникающем в процессе или потоке. Кто-то скажет процесс, кто-то скажет нить :)
hainguyen
1

Классическая и очень простая программа для понимания тупиковой ситуации: -

public class Lazy {

    private static boolean initialized = false;

    static {
        Thread t = new Thread(new Runnable() {
            public void run() {
                initialized = true;
            }
        });

        t.start();

        try {
            t.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        System.out.println(initialized);
    }
}

Когда основной поток вызывает Lazy.main, он проверяет, был ли инициализирован класс Lazy, и начинает инициализировать класс. Теперь основной поток устанавливает значение initialized в значение false, создает и запускает фоновый поток, метод запуска которого устанавливает значение initialized в значение true, и ожидает завершения фонового потока.

На этот раз класс в настоящее время инициализируется другим потоком. При этих обстоятельствах текущий поток, который является фоновым потоком, ожидает объекта Class до завершения инициализации. К сожалению, поток, который выполняет инициализацию, основной поток, ожидает завершения фонового потока. Поскольку два потока теперь ждут друг друга, программа ОТКЛЮЧЕНА.

Вивек Пратап Сингх
источник
0

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

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

Некоторые более формальные методы могут быть полезны, если вы серьезно относитесь к решению подобных проблем. Наиболее практичный метод, который мне известен, - это использование теоретического подхода к процессу. Здесь вы моделируете свою систему на некотором языке процессов (например, CCS, CSP, ACP, mCRL2, LOTOS) и используете доступные инструменты для (моделирования) проверки на наличие взаимоблокировок (и, возможно, некоторых других свойств). Примерами используемых инструментов являются FDR, mCRL2, CADP и Uppaal. Некоторые смелые души могут даже доказать, что их системы зашли в тупик, используя чисто символические методы (доказательство теорем; ищите Овики-Гриза).

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

mweerden
источник
0

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

пуджа бхарти
источник
0

Выше некоторые объяснения хороши. Надеюсь, что это также может быть полезно: https://ora-data.blogspot.in/2017/04/deadlock-in-oracle.html

В базе данных, когда сеанс (например, ora) хочет ресурс, удерживаемый другим сеансом (например, данными), но этот сеанс (данные) также хочет ресурс, который удерживается первым сеансом (ora). Также может быть задействовано более двух сессий, но идея будет одинаковой. Фактически, Deadlocks препятствуют продолжению работы некоторых транзакций. Например: предположим, что ORA-DATA удерживает блокировку A и запрашивает блокировку B, а SKU удерживает блокировку B и запрашивает блокировку A.

Спасибо,

Сапна
источник
0

Взаимная блокировка возникает, когда поток ожидает завершения другого потока, и наоборот.

Как избежать?
- Избегайте вложенных замков
- Избегайте ненужных замков
- Используйте thread join ()

Как вы это обнаружили?
запустите эту команду в cmd:

jcmd $PID Thread.print

ссылка : гиксфоргекс

Арун Раадж
источник
0

Замки не просто случаются с замками, хотя это самая частая причина. В C ++ вы можете создать взаимоблокировку с двумя потоками без блокировок, просто вызывая каждый поток вызовом join () для объекта std :: thread для другого.

Рагхав Навада
источник
0

Блокировка параллельного управления

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

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

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

Что такое тупик

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

введите описание изображения здесь

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

Восстановление из тупиковой ситуации

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

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

Даже если Threadкласс предоставляет stopметод, этот метод считается устаревшим с Java 1.1, поскольку он может привести к тому, что объекты останутся в несогласованном состоянии после остановки потока. Вместо этого Java определяетinterrupt метод, который действует как подсказка, поскольку поток, который прерывается, может просто игнорировать прерывание и продолжать его выполнение.

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

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

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

В отличие от JVM, транзакция базы данных разработана как элементарная единица работы. Следовательно, откат оставляет базу данных в согласованном состоянии.

Для более подробной информации по этой теме, проверьте эту статью .

Влад Михалча
источник
-2

Mutex по сути является замком, обеспечивающим защищенный доступ к общим ресурсам. В Linux тип данных мьютекса потока - pthread_mutex_t. Перед использованием инициализируйте его.

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

В целом, есть несколько неписаных основных принципов:

  • Получите блокировку перед использованием общих ресурсов.

  • Удерживать замок как можно быстрее.

  • Снимите блокировку, если поток возвращает ошибку.

Маркус Торнтон
источник
3
Это описывает блокировку, а не тупик.
маркиз Лорн