Транзитивное наследование приоритетов в многозадачных приложениях реального времени
Ключевые слова:
системы реального времени, модели многозадачных приложений, выполнимость задач, протоколы доступа к разделяемым ресурсамАннотация
Рассматриваются методы контроля доступа задач к разделяемым ресурсам в программных приложениях для систем реального времени. Приводится детальное представление двух процедур наследования приоритетов задач: непосредственной и транзитивной. Сформулированы достаточные условия, при которых применение непосредственной процедуры предотвращает инверсию приоритетов. Предложена модификация транзитивной процедуры снимающая известные ограничения на структуру приложения, накладываемые ее традиционной реализацией. Эта модификация, кроме того, обеспечивает динамическое обнаружение некорректных ситуаций типа взаимного блокирования задач с возможностью запланированной реакции на такие ситуации.Литература
1. Давиденко К.Я. Технология программирования АСУТП. Проектирование систем реального времени, параллельных и распределенных приложений // М.: Энергоатомиздат, 1985. 183 с.
2. Baker T. Multiprocessors EDF and Deadline Monotonic Schedulability Analysis // Proceedings of 24 IEEE Real-Time Systems Symposium. 2003. pp. 120–129.
3. Таненбаум Э. Современные операционные системы // СПб.: Питер. 2010. 1037 с.
4. Сорокин С.В. Системы реального времени: операционные системы // Современные технологии автоматизации. 1997. №2. С. 22–31.
5. 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.
6. Dhall S.K., Liu C.L. On a Real-Time Scheduling Problem // Operating Research. 1978. vol. 26. no. 1. pp. 127–140.
7. Никифоров В.В. Выполнимость приложений реального времени на многоядерных процессорах // Труды СПИИРАН. 2009. Вып. 8. С. 255–284.
8. Докучаев А.Н. К оценке эффективности механизмов диспетчеризации мультипроцессорных систем реального времени с учетом влияния длительных блокировок // Программная инженерия. 2012. №9. С. 2–7.
9. Anderson B. Global Static-Priority Preemptive Multiprocessor Scheduling with Utilization Bound 38% // Proceedings of the7th International Conference on Principles of Distributed Systems. Egypt. 2008. pp. 73–88.
10. Baker T.P., Cirinei M., Bertogna M. EDZL scheduling analysis // Real-Time Systems 2008. vol. 40. no. 3. pp. 264–289.
11. Baruah S.K. Fairness in Periodic Real-Time Scheduling Algorithms // Pro-ceedings of 16 IEEE Real-Time Symposium. 1995. pp. 200–209.
12. Cho H., Ravindran B., Jensen D. An Optimal Real-Time Scheduling Algorithm for Multiprocessors // Proceedings of the 27 IEEE Real-Time Symposium. 2006. pp. 101–110.
13. Liu J.W.S. Real-Time Systems // NJ: Prentice Hall. 2000. 590 p.
14. Laplante P.A. Real-Time Systems Design and Analysis // John Wiley & Sons, Inc. 2004. 530 p.
15. Данилов М.В. Методы планирования выполнения задач в системах ре-ального времени. // Программные продукты и системы. 2001. №4. С. 28–35.
16. Sha L., Rajkumar R., Lehoczky J.P. Priority Inheritance Protocols: An Ap-proach to Real-Time Synchronization // IEEE Transactions on Computers. 1990. vol. 20. no. 9. pp.1175–1185.
17. Никифоров В.В., Шкиртиль В.И. Спецификация средствами языка XML системы интерфейсов в приложениях реального времени. // Труды СПИИРАН. 2009. Вып 11. С.159–175.
18. Никифоров В.В., Шкиртиль В.И. Цепное блокирование взаимосвязанных задач в системах на многоядерных процессорах // Информационно-измерительные и управляющие системы. 2013. №9.
19. Dijkstra E.W. Hierarchical ordering of sequential processes // Acta Informatica. 1971. vol. 1. no. 2. pp. 115–138.
2. Baker T. Multiprocessors EDF and Deadline Monotonic Schedulability Analysis // Proceedings of 24 IEEE Real-Time Systems Symposium. 2003. pp. 120–129.
3. Таненбаум Э. Современные операционные системы // СПб.: Питер. 2010. 1037 с.
4. Сорокин С.В. Системы реального времени: операционные системы // Современные технологии автоматизации. 1997. №2. С. 22–31.
5. 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.
6. Dhall S.K., Liu C.L. On a Real-Time Scheduling Problem // Operating Research. 1978. vol. 26. no. 1. pp. 127–140.
7. Никифоров В.В. Выполнимость приложений реального времени на многоядерных процессорах // Труды СПИИРАН. 2009. Вып. 8. С. 255–284.
8. Докучаев А.Н. К оценке эффективности механизмов диспетчеризации мультипроцессорных систем реального времени с учетом влияния длительных блокировок // Программная инженерия. 2012. №9. С. 2–7.
9. Anderson B. Global Static-Priority Preemptive Multiprocessor Scheduling with Utilization Bound 38% // Proceedings of the7th International Conference on Principles of Distributed Systems. Egypt. 2008. pp. 73–88.
10. Baker T.P., Cirinei M., Bertogna M. EDZL scheduling analysis // Real-Time Systems 2008. vol. 40. no. 3. pp. 264–289.
11. Baruah S.K. Fairness in Periodic Real-Time Scheduling Algorithms // Pro-ceedings of 16 IEEE Real-Time Symposium. 1995. pp. 200–209.
12. Cho H., Ravindran B., Jensen D. An Optimal Real-Time Scheduling Algorithm for Multiprocessors // Proceedings of the 27 IEEE Real-Time Symposium. 2006. pp. 101–110.
13. Liu J.W.S. Real-Time Systems // NJ: Prentice Hall. 2000. 590 p.
14. Laplante P.A. Real-Time Systems Design and Analysis // John Wiley & Sons, Inc. 2004. 530 p.
15. Данилов М.В. Методы планирования выполнения задач в системах ре-ального времени. // Программные продукты и системы. 2001. №4. С. 28–35.
16. Sha L., Rajkumar R., Lehoczky J.P. Priority Inheritance Protocols: An Ap-proach to Real-Time Synchronization // IEEE Transactions on Computers. 1990. vol. 20. no. 9. pp.1175–1185.
17. Никифоров В.В., Шкиртиль В.И. Спецификация средствами языка XML системы интерфейсов в приложениях реального времени. // Труды СПИИРАН. 2009. Вып 11. С.159–175.
18. Никифоров В.В., Шкиртиль В.И. Цепное блокирование взаимосвязанных задач в системах на многоядерных процессорах // Информационно-измерительные и управляющие системы. 2013. №9.
19. Dijkstra E.W. Hierarchical ordering of sequential processes // Acta Informatica. 1971. vol. 1. no. 2. pp. 115–138.
Transitive Priority Inheritance in Real-Time Multi-Task Applications
Abstract
Control procedures for accessing shared resources in multi-task real-time software applications are analyzed. Two approaches to preventing priority inversion – basic and transitive procedures of priority inheritance – are analyzed in detail. To illustrate the considered notions and statements, concrete examples of multi-task application configurations are provided along with their execution diagrams under particular scenarios of system events, which demonstrate insufficient response time of tasks with sufficient computing resources and even mutual task clinches. The nomenclature of attributes to be included into task and resource descriptors for task management with the two priority inheritance procedures is proposed. The sufficient conditions for the basic procedure to prevent priority inheritance are formulated. The procedure of transitive priority inheritance is demonstrated to be capable of detecting a mutual task clinch in the application.
Опубликован
2015-11-25
Как цитировать
Баранов, С. Н., & Никифоров, В. В. (2015). Транзитивное наследование приоритетов в многозадачных приложениях реального времени. Труды СПИИРАН, 6(43), 114-134. https://doi.org/10.15622/sp.43.7
Раздел
Методы управления и обработки информации
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
