Обнаружение тупиков на мьютексах в многопоточных приложениях
3
Для обнаружения тупиков используется бихроматический направ-
ленный граф Холта [2], в котором множество вершин разбито на два не
пересекающихся подмножества: вершин-процессов и вершин-ресурсов.
Дуги графа могут соединять только вершины из разных подмножеств.
Дуга, направленная от ресурса к процессу, означает приобретение ре-
сурса процессом; в обратном же направлении — запрос процессом ре-
сурса. Доказанная в [2] теорема утверждает, что замкнутая цепь запро-
сов является необходимым условием тупика. Для обнаружения тупика
применяется метод редукции (сокращения) графа. Если граф полностью
сокращается и все вершины графа становятся изолированными, то си-
стема не находится в тупике. Если в результате сокращения графа обна-
ружена замкнутая цепь запросов, то система попала в тупик.
В результате вызова одного из вариантов библиотечной функции
mutex_lock(&mutex) поток, пытающийся войти в критическую сек-
цию, захваченную другим потоком, будет блокирован на мьютексе до
тех пор, пока другой поток не освободит этот мьютекс вызовом
mutex_unlock(&mutex). При этом для блокировки потока на мьютексе
в результате работы библиотечной функции вызывается соответ-
ствующая функция ядра. Замкнутая цепочка запросов к мьютексам
означает, что процессы попали в тупиковую ситуацию.
В отличие от семафоров, мьютексы, созданные потоками, не от-
ражены в соответствующей системной таблице. Каждый поток имеет
собственный список мьютексов в защищенном адресном простран-
стве процесса, доступ к которому из другого пользовательского про-
цесса невозможен. Однако на уровне ядра можно получить информа-
цию о состоянии блокировки потока на мьютексе. Поиск замкнутой
цепи запросов на захват мьютексов как ресурсов можно заменить по-
иском замкнутой цепи состояний блокировок на мьютексах.
Методика обнаружения блокировок потоков на мьютексах.
Для определения того, какая функция ядра блокирует поток на
мьютексе, можно использовать следующую технологию:
– написать программу, в которой искусственно создается блоки-
ровка потока на мьютексе;
– с помощью утилиты strace получить все системные вызовы, ко-
торые были выполнены программой;
– проанализировать набор полученных системных вызовов и пу-
тем сопоставления последовательности системных вызовов и про-
граммного кода найти функцию, которая блокирует процесс на
мьютексе (рис. 4).
Из полученного с помощью программы strace фрагмента дампа
видно, что библиотечная функция printf() вызывает системный вызов
write(), функция sleep() — выполнение функции ядра nanosleep(), а
вызов функции pthread_mutex_lock(&mutex1) заменяется функцией
ядра futex() (рис. 5).
