Имитационное моделирование работы вычислительной системы из трех ЭВМ в среде GPSS

Имитационное моделирование работы вычислительной системы из трех ЭВМ в среде GPSS

Федеральное агентство по образованию

Пояснительная записка к курсовому проекту

по курсу «Моделирование систем»

Тема: «Имитационное моделирование работы вычислительной системы из трех ЭВМ в среде GPSS»

Екатеринбург 2008г

Содержание

• Введение
• 1. Построение концептуальной модели системы и ее формализация
• 1.1 Формулировка цели и постановка задачи машинного моделирования системы
• 1.2 Анализ задачи моделирования системы
• 1.3 Определение требований к исходной информации об объекте моделирования и организация ее сбора
• 1.4 Выдвижение гипотез и принятие предположений
• 1.5 Определение параметров и переменных модели
• 1.6 Установление основного содержания модели
• 1.7 Обоснование критериев оценки эффективности системы
• 1.8 Определение процедур аппроксимации
• 1.9 Описание концептуальной модели системы
• 1.10 Проверка достоверности концептуальной модели
• 2. Алгоритмизация модели системы и ее машинная реализация
• 2.1 Построение логической схемы модели
• 2.2 Получение математических соотношений
• 2.3 Проверка достоверности модели системы
• 2.4 Выбор инструментальных средств моделирования
• 2.5 Составление плана выполнения работ по программированию
• 2.6 Спецификация и построение схемы программы
• 2.7 Проведение программирования модели
• 2.8 Проверка достоверности программы
• 3. Получение и интерпретация результатов моделирования системы
• 3.1 Планирование машинного эксперимента с моделью системы
• 3.2 Определение требований к вычислительным средствам
• 3.3 Проведение рабочих расчетов
• 3.4 Анализ результатов моделирования системы
• 3.5 Представление результатов моделирования
• 3.6 Интерпретация результатов моделирования
• 3.7 Подведение итогов моделирования и выдача рекомендаций

Введение

Вычислительная система состоит из трех ЭВМ. С интервалом 3 ± 1 мин в систему поступают задания, которые с вероятностями Р1 = 0,4; P2 = P3 = 0,3 адресуются одной из трех ЭВМ. Перед каждой ЭВМ имеется очередь заданий, длина которой не ограничена. После обработки задания на первой ЭВМ, оно с вероятностью P12 = 0,3 поступает в очередь ко второй ЭВМ и с вероятностью P13 = 0,7 - в очередь к третьей ЭВМ. После обработки на второй или третьей ЭВМ задание считается выполненным. Продолжительность обработки заданий на разных ЭВМ характеризуется интервалами времени Т1= 7 ± 4 мин, T2 = 3 ± 1 мин, T3 = 5 ± 2 мин. Смоделировать процесс обработки 200 заданий. Определить максимальную длину каждой очереди и коэффициенты загрузки ЭВМ.

1. Построение концептуальной модели системы и ее формализация

1.1 Формулировка цели и постановка задачи машинного моделирования системы

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

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

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

ь максимальную длину очередей к каждой ЭВМ;

ь коэффициенты загрузки каждой ЭВМ.

Пересмотр начальной постановки задачи исследования не предусмотрен.

1.2 Анализ задачи моделирования системы

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

Экзогенные (независимые) переменные модели:

ь интервал времени поступления заданий;

ь вероятность поступления заданий на первоначальную обработку к каждой из ЭВМ;

ь вероятность поступления заданий на дальнейшую обработку к оставшимся ЭВМ;

ь продолжительность обработки заданий на каждой из ЭВМ;

ь количество заданий.

Эндогенные (зависимые) переменные модели:

ь длину очереди к каждой из ЭВМ;

ь коэффициент загрузки каждой ЭВМ.

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

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

1.3 Определение требований к исходной информации об объекте моделирования и организация ее сбора

Вся необходимая информация о системе и внешней среде представлена в задании к курсовому проектированию и не требует предварительной обработки.

1.4 Выдвижение гипотез и принятие предположений

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

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

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

ь третья ЭВМ прорешивает всегда больше заданий, чем две другие ЭВМ по отдельности.

Для упрощения модели можно выдвинуть следующие предположения:

ь время перехода задания от одной ЭВМ к другой равно нулю.

1.5 Определение параметров и переменных модели

Входные переменные модели:

v интервал времени (интенсивность) поступления заданий в вычислительную систему (ВС), tп tп, где tп - средний интервал времени между поступлением заданий в ВС, tп - половина интервала, в котором равномерно распределено значение, единица измерения - минута;

Выходные переменные модели:

v количество заданий обработанных на каждой из ЭВМ в заданные интервалы времени обработки заданий и вероятностями поступления заданий на них, NОЗ1, NОЗ2, NОЗ3, единица измерения - количество заданий;

