Национальный цифровой ресурс Руконт - межотраслевая электронная библиотека (ЭБС) на базе технологии Контекстум (всего произведений: 562678)
Консорциум Контекстум Информационная технология сбора цифрового контента
Уважаемые СТУДЕНТЫ и СОТРУДНИКИ ВУЗов, использующие нашу ЭБС. Рекомендуем использовать новую версию сайта.
Информационно-управляющие системы  / №1 2016

МОДЕЛЬ УПРАВЛЕНИЯ ДВУМЯ ПАРАЛЛЕЛЬНЫМИ FIFO-ОЧЕРЕДЯМИ, ДВИГАЮЩИМИСЯ ДРУГ ЗА ДРУГОМ В ОБЩЕЙ ПАМЯТИ (140,00 руб.)

0   0
Первый авторБарковский
АвторыСоколов А.В.
Страниц9
ID352906
АннотацияПостановка проблемы: при разработке многих аппаратных и программных приложений применяют структуру данных «FIFO-очередь». В различных сетевых устройствах и встроенных операционных системах применяется несколько FIFO-очередей, расположенных в общем пространстве памяти. Также существуют архитектуры многоядерных процессоров, где каждому ядру выделено две FIFO-очереди. Программные и аппаратные решения, применяемые для реализации описанных задач, должны увеличивать надежность (снижение доли потерянных при переполнении памяти элементов очередей) работы таких устройств. Цель: построение и анализ математической модели процесса работы с двумя FIFO-очередями, двигающимися друг за другом по кругу, в общей памяти, где на нечетном шаге происходят операции включения элементов в одну из очередей, а на четном шаге — исключения (возможно как последовательное, так и параллельное выполнение операций). Результаты: построены математическая и имитационная модели этого процесса для двух очередей и проведены численные эксперименты, основывающиеся на теоретических данных. Математическая модель представлена в виде случайного блуждания по целочисленной пирамиде с отражающими экранами. Предложен алгоритм нумерации состояний, установлен вид матрицы переходных состояний полученной регулярной цепи Маркова (доказаны соответствующие утверждения), разработаны алгоритм и программа вычисления средней доли потерянных при переполнении элементов очередей. Особенностью данного исследования является специфическое выполнение операций над очередями: включение и исключение элементов происходит в зависимости от шага (были сделаны поправки для сохранения качеств однородности и регулярности цепи) и создана возможность выполнять операции параллельно. Практическая значимость: предложенные модель, алгоритм и программный комплекс для анализа метода движения очередей -друг за другом» могут применяться при проектировании сетевых устройств, например маршрутизаторов, микросхем, реализующих работу с несколькими FIFO-очередями, и других программных и аппаратных устройств, где потери элементов являются допустимой, но нежелательной ситуацией. С помощью разработанной модели можно, при заданных вероятностных характеристиках очередей, выбрать лучший метод представления очередей, например, из двух методов — классического последовательного циклического метода или метода «Друг за другом».
УДК004.942
МОДЕЛЬ УПРАВЛЕНИЯ ДВУМЯ ПАРАЛЛЕЛЬНЫМИ FIFO-ОЧЕРЕДЯМИ, ДВИГАЮЩИМИСЯ ДРУГ ЗА ДРУГОМ В ОБЩЕЙ ПАМЯТИБарковский, Соколов // Информационно-управляющие системы .— 2016 .— №1 .— С. 15-23 .— doi: 10.15217/issn1684-8853.2016.1.65 .— URL: https://rucont.ru/efd/352906 (дата обращения: 12.06.2021)

Предпросмотр (выдержки из произведения)

При разработке сетевых устройств и встроенных операционных систем требуются эффективные алгоритмы работы с этими структурами данных — в приложениях управляющих потоками пакетов Internet, требования на время обработки пакетов маршрутизатором могут быть очень жесткие. <...> Нужно также отметить, что существуют архитектуры многоядерных процессоров без кэшпамяти. <...> Очереди и стеки реализованы циклически и раздельно, при переполнении происходит потеря элементов. <...> В наших зада№ 1, 2016 чах для хранения нескольких структур данных используется общая память. <...> В ряде случаев это позволяет снизить потери элементов при переполнении. <...> Модель последовательного, связанного и страничного способов представления нескольких FIFO-очередей в памяти одного уровня описаны в работах [5–8]. <...> Здесь предполагается, что на каждом шаге дискретного времени происходят некоторые операции со структурами данных (с заданными вероятностями). <...> Так как время выполнения операций — не случайная величина, а константа, фиксированным является и шаг времени. <...> Первоначально такие модели в виде случайного блуждания в треугольнике [9–14] были построены для решения задачи анализа процесса работы с двумя стеками, растущими навстречу друг другу, поставленной в работе [3]. <...> В этом способе на нечетном шаге допускаются только операции включения элементов в одну из n очередей, а на четном ИНФОРМАЦИОННОУПРАВЛЯЮЩИЕ СИСТЕМЫ 65 МОДЕЛИРОВАНИЕ СИСТЕМ И ПРОЦЕССОВ шаге — исключения из очередей (в первом и втором случае операции равновероятны). <...> При этом не рассматривался конкретный способ представления очередей в памяти, т. е. предполагалось, что очереди могут быть неограниченной длины, что на практике невыполнимо. <...> Авторами [15] предложена математическая модель и решена задача оптимального разбиения общей памяти для двух FIFO-очередей в случае их последовательного циклического представления. <...> Операции с очередями (с заданными вероятностями) выполнялись по вышеупомянутому <...>