Оптимальное управление двумя параллельными FIFO-очередями на бесконечном времени


https://doi.org/10.15217/issn1684-8853.2015.5.65

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


Аннотация

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

Об авторах

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


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


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

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

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

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

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

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

6. 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. 325340.

7. Louchard G., Schott R. Probabilistic Analysis of Some Distributed Algorithms // Lecture Notes in Computer Science. 1990. Vol. 431. P. 239-253.

8. 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.

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

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

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

12. 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.

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

14. Драц А. В., Соколов А. В. Математический анализ процесса работы с M FIFO-очередями // Стохастическая оптимизация в информатике. 2012. Т. 8. № 2. С. 75-82.

15. Kemeny J. G., Snell J. L. Finite Markov Chains. - Springer, 1983. - 226 p.


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

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

For citation: Barkovsky E.A., Sokolov A.V. Optimal Control of Two Parallel FIFO Queues on an Infinite Time. Information and Control Systems. 2015;(5):65-71. (In Russ.) https://doi.org/10.15217/issn1684-8853.2015.5.65

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


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


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