chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2019-20-2-499-511cheb-657Research ArticleИстория математики и приложенийСomputer scienceМоделирование компьютерных систем с FIFO-дисциплиной обработки прерыванийSimulation of computer systems with FIFO-discipline interrupt handlingЛаркинЕвгений ВасильевичLarkinEugene Vasilyevichelarkin@mail.ruПриваловАлександр НиколаевичPrivalovAlexander Nikolaevichprivalov.61@mail.ru201928012020202499511Copyright © Ларкин Е.В., Привалов А.Н., 20192019Ларкин Е.В., Привалов А.Н.Larkin E.V., Privalov A.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/657

Дисциплина FIFO (First In First Out) обработки прерываний достаточно широко используется в ЭВМ Фон Неймановского типа, применяемых в информационных и цифровых управляющих системах. Цель реализации подобного режима работы — оптимизация времени доступа к данным — достижима только при наличии адекватной модели, описывающей систему. Аналитическая модель построена с использованием фундаментального математического аппарата сетей Петри-Маркова. Первичная Петри-Марковская модель разделена на иерархические уровни, соответствующие количеству заявок на обработку прерываний в очереди. Показано, что с текущего уровня возможно переключение, как на предыдущий, так и на последующий уровни прерываний. Получены зависимости для определения времени пребывания на текущем уровне и вероятностей переключения на сопряженные уровни. Предложен метод преобразования Петри-Марковской модели в полумарковский процесс. Показано, что структура подобного полумарковского процесса представляет собой бинарное дерево. Получены зависимости для определения временных и вероятностных характеристик блужданий по бинарному дереву.

The FIFO (First In First Out) discipline of interrupt processing is widely used in Von Neumann type computers of informational and digital control systems. The goal of implementing such modes of operation - optimization time to data access - is achievable only when there is an adequate model, which describes data processing in the system. The analytical model is worked out with use the fundamental mathematical apparatus of Petri-Markov nets. The initial Petri-Markov model is divided into hierarchical levels in accordance with the number of interrupts in queue for processing. It is shown, that from the current level it is possible to switch both to the previous and to the next interrupt. Dependencies for determine the time of residence on the current level, and the probabilities of switching to conjugate levels are obtained. The method of Petri-Markov model transformation into the semi-Markov process is proposed. It is shown, that semi-Markov process obtained has the binary tree structure. Dependences for determining the time and probabilistic characteristics of wandering through a binary tree, are obtained.

