Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,749

THE PROGRAM COMPLEX FOR SIMULATION MODELING OF THE TASK MANAGERS OF MULTIPROCESSOR SYSTEMS USING PRIORITY STOCHASTIC QUEUEING NETWORKS

Martyshkin A.I. 1 Biktashev R.A. 2 Vostokov N.G. 2
1 Federal State Budgetary Educational Institution of Penza State Technological University
2 Federal state budgetary educational institution of Higher Education Penza State University
The article presents more accurate mathematical models of Task Managers for multiprocessor and distributed computing systems. The developed models based on queuing networks with FIFO and priority disciplines. Presents description of a program complex for simulation distinguished classes of controllers as part of a computer system with the specified parameters. The proposed software complex is able to perform simulations and obtain the characteristics of the whole computer system, as well as its individual components. The main difference between the developed software complex from analogs is the possibility of modeling the queuing network consisting of systems with limited queue length before servicing device and priority queuing system that allows you to receive a wide range of interesting data. The complex is easy to work and does not require knowledge of the modeling language. Software complex can be used by developers of operating systems for their research and debugging during the development phase.
task manager
service discipline
multiprocessing system
program complex
queuing system
simulation
priority
1. Arkhangelsky A.Ya. Programming in Delphi 7. Beanom, 2003. 1152 p.
2. Biktashev R.A., Martyshkin A.I., Vostokov N.G. The software complex for determining the characteristics of Task Managers for multiprocessor systems with priority stochastic queuing networks // Fundamental research. 2013. no. 10 (p. 1). рр. 13–20.
3. Martyshkin A.I., Biktashev R.A., Vostokov N.G. Mathematical modeling of Task Managers for parallel processing systems based on open queuing systems // In the world of scientific discovery. 2013. no. 6.1 (42) (Mathematics. Mechanics. Informatics). рр. 81–101.
4. Mixalev V. Performance Test Results QNX Neutrino. // Modern Automation Technology: Scientific and Technical Journal. 2012. no. 2. рр. 82–88.
5. Certificate of state registration program for computer no. 2013611117. Program complex for calculate probabilistic-time characteristics of stochastic queuing networks. Application number 2012660617 from 05.12.2012. Registered in the register of the computer programs 09.01.2013.
6. Tanenbaum A. Modern Operating Systems. Third Edition. Prentice Hall PTR, 2010. 1120 p.

При разработке и совершенствовании вычислительных систем (ВС) необходимо проводить исследования ее характеристик. Для изучения характеристик ВС применяют программные модели, не являющиеся физическим устройством, а описанные данными и алгоритмами в памяти ЭВМ. Следовательно, их построение и изменение производится без финансовых затрат.

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

Постановка задачи

В работе [2] были рассмотрены аналитические ММ диспетчеров задач (ДЗ) со стратегией разделения во времени и разделения в пространстве для многопроцессорных и распределенных ОС, дано описание разработанного ПК для аналитического расчета характеристик указанных классов ДЗ в составе ВС по заданным параметрам. Здесь речь пойдет о реализации ПК для ИМ ДЗ с использованием приоритетных СеМО. Для оценки показателей производительности ДЗ авторами разработаны ММ n-процессорных систем с алгоритмами планирования процессов со стратегией разделения во времени (рис. 1, а) и разделения в пространстве (рис. 1, б). Подробно ММ описаны в [2, 3].

pic_23.tif 

Рис. 1. Схема модели n-процессорной системы с алгоритмами планирования процессов по стратегии разделения времени (а) и разделения пространства (б)

Распишем выражение для системы с общим ДЗ, полученное в [3], более подробно

739800.jpg (1)

где w1 – время ожидания в очереди перед процессорными узлами (ПУ); w2 – время ожидания ПУ перед занятием ДЗ; p10 – вероятность выхода заявки из системы; p12 – вероятность перехода задачи на обслуживание в ДЗ.

Время ответа в системе с ДЗ и общей очередью задач в МПС

739808.jpg (2)

где k – число квантов на выполнение одной заявки; tk – длительность одного кванта; δ – время, необходимое для перезагрузки кэш; ζ – время работы ДЗ; τ – время, необходимое для переключения контекста.

Время ожидания в очереди перед ПУ в системе с распределенными ДЗ и дисциплиной обслуживания FIFO

739815.jpg (3)

где λi – интенсивность входного потока в i-ю очередь; pji – вероятность перехода из очереди j в очередь i; Li – длина i-й очереди.

Время ответа в системе с распределенными ДЗ и дисциплиной обслуживания FIFO

739823.jpg (4)

где wi – время ожидания в i-й очереди.

Среднее время ожидания приоритетных задач в очередях сети в системе с распределенными ДЗ и относительными приоритетами

739832.jpg (5)

где αi – коэффициент передач в i-ю очередь, 739843.jpg – время ожидания задач с относительными приоритетами в i-й очереди

Время ответа системы с распределенными ДЗ и относительными приоритетами составит

739853.jpg (6)

где

739860.jpg 739872.jpg 

739879.jpg 

Среднее время ожидания приоритетных задач в очередях сети в системе с распределенными ДЗ и абсолютными приоритетами

739886.jpg (7)

где 739894.jpg – среднее время ожидания задач с абсолютными приоритетами в i-й очереди

Время ответа системы с распределенными ДЗ и абсолютными приоритетами составит

