Статическая проверка корректности разделения ресурсов в системах реального времени
Ключевые слова:
системы реального времени, модели многозадачных приложений, выполнимость задач, протоколы доступа, разделяемые ресурсыАннотация
В ряду вопросов, возникающих в ходе разработки программных комплексов для СРВ, необходимо решать как общие для многозадачных систем вопросы обеспечения логической корректности создаваемой системы (сохранение целостности информационных ресурсов, исключения возможности взаимного блокирования задач), так и специфические для СРВ вопросы динамической корректности (своевременности исполнения задач). Решение этих вопросов в конечном счете сводится к проверке корректности размещения в теле каждой из задач синхронизирующих операторов, обеспечивающих согласованное исполнение задач. Такая проверка корректности осуществляется статически. С этой целью строятся модели, отражающие размещение синхронизирующих операторов в задачах приложения. В настоящей статье предлагаются методы обработки таких моделей посредством построения специальных многодольных графов — графов зависимостей синхронизирующих операторов. Представляются две разновидности таких графов: а) графы связок, обеспечивающие проверку логической корректности многозадачных приложений, (корректность пересечений пар критических интервалов); и б) графы связок и критических интервалов, обеспечивающие проверку динамической корректности приложений для СРВ.Литература
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.
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.
Static Verification of Task Access to Shared Resources in Real-Time Systems
Abstract
Among issues which arise when developing software complexes for real-time systems (RTS) one should resolve common multi-task system issues of ensuring logical correctness of the system being created (preserving the integrity of informational resources, eliminating the possibility of mutual task blocking), as well as issues of ensuring dynamic correctness, specific for RTS (feasibility of the application tasks). In the long run, resolving these issues is reduced to checking the correctness of how synchronizing operators which ensure consistent execution of application tasks are scattered in the task bodies. In order to perform such checking statically, models which represent the scattering of synchronizing operators in application tasks are constructed. In this paper several methods of processing such models are proposed which are based on constructing special multi-partite graphs — graphs of synchronizing operator dependencies. Two varieties of such graphs are resented: a) graphs of bundles, which ensure verification of logical correctness of multi-task applications (correctness of intersections of critical interval pairs); and b) graphs of bundles and critical intervals, which ensure verification of dynamic correctness of RTS applications.
Опубликован
2017-05-31
Как цитировать
Никифоров, В. В., & Баранов, С. Н. (2017). Статическая проверка корректности разделения ресурсов в системах реального времени. Труды СПИИРАН, 3(52), 137-156. https://doi.org/10.15622/sp.52.7
Раздел
Методы управления и обработки информации
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
