автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математическое моделирование диспетчеров задач в многопроцессорных вычислительных системах на основе стохастических сетей массового обслуживания

На правах рукописи

МАРТЫШКИН Алексей Иванович

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ДИСПЕТЧЕРОВ ЗАДАЧ В МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ НА ОСНОВЕ СТОХАСТИЧЕСКИХ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ

Специальность 05.13.18 - математическое моделирование, численные методы и

комплексы программ

Автореферат

диссертации на соискание ученой степени кандидата технических наук

5 ДЕК 2013

005541975

ПЕНЗА - 2013

005541975

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Пензенский государственный технологический университет» на кафедре «Вычислительные машины и системы».

Защита диссертации состоится 18 декабря 2013 года в 16 часов, на заседании диссертационного совета Д 212.337.01 на базе ФГБОУ ВПО «Пензенский государственный технологический университет» по адресу: 440039, г. Пенза, пр. Байдукова / ул. Гагарина, д. 1а/11, корпус 1, конференц-зал.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Пензенский государственный технологический университет».

Автореферат разослан 15 ноября 2013 года

Ученый секретарь

Научный руководитель

кандидат технических наук, доцент Бикташев Равиль Айнулович. Михайлов Петр Григорьевич,

доктор технических наук, профессор, ФГБОУ ВПО «Пензенский государственный технологический университет», профессор кафедры «Информационные технологии и системы»; Зинкин Сергей Александрович, доктор технических наук, профессор, ФГБОУ ВПО «Пензенский государственный университет», профессор кафедры «Вычислительная техника». ОАО «Научно-производственное предприятие «Рубин», г. Пенза.

Официальные оппоненты:

Ведущая организация -

диссертационного совета

Чулков Валерий Александрович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Для обеспечения работы современных вычислительных систем в режиме реального времени все более широкое применение находят многопроцессорные и многоядерные архитектуры, создание которых сопряжено с решением задач управления процессами и ресурсами путем диспетчеризации. Эффективность выполнения функций диспетчеров задач определяется скоростью переключения процессов. Планировщик и диспетчер в многопроцессорной системе вызываются приложениями гораздо чаще, чем в однопроцессорной системе, поэтому доступ к этим программным ресурсам порождает конфликтные ситуации. Особенно это проявляется в многоядерных системах на кристалле, имеющих потенциально высокую производительность. Традиционная программная реализация диспетчеров задач часто не обеспечивает требуемой производительности системы. Поэтому при проектировании ядра операционной системы необходимо производить выбор наиболее эффективных технических средств его реализации.

Задача диспетчеризации процессов в многопроцессорной системе является двумерной. Одновременно с функцией назначения задачи выполняется функция выделения целевого процессора, что приводит к дополнительным издержкам времени. Кроме того, в диспетчере задач с разделением во времени возникает процесс перезагрузки кэш-памяти, связанный с переключением задач, когда прерванная задача с высокой вероятностью может быть направлена для продолжения обслуживания в другой процессорный узел. Названное явление увеличивает частоту кэш-промахов и неизбежно приводит к снижению производительности многопроцессорной системы. Другое требующее разрешения противоречие в диспетчерах задач с разделением в пространстве связано с невозможностью автоматического поддержания баланса нагрузки процессорных узлов. Решение задачи лежит в плоскости принудительного обеспечения баланса средствами планировщика/диспетчера, что приводит к дополнительным временным затратам на работу соответствующей программы балансирования. Перечисленные факторы неизбежно приводят к росту сложности программной реализации ядра операционных систем, снижению надежности и безопасности, снижению общей производительности многопроцессорной системы.

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

лами являются модели ресурсов, а заявками - запросы на выполнение пользовательских программ.

Первые работы по анализу систем массового обслуживания были опубликованы в конце 1950-х - начале 1960-х годов, но лишь с 1972 года начинается активное использование сетей массового обслуживания в качестве адекватных математических моделей вычислительных систем. Особый вклад в развитие методов анализа и применения систем массового обслуживания для математического моделирования различных вычислительных систем и их составляющих внесли JI. Клейнрок, X. Taxa, П.П. Бочаров, В.М. Вишневский, В.А. Жожикашвили, Б.В. Гнеденко, И.Н. Коваленко, С.А. Майоров, Т.И. Алиев, A.A. Самарский, Е.С. Вентцель, Л.Б. Богуславский, P.A. Бикташев и другие. Однако ряд вопросов, связанных с математическим моделированием диспетчеров задач в многопроцессорных системах, не нашел должного отражения.

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

Объект исследования - диспетчеры задач в многопроцессорных вычислительных системах.

Предмет исследования — математическое моделирование диспетчеров вычислительных процессов с использованием разомкнутых сетей массового обслуживания, основанных на приоритетных системах массового обслуживания и системах с ограничением длины очереди.

Цель настоящей работы - совершенствование методов математического моделирования диспетчеров задач в многопроцессорных системах на основе разомкнутых сетей массового обслуживания.

Для достижения поставленной цели в диссертационной работе решаются следующие задачи:

1) разработка методов математического моделирования диспетчеров задач с разделением во времени и разделением в пространстве, основанных на приоритетных системах массового обслуживания и системах с ограничением длины очереди, с использованием разомкнутых сетей массового обслуживания;

2) разработка и обоснование численного метода оценки производительности многопроцессорной вычислительной системы с общим диспетчером задач, учитывающего приоритетный входящий поток задач на обработку и приостановку их в случае одновременной занятости всех процессорных узлов;

3) создание комплекса проблемно-ориентированных программ, формирующего исходные данные для моделирования и производящего расчет характеристик диспетчеров задач в многопроцессорных вычислительных системах на основе разомкнутых сетей массового обслуживания;

4) проведение вычислительного эксперимента для расчета вероятностно-временных характеристик подсистемы «диспетчер задач - процессорный узел» с применением разработанных математических методов и комплекса программ, а также проверка адекватности разработанных методов с использованием имитационного моделирования.

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

Научная новизна работы состоит в следующем:

1) разработан метод математического моделирования диспетчеров задач с разделением во времени в составе многопроцессорных систем, в отличие от существующих учитывающий задержки, связанные с конфликтами за доступ к очереди задач, переключением контекстов, перезагрузкой кэш-памяти процессорных узлов, а также ограничение числа мест в очередях обслуживающих устройств;

