Статическая проверка корректности разделения ресурсов в системах реального времени
Ключевые слова:
системы реального времени, модели многозадачных приложений, выполнимость задач, протоколы доступа, разделяемые ресурсыАннотация
В ряду вопросов, возникающих в ходе разработки программных комплексов для СРВ, необходимо решать как общие для многозадачных систем вопросы обеспечения логической корректности создаваемой системы (сохранение целостности информационных ресурсов, исключения возможности взаимного блокирования задач), так и специфические для СРВ вопросы динамической корректности (своевременности исполнения задач). Решение этих вопросов в конечном счете сводится к проверке корректности размещения в теле каждой из задач синхронизирующих операторов, обеспечивающих согласованное исполнение задач. Такая проверка корректности осуществляется статически. С этой целью строятся модели, отражающие размещение синхронизирующих операторов в задачах приложения. В настоящей статье предлагаются методы обработки таких моделей посредством построения специальных многодольных графов — графов зависимостей синхронизирующих операторов. Представляются две разновидности таких графов: а) графы связок, обеспечивающие проверку логической корректности многозадачных приложений, (корректность пересечений пар критических интервалов); и б) графы связок и критических интервалов, обеспечивающие проверку динамической корректности приложений для СРВ.Литература
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.
Опубликован
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).
