Обнаружение тупиков без рутины

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

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

Изучение кода вручную подвержено ошибкам и утомительно. Гораздо лучше, чтобы компьютер сделал это для вас. Ниже мы увидим, как можно использовать инструмент статического анализа ThreadSafe от Contemplate для неустанной проверки вашего кода на наличие возможных взаимоблокировок, на примере потенциальной тупиковой ситуации, обнаруженной в приложении K9Mail для Android.

Ингредиенты тупика

Что такое тупики? С точки зрения того, что кто-то наблюдает за внешним поведением программы, у нас может возникнуть соблазн просто сказать, что тупик возникает всякий раз, когда программа перестает отвечать. Но в мире параллельного программирования мы имеем в виду нечто совершенно конкретное, когда говорим «тупик». Вот довольно общее определение, которое применяется во многих случаях:

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

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

1. Два или более одновременных потока: для возникновения взаимоблокировки должно быть несколько параллельных потоков выполнения.
2. Исключительные приобретения ресурса: тупики возникают, когда параллельные потоки пытаются получить эксклюзивный доступ к некоторому ресурсу. Исключительный доступ часто требуется для корректности в параллельных программах, чтобы предотвратить взаимодействие нескольких потоков друг с другом, но, как мы увидим, именно эта исключительность может привести к взаимоблокировке.
3. Циркулярная зависимость: для возникновения тупика конечным компонентом является круговая зависимость: кольцо потоков, каждый из которых получил доступ к какому-либо исключительному ресурсу, но желает доступа к другому. Из-за цикличности каждый поток в конечном итоге ожидает, что он освободит свой ресурс, чтобы продолжить. Этого никогда не произойдет, поэтому кольцо зашло в тупик.

Простой тупик

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

Для минимальности у нас будет два потока («A» и «B»), каждый из которых пытается получить две блокировки («lock1» и «lock2»). Блокировки являются прототипом исключительного ресурса: только один поток может одновременно удерживать блокировку.

Чтобы получить тупик, осталось получить круговую зависимость между приобретениями блокировки. «Смертельная» округлость закодирована в поведении двух потоков, которые я написал как фрагменты кода Java:

Представьте, что потоки «A» и «B» запланированы следующим образом:

A1. acquire lock1
                                  B1. acquire lock2
A2. acquire lock2
    *blocks*
                                  B2. acquire lock1
                                      *blocks*

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

В каком-то смысле нам не повезло попасть в тупик. Эти два потока могли быть запланированы следующим образом:

A1. acquire lock1
A2. acquire lock2
A3. perform action
A4. release lock2
A5. release lock1
                                  B1. acquire lock2
                                  B2. acquire lock1
                                  B3. perform action
                                  B4. release lock1
                                  B5. release lock2

В этом расписании тупиковая ситуация не возникает.

Именно эта зависимость от порядка и чередования потоковых операций делает отсутствие взаимоблокировки таким трудным для проверки. Потоки A и B всегда имеют скрытую способность к взаимоблокировке из-за циклической зависимости между приобретениями потоков «lock1» и «lock2». Во время тестирования мы можем запускать только второй сценарий. Когда система находится под небольшой нагрузкой, задачи могут эффективно выполняться последовательно, с небольшим перекрытием, как во втором сценарии. Однако по мере увеличения нагрузки, возможно, в критические моменты производства, вероятность чередования двух потоков, как в первом сценарии, возрастает, и скрытая угроза тупика становится реальной угрозой.

Более сложный тупик

В «Потоке A» и «Потоке B» выше при чтении кода было совершенно очевидно, что между блокировками lock1и существует циклическая зависимость lock2.

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

и

Предположим, опять же, что у нас есть два потока, A и B. Поток A имеет ссылку на объект Folder, а поток B имеет ссылку на объект Message. Кроме того, объект сообщения содержится в списке сообщений папки, а поле папки объекта сообщения ссылается на объект папки. Этот сценарий изображен на следующей диаграмме:

---

---

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

1. Мы предполагаем, что есть два потока, поток A и поток B, которые будут выполняться одновременно.
2. Внутренние замки встроены в Messageи Folderобъекты являются исключительными ресурсами.
3. Очевидно, что в графе объектов существует круговая зависимость между Folderобъектом и Messageобъектом. Это не обязательно круговая зависимость между двумя исключительными ресурсами.

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

Предположим, что одновременно поток A вызывает setAllRead()метод в Folderэкземпляре, а поток B вызывает setRead()метод в Messageэкземпляре. Теперь возможна следующая последовательность событий:

• Поток A получает блокировку для Folderэкземпляра, потому что setAllRead()метод объявлен как synchronized. Затем поток А переходит к списку сообщений, обращаясь setRead()к каждому из них.
• Поток B получает блокировку для Messageэкземпляра, потому что setRead()метод объявлен как synchronized.
• Поток A достигает Messageэкземпляра, который Поток B заблокировал, и вызывает setRead()его. Этот метод объявлен как synchronized, поэтому Поток A пытается получить блокировку для Messageэкземпляра. Он не может получить эту блокировку, потому что поток B уже имеет ее. Поток A теперь блокируется, ожидая снятия блокировки потоком B.
• Поток B вызывает decrementUnreadCount()метод в Folderэкземпляре. Этот метод объявлен как synchronized, поэтому Поток B пытается получить блокировку для Folderэкземпляра. Он не может получить эту блокировку, потому что поток A получил ее на шаге 1. Теперь поток B блокирует, ожидая снятия блокировки потоком A.

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