2) разработан метод математического моделирования диспетчеров задач с разделением в пространстве в составе многопроцессорных систем, в отличие от существующих учитывающий задержки, связанные с балансировкой загрузки процессорных узлов и приоритетность входящего потока задач;

3) обоснован численный метод оценки производительности многопроцессорной системы с общим диспетчером задач, учитывающий приоритетный входящий поток задач на обработку и приостановку их в случае одновременной занятости всех процессорных узлов;

4) создан комплекс проблемно-ориентированных программ для разработанных методов моделирования диспетчеров задач в составе многопроцессорных вычислительных систем на основе разомкнутых сетей массового обслуживания, обеспечивающий проведение вычислительных экспериментов по расчету вероятностно-временных характеристик подсистемы «диспетчер задач -процессорный узел».

Прастическая значимость работы.

Разработанные методы позволяют повысить адекватность моделирования и сократить сроки проектирования многопроцессорной системы. Применение предложенных вычислительных процедур и алгоритмов программного комплекса обеспечивает оценку вероятностно-временных характеристик диспетче-

ра задач на этапе эскизного проектирования, без проведения дорогостоящих физических экспериментов.

Реализация и внедрение результатов работы. Теоретические и практические результаты диссертационной работы использованы при выполнении НИР по проекту № 12-07-31150 «Разработка и исследование методов аппаратной поддержки алгоритмов управления взаимодействующими процессами в высокопроизводительных вычислительных системах», финансируемому Российским фондом фундаментальных исследований. Основные результаты исследований внедрены в ЗАО «НИИФИ и ВТ», г. Пенза, при разработке стендовой аппаратуры тестирования блоков информационно-управляющих систем в части диспетчеризации информационных потоков. Методы моделирования диспетчеров задач многопроцессорных систем использованы в учебном процессе кафедры «Вычислительные машины и системы» Пензенского государственного технологического университета при реализации основной образовательной программы по дисциплинам «Высокопроизводительные вычислительные системы» и «Моделирование» для студентов направления подготовки 230100.62 - «Информатика и вычислительная техника» и специальности 230101 — «Вычислительные машины, комплексы, системы и сети».

Достоверность результатов работы подтверждается имитационным моделированием, использованием апробированных методов математического моделирования, малой вычислительной погрешностью применяемого численного метода, апробацией на всероссийских и международных научных конференциях.

На защиту выносятся.

1. Методы математического моделирования диспетчеров задач с разделением во времени и разделением в пространстве в составе многопроцессорных систем, учитывающие потери времени, связанные с конфликтами, ограниченностью ресурсов, балансировкой загрузки процессорных узлов и приоритетностью очередей.

2. Усовершенствованный численный метод и вычислительный алгоритм оценки производительности многопроцессорной системы с диспетчером задач со стратегией разделения времени, учитывающие приоритетность входящего потока задач.

3. Комплекс проблемно-ориентированных программ для расчета характеристик диспетчеров задач в многопроцессорных вычислительных системах на основе разомкнутых сетей массового обслуживания.

4. Результаты комплексных исследований вероятностно-временных характеристик диспетчеров задач с применением разработанных математических методов и комплекса программ.

Апробация работы. Основные положения диссертационного исследования докладывались и обсуждались на следующих международных и всероссий-

ских научных конференциях: X Международной научно-технической конференции «Новые информационные технологии и системы» (Пенза, 2012 г.), XI Всероссийской научно-технической конференции «Современные методы и средства обработки пространственно-временных сигналов» (Пенза, 2013 г.), XI Международной научно-технической конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации - Распознавание - 2013» (Курск, 2013 г.), XXVI Международной научно-практической конференции «Технические науки - от теории к практике» (Новосибирск, 2013 г.), II Международной научно-практической конференции «Техника и технологии: роль в развитии современного общества» (Краснодар, 2013 г.).

Публикации. По результатам исследований опубликовано 15 печатных работ, в том числе 5 статей в журналах, рекомендованных ВАК, а также получено 2 свидетельства о государственной регистрации программ для ЭВМ.

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

Объем и структура диссертации. Диссертационная работа состоит из введения, четырех разделов, основных результатов и выводов по работе, списка литературы и приложения. Работа изложена на 160 страницах основного текста, включающего 52 рисунков, 4 таблицы, содержит список литературных источников из 154 наименований и приложения.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении отражена актуальность темы, указаны цель и задачи исследования, сформулированы научная новизна и практическая значимость полученных результатов, а также перечислены основные выносимые на защиту положения.

Раздел 1 посвящен обзору современных методов математического моделирования процессов диспетчеризации в многопроцессорных системах (МПС) на основе сетей массового обслуживания (СеМО). Диспетчер задач (ДЗ) является наиболее важной компонентой операционной системы (ОС), от производительности которого в значительной степени зависит общая произ-

водительность МПС. Основные критерии диспетчеризации - использование процессора (максимизируется), пропускная способность системы (максимизируется), среднее время обработки одного процесса (минимизируется), среднее время ожидания одним процессом (минимизируется), среднее время ответа системы (минимизируется).

На основе проведенного анализа методов планирования и диспетчеризации задач в МПС выявлены два основных подхода к планированию и диспетчеризации задач: разделение во времени и разделение в пространстве. Достоинством первого метода является автоматическое поддержание балансировки загрузки, второго - отсутствие необходимости перезагрузки кэш-памяти процессорных узлов (ПУ).

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

- конфликты за доступ к единственной очереди задач множества запрашивающих ПУ;

- задержки на переключение задач в ПУ;

- задержки, связанные с перезагрузкой кэш-памяти ПУ.

Производительность МПС с ДЗ на основе стратегии разделения в пространстве снижается из-за задержек на проведение процедуры балансировки загрузки процессорных узлов.

В результате анализа методов диспетчеризации задач современных ОС, выполнена их классификация. Эти методы можно разделить на бесприоритетные и приоритетные, причем приоритеты зависят от класса задач, устанавливаемых пользователем или ОС, от времени выполнения процесса, от остаточного времени обслуживания процесса, от частоты возникновения событий при реализации процесса. Показано, что в реальных ОС существуют ограничения на число мест в очередях перед ДЗ, формируемых планировщиками задач, из-за ограниченности ресурса памяти.

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

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

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