739902.jpg (8)

где

739909.jpg 739917.jpg 

739926.jpg 

Реализация программного комплекса

В работе предлагается ПК для визуального ИМ ВС, в частности многопроцессорных систем, реализованный в среде Delphi 7 [1].

ПК в своем составе содержит: ММ источника заявок, ММ очереди и ММ обслуживающего прибора.

ММ источника заявок используется для формирования потока транзакций в моделируемой сети по следующим законами распределения времени поступления:

1. Экспоненциальное.

739941.jpg 

где m – математическое ожидание Е[X].

2. Нормальное.

739952.jpg 

где s – среднеквадратичное отклонение; m – математическое ожидание Е[X].

3. Пуассона.

739959.jpg 

4. Равномерное.

739967.jpg 

Источник заявок исполнен в виде генератора случайных чисел (ГСЧ), выдающий не сами заявки, а временной интервал согласно с заданным законом распределения, в котором должна появиться заявка. Он включает следующие поля: наименование, интенсивность поступления заявок, дисперсия, тип распределения времени поступления заявок, уровень приоритета заявок.

ММ очереди используется для постановки заявок в очередь для их дальнейшей обработки в обслуживающем устройстве. Она содержит следующие поля: наименование, максимальная длина очереди, тип дисциплины выборки заявки из очереди (FIFO и LIFO без приоритета, FIFO и LIFO с приоритетами). Очередь представляется в виде списка, реализована проверка на ее конечность.

ММ обслуживающего прибора используется для имитации обработки или задержки транзакций в данном устройстве. Если устройство свободно, происходит автоматическая загрузка задания из предшествующей очереди. Если очередь пуста, устройство находится в режиме ожидания, пока не поступит новая транзакция. ММ обслуживающего прибора работает в соответствии с законами распределения времени задержки: экспоненциальным, нормальным, пуассоновским и равномерным. Она включает в себя следующие поля: наименование, среднее время обслуживания заявок, дисперсия, закон распределения, число каналов обслуживания.

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

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

Разрабатываемая ММ задается либо посредством ввода текста описания в соответствующее поле, либо с помощью визуального редактора, когда она представляется в виде схемы из условных обозначений устройств, очередей и генераторов на экране компьютера, на котором размещаются также возможные переходы заявок между элементами ММ. Максимальное количество элементов в ММ может быть выбрано исходя из объема ОЗУ ЭВМ, т.к. наряду со статически выделенной памятью под параметры элементов в процессе моделирования под каждую заявку динамически выделяется свободная память (по умолчанию максимальное число элементов в создаваемой ММ равно 450).

Перед расчетом ММ осуществляется проверка ее на корректность. Это необходимо, т.к. существует возможность построения ММ, в которой с течением времени будут накапливаться и простаивать заявки. При генерации заявки под нее выделяется память, а при ее уничтожении память освобождается. При неограниченном увеличении числа заявок в системе может происходить переполнение ОЗУ, что приводит к программному сбою [6].

После того как ММ создана и проверена на корректность, выполняется ее расчет. Сначала явным образом инициализируются генераторы заявок, что приводит к появлению в изначально пустом СБС следующих событий: постановки в очередь сгенерированных процедурой generator заявок и следующей генерации заявок в соответствии с параметрами генераторов. Далее управление предоставляется СБС: исполняется первая его строка и тут же удаляется. Моделирование прекращается, как только в СБС не будет ни одной строки.

В цикле моделирования вызываются процедуры generator, queue_in, queue_out, seize, release, terminator, использующие в качестве параметров номер устройства, указатель на заявку и т.д. Этим процедурам соответствуют действия с заявками: генерация, постановка в очередь, выход из очереди, постановка на обслуживание, конец обслуживания и удаление заявки. После окончания моделирования в текстовый файл на языке HTML выдается отчет.

На рис. 3, а, представлено окно разработанного ПК в режиме «Визуальный редактор». В верхнем меню можно выбрать основные режимы работы ПК: в меню Файл – создать новую ММ, загрузить ММ с диска, сохранить ее на диск, выход; в меню Расчет – изменить параметры моделирования, произвести расчет, произвести расчет по изменяемым параметрам (рис. 2, б); в меню Интерфейс – изменить представление ММ (ММ может быть представлена в виде текста или в виде схемы).

Редактирование ММ производится с помощью панели инструментов в нижней части окна ПК (рис. 2, а). Первая группа из трех кнопок служит для добавления элемента: генератора заявок, очереди или обслуживающего устройства. При добавлении элемента выводится окно, в котором необходимо ввести основные параметры элемента. Вторая группа инструментов редактирования содержит две кнопки: первая соединяет два элемента ММ, а вторая разъединяет. Чтобы соединить два элемента, например очередь и устройство обслуживания, нужно сначала щелкнуть на кнопку в панели инструментов, затем на нужную очередь, потом на устройство и после ввода вероятности такого перехода в диалоговом окне элементы будут соединены. Для разъединения элементов нужно щелкнуть левой кнопкой мыши на кнопке панели инструментов, затем на элементе, из которого происходит переход. Далее из выпадающего списка нужно выбрать переход, который нужно удалить. Следующая кнопка позволяет перемещать элементы по полю редактирования. Последняя кнопка панели инструментов редактирования нужна для удаления элементов.

pic_24.tif 

Рис. 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.