Нахождение тупиков: вручную и машиной

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

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

Нахождение тупиков вручную

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

Чтобы искать округлости, мы создаем граф зависимостей блокировок для всех блокировок и получений блокировок в программе. Мы рисуем узел для каждой блокировки в программе и грань между двумя блокировками X и Y, если существует ситуация, когда блокировка X удерживается при получении блокировки Y. Циклы на этом графике представляют циклические зависимости между блокировками: ситуации, которые могут привести к в тупик!

Для Folderи , Messageнапример, график выглядит следующим образом :

---

---

Все внутренние блокировки, связанные с объектами Folderкласса, были собраны в узел «Папка» в левом верхнем углу; аналогично, все внутренние блокировки, связанные с Messageклассом объектов , были собраны в узле «Сообщение» в правом нижнем углу. Поскольку мы не обязательно знаем, сколько Folderи сколько Messagesэкземпляров будет фактически сгенерировано во время выполнения, два узла в графе заменяют все возможные экземпляры.

Край от «Папка» до «Сообщение» возникает от вызова методом Folder.setAllRead()к Message.setRead(). Поскольку оба метода есть synchronized, этот вызов представляет получение блокировки для Messageэкземпляра, в то время как удержание блокировки для Folderэкземпляра.

Аналогично, грань от «Сообщения» до «Папки» возникает в результате вызова метода Message.setRead()к Folder.decrementUnreadCount(). Опять же, так как оба метода synchronized, этот вызов представляет получение блокировки на Folderэкземпляр, удерживая блокировку на Messageэкземпляре.

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

Мы можем сказать «потенциально» только потому, что мы абстрагировали реальный объектный граф. Вполне возможно, что никогда не будет пары Folderобъекта и Messageобъекта, которые указывают друг на друга.

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

Нахождение тупиков на машине

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

Конечно, мы можем заставить компьютер сделать это для нас?

ThreadSafe — это инструмент статического анализа, специально разработанный для поиска дефектов параллелизма в программах Java. Запуск Eclipse , плагин THREADSAFE на те Folderи Messageклассах производит следующий вывод:

---

---

ThreadSafe has discovered the potential deadlock by analysing the graph of lock acquisitions and discovering a circularity. The locks involved are clearly marked, with the line numbers showing where each lock was acquired while another lock was held.

Getting ThreadSafe to do this clearly beats finding a piece of paper big enough to draw out the graph of all the locks in a program and the edges between them!

Once ThreadSafe has found a potential deadlock situation, we can investigate further to determine whether there is a chance that it can actually arise in practice. Maybe it won’t, but it is better to be deadlock-free than sorry!

Using ThreadSafe to find a potential deadlock in K9Mail

K9Mail is an Android email client, written in Java, that uses concurrent threads to prevent the user interface from being made unresponsive during communication with the network.

K9Mail consists of over 1000 classes. It would be impractical to go through all of them to look for potential deadlock cycles. But we can get ThreadSafe to do the work for us. Running the ThreadSafe Eclipse plugin on K9Mail produces the following deadlock warning:

---

---

From the finding report, we can see that the intrinsic locks associated with objects of the Preferences and Account classes form a circular relationship. Investigating this finding using Eclipse’s call hierarchy feature, we learn that the circularity can arise from the following pieces of code (links are to the K9Mail source code on GitHub for the version that was analysed by ThreadSafe):

1. In the synchronized method Account.save(Preferences), there is a call on line 679 to the synchronized method Preferences.getAccounts().
2. In the synchronized method Preferences.getAvailableAccounts(), there is a call on line 95 to the synchronized method Account.isEnabled().

This situation is very similar to the Folder and Message example we looked at above. If two threads invoke the Account.save() method and the Preferences.getAvailableAccounts() method concurrently, then there is a real chance that a deadlock will result.

It will take further investigation to determine whether or not this scenario is actually possible, but ThreadSafe has successfully narrowed down the number of lines of code that we have to look at.

Conclusions

Deadlocks are tricky. To find them, we can either wait until the scheduler picks the unlucky schedule that results in a deadlock, or we can exhaustively search our code for potential deadlocks. By using a tool like Contemplate’s ThreadSafe, we can find potential deadlocks without too much work.

ThreadSafe is capable of discovering a range of other concurrency defects, including atomicity errors arising from incorrect use of the concurrent collections framework and potential data races. The ThreadSafe technical briefing and demonstration video provide further examples of the subtle but potentially catastrophic defects that ThreadSafe can detect.

Resources

• The Contemplate Website — including further information about ThreadSafe, information on how to request a trial version, and how to buy it.
• The k9mail Git repository — place to download the source code of K9Mail. The version used for this article has commit SHA1 id: cc8353d25572b5f1c19047c0c093371f5ac721b4.