В разделе 2 разрабатывается метод математического моделирования подсистемы «диспетчер задач - процессорный узел» («ДЗ - ПУ»), учитывающий задержки, связанные с конфликтами за доступ к очереди задач, переключением контекстов, перезагрузкой кэш-памяти ПУ и ограничением числа мест в очередях обслуживающих устройств, а также метод, учитывающий приоритетность задач и задержки, связанные с балансировкой загрузки ПУ.

На основе предложенных методов разомкнутых СеМО и СМО типа М/М/1 и М/О/1 с приоритетными потоками задач, ограничением числа мест в очередях, ограничением числа источников запросов ДЗ проведено математическое моделирование МПС с ДЗ со стратегиями разделения во времени и в пространстве. Разработан численный метод для приближенной оценки вероятностно-временных характеристик МПС с приоритетным входящим потоком задач и приостановкой их, когда все ПУ становятся занятыми обслуживанием требований.

Рассмотрена система с ДЗ и общей очередью (рисунок 1). Задача, поступающая из предварительного планировщика Л'0 с интенсивностью ).0, или после переключения контекста, может быть равновероятно назначена в любой ПУ, (все ПУ, обладают одинаковыми характеристиками). Такое назначение задач выбрано, чтобы приближенно оценить характеристики реального процесса и избежать перегрузки системы, когда все задачи будут пытаться получить обслуживание в одном или нескольких ПУ„ а некоторые ПУ/ будут простаивать. Перед ПУ/ формируется очередь задач с ограничением числа мест, поэтому при ее переполнении части задач будет отказано в обслуживании, что соответствует реальному режиму работы МПС, когда загруженное приложение остается на жестком диске, пока занята очередь готовых к обслуживанию задач. Совокупность ПУ, представляется в виде многоканальной СМО типа М/М/п/к (5^ с числом обслуживающих устройств (ПУ,) п и ограничением длины очереди Ох числом мест в ней, равным к.

ПУ, формируют поток запросов к ДЗ на переключение процесса, т.е. снятия с исполнения текущей задачи, назначения ПУ/ новой задачи из очереди 0\ и постановки прерванной задачи в конец очереди 0\. Причем, если ДЗ занят, то задача помещается в очередь 02.

Существуют два способа формирования очереди 02: когда прерванная задача перемещается ДЗ из очереди готовых процессов 0\ в очередь блокированных процессов О2, когда запрашивающий ПУ, переходит в режим ожидания (приостанавливается), а прерванная задача блокируется. В МПС, особенно ре-

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

о

Л,

о

ДЗ

и'г Ог

хс

Рисунок 1 - Схема модели многопроцессорной системы с общим диспетчером задач

Среднее число ПУ, занятых обслуживанием, определяется выражением

где Я, - интенсивность входного потока задач перед ПУ (5]), ¿1, - интенсивность обслуживания входящего потока задач ПУ.

Отказ в обслуживании происходит в том случае, когда все к мест заняты:

,, п+к

©I

Р«**=—ГТРо, (2)

п п\

где р0 - вероятность отсутствия задач в ПУ п- число ПУ, к- число мест в очереди перед ПУ.

Среднее число задач, находящихся в очереди на обслуживание, определяется выражением

. _<а"'-(1-(со /я)*-(1 + *-(1-и> /и))

'] _ , ,, , 'Ра-

Математическая модель ДЗ представляется одноканапьной СМО (52) с ограниченным числом источников задач на обслуживание. Сгенерировавший

требование ПУ, приостанавливается, если в момент запроса ДЗ занят. В представленной модели это состояние моделируется очередью ожидающих процессоров 02 перед ДЗ. Если ДЗ свободен, то он берется за обслуживание задачи, на что тратится среднее время тдз.

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

/2=ю-^-(1-Яо) = а>-(1-я„И1 + ^), (4)

где 7Г0 - вероятность отсутствия запросов от ПУ, к ДЗ, 9 = ^"у - загрузка ДЗ от потока задач, формируемого одним ПУ/.

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

»',=тЧ (5)

А, А2

Среднее время ожидания задачи в очередях подсистемы «ДЗ - ПУ» рассчитывается по формуле

IV = а,и',+а2и'2, (6)

где а,, а2 - коэффициенты передачи, показывающие, сколько раз задача проходит через СМО 5, (процессорные узлы) и 52 (диспетчер задач) соответственно; IV,, 1г2 - время ожидания обслуживания в очереди перед ПУ и перед ДЗ соответственно.

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

{/ = а, -и, + а2 -и2. (7)

где м,, и2 — время ответа от ПУ и от ДЗ соответственно.

Математическая модель ДЗ со стратегией разделения в пространстве состоит из п одноканальных СМО (5,.....5„) (рисунок 2). Источник 50 моделирует

потоки задач Х0 и поглощает обслуженные задачи (выдача результата пользователю). Перед СМО 5|, 53,..., формируются очереди с ограничением числа мест к. Если имеется свободное место в одной из очередей, то задача занимает его и находится в локальной очереди до тех пор, пока не поступит на выполнение в ПУ. Если используется режим квантования, то незавершенная задача по окончании текущего кванта назначается ДЗ на дообслуживание и помещается в конец той же очереди, где она находилась ранее, иначе результат выдается пользователю, а в локальной очереди освобождается одно место. При завершении выполнения задачи ДЗ просматривает свою очередь. Если в ней имеются требования на обслуживание, то назначается на выполнение задача, стоящая в голове списка. Если очередь пуста, система «ДЗ - ПУ» переходит в режим ожидания. «ДЗ - ПУ» в данном случае производит балансировку загрузки по некоторому алгоритму. Поэтому при переполнении /'-й очереди (с вероятностью

11

ротк ) задачи извлекаются из нее и передаются с некоторой вероятностью в наименее загруженную j-ю очередь.

Рисунок 2 - Схема модели многопроцессорной операционной системы с индивидуальными диспетчерами задач

Рассматриваемая система представлена в виде СеМО, являющейся совокупностью одноканальных СМО. На вход каждой СМО (5,,53,..., 5Л_3,5П_,) поступает поток запросов в общем случае с интенсивностью А., Д3,...Д„_3, ,

