При разработке и совершенствовании вычислительных систем (ВС) необходимо проводить исследования ее характеристик. Для изучения характеристик ВС применяют программные модели, не являющиеся физическим устройством, а описанные данными и алгоритмами в памяти ЭВМ. Следовательно, их построение и изменение производится без финансовых затрат.
Целью работы является создание программного комплекса (ПК) для имитационного моделирования (ИМ) ВС, представляемых в виде сетей массового обслуживания (СеМО), и сбора статистики по узлам математической модели (ММ) и всей сети в целом. При помощи созданного ПК будет проводиться ИМ функций управления процессами и потоками ядра многопроцессорных (МПС) и распределенных операционных систем (ОС), в частности функций планирования и диспетчеризации задач.
Постановка задачи
В работе [2] были рассмотрены аналитические ММ диспетчеров задач (ДЗ) со стратегией разделения во времени и разделения в пространстве для многопроцессорных и распределенных ОС, дано описание разработанного ПК для аналитического расчета характеристик указанных классов ДЗ в составе ВС по заданным параметрам. Здесь речь пойдет о реализации ПК для ИМ ДЗ с использованием приоритетных СеМО. Для оценки показателей производительности ДЗ авторами разработаны ММ n-процессорных систем с алгоритмами планирования процессов со стратегией разделения во времени (рис. 1, а) и разделения в пространстве (рис. 1, б). Подробно ММ описаны в [2, 3].
Рис. 1. Схема модели n-процессорной системы с алгоритмами планирования процессов по стратегии разделения времени (а) и разделения пространства (б)
Распишем выражение для системы с общим ДЗ, полученное в [3], более подробно
(1)
где w1 – время ожидания в очереди перед процессорными узлами (ПУ); w2 – время ожидания ПУ перед занятием ДЗ; p10 – вероятность выхода заявки из системы; p12 – вероятность перехода задачи на обслуживание в ДЗ.
Время ответа в системе с ДЗ и общей очередью задач в МПС
(2)
где k – число квантов на выполнение одной заявки; tk – длительность одного кванта; δ – время, необходимое для перезагрузки кэш; ζ – время работы ДЗ; τ – время, необходимое для переключения контекста.
Время ожидания в очереди перед ПУ в системе с распределенными ДЗ и дисциплиной обслуживания FIFO
(3)
где λi – интенсивность входного потока в i-ю очередь; pji – вероятность перехода из очереди j в очередь i; Li – длина i-й очереди.
Время ответа в системе с распределенными ДЗ и дисциплиной обслуживания FIFO
(4)
где wi – время ожидания в i-й очереди.
Среднее время ожидания приоритетных задач в очередях сети в системе с распределенными ДЗ и относительными приоритетами
(5)
где αi – коэффициент передач в i-ю очередь, 
– время ожидания задач с относительными приоритетами в i-й очереди
Время ответа системы с распределенными ДЗ и относительными приоритетами составит
(6)
где
Среднее время ожидания приоритетных задач в очередях сети в системе с распределенными ДЗ и абсолютными приоритетами
(7)
где 
– среднее время ожидания задач с абсолютными приоритетами в i-й очереди
Время ответа системы с распределенными ДЗ и абсолютными приоритетами составит
(8)
где
Реализация программного комплекса
В работе предлагается ПК для визуального ИМ ВС, в частности многопроцессорных систем, реализованный в среде Delphi 7 [1].
ПК в своем составе содержит: ММ источника заявок, ММ очереди и ММ обслуживающего прибора.
ММ источника заявок используется для формирования потока транзакций в моделируемой сети по следующим законами распределения времени поступления:
1. Экспоненциальное.
где m – математическое ожидание Е[X].
2. Нормальное.
где s – среднеквадратичное отклонение; m – математическое ожидание Е[X].
3. Пуассона.
4. Равномерное.
Источник заявок исполнен в виде генератора случайных чисел (ГСЧ), выдающий не сами заявки, а временной интервал согласно с заданным законом распределения, в котором должна появиться заявка. Он включает следующие поля: наименование, интенсивность поступления заявок, дисперсия, тип распределения времени поступления заявок, уровень приоритета заявок.
ММ очереди используется для постановки заявок в очередь для их дальнейшей обработки в обслуживающем устройстве. Она содержит следующие поля: наименование, максимальная длина очереди, тип дисциплины выборки заявки из очереди (FIFO и LIFO без приоритета, FIFO и LIFO с приоритетами). Очередь представляется в виде списка, реализована проверка на ее конечность.
ММ обслуживающего прибора используется для имитации обработки или задержки транзакций в данном устройстве. Если устройство свободно, происходит автоматическая загрузка задания из предшествующей очереди. Если очередь пуста, устройство находится в режиме ожидания, пока не поступит новая транзакция. ММ обслуживающего прибора работает в соответствии с законами распределения времени задержки: экспоненциальным, нормальным, пуассоновским и равномерным. Она включает в себя следующие поля: наименование, среднее время обслуживания заявок, дисперсия, закон распределения, число каналов обслуживания.
Организацию перемещения заявок по созданной ММ можно реализовать следующим способом: перемещением заявок будут управлять процедуры источника, очереди, обслуживающего устройства и поглотителя. Заявка генерируется в процедуре источника заявок. Там же планируется ее переход к следующему блоку ММ. Информация о запланированном событии помещается в список будущих событий (СБС), указывается время, номер блока, указатель на заявку и тип действия. Эти записи отсортированы по времени и приоритету события. Каждый блок, через который проходит заявка, заносит те или иные данные в СБС, лишь в блоке-поглотителе происходит удаление заявки без планирования какого-либо действия на будущее. Процесс моделирования заключается в исполнении первой строки СБС с последующим ее удалением. При этом модельному времени присваивается значение времени в данной строке СБС. Когда список оказывается пуст, то моделирование прекращается и производится вывод рассчитанных данных.
Разработанный ПК имеет визуальный интерфейс, позволяющий наглядно отображать и изменять исследуемую ММ в процессе проведения экспериментов. Наряду с этим на диске ММ сохраняется в виде файла – полного описания ММ. Это предполагает универсальность использования ММ, возможность наращивания функциональных возможностей ПК без изменения формата представления ММ, расчет которой производится непрерывно до выполнения условий: генерации определенного количества заявок или достижения определенной величины модельного времени. Возможен расчет систем с отказами и без. Результатом является сформированный ПК html-файл, содержащий основные полученные характеристики в табличном виде. Также есть возможность получить подробное описание всего процесса моделирования в виде протокола.
Разрабатываемая ММ задается либо посредством ввода текста описания в соответствующее поле, либо с помощью визуального редактора, когда она представляется в виде схемы из условных обозначений устройств, очередей и генераторов на экране компьютера, на котором размещаются также возможные переходы заявок между элементами ММ. Максимальное количество элементов в ММ может быть выбрано исходя из объема ОЗУ ЭВМ, т.к. наряду со статически выделенной памятью под параметры элементов в процессе моделирования под каждую заявку динамически выделяется свободная память (по умолчанию максимальное число элементов в создаваемой ММ равно 450).
Перед расчетом ММ осуществляется проверка ее на корректность. Это необходимо, т.к. существует возможность построения ММ, в которой с течением времени будут накапливаться и простаивать заявки. При генерации заявки под нее выделяется память, а при ее уничтожении память освобождается. При неограниченном увеличении числа заявок в системе может происходить переполнение ОЗУ, что приводит к программному сбою [6].
После того как ММ создана и проверена на корректность, выполняется ее расчет. Сначала явным образом инициализируются генераторы заявок, что приводит к появлению в изначально пустом СБС следующих событий: постановки в очередь сгенерированных процедурой generator заявок и следующей генерации заявок в соответствии с параметрами генераторов. Далее управление предоставляется СБС: исполняется первая его строка и тут же удаляется. Моделирование прекращается, как только в СБС не будет ни одной строки.
В цикле моделирования вызываются процедуры generator, queue_in, queue_out, seize, release, terminator, использующие в качестве параметров номер устройства, указатель на заявку и т.д. Этим процедурам соответствуют действия с заявками: генерация, постановка в очередь, выход из очереди, постановка на обслуживание, конец обслуживания и удаление заявки. После окончания моделирования в текстовый файл на языке HTML выдается отчет.
На рис. 3, а, представлено окно разработанного ПК в режиме «Визуальный редактор». В верхнем меню можно выбрать основные режимы работы ПК: в меню Файл – создать новую ММ, загрузить ММ с диска, сохранить ее на диск, выход; в меню Расчет – изменить параметры моделирования, произвести расчет, произвести расчет по изменяемым параметрам (рис. 2, б); в меню Интерфейс – изменить представление ММ (ММ может быть представлена в виде текста или в виде схемы).
Редактирование ММ производится с помощью панели инструментов в нижней части окна ПК (рис. 2, а). Первая группа из трех кнопок служит для добавления элемента: генератора заявок, очереди или обслуживающего устройства. При добавлении элемента выводится окно, в котором необходимо ввести основные параметры элемента. Вторая группа инструментов редактирования содержит две кнопки: первая соединяет два элемента ММ, а вторая разъединяет. Чтобы соединить два элемента, например очередь и устройство обслуживания, нужно сначала щелкнуть на кнопку в панели инструментов, затем на нужную очередь, потом на устройство и после ввода вероятности такого перехода в диалоговом окне элементы будут соединены. Для разъединения элементов нужно щелкнуть левой кнопкой мыши на кнопке панели инструментов, затем на элементе, из которого происходит переход. Далее из выпадающего списка нужно выбрать переход, который нужно удалить. Следующая кнопка позволяет перемещать элементы по полю редактирования. Последняя кнопка панели инструментов редактирования нужна для удаления элементов.
Рис. 2. Окно разработанного ПК в режиме «Визуальный редактор» (а) и окно «Расчет по изменяемым параметрам» (б)
Тестирование и отладка ПК осуществлялись с помощью ПК аналитического моделирования стохастических СеМО [5]. Разработанный ПК применен для ИМ упомянутых выше ДЗ со стратегией разделения во времени и разделения в пространстве, имеющих следующие характеристики: интенсивность входного потока задач λ0 = 0,03; 0,06; 0,09 задач/мкс (низкая, средняя и высокая загрузка ЦП); время переключения контекста ДЗ τ = 9 мкс, что соответствует средним значениям времени переключения контекста ОС «мягкого» реального времени [4]; время обработки одной задачи ЦП ν = 10 мс. Размер общей очереди перед процессорами N = 128 задач; количество ЦП варьировалось от 4 до 50.
Результаты математического моделирования показали, что ДЗ с указанными параметрами имеют время ожидания обслуживания, не превышающее 13 мкс. Такая задержка соответветсвует многим существующим ОС реального времени, например, LinuxRT [4]. Адекватность имитационных моделей ДЗ подтверждается реальными данными, полученными на системе-прототипе [4]. Погрешность полученных ММ не превышает 10 %, что вполне приемлемо для оценки вариантов реализации ДЗ на системном этапе проектирования.
Выводы
Разработанный ПК рассчитан для моделирования ВС, атрибуты графического пакета, прост в обращении и не требует знаний языка моделирования. Основным отличием разработанного ПК является возможность имитационного моделирования СеМО, содержащих СМО с ограниченной длиной очереди, и СМО с приоритетами. ПК обеспечивает удобный интерфейс пользователя, а также наглядное представление результатов моделирования в виде таблиц.
Работа выполнена при финансовой поддержке стипендии Президента РФ на 2012-2014 гг. (СП-1172.2012.5).
Рецензенты:Гарькина И.А., д.т.н., профессор, зам. зав. кафедрой «Математика и математическое моделирование», ПГУАС, г. Пенза;
Камбург В.Г., д.т.н., профессор кафедры «Информационно-вычислительные системы», ПГУАС, г. Пенза.
Работа поступила в редакцию 18.11.2014.
Библиографическая ссылка
Мартышкин А.И., Бикташев Р.А., Востоков Н.Г. ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ ДИСПЕТЧЕРОВ ЗАДАЧ МНОГОПРОЦЕССОРНЫХ СИСТЕМ С ИСПОЛЬЗОВАНИЕМ ПРИОРИТЕТНЫХ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ // Фундаментальные исследования. – 2014. – № 11-10. – С. 2155-2159;URL: https://fundamental-research.ru/ru/article/view?id=35910 (дата обращения: 23.11.2024).