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


https://doi.org/10.15217/issnl684-8853.2017.4.59

Полный текст:


Аннотация

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

Об авторах

В. В. Никифоров
Санкт-Петербургский институт информатики и автоматизации РАН
Россия


С. А. Подкорытов
Санкт-Петербургский институт информатики и автоматизации РАН
Россия


Список литературы

1. Давиденко К. Я. Технология программирования АСУТП. Проектирование систем реального времени, параллельных и распределенных приложений. - М.: Энергоатомиздат, 1985. - 183 с.

2. Liu J. W. S. Real-Time Systems. - NJ: Prentice Hall, 2000. - 590 p.

3. Sha L., Rajkumar R., Lehoczky J. P. Priority Inheritance Protocols: An Approach to Real-Time Synchronization // IEEE Trans. on Computers. 1990. N 39(9). P. 1175-1185.

4. Никифоров В. В., Баранов С. Н. Статическая проверка корректности разделения ресурсов в системах реального времени // Тр. СПИИРАН. 2017. № 3(52). С. 17-21.

5. Nikiforov V. V., Baranov S. N. Multi-Partite Graphs and Verification of Software Applications for Real-Time Systems // Cybernetics and Information Technologies. 2016. N 16(2). P. 85-96.

6. Никифоров В. В., Шкиртиль В. И. Маршрутные сети - графический формализм представления структуры программных приложений реального времени // Тр. СПИИРАН. 2010. № 14. С. 5-28.

7. Данилов М. В., Никифоров В. В. Статическая обработка спецификаций программных системного времени // Программные продукты и системы. 2000. № 4. С. 13-19.

8. Baranov S. N., Nikiforov V. V. Density of Multi-Task Real-Time Applications // Proc. 17th Conf. FRUCT, Yaroslavl, 2015. С. 9-15.

9. Никифоров В. В., Шкиртиль В. И. Составное блокирование взаимосвязанных задач в системах на многоядерных процессорах // Изв. вузов. Приборостроение. 2012. № 7. С. 25-31.

10. Никифоров В. В., Шкиртиль В. И. Цепное блокирование задач в системах реального времени // Информационно-измерительные и управляющие системы. 2013. № 7. С. 17-21.

11. Никифоров В. В. Протокол предотвращения взаимного блокирования задач в системах реального времени // Изв. вузов. Приборостроение. 2014. № 57(12). С. 21-27.

12. Johnson D. Finding All the Elementary Circuits of a Directed Graph // SIAM Journal on Computing. 1975. N 4(1). P. 77-84. doi:10.1137/0204007/issn0097-5397

13. Tarjan R. Enumeration of the Elementary Circuits of a Directed Graph // SIAM Journal on Computing. 1973. N 2(3). P. 211-216. doi:10.1137/0202017/ issn 0097-5397

14. Tiernan J. C. An Efficient Search Algorithm to Find the Elementary Circuits of a Graph // Communications of the ACM. 1970. N 13(12). P. 722-726. doi:10.1145/362814.362819

15. Mateti P., Deo N. On Algorithms for Enumerating all Circuits of a Graph // SIAM Journal on Computing. 1976. N 5(1). P. 90-99. doi:10.1137/0205007

16. Tarjan R. Depth-first Search and Linear Graph Algorithms // SIAM Journal on Computing. 1972. N 1(2). P. 146-160.

17. Dijkstra E. A Discipline of Programming. - NJ: Prentice Hall, 1976. - 217 р.


Дополнительные файлы

Для цитирования: Никифоров В.В., Подкорытов С.А. Алгоритмы проверки применимости протоколов доступа к ресурсам в системах реального времени. Информационно-управляющие системы. 2017;89(4):59-66. https://doi.org/10.15217/issnl684-8853.2017.4.59

For citation: Nikiforov V.V., Podkorytov S.A. Algorithms for Checking Applicability of Resource Access Protocols in Real-Time Systems. Information and Control Systems. 2017;89(4):59-66. (In Russ.) https://doi.org/10.15217/issnl684-8853.2017.4.59

Просмотров: 42


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1684-8853 (Print)
ISSN 2541-8610 (Online)