v коэффициент загрузки каждой из ЭВМ, ZЭ1, ZЭ2, ZЭ3, единица измерения - относительная единица;

v количество заданий, которым пришлось ждать в очереди, вследствие высокого коэффициента загрузки ЭВМ в заданные интервалы времени обработки заданий на каждой из ЭВМ и вероятностями поступления заданий на них, NО1, NО2, NО3, единица измерения - количество студентов.

Параметры модели:

вероятность поступления заданий на вторую или третью ЭВМ после обработки на первой ЭВМ, РР2, РР3, единица измерения - %;

вероятность поступления заданий на первоначальную обработку к каждой из ЭВМ, РП1, РП2, РП3, единица измерения - количество заданий;

количество заданий, решенных второй или третьей ЭВМ в заданные интервалы времени обработки заданий на каждой из ЭВМ и вероятностями поступления заданий на них, NРЗ2, NРЗ3, единица измерения - количество заданий;

количество заданий, которые надо прорешать, NО, единица измерения - количество заданий;

интервал времени (интенсивность) обработки заданий каждой из ЭВМ, tЭ1, tЭ2, tЭ3, единица измерения - минута.

Воздействия внешней среды отсутствуют.

1.6 Установление основного содержания модели

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

1.7 Обоснование критериев оценки эффективности системы

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

1.8 Определение процедур аппроксимации

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

1.9 Описание концептуальной модели системы

Концептуальная модель исследуемой системы представлена в виде структурной схемы (рис. 1), состоящей из одного входного потока х - задания, поступающие в вычислительную систему, двух выходных потоков у1, у2 - задания, решенные в вычислительной системе на второй и третьей ЭВМ.

Целевая функция модели системы:

Рис. 1. Концептуальная модель в виде структурной схемы

В качестве типовой математической схемы применяется Q-схема, состоящая из одного источника (И), трех накопителей (Н1, Н2, Н3), трех каналов (К1, К2, К3), восемью клапанов (рис. 2). Задания в систему поступают от источника И с интервалом 3  1 мин в каждый из первых трех клапанов с вероятностями: клапан 1 - 40%, клапан 2 - 30%, клапан 3 - 30%. Клапан 1, клапан 2, клапан 3 управляются накопителями Н1, Н2, Н3, ёмкость которых LН1, LН2, LН3 не ограничена по условию задачи. С накопителя 1 (Н1), задания поступают в клапан 4, который управляется каналом 1 (К1). Аналогично с накопителями 2 и 3 (Н2, Н3), задания с которых поступают в клапан 5 и 6, управляются каналами 2 и 3 (К2, К3) соответственно. Обработка (задержка) заданий в каналах К1, К2, К3 занимает 7  4 мин, 3  1 мин, 5  2 мин соответственно. После обработки каналом 1 (К1), задания поступают на конечный этап обработки до решенного состояния с вероятностями 30% в клапан 2 и 70% в клапан 3. После вновь поступившие задания в клапан 2 и 3, управляются накопителями 2 и 3 (Н2, Н3), задания с которых поступают в клапан 5 и 6, управляются каналами 2 и 3 (К2, К3) соответственно. После очередной обработки (задержки) в каналах 2 и 3 (К2, К3), задания поступают в клапаны 7 и 8, где и уничтожаются, как полностью выполненные (решенные) задания.

Рис. 2. Концептуальная модель в виде Q-схемы

Формальная модель системы:

Q = {И, Н1, Н2, Н3, К1, К2, К3, NО, NОЗ1, NРЗ2, NРЗ3, кл1, кл2, кл3, кл4, кл5, кл6, кл7, кл8, LН = ? }.

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

1.10 Проверка достоверности концептуальной модели

Проверка достоверности концептуальной модели включает:

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

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

в) рассмотрение задачи моделирования: проходит через анализ по отдельным этапам, по которым выдвигаются начальные зависимости данных в задаче;

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

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

2. Алгоритмизация модели системы и ее машинная реализация

2.1 Построение логической схемы модели

Логическая схема модели представлена на рис. 3.

После генерации заявок в источнике И (блок 1) осуществляется распределение потока заданий с вероятностями 40%, 30%, 30% между накопителями Н1 (блок 2), Н2 (блок 3), Н3 (блок 4). В условии задачи емкость накопителя не ограничена, поэтому отказов в системе нет. После ожидания в накопителях Н1, Н2, Н3, задания поступают на обслуживание в каналы К1 (блок 5), К2 (блок 6), К3 (блок 7). Задание, закончившее обработку на первом канале не является решенным, поэтому поступает на ожидание последней обработки в накопители Н2 (блок 3), Н3 (блок 4) с вероятностным распределением 30% и 70% соответственно. Для того чтобы определить загруженность (или простои) каналов К1, К2 и К3, можно проанализировать статистические данные, касающиеся очереди перед соответствующими каналами. После обработки в каналах К2 и К3, задание поступает на удаление (блок 8 и блок 9) и покидает систему.

