Математическая модель оптимального управления настраиваемой очередью из двух последовательных циклических FIFO-очередей в общей памяти


https://doi.org/0.15217/issnl684-8853.2017.4.44

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


Аннотация

Введение: при разработке многих аппаратных и программных приложений применяют структуру данных «настраиваемая очередь» (Custom Queuing). В различных сетевых устройствах и встроенных операционных системах настраиваемая очередь представлена в виде нескольких последовательных циклических FIFO-очередей, расположенных в общем пространстве памяти. Цель: построить и проанализировать математическую модель процесса работы с настраиваемой очередью, представленной в виде двух последовательных циклических FIFO-очередей, в целях повышения стабильности работы системы. Результаты: построена математическая модель процесса работы с настраиваемой очередью, в которой на каждом шаге дискретного времени происходят операции включения и исключения элементов в одну из очередей. Математическая модель представлена в виде случайного блуждания по двухмерной целочисленной решетке, для которой строится соответствующая регулярная однородная цепь Маркова. Критерием оптимальности является минимальная средняя доля потерянных при переполнении элементов очередей. Проведены численные эксперименты, основывающиеся на теоретических данных. Практическая значимость: с помощью разработанной модели можно найти оптимальное назначение весов каждой FIFO-очереди для повышения стабильности работы системы. Предложенные модели, алгоритмы и разработанный программный комплекс могутприменяться при проектировании сетевыхустройств, например маршрутизаторов, где потери пакетов являются допустимой, но нежелательной ситуацией. Назначая веса для очередей оптимально, мы теряем меньше пакетов, и, как следствие, данные доставляются быстрее.

Об авторах

А. М. Сазонов
Петрозаводский государственный университет
Россия


А. В. Соколов
Институт прикладных математических исследований Карельского научного центра Российской академии наук
Россия


Список литературы

1. Sedgewick R. Algorithms in C++. Parts 1-4. - Addison-Wesley Professional, 1998. - 752 p.

2. Олифер В. Г., Олифер Н. А. Компьютерные сети. Принципы, технологии, протоколы. - СПб.: Питер, 2010. - 944 с.

3. Bollapragada V., Murphy C., White R. Inside Cisco IOS Software Architecture. - Cisco Press, 2000. - 240 p.

4. Knuth D. The Art of Computer Programming. Vol. 1. - Addison-Wesley Professional, 1997. - 672 p.

5. Калачев А. В. Многоядерные процессоры. - М.: БИНОМ, 2014. - 247 с.

6. Соколов А. В. Математические модели и алгоритмы оптимального управления динамическими структурами данных. - Петрозаводск: ПетрГУ, 2002. - 216 с.

7. Аксенова Е. А., Драц А. В., Соколов А. В. Оптимальное управление n FIFO-очередями на бесконечном времени // Информационно-управляющие системы. 2009. № 6. С. 46-54.

8. Aksenova E. A., Sokolov A. V. The Optimal Implementation of Two FIFO-Queues in Single-Level Memory // Applied Mathematics. 2011. Vol. 2. P. 1297-1302.

9. Sokolov A. V., Drac A. V. The Linked List Representation of n LIFO-Stacks and/or FIFO-Queues in the Single-Level Memory // Information Processing Letters. 2013. Vol. 13. P. 832-835.

10. Соколов А. В., Сазонов А. М., Морозов Е. В., Некрасова Р. С., Разумчик Р. В. Математические модели и алгоритмы оптимального управления FIFO-очередями в общей памяти// Тр. КарНЦ РАН. Сер. Математическое моделирование и информационные технологии. 2016. № 8. C. 98-107. doi:10.17076/mat396

11. Соколов А. В., Барковский Е. А. Оптимальное управление двумя параллельными FIFO-очередями на бесконечном времени // Информационноуправляющие системы. 2015. № 5. С. 65-71. doi:10.15217/ issn1684-8853.2015.5.65