я-1

Х0 = ^ А, • Задача, поступившая в момент, когда система занята, становится пе-

1=1

ред ней в очередь и ожидает обслуживания. Допустим, независимо от того, сколько задач поступает в очередь, она не может вместить более к задач, из которых одна обслуживается, а к—\ ожидают. Требования, не попавшие в очередь ожидания О,-, обслуживаются в другом месте, направляются в другую очередь.

Интенсивности Я,,, к,,..., Я„_3, зависят от входящей интенсивности потока задач источника (ка) и вероятностей переходов из СМО 5, в СМО 5). Поскольку в СМО ¿„Яз,...,^,^, могут возникать отказы в обслуживании (с вероятностью рош,- ^ ри), то интенсивности потоков^.,, Х,3,..., А.„_3, будут снижаться. С другой стороны это падение будет компенсироваться переназначением задач из заполненных очередей.

Коэффициент передачи, показывающий, сколько раз задача будет проходить через /-ю СМО, определяется выражением

<*,=-т-1-, ',У = 1,и- (8)

Л„

Задача получает отказ в том случае, когда подсистема «ДЗ - ПУ» занята и все к мест в очереди - тоже, причем вероятность отказа

где р, = X, ■ (тда + упу).

Средняя длина очереди перед подсистемой «ДЗ - ПУ» определяется выражением

¿_Р,2-(1-Р,)-(1-Р,Ч*+1-*-Р.)) Р,2-Р-Р,Ч*+1-*-Р,))

0-р*+2)-0-р,)2 (1-р*+2)-(1-р,) • ( } Определено среднее время ожидания задачи в г'-ой очереди перед «ДЗ -ПУ» и*,, которое равно

= (П) Среднее время ожидания задачи в очередях сети рассчитывается как

п

1¥ = ^аги'., (12)

где а, - коэффициент передачи /-й СМО сети ; и-, - время ожидания в очереди перед /-и СМО.

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

и = Ъаг», (13)

где и/ - время ответа подсистемы «ДЗ - ПУ».

Чтобы определить характеристики МПС с общим ДЗ и приоритетными потоками запросов, применен численный метод, позволивший получить ряд выражений, описывающих поведение рассматриваемой МПС. Например, вероятность приостановки обслуживания задач второго приоритета, когда все ПУ уже заняты обслуживанием, может быть рассчитана по выражению

' V ]'

п-у |--а!_

. т

yl

/ \ Y"

и-у- I" „"\ 1 ил)

(14)

ÍSjl

где c =

n-y

z11

7АЛ

y = —11 = —L — приведенные плотности первого и вто-Hi Из

poro потоков задач, п - число ПУ.

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

Используя усовершенствованный численный метод, можно определить пропускную способность МПС с общим ДЗ по каждому конкретному типу приоритета. Пропускная способность по i-му приоритету определяется по формуле

(15)

где Рпршк:т - вероятность приостановки обслуживания задач /-го приоритета, —

интенсивность потока задач i-го приоритета.

Таким образом, разработанные методы моделирования подсистемы «ДЗ -ПУ», позволяют создать комплекс проблемно-ориентированных программ для проведения вычислительных экспериментов и расчета вероятностно-временных характеристик ДЗ со стратегиями разделения во времени и в пространстве в составе МПС, основанных на разомкнутых СеМО.

Раздел 3 посвящен разработке комплекса программ для реализации разработанных методов моделирования ДЗ в составе МПС на основе разомкнутых сетей массового обслуживания. Комплекс состоит из двух программ: для расчета вероятностно-временных характеристик стохастических сетей массового обслуживания и для измерения производительности функций ОС. Первая программа предназначена для анализа характеристик функционирования ДЗ в составе МПС, представляемой в виде математических моделей устройств, каждому из которых ставится в соответствие одноканальная или много-

14

канальная СМО. Так как ДЗ является составляющей частью МПС и представляется отдельной СМО, то и описываться он будет как часть СеМО.

На рисунке 3 представлена ШЛ-диаграмма алгоритма функционирования предлагаемой программы для расчета вероятностно-временных характеристик стохастических сетей массового обслуживания.

Рисунок 3 - Схема алгоритма функционирования программы для расчета вероятностно-временных характеристик стохастических сетей массового обслуживания

Характеристики отдельных СМО (ДЗ, ПУ) и всей МПС в целом вычисляются перед сохранением в файл отчета по выражениям, полученным в разделе 2. {УМ/,-диаграмма алгоритма ввода начальных параметров и проверки их корректности приведена на рисунке 4.

За основу пользовательского интерфейса взят многооконный интерфейс. Ниже представлены основные окна программы.

Окно визуального редактора показано на рисунке 5. Здесь пользователь может с помощью предоставленных графических элементов создавать и редактировать схему МПС, включающую ДЗ, подлежащую моделированию.

Рисунок 5 - Окно визуального редактора

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

а) б)

Рисунок 6 - Окно редактора матрицы вероятностей передач (а) и окно параметров СМО (б)

Вторая программа предназначена для получения параметров моделирования, а именно для измерения временных параметров функций ОС, таких как переключение контекста, системных вызовов и некоторых других.

Разработанная программа ориентирована на решение следующих задач: выбор тестируемых функций; сбор результатов тестирования; обработка полученных результатов; отображение полученной статистики в виде графиков; отображение результатов в отдельном окне; настройка цветов для отображения данных; сглаживание графиков.

В результате анализа поставленных задач, сделан вывод о целесообразном формате входных и выходных данных программы. Входные данные обязаны включать: а) название тестируемой функции; б) цветовую палитру для отображения результатов. Выходные данные представляются в виде графиков полученных результатов и отображения числовых результатов, не требующих представления в виде графиков.

На рисунке 7 представлена ШЛ-диаграмма алгоритма работы программы для измерения временных параметров некоторых функций ядра ОС.

Рисунок 7 - Схема алгоритма работы программы для измерения временных параметров некоторых функций ядра ОС

В разработанной программе применяется процедура сглаживания графиков по методу наименьших квадратов, обеспечивающему наилучшее согласование кривой ;/ = ф(х) и экспериментальных точек.

