Параллелизм Java: тупик

В этой статье мы рассмотрим ситуации взаимоблокировки в многопоточном программировании Java и способы их избежать.

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

Например, если поток 1 блокирует A и пытается заблокировать B, а поток 2 уже заблокировал B и пытается заблокировать A, возникает взаимоблокировка. Поток 1 никогда не получит B, а поток 2 никогда не получит A. Кроме того, ни один из них никогда не узнает. Они навсегда останутся заблокированными для каждого своего объекта, A и B. Это тупиковая ситуация.

Ситуация проиллюстрирована ниже:

Thread 1  locks A, waits for B
Thread 2  locks B, waits for A

Более сложные тупиковые ситуации

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

Thread 1  locks A, waits for B
Thread 2  locks B, waits for C
Thread 3  locks C, waits for D
Thread 4  locks D, waits for A

Поток 1 ожидает потока 2, поток 2 ожидает потока 3, поток 3 ожидает потока 4, а поток 4 ожидает потока 1.

Взаимоблокировки базы данных

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

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

Например

Transaction 1, request 1, locks record 1 for update
Transaction 2, request 1, locks record 2 for update
Transaction 1, request 2, tries to lock record 2 for update.
Transaction 2, request 2, tries to lock record 1 for update.

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

Предотвращение тупиковых ситуаций

В некоторых ситуациях есть возможность предотвратить тупиковые ситуации. Есть три основных метода:

Блокировать порядок
Тайм-аут блокировки
Обнаружение взаимоблокировок

Блокировка заказа

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

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

Thread 1:
  lock A 
  lock B

Thread 2:
   wait for A
   lock C (when A locked)

Thread 3:
   wait for A
   wait for B
   wait for C

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

Например, ни поток 2, ни поток 3 не могут заблокировать C, пока они сначала не заблокируют A. Поскольку поток 1 удерживает блокировку A, потоки 2 и 3 должны сначала дождаться разблокировки блокировки A. Затем они должны успешно заблокировать A, прежде чем они смогут попытаться заблокировать B или C.

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

Тайм-аут блокировки

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

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

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

Thread 1 locks A
Thread 2 locks B
Thread 1 attempts to lock B but is blocked
Thread 2 attempts to lock A but is blocked
Thread 1's lock attempt on B times out
Thread 1 backs up and releases A as well
Thread 1 waits randomly (e.g. 257 millis) before retrying.
Thread 2's lock attempt on A times out
Thread 2 backs up and releases B as well
Thread 2 waits randomly (e.g. 43 millis) before retrying.

В приведенном выше примере поток 2 попытается снять блокировки примерно за 200 мс до потока 1 и, следовательно, скорее всего, удастся снять обе блокировки. Затем поток 1 будет ждать, уже пытаясь принять блокировку A. Когда поток 2 завершится, поток 1 также сможет принять обе блокировки (если поток 2 или другой поток не возьмет промежуточные блокировки).

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

Кроме того, если достаточное количество потоков конкурирует за одни и те же ресурсы, они все равно рискуют пытаться использовать потоки в одно и то же время снова и снова, даже если истечет время ожидания и будет выполнено резервное копирование. Этого может не произойти с 2 потоками, каждый из которых ожидает от 0 до 500 мс перед повторной попыткой, но с 10 или 20 потоками ситуация иная. Тогда вероятность того, что два потока ждут в одно и то же время перед повторной попыткой (или достаточно близко, чтобы вызвать проблемы), намного выше.

Проблема с механизмом тайм-аута блокировки заключается в том, что невозможно установить тайм-аут для ввода синхронизированного блока в Java. Вам придется создать собственный класс блокировки или использовать одну из конструкций параллелизма Java 5 в пакете java.util.concurrency.

Обнаружение тупиковых ситуаций

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

Каждый раз, когда поток принимает блокировку, это отмечается в структуре данных (карта, график и т. Д.) Потоков и блокировок. Кроме того, всякий раз, когда поток запрашивает блокировку, это также отмечается в этой структуре данных.

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

Конечно, сценарий взаимоблокировки может быть намного сложнее, чем два потока, удерживающие блокировки друг друга. Поток A может ждать потока B, поток B ожидает потока C, поток C ожидает потока D, а поток D ожидает потока A. Чтобы поток A обнаружил тупик, он должен транзитивно проверить все запрошенные блокировки потоком B Из запрошенных блокировок потока B поток A перейдет к потоку C, а затем к потоку D, из которого он найдет одну из блокировок, удерживаемых самим потоком A. Тогда он знает, что произошла тупиковая ситуация.

Ниже приведен график блокировок, принятых и запрошенных 4 потоками (A, B, C и D). Подобная структура данных может использоваться для обнаружения взаимоблокировок.

Итак, что делают потоки, если обнаруживается тупик?

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

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

Вывод

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

В следующей статье мы проверим Блокировки в Java. Следите за обновлениями.

Эта статья оказалась полезной? Подписывайтесь на меня (Дмитрий Тимченко) на Medium и смотрите другие мои статьи ниже! Пожалуйста, поделитесь этой статьей!

Параллелизм Java: сигнализация потоков
В этой статье мы рассмотрим сигнализацию потоков и то, как она помогает потокам взаимодействовать друг с другом. medium.com

Java Concurrency: Synchronized
В этой статье мы расскажем о Synchronized и о том, как это помогает многопоточному программированию Java medium.com

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