12. Sokolov A. V., Barkovsky E. A. Some Problems of Optimal Control of Two Parallel FIFO-queues // International Conference on Numerical Analysis and Applied Mathematics: Proc. 12th Intern. Conf., Rhodes, 18-22 Sept. 2014. AIP Publishing, 2015. Vol. 1648. P. 520003.

13. Драц А. В., Соколов А. В. Оптимальное управление приоритетной очередью в памяти одного уровня// Тр. КарНЦ РАН. 2011. № 2. С. 103-110.

14. Барковский Е. А. Оптимальное управление двумя очередями, работающими по принципу настраиваемых очередей// Стохастическая оптимизация в информатике. 2016. Т. 12. Вып. 2. С. 1-14. http:// www.math.spbu.ru/user/gran/optstoch.htm

15. Соколов А. В. О распределении памяти для двух стеков // Автоматизация эксперимента и обработки данных. - Петрозаводск: Изд-во Карельского филиала АН СССР, 1980. - С. 65-71.

16. Yao A. C. An Analysis of a Memory Allocation Scheme for Implementing Stacks // SIAM Journal on Computing. 1981. Vol. 10. P. 398-403.

17. Flajolet P. The Evolution of Two Stacks in Bounded Space and Random Walks in a Triangle // Lecture Notes in Computer Science. 1986. Vol. 223. P. 325-340.

18. Louchard G., Schott R., Tolley M., Zimmermann P. Random Walks, Heat Equation and Distributed Algorithms // Journal of Computational and Applied Mathematics. 1994. N 53. P. 243-274.

19. Maier R. S. Colliding Stacks: A Large Deviations Analysis // Random Structures and Algorithms. 1991. N 2. P. 379-421.

20. Ozel O., Uysal-Biyikoglu E., and Girici T. Optimal Buffer Partitioning on a Multiuser Wireless Link// Proc. of Information Theory and Applications Workshop, UCSD, San Diego, CA, Jan. 31-Feb. 5, 2010. doi:10.1109/ITA.2010.5454079

21. Гайдамака Ю. В., Самуйлов А. К. Анализ стратегий заполнения буфера оборудования пользователя при предоставлении услуги потокового видео в одноранговой сети // T-Comm - Телекоммуникации и Транспорт. 2013. № 11. C. 77-81.

22. Gaidamaka Yu., Shorgin S., Samouylov K., Etezov Sh. Polling System with Threshold Control for Modeling of SIP Server under Overload / J. Swiatek et al. (Eds.) // Advances in Systems Science, AISC 240. 2014. P. 97107. doi:10.1007/978-3-319-01857-7_10

23. Morozov E., Nekrasova R., Potakhina L., Tikhonenko O. Asymptotic Analysis of Queueing Systems with Finite Buffer Space // Communications in Computer and Information Science: Proc. 21st Intern. Conf., CN 2014, Brunow, Poland, June 23-27, 2014. Vol. 431. P. 223-232.

24. Кемени Дж., Снелл Дж. Конечные цепи Маркова. - М.: Наука, 1970. - 272 с.

25. Танненбаум Э., Уэзеролл В. Компьютерные сети. 5-е изд. - СПб.: Питер, 2012. - 960 с.


Дополнительные файлы

Для цитирования: Сазонов А.М., Соколов А.В. Математическая модель оптимального управления настраиваемой очередью из двух последовательных циклических FIFO-очередей в общей памяти. Информационно-управляющие системы. 2017;89(4):44-50. https://doi.org/0.15217/issnl684-8853.2017.4.44

For citation: Sazonov A.M., Sokolov A.V. Mathematical Model of Optimal Memory Management for Custom Queue of Two Consecutive Cyclic FIFOs in Shared Memory. Information and Control Systems. 2017;89(4):44-50. (In Russ.) https://doi.org/0.15217/issnl684-8853.2017.4.44

Просмотров: 83


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1684-8853 (Print)
ISSN 2541-8610 (Online)