Рис. 3. Логическая схема

2.2 Получение математических соотношений

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

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

2.3 Проверка достоверности модели системы

На данном подэтапе достоверность модели системы проверяется по следующим показателям:

а) возможности решения поставленной задачи:

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

б) точности отражения замысла в логической схеме:

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

в) полноте логической схемы модели:

Проверить наличие всех выше описанных переменных, параметров, зависимостей, последовательности действий;

г) правильности используемых математических соотношений:

2.4 Выбор инструментальных средств моделирования

В нашем случае для проведения моделирования системы массового обслуживания с непрерывным временем обработки параметров при наличии случайных факторов необходимо использовать ЭВМ с применением языка имитационного моделирования GPSS, т.к. в настоящее время самым доступным средством моделирования систем является ЭВМ, а применение простого и доступного языка имитационного моделирования GPSS (http://www.gpss.ru) позволяет получить информацию о функции состояний zi(t) системы, анализируя непрерывные процессы функционирования системы только в «особые» дискретные моменты времени при смене состояний системы благодаря моделирующему алгоритму, реализованному по «принципу особых состояний» (принцип z). Кроме того, высокий уровень проблемной ориентации языка GPSS значительно упростит программирование, специально предусмотренные в нем возможности сбора, обработки и вывода результатов моделирования позволят быстро и подробно проанализировать возможные исходы имитационного эксперимента с моделью.

2.5 Составление плана выполнения работ по программированию

Выбранный язык имитационного моделирования GPSS имеет три версии: MICRO-GPSS Version 88-01-01, GPSS/PC Version 2, GPSS World Students Version 4.3.5. Micro-GPSS имеет DOS-интерфейс, который чувствителен к стилю написания программы (количеству пробелов между операндами, длине меток и имен и др.), не содержит текстового редактора. GPSS/PC лишен указанных недостатков, однако интерпретатор GPSS World Students имеет ряд преимуществ перед ним, например наличие интерфейса Windows, пошагового отладчика, возможность сбора и сохранения в файлах различной статистической информации, визуальный ввод команд. Поэтому для разработки модели был выбран именно интерпретатор GPSS World Students.

Для моделирования достаточно использовать ЭВМ типа IBM/PC, применение специализированных устройств не требуется. В программное обеспечение ЭВМ, на которой проводится моделирование, должны входить операционная система Windows (версия 9Х и выше) и интерпретатор GPSS. Затраты оперативной и внешней памяти незначительны, и необходимости в их расчете при современном уровне техники нет. Затраты времени на программирование и отладку программы на ЭВМ зависят только от уровня знаний языка и имеющихся навыков, которые были получены мною на лабораторных работах.

2.6 Спецификация и построение схемы программы

к программе на языке имитационного моделирования GPSS согласно спецификации программы предъявляются традиционные требования: структурированность, читабельность, корректность, эффективность и работоспособность.

Спецификация постановки задачи данного курсового проекта - определить максимальную длину очередей перед каждой ЭВМ (NО1, NО2, NО3) и коэффициенты загрузки каждой из ЭВМ (ZЭ1, ZЭ2, ZЭ3). В качестве исходных данных задаются интервал времени (интенсивность) поступления заданий в вычислительную систему, состоящую их трех ЭВМ (tпр tпр), интервал времени обработки заданий на каждой из ЭВМ (tЭ1, tЭ2, tЭ3), а также процент распределения заданий на одну из трех ЭВМ (РЭ1, РЭ2, РЭ3), процент распределения заданий на последний этап обработки на вторую и третью ЭВМ (РР2, РР3).

Спецификация ограничений на параметры исследуемой системы следующая: исходные данные должны быть положительными числами, кроме того, процент распределения заданий на одну из трех ЭВМ (РЭ1, РЭ2, РЭ3) и процент распределения заданий на последний этап обработки на вторую и третью ЭВМ (РР2, РР3), каждый по отдельности в сумме должен составлять 100%.

Схема программы (см. рис. 4) зависит от выбранного языка моделирования.

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

Оценка затрат машинного времени проводится по нескольким критериям эффективности программы: затраты памяти ЭВМ, затраты вычислений (идентичны времени вычислений при последовательной обработке), время вычислений («время ответа»). Форма представления входных и выходных данных определяется интерпретатором языка GPSS и изменить ее по усмотрению пользователя невозможно.

рис. 4. Схема программы

2.7 Проведение программирования модели