Раздел 4 посвящен описанию вычислительных экспериментов, проведенных с использованием разработанных методов математического моделирования и комплекса проблемно-ориентированных программ. При моделировании учитывалась трудоемкость задач: низкая или высокая, а также реакция на запрос. Низкая

трудоемкость характерна для систем жесткого реального времени, когда задача должна быть выполнена точно в срок и, зачастую, с высокой скоростью. Низкая трудоемкость обусловлена либо небольшой длиной программы, либо высокой производительностью процессора. Трудоемкость задач варьировалась путем изменения времени обслуживания в ПУ. Считается, чем меньше время обслуживания задачи в ПУ, тем ниже её трудоемкость (выше реакция на запрос, что характерно для систем реального времени). Реакция на запрос варьировалась путем изменения величины кванта процессорного времени, предоставляемого выполняемым задачам. Известно, что чем меньше квант, тем выше реакция на запрос.

Для вычислительного эксперимента приняты следующие значения параметров: число ПУ (и) в МПС варьировалось от 2 до 20; трудоемкость задач (0) принята следующей: для задач с высокой реакцией - 0,1 мс, для задач со средней реакцией - 0,5 мс, наконец, для задач с низкой реакцией (самые трудоемкие) - 1,0 мс; загрузка ПУ (р„у) поддерживалась постоянной и

равной 0,65; время кванта (tk ) для проведенных опытов принято постоянным и равным 0,1 мс; время работы ДЗ (хдз) при переключении контекста

задач составляет 5 мкс (получено измерением на системе-прототипе с помощью программы измерения); время перезагрузки кэш-памяти принято равным 5 мкс (оценка получена с помощью тестового пакета RightMark Memory Analyzer).

Некоторые результаты моделирования МПС, включающей ДЗ со стратегиями разделения во времени и в пространстве, показаны на рисунках 8 и 9.

Из графика (рисунок 8) следует, что загрузка ДЗ со стратегией разделения во времени растет с понижением трудоемкости задач, т.е. с увеличением реактивности МПС. Загрузка ДЗ со стратегией разделения в пространстве остается постоянной при увеличении числа ПУ.

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

В результате моделирования (рисунок 9) выявлено, что ДЗ со стратегией разделения во времени с заданными параметрами показывают лучшие результаты по производительности в диапазоне от 2 до 19 ПУ, чем ДЗ со стратегией разделения в пространстве. Таким образом, для МПС жесткого реального времени с небольшим числом ПУ следует использовать ДЗ с разделением во времени, при большом, соответственно, - ДЗ с разделением в пространстве.

Рисунок 8 - Зависимость загрузки ДЗ от трудоемкости задам

I °<6 I'M.............В......И ■ И......и.....И""~МТИ"" - „

Ь ™ га т шс шгу-ш «ч—ютв при задачах с

£ 0,5 I------------------------------------------------------------------------------------------1................высокой реакцией,

к I общий ДЗ

о. 0,4 I —#~toTB при задачах с

ей

высокой реакцией, распр. ДЗ

0,3 0,2

0

JH^zz.

2 4 6 S 10 12 14 16 18 20 Число процессорных узлов, шт

Рисунок 9 - Зависимость времени ответа МПС от числа ПУ

С использованием метода регрессионного анализа определена корреляционная зависимость результатов, полученных на имитационной и аналитических моделях. Коэффициент корреляции существующего метода моделирования с имитационной моделью составляет 0,83, а разработанного метода - 0,99. Это свидетельствует о большей адекватности разработанных методов моделирования процессам в реальной системе, чем при использовании традиционных методов, основанных на экспоненциальных разомкнутых сетях массового обслуживания.

В приложении приведены акты внедрения результатов диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

1.На основе выполненного анализа современных методов математического моделирования диспетчеров задач в многопроцессорных системах разработаны методы математического моделирования подсистемы «диспетчер задач — процессорный узел», основанные на приоритетных системах массового обслуживания и системах с ограничением длины очереди с использованием разомкнутых сетей массового обслуживания.

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

3. Разработан метод математического моделирования для оценки показателей производительности диспетчеров задач с разделением в пространстве в многопроцессорных системах, который в отличие от существующих, учитывает задержки, связанные с балансировкой загрузки процессорных узлов, а также приоритетность задач и ограничение числа мест в очередях обслуживающих устройств.

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

5. Создан комплекс проблемно-ориентированных программ для реализации разработанных методов моделирования диспетчеров задач в составе многопроцессорных вычислительных систем на основе разомкнутых сетей массового обслуживания и для измерения временных параметров некоторых функций ядра операционной системы, в частности, времени переключения контекста диспетчера задач.

6. С применением разработанных математических методов и комплекса программ проведены комплексные исследования вероятностно-временных характеристик подсистемы «диспетчер задач - процессорный узел». Адекватность приведенных методов проверена путем имитационного моделирования.

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных ВАК

1. Мартышкин, А.И. Исследование диспетчеров задач многопроцессорных систем на моделях массового обслуживания [Текст] / А.И. Мартышкин // XXI век: Итоги прошлого и проблемы настоящего плюс* Серия: Технические науки. Информационные технологии. -2012. -№05 (09).-С. 139-146.

2. Мартышкин, А.И. Математическое моделирование диспетчеров задач для систем параллельной обработки на основе разомкнутых систем массового обслуживания [Текст] / А.И. Мартышкин, P.A. Бикташев, Н.Г. Востоков // В мире научных открытий. - 2013. - № 6.1 (42) (Математика. Механика. Информатика). - С. 81-101.

3. Мартышкин, А.И. Комплекс программ для определения характеристик диспетчеров задач многопроцессорных систем с использованием приоритетных стохастических сетей массового обслуживания [Текст] / P.A. Бикташев, А.И. Мартышкин, Н.Г. Востоков // Фундаментальные исследования. - 2013. -№ 10(ч. 1).-С. 13-20.

4. Мартышкин, А.И. Численное моделирование диспетчеров задач со стратегией разделения пространства для параллельных вычислительных систем на основе разомкнутых сетей массового обслуживания [Текст] / А.И. Мартышкин // XXI век: Итоги прошлого и проблемы настоящего плюс. Технические науки. Информационные технологии. - 2013. - № 10 (14). - С. 159-166.

