УДК 004.04

СТАТИЧЕСКАЯ ПРОВЕРКА КОРРЕКТНОСТИ РАЗДЕЛЕНИЯ РЕСУРСОВ В СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ

В.В. Никифоров, С.Н. Баранов

Аннотация


В ряду вопросов, возникающих в ходе разработки программных комплексов для СРВ, необходимо решать как общие для многозадачных систем вопросы обеспечения логической корректности создаваемой системы (сохранение целостности информационных ресурсов, исключения возможности взаимного блокирования задач), так и специфические для СРВ вопросы динамической корректности (своевременности исполнения задач). Решение этих вопросов в конечном счете сводится к проверке корректности размещения в теле каждой из задач синхронизирующих операторов, обеспечивающих согласованное исполнение задач. Такая проверка корректности осуществляется статически. С этой целью строятся модели, отражающие размещение синхронизирующих операторов в задачах приложения.
В настоящей статье предлагаются методы обработки таких моделей посредством построения специальных многодольных графов — графов зависимостей синхронизирующих операторов. Представляются две разновидности таких графов: а) графы связок, обеспечивающие проверку логической корректности многозадачных приложений, (корректность пересечений пар критических интервалов); и б) графы связок и критических интервалов, обеспечивающие проверку динамической корректности приложений для СРВ.

Ключевые слова


системы реального времени; модели многозадачных приложений; выполнимость задач; протоколы доступа; разделяемые ресурсы

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

PDF

