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

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

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

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

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

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

Содержание

Введение

Вычислительная система состоит из трех ЭВМ. С интервалом 3 ± 1 мин в систему поступают задания, которые с вероятностями Р₁ = 0,4; P₂ = P₃ = 0,3 адресуются одной из трех ЭВМ. Перед каждой ЭВМ имеется очередь заданий, длина которой не ограничена. После обработки задания на первой ЭВМ, оно с вероятностью P₁₂ = 0,3 поступает в очередь ко второй ЭВМ и с вероятностью P₁₃ = 0,7 - в очередь к третьей ЭВМ. После обработки на второй или третьей ЭВМ задание считается выполненным. Продолжительность обработки заданий на разных ЭВМ характеризуется интервалами времени Т₁= 7 ± 4 мин, T₂ = 3 ± 1 мин, T₃ = 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. Концептуальная модель в виде структурной схемы

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

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

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

Q = {И, Н₁, Н₂, Н₃, К₁, К₂, К₃, N_О, N_ОЗ1, N_РЗ2, N_РЗ3, кл₁, кл₂, кл₃, кл₄, кл₅, кл₆, кл₇, кл₈, L_Н = ? }.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В нашем случае для проведения моделирования системы массового обслуживания с непрерывным временем обработки параметров при наличии случайных факторов необходимо использовать ЭВМ с применением языка имитационного моделирования GPSS, т.к. в настоящее время самым доступным средством моделирования систем является ЭВМ, а применение простого и доступного языка имитационного моделирования GPSS (http://www.gpss.ru) позволяет получить информацию о функции состояний z_i(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 Проведение программирования модели

2.9 Проверка достоверности программы

На данном подэтапе последняя проверка машинной реализации модели проводится следующим образом:

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

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

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

На этом подэтапе необходимо также проверить затраты машинного времени на моделирование.

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

3.1 Планирование машинного эксперимента с моделью системы

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

Согласно выбранным критериям оценки эффективности системы и целевой функции модели выберем следующие существенные факторы:

х₁ - интервал времени (интенсивность) поступления заданий в вычислительную систему, состоящую их трех ЭВМ, t_пр = 3мин;

х₂ - интервал времени обработки заданий на первой ЭВМ, t_Э1 = 7;

х₃ - интервал времени обработки заданий на второй ЭВМ t_Э2 = 3;

х₄ - интервал времени обработки заданий на третьей ЭВМ t_Э3 = 5.

Зададим уровни вариации для каждого фактора:

х₁= 1, х₂= 4, х₃= 1, х₂= 2.

Составим матрицу плана полного факторного эксперимента

3.2 Определение требований к вычислительным средствам

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

3.3 Проведение рабочих расчетов

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

3.4 Анализ результатов моделирования системы

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

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

Результаты моделирования представлены в табл. 1, 2.

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

Таблица 1. Результаты работы устройств EVM1, EVM2, EVM3

Таблица 2. Результаты работы очередей EVMQ1, EVMQ2, EVMQ2