5. Мартышкин, А.И. Комплекс программ для измерения производительности функций операционных систем [Текст] / P.A. Бикташев, А.И. Мартышкин // XXI век: Итоги прошлого и проблемы настоящего плюс. Серия: Технические науки. Информационные технологии. - 2013. -№ 10 (14). -С. 187-195.

Публикации в других изданиях

6. Мартышкин, А.И. Исследование подсистем памяти с буферизацией транзакций на моделях массового обслуживания [Текст] / А.И. Мартышкин // XXI век: Итоги прошлого и проблемы настоящего „люс- Серия: Технические науки. Информационные технологии.-2011.-№03 (ОЗ).-С. 124-131.

7. Мартышкин, А.И. Моделирование диспетчеров задач многопроцессорных систем [Текст] / P.A. Бикташев, А.И. Мартышкин // Успехи современного естествознания. - 2012. — № 6. — С. 83-85.

8. Мартышкин, А.И. Модели для оценки производительности семафоров многопроцессорных систем [Текст] / P.A. Бикташев, А.И. Мартышкин // Новые информационные технологии и системы: Сборник статей X международной научно-технической конференции. - Пенза: ПГУ, 2012. - С. 29-32.

9. Мартышкин, А.И. Разработка комплекса программ для расчета систем и сетей массового обслуживания [Текст] / P.A. Бикташев, А.И. Мартышкин, Н.Г. Востоков // Современные методы и средства обработки пространственно-временных сигналов: Сборник статей XI Всероссийской научно-технической конференции. - Пенза: ПДЗ, 2013. - С. 78-82.

10. Мартышкин, А.И. Разработка комплекса программ для измерения производительности функций операционных систем [Текст] / А.И. Мартышкин, P.A. Бикташев, Е.В. Воронкин // Современные методы и средства обработки пространственно-временных сигналов: Сборник статей XI Всероссийской научно-технической конференции. - Пенза: ПДЗ, 2013. - С- 82-87.

11. Мартышкин, А.И. Математическая модель диспетчера задач с общей очередью для систем параллельной обработки [Текст] / А.И. Мартышкин // Современные методы и средства обработки пространственно-временных сигналов: Сборник статей XI Всероссийской научно-технической конференции. -Пенза: ПДЗ, 2013. - С. 87-91.

12. Мартышкин, А.И. Математическое моделирование функций управления взаимодействующими процессами и ресурсами многопроцессорных систем [Текст] / P.A. Бикташев, А.И. Мартышкин, Н.Г. Востоков // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознавание -2013: Сборник статей XI международной научно-технической конференции. - Курск: ЮЗГТУ, 2013.-С. 218-220.

13. Мартышкин, А.И. Математическое моделирование диспетчеров задач со стратегией разделения пространства для параллельных вычислительных систем на основе разомкнутых сетей массового обслуживания [Текст] / А.И. Мартышкин, P.A. Бикташев // Технические науки — от теории к практике: сборник статей по материалам XXVI международной научно-практической конференции. — Новосибирск: Изд-во «СибАК», 2013. - С. 36^12

14. Мартышкин, А.И. Численное моделирование диспетчеров задач со стратегией разделения пространства на основе разомкнутых сетей массового обслуживания [Текст] / А.И. Мартышкин // Техника и технологии: роль в развитии

современного общества: Сборник статей И Международной научно-практической конференции. - Краснодар: Изд-во «Априори», 2013. - С. 126-130.

15. Мартышкин, А.И. Математическое моделирование семафоров для оценки производительности вычислительных систем [Текст] / А.И. Мартышкин// Итоги диссертационных исследований: Материалы V Всероссийского конкурса молодых ученых. -М.: РАН, 2013.-Т. 4.-С. 114-121.

Зарегистрированные программы

16. Свидетельство о государственной регистрации программы для ЭВМ № 2013611117. Программный комплекс для расчета вероятностно-временных характеристик стохастических сетей массового обслуживания. Правообладатель: ФГБОУ ВПО «Пензенская государственная технологическая академия». Авторы: Мартышкин А.И., Бикташев P.A. Заявка № 2012660617 от 5.12.2012 г. Зарегистрировано в Реестре программ для ЭВМ 9.01.2013 г.

17. Свидетельство о государственной регистрации программы для ЭВМ № 2013611118. Программный комплекс для измерения производительности функций операционных систем. Правообладатель: ФГБОУ ВПО «Пензенская государственная технологическая академия». Авторы: Мартышкин А И Бикташев P.A. Заявка № 2012660618 от 5.12.2012 г. Зарегистрировано в Растре программ для ЭВМ 9.01.2013 г.

МАРТЫШКИН Алексей Иванович

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ДИСПЕТЧЕРОВ ЗАДАЧ В МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ НА ОСНОВЕ СТОХАСТИЧЕСКИХ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ

Специальность 05.13.18 - математическое моделирование, численные методы и

комплексы программ

Автореферат диссертации на соискание ученой степени кандидата технических наук

Компьютерная верстка Т А. Антиповои

Сдано в производство 12.11.13. Формат 60x84 '/if, Бумага типогр. № 1. Печать трафаретная. Шрифт Times New Roman Cyr. Усл. печ. л. 1,39. Уч.-издл. 1,4. Заказ .№ 2375. Тираж 100.

Пензенский государственный технологический университет.

440039, Россия, г. Пенза, пр. Байдукова'ул. Гагарина, 1а/11

фгбоу впо «пензенский государственный

технологический университет»

На правах рукописи

04201453771 мартышкин алексей иванович

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ДИСПЕТЧЕРОВ ЗАДАЧ В МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ НА ОСНОВЕ СТОХАСТИЧЕСКИХ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: кандидат технических наук, доцент бикташев р. а.

пенза-2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 5

1 ОБЗОР СОВРЕМЕННЫХ МЕТОДОВ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ ПРОЦЕССОВ ДИСПЕТЧЕРИЗАЦИИ

В МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ НА ОСНОВЕ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ 12

1.1 Методы планирования и диспетчеризации процессов

в операционных системах 12

1.2 Общее назначение и функции механизмов диспетчеризации

потоков задач и методы их математического моделирования 17

1.3 Анализ методов диспетчеризации задач современных операционных систем 20

