Алгоритмы проверки применимости протоколов доступа к ресурсам в системах реального времени

Аннотация

Введение: разработка многозадачных приложений требует организации разделения доступа отдельных задач к общим ресурсам. Для этого принято использовать синхронизирующие элементы типа мьютексов. Использование мьютексов может приводить к взаимному блокированию задач, для предотвращения которого применяются специальные протоколы доступа к ресурсам, усложняющие выполнение операций над мьютексами (запрос/освобождение ресурса) за счет введения дополнительных условий и (или) действий. Для приложений, работающих в реальном времени, соответствующее увеличение времени отклика может оказаться существенным. Ранее было предложено решение проблемы возникновения взаимного блокирования на основе статической обработки моделей программных приложений реального времени, представляемых средствами графического формализма типа маршрутных сетей. Это решение опирается на построение специального многодольного ориентированного графа - графа зависимостей связок критических интервалов. Цель исследования: разработать алгоритмы, реализующие предложенную ранее обработку, и дать оценку сложности их исполнения. Результаты: разработаны алгоритмы, позволяющие анализировать программные продукты на возможность возникновения в них взаимного блокирования задач. Анализ проводится в три этапа. На первом этапе строится граф связок критических интервалов. После этого в построенном графе выделяются междольные контуры. Наконец, обнаруженные на предыдущем этапе междольные контуры проверяются на дизъюнктность. Оценка сложности показала, что время построения графа связок линейно относительно суммы числа связок и их зависимостей. Сложность построения перечня междольных контуров оценивается как 0((n + e)(c + 1)), где с - число контуров в графе связок; п - число вершин; е - число ребер. Сложность проверки графа связок на дизъюнктность междольных контуров линейно зависит от суммы длин всех этих контуров. Практическая значимость: разработанные алгоритмы позволяют на раннем этапе разработки принимать решения о перестройке структуры приложения для устранения возможности взаимной блокировки задач и о выборе оптимального с точки зрения производительности протокола доступа.