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