1.4 Анализ существующих средств компьютерного моделирования

систем массового обслуживания, представленных в аналитической форме 28

1.5 Анализ существующих методов моделирования систем

массового обслуживания 33

1.6 Сети массового обслуживания 35

1.7 Стохастические сети массового обслуживания как метод для анализа и оценки вероятностно-временных характеристик диспетчеров задач в многопроцессорных вычислительных системах 39

1.8 Выводы по разделу 1 42

2 МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ДИСПЕТЧЕРОВ ЗАДАЧ МНОГОПРОЦЕССОРНЫХ СИСТЕМ НА ОСНОВЕ РАЗОМКНУТЫХ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ

С ПРИМЕНЕНИЕМ АНАЛИТИЧЕСКИХ И ЧИСЛЕННЫХ МЕТОДОВ 45

2.1 Математическое моделирование диспетчеров задач

со стратегией разделения во времени 46

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

2.1.2 Многопроцессорная вычислительная система с общим диспетчером задач и приоритетными дисциплинами обслуживания

2.2 Математическое моделирование диспетчеров задач со стратегией разделения в пространстве

2.2.1 Диспетчеры задач в многопроцессорных вычислительных системах основанных на системах массового обслуживания типа М/М/1,

с однородным входящим потоком задач, бесприоритетным методом диспетчеризации и очередью с ограничением числа мест

2.2.2 Диспетчеры задач в многопроцессорных вычислительных системах основанных на системах массового обслуживания типа МЮ/1,

с неоднородным потоком задач на обслуживание

2.3 Совершенствование численного метода оценки производительности многопроцессорной вычислительной системы с общим диспетчером задач, приоритетным входящим потоком задач и приостановкой их в случае, когда заняты все процессорные узлы

2.4 Выводы по разделу 2

3 КОМПЛЕКС ПРОГРАММ ДЛЯ МОДЕЛИРОВАНИЯ ДИСПЕТЧЕРОВ ЗАДАЧ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ НА ОСНОВЕ РАЗОМКНУТЫХ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ

3.1 Программа для расчета вероятностно-временных характеристик стохастических сетей массового обслуживания

3.1.1 Разработка структуры данных

3.1.2 Разработка алгоритмов решения задачи

3.1.3 Описание программы

3.2 Программа для измерения временных параметров некоторых функций операционных систем

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

3.2.2 Архитектура программы

3.2.3 Разработка программы

3.3 Выводы по разделу 3

4 ПРОВЕДЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ С ИСПОЛЬЗОВАНИЕМ РАЗРАБОТАННОГО КОМПЛЕКСА ПРОГРАММ И ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ 102

4.1 Расчет характеристик многопроцессорной вычислительной системы

с общим диспетчером задач и бесприоритетным методом обслуживания 102

4.2 Расчет характеристик многопроцессорной вычислительной системы с общим диспетчером задач с приоритетными

дисциплинами обслуживания 111

4.3 Расчет характеристик диспетчеров задач с разделением в пространстве с бесприоритетным методом обслуживания и очередью с ограничением

числа мест 114

4.4 Расчет характеристик диспетчеров задач с разделением в пространстве

с неоднородным входящим потоком задач 122

4.5 Численное моделирование диспетчеров задач со стратегией разделения

по пространству, неоднородным потоком и относительными приоритетами 127

4.6 Выводы по разделу 4 134 ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ 136 СПИСОК СОКРАЩЕНИЙ 138 СПИСОК ТЕРМИНОВ 139 ЛИТЕРАТУРА 144 ПРИЛОЖЕНИЕ А. Акты внедрения результатов диссертации 158

ВВЕДЕНИЕ

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

Задача диспетчеризации процессов в многопроцессорной системе является двумерной. Одновременно с функцией назначения задачи выполняется функция выделения целевого процессора, что приводит к дополнительным издержкам времени. Кроме того, в диспетчере задач с разделением во времени возникает процесс перезагрузки кэш-памяти, связанный с переключением задач, когда прерванная задача с высокой вероятностью может быть направлена для продолжения обслуживания в другой процессорный узел. Названное явление увеличивает частоту кэш-промахов и неизбежно приводит к снижению производительности многопроцессорной системы. Другое требующее разрешения противоречие в диспетчерах задач с разделением в пространстве связано с невозможностью автоматического поддержания баланса нагрузки процессорных узлов. Решение задачи лежит в плоскости принудительного обеспечения баланса средствами планировщика/диспетчера, что приводит к дополнительным временным затратам на работу соответствующей программы балансирования. Перечисленные факторы неизбежно приводят к росту

5

сложности программной реализации ядра операционных систем, снижению надежности и безопасности, снижению общей производительности многопроцессорной системы.

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

Первые работы по анализу систем массового обслуживания были опубликованы в конце 1950-х - начале 1960-х годов, но лишь с 1972 года начинается активное использование сетей массового обслуживания в качестве адекватных математических моделей вычислительных систем. Особый вклад в развитие методов анализа и применения систем массового обслуживания для математического моделирования различных вычислительных систем и их составляющих внесли Л. Клейнрок, X. Taxa, П.П. Бочаров, В.М. Вишневский, В.А. Жожикашвили, Б.В. Гнеденко, И.Н. Коваленко, CA. Майоров, Т.И. Алиев, A.A. Самарский, Е.С. Вентцель, Л.Б. Богуславский, P.A. Бикташев и другие. Однако ряд вопросов, связанных с математическим моделированием диспетчеров задач в многопроцессорных системах, не нашел должного отражения.

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

для специализированных многопроцессорных систем и снизить себестои-

6

мость проекта. Вышесказанное обусловливает актуальность темы исследования.

Объект исследования - диспетчеры задач в многопроцессорных вычислительных системах.

Предмет исследования - математическое моделирование диспетчеров вычислительных процессов с использованием разомкнутых сетей массового обслуживания, основанных на приоритетных системах массового обслуживания и системах с ограничением длины очереди.

Цель настоящей работы - совершенствование методов математического моделирования диспетчеров задач в многопроцессорных системах на основе разомкнутых сетей массового обслуживания.

Для достижения поставленной цели в диссертационной работе решаются следующие задачи:

