Аннотації

Метод визначення часових характеристик систем реального часу

Автор(и):
Юрович І. В., Зайцев В. Г.
Автор(и) (англ)
Yurovych I., Zaitsev V.
Дата публікації:

19.11.2024

Анотація (укр):

Системи реального часу широко розповсюджені і активно впроваджуються у передових розробках багатьох галузей, від медицини до космічної промисловості. Дослідження і моделювання систем реального часу є важливою задачею на етапі проєктування системи, адже воно дає змогу визначити, чи відповідає система, що моделюється, заданим часовим характеристикам, і відповідно визначити спроможність системи задовольнити часові вимоги. Адже успішність роботи систем реального часу залежить не лише від її логічної коректності, але і від часу, за який система генерує результат. Враховуючи, що є різні типи задач, наприклад синхронні і асинхронні, паралельні і послідовні, визначення їх часових характеристик на стадії проєктування є доволі складною проблемою. Також слід враховувати послідовність задач і час їх появи, адже є випадки, коли одна задача має залежність на результат виконання іншої задачі, відповідно час появи нової задачі в черзі планувальника залежить від часу завершення попередньої задачі. У попередніх роботах були проведені дослідження методів оцінки часових характеристик задач в системах реального часу шляхом аналізу даних, отриманих моделюванням розподілу процесорного часу між задачами згідно обраних алгоритмів планувальника з використанням моделі сіток Петрі в однопроцесорних та багатопроцесорних системах. Методи гарантували отримання часових характеристик задач при обранні конкретного типу процесора і планувальника, що є необхідним для початку технічного проєктування системи реального часу. Проте методи не враховували динамічну природу появи задач, що є невідʼємною складовою новітніх систем реального часу. У роботі запропоновано метод для визначення часових характеристик систем реального часу на етапі проєктування системи. Запропонований метод допомагає визначати час появи задачі, враховуючи різні типи задач та їх залежності. Визначені часові характеристики можуть бути використані у подальшому для моделювання роботи системи та визначення оптимального алгоритму планувальника задач.

Анотація (рус):

Анотація (англ):

Real-time systems are widely used and actively implemented in advanced developments across many industries, from medicine to aerospace. Research and modelling of real-time systems are crucial tasks at the design stage, as they help in the determination of whether the system being modelled meets the specified timing characteristics and, accordingly, assess the system's ability to satisfy timing requirements. After all, the success of a real-time system depends not only on their logical correctness but also on the time it takes for the system to generate a result. Considering the various types of tasks, such as synchronous and asynchronous, parallel and sequential, determining their timing characteristics at the design stage is quite a complex problem. It is also essential to consider the sequence of tasks and their arrival times since there are cases where one task depends on the result of another task, and thus, the arrival time of a new task to the scheduler's queue depends on the completion time of the previous task. Previous studies have investigated methods for evaluating the timing characteristics of tasks in real-time systems by analyzing data obtained from modeling the distribution of processor time among tasks according to selected scheduler algorithms using Petri net models in both single-processor and multi-processor systems. These methods ensured the acquisition of task timing characteristics when choosing a specific type of processor and scheduler, which is necessary for the initial technical design of a real-time system. However, the methods have not considered the dynamic nature of task yielding, which is an essential component of modern real-time systems. This paper proposes a method for determining the timing characteristics of real-time systems at the design stage. The proposed method helps to identify the arrival time of tasks, taking into account various types of tasks and their dependencies. The identified timing characteristics can subsequently be used for modelling the system's operation and determining the optimal task scheduling algorithm.

