Обнаружение тупиков на мьютексах в многопоточных приложениях
1
УДК 681.3.066
Обнаружение тупиков на мьютексах
в многопоточных приложениях
© В.С. Белоус, В.А. Крищенко, Н.Ю. Рязанова
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
Статья посвящена разработке метода обнаружения тупиков при использовании в
приложениях мьютексов, реализованных по стандарту POSIX. В рамках теории
тупиков проанализирован и реализован способ получения информации о блокиро-
ванных на мьютексах процессах. Показано, что обнаружение замкнутой цепи бло-
кировок соответствует обнаружению цикла в графе запросов — распределений.
Описан механизм включения в ядро средств перехвата функции ядра, которая
управляет захватом и освобождением потоков на мьютексах. Предложен алго-
ритм обнаружения тупика на основе полученной информации.
Ключевые слова
:
тупик, взаимоисключение, мьютекс, функция-перехватчик, обна-
ружение тупиков.
Введение.
Современные приложения, как правило, являются мно-
гопоточными. Часто в процессе выполнения параллельные потоки об-
ращаются к одним и тем же структурам данных и пытаются выполнить
какие-то действия с этими структурами. Например, несколько потоков
могут пытаться одновременно добавить в список, такой как стек или
очередь, новый элемент. Добавление элемента в список выполняется с
помощью последовательности действий показанной на рис. 1:
Рис. 1.
Пример параллельного выполнения вставки элемента в очередь
В результате выполнения данной последовательности операций
каждым потоком, новый элемент включается в цепочку элементов.
Если данная последовательность операций в список будет прервана,
то возможна потеря связи с одним из новых элементов.
Например, если после выполнения первой строки в коде первого
потока будет прервано его выполнение, то элемент, добавляемый
вторым потоком, может быть утерян (рис. 2).
Чтобы таких проблем не возникало, последовательность дей-
ствий, выполняемая над структурами данных, должна быть недели-
мой. Необходимо предпринять специальные меры, чтобы такую по-
следовательность действий нельзя было прервать. В ОС Linux для
этого могут использоваться такие средства взаимоисключения, как