1) разработка методов математического моделирования диспетчеров задач с разделением во времени и разделением в пространстве, основанных на приоритетных системах массового обслуживания и системах с ограничением длины очереди, с использованием разомкнутых сетей массового обслуживания;

2) разработка и обоснование численного метода оценки производительности многопроцессорной вычислительной системы с общим диспетчером задач, учитывающего приоритетный входящий поток задач на обработку и приостановку их в случае одновременной занятости всех процессорных узлов;

3) создание комплекса проблемно-ориентированных программ, формирующего исходные данные для моделирования и производящего расчет характеристик диспетчеров задач в многопроцессорных вычислительных системах на основе разомкнутых сетей массового обслуживания;

4) проведение вычислительного эксперимента для расчета вероятностно-временных характеристик подсистемы «диспетчер задач - процессорный

узел» с применением разработанных математических методов и комплекса

7

программ, а также проверка адекватности разработанных методов с использованием имитационного моделирования.

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

Научная новизна работы состоит в следующем:

1) разработан метод математического моделирования диспетчеров задач с разделением во времени в составе многопроцессорных систем, в отличие от существующих учитывающий задержки, связанные с конфликтами за доступ к очереди задач, переключением контекстов, перезагрузкой кэшпамяти процессорных узлов, а также ограничение числа мест в очередях обслуживающих устройств;

2) разработан метод математического моделирования диспетчеров задач с разделением в пространстве в составе многопроцессорных систем, в отличие от существующих учитывающий задержки, связанные с балансировкой загрузки процессорных узлов и приоритетность входящего потока задач;

3) обоснован численный метод оценки производительности многопроцессорной системы с общим диспетчером задач, учитывающий приоритетный входящий поток задач на обработку и приостановку их в случае одновременной занятости всех процессорных узлов;

4) создан комплекс проблемно-ориентированных программ для разработанных методов моделирования диспетчеров задач в составе многопроцессорных вычислительных систем на основе разомкнутых сетей массового обслуживания, обеспечивающий проведение вычислительных экспериментов по расчету вероятностно-временных характеристик подсистемы «диспетчер задач - процессорный узел».

Практическая значимость работы.

Разработанные методы позволяют повысить адекватность моделирования и сократить сроки проектирования многопроцессорной системы. Приме-

8

нение предложенных вычислительных процедур и алгоритмов программного комплекса обеспечивает оценку вероятностно-временных характеристик диспетчера задач на этапе эскизного проектирования, без проведения дорогостоящих физических экспериментов.

Реализация и внедрение результатов работы. Теоретические и практические результаты диссертационной работы использованы при выполнении НИР по проекту № 12-07-31150 «Разработка и исследование методов аппаратной поддержки алгоритмов управления взаимодействующими процессами в высокопроизводительных вычислительных системах», финансируемому Российским фондом фундаментальных исследований. Основные результаты исследований внедрены в ЗАО «НИИФИ и ВТ», г. Пенза, при разработке стендовой аппаратуры тестирования блоков информационно-управляющих систем в части диспетчеризации информационных потоков. Методы моделирования диспетчеров задач многопроцессорных систем использованы в учебном процессе кафедры «Вычислительные машины и системы» Пензенского государственного технологического университета при реализации основной образовательной программы по дисциплинам «Высокопроизводительные вычислительные системы» и «Моделирование» для студентов направления подготовки 230100.62 - «Информатика и вычислительная техника» и специальности 230101 - «Вычислительные машины, комплексы, системы и сети».

Достоверность результатов работы подтверждается имитационным моделированием, использованием апробированных методов математического моделирования, малой вычислительной погрешностью применяемого численного метода, апробацией на всероссийских и международных научных конференциях.

На защиту выносятся.

1. Методы математического моделирования диспетчеров задач с разделением во времени и разделением в пространстве в составе многопроцессорных систем, учитывающие потери времени, связанные с конфликтами, огра-

9

ниченностью ресурсов, балансировкой загрузки процессорных узлов и приоритетностью очередей.

2. Усовершенствованный численный метод и вычислительный алгоритм оценки производительности многопроцессорной системы с диспетчером задач со стратегией разделения времени, учитывающие приоритетность входящего потока задач.

3. Комплекс проблемно-ориентированных программ для расчета характеристик диспетчеров задач в многопроцессорных вычислительных системах на основе разомкнутых сетей массового обслуживания.

4. Результаты комплексных исследований вероятностно-временных характеристик диспетчеров задач с применением разработанных математических методов и комплекса программ.

Апробация работы. Основные положения диссертационного исследования докладывались и обсуждались на следующих международных и всероссийских научных конференциях: X Международной научно-технической конференции «Новые информационные технологии и системы» (Пенза, 2012 г.), XI Всероссийской научно-технической конференции «Современные методы и средства обработки пространственно-временных сигналов» (Пенза, 2013 г.), XI Международной научно-технической конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации - Распознавание - 2013» (Курск, 2013 г.), XXVI Международной научно-практической конференции «Технические науки - от теории к практике» (Новосибирск, 2013 г.), II Международной научно-практической конференции «Техника и технологии: роль в развитии современного общества» (Краснодар, 2013 г.).

По материалам диссертации имеется 17 публикаций, в том числе пять статей в журналах, рекомендованных ВАК и 2 свидетельства о государственной регистрации программ для ЭВМ.

Автор считает необходимым выразить искреннюю благодарность кандидату технических наук Бикташеву Равилю Айнуловичу, доктору техниче-

10

ских наук Сальникову Игорю Ивановичу, доктору технических наук Чулкову Валерию Александровичу, коллективу кафедры «Вычислительные машины и системы» ФГБОУ ВПО «Пензенский государственный технологический университет» за внимание и помощь при подготовке диссертационной работы.

1 ОБЗОР СОВРЕМЕННЫХ МЕТОДОВ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ ПРОЦЕССОВ ДИСПЕТЧЕРИЗАЦИИ В МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ НА ОСНОВЕ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ

1.1 Методы планирования и диспетчеризации процессов в операционных системах

В общем случае планирование состоит из двух шагов, выполняющихся друг за другом:

1) собственно планирование, т.е. составление расписания запуска задач;

2) диспетчеризация - выбор задачи из списка и назначение ей ПУ.

Существует два основны