ReferencesTzafestas S.G. Introduction to Mobile Robot Control. Elsevier, 2014. 750 p.Tzafestas S.G. Introduction to Mobile Robot Control. Elsevier, 2014. 750 p.Landau I.D., Zito G. Digital Control Systems, Design, Identification and Implementation. Springer, 2006. 484 p.Landau I.D., Zito G. Digital Control Systems, Design, Identification and Implementation. Springer, 2006. 484 p.Åström J., Wittenmark B., Computer Controlled Systems: Theory and Design. Tsinghua University Press. Prentice Hall, 2002. 557 p.Åström J., Wittenmark B., Computer Controlled Systems: Theory and Design. Tsinghua University Press. Prentice Hall, 2002. 557 p.Regehr J. Duongsaa U. 2005. Preventing interrupt overload // Proceedings of the Conference on Languages, Compilers, and Tools for Embedded Systems. 2005. - Pp. 50 – 58.Regehr J. Duongsaa U. 2005. Preventing interrupt overload // Proceedings of the Conference on Languages, Compilers, and Tools for Embedded Systems. 2005. - Pp. 50 – 58.Czerwinski, M., Cutrell, E., Horvitz, E. Instant messaging and interruption: Influence of task type on performance // Proceedings of OZCHI. Sydney, Australia - 2000, - https://interruptions.net/literature/Czerwinski-OZCHI00.pdf.Czerwinski, M., Cutrell, E., Horvitz, E. Instant messaging and interruption: Influence of task type on performance // Proceedings of OZCHI. Sydney, Australia - 2000, - https://interruptions.net/literature/Czerwinski-OZCHI00.pdf.Bielecki T.R., Jakubowski J., Niewкgiowski M. Conditional Markov chains: Properties, construction and structured dependence // Stochastic Processes and their Applications. V. 127, N. 4. 2017. Pp. 1125–1170.Bielecki T.R., Jakubowski J., Niewкgiowski M. Conditional Markov chains: Properties, construction and structured dependence // Stochastic Processes and their Applications. V. 127, N. 4. 2017. Pp. 1125–1170.Ching W.K., Huang X., Ng M.K., Siu T.K. Markov Chains: Models, Algorithms and Applications / International Series in Operations Research & Management Science. V. 189. Springer Science + Business Media NY, 2013. 241 p.Ching W.K., Huang X., Ng M.K., Siu T.K. Markov Chains: Models, Algorithms and Applications / International Series in Operations Research & Management Science. V. 189. Springer Science + Business Media NY, 2013. 241 p.Markov A.A. Extension of the law of large numbers to dependent quantities // Izvestiia Fiz.- Matem. Obsch. Kazan Univ., (2-nd Ser.), - 1906, - Pp. 135–156.Markov A.A. Extension of the law of large numbers to dependent quantities // Izvestiia Fiz.- Matem. Obsch. Kazan Univ., (2-nd Ser.), - 1906, - Pp. 135–156.Howard R. A. Dynamic Probabilistic Systems. Vol. 1: Markov Models. Vol. II: Semi-Markov and Decision Processes. Courier Corporation, 2012.Howard R. A. Dynamic Probabilistic Systems. Vol. 1: Markov Models. Vol. II: Semi-Markov and Decision Processes. Courier Corporation, 2012.Janssen J., Manca R. Applied Semi-Markov processes. Springer US, 2006. 310 p.Janssen J., Manca R. Applied Semi-Markov processes. Springer US, 2006. 310 p.Larkin E.V., Malikov A.A., Ivutin A.N. Petri-Markov model of fault-tolerant computer systems // 4th International Conference on Control, Decision and Information Technologies (CoDIT). – 5-7 April 2017, Barcelona, Spain – IEEE, 2017. – P. 416-420.Larkin E.V., Malikov A.A., Ivutin A.N. Petri-Markov model of fault-tolerant computer systems // 4th International Conference on Control, Decision and Information Technologies (CoDIT). – 5-7 April 2017, Barcelona, Spain – IEEE, 2017. – P. 416-420.Heymann M. Concurrency and Discrete Event Control // IEEE Control Syst. Mag. 1990. Vol. 10. Pp. 103 – 112.Heymann M. Concurrency and Discrete Event Control // IEEE Control Syst. Mag. 1990. Vol. 10. Pp. 103 – 112.Valk R. Concurrency in Communicating Object Petri Nets // Concurr. object-oriented Program. Petri nets. 2001. Pp. 164 – 195.Valk R. Concurrency in Communicating Object Petri Nets // Concurr. object-oriented Program. Petri nets. 2001. Pp. 164 – 195.Ivutin A.N, Larkin E.V. Simulation of Concurrent Games // Bulletin of the South Ural State University. Series: Mathematical Modeling, Programming and Computer Software. – Chelyabinsk, 2015. – Vol. 8, № 2. – Pp. 43 – 54.Ivutin A.N, Larkin E.V. Simulation of Concurrent Games // Bulletin of the South Ural State University. Series: Mathematical Modeling, Programming and Computer Software. – Chelyabinsk, 2015. – Vol. 8, № 2. – Pp. 43 - 54.Larkin E.V., Ivutin A.N., Kotov V.V., Privalov A.N. Simulation of Relay-races // Bulletin of the South Ural State University. Mathematical Modelling, Programming & Computer Software. - 2016. - Vol. 9. - No 4. - Pp. 117 - 128.Larkin E.V., Ivutin A.N., Kotov V.V., Privalov A.N. Simulation of Relay-races // Bulletin of the South Ural State University. Mathematical Modelling, Programming & Computer Software. - 2016. - Vol. 9. - No 4. - Pp. 117 – 128.Larkin E.V., Ivutin A.N. Estimation of Latency in Embedded Real-Time Systems // 3-rd Meditteranean Conference on Embedded Computing (MECO-2014). - 2014. - Budva, Montenegro, 2014. - Pp. 236 - 239.Larkin E.V., Ivutin A.N. Estimation of Latency in Embedded Real-Time Systems // 3-rd Meditteranean Conference on Embedded Computing (MECO-2014). - 2014. - Budva, Montenegro, 2014. - Pp. 236 - 239.Larkin E.V., Ivutin A.N., Troshina A. Model of interruptions in Swarm unit // Advances in swarm intelligence. Proceedings of 8-th Internati0onal conference ICSI 2017. Fukuoka, Japan. 2017. Part 1. Pp. 50–59.Larkin E.V., Ivutin A.N., Troshina A. Model of interruptions in Swarm unit // Advances in swarm intelligence. Proceedings of 8-th Internati0onal conference ICSI 2017. Fukuoka, Japan. 2017. Part 1. Pp. 50 - 59.Bienstock D., Graph searching, path-width, tree-width and related problems (a survey) // Reliability of Computer and Communication Networks, New Brunswick, NJ, 1989, in: DIMACS Ser. Discrete Math. Theoret. Comput. Sci. Vol. 5, Amer. Math. Soc., Providence, RI, 1991. Pp. 33–49.Bienstock D., Graph searching, path-width, tree-width and related problems (a survey) // Reliability of Computer and Communication Networks, New Brunswick, NJ, 1989, in: DIMACS Ser. Discrete Math. Theoret. Comput. Sci. Vol. 5, Amer. Math. Soc., Providence, RI, 1991. Pp. 33–49.

The authors declare that there are no conflicts of interest present.