Содержание к диссертации
Введение
1 Обзор современных методов математического моделирования процессов диспетчеризации в многопроцессорных вычислительных системах на основе сетей массового обслуживания 12
1.1 Методы планирования и диспетчеризации процессов в операционных системах 12
1.2 Общее назначение и функции механизмов диспетчеризации потоков задач и методы их математического моделирования
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 Многопроцессорная вычислительная система с единственным диспетчером задач, общей очередью требований на обслуживание с ограничением числа мест, бесприоритетным методом диспетчеризации
2.1.2 Многопроцессорная вычислительная система с общим диспетчером задач и приоритетными дисциплинами обслуживания 52
2.2 Математическое моделирование диспетчеров задач со стратегией разделения в пространстве 54
2.2.1 Диспетчеры задач в многопроцессорных вычислительных системах, основанных на системах массового обслуживания типа М/М/1, с однородным входящим потоком задач, бесприоритетным методом диспетчеризации и очередью с ограничением числа мест 54
2.2.2 Диспетчеры задач в многопроцессорных вычислительных системах, основанных на системах массового обслуживания типа М/G/l, с неоднородным потоком задач на обслуживание 59
2.3 Совершенствование численного метода оценки производительности многопроцессорной вычислительной системы с общим диспетчером задач, приоритетным входящим потоком задач и приостановкой их в случае, когда заняты все процессорные узлы 66
2.4 Выводы по разделу 2 76
3 Комплекс программ для моделирования диспетчеров задач в многопроцессорных системах на основе разомкнутых сетей массового обслуживания 77
3.1 Программа для расчета вероятностно-временных характеристик стохастических сетей массового обслуживания 77
3.1.1 Разработка структуры данных 81
3.1.2 Разработка алгоритмов решения задачи 82
3.1.3 Описание программы 88
3.2 Программа для измерения временных параметров некоторых функций операционных систем 92
3.2.1 Постановка задачи 93
3.2.2 Архитектура программы 95
3.2.3 Разработка программы 96
3.3 Выводы по разделу 3 100
Проведение вычислительных экспериментов с использованием разработанного комплекса программ и имитационного моделирования 102
4.1 Расчет характеристик многопроцессорной вычислительной системы с общим диспетчером задач и бесприоритетным методом обслуживания 102
4.2 Расчет характеристик многопроцессорной вычислительной системы с общим диспетчером задач с приоритетными дисциплинами обслуживания 111
4.3 Расчет характеристик диспетчеров задач с разделением в пространстве с бесприоритетным методом обслуживания и очередью с ограничением числа мест 114
4.4 Расчет характеристик диспетчеров задач с разделением в пространстве с неоднородным входящим потоком задач 122
4.5 Численное моделирование диспетчеров задач со стратегией разделения по пространству, неоднородным потоком и относительными приоритетами 127
4.6 Выводы по разделу 4 134
Основные результаты и выводы 136
Список сокращений 138
Список терминов 139
Литература 144
- Общее назначение и функции механизмов диспетчеризации потоков задач и методы их математического моделирования
- Многопроцессорная вычислительная система с единственным диспетчером задач, общей очередью требований на обслуживание с ограничением числа мест, бесприоритетным методом диспетчеризации
- Программа для измерения временных параметров некоторых функций операционных систем
- Расчет характеристик диспетчеров задач с разделением в пространстве с бесприоритетным методом обслуживания и очередью с ограничением числа мест
Введение к работе
Актуальность темы. Для обеспечения работы современных вычислительных систем в режиме реального времени все более широкое применение находят многопроцессорные и многоядерные архитектуры, создание которых сопряжено с решением задач управления процессами и ресурсами путем диспетчеризации. Эффективность выполнения функций диспетчеров задач определяется скоростью переключения процессов. Планировщик и диспетчер в многопроцессорной системе вызываются приложениями гораздо чаще, чем в однопроцессорной системе, поэтому доступ к этим программным ресурсам порождает конфликтные ситуации. Особенно это проявляется в многоядерных системах на кристалле, имеющих потенциально высокую производительность. Традиционная программная реализация диспетчеров задач часто не обеспечивает требуемой производительности системы. Поэтому при проектировании ядра операционной системы необходимо производить выбор наиболее эффективных технических средств его реализации.
Задача диспетчеризации процессов в многопроцессорной системе является двумерной. Одновременно с функцией назначения задачи выполняется функция выделения целевого процессора, что приводит к дополнительным издержкам времени. Кроме того, в диспетчере задач с разделением во времени возникает процесс перезагрузки кэш-памяти, связанный с переключением задач, когда прерванная задача с высокой вероятностью может быть направлена для продолжения обслуживания в другой процессорный узел. Названное явление увеличивает частоту кэш-промахов и неизбежно приводит к снижению производительности многопроцессорной системы. Другое требующее разрешения противоречие в диспетчерах задач с разделением в пространстве связано с невозможностью автоматического поддержания баланса нагрузки процессорных узлов. Решение задачи лежит в плоскости принудительного обеспечения баланса средствами планировщика/диспетчера, что приводит к дополнительным временным затратам на работу соответствующей программы балансирования. Перечисленные факторы неизбежно приводят к росту сложности программной реализации ядра операционных систем, снижению надежности и безопасности, снижению общей производительности многопроцессорной системы.
При доступе к критическим ресурсам операционной системы, планировании и диспетчеризации задач к этим ресурсам возникают очереди ожидающих обслуживания процессов. Поэтому для аналитического описания многопроцессорной системы обычно привлекается теория массового обслуживания. При этом математическая модель многопроцессорной системы представляется в виде стохастической сети массового обслуживания, где уз-
лами являются модели ресурсов, а заявками - запросы на выполнение пользовательских программ.
Первые работы по анализу систем массового обслуживания были опубликованы в конце 1950-х - начале 1960-х годов, но лишь с 1972 года начинается активное использование сетей массового обслуживания в качестве адекватных математических моделей вычислительных систем. Особый вклад в развитие методов анализа и применения систем массового обслуживания для математического моделирования различных вычислительных систем и их составляющих внесли Л. Клейнрок, X. Таха, П.П. Бочаров, В.М. Вишневский, В.А. Жожикашвили, Б.В. Гнеденко, И.Н. Коваленко, С.А. Майоров, Т.И. Алиев, А.А. Самарский, Е.С. Вентцель, Л.Б. Богуславский, Р.А. Бикташев и другие. Однако ряд вопросов, связанных с математическим моделированием диспетчеров задач в многопроцессорных системах, не нашел должного отражения.
Многие задачи проектирования многопроцессорных вычислительных систем связаны с распределением и диспетчеризацией ресурсов среди конкурирующих требований, причем моменты появления этих требований носят случайный характер. Эффективным путем решения этих задач является математическое моделирование многопроцессорных систем, включающих диспетчеры задач, что позволит сократить сроки проектирования диспетчеров для специализированных многопроцессорных систем и снизить себестоимость проекта. Вышесказанное обусловливает актуальность темы исследования.
Объект исследования - диспетчеры задач в многопроцессорных вычислительных системах.
Предмет исследования - математическое моделирование диспетчеров вычислительных процессов с использованием разомкнутых сетей массового обслуживания, основанных на приоритетных системах массового обслуживания и системах с ограничением длины очереди.
Цель настоящей работы - совершенствование методов математического моделирования диспетчеров задач в многопроцессорных системах на основе разомкнутых сетей массового обслуживания.
Для достижения поставленной цели в диссертационной работе решаются следующие задачи:
-
разработка методов математического моделирования диспетчеров задач с разделением во времени и разделением в пространстве, основанных на приоритетных системах массового обслуживания и системах с ограничением длины очереди, с использованием разомкнутых сетей массового обслуживания;
-
разработка и обоснование численного метода оценки производительности многопроцессорной вычислительной системы с общим диспетчером задач, учитывающего приоритетный входящий поток задач на обработку и приостановку их в случае одновременной занятости всех процессорных узлов;
-
создание комплекса проблемно-ориентированных программ, формирующего исходные данные для моделирования и производящего расчет характеристик диспетчеров задач в многопроцессорных вычислительных системах на основе разомкнутых сетей массового обслуживания;
-
проведение вычислительного эксперимента для расчета вероятностно-временных характеристик подсистемы «диспетчер задач - процессорный узел» с применением разработанных математических методов и комплекса программ, а также проверка адекватности разработанных методов с использованием имитационного моделирования.
Методы исследований. Для решения поставленных задач в диссертационной работе использованы методы теории аналитического, численного и имитационного моделирования, теории систем и сетей массового обслуживания, теории вероятностей и математической статистики.
Научная новизна работы состоит в следующем:
-
разработан метод математического моделирования диспетчеров задач с разделением во времени в составе многопроцессорных систем, в отличие от существующих учитывающий задержки, связанные с конфликтами за доступ к очереди задач, переключением контекстов, перезагрузкой кэш-памяти процессорных узлов, а также ограничение числа мест в очередях обслуживающих устройств;
-
разработан метод математического моделирования диспетчеров задач с разделением в пространстве в составе многопроцессорных систем, в отличие от существующих учитывающий задержки, связанные с балансировкой загрузки процессорных узлов и приоритетность входящего потока задач;
-
обоснован численный метод оценки производительности многопроцессорной системы с общим диспетчером задач, учитывающий приоритетный входящий поток задач на обработку и приостановку их в случае одновременной занятости всех процессорных узлов;
-
создан комплекс проблемно-ориентированных программ для разработанных методов моделирования диспетчеров задач в составе многопроцессорных вычислительных систем на основе разомкнутых сетей массового обслуживания, обеспечивающий проведение вычислительных экспериментов по расчету вероятностно-временных характеристик подсистемы «диспетчер задач -процессорный узел».
Практическая значимость работы.
Разработанные методы позволяют повысить адекватность моделирования и сократить сроки проектирования многопроцессорной системы. Применение предложенных вычислительных процедур и алгоритмов программного комплекса обеспечивает оценку вероятностно-временных характеристик диспетче-
pa задач на этапе эскизного проектирования, без проведения дорогостоящих физических экспериментов.
Реализация и внедрение результатов работы. Теоретические и практические результаты диссертационной работы использованы при выполнении НИР по проекту № 12-07-31150 «Разработка и исследование методов аппаратной поддержки алгоритмов управления взаимодействующими процессами в высокопроизводительных вычислительных системах», финансируемому Российским фондом фундаментальных исследований. Основные результаты исследований внедрены в ЗАО «НИИФИ и ВТ», г. Пенза, при разработке стендовой аппаратуры тестирования блоков информационно-управляющих систем в части диспетчеризации информационных потоков. Методы моделирования диспетчеров задач многопроцессорных систем использованы в учебном процессе кафедры «Вычислительные машины и системы» Пензенского государственного технологического университета при реализации основной образовательной программы по дисциплинам «Высокопроизводительные вычислительные системы» и «Моделирование» для студентов направления подготовки 230100.62 - «Информатика и вычислительная техника» и специальности 230101 - «Вычислительные машины, комплексы, системы и сети».
Достоверность результатов работы подтверждается имитационным моделированием, использованием апробированных методов математического моделирования, малой вычислительной погрешностью применяемого численного метода, апробацией на всероссийских и международных научных конференциях.
На защиту выносятся.
-
Методы математического моделирования диспетчеров задач с разделением во времени и разделением в пространстве в составе многопроцессорных систем, учитывающие потери времени, связанные с конфликтами, ограниченностью ресурсов, балансировкой загрузки процессорных узлов и приоритетностью очередей.
-
Усовершенствованный численный метод и вычислительный алгоритм оценки производительности многопроцессорной системы с диспетчером задач со стратегией разделения времени, учитывающие приоритетность входящего потока задач.
-
Комплекс проблемно-ориентированных программ для расчета характеристик диспетчеров задач в многопроцессорных вычислительных системах на основе разомкнутых сетей массового обслуживания.
-
Результаты комплексных исследований вероятностно-временных характеристик диспетчеров задач с применением разработанных математических методов и комплекса программ.
Апробация работы. Основные положения диссертационного исследования докладывались и обсуждались на следующих международных и всероссий-
ских научных конференциях: X Международной научно-технической конференции «Новые информационные технологии и системы» (Пенза, 2012 г.), XI Всероссийской научно-технической конференции «Современные методы и средства обработки пространственно-временных сигналов» (Пенза, 2013 г.), XI Международной научно-технической конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации - Распознавание - 2013» (Курск, 2013 г.), XXVI Международной научно-практической конференции «Технические науки - от теории к практике» (Новосибирск, 2013 г.), II Международной научно-практической конференции «Техника и технологии: роль в развитии современного общества» (Краснодар, 2013 г.).
Публикации. По результатам исследований опубликовано 15 печатных работ, в том числе 5 статей в журналах, рекомендованных ВАК, а также получено 2 свидетельства о государственной регистрации программ для ЭВМ.
Личный вклад автора. Все основные научные результаты, приведенные в диссертации и сформулированные в положениях, выносимых на защиту, получены автором лично. Работы опубликованы в соавторстве с научным руководителем, которому принадлежат формулировка концепции решаемой задачи и постановка цели исследования. Лично автором проведено математическое моделирование диспетчеров задач с разделением во времени и в пространстве в составе многопроцессорных систем, разработаны компьютерные программы, обработаны статистические данные, проведены экспериментальные исследования, интерпретированы и обобщены полученные результаты, сформулированы выводы.
Объем и структура диссертации. Диссертационная работа состоит из введения, четырех разделов, основных результатов и выводов по работе, списка литературы и приложения. Работа изложена на 160 страницах основного текста, включающего 52 рисунков, 4 таблицы, содержит список литературных источников из 154 наименований и приложения.
Общее назначение и функции механизмов диспетчеризации потоков задач и методы их математического моделирования 17
Современные средства моделирования МПС строятся на основе трех различных концепций. К одной из них относятся сети Петри, известные методы аналитического моделирования которых позволяют находить тупиковые ситуации и доказывать способность системы возвращаться в исходное состояние (свойство достижимости). В настоящее время сети Петри и их расширения широко используются для моделирования подсистем диспетчеризации задач. Однако они обладают существенным недостатком: транзакты одного типа в сетях Петри неразличимы, что не позволяет получать времена их обслуживания. Кроме того, подобный аппарат не обладает достаточной наглядностью представления математической модели, что затрудняет в ряде случаев его использование для анализа сложных ВС, состоящих из множества разнородных объектов.
Другая концепция математического моделирования подсистем диспетчеризации задач в МПС основана на построении имитационной модели [50, 52, 63, 66, 144], в которой система представлена в виде совокупности устройств и множества связей между ними. На основе подобной структуры производится обработка случайного или детерминированного потока входных задач. Как правило, алгоритм обработки задается на специальном языке, например на GPSS. Языки транзактного типа обладают большей гибкостью, так как близки к языкам программирования высокого уровня. Они позволяют получать более точные данные о процессах функционирования ВС, так как осуществляют обслуживание каждого транзакта, однако для их реализации необходимо составить достаточно сложную программу, требующую большого количества машинного времени. Однако проведение исследований на имитационной модели затруднительно из-за сложностей, возникающих при изменении параметров моделируемой системы. Третья концепция математического моделирования подсистем диспетчеризации задач в МПС основана на аналитических моделях массового обслуживания [151, 152, 154]. Для аналитического моделирования в МПС широко применяются СеМО, включающие в себя совокупность связанных между собой СМО. Назначение такой модели состоит в оценке показателей производительности ВС в целом, или конкретного устройства (например, ДЗ) в частности, путем определения таких характеристик, как пропускные способности ресурсов, средние длины очередей к ним, коэффициенты загрузки, средние времена ожидания доступа к ресурсам, средние времена ответа. Кроме того важны такие общесистемные характеристики как пропускная способность системы, общее время ожидания в очередях и время ответа системы.
Если заданы параметры сети, то можно определить следующие характеристики каждой СМО и сети в целом:
Состояние рассматриваемой сети описывается вектором (a,,a2,...,an), где а11 - число заявок в г -й СМО. Если через р, (а,) обозначить распределение вероятностей того, что в установившемся режиме в г -й СМО будет находиться а, заявок, то распределение числа заявок в сети определяется произведением распределений по всем СМО определится согласно выражения р{щ,а2 ап) = р,(а,) р2(а2) р„(ап), где д(а,) - вероятность нахождения а, заявок в г -й СМО. Справедливость приведенного выражения была доказа на теоремой Джексона [22]. Произведение распределений вероятностей в этом выражении означает, что между отдельными СМО сети в значительной степени существует независимость. Это дает основание декомпозировать сеть на п независимых СМО.
Считается, что аналитическое моделирование является наиболее предпочтительным методом на эскизном этапе проектирования. Аналитические модели обычно представляются набором или системой уравнений, связывающих показатели производительности с параметрами решаемых задач и архитектурными параметрами ВС. Однако зачастую преимущества аналитических моделей реализуются путем их упрощения, для чего предпринимаются соответствующие допущения по отношению к структуре системы и рабочей нагрузке, что в некоторой степени ограничивает детальность и, следовательно, точность аналитических моделей. Аналитическое моделирование МПС в целом и их основных компонент с учетом особенностей диспетчеризации задач обеспечивают достаточно достоверное выявление «узких мест» и основных факторов, влияющих на производительность.
В ДЗ с разделением во времени присутствует явление перезагрузки кэшпамяти связанное с переключением задач, когда прерванная задача, например по истечении кванта, с высокой вероятностью может быть направлена для продолжения обслуживания в другой ПУ. Названное явление увеличивает частоту кэш-промахов и неизбежно приводит к снижению производительности МПС. Важным преимуществом ДЗ с разделением во времени, что он автоматически балансирует загрузку ПУ, обеспечивая тем самым высокую степень параллелизма.
В ДЗ с разделением в пространстве у каждого ПУ имеется своя очередь задач, причем ДЗ взаимодействует только с одним ПУ и его функция ограничивается выборкой очередной задачи и назначения ее освободившемуся ПУ. При прерываниях по истечении кванта времени (ПК) задача остается в той же очереди, в которой она находилась ранее. Таким образом, в ВС действует одновременно п ДЗ, в результате чего задачи выбираются из очередей бес конфликтно, поступают в ПУ параллельно, что создает условия для повышения производительности. Балансировка загрузки ПУ слабая, что приводит к «перекосу» в системе, когда часть ПУ может простаивать.
Для оценки показателей производительности в процессе диспетчеризации предложен подход, основанный на применении аналитических моделей n-процессорных систем с алгоритмами планирования задач по стратегиям разделения во времени и разделения в пространстве. Модели представляются в виде разомкнутых стохастических СеМО.
Многопроцессорная вычислительная система с единственным диспетчером задач, общей очередью требований на обслуживание с ограничением числа мест, бесприоритетным методом диспетчеризации
Определим среднее число ПУ ожидающих обслуживания ДЗ. Число приостановленных ПУ (Р,) из общего числа работающих со складывается из числа задач (/2), стоящих в очереди на обслуживание к ДЗ, и числа задач (г2), непосредственно обслуживающихся: Pt = /2 + г2. Число задач, занятых непосредственно обслуживанием, равно единице, если ДЗ занят, и нулю, если он свободен, то есть среднее значение г2 - есть вероятность того, что ДЗ занят, г2 = 1 - 7i0. Если вычесть эту величину из величины среднего числа ПУ, занятых обслуживанием, получим среднее число задач, ожидающих обслуживание /2 = ю- -(1-л0) = со-(1-л0)-(1 + \ (2.9) Рассмотрим интенсивности потоков задач в СеМО, включающей СМО Si и S2. Их можно представить следующей системой уравнений:
Интенсивности Хх и Х2 зависят от входящей интенсивности задач от источника 50 и вероятностей переходов из Sx в 52 (р2) и из 5, в 50 (рх0). Поскольку в СМО S2 возникают отказы в обслуживании, то интенсивности потоков Хх и Х2 будут снижаться:
Определим коэффициент передач [7, 54], показывающий сколько раз за X дача будет проходить через і-ю СМО. а, = —-, где Х: - интенсивность на вы 0 ходе /-Й СМО, Х0 - интенсивность источника задач. Поскольку каждая задача может получить обслуживание в г -й СМО в среднем а, раз, то соответственно время ожидания обслуживания и время ответа системы увеличится в а, раз. Приведем выражение для среднего времени ожидания задачи в очередях МПС W = alwl + a2w2, (2.14) где а,, сс2 - коэффициенты передач, показывающие сколько раз задача проходит через СМО 5, и соответственно; wp w2 - время ожидания обслуживания в очереди перед ПУ и перед ДЗ соответственно.
Во многих случаях на практике необходимо, чтобы задачи определенного типа обслуживались быстрее, чем требования других типов [24, 33, 127]. С целью обеспечения преимущественного права на обслуживания одних задач (в СРВ требования, которые необходимо исполнить сразу же после появления) перед другими, им присваивается различный приоритет. Различия в важности задач, их трудоемкости и требованиях к оперативности принятия решения приводят к введению приоритетных ДО. Задачи разного приоритета имеют, как правило, различную интенсивность поступления в систему. То есть на вход поступает неоднородных поток задач, что вполне соответствует реальным ВС.
Приоритеты задачам реального времени устанавливают и по остаточному времени решения (смотри раздел 1, алгоритмы RMS, EDF), чем меньше остаточное время, тем приоритетнее задача и по некоторым другим признакам. В приоритетной многоканальной системе (с п ПУ,) неоднородный поток задач, формируемый предварительным планировщиком, образует очередь перед ДЗ, который распределяет задачи на обслуживание по ПУ,. Он формирует потоки задач с интенсивностями Я,,,...,А, каждый из которых имеет
приоритет ki (i = l,...,g). Приоритеты задач распределяются следующим образом: 1 - сверхсрочные требования, реакция на воздействия которых должна быть незамедлительно, 2 -срочные требования, реакция на воздействие которых может быть не такой мгновенной, как в предыдущем случае, ..., g - задачи с самым низким приоритетом (например, фоновые задачи СРВ). Приоритет задачи уменьшается с увеличением номера потока запросов от ДЗ к ПУ. При таком распределении задач по ПУ не формируется очередь. То есть данная система является приоритетной, но с приостановкой обслуживания в случае, если все ПУ заняты обслуживанием задач. Системная программа, реализующая ДЗ, может быть выполняться как выделенным ПУ как, например, в ОС с ведущим, или управляющим процессором, так и в любом ПУ как, например, в ОС с симметричной обработкой [127]. Предварительный планировщик формирует очередь задач, ДЗ направляет их на обслуживание в ПУ. Если все ПУ в определенный момент времени будут заняты обслуживанием задач, другая пришедшая задача будет приостановлена, пока не освободится г -й ПУ. Схема такой модели приведена на рисунке 2.2.
Рисунок 2.2 - Схема многопроцессорной системы с общим диспетчером задач и приоритетным обслуживанием Аналитическими методами такую систему описать очень трудно. Нужны сложные преобразования и выкладки. Работы [24, 65, 99, 111, 112, 114, 126, 133, 142] дают некоторые представления о расчетах приоритетных многоканальных СМО. Решить такую сложную систему «на бумаге» можно лишь некоторыми приближенными методами. Такие методы оценки эффективности системы с п ПУ и общим ДЗ, приоритетным входящим потоком задач и их приостановкой, в случае занятости всех ПУ обслуживанием, будут подробно рассмотрены в подразделе 2.3, где представлен численный метод для оценки производительности МПС.
Диспетчеры задач в многопроцессорных вычислительных системах, основанных на системах массового обслуживания типа М/М/1, с однородным входящим потоком задач, бесприоритетным методом диспетчеризации и очередью с ограничением числа мест
В реальных ВС требования на обслуживание поступают, как правило, в случайные моменты времени. Распределение времен поступления и обслуживания может подчиняться определенным законам. В данном подразделе математическое моделирование системы производится на основе СМО типа М/М/1, по причине того, что это экспоненциальная СМО (поток поступающих задач является простейшим, длительность обслуживания распределена по экспоненциальному закону). При создании модели реальной ВС на основе СМО М/М/1 и исследовании ее будут получены предельные характеристики рассматриваемой системы. Такая модель дает наихудший вариант поведения ВС, при котором получают верхние граничные вероятностно-временные характеристики и гарантию работоспособности моделируемой вычислительной системы при заданных параметрах.
Программа для измерения временных параметров некоторых функций операционных систем
Комплекс состоит из двух программ: для расчета вероятностно-временных характеристик стохастических сетей массового обслуживания и для измерения производительности функций ОС.
Первая программа предназначена для анализа характеристик функционирования ДЗ в составе МПС. Вторая программа предназначена для получения параметров моделирования, а именно для измерения временных параметров функций ОС, таких как переключение контекста, системных вызовов и некоторых других.
ДЗ является частью МПС (своеобразный общий ресурс системы). Рассматривать его отдельно нет смысла. Мы рассматриваем ДЗ в составе МПС и исследуем его вероятностно-временные характеристики, которые полезны разработчикам на предварительном (эскизном) этапе проектирования ядра ОС. ДЗ представляется в виде СМО, совокупность которых (ДЗ, обслуживающие устройства (ПУ) и другие ресурсы ВС) образуют СеМО (вся МПС целиком). Поэтому для математического моделирования МПС создается специализированная программа для моделирования систем и сетей массового обслуживания (при помощи данного продукта можно исследовать различные ВС, которые можно представить в виде СМО типа М/М/1, М/М/п/к, MIGII, MIGInlk и систем с приоритетами).
Разрабатываемая программа для расчета вероятностно-временных характеристик ДЗ, представляемых СМО, предназначена для анализа характеристик функционирования ДЗ в составе МПС, представляемой в виде аналитических моделей устройств, каждому из которых ставится в соответствие одноканальная или многоканальная СМО [15, 67, 107]. Так как ДЗ является составляющей частью МПС в целом и представляется отдельной СМО, будем описывать его как часть СеМО [76,79].
Создание и вывод формы отчета Рисунок 3.1 - Схема алгоритма функционирования программы для расчета вероятностно-временных характеристик стохастических сетей массового обслуживания Характеристики отдельных СМО (устройств системы) и всей сети (МПС) в целом будут вычисляться перед сохранением в файл отчета по выражениям, представленным в разделе 2. Теперь определимся с языком программирования для написания программы. Он должен соответствовать следующим требованиям. 1) Наличие средств обработки больших массивов с вещественными данными; 2) Возможность решать математические задачи численными методами; 3) Простота работы с файлами 4) Возможность создавать программы с удобным графическим интерфейсом для ввода большого количества числовых данных.
Всем перечисленным требованиям отвечают многие современные языки программирования, но для решения поставленных автором задач была выбрана среда разработки Borland Delphi 7, отличающаяся широким набором встроенных математических функций, простотой синтаксиса языка программирования и наличие средств для работы с внешними файлами [9].
Промежуточные пользовательские и статистические данные инкапсулируются в отдельные классы, имеющие методы для безопасного чтения и записи данных [9].
В состав характеристик любой СМО (любого устройства в составе МПС) входят: - частота входящего потока задач; - время обслуживания в канале; - коэффициент загрузки канала; - коэффициент загрузки СМО; - длина очереди; - время ожидания задачи в очереди; - время пребывания заявки в СМО; - наличие ограничения длины очереди; - длина ограниченной очереди; - тип приоритета; - количество уровней приоритета; - промежуточные данные. 3.1.1 Разработка структуры данных Для стабильной работы программы необходимо определить формат и структуру входных, выходных и промежуточных данных. Информация будет храниться в файле. Опишем ее в виде таблицы.
Выше была обозначена последовательность действий выполняемых программой для решения поставленной задачи и бьша определена структура данных. Рассмотрим подробнее алгоритм работы каждого отдельного действия.
После загрузки программы на исполнение открывается окно для ввода структуры СеМО (рассматриваемой МПС, включающей ДЗ в своем составе). В дальнейшем происходит изменение конфигурации модели, ввод параметров отдельных СМО (ДЗ, ПУ, каналов ввода-вывода и др.), ввод варьируемых параметров. При запуске построенной модели МПС на исполнение проверяются введенные параметры на допустимость, если все они верны, запускается расчет характеристик по заданным параметрам.
Количество СМО добавляется автоматически по желанию пользователя. При вводе матрицы вероятностей производится контроль суммы по строкам матрицы, которая должна равняться единице. При вводе данных в визуальном редакторе между отдельными СМО проводятся связи и так же производится контроль суммы строк матрицы.
После ввода всей информации можно выбрать расчет по входным данным. Во время расчета происходит контроль существования стационарного режима, т. е. контроль коэффициента загрузки отдельных СМО (р 1). При нарушении условия существования стационарного режима вьшодится сообщение об ошибке показывающее, что коэффициент загрузки превышает единицу (указывается полученное значение) и ожидается подтверждение пользователем того, что информация получена После подтверждения расчет продолжается. После окончания процедуры расчета на экран выводится сводный отчет, в котором содержатся входные параметры, а так же характеристики СМО полученные в результате расчетов. Полученные данные можно сохранить в виде таблицы в текстовый файл, либо представить в виде графика, который сохраняется на диск в файл в виде картинки. C/ML-диаграмма алгоритма ввода начальных параметров и проверки их корректности приведена на рисунке 3.2.
Расчет характеристик диспетчеров задач с разделением в пространстве с бесприоритетным методом обслуживания и очередью с ограничением числа мест
Для определения адекватности использован метод имитационного моделирования в совокупности с корреляционным анализом характеристик базового и разработанного методов моделирования. Под базовым понимается метод моделирования СеМО, основанный на СМО с простейшими потоками задач, экспоненциальным временем обслуживания, неограниченной очередью заявок и бесприоритетной дисциплиной обслуживания.
Аналитическое моделирование. Для начала нужно рассмотреть базовый метод моделирования, чтобы определить относительно него адекватность разработанного в подразделе 2.1.1 метода. Характеристики базовой и исследуемой системы (быстродействие ПУ, время кванта, интенсивность входного потока задач, число ПУ, средняя загрузка ПУ и др.) одинаковы, отличием является общая очередь перед блоком ПУ (в базовом варианте она принята неограниченной длины, в варианте с общим ДЗ со стратегией разделения во времени - она ограничена, также отличительной особенностью является наличие ДЗ для устранения конфликтов за доступ к общей очереди задач перед блоком ПУ. Для проведения вычислительного эксперимента приняты следующие параметры, соответствующие реальным МПС: число ПУ варьировалось от 2 до 20; интенсивность входящего потока задач \ для задач с высокой реакцией варьировалась от 6,5 до 65 задач/мс (среднее время обработки на ПУ/ составляет 0,1 мс), интенсивность входящего потока задач Х0 для задач со средней реакцией варьировалась от 0,416 до 4,16 задач/мс (среднее время обработки на ПУ/ составляет 0,5 мс), интенсивность входящего потока задач А.0 для задач со средней реакцией варьировалась от 0,13 до 1,3 задач/мс (среднее время обработки на ПУ/ составляет 1,0 мс). Такие зна 102 чения интенсивностей обеспечивают среднюю загрузку ПУ на уровне 65% (РПУ=0,65); длина общей очереди в базовой системы принята неограниченного размера, в системе с ДЗ длина общей очереди принята равной 128 задач; среднее время работы ДЗ, учитывая время перезагрузки кэш-памяти и переключения контекста задач, составляет 0,015 мс.
Известно, что в СРВ имеется большой запас производительности ПУ, чтобы можно было решать задачи с низкой трудоемкостью (так называемые «короткие» задачи). При моделировании учитывалась трудоемкость задач: низкая или высокая, а также реакция на запрос. Низкая трудоемкость характерна для систем жесткого реального времени, когда задача должна быть выполнена точно в срок и, зачастую, с высокой скоростью. Низкая трудоемкость обусловлена либо небольшой длиной программы, либо высокой производительностью процессора. Трудоемкость задач варьировалась путем изменения времени обслуживания в ПУ. Считается, чем меньше время обслуживания задачи в ПУ, тем ниже её трудоемкость (выше реакция на запрос, что характерно для систем реального времени). Реакция на запрос варьировалась путем изменения величины кванта процессорного времени, предоставляемого выполняемым задачам. Считается, чем меньше квант, тем выше реакция на запрос.
Теперь исследуем нашу систему с ограниченной общей очередью и ограничением числа источников запросов ДЗ. Представим граф системы, приведенной на рисунке 2.1 (рисунок 4.1):
На представленном рисунке: S0 - предварительный планировщик - источник запросов, 5[ - процессорные узлы, S2- диспетчер задач.
Распишем полученное выражение (2.14) более подробно где w, - время ожидания в очереди перед процессорными узлами; щ - время ожидании процессорных узлов перед занятием ДЗ; р10 - вероятность выхода обработанной задачи из системы; рп - вероятность перехода задачи на обслуживание в ДЗ. Время ответа в системе с ДЗ и общей очередью задач в МПС u = (Wl+k-{tk+b)) Pn-(w2 + k-{z + q))_ Р Р = wl+k-(tk+b) + Pl2-(w2 + k-(x + q)) где к — число квантов на выполнение одной задачи; tk - длительность одного кванта; 5 - время, необходимое для перезагрузки кэш; д - время работы ДЗ, т - время, необходимое для переключения контекста (ПК).
Вероятности р10 и рп зависят от трудоемкости пришедшей на выполнение задачи (чем большей трудоемкостью обладает пришедшая задача, тем дольше она находится на обработке в ПУ, тем меньшее значение имеет вероятность выхода отработанной задачи из системы (pw) и тем большее значение вероятности (р12) возвращения на дообслуживание задачи в ПУ). При моделировании прохождения через систему трудоемких («длинных») задач значения р10 и рп задавались 0,1 и 0,9 соответственно. При рассмотрении задач средней трудоемкости значения принимались равными 0,16 и 0,84 соответственно. При моделировании поступления и обслуживания коротких (задач с самой маленькой трудоемкостью), р10 и рп принимались равными 0,5 и 0,5 соответственно. Все расчеты проводились в разработанной программе расчета стохастических сетей массового обслуживания STSET[120].
Были получены времена ожидания в очередях МПС с общим ДЗ с разделением во времени, времена ответа МПС с общим ДЗ, а также загрузка ДЗ от трудоемкости задач. Результаты представлены в виде графиков на рисунках 4.3 и 4.4.
Имитационное моделирование. Модель описывает процесс обработки задач в МПС. Время обработки каждой задачи выбирается при генерировании экспоненциально по значению интенсивности входного потока V Среднее время обработки задачи выбирается экспоненциально по произведению времени одного кванта (tk) на количество квантов (к), необходимых для полного выполнения задачи ПУ.