Литература


  1. Давиденко К.Я. Технология программирования АСУТП. Проектирование систем реального времени, параллельных и распределенных приложений // М.: Энергоатомиздат. 1985. 183 с.
  2. Liu C., Layland J. Scheduling Algorithms for Multiprocessing in a Hard Real-Time Environment // Journal of the ACM. 1973. vol. 20. no. 1. pp. 46–61.
  3. Сорокин С.В. Системы реального времени: операционные системы // Современные технологии автоматизации. 1997. №2. C. 22-31.
  4. Buttazo G.C., Bertogna M., Yao G. Limited Preemptive Scheduling for Real-Time Systems // IEEE Transactions on Industrial Informatics. 2013. vol. 9. no 1. pp. 3–15.
  5. Грюнталь А.И. Планирование систем с асинхронным стартом // Информационные технологии и вычислительные системы. 2012. № 1. С. 32–51.
  6. Sun Y., Lipari G., Guan N., Yi W. Improving the response time analysis of global fixed-priority multiprocessor scheduling // Proc. of 20 IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA). 2014. pp. 1–9.
  7. Guan N. et al. Bounding Carry-in Interference to Improve Fixed-Priority Global Multiprocessor Scheduling Analysis // Proc. of 21 IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA). 2015. pp. 11–20.
  8. Andersson B. Global Static-Priority Preemptive Multiprocessor Scheduling with Utilization Bound 38% // Proceedings of the 12th International Conference on Principles of Distributed Systems. 2008. pp. 73–88.
  9. Baruah S., Bonifaci V., Marchetti-Spaccamela A. The Global EDF Scheduling of Systems of Conditional Sporadic DAG Tasks // Proc. of 27 Euromicro Conference on Real-Time Systems (ECRTS). 2015. pp. 222–231.
  10. Guan N., Chuancai G., Stigge M., Deng Q. Approximate Response Time Analysis of Real-Time Task Graphs // Proc. of 35 IEEE Real-Time Systems Symposium (RTSS). 2014. pp. 304–313.
  11. Докучаев А.Н. Особенности диспетчеризации сверхлегких задач в мультипроцессорных вычислительных системах реального времени // Информационные технологи. 2012. №2. С. 14–18.
  12. Колесов Н.В., Скородумов Ю.М., Толмачева М.В. Алгоритм независимого назначения иерархических заданий на процессоры в системе реального времени // Вестник компьютерных и информационных технологий. 2013. № 6. С.28–33.
  13. Pomeranz I. Design-for-Testability for Functional Broadside Tests under Primary Input Constraints // ACM Transactions on Design Automation of Electronic Systems (TODAES). 2016. vol. 21. Issue 2. Article No. 35.
  14. Bujtor F., Sorokin L., Vogler W. Testing Preorders for dMTS: Deadlock-and the New Deadlock-/DivergenceTesting // ACM Transactions on Embedded Computing Systems (TECS). 2016. vol. 16. Issue 2. Article No. 41.
  15. Данилов М.В., Никифоров В.В. Статическая обработка спецификаций программных систем реального времени // Программные продукты и системы. 2000. №4. С. 13–19.
  16. Dijkstra E.W. Hierarchical Ordering of Sequential Processes // Acta Informatica. 1971. vol. 1. no. 2. pp. 115–138.
  17. Liu J.W.S. Real-Time Systems // NJ: Prentice Hall. 2000. 590 p.
  18. Котов В.Е. Сети Петри // М.: Физматгиз. 1984. 160 с.
  19. Никифоров В.В., Шкиртиль В.И. Маршрутные сети — графический формализм представления структуры программных приложений реального времени // Труды СПИИРАН. 2010. Вып. 14. С. 5–28.
  20. Audsley N.C. Resource Control for Hard Real-Time Systems: A Review // Real-Time Systems Research Group. Department of Computer Science. University of York. UK. August 1991.
  21. Sha L., Rajkumar R., Lehoczky J.P. Priority Inheritance Protocols: An Approach to Real-Time Synchronization // IEEE Trans. on Computers. 1990. vol. 39. no 9. pp. 1175–1185.
  22. Andersson B., Jonsson J. Fixed-Priority Preemptive Multiprocessor Scheduling: To Partition or Not to Partition // Proceedings of the 7th International Conference on Real-Time Systems and Applications. 2000. pp. 337–346.
  23. Baker T.P., Cirinei M., Bertogna M. EDZL scheduling analysis // Real-Time Systems. 2008. vol. 40. no. 3. pp. 264-289.
  24. Докучаев А.Н. К оценке эффективности диспетчеризации мульти-процессорных систем реального времени с учетом влияния длительных блокировок // Программная инженерия. 2012. №9. С.2–7.
  25. Никифоров В.В., Шкиртиль В.И. Составное блокирование взаимосвязанных задач в системах на многоядерных процессорах // Известия высших учебных заведений. Приборостроение. 2012. № 2. С. 25–31.
  26. Nikiforov V.V., Baranov S.N. Multi-Partite Graphs and Verification of Software Applications for Real-Time Systems // Cybernetics and Information Tech-nologies. 2016. vol. 16. no. 2. pp. 85–96.


Виктор Викентьевич Никифоров - д-р техн. наук, профессор, главный научный сотрудник лаборатории информационно-вычислительных систем и технологий программирования, Федеральное государственное бюджетное учреждение науки Санкт-Петербургского института информатики и автоматизации Российской академии наук (СПИИРАН).
Область научных интересов: системы реального времени, встроенные системы, операционные системы.
Число научных публикаций: 120.

Адрес (E-mail): nik@iias.spb.su
Почтовый адрес: 14-я линия В.О., 39, Санкт-Петербург, 199178
Телефон: +7(812)3280887


Сергей Николаевич Баранов - д-р физ.-мат. наук, профессор, главный научный сотрудник лаборатории информационно-вычислительных систем и технологий программирования, Федеральное государственное бюджетное учреждение науки Санкт-Петербургского института информатики и автоматизации Российской академии наук (СПИИРАН), профессор, международная научная лаборатория Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики (ИТМО).
Область научных интересов: технология программирования, формальные методы.
Число научных публикаций: 120.

Адрес (E-mail): snbaranov@googlemail.com
Почтовый адрес: 14-я линия В.О., д. 39, Санкт-Петербург, 199178
Телефон: +7-812-328-0887




DOI: http://dx.doi.org/10.15622/sp.52.7