Здравствуйте, уважаемые Хабраузеры! Так получилось, что это уже третий пост в блоге нашей компании, и он, как и первые два, посвящен вопросам многопоточного программирования и возникающим проблемам.
Так получилось не случайно, ведь мы на собственном опыте убедились, что ситуации, возникающие при написании многопоточных программ, невероятно сложны для отладки, поскольку они во многом определяются динамикой программы на конкретной аппаратной платформе.
Я уверен, что большинство программистов сталкивались с ситуацией, когда программа, прекрасно работающая на одном компьютере, на другом совершенно неожиданно начинает вырождаться практически на ровном месте.
При написании наших предыдущих постов мы допустили непростительную ошибку, начав рассматривать взаимные блокировки со сложных, но, как нам казалось, наиболее интересных случаев.
Уважаемая аудитория Хабра, к сожалению, этого не оценила.
Спешим исправиться и пусть не с первого раза, но все же подходим к проблеме блокировки с самого начала.
Однако мы все равно ожидаем, что вы знаете, зачем нужны инструменты синхронизации и что они собой представляют при написании многопоточных программ.
Рецепты, описанные в этом посте, очень просты, но не все даже профессиональные программисты используют их осознанно, руководствуясь скорее ощущением «почему-то кажется, что захватывать тот мьютекс из-под захваченного не стоит».
Так мы жили много-много лет, когда в один страшно ответственный момент не обнаружили, что на оборудовании, которое срочно нужно было отправить заказчику, наш любимый софт не может прожить и часа без тупиковой ситуации.
Потратив несколько дней на работу над этой проблемой вместе с нашими ведущими программистами, мы приняли решение, которое изменило нашу жизнь — мы начали строгую формализацию тупиковых ситуаций, включая строгие математические доказательства того, почему это можно сделать, а почему нельзя.
Надо сказать, что наше исследование выродилось в кандидатскую диссертацию одного из наших сотрудников, но я не уверен, что использованный там формат изложения будет здесь интересен.
Итак, про блокировку с самого начала.
Природа тупиков
Не будем вдаваться в сложные математически выверенные определения тупиковых ситуаций и скажем просто: взаимоблокировка — это состояние системы, при котором один поток ждет, чтобы что-то произошло, но это нечто не может произойти, потому что другого потока ждет, чтобы что-то произошло.затем из первого потока.
Традиционно считается, что блокировки всегда вызываются мьютексами, но это не совсем так.
Причиной блокировки могут быть любые средства и механизмы синхронизации, предполагающие ожидание чего-либо от одного потока со стороны другого, например, ожидание сигнала по условной переменной или, что гораздо менее очевидно, ожидание завершения другого поток (ожидание/присоединение к потоку).
По сути, второй случай — это то же самое «ожидание сигнала», однако из-за неявного характера этой операции синхронизации при поиске взаимоблокировок о ней просто забывают как о потенциальном источнике угрозы и часто в коде не замечено.
Прежде чем перейти к рассмотрению конкретных ситуаций простейших взаимоблокировок, хотелось бы сказать несколько слов о модели, которую мы используем для описания многопоточных программ и ситуаций, возникающих в них.
Несколько слов о модели многопоточной программы
Мы назвали эту модель «моделью перехода» и она представляет собой набор ориентированных графов, где каждый граф представляет поток (субъект).Каждый граф имеет одну начальную вершину, соответствующую состоянию, когда ни одно средство синхронизации еще не задействовано, и одну конечную вершину, соответствующую состоянию, когда ни одно средство синхронизации еще не задействовано.
Предполагается, что при достижении конечной вершины поток автоматически начинается заново.
Все остальные вершины графов представляют собой операцию по отношению к тому или иному средству синхронизации, например, L (lock) – захват мьютекса, U (unlock) – освобождение мьютекса и т. д. Для доказательства утверждений важно, что модель игнорирует время между выполнением отдельных операций по отношению к средствам синхронизации, тем самым расширяя возможный диапазон динамики до бесконечности.
Если аудитории Хабра интересна математическая и физическая суть модели, то я готов написать на эту тему отдельный пост, а здесь.
это только начало долгого, но интересного рассказа о многопоточном программировании.
Пример модели, состоящей из одного потока (предмета): 
Рисунок 1.
В соответствии с этим рисунком испытуемый может идти по двум ветвям: 0, L1, U1, 0 или 0, L1, L2, U2, U1, 0. Эту схему можно рассматривать как конечный автомат, грамматика которого включает в себя две фразы {0, L1, U1, 0} и {0, L1, L2, U2, U1, 0}.
Будем считать, что время перехода между действиями по отношению к средствам синхронизации конечно, т.е.
алгоритмически корректно.
Давайте не будем считать ошибкой синхронизации захват и удержание мьютекса в ожидании какого-либо действия пользователя, которое потенциально может никогда не произойти.
Чтобы проверить программу на предмет потенциального возникновения тупиковой ситуации, необходимо создать цепочки выполнения всех возможных субъектов в программе.
Простейшая взаимная блокировка с использованием мьютексов
Предположим, что в нашей программе помимо потока (предмета), показанного на рисунке 1, есть еще один:
Фигура 2. Смею сказать, что наша программа имеет потенциальный тупик, и даже если ваши тестировщики утверждают, что все работает отлично, то вы не застрахованы от ситуации, что на другом железе ваша программа будет вести себя так:
Рисунок 3. Ничто не мешает нашим двум независимым потокам выполняться так: поток 1 успел захватить мьютекс 1, затем планировщик переключил выполнение на поток 2, который заполучил мьютекс 2, и после этого оба наших потока пытаются захватить уже захваченные мьютексы — взаимоблокировка ! Назовем систему потоков (субъектов) несовместимой, если существует хотя бы один вариант перекрытия их цепочек выполнения, при котором возникает ситуация взаимной блокировки.
Соответственно, совместима система субъектов, для которой нет динамики, при которой может возникнуть ситуация взаимного блокирования.
Два рассматриваемых субъекта несовместимы, т.к.
существует вариант наложения, показанный на рисунке 3, при котором возникает тупиковая ситуация.
Обратите внимание, что подобные темы не обязательно приведут к блокировке (зависанию) программы.
Динамика конкретного задания (время перехода между обращениями к инструментам синхронизации) может быть такой, что найденный вариант наложения никогда не появится в реальности.
В любом случае программный код, описываемый такой моделью, потенциально опасен и блокировка может произойти при портировании на другую программную или аппаратную платформу или просто при изменении условий эксплуатации.
Рисунок 4
Важно помнить, что потоки могут быть попарно совместимы друг с другом, но не совместимы в более крупной комбинации.
На рис.
5 представлена модель программы, в которой все субъекты попарно совместимы друг с другом, но вместе они приводят к тупиковой ситуации.
Рисунок 5
На рисунке 6 показан еще один вариант объединения цепочек выполнения для модели, представленной на рисунке 5, в которой возникает взаимоблокировка.
Рисунок 6
Я просто хочу сказать: Как страшно жить!
И это действительно было бы так, если бы не два очень простых правила, которым интуитивно следуют профессиональные программисты, часто даже не задумываясь, почему они это делают.
Первое правило
Всегда освобождайте захваченные мьютексы в порядке, обратном их получению, т. е.следуйте логике «первый захвачен, последний освобожден».
Второе правило
Всегда следуйте одному и тому же порядку получения мьютексов.Если вы захватываете мьютекс 1, а затем мьютекс 2 в одном потоке, то в другом потоке их получение в другом порядке недопустимо.
На самом деле правило не так просто, как кажется на первый взгляд. Давайте еще раз внимательно посмотрим на рисунок 6. Там это правило нарушается, но это несколько неочевидно.
Глядя на первый поток, мы видим, что мы приобретаем мьютекс 2 после мьютекса 1. Глядя на второй поток, мы видим, что мы приобретаем мьютекс 3 после мьютекса 2. Объединение этих наблюдений означает, что мы приобретаем мьютекс 3 после мьютекса 1, что не является выполняется в потоке 3. Результатом этого неисполнения является взаимоблокировка, показанная на рисунке.
Несмотря на простоту этих правил, смею сказать, что если ваша программа в качестве инструментов синхронизации использует только мьютексы и вы соблюдали эти правила, то взаимоблокировки вам не страшны! Мы, конечно, не учитываем ситуацию с попыткой двойного захвата нерекурсивного мьютекса одним потоком, но это скорее глупость, чем тупик.
В заключение хотелось бы задать вопрос: интересна ли эта тема аудитории Хабра? Если да, то есть желание и возможность рассказать о чуть более интересных ситуациях, возникающих при использовании сигнальных переменных и, возможно, чуть глубже погрузиться в доказательную базу — это уже для опытных программистов многопоточных приложений.
Я надеюсь, что этот пост был полезен.
Читай продолжение - Рецепты против взаимоблокировок в сигнальных переменных .
Теги: #многопоточность #взаимные блокировки #мьютекс #проектирование и рефакторинг #Параллельное программирование
-
Йемен
19 Oct, 24 -
Приложения Для Sony Nex-6
19 Oct, 24 -
Интеллектуальная Собственность В Стартапах
19 Oct, 24
