Моделирование компьютерных систем с FIFO-дисциплиной обработки прерываний
https://doi.org/10.22405/2226-8383-2019-20-2-499-511
Аннотация
Дисциплина FIFO (First In First Out) обработки прерываний достаточно широко используется в ЭВМ Фон Неймановского типа, применяемых в информационных и цифровых управляющих системах. Цель реализации подобного режима работы — оптимизация времени доступа к данным — достижима только при наличии адекватной модели, описывающей систему. Аналитическая модель построена с использованием фундаментального математического аппарата сетей Петри-Маркова. Первичная Петри-Марковская модель разделена на иерархические уровни, соответствующие количеству заявок на обработку прерываний в очереди. Показано, что с текущего уровня возможно переключение, как на предыдущий, так и на последующий уровни прерываний. Получены зависимости для определения времени пребывания на текущем уровне и вероятностей переключения на сопряженные уровни. Предложен метод преобразования Петри-Марковской модели в полумарковский процесс. Показано, что структура подобного полумарковского процесса представляет собой бинарное дерево. Получены зависимости для определения временных и вероятностных характеристик блужданий по бинарному дереву.
Список литературы
1. Tzafestas S.G. Introduction to Mobile Robot Control. Elsevier, 2014. 750 p.
2. Landau I.D., Zito G. Digital Control Systems, Design, Identification and Implementation. Springer, 2006. 484 p.
3. Åström J., Wittenmark B., Computer Controlled Systems: Theory and Design. Tsinghua University Press. Prentice Hall, 2002. 557 p.
4. Regehr J. Duongsaa U. 2005. Preventing interrupt overload // Proceedings of the Conference on Languages, Compilers, and Tools for Embedded Systems. 2005. - Pp. 50 – 58.
5. 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.
6. 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.
7. 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.
8. 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.
9. Howard R. A. Dynamic Probabilistic Systems. Vol. 1: Markov Models. Vol. II: Semi-Markov and Decision Processes. Courier Corporation, 2012.
10. Janssen J., Manca R. Applied Semi-Markov processes. Springer US, 2006. 310 p.
11. 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.
12. Heymann M. Concurrency and Discrete Event Control // IEEE Control Syst. Mag. 1990. Vol. 10. Pp. 103 – 112.
13. Valk R. Concurrency in Communicating Object Petri Nets // Concurr. object-oriented Program. Petri nets. 2001. Pp. 164 – 195.
14. 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.
15. 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.
16. 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.
17. 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.
18. 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.
Рецензия
Для цитирования:
Ларкин Е.В., Привалов А.Н. Моделирование компьютерных систем с FIFO-дисциплиной обработки прерываний. Чебышевский сборник. 2019;20(2):499-511. https://doi.org/10.22405/2226-8383-2019-20-2-499-511
For citation:
Larkin E.V., Privalov A.N. Simulation of computer systems with FIFO-discipline interrupt handling. Chebyshevskii Sbornik. 2019;20(2):499-511. (In Russ.) https://doi.org/10.22405/2226-8383-2019-20-2-499-511
Просмотров: 327
Послать статью по эл. почте 