Література:

  1. Tindell K. W. An extendible approach for analyzing fixed priority hard real-time tasks / K. W. Tindell, A. Burns,
    A. J. Wellings. Real-Time Systems. 1994. № 6. С. 133–151.
  2. Motorola, Inc. MSCAN Block Guide [Електронний ресурс] / Motorola, Inc. 1998. URL: https://www.rose-hulman.edu/class/ee/hoover/ece331/9S12C128%20PDF%20Documents/9S12%20Microcontroller%20Docs/S12MSCANV2.pdf.
  3. Punnekkat S. Response time analysis under errors for CAN / S. Punnekkat, H. Hansson, C. Norstrom. IEEE Computer Society Press. 2000. С. 258–265.
  4. Nolte T. Minimizing CAN response-time analysis jitter by message manipulation / T. Nolte, H. Hansson, C. Norstrom. // IEEE real-time and embedded technology and applications symposium. – 2002. – С. 197–206.
  5. Nolte T. Probabilistic worst-case response-time analysis for the Controller Area Network / T. Nolte, H. Hansson, C. Norstrom. 9th IEEE real-time and embedded technology and applications symposium. 2003. С. 200–207.
  6. Broster I. Probabilistic analysis of CAN with Faults / I. Broster, A. Burns, G. Rodr ́ıguez-Navas. 23rd IEEE real-time systems symposium. 2002. С. 269–278.
  7. Broster I. Timing analysis of real-time communication under electro- magnetic interference / I. Broster, A. Burns, G. Rodr ́ıguez-Navas. Real-Time Systems. 2005. № 30. С. 55–81.
  8. Integrating reliability and timing analysis of CAN- based Systems / H.Hansson, T. Nolte, C. Norstrom, S. Punnekkat. IEEE Transactions on Industrial Electronics. 2002. № 49. С. 1240–1250.
  9. Broster I. An analysable bus-guardian for event-triggered communication / I. Broster, A. Burns. IEEE Computer Society Press. 2003. № 24. С. 410–419.
  10. Volcano – a revolution in on-board communica- tions [Електронний ресурс] / L.Casparsson, A. Rajnak, K. Tindell, P. Malmberg Volvo Technology Report. 1998. URL: https://theeshadow.com/files/volvo/can/Casparsson-Volcano%20in%20Volvo%20Tech%20Report%201998.pdf.  Lukkien. Springer Science + Business Media. 2007. № 35.
    С. 239–272.
  11. Audsley N. Optimal Priority Assignment And Feasibility Of Static Priority Tasks With Arbitrary Start Times [Електронний ресурс] / Audsley Department of Computer Science, University of York. 1991. URL: https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=59911c0872b2e598ebc4fe8eefdb75d39f0e3f01.
  12. Зайцев В. Г, Цибаєв Є. І. Оцінка часових характеристик у компʼютерних системах реального часу з використанням сіток Петрі. Управління розвитком складних систем. 2023. № 54. С. 48–62.
  13. Зайцев В. Г., Цибаєв Є. І. Модель оцінки часових характеристик у комп’ютерних системах реального часу з використанням сіток. Управління розвитком складних систем. 2019. No 40. С. 76 – 86; dx.doi.org\10.6084/m9.figshare.11969013.
  14. Зайцев В. Г., Цибаєв Є. І. Оцінка часових характеристик задач в багатопроцесорних системах реального часу з використанням сіток Петрі. Управління розвитком складних систем. 2020. № 42. С. 43 – 50.

References:

  1. Tindell, K. W., Burns, A., Wellings, A. J. (1994). An extendible approach for analyzing fixed priority hard real-time tasks. Real-Time Systems, 6, 133–151.
  2. Motorola, Inc. (1998). MSCAN Block Guide. URL: https://www.rose-hulman.edu/class/ee/hoover/ece331/9S12C128%20PDF%20Documents/9S12%20Microcontroller%20Docs/S12MSCANV2.pdf.
  3. Punnekkat, S., Hansson, H., Norstrom, C. (2000). Response time analysis under errors for CAN. IEEE Computer Society Press, 258–265.
  4. Nolte, T., Hansson, H., Norstrom, C. (2002). Minimizing CAN response-time analysis jitter by message manipulation. IEEE real-time and embedded technology and applications symposium, 197–206.
  5. Nolte, T., Hansson, H., Norstrom, C. (2003). Probabilistic worst-case response-time analysis for the Controller Area Network. 9th IEEE real-time and embedded technology and applications symposium, 200–207.
  6. Broster, I., Burns, A., Rodr ́ıguez-Navas, G. (2002). Probabilistic analysis of CAN with Faults. 23rd IEEE real-time systems symposium, PP. 269–278.
  7. Broster, I., Burns, A., Rodr ́ıguez-Navas, G. (2005). Timing analysis of real-time communication under electromagnetic interference. Real-Time Systems, 30, 55–81.
  8. Hansson, H., Nolte, T., Norstrom, C., Punnekkat, S. (2002). Integrating reliability and timing analysis of CAN-based Systems. IEEE Transactions on Industrial Electronics, 49, 1240–1250.
  9. Broster, I., Burns, A. (2003). An analysable bus-guardian for event-triggered communication. IEEE Computer Society Press, 24, 410–419.
  10. Casparsson, L., Rajnak, A., Tindell, K., Malmberg, P. (1998). Volcano – a revolution in on-board communications. URL: https://theeshadow.com/files/volvo/can/Casparsson-Volcano%20in%20Volvo%20Tech%20Report%201998.pdf.
  11. Davis, R., Burns, A., Bril, R., Lukkien, J. (2007). Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised. Springer Science + Business Media, 35, 239–272.
  12. Audsley, N. (1991). Optimal Priority Assignment And Feasibility Of Static Priority Tasks With Arbitrary Start Times. URL: https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=59911c0872b2e598ebc4fe8eefdb75d39f0e3f01.
  13. Zaitsev, V. G., Tsybaev, E. I. (2023). Estimation of timing characteristics in real-time computer systems using petri nets. Management of development of complex systems, 40, 48–62.
  14. Zaitsev, V. G. Tsybaev, E. I. (2019). A model for estimating time characteristics in real-time computer systems using Petri nets. Management of development of complex systems, 40, 76–86.
  15. Zaitsev, V. G. Tsybaev, E. I. (2020). Evaluation of time characteristics of problems in multiprocessor real-time systems using petri networks. Management of development of complex systems, 42, 43–50.