Национальный цифровой ресурс Руконт - межотраслевая электронная библиотека (ЭБС) на базе технологии Контекстум (всего произведений: 552169)
Консорциум Контекстум Информационная технология сбора цифрового контента
Уважаемые СТУДЕНТЫ и СОТРУДНИКИ ВУЗов, использующие нашу ЭБС. Рекомендуем использовать новую версию сайта.
Информационно-управляющие системы  / №4 2017

АЛГОРИТМЫ ПРОВЕРКИ ПРИМЕНИМОСТИ ПРОТОКОЛОВ ДОСТУПА К РЕСУРСАМ В СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ (160,00 руб.)

0   0
Первый авторНикифоров В. В.
АвторыПодкорытова С. А.
Страниц8
ID633391
АннотацияВведение: разработка многозадачных приложений требует организации разделения доступа отдельных задач к общим ресурсам. Для этого принято использовать синхронизирующие элементы типа мьютексов. Использование мьютексов может приводить к взаимному блокированию задач, для предотвращения которого применяются специальные протоколы доступа к ресурсам, усложняющие выполнение операций над мьютексами (запрос/освобождение ресурса) за счет введения дополнительных условий и (или) действий. Для приложений, работающих в реальном времени, соответствующее увеличение времени отклика может оказаться существенным. Ранее было предложено решение проблемы возникновения взаимного блокирования на основе статической обработки моделей программных приложений реального времени, представляемых средствами графического формализма типа маршрутных сетей. Это решение опирается на построение специального многодольного ориентированного графа – графа зависимостей связок критических интервалов. Цель исследования: разработать алгоритмы, реализующие предложенную ранее обработку, и дать оценку сложности их исполнения. Результаты: разработаны алгоритмы, позволяющие анализировать программные продукты на возможность возникновения в них взаимного блокирования задач. Диализ проводится в три этапа. На первом этапе строится граф связок критических интервалов. После этого в построенном графе выделяются междольные контуры. Наконец, обнаруженные на предыдущем этапе междольные контуры проверяются на дизъюнктность. Оценка сложности показала, что время построения графа связок линейно относительно суммы числа связок и их зависимостей. Сложность построения перечня междольных контуров оценивается как 0((п + е)(с * 1)), где с – число контуров в графе связок; п – число вершин; е - число ребер. Сложность проверки графа связок на дизъюнктность междольных контуров линейно зависит от суммы длин всех этих контуров. Практическая значимость: разработанные алгоритмы позволяют на раннем этапе разработки принимать решения о перестройке структуры приложения для устранения возможности взаимной блокировки задач и о выборе оптимального с точки зрения производительности протокола доступа.
АЛГОРИТМЫ ПРОВЕРКИ ПРИМЕНИМОСТИ ПРОТОКОЛОВ ДОСТУПА К РЕСУРСАМ В СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ [Электронный ресурс] / В.В. Никифоров, С.А. Подкорытова // Информационно-управляющие системы .— 2017 .— №4 .— Режим доступа: https://rucont.ru/efd/633391

Предпросмотр (выдержки из произведения)

Для обеспечения анализа особенностей структуры многозадачных приложений реального времени строятся модели, отражающие размещение синхронизирующих операторов в задачах приложения, строятся методы обработки таких моделей, позволяющие проверить возможность возникновения аномальных ситуаций в ходе исполнения приложения. <...> Примером аномальных ситуаций является взаимное блокирование задач, когда две или более задач оказываются связанными замкнутой цепочкой ожиданий поступления синхронизирующих посылок [2]. <...> Известны подходы к построению таких моделей и методов их обработки, направленные на предотвращение возможностей возникновения взаимного блокирования задач [3]. <...> Подход, представленный в работах [4, 5], опирается на представление структуры многозадачного программного приложения средствами маршрутных сетей [6] и обработку таких моделей с помощью специ№ 4, 2017 альных многодольных графовграфов связок критических интервалов. <...> При этом для проверки возможности возникновения взаимного блокирования предлагается выполнять проверку наличия в графе связок междольных контуров. <...> Однако в указанных работах не представлены алгоритмы: — построения перечня связок критических интервалов; — построения графа связок, соответствующего конкретному экземпляру маршрутной сети; — построения перечня имеющихся в графе связок междольных контуров; — проверки наличия в графе связок пересекающихся междольных контуров. <...> В настоящей статье приведены такие алгоритмы, выполнена оценка их сложности. <...> Протоколы доступа к разделяемым ресурсам Большинство реальных программных приложений реального времени содержит взаимозависимые задачи, для которых не исключается возможность попадания в состояние ожидания сигнальных сообщений от других задач. <...> Одной из разновидностей причин возникновения взаимной ИНФОРМАЦИОННОУПРАВЛЯЮЩИЕ СИСТЕМЫ 59 ПРОГРАММНЫЕ И АППАРАТНЫЕ СРЕДСТВА зависимости задач является необходимость <...>