УДК 004.4

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

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

Аннотация


Рассматриваются методы контроля доступа задач к разделяемым ресурсам в программных приложениях для систем реального времени. Приводится детальное представление двух процедур наследования приоритетов задач: непосредственной и транзитивной. Сформулированы достаточные условия, при которых применение непосредственной процедуры предотвращает инверсию приоритетов. Предложена модификация транзитивной процедуры снимающая известные ограничения на структуру приложения, накладываемые ее традиционной реализацией. Эта модификация, кроме того, обеспечивает динамическое обнаружение некорректных ситуаций типа взаимного блокирования задач с возможностью запланированной реакции на такие ситуации.

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


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

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

PDF

Литература


  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.


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

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


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

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




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