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


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

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


Аннотация

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

Об авторах

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


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


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

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

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

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

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

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

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

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

8. Соколов А. В., Драц А. В. Моделирование некоторых методов представления n FIFO-очередей в памяти одного уровня // Эвристические алгоритмы и распределенные вычисления. 2014. Т. 1. № 1. С. 40-52.

9. Соколов А. В. О распределении памяти для двух стеков // Автоматизация эксперимента и обработки данных. 1980. С. 65-71.

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

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

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

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

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

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

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

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

18. Kemeny J. G., Snell J. L. Finite Markov Chains. - Van Nostrand, 1969. - 210 p.

19. Tanenbaum A. S., Wetherall D. J. Computer Networks. - Pearson Education, 2011. - 933 p.


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

Для цитирования: Барковский Е.А., Соколов А.В. Модель управления двумя параллельными FIFO-очередями, двигающимися друг за другом в общей памяти. Информационно-управляющие системы. 2016;(1):65-73. https://doi.org/10.15217/issn1684-8853.2016.1.65

For citation: Barkovsky E.A., Sokolov A.V. Management Model for Two Parallel FIFO Queues Moving One after Another in Shared Memor. Information and Control Systems. 2016;(1):65-73. (In Russ.) https://doi.org/10.15217/issn1684-8853.2016.1.65

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


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


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